Maximum likelihood Markov networks : an algorithmic approach
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. Markov networks are a class of graphical models that use an undirected graph to capture dependency information among random variables. Of particular interest are Markov networks over low treewidth graphs, under which many operations are tractable. We study the problem of finding a maximum likelihood distribution among Markov networks over graphs of bounded treewidth. We define the maximum hypertree problem, which is the problem of finding an acyclic hypergraph of bounded width, that maximizes the weight of hyperedges it covers (or equivalently, a triangulated graph of bounded clique size maximizing the weight of its cliques). We show that the maximum likelihood Markov network problem can be formulated as a maximum hypertree problem, and in fact the two problems are equivalent. This extends the work of Chow and Liu (1968) who considered the case where k = 1 (i.e. trees). We show that the maximum hypertree problem is NP-hard even for k = 2 and give the first constant factor approximation algorithm for it. More precisely, for any fixed treewidth objective k, we find a k-hypertree with an f(k) fraction of the maximum possible weight of any k-hypertree graph. Thesis Supervisor: David Karger Title: Associate Professor