Accept-Reject Sampling : Data Science Concepts

Key Takeaways

[Music] hey everyone welcome back so we're filming this around the holiday so I got my holiday pajamas on so we can be fested and the uh topic of this video is going to be called accept reject sampling and sometimes people just call this rejection sampling so the last video we made on sampling from a distribution was a little while ago I'll post that video in the description and it was called inverse transform sampling so that was a method to sample from some distribution it's a cool method but the biggest issue with it by far is that we explicitly need the cumulative distribution function the CDF in order to do this method and for a lot of real world distributions either those that you're using in your research or your job or ones you're forming yourself you're simply just not going to have access to the CDF and even if you do another step in inverse transform sampling is to invert the CDF we need to take the inverse and that might be difficult even if you have it so this method except reject sampling is solving a lot of those issues at least starting two it's a method which you don't need the CDF for in fact you don't even need the full form of the PDF which is the probability density function so let's go on we're going to be working with a real world kind of example here let's say that you are the counselor for some department at a university and the students in this department normally take about four years to complete their studies and let's say that the way your department works halfway into their studies so two years in they take an assessment which tells us how well or how badly they're doing in their studies let's say this assessment can take any score s where this s is the score they get on the assessment between negative Infinity so more negative means they're not doing well and to positive Infinity higher values mean they are doing well and now let's say that the PDF the probability density function of the scores that students get on these exams is given by P of s so again to be clear P of s is a probability density function for S the score of the student that gets on the exam now we don't know p ofs and that's where this method starts to get interesting we do know however the numerator of P of s so P of s is equal to some numerator F of s so F of s is the function which is the numerator of P of s divided by NC NC stands for normalizing constant and now this is actually a very common thing that we see in probability and statistics especially as we get into research and work in these fields where we get this case where we often know the numerator of some probability density function but we don't know the denominator and why is that the case well if we think about this n C how would we compute it NC would simply just be the integral of the numerator between negative infinity and infinity that's how we Define these normalizing constants and so that form is given down here but if you think about taking the integral of this function which we haven't talked about yet but it already looks pretty disgusting if you think about taking the integral of this thing between negative infinity infinity doesn't look like a fun time often times it's not even possible oftentimes it's just really difficult so we often get this situation where we can easily get the numerator of the probability density function but we don't know the explicit form for the normalizing constant and that's the case we're going to be assuming in this video here so speaking of that numerator this is the form of the numerator we won't need to worry too much about it for this video we're just going to be talking about it in general but to talk about it a little bit we see that it's a piece-wise function so if the student's score is positive it's given by this sum of exponential functions if the student score is negative it's given by this slightly different sum of exponential functions and the graph is Loosely shown here so it looks almost symmetric but it's not because there's two different functions going on it looks almost normal but it's not again because it doesn't follow the exact form of a normal distribution so while it looks similar to a normal distribution kind of it's not the same and so we can't as easily sample from it which does beg the question now if we have this probability density function P of s but we don't explicitly know it we only know its numerator what hope do we even have of sampling from this distribution it seems like it's pretty hard slimpossible well let's move on here so how do we sample from P of s the next thing I'm going to do so I went through several iterations of this whiteboard trying to figure out the best way to convey this message and I think what I'll do first is show you the method so for the next minute or so just I'm going to show you the method but I promise to come back and explain it intuitively and show you why it works but first let's see how the method of accept reject sampling works the first thing we do is we sample from some other distribution G of s which is in some sense close to P ofs so the shape is similar to P ofs similar as we can make it and also we want this to be easy to sample from so to be more clear here G ofs only needs to satisfy two properties the first is that we can easily sample from it and the second is that it needs to span the same domain as our Target distribution so our Target distribution goes from minus to positive infinity and therefore the only two conditions we absolutely need for this different distribution GFS is that it is easy to sample from and it also goes from negative to positive Infinity this idea of being close to P ofs so the shape being similar to P of s is a big added bonus that's going to make our whole process more efficient as we'll see at the end of this video but it's not a requirement but since we were talking about how this is almost symmetric and almost normal I think the natural thing to use here is G of s being the normal distribution so that's what we'll use here and so if we plot F which is again this black curve here that's the same curve we saw on this side of the board a moment ago and we plot this green curve G which is the normal distribution then this is what they look like now the next step we need to do is ensure that the green line is always above the black line so we want to scale G up we want to multiply G by some large enough number such that it is always going to be above F which is that black curve so we're going to pick some number M such that for any value of s I choose so any value of s along this line If I multiply M and G together it's always going to be above F and now that we have all of this set up this is how accept reject sampling actually works so step one is to get a sample from G ofs again we said that that is possible because G ofs is easy to sample from so we're going to Boop get a sample from G ofs that could be anywhere it could be here it could be here it's going to be more likely in places where G ofs has a higher density and less likely in places where G ofs has a lower density naturally so that's step number one and step number two is we're either going to accept this sample or reject this sample we accept this sample s with some probability given by this formula which is f of s s being the thing we just sampled from G divided M * G of s and now just a quick note how do we know that this thing can be interpreted as a probability how do we know it's bounded between zero and one well that comes back to why we did this transformation of multiplying G by some big enough constant M because we know that this form M * G of s which is exactly what we see in the denominator here is always going to be above F of s which is the numerator here so this is safely assumed to be interpreted as a probability it's bounded between 0 and one okay so no issues there so again the process is pretty simple once you have this set up you simply just keep getting samples from G ofs and for each sample you compute this acceptance probability and then you simply just choose to accept or reject that sample you just got with that probability and so as you go through this method you'll have a bunch of samples going to the accept pile which is this green bar I visualized up here and other samples will go into the reject pile if they don't meet that probability which is that reject pile over here and then after some stopping condition however many samples you want to get you're going to stop and the samples that are in the accept pile so all of the samples that you've accepted through this process are very mysteriously right now actually going to be as if you sampled from P of s itself now I want to pause here and say that when I first learned this when I first learned the method it seemed like magic it didn't seem like it should work it doesn't seem like there's anything in it that inherently really has to do with P of s so how can we say that all these things that we've accepted are actually a draw from P of s and so how I'll do it first I'll prove it to you mathematically but that's usually not enough for me to really understand it from first principles so after we prove it mathematically I'm going to go back and talk about more intuitively why this works what we want to prove mathematically is if we look at all of the samples that we have accepted in this process so if we look at all the samples that are in this green accept bar up here then we want to show that the density of those samples is actually P of s if we can show that that proves that all the samples in there are samples from P of s so we'll start by asking what is the density so this capital D is just kind of a standin for a density if you want you can think of it as a probability symbol I want it to be a little bit clear here and where densities are not exactly probabilities but if it mentally helps you just replace all these Capital D's by probability symbols you'll get the same intuition so the density of a sample given that that we have accepted it okay that's exactly what we're after right now we're going to use a little bit of Baye theorem here so whenever we have a conditional we can write it as the combination of the following terms the first one being the probability of accepting a sample given the value of the sample is little s times the unconditional density of that sample little s all divided by the probability that we accept a sample again unconditional so getting from here to here is just using base theorem so now we can actually get some good forms for all these components so first of all what's the probability of accepting a sample given that its value is little s well we literally know that's equal to this formula that's how we constructed the process so we're going to put in F of s divided mg of s for that term now what is the unconditional density of getting the sample little s in the first place well that's just the probability or more specifically the probability density that our different distribution G would give us that sample back and so that would just be G of s and that's all divided by the probability that we accept a sample unconditionally so the only difficult thing to compute now is what's the probability that we accept a sample unconditionally and we're going to work that out here it's not too tricky so we're asking about what's the probability that we accept a sample unconditionally so it turns out this can be written as an integral because notice there's no conditional on here so we need to go over all the different possible samples from negative Infinity to infinity and ask about what's the probability that we would get this and accept this and the first part that I just said the probability that we would get this sample that it would emerge is exactly the probability that g would suggest this sample which is G of s so that is the probability that we would get proposed this sample and given that we're proposed that sample what's the probability that we accept it that is again the same form here F of s divided mg of s or the acceptance probability now we get this nice cancellation of G of S and G of s so this integral simplifies to 1/ capm integral of f of s DS from negative Infinity to Infinity seems a little bit tricky but have we seen that form before well that is exactly the formula for the normalizing constant so it turns out interestingly enough that the probability of accepting a sample using this method is given by normalizing constant whatever that is divided by Big M Big M again being the thing that we multiply G by to make it always above F and now completing this formula so let's bring this down here we see that density of s given except is equal so what so this G and this G will actually cancel so the numerator is just F of s / m f of s / M and the denominator is the probability of accepting which we just said is normalizing constant divided M normalizing constant divided M these M's also cancel out and mysteriously magically enough we get back that the density of getting a sample given that we accepted it is equal to F of Sid normalizing constant which is exactly P of s which is exactly P of s we have just proved mathematically using the still mysterious method where we use this different distribution G to get candidates and accept them with this probability here if we do that we are exactly going to be sampling from P of s so this works this mathematically is sound it works but if you're anything like me you're not satisfied at this point because we don't really understand why it works what's the intuition behind it and so let's talk about that next so I think the key in intuitively understanding this method is hidden in this board and let me highlight the place that I think is the most important so this ratio here F of s divided G ofs Let's ignore the M for a second we'll bring that back in what does that ratio F of s divided G ofs inherently mean well let's think about if that ratio was very high if that ratio that I just circled was very high that means the numerator was very high and the denominator was low if the numerator is high that means that the sample we are talking about is very likely in the distribution P because P and F are proportional to each other so if there's a value of s such that f is very high that means that value of s is actually very high in P of s as well so if the numerator is high it means that it is a sample that is very very likely if the denominator is low that means that it's a sample that is very rare in G ofs it has a very low density so what would you say if I told you that here's a sample that is very likely in your target distribution but is very unlikely in your proposal distribution or your candidate distribution G well my first instinct would be accepted accept it we might not see it again because we only see samples if they are proposed by G and if this G is very low for that sample we might not see the sample again for a really long time so let's jump on it and accept that sample now we need it and that's where the intuition comes in because High values for this ratio imply that this is a very important sample important because it's rare to get proposed and also because it's very high probability in our Target distribution that leads to very high probabilities of accept which is why this is exactly the form of our ratio and this Big M is just there so that this F over G can get interpreted as a probability because F over G can be higher than one arbitrarily higher lower than one so m is just there to scale everything down make sure that we can interpret this as a probability but the main point I want to get across is that the thing I've Circle F / G is exactly the quantity that is driving this whole process if FID G is high these are samples that are very rare to get proposed but if they get proposed they're extremely common in our Target distribution so we should accept them if F divided by G is low that means these are samples that are very commonly proposed G is high and F is low which means that they don't actually occur too much in our Target distribution so we don't care too much about accepting them so once I saw that link I think the process process made a little bit more sense to me where some different distribution G is throwing samples at us and we are accepting them based on this ratio here M just being a normalizer and so that's acceptor reject sampling and the last thing I'll talk about is just an issue that people commonly face in acceptor reject sampling and that is the choice of G of s as we said here we used a normal distribution because it was sort of similar to this and it was an Easy distribution to sample from but even though I framed this as kind of a real world problem real world distributions are usually even more complex than something that is kind of nice looking as this for example if this black line this crazy squiggly black line was your F then we need to go through the same steps if we want to use the normal distribution again we need to multiply the normal distribution by some big enough constant M so it's always going to be above this and that wouldn't really be a problem except for this terrible Spike that happens in F which means that we need to scale the normal distribution up so much that it's going to be above this Spike what that means is that m is going to be huge because we need to multiply the normal distribution by a very large number to always be above F and what does it mean if m is huge well look at this probability of accept that was normalizing constant divided by m if m is massive then this quantity becomes very small so the probability of accepting a sample goes towards zero what that means for our process is that g is going to keep proposing us samples hey do you want to accept this do you want to accept this but because our M was so large our probability of accepting any of those samples is extremely low very close to zero so this process is going to take a very very very long time in order for us to get however many samples we need to get so although this algorithm this method that I've proposed seems pretty similar it's just a two-step process the real heavy lifting and the real creative work if you choose to use this process come before that and choosing a g that is similar sort of to your target distribution which isn't a problem if your target distribution looks nice but is potentially a problem if your target distribution looks kind of disgusting like this so This choosing your G is a big art and if you do it wrong you're going to lead to very inefficient process here okay so that was accept reject sampling or sometimes it's called just rejection sampling hopefully um I've showed you a couple things I've showed you why we need it instead of inverse transform sampling many times in the real world I've showed you how it works I've showed you mathematically that it works but most importantly hopefully you understand now intuitively why it works and it all comes down to this F overg ratio okay so if you learn something please like And subscribe any comments are always welcome below and I'll see you next time