Learning Polytrees
This addresses the computational challenge of learning polytrees for researchers in machine learning and statistics, though it is incremental as it builds on existing approximation and hardness results.
The paper tackles the problem of learning the maximum-likelihood polytree from data, showing that the optimal branching (Chow-Liu tree) provides a good approximation to the best polytree, but proves that the learning problem is NP-hard to approximate within a constant factor.
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.