Monte Carlo methods

Preface
Contents
About the Authors
1 Introduction to Monte Carlo Methods
	1.1 Introduction
	1.2 Motivation and Objectives
	1.3 Tasks in Monte Carlo Computing
		1.3.1 Task 1: Sampling and Simulation
		1.3.2 Task 2: Estimating Quantities by Monte Carlo Simulation
		1.3.3 Task 3: Optimization and Bayesian Inference
		1.3.4 Task 4: Learning and Model Estimation
		1.3.5 Task 5: Visualizing the Landscape
	References
2 Sequential Monte Carlo
	2.1 Introduction
	2.2 Sampling a 1-Dimensional Density
	2.3 Importance Sampling and Weighted Samples
	2.4 Sequential Importance Sampling (SIS)
		2.4.1 Application: The Number of Self-Avoiding Walks
		2.4.2 Application: Particle Filtering for Tracking Objectsin a Video
			2.4.2.1 Application: Curve Tracking
		2.4.3 Summary of the SMC Framework
	2.5 Application: Ray Tracing by SMC
		2.5.1 Example: Glossy Highlights
	2.6 Preserving Sample Diversity in Importance Sampling
		2.6.1 Parzen Window Discussion
	2.7 Monte Carlo Tree Search
		2.7.1 Pure Monte Carlo Tree Search
		2.7.2 AlphaGo
	2.8 Exercises
	References
3 Markov Chain Monte Carlo: The Basics
	3.1 Introduction
	3.2 Markov Chain Basics
	3.3 Topology of Transition Matrix: Communication and Period
	3.4 The Perron-Frobenius Theorem
	3.5 Convergence Measures
	3.6 Markov Chains in Continuous or Heterogeneous State Spaces
	3.7 Ergodicity Theorem
	3.8 MCMC for Optimization by Simulated Annealing
		3.8.1 Page Rank Example
	3.9 Exercises
	References
4 Metropolis Methods and Variants
	4.1 Introduction
	4.2 The Metropolis-Hastings Algorithm
		4.2.1 The Original Metropolis-Hastings Algorithm
		4.2.2 Another Version of the Metropolis-Hastings Algorithm
		4.2.3 Other Acceptance Probability Designs
		4.2.4 Key Issues in Metropolis Design
	4.3 The Independence Metropolis Sampler
		4.3.1 The Eigenstructure of the IMS
		4.3.2 General First Hitting Time for Finite Spaces
		4.3.3 Hitting Time Analysis for the IMS
	4.4 Reversible Jumps and Trans-Dimensional MCMC
		4.4.1 Reversible Jumps
		4.4.2 Toy Example: 1D Range Image Segmentation
			4.4.2.1 Jump-Diffusion
	4.5 Application: Counting People
		4.5.1 Marked Point Process Model
		4.5.2 Inference by MCMC
		4.5.3 Results
	4.6 Application: Furniture Arrangement
	4.7 Application: Scene Synthesis
	4.8 Exercises
	References
5 Gibbs Sampler and Its Variants
	5.1 Introduction
	5.2 Gibbs Sampler
		5.2.1 A Major Problem with the Gibbs Sampler
	5.3 Gibbs Sampler Generalizations
		5.3.1 Hit-and-Run
		5.3.2 Generalized Gibbs Sampler
		5.3.3 Generalized Hit-and-Run
		5.3.4 Sampling with Auxiliary Variables
		5.3.5 Simulated Tempering
		5.3.6 Slice Sampling
		5.3.7 Data Augmentation
		5.3.8 Metropolized Gibbs Sampler
	5.4 Data Association and Data Augmentation
	5.5 Julesz Ensemble and MCMC Sampling of Texture
		5.5.1 The Julesz Ensemble: A Mathematical Definitionof Texture
		5.5.2 The Gibbs Ensemble and Ensemble Equivalence
		5.5.3 Sampling the Julesz Ensemble
		5.5.4 Experiment: Sampling the Julesz Ensemble
	5.6 Exercises
	References
6 Cluster Sampling Methods
	6.1 Introduction
	6.2 Potts Model and Swendsen-Wang
	6.3 Interpretations of the SW Algorithm
		6.3.1 Interpretation 1: Metropolis-Hastings Perspective
		6.3.2 Interpretation 2: Data Augmentation
	6.4 Some Theoretical Results
	6.5 Swendsen-Wang Cuts for Arbitrary Probabilities
		6.5.1 Step 1: Data-Driven Clustering
		6.5.2 Step 2: Color Flipping
		6.5.3 Step 3: Accepting the Flip
		6.5.4 Complexity Analysis
	6.6 Variants of the Cluster Sampling Method
		6.6.1 Cluster Gibbs Sampling: The ``Hit-and-Run\'\' Perspective
		6.6.2 The Multiple Flipping Scheme
	6.7 Application: Image Segmentation
	6.8 Multigrid and Multi-level SW-cut
		6.8.1 SW-Cuts at Multigrid
		6.8.2 SW-cuts at Multi-level
	6.9 Subspace Clustering
		6.9.1 Subspace Clustering by Swendsen-Wang Cuts
		6.9.2 Application: Sparse Motion Segmentation
	6.10 C4: Clustering Cooperative and Competitive Constraints
		6.10.1 Overview of the C4 Algorithm
		6.10.2 Graphs, Coupling, and Clustering
		6.10.3 C4 Algorithm on Flat Graphs
		6.10.4 Experiments on Flat Graphs
		6.10.5 Checkerboard Ising Model
		6.10.6  C4 on Hierarchical Graphs
		6.10.7 Experiments on Hierarchical C4
	6.11 Exercises
	References
7 Convergence Analysis of MCMC
	7.1 Introduction
	7.2 Key Convergence Topics
	7.3 Practical Methods for Monitoring
	7.4 Coupling Methods for Card Shuffling
		7.4.1 Shuffling to the Top
		7.4.2 Riffle Shuffling
	7.5 Geometric Bounds, Bottleneck and Conductance
		7.5.1 Geometric Convergence
	7.6 Peskun\'s Ordering and Ergodicity Theorem
	7.7 Path Coupling and Exact Sampling
		7.7.1 Coupling From the Past
		7.7.2 Application: Sampling the Ising Model
	7.8 Exercises
	References
8 Data Driven Markov Chain Monte Carlo
	8.1 Introduction
	8.2 Issues with Segmentation and Introduction to DDMCMC
	8.3 Simple Illustration of the DDMCMC
		8.3.1 Designing MCMC: The Basic Issues
		8.3.2 Computing Proposal Probabilities in the Atomic Spaces: Atomic Particles
		8.3.3 Computing Proposal Probabilities in Object Spaces: Object Particles
		8.3.4 Computing Multiple, Distinct Solutions: Scene Particles
		8.3.5 The Ψ-World Experiment
	8.4 Problem Formulation and Image Models
		8.4.1 Bayesian Formulation for Segmentation
		8.4.2 The Prior Probability
		8.4.3 The Likelihood for Grey Level Images
		8.4.4 Model Calibration
		8.4.5 Image Models for Color
	8.5 Anatomy of Solution Space
	8.6 Exploring the Solution Space by Ergodic Markov Chains
		8.6.1 Five Markov Chain Dynamics
		8.6.2 The Bottlenecks
	8.7 Data-Driven Methods
		8.7.1 Method I: Clustering in Atomic Spaces
		8.7.2 Method II: Edge Detection
	8.8 Computing Importance Proposal Probabilities
	8.9 Computing Multiple Distinct Solutions
		8.9.1 Motivation and a Mathematical Principle
		8.9.2 A K-Adventurers Algorithm for Multiple Solutions
	8.10 Image Segmentation Experiments
	8.11 Application: Image Parsing
		8.11.1 Bottom-Up and Top-Down Processing
		8.11.2 Generative and Discriminative Methods
		8.11.3 Markov Chain Kernels and Sub-Kernels
		8.11.4 DDMCMC and Proposal Probabilities
			8.11.4.1  Generative Models and Bayesian Formulation
			8.11.4.2  Shape Models
			8.11.4.3  Generative Intensity Models
			8.11.4.4  Overview of the Algorithm
			8.11.4.5 Discriminative Methods
			8.11.4.6 Control Structure of the Algorithm
		8.11.5 The Markov Chain Kernels
			8.11.5.1 Boundary Evolution
			8.11.5.2  Markov Chain Sub-Kernels
			8.11.5.3 AdaBoost for Discriminative Probabilities for Face and Text
		8.11.6 Image Parsing Experiments
	8.12 Exercises
	References
9 Hamiltonian and Langevin Monte Carlo
	9.1 Introduction
	9.2 Hamiltonian Mechanics
		9.2.1 Hamilton\'s Equations
		9.2.2 A Simple Model of HMC
	9.3 Properties of Hamiltonian Mechanics
		9.3.1 Conservation of Energy
		9.3.2 Reversibility
		9.3.3 Symplectic Structure and Volume Preservation
	9.4 The Leapfrog Discretization of Hamilton\'s Equations
		9.4.1 Euler\'s Method
		9.4.2 Modified Euler\'s Method
		9.4.3 The Leapfrog Integrator
		9.4.4 Properties of the Leapfrog Integrator
	9.5 Hamiltonian Monte Carlo and Langevin Monte Carlo
		9.5.1 Formulation of HMC
		9.5.2 The HMC Algorithm
		9.5.3 The LMC Algorithm
		9.5.4 Tuning HMC
		9.5.5 Proof of Detailed Balance for HMC
	9.6 Riemann Manifold HMC
		9.6.1 Linear Transformations in HMC
		9.6.2 RMHMC Dynamics
		9.6.3 RMHMC Algorithm and Variants
		9.6.4 Covariance Functions in RMHMC
	9.7 HMC in Practice
		9.7.1 Simulated Experiments on Constrained NormalDistributions
		9.7.2 Sampling Logistic Regression Coefficients with RMHMC
		9.7.3 Sampling Image Densities with LMC: FRAME, GRADE and DeepFRAME
	9.8 Exercises
	References
10 Learning with Stochastic Gradient
	10.1 Introduction
	10.2 Stochastic Gradient: Motivation and Properties
		10.2.1 Motivating Cases
		10.2.2 Robbins-Monro Theorem
		10.2.3 Stochastic Gradient Descent and the Langevin Equation
	10.3 Parameter Estimation for Markov Random Field (MRF) Models
		10.3.1 Learning a FRAME Model with Stochastic Gradient
		10.3.2 Alternate Methods of Learning for FRAME
		10.3.3 Four Variants of the FRAME Algorithm
		10.3.4 Experiments
	10.4 Learning Image Models with Neural Networks
		10.4.1 Contrastive Divergence and Persistent ContrastiveDivergence
		10.4.2 Learning a Potential Energy for Images with Deep Networks: DeepFRAME
		10.4.3 Generator Networks and Alternating Backward Propagation
		10.4.4 Cooperative Energy and Generator Models
	10.5 Exercises
	References
11 Mapping the Energy Landscape
	11.1 Introduction
	11.2 Landscape Examples, Structures, and Tasks
		11.2.1 Energy-Based Partitions of the State Space
		11.2.2 Constructing a Disconnectivity Graph
		11.2.3 ELM Example in 2D
		11.2.4 Characterizing the Difficulty (or Complexity) of Learning Tasks
	11.3 Generalized Wang-Landau Algorithm
		11.3.1 Barrier Estimation for GWL Mapping
		11.3.2 Volume Estimation with GWL
		11.3.3 GWL Convergence Analysis
	11.4 GWL Experiments
		11.4.1 GWL Mappings of Gaussian Mixture Models
			11.4.1.1 GMM Energy and Gradient Computations
			11.4.1.2 Experiments on Synthetic GMM Data
			11.4.1.3 Experiments on GMMs of Real Data
		11.4.2 GWL Mapping of Grammar Models
			11.4.2.1 Learning Dependency Grammars
			11.4.2.2 Energy Function of Dependency Grammar
			11.4.2.3 Discretization of the Dependency Grammar Hypothesis Space
			11.4.2.4 GWL Dependency Grammar Experiments and Curriculum Learning
	11.5 Mapping the Landscape with Attraction-Diffusion
		11.5.1 Metastability and a Macroscopic Partition
		11.5.2 Introduction to Attraction-Diffusion
		11.5.3 Attraction-Diffusion and the Ising Model
		11.5.4 Attraction-Diffusion ELM Algorithm
		11.5.5 Tuning ADELM
		11.5.6 Barrier Estimation with AD
	11.6 Mapping the SK Spin Glass Model with GWL and ADELM
	11.7 Mapping Image Spaces with Attraction-Diffusion
		11.7.1 Structure of Image Galaxies
		11.7.2 Experiments
			11.7.2.1 Digits 0–9 ELM in Latent Space
			11.7.2.2 Ivy Texton ELM in Latent Space
			11.7.2.3 Multiscale Ivy ELM in Latent Space
			11.7.2.4 Cat Faces ELM in Latent Space
	11.8 Exercises
	References
Index