Exact and Approximate Algorithms for Polytree Learning
For researchers in Bayesian network structure learning, this work advances the state of the art by offering faster exact algorithms and new approximation guarantees for polytree learning.
The paper studies the NP-hard problem of learning optimal polytrees from data, providing an exact algorithm with runtime O((2+ε)^n) for bounded in-degree, improving over the previous O(3^n), and polynomial-time approximation algorithms with constant factors.
Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.