(30 minutes to learn)
Rejection sampling (RS) is a monte carlo method for sampling from a potentially complex distribution p(x) given a simpler distribution q(x). RS is applicable when we can evaluate p(x) easily and sample from q(x) easily. The basic idea is to scale q(x) by some constant K such that K*q(x) >= p*(x) for all x, where p(x) = 1/Z p*(x) for some constant Z (that is, we only need to know p(x) up to a normalization factor, which is common in practice). RS operates by sampling a value x0 from q(x) and then generating a uniform random number, u, between [0, K*q(x0)]. If u <= p*(x0) we keep x0 as a valid sample from p(x), else we discard x0.
This concept has the prerequisites:
Core resources (read/watch one of the following)
→ Machine learning summer school: Markov chain Monte Carlo (2009)
A video tutorial on MCMC methods.
Location: 13:50 to 15:36
→ Information Theory, Inference, and Learning Algorithms
A graudate-level textbook on machine learning and information theory.
- multivariate Gaussian distribution
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location: Sections 23.3-23.3.3, pages 817-819
→ Pattern Recognition and Machine Learning
A textbook for a graduate machine learning course, with a focus on Bayesian methods.
Location: Section 11.1.2
Supplemental resources (the following are optional, but you may find them useful)
→ Mathematical Monk Tutorials
→ Bayesian Reasoning and Machine Learning
A textbook for a graudate machine learning course.
- Importance sampling is a way of getting weighted samples from a distribution and is useful in many of the same situations.
- Adaptive rejection sampling is a way to improve the sampler based on the rejected samples [ (go to concept)](adaptive_rejection_sampling)
- Other commonly used sampling methods include:
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation