## Cmpe 548, Monte Carlo methods## Fall 2017## Instructor:A. Taylan Cemgil ## TAIlker Gundogdu, Serhan Danis ## Announcements## Past Midterms and assignments## Course DescriptionMonte 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. ## NotebooksSome Class notes can be found as iPython notebooks ## SubmissionsWe will use the grader system we have developed based on git.
## Computer UsageWe 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## GradingWritten Exam 40 Homeworks 20 Final Project and Presentation 40
## Lecture NotesThe class will follow closely these lecture notes Download ## SlidesLecture 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## AssignmentsUniform 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 BooksJun 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 TheoryGeoffrey 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 PapersC. 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 Chapter on Monte Carlo technique, Available online
## Rejection SamplingW. Gilks and P. Wild, Adaptive rejection sampling for Gibbs sampling, Applied Statistics, 1992 B.D. Flury, Rejection sampling made easy, SIAM Review, 1990 <a A. Peterson and R. Kronmal, On mixture methods for the computer generation of random variables, The American Statistician, 1982
## Random Variate GenerationL. Devroye. Non-Uniform Random Variate Generation. Springer, 1986. Freely available online.
## Sequential Monte Carlo/Particle filteringA. 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 fantastic SMC Resources page and an earlier SAMSI course webpage
## Applications## Cipher TextPersi Diaconis, The Markov chain Monte Carlo revolution Bull. Amer. Math. Soc. 46 (2009), 179-205. J. Chen and J.S. Rosenthal, Decrypting Classical Cipher Text Using Markov Chain Monte Carlo. Stat. and Comput. 22:397-413, 2011. Related Software
## HMM's and Parameter EstimationT. 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 |