Exact and Approximate Algorithms for Polytree Learning

Abstract

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of 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 for arbitrarily small and any constant in-degree bound , improving over the fastest previously known algorithm of time complexity . We further give polynomial-time algorithms for finding a polytree whose score is within a factor of from the optimal one for arbitrary scores and a factor of for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.