Most Inforbable Explanations: Finding Explanations in Bayesian Networks that are both Probable and Informative
Notes for both the lecture and the paper.
Inference to the best explanation is more than just doing MAP. Given a joint assignment answer to MAP, it is yet another question what we will infer from this.
Sander: is most inforbable explanation similar to Lipton's loveliest explanation? (I did not get the answer) The underlying ratio is the same: the best explanation is not simply the most probable. In this case we take informativeness into account. This only partly covers what Lipton views as a lovely explanation.
More practically: a good explanation is not necessarily a (full) joint probability assignment.
The most probable explanation in MAP may still have a low probability and not warrant an inference (e.g. in a medical context).
Main complexity result:
What is important from this proof is the actual result that Most Inforbable Explanation is not harder than MAP (despite it being more expressive) when either the number of possible worlds grouped as an explanation, or the size of the encoding of these worlds in a logical sentence, is bounded. (59)
Relevant parts of nondemonstrative reasoning
In this paper we will discuss a possible computational formalization of finding an explanation which is both probable and as informative as possible, thereby combining (at least some aspects of) both the 'hypotheses-generating' and 'inference' steps of the abduction process. (328)
Inference, because "inforbable" explanations aim to be actionable, i.e. they balance probability with informativeness in such a way that the generated set of hypotheses has enough probability mass to guide action.
Hypotheses-generating, because it does not pit singleton explanations against each other. Instead, it allows returning of sets of hypotheses / possible explanations; another way of saying this is that multiple hypotheses are 'grouped' together into a new hypotheses. In this sense, most inforbable explanations offers a guide for specifying what (set of) hypotheses are appropriate.
Finding the right granularity of reasoning
There are several trade-offs to take into account when making a good explanation. The general rationale of Kwisthout's paper is to take some aspects of non-demonstrative inference or IBE into account against the background of the Bayesian MAP approach to explanation.
There is a trade-off between probability vs informativeness. You want an explanation to be informative enough to support a course of action
A singleton explanation is extremely informative, but it's probability mass may be too low.
Research lines
Bayesian IBE:
- What is relevant?
- What is "best"?
- What is considered evidence
- What is the right granularity of reasoning?
- etc.
Common question: how can we make it tractable?
Best vs. most probable trade-off
Probability, informativeness, parsimony.
- Barwise (1997): Inverse Relationship Principle: "The more specific an explanation is, the lower its probability will be."
- Contrasting explanations (Lipton 2004, Garfinkel 1981, Van Fraassen 1980): Explanations do not answer why "this" but "why this, rather than that"
- Ptolemy: "We consider it a good principle to explain the phenomena by the simplest hypothesis possible"
- Or Ockham's razor
Contrasting explanations
Alice got tenure, but Bob didn't. What's the best explanation here?
If your explanation variable is Publication Record, and you marginalize out the Quality of Teaching, you won't see why Alice got chosen.
- MAP: Both Alice and Bob have a great publication record. But why is Alice chosen?
- Contrast: Alice had good publications and high quality teaching.
- Bob was a poor teacher.
Then the question is, what variables are relevant to contrast? Not their badminton skills!
So you want to be more informative to allow for contrast (but not too specific without it making a difference, because this adds complexity!)
Hypothesis competition
See "Hypothesis Competition beyond Mutual Exclusivity" by Jonah N. Schupbach and David H. Glass. Philosophy of Science 2017 8 4:5, 810-824.
Hypotheses are not necessarily mutually exclusive and neither are they always independent!
In that case, a singleton joint value assignment does not do justice to the required explanation.
Dinosaur extinction:
- Massive volcanism
- Climate change
- Asteroid impact etc.
And massive volcanism and climate change are not independent. Choosing one or the other is not very helpful.
What's the right granularity
Assume long related symptoms.
- Patient is ill
- High probability, low information:
- Patient has pneumonia
- Patient's lungs are infected with Streptococcus pneumoniae
- Very informative, but will have low probability
- Singleton explanation would exclude many other explanations of the symptoms
Most inforbable explanation requirements
Desired output:
- High probability
- Use MAP
- Informative
- Often assumes ontology
- Succinctly encodable
See scenarios from paper that show how a single joint value assignment (singleton) is not always sufficient, and that .
Problem: you need some problem taxonomy/ontology to make sense of the probability, in order to choose an appropriate set of value assignments.
Zooming in and zooming out assumes you have levels of explanation available based on some existing ontology in the problem domain (e.g. medicine).
The notion of parsimony is independent of this ontology, however.
Kwisthout did suggest that parsimony has a link to ontology.
Q: Did I understand correctly that you suggest that using parsimony is a way of still sneaking in some ontology in the absence of an explicit ontology?
A: you assume that the sentence is describable in a succint way; therefore they sort of induce a taxonomy. If they are describable in a succint way with a logical expression, they suggest a meaningful grouping that may correspond to an ontological distinction.
Formally define explanation
In MAP -> explanation is a joint value assignment; argmax_{h}Pr(h,e)
In MIE (most informative explanation): set of joint value assignments to the hypothesis nodes
SLIDE SKIPPED VERY FAST, LOOK BACK LATER
Possible world semantics
Assume we have 6 binary variables, then we have 2^6=64 options. Assume we know the value of one must be true, then there's 32 possible worlds left (hence less informative). But we can very succinctly represent all this possible worlds with {(AS=True)} if we simply don't care about the rest. The alternative is many enumerations, which is more specific, but cannot be encoded efficiently.
Succinctness
Chosen to define it mathematically: use a short binary encoding.
At most w=O(Log2(w+1)) for w joint value assignments. (w for possible worlds)
The crux is that you use a set of partial joint assignments (to subsets of H) to succinctly describe a whole set of joint value assignments.
Kwisthout chose for a logarithmic rather than a linear constraint, because this was enough for the desired complexity results.
Decision problem variant
See paper.
If w=1, you ask for one possible world (i.e. joint value assignment) this problem degenerates to MAP. So it must be at least as hard as MAP, because MAP is a special case. But it stays within the same complexity class as MAP, i.e. it is not substantially harder.
Two weeks ago we saw that we could make MAP tractable by adding some constraints.
Here we need the additional constraint that 1) the amount of possible worlds w is low or 2) we have a succinct encoding (i.e. it does not matter if there are many possible worlds as long as we can still encode them succinctly).
Main result:
What is important from this proof is the actual result that Most Inforbable Explanation is not harder than MAP (despite it being more expressive) when either the number of possible worlds grouped as an explanation, or the size of the encoding of these worlds in a logical sentence, is bounded. (Lecture notes, p. 59)
Conclusion
- Extension of Bayesian IBE to include explanations with multiple joint value assignments
- This allows for explanations that are not singular, but have different granularities (lower informativeness). By allowing sets of assignments, you battle the probability vs. information trade-off, because the explanation can have the combined probability mass of its component sets.
- No higher complexity than MAP.