Bayesian Machine Learning: Graphical Models and Approximate Inference Summer Semester 2009

Lecturer

Registration and Grading

Time and Place

• Lecture:
  Friday, 8:30am-10am s.t., MPII E 1.4, Room 024; starting 24 April (not 10am-12pm, as previously announced!)
  
• Tutorials:
  Tuesday, 4pm-6pm c.t., MPII E 1.4, Room 023; starting 5 May
  

ATTENTION: Date change of lecture: Friday 8:30am-10am now (8:30am strict), to avoid overlap with Prof. Weickert's lecture.

Teamwork is OK for solving the exercises, as long as there is only two persons per group, and each of you thought about each of the exercises (it is not OK to just halve the work). If you do this, please hand in one solution, not two copies.

Motivation

• Coding and information transmission methods, based on loopy belief propagation in randomized low density codes have, within a range of a decade only, all but replaced prior algebraic codes, and are used now in deep space communication, satellite transmission, and even CD players
• Hidden Markov models, trained by expectation maximization based on belief propagation, have revolutionized speech recognition to an extent that it is hard to appreciate there ever having been alternative approaches (rule-based, linguistic, logics)
• The same models are widely used in bioinformatics, in order to find promising candidates for gene-coding DNA (estimates about the number of humans genes you read in the paper, are due to HMMs), to compare and classify proteins, and to reconstruct phylogenetic trees in order to understand evolution of species and diseases
• Probabilistic expert systems are widely used in industry, and increasingly so in health care. In situations with many unknown or poorly determined variables, they surpass rule-based systems
• Probabilistic state space models allow autonomous (even humanoid) robots (such as the autonomous vehicle that won the DARPA grand challenge) to localize themselves based on erroneous readings from multiple sensors of different modalities, to reason about impacts of potential actions in this world representation, and to plan useful behaviour accordingly
• Models for natural images (photographs, medical scans), such as Markov random fields or sparse linear models, are used for a multitude of computer vision and imaging problems, from denoising, quality enhancement, completion, and compression over segmentation and classification to improving image acquisition architectures

The relevance of probabilistic or Bayesian Machine Learning is likely to grow in the future, with more and more problems being approached the way humans do it. Apart from the general good press of artificial intelligence, adaptive, intelligent, predictive approaches will simply be demanded by way of growing pressures for simplification and cost reduction. At their heart, adaptive techniques have to reason about and calculate with uncertainty. In this course, we will explore one of the most far-reaching uncertainty calculi (Bayesian Statistics), its rules, mechanics, basic models and algorithms, and obtain insight in several of its key applications today.

Goals

The course will not be comprehensive, but will provide a solid overview. I aim to show up connections between ideas, and to convey basic understanding, pointing out further literature as I go. A major goal will be to show how ideas and algorithms are grounded on traditional computational disciplines, such as graph theory, convex optimization, numerical optimization, and classical estimation theory.

Background

There will be some practical exercises in Matlab. If you did not work with Matlab before, there are helpful tutorials on the web, for example here.

Organisatorial Details

There will be lectures and tutorials. After most lectures, assignments will be made available, for electronic download here. Briefly, you will be awarded exercise points for handing in correct solutions to these assignment. You are allowed to take part in the final course examination, if you attain 60 percent or more of the total exercise points, otherwise you are not. In order to gain credit points (different from exercise points), you have to take part in the final examination and pass it. Since there will be no script, and I will use the blackboard, attendance at the lectures is strongly recommended. The final examination will be oral or written, depending on the number of participants. The type of final examination will be disclosed no earlier than after lecture 8, and no later than two weeks before the end of semester. For more details, read on.

Teamwork: You may form teams of two people for doing the exercises, if that does not mean that you simply split up the work. Each of you should have thought about each of the exercises. In fact, if you did solve them together (two people, no more), then do not hand in two different sheets, but just one.

Each assignment has a due date, typically the subsequent lecture, sometimes you have more time. There are pencil/paper exercises and programming exercises. For the former (there will be more of these), you can hand in written pages (to me before lecture, or to course mailbox; legible please), or you can send pdf or ps files to the course email address. Whatever you do, always mark everything (every page) with your name and matriculation number.
For the programming exercises, you will have to use Matlab. The course will not include any Matlab tutorial. Solutions to programming exercises have to be sent to the course email address. Instructions about format will be given with the first programming exercise. But in general, make sure that every mail contains your name and matriculation number in the subject header.

Exercise sheets will be marked, and returned in general in the first tutorial session after the due date (unless otherwise said). In these sessions, we will work out correct solutions for pencil/paper exercises together. I will not distribute or upload written solutions, so please come to these sessions. The tutorial sessions will also be used to reiterate the corresponding lecture material. Programming exercises will not be discussed in the tutorials, except you asking me questions. Your solutions will be tested by applying them to data, using a protocol that will be explained in detail together with the first programming exercise.

I will be strict regarding a few points (for fairness):

• Assignment sheets have to be handed in at or before the due date (which is a time, the time of the lecture). Anything that arrives later, will not be looked at.
• A complete solution to a pencil/paper exercise is a complete derivation, in the style of a mathematical proof. There will be point deductions for any missing step. I strongly encourage you to save on steps by clever arguments, but make sure there are no holes (in general, a clever argument with a tiny hole will get you more points than two pages of algebra with a tiny hole). Answers like "The posterior probability is 0.18925; QED" will get nil points in general.

Lectures

Tutorials

Literature

• D. MacKay: Information Theory, Inference, and Learning Algorithms (2003)
  
• C. Bishop: Pattern Recognition and Machine Learning (2006)
  
• D. Barber: An Introduction to Bayesian Reasoning and Machine Learning (2010)
  This will certainly be up to date, and in the style of the lecture. I highly recommend you having a look. If you find mistakes that are not already listed in the wiki, please post them on the site. The book comes with lots of Matlab code for trying things out.

• T. Minka
  Nuances of Probability Theory
  The subtitle is "Why you must take a probability course in order to understand pattern recognition": I could not agree more. Very useful read for those confused by classical notions of probability, fruitless approaches to "fuzzify" logics, and the like.
  
• M. Seeger
  Bayesian Modelling in Machine Learning: A Tutorial Review
  An overview over some of the material of the first part of the lecture, plus some more we'll not visit here (Gaussian process models).
  
• M. Seeger
  PhD thesis. Appendix A
  Not an easy read, but useful as a lookup paper.
  
• T. Minka
  Old and New Matrix Algebra Useful for Statistics
  A very useful collection of formulae for doing matrix/vector derivatives. Needs some work to read, but this is very well spent.
  

• Matlab tutorial
  
• JavaBayes
  This is a simple applet to construct, store, and load small Bayesian networks, and do inference for them. Use this to play around, or to check your derivations.
  

• Probabilistic Modelling and Reasoning (C. Williams, Edinburgh University)
  
• Bayes net tutorial by K. Murphy
  
• Pattern Recognition Glossary by T. Minka