CSAIL Event Calendar: Previous Series
|
An Algorithmic Approach to Maximumum Likelihood Markov Network Structure Speaker: Nathan Srebro , MIT Laboratory for Computer Science 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. See other events that are part of CSAIL Student Seminar Fall 2000 |
