Cmpe 548, Monte Carlo methods
Fall 2017
Instructor:
A. Taylan Cemgil
For contact details and further information see the web: http://www.cmpe.boun.edu.tr/~cemgil/
TA
Ilker Gundogdu, Serhan Danis
Announcements
Past Midterms and assignments
cmpe58n-spring12-midterm.pdf
cmpe58n-spring14-midterm.pdf
Assignment 3
Assignment 2
Assignment 1
Course Description
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.
Notebooks
Some Class notes can be found as iPython notebooks
Submissions
Computer Usage
We will use Python, ipython notebooks and occasionally Octave. See:
Octave is a popular matlab clone. So, most (but not all) matlab material is useful
Alternative Computing environments
Grading
Lecture Notes
The class will follow closely these lecture notes Download
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 Model Selection (older version)
Lecture 8 Sequential Monte Carlo
Lecture 7 Reversible Jump
Online Demos
Code Breaking via MCMC
Assignments
Uniform sampling on the circle
Uniform sampling of permutations
Code Breaking
Solitair
Hit and Run, Uniform sampling on convex sets
Simulated Annealing, LP Solver, Convex Optimization
Variable Selection in Linear Regression
Change Point, Multiple Change Point
Slice Sampling
HMC Hybrid Monte Carlo
Reversible Jump MCMC
Stan
Nonparametric Bayesian method
Reference Books
Adam M. Johansen and Ludger Evers (edited by Nick Whiteley), Monte Carlo Methods, Lecture notes, University of Bristol
Available online
References
Probability Theory
Geoffrey Grimmet and David Stirzaker, Probability and Random Processes, (3rd Ed), Oxford, 2006
Grinstead and Snell, Introduction to probability, available online!
Dimitri P. Bertsekas and John N. Tsitsiklis. Introduction to Probability. Athena Scientific, 2002
Programming
Overview/Tutorial Papers
C. Andrieu. Monte Carlo Methods for Absolute beginners, 2004, Springer Lecture Notes in Computer Science,
Andrieu, de Freitas, Doucet, Jordan. An Introduction to MCMC for Machine Learning, Machine Learning, 2002
Information Theory, Inference, and Learning Algorithms, David MacKay, Cambridge University Press
Rejection Sampling
Random Variate Generation
Sequential Monte Carlo/Particle filtering
Applications
Cipher Text
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
Review Material
|