I designed this course while I was an intern at the Intel Berkeley Research Center during the summer of 2003. If you find the slides useful, you are welcome to use them (with proper credit). Please let me know if you find any typos or errors.
A Short Course on Graphical Models
Mark A. Paskin
This course covers the basics of graphical models, which are powerful tools for reasoning under uncertainty in large, complex systems. The course assumes little or no mathematical background beyond set theory, and no background knowledge of Probability Theory. The emphasis is on presenting a set of tools that are useful in a large number of applications, and presenting these tools in a rigorous but intuitive way.
The course has three lectures, each of which can be presented at a high level in 90 minutes or split into two 60 minute sessions for more depth.
| Lectures |
Slides |
| 1. |
Introduction to Probability Theory |
Motivation, probability spaces, axioms of probability, conditional probability, product rule, chain rule, Bayes' rule, random variables, densities, table densities, Gaussians, marginalization and conditioning, inference. [1, Ch. 1; 5; 2, Ch. 13; 3, Ch. 13; 9] |
 |
| 2. |
Structured Representations |
Independence, conditional independence, Bayesian networks, the Bayes Ball algorithm, Markov Random Fields, the Hammersley-Clifford Theorem, moralization, Variable Elimination, NP and #P hardness of inference. [3, Ch. 2; 5; 6; 2, Ch. 14] |
|
| 3. |
The junction tree algorithms |
Junction trees, the Shafer-Shenoy algorithm, its relation to Variable Elimination, the HUGIN algorithm, its relation to Shafer-Shenoy, the Viterbi algorithm, Generalized Distributive Law, triangulation, elimination. [3, Ch. 17; 4] |
|
| References for further study |
| [1] |
D. Bertsekas and J. Tsitsiklis (2002). Introduction to Probability. Athena Scientific, Belmont, Mass. (First chapter online.) |
| [2] |
S. Russell and P. Norvig (2003). Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs, NJ. |
| [3] |
M. I. Jordan (2003). Introduction to Graphical Models. (Forthcoming.) |
| [4] |
R. Cowell, A. Dawid, S. Lauritzen, D. Spiegelhalter (1999). Probabilistic Networks and Expert Systems. Springer, New York, NY. |
| [5] |
J. Pearl (1997). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, CA. |
| [6] |
R. Shachter (1998). Bayes-Ball: The Rational Pasttime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams). In Gregory F. Cooper and Serafmn Moral (editors), Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann1 San Francisco, CA. | |
