Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Learning Polytrees
Sanjoy Dasgupta
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
Pages: 134-141
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"

hosted by DSL   •   site info   •   help