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

Spring 2009

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

Catalog Information

A midterm example is here

Lecture Outline, Slides, Assignments,


DateTopicSlidesReadingAssignmentSolutions
Feb 18, Wed Introduction, Course structure, Motivating Examples, Applications, Law of Large numbers, CLT Lecture 1 (corrected) Johansen and Evers, Ch1, Andrieu, Absolute beginners, Section 1.1-1.5 Grinstead and Snell, Ch. 2.1 Problem 7,8,9,10,11 *
Feb 25, Wed Probability and Statistics Review, Random Number generation, Rejection sampling Lecture 2 - + *
Mar 04, Wed Importance sampling Lecture 3 Sections 2.5.2, 2.5.3 and 2.6.1. from Liu. Problem set 2 *
Mar 11, Wed Markov Chains, Stochastic Processes, Discrete State Space Markov Chains Lecture 4 Grinstead and Snell, Ch. 11, Sec 1 - Quiz solution
Mar 18, Wed The Metropolis-Hastings Algorithm, The Gibbs Sampler Lecture 5 - + *
Mar 25, Wed Example applications with MH and Gibbs See Lecture 5 slides - + *
Apr 01, Wed Model selection, Change Point models Lecture 6 - See last slide *
Apr 08, Wed Latent State space models, Reversible Jump, Lecture 7 - + *
Apr 15, Wed Midterm - + MT Solutions
Apr 22, Wed Cancelled - + *
Apr 29, Wed Spring Break - + *
May 06, Wed Sequential Monte Carlo Lecture 8 - + *
May 13, Wed Further topics in SMC, the Cross Entropy method Lecture 9 (link not active yet) CE tutorial + *
May 20, Wed Optimisation, Simulated Annealing, Iterative Improvement, Selected Advanced Topics Lecture 10 (link not active yet) - Assignment 5 *
June 08, Mon 10:00: Deadline for submission of project reports Example Reports (link not active yet) - + *
June 15, Mon (Tentative) Project presentations (link not active yet) guidelines (link not active yet) - + *

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

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