Rejection Sampling - VISUALLY EXPLAINED with EXAMPLES!

This tutorial explains the Rejection Sampling algorithm using a difficult to sample univariate distribution function.
#sampling
#montecarlo
#statistics
If you prefer to read, I have written an article on this algorithm here -
towardsdatasci...

[@rfhp1710]

Rotating the plots is a stroke of genius, things clicked instinctively. You are a gifted content maker. Keep making videos.

[@KapilSachdeva]

Thanks 🙏… finally someone saw the rotated plot and understood its significance … I am happy now :)

[@partha95123]

Indeed Kapil ji is an artist! I'm writing my thesis with his videos as inspiration.

[@KapilSachdeva]

You guys are so kind. Many thanks for the encouragement. @adithyanssathish5485 would love to read your thesis when it is ready.

[@partha95123]

Yes Kapil ji. I will send an invite to public part of my thesis defence for a duration of 30 minutes.

[@chriskindler10]

that's actually a terrific explanation

[@KapilSachdeva]

🙏

[@prajwalchauhan6440]

Best explanation for this topic on KZbin. I wonder how you even came up with this. Genius

[@KapilSachdeva]

🙏

[@yli6050]

Watching your videos keeps reminding me of the phrase “a picture is worth a thousand words”, to which I want to add “ a great picture is worth thousands in gold”. Many times I had to freeze the video to let a particular moment sink in, because I couldn’t believe the insight that picture brings out . ❤❤❤

[@Lyr4s3L]

You just saved a college student living in South Korea! Thanks for amazing visualization and explanations!

[@KapilSachdeva]

🙏

[@julialikesscience]

this brilliant change of viewpoint helps to explain the method in a much simpler way!

[@KapilSachdeva]

🙏

[@drewburns7805]

Fantastic explanation! Best video on this subject I've seen so far. Saved me lots of time searching for clarification. Thank you!

[@KapilSachdeva]

🙏

[@alonsomadronal2919]

Such a Masterpiece of a video, thanks for the explanation!

[@KapilSachdeva]

🙏

[@sudhagarraghavan9696]

Excellent video and clearly explained ! Hope you can also do tutorials on other MCMC sampling methods such Gibbs Sampling, Metropolis-Hasting and Hamiltonian !

[@KapilSachdeva]

coming soon :)

[@YogeshYewale-i3m]

Excellent explanation ever on rejection sampling

[@KapilSachdeva]

🙏

[@hiiiqwq5833]

This is sooo helpful! Totally addressed my concern!! Thank you!

[@KapilSachdeva]

🙏

[@dhimanbhowmick9558]

Thank you for your hard work, which enables us to understand crystal clear. Thanks a lot ❤❤❤

[@haihoangthanh8949]

thank you for your detail and understandable explanation. The video animations are great and impressive.

[@KapilSachdeva]

🙏

[@MarcusRosenberger]

Thank you so much! Your video really helped me understand the method and remember it, which is equally important. 🙂

[@jeexika3207]

What a wonderful explanation

[@korntantiwanit]

Thank you for your explanation, nice presentation!

[@KapilSachdeva]

🙏

[@ilke3395]

Thank you so much sir for the amazing explanation and visualization.

[@KapilSachdeva]

🙏

[@olivier306]

Legendary video man thank you!!!

[@KapilSachdeva]

🙏

[@cjhhong]

Thank you so much. I now understand the concept better.

[@KapilSachdeva]

🙏

[@corradoforza]

Thank you so much for this video, it is very clear and makes rejection sampling easy to understand

[@corradoforza]

Could you make one on copulae? tks

[@KapilSachdeva]

🙏

[@abhijitharakali]

Kudos for explaining very well. I wish to comment on just one thing. @12:08 I could not see the two colors (red and blue) clearly in the video. Maybe the picture can be made to have white background to make the colors more obvious.

[@ankushkothiyal5372]

Thank you, I understood clearly.

[@KapilSachdeva]

🙏

[@cello9834]

thank you so much , very well explained !

[@KapilSachdeva]

🙏

[@sujatharamakrishnan]

Thank you for the very clear explanation of the rejection samling method?.I want to compute the acceptance rate for a specifice probem. Could you define what is the acceptance rate?

[@baongocsen5768]

Thank you very much for your video. But I have a question: when g(x) is a function U(a,b), the probability of choosing Y which obeys g(x) is the same for all Y in (a,b). But when the bounding function is Gaussian or something else (i.e. when simulating g(x) we cannot guarantee the probability of selecting each point is the same), does it affects the probability of selecting X which obeys f( x) ? ( Because if the simulation of Y is not equivalent then even if the next steps are effective, we cannot guarantee that we give equal chances to all points X when starting before "reject or accept")

[@jahanvi9429]

thank you, very well explained!

[@KapilSachdeva]

🙏

[@leilanifrost771]

That was a great video! Just wanted to ask how you would approach scaling the proposal distribution if you don't know the parameters of the target distribution?

[@KapilSachdeva]

In that case you would not use Rejection sampling. You would want to use an algo like metropolis Hastings, HMC etc

[@pcaltd.1824]

Lovely video. If you do not know what the target function is, how can you obtain C and how can you ensure the envelope function is not exceeded by the value of the target?

[@KapilSachdeva]

Sorry for the late reply. My understanding is that for Rejection sampling you need to know the function as this is how you will evaluate f(x) (f is the target distribution). Finding the good envelop - This is the challenge with this algorithm and it becomes worse as you go in higher dimensions. One remedy that is generally suggested is to use - "adaptive rejection sampling" . See section 11.1.3 of PRML (www.microsoft.com/en-us/research/uploads/prod/2006/01/Bishop-Pattern-Recognition-and-Machine-Learning-2006.pdf), it is quite well explained there.

[@pcaltd.1824]

@@KapilSachdeva Thanks for clarifying. The reference looks very useful.

[@KapilSachdeva]

🙏

[@MeesumQazalbash]

Wonderful tutorial no doubt Indian teachers are best. I am new to sampling and my work often involves multivariate pdfs to sample from. Is there any beginner's tutorial on it?

[@KapilSachdeva]

May be see the metropolis Hastings tutorial on my channel. I would suggest to learn pymc3 library as these sampling algos are part of it with a nice framework and api.

[@Anteater23]

Excellent video

[@KapilSachdeva]

🙏

[@lerneninverschiedenenforme7513]

Do I understand correctly, that you need two random values? 1st: Random value used as the actual "random variable" 2nd: Random value to evaluate, wheather the random value from (1) is used or not.

[@KapilSachdeva]

Your understanding is correct.

[@ZoeZhou-yk9sd]

Thank you for the video! Whats is the software you used to create this video plz?

[@KapilSachdeva]

🙏 PowerPoint

[@Nier914]

Thank you, I understand now😊

[@KapilSachdeva]

🙏

[@minma02262]

Hi Sir. Amazing tutorial!

[@KapilSachdeva]

🙏

[@fatihboyar9697]

great tutorial thanks a lot

[@KapilSachdeva]

🙏

[@MuhammadAbdullah-iv2gu]

Best explanation

[@KapilSachdeva]

🙏

[@UUalead]

Amazing, thx a lot.

[@marcogelsomini7655]

nice vid, what is the point of sampling if you know the analytical form of the function?

[@KapilSachdeva]

Good question. Three points to note - * Knowing the analytical form of the function does not mean that one can sample from it. * In a more sophisticated setup you do not even know the analytical form a function. A typical example is the posterior in Bayesian Statistics. *Sampling is necessary to use Law of large numbers to approximate a function (where its analytical form is available or not!)

[@marcogelsomini7655]

@@KapilSachdeva ok thanks. But this algorithm required to know the real function as you need to compute C the intersection of the random sample and confront with uniform random sample in order to accept o reject right?

[@KapilSachdeva]

@@marcogelsomini7655 This is the correct understanding. This is also why it is a limited and inefficient algorithm. Look at the metropolis-hasting algorithm that does not have this requirement. I have a tutorial on that as well.

[@marcogelsomini7655]

@@KapilSachdeva thx good work!

[@janhavisoni1559]

Thank you so much

[@KapilSachdeva]

🙏

[@lawrencege6942]

Thank you so much!

[@KapilSachdeva]

🙏

[@lone_Traveller_101]

Lovely sir!

[@KapilSachdeva]

👌

[@ananyapamde4514]

May god bless you

[@KapilSachdeva]

🙏

[@ahnafsamin3777]

Excellent

[@KapilSachdeva]

🙏

[@pzakala]

Sorry for stupid question. I`m now in static algorithms. Why we can`t sample for target function in this case. For example, we can just divide over function for 4.5. The resulting function will looks like distribution function 😅.

[@KapilSachdeva]

Most likely I am not following your suggestion - "divide over function for 4.5". If possible elaborate on this.

[@BilalTaskin-om6il]

magnificent...

[@KapilSachdeva]

🙏

[@gwirvanmenez3470]

Hello after computation I find that the integral of f(x) is ~5.73 on [-3;3]. Wich mean that f(x) is not a density fonction. Is the exemple still corect if the integral of f(x) is not equal to 1 on [-3;3] ?

[@KapilSachdeva]

Yes. Think of the function as unnormalized density function.

[@prateekcaire4193]

Assuming the proposal function is the same as the target function, then the rejection region would be 0. However, this would result in accepting everything, which could lead to incorrect acceptance if there is nothing above the pink blinker point.

[@prateekcaire4193]

It was helpful to build some intuition around though. Thanks!

[@prateekcaire4193]

ok i got it now. proposal function sampling will also follow probabilistic sampling and sampling from proposal (guassian or uniform) is quite easy

[@arpansrivastava6405]

1:31 how do we not know how to sample as the distribution function is already given and you also plotted it ?

[@KapilSachdeva]

Somehow it is a common confusion for many. Knowing a distribution function can only help you find the probability of a sample. Sampling from a function is a different task. Sampling means asking your computer to generate a sample. Sampling makes use of random number generator. Now your random number generator (algorithm) is to behave in such a way that the samples (random numbers) are generated in accordance with their prob distribution. Some samples are supposed to be more (the one with high prob) and some less. This is why various sampling algos/techniques are created. Your computer by default can give uniform random numbers. Most of the algorithms directly or indirectly manipulate the result of uniform random number generator.

[@ddiq47]

How do you get the values of f to determine rejection or acceptance? It’s confusing to me as the reason for using this method was based on being unable to sample from the original distribution f. What am I missing here

[@KapilSachdeva]

In many situations you have an analytical form of the distribution function available but this does not mean you can sample from that function. This is where this technique is used.

[@ddiq47]

@@KapilSachdeva when you say an analytical form of the distribution, what does that mean? Would it be a function like in the video, or a dataset of known function values?

[@KapilSachdeva]

A function. Using this function for a give sample you can compute it’s prob/score/value.

[@chronicillnessrevolution5079]

Heads up: I plotted the target function according to its expression shown in the video, but the graph that results from this expression is different from the one you show.

[@KapilSachdeva]

Have uploaded my (very old notebook) on colab. See if it helps colab.research.google.com/drive/1olDMLkwPk16YBmfPdq1zXmvtIVG8kF8R?usp=sharing

[@chronicillnessrevolution5079]

@@KapilSachdeva Found your typo. In the video it says sin^2(6+x) but in your code it is sin^2(6*x). Using the latter gives the correct plot

[@KapilSachdeva]

Thank you for catching it 🙏

[@schlast8311]

then why not just use f(x), let c*g be a straight line equal to the maximum of f(x)

[@JoseVinicius-fe3vk]

why Y axis goes beyond 1? there is no way something has over 100% chance of happening

[@KapilSachdeva]

This is an example function that does not represent pdf but you still want to obtain samples in accordance with this function. Or, think of it as unnormalized PDF.