ECE1508F 2007: Probabilistic Inference Algorithms and Machine Learning, University of Toronto

University of Toronto
Department of Electrical and Computer Engineering

ECE1508, Fall 2007: Probabilistic Inference Algorithms and Machine Learning

Instructor: Brendan J. Frey
Email: frey psi toronto edu
Office: 4136, Bahen Centre, 40 St. George St.

Time: Wednesday, 2:10pm-4:00pm
Location: Bahen 4164

NOTE: NO LECTURE ON WEDNESDAY NOV 28

PROJECT DUE FRIDAY NOV 30 BY NOON AT MY OFFICE (BA4161) -- PLEASE PICK UP A COURSE EVALUATION SHEET AT THAT TIME AND SUBMIT IT AT THE FINAL EXAM

FINAL EXAM: WEDNESDAY DECEMBER 5, 2.10PM-4.00PM
Final exam from 2003
Final exam from 2006

Description of Assignment/Project due Nov 28.
Toy Data
Real Data (handwritten digits)
MATLAB function for regular factor analysis
MATLAB function for k-centers clustering

Reading materials
Readings:
Review paper: A comparison of algorithms for inference and learning
Textbooks:
C.M. Bishop. Pattern Recognition and Machine Learning, Springer, 2006.
M.I. Jordan. Introduction to Probabilistic Graphical Models, 2005, Online. (Click to access chapters -- do not distribute)

Lectures

Sep 12: Introduction, Motivation, Function Learning, Review of Probability, Maximum Likelihood, Review of Information Theory | Slides - part A | Slides - part B

Sep 19: Bayesian Learning, Estimation Theory, Pattern Classification, Decision Theory | Slides - part A | Slides - part B

SEP 28: Neural Networks, Kernel Methods, Clustering, Affinity Propagation | Slides - part A | Slides - part B

Oct 3: Bayesian Networks, Factor Graphs and Markov Random Fields | Slides

Oct 10: Learning Bayesian Networks, the EM algorithm | Slides - part A | Slides - part B

Oct 17: MIDTERM EXAM, 2.10pm-4.00pm, closed book, covers up to and including learning Bayesian networks and the EM algorithm

Oct 24: Exact Probabilistic Inference | Slides

Oct 31: Approximate Probabilistic Inference | Slides

Oct 24: Learning using Free Energy, Vision Example, ICM, Gibbs Sampling | Slides

Nov 5: Exact EM and Variational Methods | Slides

Nov 12: Variational Methods Continued | Slides

Nov 19: Loopy Belief Propagation, Summary of Methods | Slides

Nov 26 (last lecture): Layered Vision | Slides

Course description
Algorithms for automatically analyzing images, video, biological sequences, biological sensory data, audio, communication signals, text, and other types of data should take into account the uncertain relationships between inputs, intermediate representations, and outputs. Probability theory can account for these uncertainties, and provides a way to pose information processing problems as the computational task of learning an appropriate probability model and computing conditional probabilities using the model. Complex probability models for real-world applications often involve millions of random variables and intractable density functions, so probabilities cannot be computed using straightforward approaches.

This course examines the fundamental concepts of graph-based formulations of complex probability models and introduces computationally efficient techniques for computing probabilities and estimating parameters in these models.

Topics covered include:

Bayesian networks
Markov random fields
Factor graphs
Probabilistic inference and why its "optimal"
Marginalization versus Maximization
Maximum likelihood learning
Bayesian learning
The elimination algorithm
Probability (belief) propagation and the sum-product algorithm
The EM algorithm for MAP estimation
Factor analysis (and principal components analysis)
Mixtures of Gaussians and generalized mixture models
Hidden Markov models
The forward-backward algorithm and the Baum-Welch algorithm
Kalman filtering and adaptive Kalman filtering
The leaf-root-leaf algorithm in trees
Approximate inference techniques and the generalized EM algorithm
Loopy belief propagation
Iterated conditional modes
Mean field methods
Variational techniques
Bethe and Kikuchi free energy minimization
Convexified free energies
Inference using linear programming
Markov chain Monte Carlo techniques

In addition to introducing new concepts in conjunction with toy examples, we will survey applications in the following areas:

Image and video analysis
Bioinformatics
Digital Communication

Prerequisites include introductory courses in probability, statistics, calculus and linear algebra. Some background in information theory and continuous optimization will be helpful, but not necessary.

Grading:
Project (Comprehensive assignment): 35%
Midterm exam: 25%
Final exam: 40%