Approximating MAP using Local Search

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network, given (partial) evidence about the complement of that set. Unlike computing priors, posteriors, and MPE (a special case of MAP), the time and space complexity of MAP is not only exponential in the network treewidth, but also in a larger parameter known as the "constrained" treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computing priors, posteriors or MPE. For this reason, MAP computations are generally avoided or approximated by practitioners. We have investigated the approximation of MAP using local search. The local search method has a space complexity which is exponential only in the network treewidth, as is the complexity of each step in the search process. Our experimental results show that local search provides a very good approximation of MAP, while requiring a small number of search steps. Practically, this means that the average case complexity of local search is often exponential only in treewidth as opposed to the constrained treewidth, making approximating MAP as efficient as other computations.

• Publication year

  2001

• Venue

  Conference on Uncertainty in Artificial Intelligence

• Publication date

  2001-08-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1301.2299
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Recursive conditioning

  2001cited by this paper
• Probabilistic Networks and Expert Systems

  2001cited by this paper
• Stochastic Greedy Search: Efficiently Computing a Most Probable Explanation in Bayesian Networks

  2000cited by this paper
• Any-Space Probabilistic Inference

  2000cited by this paper
• A differential approach to inference in Bayesian networks

  2000cited by this paper
• Partial abductive inference in Bayesian belief networks using a genetic algorithm

  1999cited by this paper
• Stochastic local search for Bayesian network

  1999cited by this paper
• Probabilistic Networks and Expert Systems

  1999cited by this paper
• Bucket elimination: A unifying framework for probabilistic inference

  1996cited by this paper
• Inference in belief networks: A procedural guide

  1996cited by this paper
• Exploiting Causal Independence in Bayesian Network Inference

  1996cited by this paper
• Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard

  1993cited by this paper
• Local computations with probabilities on graphical structures and their application to expert systems

  1990cited by this paper
• The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

  1990cited by this paper
• Triangulation of Graphs { Algorithms Giving Small Total State Space Triangulation of Graphs { Algorithms Giving Small Total State Space

  1990cited by this paper
• Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

  1990cited by this paper
• Probabilistic reasoning in intelligent systems

  1988cited by this paper

• Speeding up approximate MAP by applying domain knowledge about relevant variables

  2024cites this paper
• Counting and Sampling Directed Acyclic Graphs for Learning Bayesian Networks

  2019cites this paper
• Survey on Models and Techniques for Root-Cause Analysis

  2017cites this paper
• Exact Algorithms for MRE Inference

  2016influential citation
• Scalable MAP inference in Bayesian networks based on a Map-Reduce approach

  2016cites this paper
• An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks

  2015influential citation
• Learning Bayesian networks from data by the incremental compilation of new network polynomials

  2015cites this paper
• Extracting Scenarios from a Bayesian Network as Explanations for Legal Evidence

  2014cites this paper
• Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams

  2014cites this paper
• Treewidth and the Computational Complexity of MAP Approximations

  2014cites this paper
• Mining Online Text Data for Sentiment and News Impact Analysis

  2013cites this paper
• Most Inforbable Explanations: Finding Explanations in Bayesian Networks That Are Both Probable and Informative

  2013cites this paper
• Portfolios in Stochastic Local Search: Efficiently Computing Most Probable Explanations in Bayesian Networks

  2011influential citation
• Most Relevant Explanation: computational complexity and approximation methods

  2011cites this paper
• Integrating Probabilistic Reasoning with Constraint Satisfaction

  2011cites this paper
• Computational complexity and approximization methods of most relevant explanation

  2010cites this paper
• Disease Models, Part II: Querying & Applications

  2010cites this paper
• Probabilistic error analysis models for nano-domain vlsi circuits

  2010cites this paper
• Understanding the scalability of Bayesian network inference using clique tree growth curves

  2010cites this paper
• Maximum error modeling for fault-tolerant computation using maximum a posteriori (MAP) hypothesis

  2009cites this paper
• Efficient Computation of Jointree Bounds for Systematic MAP Search

  2009cites this paper
• Study of Circuit-Specific Error Bounds for Fault-Tolerant Computation using Maximum a posteriori (MAP) Hypothesis

  2009cites this paper
• Understanding the role of noise in stochastic local search: Analysis and experiments

  2008cites this paper
• On probabilistic inference by weighted model counting

  2008cites this paper
• Likelihoods and Explanations in Bayesian Networks

  2008cites this paper
• Finding Minimum Data Requirements Using Pseudo-independence

  2008cites this paper
• Efficient Probabilistic Diagnostics for Electrical Power Systems

  2008cites this paper
• System Diagnosability Analysis Using p-slop MAP

  2007cites this paper
• Dynamic Weighting A* Search-based MAP Algorithm for Bayesian Networks

  2007cites this paper
• Probabilistic maximum error modeling for unreliable logic circuits

  2007cites this paper
• Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering

  2006influential citation
• Preprocessing the MAP Problem

  2006cites this paper
• Solving Factored MDPs with Hybrid State and Action Variables

  2006cites this paper
• Calculating Likelihoods in Bayesian Networks

  2006cites this paper
• An Anytime Scheme for Bounding Posterior Beliefs

  2006cites this paper
• Planning in hybrid structured stochastic domains

  2006cites this paper
• Exploiting graph cutsets for sampling-based approximations in bayesian networks

  2006cites this paper
• Importance sampling for bayesian networks: principles, algorithms, and performance

  2006cites this paper
• Solving MAP Exactly by Searching on Compiled Arithmetic Circuits

  2006cites this paper
• Diagnostic problem solving using swarm intelligence

  2005cites this paper
• Stochastic Local Search for Solving the Most Probable Explanation Problem in Bayesian Networks

  2004cites this paper
• Abductive Inference in Bayesian Networks: A Review

  2004cites this paper
• A differential semantics for jointree algorithms

  2004cites this paper
• The Minimum Information Principle for Discriminative Learning

  2004cites this paper
• Annealed MAP

  2004influential citation
• Morphing the Hugin and Shenoy-Shafer Architectures

  2003cites this paper
• Solving MAP Exactly using Systematic Search

  2002influential citation
• Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference

  2002cites this paper
• MAP Complexity Results and Approximation Methods

  2002influential citation
• A differential approach to inference in Bayesian networks

  2000cites this paper
• Map Search in Bayesian Networks Using Joint Bounds

  year unknowncites this paper