Chapter 11. Sampling algorithms

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.

11.1. The sampling principle

11.2. Importance sampling

11.3. Markov chain Monte Carlo sampling

11.4. Getting MH to work well

11.5. Summary

11.6. Exercises