Scaling Bayesian Experimentation

Scale By The Bay 2018: Robert J Neal, Paul Cho, Scaling Bayesian Experimentation

Recording: Scale By The Bay 2018: Robert J Neal, Paul Cho, Scaling Bayesian Experimentation

you great thanks for coming I just want to start with a quick survey how many of you have beliefs you believe anything at all good and then how many of you when you get some data that maybe isn't consistent with your belief you update your belief oh it should be more of you but ok good looks like we've got some internet trolls that didn't raise their hand cool so yeah it's basically what Bayesian it's Bayesian statistics is and that's what we'll be talking about today so first of all motivate a little bit about why we want to use Bayesian experimentation there are some challenges with it and these are reasons that people have avoided using Bayesian experimentation and have mostly used frequentist experimentation so we'll talk about those one is where do we get priors and then whether or not it's gonna be fast enough and generally we can if we can find a generally applicable solution to generating bayesian posteriors I want to breeze through this pretty quick because the meat of it is really a statistical method we use called bootstrapping and how we can do that efficiently so Paul we'll be talking about that and then you know as you all know these talks are very short so Q&A will probably be like in the halls or over lunch I would probably won't have time in this room cool so why Bayesian experimentation there's a bunch of reasons I've only listed three here one is that Bayesian statistics give you a little bit more natural interpretations of the data it's a little bit harder for laypersons to understand some of the interpretations of frequency statistics it also gives you a sequential updating automatically I mean that's just a natural feature of Bayesian statistics whereas if you do something so in frequentist experimentation there's often a problem of peaking where if you look at the data too much you have to apply corrections to it well you get that sort of for free with Beijing experimentation and it's all well so it's also well suited for optimization problems so you'll see this Bayesian posteriors used a lot in multi hour bandits for sampling with different arms and military payments nonetheless there are some challenges a one is how do you come up with priors so in order to get a posterior you need priors and for a long time Beijing's used non informative priors which was sort of a cop-out but more and more you see people thinking that you really need you really need a motivated priors to use Bayesian experimentation our Bayesian statistics to its fullest so additionally like let's say you do have priors for a particular metric coming up with priors for all these different metrics can be a lot of work because they're all parametrize differently and then even if you come up with priors you might wonder like well can we efficiently compute the posterior as for all these metrics so these are some of the challenges we set out to solve the first one is where do we apply errs and just to make sure everybody on the same page because I know not not everybody's Bayesian I'm gonna talk a little bit about what what priors are so I'm gonna start with this guy Peter Griffin who has this belief so priors are just prior beliefs stuff you believe before you have data so you know Peter might think well there's something like a 30 to 50 per chance that'll thirty to fifty percent chance that he'll bring tomorrow so that's his prior belief and then he gets some data so the weather forecaster says look there's an 80% chance it'll rain tomorrow so now you have the prior and you have this data well you should update your belief you should say okay well given that depending on how strong your prior was you say something like there's a 60 to 80 percent chance that will rain tomorrow so that's the general process representing it as distributions again on the left is the prior so it might be centered around like 0.4 you get some data and then depending on how strong your prior is you update your posterior which is a mix of the prior and the data the data is the easy part we all have data so today we'll be talking about how to get priors and and posteriors this is just an obligatory slide that shows base theorem every Bayesian talk has to include this theorem it's the it's a Bayesian law so then okay so that's what priors are how do you come up with priors for experimentation I'll talk a little bit about why it's challenging so imagine that you just have one metric and its revenue and it's distributed like this so you have a lot of people who don't convert so revenue for those people is zero and then you have some distribution the rest of the distribution is like actual from from people so you might wonder like well how do i model that so maybe you can come up with some probabilistic function that says you know there's some probability P that people will convert or not that's the Bernoulli trial and then if they don't convert obviously revenue 0 that's easy if they do convert revenues a random distribution from a gamma distribution with some parameters say alpha beta so so you have these parameters from which the data is generated from which you're sampling from the population and you need to come up with priors so the first thing you need is a prior on P so what is the chance that somebody actually converts and that prior is going to be represented as a distribution because you don't know exactly what that P will be but you think will be within a certain range so you express that as a distribution and then the Tildy here is just it means that we're we're getting a random draw from from that distribution and then we also need a prior for the gamma portion of the distribution so for the alpha and beta parameters and those alpha and beta parameters will be distributed from some some prior that we have so that's our prior so that's pretty straightforward you know we can do that pretty pretty straightforwardly but now we need to do it for all these different metrics that our project manager says they care about right so every project manager will say hey I want a metrics dashboard with tens of thousands of metrics because they're all important so the problem is that these different metrics have different distributions and those different distributions have different parameters so then you have to come up with priors that all have these different types of parameters and that's not that's not straightforward this is a actual video of a project manager asking me for more metrics on the dashboard it doesn't go well so there's a pretty straightforward solution to this it's the same thing that you would use in null hypothesis significance testing so we know how to present the null hypothesis significance testing so for example t-test what you do is you actually don't look at the parameters of the distribution you look at the metric of interest so if you're using a t-test you're actually wondering like what is the distribution of of my mean my population mean given this data and then you ask for the variant so you have this distribution of that's distributed as a student T distribution you have this distribution of means for the control and then you want to know well is my variance different that's sort of statistical significance is it statistically different so you're asking is that variant mean within the 95% confidence interval of that student T distribution so it looks sort of like this if your variant mean falls within there then it's not statistically significant if it falls outside of there it is statistically significant so that's the problem or that's that's the way that the frequentist approaches it and it works really well for all types of distributions you know you might hear that there's an assumption that for a t-test the underlying distribution is normal but actually it's pretty robust for for all types of distributions with large enough sample size so it turns out you can actually do the same thing with Bayesian priors so with Bayesian priors you can actually look at the metric of interest the the means for example you know that that's going to be normally distributed because the central limit theorem so the nice thing about that is before when we were saying well look all of these different distributions have all these different parameters a normal distribution always has the same parameters regardless of the underlying distribution so whatever the distribution is on the Left whether we care about revenue or clicks it doesn't matter how that's distributed the means of that are going to be distributed normally so the nice thing about that is the parameters will always be just the mean and the standard deviation of that distribution and so your priors can always be represented as a normal distribution and say inverse gamma for the standard deviation moreover there's some interesting data so Ronnie Kay has a paper where he talks about a meta-analysis of experiments across a bunch of different companies like Microsoft and Netflix and it turns out that most experiments actually don't have have any effect at all so this is a good way for you to form a prior belief about what a new experiment what effect it will have and you're probably really should be that most experiments aren't going to have any effect at all so what that means is that if you look at that normal distribution in the top right the mean of that can always just be set to whatever the mean of the control is so that's that should be your prior belief that there's actually no difference the control in the variant and then you can get the parameters for your your inverse gamma distribution just from historical data that's really just the variance of the of the sampling mean the sampling distribution of the means so that's that's the solution to where do you get your priors the nice thing is it's generalizable and scalable and you don't have to worry about handling it for a bunch of different metrics and so another question that people have is is Bayesian experimentation fast enough and generally applicable and one of the reasons they ask this is that there's a way to compute priors for for distributions called Markov chain Monte Carlo processes if you're interested in that I saw that IV from stripe is going to be doing a talk at 1:10 I'll be there it sounds really interesting but the problem is that that process is actually computationally quite expensive and fairly slow so we've answered the question like how do you come up with priors and now the question is can we efficiently compute the posterior for all these metrics the nice thing about using a distribution of means is that we don't have to compute the posterior with MCMC because that's fairly expensive because it has something called a conjugate prior so the normal distribution is something called a conjugate prior which has a closed form solution to computing the posterior so the nice thing about that is that our data is normally distributed so our prior to get from our prior plus our data to our posterior it's actually really fast so we don't have to do some random sampling like you do it in Markov chain Monte Carlo simulations we can actually just run it through our closed form solution and get a really a really fast answer to what our posterior distribution is so one other thing that I'm going to mention is why we're using bootstrapping so for the data there are a few reasons that you might want to use bootstrapping in to get your your distribution of means for your data so there's different different papers on why this is the case but some of them are related to like model miss specification or non independence of bandit arms so we want to use our experimentation system we use it both for like traditional a/b experiments as well as bandit type experiments and we want to make sure that our approach is generalizable so bootstrapping is an important way for us to get good estimates of our sampling distributions but bootstrapping is a little bit expensive so it's not as expensive as MCMC it's a little bit expensive so we've done a lot of work on trying to make that more efficient so that we can make our experimentation pipeline run run faster fast enough so that you know our product managers don't come ask us when the experimentation pipeline is going to finish running so that's what Paul is going to talk about all right so so I'm going to talk about what bootstrapping is and some of the ways that we've tried to overcome its computational costs so to illustrate bootstrapping let's say that we had some sample data for an experiment so each letter here is supposed to represent a revenue value for a given visitor in our experiment so to generate a bootstrap sample we will sample from this data set with replacement seven times so the same number of times as the size of our original data and we're doing this with replacement so once we have that sample we compute whatever statistic that were interested in so in this case we might look for the mean of our revenue and then you repeat this process a large amount of time so you want to you want to repeat this procedure as many times I was required to have a sufficiently precise estimate of your sampling distributions so this result here is a collection of values that represent your sampling distribution and you can generate some properties of that distribution for your analysis so here's that same procedure just in words so as you can tell this it's a very computationally expensive procedure generating thousands of food it takes a long time and when we're talking about the scale of online experimentation the datasets are so large that they don't fit in memory usually so this is kind of like a classic big data problem so we set set out to tackle it using spark and you know spark is as you know it's it's useful for handling large amounts of data and processing it in parallel across multiple machines but as we were approaching this problem of implementing bootstrapping using spark we quickly realized an issue with the way that tip spark is typically used so just to illustrate let's say that we had our data in this RDD usually what happens is you you partition your data and tasks on those partitions are distributed among your workers so we thought ok how can we generate a bootstrap sample in a way that's distributed using spark a natural way to think that you could do this is by saying why don't we just generate a fraction of the samples required from each partition so say we have seven partitions we can generate n over seven samples where n is the total size of your original data set you do this for all your partitions and if you combine them combine them you have a full bootstrap sample so this doesn't work and the reason why it doesn't is because this is this doesn't actually count as bootstrapping so remember that when we're bootstrapping we have to sample with replacement so each draw should be completely independent so a way to check to see whether it's a valid bootstrap sample or not is to see if their procedure is such that it's possible to generate a sample where where every sample is the same value so that should be possible if we're actually sampling with replacement but it isn't here so we kind of considered other ways to distribute this work but there were issues with those as well so we thought of okay what if we can compress our data set so that each worker in our cluster can generate the bootstrap samples independently and in parallel so we could use the feature of spark broadcasting where you take a where we could take our compressed data set broadcast it to all our nodes and so that the data set is available available for all our workers to generate the bootstrap samples in parallel so as we were thinking about how can we compress our data set so that it fits in memory as well as so that we can sample from it in a way that has the right properties we realize that our experiment data has a very low cardinality compared to so it has the number of unique revenue values is quite small compared to the size of the original data set so that's typical for an online marketplace like you mean and most of them are actually 0 cos conversion conversion rates are typically low in online marketplaces so so what we decided to do was oh the idea that we had was to compress the data by constructing a frequency distribution and sampling from that distribution so to illustrate we have some example fake data here where on the Left we have some visitor identifier and then on the right is the metric value for that visitor in a particular variant of an experiment so we do here from that we construct a frequency distribution so here on the left is our all the unique values that occur in our data set and on the right are the counts of each of those unique values so just one thing to note that this this collection is sorted by frequency and descending order that'll become important later as we talk about how we sample from this but at this point we were able to compress our data small enough to fit in memory for all our experiments so now how do we sample from this data so to do that we then crunch a collection of cumulative frequencies so each entry in this collection the cumulative frequency is the sum of the previous cumulative frequency plus the current frequency so yeah and so that so the last entry of this collection should be the least frequent number because we've sorted by frequency and then the cumulative frequency of that final row should be n the size of the original data set so now these cumulative frequencies can represent the upper bound of the range of indices that represent the value on the left so now a sample from this this collection we just sampled by we draw a random index from 0 to n minus 1 and then we retrieve the value by checking which range the index falls into and then we take that value out so some things to say about this approach so well the way that we chose to do this was by starting from the top and checking to see if it falls under that range and if not go on to the next one until you get to the right range of indices and then retrieve your value that way so in the worst case if we choose if we randomly sample an index n we have 2 or n minus 1 I should say we have to traverse the entire collection to retrieve that value but actually most of the time and this is why the sorting by frequencies is important because because most of the time we're actually spending around the top of a collection and if you were to construct it or plot the distribution the complexity the time complexity is is the expectation of this distribution of your unique values so there are some assumptions about the sparsity and distribution of your value of your data for this approach to work and there's other optimizations you can make so if that tail is like really really long you can use a binary search tree instead and but yeah so this is this is what we have in production our analysis pipeline today and it's working fine for daily batch processing yeah so the other thing that I wanted to talk about is just kind of like an idea that we have for doing this faster so currently we're sort of limited to daily batch processing and what we do challenge that we have with bootstrapping is that every time the data is updated say a new visitor is added to an experiment or the metric for a particular visitor changes we have to kind of scrap all the work that we did before and start from scratch with the bootstrapping to estimate the sampling distribution so we kind of thought about is there a way that we can update our bootstraps so to illustrate this idea let's say we had an experiment that just started and six visitors were added to the experiment so to generate a single bootstrap sample again we sample with replacement six times so let's say we did that and then three new visitors were added to the experiment minutes later let's say so what we do today we kind of scrap all the work we did before and then start over we we sample nine times with replacement from this full data set but is there a way that we can update the previous lis bootstrapped sample to reflect the addition of our new visitors so we can ask okay if I went back in time what is the probability at each step of the sequence of random samples that I would have drawn from one of our new visitors so that probability is three out of nine right so we can do is we can conduct a Bernoulli trial at each slot in the sequence to see whether or not we would have actually chosen a new visitor so we could do that and let's say that the only success was at the second slot and we replaced that with a random draw from our set of visitors and then for the remaining three slots we just draw from the the full data set from all nine visitors so this is a way that you might be able to update bootstraps to reflect new data and actually we don't have to conduct all these each Bernoulli trial for each slot of this sequence because the distribution of an independent Bernoulli trials is has a known distribution called the binomial distribution so actually we just have to draw once from the binomial distribution where n is 6 the size of the original data and then P is 3 over 9 so the size of the new the set of new visitors divided by the full data set so this is kind of just a way that we thought that we can an approach that we can go with to be able to update our analyses faster by updating our bootstraps there's a lot of work that still needs to be done obviously this is just the ideas all we have basically there's a lot of open questions that we have namely how do we store efficiently store and persist our our bootstrap data which is something that we're not doing today but yeah that's that's something that we're working on and we love to hear ideas that you might have yeah I'm gonna hand it back to Robert to wrap it up ok cool just to recap so we covered why bayesian experimentation some of the challenges like where do we get priors and is it fast enough and generally applicable and then can we make it faster like Paul said we're working on some techniques for being able to do like real-time processing where experimentation data which you can't really do if you're bootstrapping full full data sets so we have some resources we've just started open sourcing our statistics libraries they're written in Scala they're very early stages so if you're interested in contributing that would be great the the techniques that Paul mentioned with cumulative live frequencies we have that in a our spark statistics library so you could start using that today and then we plan to roll out more bootstrapping algorithms like the more real-time bootstrapping algorithms as we develop them also if you're interested in working on these sorts of things Vietnamese hiring so go to that link if you're interested in that and then you know feel free to grab us in the hall oh also on our data engineering blog we have a couple posts about bootstrapping so Paul goes more into depth about stuff he was talking about today so feel free to visit that as well and then you know grab us in the hall or at lunch if you have questions [Applause]