Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis

DOI10.1613/JAIR.1.13138MaRDI QIDQ5094064OpenAlexFDO

Authors Niels Grüttemeier, Christian Komusiewicz

Publication date 2 August 2022

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.14724

zbMATH Keywords

machine learningBayesian networksmathematical foundations

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Recommendations

• Parameterized complexity results for exact Bayesian network structure learning
• Learning Bayesian Networks Does Not Have to Be NP-Hard
• Large-sample learning of Bayesian networks is NP-hard
• Optimal search on clustered structural constraint for learning Bayesian network structure
• Efficient structure learning of Bayesian networks using constraints

Cites work

• scientific article; zbMATH DE number 5968954 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1753154 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Approximating discrete probability distributions with dependence trees
• Color-coding
• Kernel bounds for disjoint cycles and disjoint paths
• Modeling and Reasoning with Bayesian Networks
• On finding optimal polytrees
• On the Complexity of General Graph Factor Problems
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized algorithms
• Parameterized complexity results for exact Bayesian network structure learning
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(3)

• Automatically finding the right probabilities in Bayesian networks
• scientific article; zbMATH DE number 7255155 (Why is no real title available?)
• The complexity of optimizing atomic congestion

This page was built for publication: Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5094064)