Most probable explanations in Bayesian networks: complexity and tractability

DOI10.1016/j.ijar.2011.08.003zbMath1242.68332OpenAlexW2110715012MaRDI QIDQ433524

Johan Kwisthout

Publication date: 5 July 2012

Published in: International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2066/83894

zbMATH Keywords

computational complexityBayesian networksapproximationfixed parameter tractabilitymost probable explanation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Related Items (13)

MPE Inference in Conditional Linear Gaussian Networks ⋮ Explainable AI using MAP-independence ⋮ Motivating explanations in Bayesian networks using MAP-independence ⋮ Thirty years of credal networks: specification, algorithms and complexity ⋮ A computational-level explanation of the speed of goal inference ⋮ Rational analysis, intractability, and the prospects of `as if'-explanations ⋮ An evaluation of probabilistic approaches to inference to the best explanation ⋮ Tractability of most probable explanations in multidimensional Bayesian network classifiers ⋮ Approximate inference in Bayesian networks: parameterized complexity results ⋮ Competing hypotheses and abductive inference ⋮ Most frugal explanations in Bayesian networks ⋮ Learning tractable Bayesian networks in the space of elimination orders ⋮ Energy distribution view for monotonic dual decomposition

Uses Software

• NESTOR

Cites Work

• Multi-dimensional classification with Bayesian networks
• The complexity of combinatorial problems with succinct input representation
• The complexity of optimization problems
• Approximating MAPs for belief networks is NP-hard and other theorems
• Cost-based abduction and MAP explanation
• Finding MAPs for belief networks is NP-hard
• Simple characterizations of \(P(\# P)\) and complete problems
• Parametrized complexity theory.
• Financial analysis using Bayesian networks
• The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks
• PP is as Hard as the Polynomial-Time Hierarchy
• Bayesian Networks and Decision Graphs
• Inference and Learning in Multi-dimensional Bayesian Network Classifiers
• Graph minors. II. Algorithmic aspects of tree-width
• Computational Complexity of Probabilistic Turing Machines
• The Computational Complexity of Monotonicity in Probabilistic Networks
• The complexity of theorem-proving procedures
• Stochastic Boolean satisfiability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Most probable explanations in Bayesian networks: complexity and tractability