Source-linked AI summary
Complexity Results and Approximation Strategies for MAP Explanations
A. Darwiche, J. D. Park
TL;DR
MAP is harder than related inference tasks, motivating the search for practical methods despite limited guarantees. The paper establishes complexity barriers, introduces a general approximation framework with two instantiations, and reports improved solutions and accurate MAP estimates across networks.
Problem
MAP is difficult to compute and approximate, even when probability inference and MPE are easy or the network is restricted to polytrees.
Method
The paper develops a generic local-search framework with instantiations for networks amenable and not amenable to exact probability inference.
Results
The proposed approximation methods produce much better solutions than MPE and ML and extend MAP approximation to networks that work well with belief propagation.
Takeaways & Limitations
Best-effort MAP approximation can provide useful solutions where exact computation is infeasible, including networks too complex for exact probability inference or MPE.
Takeaways & Limitations
Variable elimination requires exponential time on some polytrees, and the local-search method assumes sufficiently small unconstrained width for efficient search steps.
Abstract
from arXiv · showhide
MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases.
1. Introduction
The paper studies the computational complexity of MAP in Bayesian networks and develops best-effort approximation methods because exact and approximate solutions can be difficult even in restricted settings.
- MAP finds the most likely configuration of selected variables given partial evidence about the remaining variables.
- MPE fixes complete evidence for the variables outside the explanation set, making it a specialization of MAP.
- MPE-based explanations can include unknown variables irrelevant to the explanation, and projecting them away usually does not yield the most likely MAP configuration.
- MAP is substantially harder than MPE or computing the probability of evidence, with exact or approximate solutions lacking guarantees even under restricted circumstances.
- The paper proposes a general local-search framework and two instantiations for networks with either tractable or intractable exact probability inference.
2. MAP Complexity
MAP combines probability computation with optimization, making it substantially harder than Pr and MPE. The paper proves strong complexity and variable-elimination barriers, including hardness on polytrees and severe approximation limits.
- General complexity: MAP combines counting and optimization, unlike MPE's optimization-only structure and Pr's counting problem.Computing a candidate MAP probability requires a Pr query, while optimization chooses among candidate instantiations.
- General complexity: D-MAP is NPPP-complete, even for depth-2 networks with no evidence, Boolean variables, and parameters in [1/2 + ǫ].The same completeness result holds for any fixed ǫ > 0.
- General complexity: Approximating MAP within any factor f(n) is NP-hard.This follows from MAP's inherited non-approximability through the Bayesian-network simulation of SAT.
- Variable elimination: MAP variable-elimination orders must place maximization after projection, often producing widths much larger than for Pr or MPE.Although other valid orders can interleave variables, Theorem 5 shows an equal-width order exists with all MAP variables eliminated last.
- Variable elimination: Constrained widths rise dramatically with the number of MAP variables: at X = 25, widths range from 22 to 34 versus unconstrained widths of 11 to 18.The weighted average exceeds 30, while problems with very few or very many MAP variables are significantly easier.
- MAP on polytrees: MAP remains difficult on polytrees: it is NP-complete, elimination algorithms require exponential resources on some polytrees, and approximation within 2n^ǫ is NP-hard.The hardness applies for any fixed ǫ with 0 ≤ ǫ < 1, ruling out constant, polynomial, and subexponential-factor guarantees.
3. Approximating MAP when Inference is Easy
The paper develops local-search approximations for MAP when inference is tractable, efficiently scoring neighboring MAP assignments and testing multiple search and initialization strategies.
- Framework: The framework separates MAP into optimization over MAP variables and inference for candidate scores, allowing approximation of either component.This supports algorithms that combine exact or approximate inference with local optimization.
- Search Methods: Local search starts from an initial MAP assignment and repeatedly moves to a neighboring assignment with higher Pr(s, e).A neighbor changes the value of one MAP variable, and binary variables yield |S| neighbors.
- Computing Neighbor Scores Efficiently: Neighbor scores can be computed in O(n exp(w)) time and space using inference over evidence indicators and partial derivatives.The width w is from an unconstrained elimination order, making each search step efficient when that width is manageable.
- Experimental Results: Search methods found the optimal solution in the majority of cases even from random starts and outperformed mini-bucket approximations on every tested network.Hill climbing did not improve beyond its first peak, whereas taboo search sometimes improved on that peak.
- Experimental Results: Taboo search generally outperformed hill climbing, while search methods typically improved substantially over initialization alone.Taboo search with sequential initialization performed best overall but required the most network evaluations.
4. Approximating MAP when Inference is Hard
When exact inference is intractable, the paper uses approximate inference within local-search methods to approximate MAP. Experiments report improvements over standard initialization and approximation techniques, though performance can degrade in deterministic networks.
- Approximation framework: Belief propagation replaces exact inference when inference itself is intractable, supplying approximate scores for MAP local-search neighbors.The method uses belief propagation for inference and local search for optimization.
- Approximation framework: In polytrees, a single belief-propagation run computes the quantities needed to rank neighboring MAP assignments.For loopy networks, the method ignores possible dependence of incoming messages on evidence or local CPTs.
- Approximation framework: Figure 7 compares exact and approximate retracted probabilities for 30 Barley-network variables, with true probability on x and approximate probability on y.The figure evaluates correspondence between exact and belief-propagation approximations.
- Experimental results: On synthetic and Barley problems, hill-climbing methods improved substantially over initialization methods, including MPE or ML starting points.The random-network study evaluated 59 cases with computable true MAP values; the Barley study reported improvement ratios over initialization.
- Experimental results: On Pigs, the first problems were too easy to improve, while harder instances were created by using 200 MAP variables and 20 evidence values.The initial Pigs experiment used more than 400 variables and found no improvement over ML initialization.
- Experimental results: Across real-world networks, sequential initialization performed best among approximate algorithms, while hill climbing sometimes reduced performance, especially under determinism.The authors suggest marginal computations were often more accurate than probability-of-evidence computations in these cases.
5. Conclusion
The paper concludes that MAP remains difficult even on restricted networks, but approximate inference and optimization can improve practical solutions beyond standard methods.
- Conclusion: MAP is generally too hard for exact solution, even in restricted classes such as polytrees.The conclusion also states that approximation is difficult.
- Conclusion: Belief propagation combined with stochastic hill climbing significantly improved over MPE and ML and extended MAP approximation to networks where belief propagation works well.These methods provide approximations rather than exact MAP solutions.
Proof of Theorem 2
Theorem 2 establishes MAP hardness under severe restrictions by reducing E-MAJSAT to shallow binary Bayesian networks with nearly uniform parameters. Weight variables encode consistency and satisfiability so MAP identifies the relevant assignments.
- Reduction construction: The reduction targets depth-2 networks with no evidence, binary variables, and parameters arbitrarily close to 1/2.Membership in NP^PP is assumed from an earlier theorem, while hardness is shown via E-MAJSAT.
- Reduction construction: Each logical variable and operand induces a uniformly distributed network variable, while weight variables reward consistency between operators and operands.The weight variables have the operator and operand variables as parents.
- Reduction construction: Additional binary variables attached to the top-level operator weight states in which the formula is satisfied.The construction uses r such variables for satisfiability weighting.
- Probability separation: Setting all weight variables true yields a configuration whose probability separates consistent satisfying assignments from inconsistent or unsatisfying assignments.The proof chooses r so one consistent satisfying instance outweighs the aggregate contribution of the other cases.
- Reduction conclusion: Including the evidence variables as MAP variables removes the need for evidence and makes the thresholded MAP query equivalent to E-MAJSAT.The proof uses the fact that true weight-variable assignments are at least as probable as false assignments.
Proof of Theorem 8
Theorem 8 shows that even approximating MAP on polytrees within the stated relative factor would allow polynomial-time SAT solving. The proof repeats a weighted construction enough times to separate satisfiable from unsatisfiable instances while keeping the network polynomial in size.
- Reduction strategy: The proof repeats the construction from Theorem 7 polynomially many times and connects copies into a polytree.Each copy receives a variable B_i, with links between successive copies.
- Size bound: The constructed network has q(2n + 2) variables and CPTs with at most 2(m + 1)^2 parameters, yielding a polynomial-size reduction.The proof bounds the total reduction size by q(m + 1)^2(4n + 4).
- Satisfiability separation: The construction distinguishes satisfiable instances, where k = m, from unsatisfiable instances, where k ≤ m − 1, through separated bounds on the approximate MAP value.Here k is the maximum number of simultaneously satisfiable clauses.
- Hardness consequence: Because the satisfiable and unsatisfiable bounds do not overlap, the assumed approximation would decide SAT in polynomial time.The network construction and bound tests are themselves polynomial-time procedures.
Appendix B. Generating Random Networks
The experiments used several types of generated networks, with two methods for generating structure and one parametric method for generating quantification.
- The experiments used several types of generated networks.
- Network structure was generated using two methods.
- Network quantification was generated using a single parametric method.
B.1 Generating the Network Structure
Network structures were generated using two parameterized methods: one based on variable count and connectivity, and another based on variable count and edge probability.
- The first structure-generation method is parameterized by the number of variables N and connectivity c.It tends to produce structures with widths close to c.
- The first method tends to produce structures with widths close to c.
- The second method is parameterized by the number of variables N and edge probability p.
- For the second method, edges are added between ordered variables with probability p and directed toward the later variable.
B.2 Quantifying the Dependencies
Dependencies were quantified using a bias parameter b: root CPT values were uniform, while non-root values were generated as biased complementary probabilities.
- The quantification method is parameterized by a bias parameter b.
- CPT values for root variables were chosen uniformly.
- For non-root nodes, one value was chosen uniformly in [0, b), and the other was set to 1 −v.
- At b = 0, quantifications are deterministic, while b = .5 produces uniformly random quantifications.