Large-sample learning of Bayesian networks is NP-hard

zbMATH Open1222.68169arXiv1212.2468MaRDI QIDQ3093225FDOQ3093225

Authors: David Heckerman, Christopher Meek, David Maxwell Chickering 

Publication date: 12 October 2011

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

Recommendations

• Learning Bayesian Networks Does Not Have to Be NP-Hard
• Learning Bayesian networks from big data with greedy search: computational complexity and efficient implementation
• Parameterized complexity results for exact Bayesian network structure learning
• Exact Bayesian structure discovery in Bayesian networks
• Learning Bayesian networks: The combination of knowledge and statistical data

zbMATH Keywords

NP-hardlearning Bayesian networkssearch complexitylarge-sample data

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25)

Cited In (62)

• The dual PC algorithm and the role of Gaussianity for structure learning of Bayesian networks
• Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks
• A ring-based distributed algorithm for learning high-dimensional Bayesian networks
• Learning the structure of Bayesian networks with ancestral and/or heuristic partition
• Testing Directed Acyclic Graph via Structural, Supervised and Generative Adversarial Learning
• A Bayesian approach for learning Bayesian network structures
• Fault trees from data: efficient learning with an evolutionary algorithm
• Title not available (Why is that?)
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• Exact Bayesian structure discovery in Bayesian networks
• Improving Bayesian network local structure learning via data-driven symmetry correction methods
• Parameterized complexity results for exact Bayesian network structure learning
• Incremental causal network construction over event streams
• Fast learning of relational dependency networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• A review on evolutionary algorithms in Bayesian network learning and inference tasks
• Labeled directed acyclic graphs: a generalization of context-specific independence in directed graphical models
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
• Parent Assignment Is Hard for the MDL, AIC, and NML Costs
• Causal inference in biomolecular pathways using a Bayesian network approach and an implicit method
• Efficient approximation of the conditional relative entropy with applications to discriminative learning of Bayesian network classifiers
• Partitioned hybrid learning of Bayesian network structures
• Structural learning of mixed noisy-or Bayesian networks
• Scalability of the Bayesian optimization algorithm.
• Learning a flexible \(K\)-dependence Bayesian classifier from the chain rule of joint probability distribution
• Predicting pediatric clinic no-shows: a decision analytic framework using elastic net and Bayesian belief network
• Structure learning of Bayesian networks using global optimization with applications in data classification
• 10.1162/jmlr.2003.3.4-5.709
• Learning factor graphs in polynomial time and sample complexity
• An efficient Bayesian network structure learning strategy
• Learning the naive Bayes classifier with optimization models
• Inference of structures of models of probabilistic dependences from statistical data
• Entropy-based pruning for learning Bayesian networks using BIC
• Network modeling in biology: statistical methods for gene and brain networks
• Learning continuous time Bayesian network classifiers
• Estimating Bayesian networks for high-dimensional data with complex mean structure and random effects
• Learning Bayesian networks from big data with greedy search: computational complexity and efficient implementation
• Counterfactual inference with latent variable and its application in mental health care
• Bayesian network models for incomplete and dynamic data
• Linkage Learning Accuracy in the Bayesian Optimization Algorithm
• Learning Bayesian Networks Does Not Have to Be NP-Hard
• BNC-PSO: structure learning of Bayesian networks by particle swarm optimization
• Learning failure-free PRISM programs
• Hybrid learning of Bayesian multinets for binary classification
• Discrete Bayesian network classifiers: a survey
• Minimal separators in dependency structures: properties and identification
• Graphical modeling of stochastic processes driven by correlated noise
• Mind change optimal learning of Bayes net structure from dependency and independency data
• A sparse conditional Gaussian graphical model for analysis of genetical genomics data
• Who learns better Bayesian network structures: accuracy and speed of structure learning algorithms
• Spectral Bayesian network theory
• The Complexity of Distinguishing Markov Random Fields
• PercolationDF: a percolation-based medical diagnosis framework
• Sum-product graphical models
• Approximate structure learning for large Bayesian networks
• The max-min hill-climbing Bayesian network structure learning algorithm
• On the incompatibility of faithfulness and monotone DAG faithfulness
• Mind Change Optimal Learning of Bayes Net Structure
• Data based identification and prediction of nonlinear and complex dynamical systems
• Streaming feature-based causal structure learning algorithm with symmetrical uncertainty
• The difficulty of being moral

This page was built for publication: Large-sample learning of Bayesian networks is NP-hard

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