CMPE 58N, Monte Carlo methods for data analysis and scientific computing

Fall 2009

Instructor: Ali Taylan Cemgil
Bogaziçi University, Department of Computer Engineering, Istanbul, Turkey

Catalog Information (pdf)

Monte Carlo methods are stochastic simulation based algorithms designed to compute answers to problems
where exact solutions are intractable and take exponential time to compute. While these techniques
provide an exact answer only asymptotically, they perform remarkably well in practice and
are now used extensively in science and engineering, including statistics, machine learning, aerospace, computer vision,
network analysis, speech recognition, robotics, physics and bioinformatics.

The scope of this course is to review the following fundamental aspects in Monte Carlo computations:

 * Model construction
 * Design of strategies for inference
 * Theoretical aspects (convergence proofs, performance analysis)

Our exposure will be primarily slanted towards inference strategies.

In particular, we will study Markov Chain Monte Carlo methods and Sequential Monte Carlo. Our ultimate aim
is to provide a basic understanding of computational techniques based on Monte Carlo simulations and associated
concepts such that the students can orient themselves in the relevant literature and understand the current
state of the art.


Announcements

Slides
Lecture 0 Introduction, Course structure, Motivating Examples
Lecture 1 History of the MC method, Law of Large numbers, Central Limit Theorem
Lecture 2 Random Number generation, Rejection sampling, Importance Sampling
Lecture 3 Discrete state space Markov Chains, MCMC, Metropolis-Hastings Algorithm
Lecture 4 Gibbs sampler, Applications
Lecture 5 Model Selection
Lecture 6 
Lecture 7 Reversible Jump (Slides from previous year)
Lecture 8 Sequential Monte Carlo (Slides from previous year)


	
Lecture Schedule and Assignments, 

Date Topic Reading Assignment Solutions
Sep 28, Mon

 Introduction, Course structure, Motivating Examples 

Applications, Probability and Statistics Review 

  

  

  

Oct 05, Mon

 Law of Large numbers, Central Limit Theorem, Random Number generation, Rejection sampling 

  

  HW1  

  

Oct 12, Mon

 Importance sampling 

  

  

  

Oct 19, Mon

 Discrete State Space Markov Chains, Stochastic Processes 

  

  

  

Oct 26, Mon

 The Metropolis-Hastings Algorithm, The Gibbs Sampler 

  

  

  

Nov 02, Mon

 Example applications with MH and Gibbs 

  

  HW2  

  

Nov 09, Mon

 Example applications, Model selection 

  

  

  

Nov 16, Mon

 Reversible Jump 

  

  

  

Nov 23, Mon

 State space models, Sequential Monte Carlo 

  

  

  

 Nov 30, Mon 

 Kurban Bayrami 

  

  

  


Dec 07, Mon

 Midterm 

  

  

  

Dec 14, Mon

 Advanced Sequential Monte Carlo, Annealed Importance sampling, SMC Samplers 

  

  

  

Dec 21, Mon

 Optimisation, Simulated Annealing, Iterative Improvement, Cross Entropy method 

 

  

  

Dec 28, Mon

 Selected advanced topics/Review

Advanced Topics

Ising Models and Boltzman machines,
Clustering methods, Swedsen-Wang,
Hybrid Monte Carlo,
Slice sampling,
Perfect sampling,
Propp-Wilson, Coupling from the past

References

Tutorials

C. Andrieu. Monte Carlo Methods for Absolute beginners, 2004, Springer Lecture Notes in Computer Science,

Markov Chains

Grinstead and Snell, Introduction to probability Chapter 11

Random Variate Generation

L. Devroye. Non-Uniform Random Variate Generation. Springer, 1986. Freely available online.

Markov Chain Monte Carlo

Andrieu, de Freitas, Doucet, Jordan. An Introduction to MCMC for Machine Learning, 2001

Sequential Monte Carlo/Particle filtering

A. Doucet, S.J. Godsill and C. Andrieu, On Sequential Monte Carlo sampling methods for Bayesian filtering, (section IV) Stat. Comp., 2000
A.Doucet and A. Johansen, Particle filtering and smoothing: Fifteen years later, 2008 Arnaud Doucet's SAMSI course webpage

HMM's and Parameter Estimation

T. Ryden, EM versus Markov chain Monte Carlo for Estimation of Hidden Markov Models: A Computational Perspective, Bayesian Analysis (2008), 3(4), p.p. 659-688
Bayesian Inference on Mixtures of Distributions, K. Lee, J. Marin, K. Mengersen and C. Robert

Propp-Wilson

MacKay book Diaconis and Friedman Iterated Random Functions
spade

Date	Topic	Reading	Assignment	Solutions
Sep 28, Mon	Introduction, Course structure, Motivating Examples Applications, Probability and Statistics Review
Oct 05, Mon	Law of Large numbers, Central Limit Theorem, Random Number generation, Rejection sampling		HW1
Oct 12, Mon	Importance sampling
Oct 19, Mon	Discrete State Space Markov Chains, Stochastic Processes
Oct 26, Mon	The Metropolis-Hastings Algorithm, The Gibbs Sampler
Nov 02, Mon	Example applications with MH and Gibbs		HW2
Nov 09, Mon	Example applications, Model selection
Nov 16, Mon	Reversible Jump
Nov 23, Mon	State space models, Sequential Monte Carlo
Nov 30, Mon	Kurban Bayrami
Dec 07, Mon	Midterm
Dec 14, Mon	Advanced Sequential Monte Carlo, Annealed Importance sampling, SMC Samplers
Dec 21, Mon	Optimisation, Simulated Annealing, Iterative Improvement, Cross Entropy method
Dec 28, Mon	Selected advanced topics/Review