Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

An Algorithmic Approach to Maximum Likelihood Markov Network Structure
Nathan Srebro
Lab for Computer Science, MIT

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 clique-bound 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 NP-hard even for a clique-bound of three. We present a polynomial-time algorithm that finds, for any constant clique-bound 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