Learning Polytrees
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.
Cite
Text
Dasgupta. "Learning Polytrees." Conference on Uncertainty in Artificial Intelligence, 1999.Markdown
[Dasgupta. "Learning Polytrees." Conference on Uncertainty in Artificial Intelligence, 1999.](https://mlanthology.org/uai/1999/dasgupta1999uai-learning/)BibTeX
@inproceedings{dasgupta1999uai-learning,
title = {{Learning Polytrees}},
author = {Dasgupta, Sanjoy},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {1999},
pages = {134-141},
url = {https://mlanthology.org/uai/1999/dasgupta1999uai-learning/}
}