Rejection Sampling - VISUALLY EXPLAINED with EXAMPLES!
ฝัง
- เผยแพร่เมื่อ 28 ม.ค. 2021
- 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 -
towardsdatascience.com/what-i... - วิทยาศาสตร์และเทคโนโลยี
![4BANG - NOT LIKE US (REMIX) [Official Music Video]](http://i.ytimg.com/vi/HO22cYkha1s/mqdefault.jpg)
Rotating the plots is a stroke of genius, things clicked instinctively. You are a gifted content maker. Keep making videos.
Thanks 🙏… finally someone saw the rotated plot and understood its significance … I am happy now :)
Indeed Kapil ji is an artist! I'm writing my thesis with his videos as inspiration.
You guys are so kind. Many thanks for the encouragement. @adithyanssathish5485 would love to read your thesis when it is ready.
Yes Kapil ji. I will send an invite to public part of my thesis defence for a duration of 30 minutes.
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 . ❤❤❤
that's actually a terrific explanation
🙏
Best explanation for this topic on TH-cam. I wonder how you even came up with this. Genius
🙏
You just saved a college student living in South Korea! Thanks for amazing visualization and explanations!
🙏
Thank you for your hard work, which enables us to understand crystal clear. Thanks a lot ❤❤❤
this brilliant change of viewpoint helps to explain the method in a much simpler way!
🙏
Fantastic explanation! Best video on this subject I've seen so far. Saved me lots of time searching for clarification. Thank you!
🙏
thank you for your detail and understandable explanation. The video animations are great and impressive.
🙏
Such a Masterpiece of a video, thanks for the explanation!
🙏
Excellent video and clearly explained ! Hope you can also do tutorials on other MCMC sampling methods such Gibbs Sampling, Metropolis-Hasting and Hamiltonian !
coming soon :)
This is sooo helpful! Totally addressed my concern!! Thank you!
🙏
Thank you so much sir for the amazing explanation and visualization.
🙏
Thank you so much. I now understand the concept better.
🙏
Legendary video man thank you!!!
🙏
Thank you for your explanation, nice presentation!
🙏
Excellent explanation ever on rejection sampling
🙏
Thank you, I understood clearly.
🙏
thank you so much , very well explained !
🙏
thank you, very well explained!
🙏
Thank you so much for this video, it is very clear and makes rejection sampling easy to understand
Could you make one on copulae? tks
🙏
Thank you so much!
🙏
Thank you, I understand now😊
🙏
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?
Hi Sir. Amazing tutorial!
🙏
Thank you so much
🙏
Lovely sir!
👌
great tutorial thanks a lot
🙏
Excellent video
🙏
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?
In that case you would not use Rejection sampling. You would want to use an algo like metropolis Hastings, HMC etc
Best explanation
🙏
magnificent...
🙏
Excellent
🙏
Thank you for the video! Whats is the software you used to create this video plz?
🙏 PowerPoint
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?
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.
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.
Your understanding is correct.
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?
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.
@@KapilSachdeva Thanks for clarifying. The reference looks very useful.
🙏
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] ?
Yes. Think of the function as unnormalized density function.
May god bless you
🙏
nice vid, what is the point of sampling if you know the analytical form of the function?
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!)
@@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?
@@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.
@@KapilSachdeva thx good work!
1:31 how do we not know how to sample as the distribution function is already given and you also plotted it ?
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.
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 😅.
Most likely I am not following your suggestion - "divide over function for 4.5". If possible elaborate on this.
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.
Have uploaded my (very old notebook) on colab. See if it helps
colab.research.google.com/drive/1olDMLkwPk16YBmfPdq1zXmvtIVG8kF8R?usp=sharing
@@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
Thank you for catching it 🙏
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.
It was helpful to build some intuition around though. Thanks!
ok i got it now. proposal function sampling will also follow probabilistic sampling and sampling from proposal (guassian or uniform) is quite easy
why Y axis goes beyond 1? there is no way something has over 100% chance of happening
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.
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
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.
@@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?
A function. Using this function for a give sample you can compute it’s prob/score/value.