Notebooks

Graphical Models

14 Sep 2014 11:34

That is, statistical models in which are represented by graphs or networks: random variables are nodes, and relationships of direct statistical dependence are shown as edges. I'm sticking latent-variable and path-analysis models in here, too, because they all pretty much work the same way. It's the causal modeling angle which got me interested in this originally, and which I still think is the most important, but there are many other uses.

(Some people call all of these "Bayesian graphs" or "Bayesian networks", using "Bayes" as a metonym for "conditional probability" — there are perfectly good frequentist interpretations of these models. Others draw a distinction between "Bayesian networks", with directed edges between variables, and "Markov networks", with undirected edges. The distinction between directed and undirected is important, but "Bayes" and "Markov" don't really convey it, since directed graphs have Markov properties and one uses Bayes's rule all the time in undirected graphs.)

Things I want to understand better: frequentist inference procedures. Computational learning theory for graphical models (the paper by Janzing and Herrmann is good). How to treat directed cyclic graphs? How to treat dynamical systems and time series?

Not even a conjecture. Back in the 1960s, Chow and Liu (reference below) gave a polynomial-time algorithm for finding the best approximation to a global joint probability distribution using only pairwise interactions among the variables, i.e., the one which minimized the Kullback-Leibler divergence between the true and the approximating distribution. I have read that extending this to even three-way interactions is NP-hard, though I don't know if it's NP-complete. (1) How is the intractability result established? (2) Is this the same as the computational phase transition one finds in going from 2-SAT to 3-SAT, where the critical point is at two-point-something SAT? (Presumably the answer to (1) would shed some light on this.) (3) Even if not, is there an analogous phase transition, perhaps in a different universality class? (Update in 2009, several years later: Bento and Montanari, below, sounds relevant, but I haven't read it yet.)


Notebooks:     Hosted, but not endorsed, by the Center for the Study of Complex Systems