The MAP problem: Definition, algorithm and complexity.
MAP is NP^{PP}
Q: The material from this week is very dense. On what level of detail are we expected to (re)produce?
A: you are not expected to replicate proofs at the exam.
Maximum A posteriori Probability. The problem of finding the joint value assignment of variables in a Bayesian network, given some observed variables.
Can be interpreted as the Bayesian network's approach to inference of the best explanation.
This because it can be used for comparing hypotheses and selecting the best one. Where "best" is defined as "most probable" within a set of candidate hypotheses.
This notes an important distinction with abduction . We now already assume a set of hypotheses, so the problem of generating hypotheses has already been solved!
Defining MAP
I don't bother too much with the formalizations.
Input:
- Graph and probability distribution; types of vertices:
- Evidence nodes E with joint value assignment
- Intermediate nodes I
- Explanation set H (i.e. variables that are to be explained)
Output:
- argmax Pr(h|e), so the most probable joint value assignment h for nodes H.
- Or 0 if there is no satisfying assignment.
The special case where there are no intermediate nodes (I is empty) is called MPE, for "most probable explanation". In this case you only do maximization because Pr(h|e) is proportional to P(h|e) (i.e. P(e) is just a normalization constant).
Because Pr(h|e)=Pr(h,e)/Pr(e), and Pr(e) is a fixed normalization constant because the evidence is given, it is sufficient to compute argmax Pr(h,e) instead.
So the MAP problem turns into the problem of efficiently computing the most probable joint distribution over the explanation set H instead.
This requires you to marginalize out the intermediate variables.
Together, we have a max-sum-product computation:
- maximize h
- sum over set I
- take the product over all conditional probabilities $Pr(V_{i}|\pi(V_{i}))$ where i indicates an intermediate variable in I.
So you get rid of I by summing all options out, and you get rid of variable H by taking the argmax at after having summed out everything other than the evidence. You do this with a variable elimination algorithm (smartly choose the order of elimination, taking into account dependencies).
You reorder the computations so you do not have to sum and max over the whole field of joint probabilities, but instead you try to do them as local as possible.
The variable elimination algorithm is the default exact approach to Bayesian inference.
How hard is MAP?
Bayesian inference (applying conditionalization to get a new posterior credence on H) is NP-hard, because you need to marginalize over a potentially exponential (w.r.t. input variables) number of values in the normalization constant.
The INFERENCE problem is the decision problem whether Pr(H=h|E=e) > q for rational q.
MAP is even harder, because you also need to find a maximum out of a potentially exponential number of joint value assignments.
So there are not one, but two sources of exponential complexity that work on top of each other.
Even if the inference part is tractable, the second part of maximization is still making the problem intractable. Similarly, even if the maximization is constrained, you need to avoid marginalizing over an exponential amount of values.
"MAP happens to be complete for the complexity class $NP^{PP}$ (pronounce "NP with a PP oracle").
What does that mean? This complexity class is defined using Oracle Turing Machines.
The canonical $NP^{PP}-complete$ problem is E-MajSat.
Park and Darwiche (2004) have proven that MAP is $NP^{PP}-complete$ by reducing E-MajSat to MAP (meaning MAP is at least as hard as E-MajSat and thus also $NP^{PP}-complete$).
Insight (informal): for Bayesian networks this usually involves a combination of a) selecting and b) probabilistic inference.
The point of proving how hard a problem is not to show that there's no point in trying, but rather to more clearly specify what it would take to solve the problem.
Identifying the sources of complexity is also important for doing a parametrized complexity analysis: which sources do we have to eliminate for the algorithm to become tractable again?
Proof: Reduce E-MajSat to MAP
The E-MajSat problem:
- Input: Have a boolean formula $\phi$ with n variables, partitioned into two sets $X_E$ and $X_M$.
- Decision problem: Is there a truth assignment to $X_E$ such that the majority of truth assignments to $X_M$ satisfies $\phi$, together with the given assignment over $X_E$.
MAP as decision problem:
- Input: Bayesian network (G, Pr) with V divided in E, I, H.
- Decision problem: is there a joint value assignment h such that Pr(h,e) > q?
Running example: $\phi = ( \neg(x_1 \lor x_2)) \land (x_3 \lor \neg x_4)$ with $X_E=x_1,...,x_k$ and $X_M = x_{k+1},...,x_n$ for $1 \leq k \leq n$.
Construct a Bayesian network corresponding to this formula (see the previous lecture 6 for an example).
Proof. We have to show that MAP can be a) verified in polynomial time (so NP) b) specifically on a machine with oracle access to inference!
- For the verification we have a certificate, namely a joint value assignment over all explanation variables H.
- The inference oracle is used to decide Pr(h,e) > q in polynomial time
- We need to marginalize over all intermediate variables, but this is itself NP-hard (I think?)
- REVIEW: We need this because ... we need the reduction to be done in polynomial time?
- Set $V_{\phi} = true$ as evidence.
- Set q = 1/2.
- if $\phi$ is a yes-instance, then by definition there must exist some truth assignment over $X_E$ such that the majority of truth assignments over $X_M$ satisfies $\phi$. This is true by definition of the decision problem.
- REVIEW: We know majority $#sat > 2^{|M|-1}$
- Conversely, if we know some joint value assignment h exists such that $Pr(h, V_{\phi} = true) > q$, then the corresponding assignment over $X_E$ must be such that the majority of assignments over $X_M$ satisfies $\phi$.