On the Parameterized Complexity of Polytree Learning

2021/05/20 by Grüttemeier, Niels, Komusiewicz, Christian, Morawietz, Nils · 2 citations
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2105.09675

Abstract

A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. Polytree Learning is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of Polytree Learning. We show that Polytree Learning can be solved in 3ⁿ ⋅ |I|^O(1) time where n is the number of variables and |I| is the total instance size. Moreover, we consider the influence of the number of variables d that might receive a nonempty parent set in the final DAG on the complexity of Polytree Learning. We show that Polytree Learning has no f(d)⋅ |I|^O(1)-time algorithm, unlike Bayesian network learning which can be solved in 2^d ⋅ |I|^O(1) time. We show that, in contrast, if d and the maximum parent set size are bounded, then we can obtain efficient algorithms.

Cited by

• Model-oriented Graph Distances via Partially Ordered Sets
• Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy

Related

• Learning bounded-degree polytrees with known skeleton
• Large-Sample Learning of Bayesian Networks is NP-Hard
• Learning Bounded Treewidth Bayesian Networks with Thousands of Variables
• Learning Polytrees
• Algorithms and Complexity Results for Exact Bayesian Structure Learning