Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Learning Polytrees
Sanjoy Dasgupta
Abstract:
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
BibTex:
@INPROCEEDINGS{Dasgupta99,
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