Maximum Likelihood Bounded Tree-Width Markov Networks
  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 howtree-width is in many ways the appropriate
measure of complexity andthus analyze the problem of learning a maximum
likelihood Markovnetwork of bounded tree-width.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 boundedtree-width is equivalent to finding a maximum weight
hypertree. Thisequivalence gives rise to global, integer-programming
based,approximation algorithms with provable performance guarantees, for
thelearning problem. This contrasts with heuristic local-searchalgorithms 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 tree-width is NP-hard,
and discuss thehardness of approximation.
