CMPE 58N, Monte Carlo methods for data analysis and scientific computing
Spring 2011
Instructor: Ali Taylan Cemgil
TA (voluntary): Orhan Sonmez, Baris Kurt
Bogaziçi University, Department of Computer Engineering, Istanbul, Turkey
Time: WWW234 (Wednesday 10:00-13:00, ETA A5)
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
Assignment 1 is available online.
Lecture Slides, Topics
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
Lecture 8 Sequential Monte Carlo
Assignments
Assignment 1
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
Overview/Tutorial Papers
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
Persi Diaconis, The Markov chain Monte Carlo revolution Bull. Amer. Math. Soc. 46 (2009), 179-205.
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
