Exact and Approximate Algorithms for Polytree Learning

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 $\mathcal{O}((2+\epsilon)^n)$ for arbitrarily small $\epsilon > 0 $ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $\mathcal{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.

Modern AI systems often reason about uncertainty by modeling how variables — say, symptoms, diseases, and test results — influence each other. A standard tool is the Bayesian network, a diagram of these influences. In general, these networks are slow to query, so practitioners often prefer a simpler shape called a polytree, in which the underlying connections form no cycles. Polytrees are fast to use, but finding the best one from data is computationally intractable: in particular, the number of candidate diagrams explodes with the number of variables. We study how much that intractability can be tamed. Our new exact algorithm finds the best polytree noticeably faster than the previously known ones whenever each variable depends on at most a small fixed number of others. We also give fast "approximation" algorithms that produce a polytree provably close to optimal, even when finding the very best one is hopeless. Matching mathematical lower bounds show that many of our running times and approximation ratios cannot be substantially improved unless long-standing conjectures in theoretical computer science are wrong.