Most frugal explanations in Bayesian Networks | Johan Kwisthout
Johan Kwisthout , Artificial Intelligence Volume 218, January 2015, Pages 56-73:
N.B. I read this paper for the first time in an academic skills lecture, and didn't understand much. Revisited in the TFCA course. However, I did not update the notes yet.
Some quick notes
- 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 approximation with expectation-approximation under certain parametrized situations. (65)
Introduction
Abduction: inference to the best explanation.
Abduction can be done with Bayesian statistics and has numerous applications.
In Bayesian terms, the "best" explanation is the one with the highest posterior probability, i.e. the highest probability given the observed evidence. In other words, this is the mode of the posterior distribution.
This "best" explanation is called the maximum a posteriori probability (MAP). The problem of inferring this explanation is called the MAP problem, which is NP-hard.
The MAP problem is especially hard when there are many intermediate variables, i.e. variables that are neither evidence, nor to be explained. These variables need to be marginalized over.
However, not all these intermediate variables are relevant for a particular query:
It is known that in general the posterior probability distribution of a (discrete) Bayesian network is skewed, i.e., fewjoint value assignments together cover most of the probability space [13], and that typically only a fewof the variables in a network are relevant for a particular inference query [14]. We propose to utilize this property of Bayesian networks in order to make tractable (approximate) inferences to the best ex-planation over large and unencapsulated knowledge structures. We introduce a heuristic formulation of MAP, denoted as Inference to the Most Frugal Explanation (MFE), that is explicitly designed to reflect that only a fewintermediate variables are typically relevant in real-world situations. In this formulation we partition the set of intermediate variables in the net-work into a set of ‘relevant’ intermediate variables that are marginalized over, and a set of ‘irrelevant’ intermediate variables that we sample from in order to estimate an explanation. (57)
The paper claims some desirable properties of the MFE approach:
- Knowledge structures are isotropic and Quinean.
- Isotropic: everything can be relevant to the outcome of an inference process
- "Quinean: candidate explanations are sensitive to the entire belief system"
- If we assume some situational constraints, the inferences can be proved to be tractable
- Resulting explanations have an optimal or close-to-optimal posterior probability.
- MFE "tracks truth" (see Glass 2012, Synthese 185)
Preliminaries
Various definitions and formalizations. Also of the MAP problem.
ALARM network is one of the most prominent benchmark networks for Bayesian networks.
Complexity theory
- Turing Machines
- P
- NP
- intractability proofs
Additional, specific to Bayesian:
- Probabilistic Turing Machines
- Oracle Turing Machines
- PP class
- Counting Hierarchy
- Parameterized complexity theory.
The class PP is defined as those languages accepted by some PTM in polynomial time, where the chance of ending up in an accepting state is strictly larger than 0.5 if the input is part of an accepted language (misschien net niet goed geformuleerd).
NP is a subset of PP.
PP contains complete problems.
Oracle Turing Machine (OTM) is a Turing Machine enhanced with a so-called oracle tape and an oracle O for deciding membership queries for a particular language LO. Apart from its usual operations, the OTM can write a string y on the oracle tape and ‘summon the oracle’. In the next state, the OTM will have either replaced the string with 1 if y is an element of LO, or 0 if y is not an element of LO. The oracle can thus be seen as a ‘black box’ that answers membership queries in constant time.
Counting Hierarchy: generalization of Polynomial Hierarchy, including NP^(PP), P^(NP)^(PP), NP^(PP)^(PP). I have no idea what this is about.
Fixed-parameter tractable: if fixing parameter k makes a problem tractable, then k is a source of complexity.
Most frugal explanations
Idea: get rid of all irrelevant intermediate variables.
One strategy is to remove everything that is conditionally independent on the evidence. However, this might still leave quite some conditionally dependent variables that do not really have influence on the best explanation. So they are still irrelevant and are ideally removed.
Another strategy is to find all variables whose value might change the most probably explanation.
Or even stricter: that it does change that explanation.
Finding these however can itself again be intractable.
Example 2 is Mr. Jones not showing up for work. Relevant could be 1) train delay, 2) that there was a robbery and a person got shot. The color of his jacket is not relevant for this specific query with the current evidence. It might become relevant if we learn new evidence:
The approach sketched above guarantees that, as in the MAP problem, the knowledge structures remain both isotropic and Quinean, i.e., everything still can be relevant to the outcome of the inference process and the candidate explanations remain sensitive to the entire belief system, as claimed in Section 1. For example, when new evidence arises (say, that we learn of a bank robbery where an innocent passerby was shot), the color of Mr. Jones’s coat suddenly may become relevant to explain his absence.
Note that MFE is not guaranteed to give the MAP explanation, unless we marginalize over all intermediate variables (i.e., consider all variables to be relevant). When the set of irrelevant variables is non-empty, the most frugal explanation may differ from the MAP explanation, even when using a voting strategy based on all joint value assignments to the irrelevant intermediate variables, since both explanations are computed differently.
Relevance
N.B. this paper only discusses the relevance of intermediate variables, not the separation between intermediate and explanatory variables itself (it assumes that distinction, actually).
According to Druzdzel and Suermondt a variable in a Bayesian model is relevant for a set Tof variables, given an observation E, if it is “needed to reason about the impact of observing Eon T” ([14], p.60). Our operationalization of “needed to reason” is inspired by Wilson and Sperber, who state that “an input is relevant to an individual when its processing in a context of available assumptions yields (...) a worthwhile difference to the individual’s representation of the world” ([65], p.608). The term ‘worthwhile difference’ in this quote refers to the balance between the actual effects of processing that particular input and the effort required to do so. We therefore define the relevance of an intermediate variable as a measure, indicating how sensitive explanations are to changes in its value assignment. Informally, an intermediate variable I has a low relevance when there are only a few possible worlds in which the most probable explanation changes when the value of I changes.
This strict measure is called "intrinsic relevance", but computing it is again intractable.
So the paper also proposes a "subjective relevance" or "estimated relevance".
In any case a set of candidate explanations and value assignments to evidence nodes are assumed.
"Thus, the distribution of MFE explanations is typically more ‘skewed’ towards one explanation when more variables are considered to be relevant." (62)