Stochastic Systems Group  

In this talk, we show how a graphical model learning problem can be presented as a purely combinatorial problem. This allows us to analyze the computational hardness of the learning problem, and devise global optimization algorithms with proven performance guarantees. Furthermore, it introduces the problem to the algorithms community, hopefully yielding future improved algorithms.
A random vector indexed by an undirected graph is a Markov network (also known as Markov random fields) over the graph if every random variable is independent of all others, given its neighbors in the graph. For a specified triangulated graph (i.e. having no minimal cycles of more then three vertices) of bounded clique size, the maximum likelihood Markov network over the graph can be found explicitly and efficiently. We are concerned with the case in which the graph structure is not known, and one wishes to find the maximum likelihood triangulated graph of bounded clique size.
Chow and Liu (1968) analyzed the problem for a cliquebound of two, in which case the permissible structures are trees. We define the appropriate combinatorial problem for the general case, and prove that the learning problem is NPhard even for a cliquebound of three. We present a polynomialtime algorithm that finds, for any constant cliquebound k, a graph with gain in log maximum likelihood, over a fully independent model, within a multiplicative constant c(k) of the optimal gain.
Joint work with Tommi Jaakkola and David Karger.
Problems with this site should be emailed to jonesb@mit.edu