[Reading] An Introduction to Graphical Models

This technical report gives an introduction to graphical models. it says that graphical models are a marriage between probability theory and graph theory.

graphical models provide a natural tool for dealing with (1) uncertainty and (2) complexity. In particular, graph theory provides the notion of modularity, i.e. a complex system is built by combining simpler parts. Probability theory provides the glue whereby the parts are combined, ensuring that the system as a whole is consistent, and providing ways to interface models to data.

This graphical model framework provides a way to view several systems as instances of a common underlying formalism, ex: mixture models, factor analysis, hidden Markovmodels, Kalman filters. Probabilistic graphical models are graphs in which nodes represent random variables, and the arcs represent conditional independence assumptions. They provide a compact representation of joint probability distributions.

There are two main kinds of graphical models: undirected and directed. In a directed graphical model (a Bayesian network), an arc from A to B can be informally interpreted as indicating that A causes B. We can see that the conditional independence relationships allow us to represent the joint more compactly.

Talking about inference, its goal is to estimate the values of hidden nodes, given the values of the observed nodes. In particular, we can use the conditional independence assumptions encoded in the graph to speed up exact inference. The key idea of the variable elimination algorithm (and many others) is to "push" the sums in as far as possible. Also, if we wish to compute several marginals at the same time, we can use dynamic programming to avoid the redundant computation that would be involved if we used variable elimination repeatedly. The reason why we use approximate inference is that the running time of these exact algorithms is exponential in the size of the largest cluster , and minimizing it is NP-hard. When it is large, it is necessary to use approximate inference.