Maximum Likelihood Bounded TreeWidth Markov Networks
Nathan Srebro
Abstract:
Chow and Liu (1968) studied the problem of learning a maximumlikelihood Markov tree. We generalize their work to more complexMarkov networks by considering the problem of learning a maximumlikelihood Markov network of bounded complexity. We discuss howtreewidth is in many ways the appropriate measure of complexity andthus analyze the problem of learning a maximum likelihood Markovnetwork of bounded treewidth.Similar to the work of Chow and Liu, we are able to formalize thelearning problem as a combinatorial optimization problem on graphs. Weshow that learning a maximum likelihood Markov network of boundedtreewidth is equivalent to finding a maximum weight hypertree. Thisequivalence gives rise to global, integerprogramming based,approximation algorithms with provable performance guarantees, for thelearning problem. This contrasts with heuristic localsearchalgorithms which were previously suggested (e.g. by Malvestuto 1991).The equivalence also allows us to study the computational hardness ofthe learning problem. We show that learning a maximum likelihoodMarkov network of bounded treewidth is NPhard, and discuss thehardness of approximation.
Keywords:
Pages: 504511
PS Link:
PDF Link: /papers/01/p504srebro.pdf
BibTex:
@INPROCEEDINGS{Srebro01,
AUTHOR = "Nathan Srebro
",
TITLE = "Maximum Likelihood Bounded TreeWidth Markov Networks",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "504511"
}

