.

## University of Washington, Department of Electrical Engineering## EE 512: Graphical Models -- Spring 2006 |

Office: 418 EE/CS Bldg., 221-5236

Office hours: Wednesdays, 11:30pm-12:30pm, 418 EE/CS Bldg.

Office: Sieg Tutoring Center (ground floor)

Office hours: Thursdays, 3:30-4:30pm (or by appointment), Sieg Tutoring Center

Discussion Section: Fridays, 9:30-10:30am, Sieg 128

- Intro. Graph types: conditional independence; directed, undirected, and factor models; algorithms for conditional independence (e.g., Bayes-ball, d-separation, Markov properties on graphs, factorization, Hammersley-Clifford theorems).
- Models: linear Gaussian models, mixture models, factor analysis, probabilistic decision trees, Markov Random Fields, Gibbs distributions, static conditional random fields (CRFs), multivariate Gaussians as graphical models.
- Dynamic (temporal) models: Hidden Markov Models, Kalman filtering and linear-Gaussian HMMs, linear dynamic models, dynamic Bayesian networks (DBNs), label and observation bias in natural language processing, dynamic conditional random fields (CRFs), and general dynamic graphical models.
- Chordal Graph Theory: moralization; triangulated, decomposable, and intersection graphs, $k$-trees, hyper-graphs. Tree-width and path-width parameters of a graph. Graph separators and their crossings. Relational data-base systems and joins, and phylogenetic tree construction.
- Exact Probabilistic Inference: junction trees, belief propagation in its various forms (including Pearl's formulation, Hugin, Shafer-Shenoy, Bucket-elimination, etc.); join-trees and data-structures; optimal triangulations. The elimination family of algorithms. Generalized distributed law (GDL). Relation to dynamic programming. Generality (such as Viterbi, MPE, the fast Fourier transform). NP hardness results, and NP hardness results for finding the best form.
- Inference as search: Search-based approaches to inference and how it relates to junction trees, message passing, and BP. Results from the constraint satisfaction (CSP) and SAT literatures, constraint solvers, and heuristics used in these domains. Cutset and recursive conditioning, comparison with elimination. Branch-and-bound.
- Approximate Probabilistic Inference: loopy belief propagation (BP), expectation propagation (EP), generalized belief propagation (GBP), cluster GBP, comparisons with mean-field and variational approaches, statistical physics, Bethe and Kikuchi free-energies, fixed points, recent theoretical results and open questions. Also, sampling approaches such as MCMC and particle algorithms (such as Rao-Blackwellized particle filtering). Pruning based approaches.
- Learning: learning Bayesian networks, hardness results for learning networks in the maximum likelihood sense, learning in the PAC (probably approximately correct) framework, EM for parameter and structure learning, alternating minimization, discriminative parameter and structure learning, CRF training vs. discriminatively trained HMM, other learning methods. Information theory and graphical models.
- Models in practice: Real-world static graphs. HMMs and DBNs in speech, language, and bioinformatics, QMR and Factorial HMMs, turbo-coding, low-density parity check codes, other codes on graphs, belief propagation algorithms on these graphs. Practical issues such as data structures and algorithms useful for performing inference.

Prerequisites: basic probability, statistics, and random processes
(e.g., EE505 or a Stat 5xx class or consent of the
instructor). Knowledge of matlab. The course is open to students in
all UW departments.

Course Format: Four hours of lecture (TTh 1:30-3:20
EE1-
031)
per week.

Texts: We will use one main text, but draw from two other texts:

- The main text will be "An Introduction to Graphical Models", by Mike Jordan. This text has not yet been published, but we will use a printed version available in the communications copy center.
- We will also use handouts.

A printable course overview is in PS and PDF formats, which gives more information (such as grading policy, other interesting texts, etc.).

- Midterm (solutions, statistics).
- HW4 is now ready in PDF form. (hw4 solutions, statistics).
- HW3 is now ready in PDF form. (hw3 solutions, statistics).
- HW2 is now ready in PDF form. (hw2 solutions, statistics).
- HW1 is now ready in PDF form. (hw1 solutions, statistics).

Uncertainty in Artificial Intelligence (UAI) Archive

The GMTK page

Kevin Murphy's Bayes net toolbox and collection of other software

Various Graphical Models Papers (including structure learning)

- The original Bayes-ball aper, that includes both the non-deterministic description of the algorithm, and the actual algorithm, by Ross D. Shachter, entitled Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence
- K. Murphy's brief overview of Bayes nets. March, 1995 (revised November, 1996).
- D. Heckerman, D. Geiger, D. Chickering. Learning Bayesian networks: The Combination of Knowledge and Statistical Data. Technical Report MSR-TR-94-09, Microsoft Research, March, 1994 (revised December, 1994).
- Thiesson, Bo ; Meek, Christopher ; Chickering, David Maxwell ; Heckerman, David Learning Mixtures of DAG Models, December 1997 (Revised May 1998)
- Bilmes, Jeff; A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models ICSI-TR-97-021
- Roweis, S.T. and Ghahramani, Z. A Unifying Review of Linear Gaussian Models
- H. Attias Independent Factor Analysis
- D. Heckerman. A tutorial on learning with Bayesian networks. Technical Report MSR-TR-95-06, Microsoft Research, March, 1995 (revised November, 1996).
- Learning Probabilistic Networks by Paul J. Krause, manuscript, 1998.
- NIPS 95 Workshop on Learning in Bayesian Networks and Other Graphical Models
- A Guide to the Literature on Learning Probabilistic Networks From Data literature review on learning graphical models, in IEEE Trans. on Knowledge and Data Engineering. 235Kb. Final draft submitted 29th Nov., '95
- John Binder, Daphne Koller, Stuart Russell, Keiji Kanazawa, `` Adaptive Probabilistic Networks with Hidden Variables. '' Machine Learning, 29, 213--244, 1997.
- N. Friedman. The Bayesian Structural EM Algorithm
- N. Friedman. Learning belief networks in the presence of missing values and hidden variables
- N. Fridman and D. Koller Being Bayesian about Network Structure
- H. Attias 1999. Inferring parameters and structure of latent variable models by variational Bayes. Proc. 15th Conference on Uncertainty in Artificial Intelligence.
- J. Bilmes Graphical Models and Automatic Speech Recognition UWEETR-2001-005.

Maintained by Jeff Bilmes and Chris Bartels.