(45 minutes to learn)
Importance sampling is a way of estimating expectations under an intractable distribution p by sampling from a tractable distribution q and reweighting the samples according to the ratio of the probabilities. While importance sampling has unreasonably large variance when applied naively, it forms the basis for some very effective Monte Carlo estimators.
This concept has the prerequisites:
- Monte Carlo estimation
- conditional distributions (Importance sampling is commonly used to estimate conditional expectations.)
Core resources (read/watch one of the following)
→ Information Theory, Inference, and Learning Algorithms
A graudate-level textbook on machine learning and information theory.
- multivariate Gaussian distribution
→ Probabilistic Graphical Models: Principles and Techniques
A very comprehensive textbook for a graduate-level course on probabilistic AI.
Location: Sections 12.2-12.2.2, pages 494-498
Supplemental resources (the following are optional, but you may find them useful)
→ Machine learning summer school: Markov chain Monte Carlo (2009)
A video tutorial on MCMC methods.
Location: 15:36 to 22:37
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location: Sections 23.4-23.4.3
- Bayesian networks
→ Pattern Recognition and Machine Learning
A textbook for a graduate machine learning course, with a focus on Bayesian methods.
Location: Section 11.1.4, pages 532-534
- The variance of the importance weights depends on a Renyi divergence between the two distributions.
- Importance sampling is ineffective except in simple situations. More sophisticated versions 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