Lecture 8: Most Frugal Explanations in Bayesian networks

Last week we already discussed that even approximations of MAP are NP-hard, unless some very explicit constraints are added to the MAP-problem.

These constraints are very limiting if you want to use Bayesian networks in the field of perception, for example.

Apart from approximations, there are also heuristics to consider.

Today we discuss a 2015 paper from Johan Kwisthout on "Most Frugal Explanations".

Frugal: being very economic; do not do all computations but be very economic in which computations you do.

  • Why, what, and how?
  • Most frugal explanation is even more complex than the MAP-problem itself, when unconstrained. (Surprising!)
  • However, the parametrized tractability of MFE has more realistic parameter assumptions than MAP.

Def:

MFE: best explanation is explanation that is most probable for the maximum number of joint value assignments to the irrelevant intermediate variables

You sample values for the irrelevant intermediate variables instead of pruning them.

Some quick notes

MFE is a good approximation of MAP only if all intermediate variables that are actually relevant are also taken as relevant in MFE (i.e. marginalized over).

But note that MFE can only guarantee to give the MAP unless we designate all variables as relevant; in which case it degenerates into MAP.

  • Note that MFE maintains isometry and Being Quinean (p.57) which are important (according to Fodor) for non-demonstrative inferences (and the frame problem).
  • Specifically, this is the case because irrelevant variables are not pruned i.e. we instead use a sampling strategy to assign any value to variables that are estimated to be relevant. (60)
    • They are still part of, and influence, the overall belief system (Being Quineian)
    • They are not pruned and may become relevant when new evidence arises (isometry).

Removing conditionally independent (on the explanatory variable) variables is not enough; may still be many.

In general the posterior probability distribution of a (discrete) Bayesian network is often skewed in purpose, which is desirable in this case. (57)

The more relevant variables are includes, the more skewed towards one explanation the distribution of MFE explanations is.

This "skewness" is worked out as decisiveness (64).

MFE is intractable but can be approximated with expectation-approximation under certain parametrized situations. (65)

Chapter 8: Types of approximation

What sort of approximation can you find for inference to the best explanation? And what would be the complexity?

We're happy with an answer within some error bound e of the true probability.

But this is not possible for a posterior probability, if you take the evidence into account. That again makes the problem intractable in general (NP-hard in general).

What is a suitable notion of approximation for MAP? Will the second- or third- most probable also do? Kwisthout calls this a "rank approximation"

If I can't get the most probable explanation, can I instead get an explanation with a probability that is almost as probable? The second best may have a way lower probability, so this is a different issue than the "rank approximation" approach.

And what if all explanations are very close to each other? Then these methods may produce bad results anyway.

What if we get a solution that is structurally similar from the best explanation? E.g. it only different in one or very few variables (even though it may be quite wrong there).

Why is this relevant?

If you show that one notion of approximation leads to an intractable algorithm, this does not necessarily mean that the others also are intractable approximations!

Value approximation

Expect the value of the approximation to be close to that of the optimal solution.

Additive: the absolute difference has to be smaller than e.

Relative: the ratio between optimal and approximate should be smaller than e.

Lecture notes, p.51: both are intractable.

Note that Kwisthout's MFE paper uses relative value approximation ( if I remember correctly ).

Structure approximation

Instead measure structure difference with a solution distance function. For MAP, the Hamming distance is appropriate.

N.B. Hamming distince is used in Kwisthout's MFE paper.

Rank-approximation

Instead, ensure that your approximation is in the top m best explanations.

In this type of approximation, it is most obvious that the solution may look completely different both in terms of value and structure.

Expectation-Approximation

We can also use a stochastic algorithm for approximation. In that case it makes sense to work with expectations.

It's a good "expectation-approximation" when the expectation that the approximate solution does not equal the optimal solution, is smaller than some error bound e.

Theoretical argument against tractable expectation-approximation: PP is at least as hard and often even harder than NP, so if we would find a tractable algorithm we would also solve NP. But we do not believe that is possible.

Only tractable approach: have constraints on nature of the MAP problem:

  • Not too many intermediate variables for marginalization (big constraint)
  • Limited amount of hypotheses
  • Or best hypothesis is guaranteed to have high probability
  • Bounded tree width network.
  • Background knowledge about relevance of variables

Below we discuss Kwisthout's heuristic approach called Most Frugal Algorithms.

MAP problem intro

ALARM network, with hypothesized causes, observable findings, intermediate variables.

All hypothesis is powerset of all hypothesized causes, i.e. all join value assignments over all potential hypothesized causes (so in the thousands).

Intermediate example: you cannot directly measure heart rate. You have to infer that from other measurements, e.g. pulse in the wrist.

This is not a binary variable network. Many are binary, but many are not.

Known complexity properties of MAP

  • MAP is NP^PP (NP with a PP oracle) and therefore strictly harder than MPE and INFERENCE. (it's still NP-hard even if you have that oracle!) (Park and Darwiche, 2004)
  • MAP is still NP-hard in general if have bounded treewidth and cardinality (De Campos, 2011)
    • Cardinality: E.g. binary variables, still NP-hard.
    • Treewidth: look back, I didn't get this, about 10 min in the lecture.
  • NP-hard to approximate MAP even on polytrees (Park and Darwiche, 2004)

When does MAP become tractable?

  • Bounded both treewidth, cardinality, and intermediate variables (Kwisthout, 2011)
    • Relatively trivial, because then you have way less marginality
  • If MAP explanation is very likely and treewidth and cardinality are bounded (Bodlaender et al, 2002; Kwisthout 2011)
    • Unlikely for very big networks

Are these constraints reasonable in real-world large networks?

Not all intermediate variables are relevant for a given inference query

Druzdzel and Suermondt (1994): more a given inference query, most intermediate variables are not relevant. I.e. they don't contribute much to finding the best explanation.

This means that another strategy would be to leave out irrelevant variables. Can we exploit this with a heuristic, to avoid marginalizing over irrelevant intermediate variables?

If you assign a variable a random valuable, does the best explanation change? If consistently the answer is no, then the variable is not (very) relevant.

You widen this reasoning to join value assignments. If the majority (60%? 70%?) of value assignments results in the same best explanation, you could still consider that group of variables as irrelevant.

  • Sample over the irrelevant nodes: what's the majority explanation?
  • Marginalize over the relevant nodes

This means that in computing MAP, you can just give them a random value, as if they are evidence. This allows you to strongly reduce all factors in which they occur.

What happens if sampling over irrelevant does not yield a majority explanation? (e.g. in a random network). Graph likes this is discussed in

MFE: best explanation is explanation that is most probable for the maximum number of joint value assignments to the irrelevant intermediate variables

Properties

  • MFE = MAP if all variables are relevant
  • if you designate all intermediate variables as relevant, the heuristic approximations results of MAP
  • if relevance is misunderstood and you do not designate all relevant variables, then MFE and MAP diverge

The more relevant variables are included (as relevant), the more the distribution of MFE is skewed towards a single explanation.

So now we need a procedure to find which variables are relevant.

Computational specification

See slide and pay attention to red text.

Input:

Output:

Which variables are relevant?

Intrinsic relevance of variable I, R(I) = Int / {I}. REVIEW.

If this variable matters, the MFE will be different (in most cases) when you set this variable to false instead of true.

If it's always dependent -> R(I) = 1; if explanation is never dependent on I, then R(I)=0.

BUMMER. Computing intrinsic relevance is highly intractable.

Computations is over million for ALARM. For each one of these, you need to compute the MAP if you are interested in testing the quality of the approximation.

Then you need a relevance threshold. E.g. >20% or >80%. Stricter threshold is more efficient, but including less relevant variables will limit the approximation of MAP.

Complexity of MPE

  1. MFE is intractable because MAP is a special case!. If you do not have irrelevant variables, the problem is MAP.

  2. But you can also show MFE is strictly harder than MAP (in a bigger complexity class).

  3. Stays intractable when bounded on treewidth, cardinality, relevant variables are bounded.
  4. However, this problem can be approximated efficiently by sampling when the distribution of MFE explanations is "skewed" towards one explanation.
    • See from last weeks: then you need way less samples to be certain enough that your sampling is accurate.

Computing MFE is NP PP^PP! Omg...

Few natural frameworks have such weird complexity classes for problems defined over them.

Three sources of complexity on top:

  1. NP:Select join value assignment out of potential exponential candidates
  2. PP: solving inference
  3. PP: deciding what the threshold of the join value assignments is to the set of irrelevant

You are not to expected to understand the proof in the paper. Understanding the SAT variant is quite complex. The reduction itself should be understandable.

How we deal with this horrible complexity?

How can this be a usable heuristic if it's even more complex than the original problem?!

We approximate the heuristic. Nice and meta.

Given that we can sample (i.e. the skewedness of the underlying MFE(!) probability distribution), do a randomized algorithm:

  • pick random joint assignments over variables
  • compute MAP i.e. explanation h
  • Keep track of h's.
  • Do a majority vote at the end.

This is fixed-parameter tractable approximation of MFE, with parameters:

  • Treewidth: related to network topology.
  • Cardinality: maximum number of values
  • Relevant: number of variables to marginalize over.
  • Decisiveness (REVIEW SLIDE); but indicates the "skewedness" that we considered before.

  • It's OK to have many irrelevant intermediate variables

  • Best explanation does not need to have a high probability
    • Very likely with many possible explanations
  • Treewidth/cardinality of reduced XXX tree (REVIEW slide)

Simulation results

On 100 randomly constructed networks.

See slides and paper.

Measures:

  • Ratio MAP/MFE; sort of value approximation in terms of probability
  • Rank
  • Structurally: Hamming distance

TODO REVIEW: how to read the graphs from the paper?

  • gray bars are heuristic resulting explanations.
  • gray box is certainty if you settle for top 5 explanation, given 1 sample?

I completely zoned out during discussion of simulation results.

Review the second part of the lecture. Could be an exam question, I think.

There is no formal equivalent of the Hoeffing-inequality for non-binary decisions.

Conclusion

From paper, the main takeaway is:

  • Constraints that should apply
  • Importance of background knowledge
  • Conditions for efficient randomized sampling algorithm (decisiveness)

State of the art MAP algorithm is simulated annealing. Current WIP on the MFE heuristic: when can the frugal heuristic beat simulated annealing?