We consider the task of learning the maximum-likelihood polytree from data. Our first result is a performance guarantee establishing that the optimal branching (or Chow-Liu tree), which can be computed very easily, constitutes a good approximation to the best polytree. We then show that it is not possible to do very much better, since the learning problem is NP-hard even to approximately solve within some constant factor.
Keywords: polytree, learning structure, approximation algorithm
PS Link: http://www.cs.berkeley.edu/~dasgupta
PDF Link: /papers/99/p134-dasgupta.pdf
AUTHOR = "Sanjoy Dasgupta
TITLE = "Learning Polytrees",
BOOKTITLE = "Proceedings of the Fifteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-99)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1999",
PAGES = "134--141"