Information
Description: This course will serve as a thorough overview of
graphical models including Bayesian networks, undirected models, and
factor graphs.
- 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.).