Chapter 11. Sampling algorithms
This chapter covers
- The basic principles of sampling algorithms
- The importance sampling algorithm
- Markov chain Monte Carlo (MCMC) algorithm
- The Metropolis-Hastings variant of MCMC
This chapter continues the theme of the previous chapter, presenting some of the main algorithms used in probabilistic programming inference. Whereas chapter 10 focused on factored algorithms such as variable elimination and belief propagation, this chapter looks at sampling algorithms that answer queries by generating possible states of variables drawn from the probability distribution defined by the program. In particular, the chapter presents two useful algorithms: importance sampling and Markov chain Monte Carlo (MCMC).
After you’ve finished this chapter, you’ll have a solid understanding of inference algorithms used in probabilistic programming systems such as Figaro. This understanding will help you design your models and control inference to make it work well. MCMC, in particular, requires extra effort to make it work well, and the chapter presents a couple of techniques to do that. Chapter 12 then builds on this knowledge to show you how to use similar algorithms to answer other kinds of queries on probabilistic programs.