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

  1. cmpe58n-spring12-midterm.pdf

  2. cmpe58n-spring14-midterm.pdf

  3. Assignment 3

  4. Assignment 2

  5. 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:

  1. Model construction

  2. Design of strategies for inference

  3. 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

  • We will use the grader system we have developed based on git.

Computer Usage

We will use Python, ipython notebooks and occasionally Octave. See:

Starting Octave
octave --force-gui

Octave is a popular matlab clone. So, most (but not all) matlab material is useful

Alternative Computing environments

Grading

  • Written Exam 40

  • Homeworks 20

  • Final Project and Presentation 40

Lecture Notes

The class will follow closely these lecture notes Download

Slides

  1. Lecture 0 Introduction, Course structure, Motivating Examples

  2. Lecture 1 History of the MC method, Law of Large numbers, Central Limit Theorem

  3. Lecture 2 Random Number generation, Rejection sampling, Importance Sampling

  4. Lecture 3 Discrete state space Markov Chains, MCMC, Metropolis-Hastings Algorithm

  5. Lecture 4 Gibbs sampler, Applications

  6. Lecture 5 Model Selection

  7. Lecture 6 Model Selection (older version)

  8. Lecture 8 Sequential Monte Carlo

  1. Lecture 7 Reversible Jump

Online Demos

  1. Code Breaking via MCMC

Assignments

  1. Uniform sampling on the circle

  2. Uniform sampling of permutations

  3. Code Breaking

  4. Solitair

  5. Hit and Run, Uniform sampling on convex sets

  6. Simulated Annealing, LP Solver, Convex Optimization

  7. Variable Selection in Linear Regression

  8. Change Point, Multiple Change Point

  9. Slice Sampling

  10. HMC Hybrid Monte Carlo

  11. Reversible Jump MCMC

  12. Stan

  13. Nonparametric Bayesian method

Reference Books

  • Jun S. Liu, Monte Carlo Strategies in Scientific Computing, 2001, Springer.

  • 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

    • Companion book containing 1000 exercises and solutions

  • 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

Rejection Sampling

Random Variate Generation

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

  • Stack Overflow

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