2.1 Philosophical foundations

In the social sciences, it is generally accepted that explanations are contrastive (Miller, Reference Miller2018). The questions that people ask have a contrast case, which is sometimes implicit, and the explanations that people give explain relative to this contrast case. Even when giving an explanation with no question, people explain relative to contrast cases.

Garfinkel (Reference Garfinkel1981) seems to be the first to make a case for contrastive explanationFootnote ¹ . He provides a story about a well-known bank robber Willie Sutton who purportedly replied to journalist who asked why he robbed banks, with: ‘That’s where the money is.’ Garfinkel argues that Sutton answered why he robs [banks vs. other things], rather than why he [robs vs. does not rob] banks because he answered to a different contrast case: that of banks vs. non-banks, rather than robbing vs. not robbing. Garfinkel notes that these two different contrasts create two different contexts, and that explanations are relative to these contrastive contexts. An object of explanation is not just a state of affairs, but a ‘state of affairs together with a definite space of alternatives to it’ (Garfinkel, Reference Garfinkel1981, p. 21).

At the same time, Van Fraassen (Reference Van Fraassen1980) was also arguing the case of contrastive explanations. He states that the underlying structure of a why-question is: ‘Why (is it the case that) P in contrast to (other members of) X?’, in which P is the topic and X is the contrast class to P (Van Fraassen, Reference Van Fraassen1980, p. 127). An answer to such a question has the structure ‘P in contrast to (the rest of) X because A’ (Van Fraassen, Reference Van Fraassen1980, p. 143). Van Fraassen argues that when a questioner asks such a question, they presuppose that: (1) the topic P is true; (2) all other elements of the contrast class X are false; and (3) A is both true and explanatorily relevant to the topic. He proposes an explicit relation R that determines explanatory relevance.

Hesslow (Reference Hesslow1983); Hesslow (Reference Hesslow1988) extends this idea of explanatory relevance and seems to be the first to make a case for the idea of contrast cases themselves defining explanatory relevance. He argues that there is a distinction between determining causes and explanatory causes, with the former being the (often large) set of conditions that contribute to causing an event, and the latter being a subset of the determining causes that are selected due to their explanatory power. Hesslow’s theory of explanation is based on two complementary ideas. The first is that of contrastive explanation. He states that:

The second is of explanatory relevance. Hesslow argues that by explaining only those causes that are different between the two or more objects, the explanation is more relevant to the questioner as it provides those causes that the questioner does not know. In essence, the contrast case provides a window into the particular causes that the questioner does not understand.

Hesslow presents an example: ‘Why did the barn catch on fire?’. The explanation that someone dropped a lit cigarette in the hay has strong explanatory power and would satisfy most people. But what about other causes? The presence of oxygen, the hay being dry, and absence of fire sprinklers are all causes, but the cigarette has particular explanatory power because oxygen is always present in barns, and most barns are dry and have no fire sprinklers. The explanation is contrasting to these normal cases.

He formalizes this notion as follows. Given an object a, a property E, and a reference class R (the contrast cases), the cause Ca is an adequate explanation of $\langle a, E, R\rangle$ iff:

1. 1. for all x in R, if Cx had been true then Ex would have been true; and

2. 2. if $\neg Ca$ had been true, then $\neg Ea$ would have been true,

in which Cx and Ex refer to the cause C and property E respectively applying to x. This states that Ca is an adequate explanation if and only if (1) the cause C held on all the other objects x in R (e.g. other barns), then the property E would also hold (the other barns would have also caught fire); and (2) the cause C did not apply to a, then the property E would not hold. We can see that (1) does not apply to oxygen, because oxygen is present in other barns that do not catch fire, while for the cigarette this is the case; and that (2) applies to the cigarette—if the cigarette had not been dropped, the fire would not have occurred.

At a similar time, Lewis (Reference Lewis1986) proposed a short account of contrastive explanation. According to Lewis, to explain why P occurred rather than Q, one should offer an event in the history of P that would not have applied to the history of Q, if Q had occurred. For example, he states: ‘Why did I visit Melbourne in 1979, rather than Oxford or Uppsala or Wellington? Because Monash University invited me. That is part of the causal history of my visiting Melbourne; and if I had gone to one of the other places instead, presumably that would not have been part of the causal history of my going there’ (Lewis, Reference Lewis1986, p. 229–230). This has parallels with Hesslow’s account (Hesslow, Reference Hesslow1983; Reference Hesslow1988).

Temple (Reference Temple1988) subsequently argued against the case of contrastive explanation. Temple argued that the question ‘Why P rather than Q?’ presupposes that P is true and Q is not, and that the object of explanation is not to explain why P and Q are mutually exclusive, but instead to ask ‘Why [P and not Q]?’. Therefore, contrastive why-questions are just standard propositional why-questions of the form ‘Why X?’, but with X being [P and not-Q].

However, Lipton (Reference Lipton1990) argues that this is a language phenomenon, and semantically, explaining ‘Why P rather than Q?’ is not the same as explaining ‘Why [P and not Q]?’. Building on Lewis’s interpretation based on the history of events (Lewis, Reference Lewis1986), Lipton argues that answering ‘Why [P and not Q]?’ requires an explanation of P and of not-Q. For example, to answer why the barn burned down rather than not burning down would require a complete attribution of why the barn burned down, including the presence of oxygen, as well as why other barns do not typically burn down. Lipton argues that this is not what the explainee wants.

Lipton (Reference Lipton1990) proposes that explanation selection is best described using the difference condition:

This differs from the definition of contrastive explanation from Lewis (Reference Lewis1986) in that instead of selecting a cause of P that is not a cause of Q if Q had occurred, we should explain the actual difference between P and not-Q; that is, we should cite a cause that is in the actual history of P, and an event that did not occur in the actual history of not-Q.

We can formalize this as the following, in which $\leadsto$ is the causal relation, and $H_{P}$ and $H_{not{Q}}$ are the history of P and not-Q respectively, and $H_{Q}$ is the hypothetical history of Q had it occurred:

Thus, Lewis’s definition (Lewis, Reference Lewis1986) cites some alternative history of facts in which Q occurred, whereas Lipton’s definition (Lipton, Reference Lipton1990) refers to the actual history of not-Q. Further, Lewis’s definition states that the explanation should be an event c (or perhaps set of events), whereas Lipton’s states that the explanation is the difference between c and c ^′.

It was generally accepted at the time that Lipton (Reference Lipton1990) proposed his ideas, that facts and contrast cases are incompatible events (Temple, Reference Temple1988; Garfinkel, Reference Garfinkel1981; Van Fraassen, Reference Van Fraassen1980; Ruben, Reference Ruben1987); for example, a barn cannot both burn down and not burn down, or leaves cannot be blue and yellow at the same time. However, Lipton notes that compatible contrastive cases are also valid. For example, we can ask why one leaf is blue while another leaf is yellow. It is perfectly possible that both leaves could be blue, but we are looking for explanations as to why only one of them is.

Ylikoski (Reference Ylikoski2007) provides a more refined model to explain this, noting that incompatible vs. compatible contrast cases are two different types of question. The first is when we contrast two incompatible contrasts of the same process: one the fact and one the ‘imagined’ foil, such as a leaf being yellow rather than that leaf being blue. The fact and the foil must be inconsistent. The second is when we contrast two facts from two actual and different processes. That is, both facts actually occurred, such as one yellow leaf and one blue leaf. Ylikoski calls the second fact a surrogate for a counterfactual claim about the first process. He claims that the surrogate is used to simplify the explanation—as one simply needs to find the difference between the fact and surrogate, which is consistent with the idea from Lipton (Reference Lipton1990) that this is cognitively a simpler problem.

Van Bouwel and Weber (Reference Van Bouwel and Weber2002) divide explanatory questions into four types:

• Plain fact: Why does object a have property P?

• P-contrast: Why does object a have property P, rather than property Q?

• O-contrast: Why does object a have property P, while object b has property Q?

• T-contrast: Why does object a have property P at time t, but property Q at time t ^′?

This defines three types of contrast: within an object (P-contrast), between objects themselves (O-contrast), and within an object over time (T-contrast). P-contrast is the standard ‘rather than’ interpretation, while O-contrast and T-contrast correspond to Ylikoski’s notion of different processes (Ylikoski, Reference Ylikoski2007).

In Section 4, we will formalize the notion of contrastive questions using the framework of Halpern and Pearl (Reference Halpern and Pearl2005a), and will show that the reasoning of Ylikoski (Reference Ylikoski2007) is natural with respective to structural equations and fits the types of questions we would expect in XAI. The concept of P-contrast is captured as counterfactual explanations, while O-contrast and T-contrast are captured as bi-factual explanations.

2.2 Computational approaches

In artificial intelligence, contrastive questions are not just a matter of academic interest. User studies investigating the types of questions that people have for particular systems identify ‘Why not?’ questions and contrast classes as important. Lim and Dey (Reference Lim and Dey2009) showed that ‘Why not?’ questions are important in context-aware applications, while Haynes et al. (Reference Haynes, Cohen and Ritter2009) found that users of their virtual aviation pilot system particularly sought information about contrast cases. Given that this is consistent with views from philosophy and psychology, it makes sense to consider the difference condition as key to answering these questions.

The idea of why-not questions in artificial intelligence was around prior to these studies. The explanation module of the MYCIN expert system explicitly allowed users to pose questions such as ‘Why didn’t you do X?’ (Buchanan & Shortliffe, Reference Buchanan and Shortliffe1984), which is providing a foil for the fact. More recently, there has been a keen interest in answering why-not questions for many different sub-fields of artificial intelligence, including machine learning classification (Dhurandhar et al.,, Reference Dhurandhar, Chen, Luss, Tu, Ting, Shanmugam and Das2018; Mothilal et al.,, Reference Mothilal, Sharma and Tan2020), belief-desire-intention agents (Winikoff, Reference Winikoff2017), reinforcement learning (Madumal et al.,, Reference Madumal, Miller, Sonenberg and Vetere2020; Waa et al.,, Reference Waa, van Diggelen, Bosch and Neerincx2018), classical planning (Krarup et al.,, Reference Krarup, Cashmore, Magazzeni and Miller2019; Sreedharan et al.,, Reference Sreedharan, Srivastava and Kambhampati2018), and image classification (Akula et al.,, Reference Akula, Wang and Zhu2020), to cite just a few papers.

However, while the idea of why-not questions is being addressed, there is not a clear and consistent understanding of contrastive explanation in the explainable AI community. First, while there many of papers what answer why-not questions, most of these are counterfactual solutions, not contrastive, meaning that they do not make explicit use of the difference between the fact and the foil, with some exceptions; for example, Madumal et al. (Reference Madumal, Miller, Sonenberg and Vetere2020). This may seem trivial, and from an algorithmic perspective perhaps it is. But from the perspective of helping people to understand models and decisions, this is a crucial step that requires further research in human factors and human–computer interaction.

Second, there is no general understanding in the community about contrastive and counterfactual explanation, with much of it built on the intuitions of authors. This leads to algorithms that can be useful, but terminology and solutions that are not aligned. For example, Dhurandhar et al. (Reference Dhurandhar, Chen, Luss, Tu, Ting, Shanmugam and Das2018) use the term pertinent negatives/positives to refer to foils, while Akula et al. (Reference Akula, Wang and Zhu2020) use the term fault lines, and Krarup et al. (Reference Krarup, Cashmore, Magazzeni and Miller2019) use foil.

Third, while there is work on counterfactual explanation that contributes to contrastive explanation, there is no work that the author is aware of that addresses why we call bi-factual questions: why P this time but Q last time? As noted by Wang et al. (Reference Wang, Yang, Abdul and Lim2019) in their study of clinicians using AI-driven diagnosis in intensive care units, some clinicians ‘wanted to see past patients which had similar presentations (e.g., complaints, vital signs), but not necessarily similar diagnoses (decision outcomes)’. This is a request for a bi-factual contrastive explanation. Showing similar cases with different outcomes, and importantly, showing the difference between the two helps people to understand why the outcomes differ. Currently, this form of why-not question is lacking in explainable AI literature.

The aim of this paper is to mitigate some of the issues above by providing a general model of contrastive explanation that can be mapped to other models in artificial intelligence, such as machine learning, planning, reinforcement learning, case-based reasoning, and BDI agents. By presenting a single, coherent general model, we can begin to understand the similarities and differences between proposed solutions and can start to plug holes, such as lack of bi-factual explanation, in explainable AI.

As far as the author is aware, Kean (Reference Kean1998) is the only other author to consider a general computational model of contrastive explanation. Kean’s model of contrastive explanation is also built on Lipton’s difference condition (Lipton, Reference Lipton1990). Given a knowledge base $\mathcal{K}$ and an observation P, Kean proposes a simple model to calculate why P occurred instead of Q. Kean provides a definition of a non-preclusive contrastive explanation for ‘Why P rather than Q?’, which refers to the propositions that are required for P to hold but not Q. The definition of a preclusive contrastive explanation uses the difference condition, and, as in this paper, identifies that the contrastive explanation must reference both the causes of ${P}$ and causes of Q that were not true. There are three key differences between Kean’s model and the structural approach model approach in this paper. First, Kean’s model was published when the understanding of causality in artificial intelligence was in its infancy, and is therefore built on propositional logic, rather than on a logic of causality and counterfactuals, which is more suitable. Second, Kean’s model considers only ‘rather than’ questions, and not contrastive explanations with surrogates rather than foils. Third, and most importantly Kean’s model is in fact a model of abductive reasoning, in which assumptions are made about the truth of certain propositions to find the ‘best’ explanation. As such, this is a model of the cognitive process of contrastive explanation from the perspective of an explainer, and the task is to derive an explanation for an observation. There is no explainee in Kean’s model. In contrast, our model is not concerned with abductive reasoning, but instead models an explainer with complete knowledge of the explanation using the difference condition to communicate to an unaware explainee.

3.1 Models

Formally, a signature $\mathcal{S}$ is a structure $(\mathcal{U}, \mathcal{V}, \mathcal{R})$ , in which $\mathcal{U}$ is a set of exogenous variables, $\mathcal{V}$ a set of endogenous variables, and $\mathcal{R}$ is a function that defines the range of values for every variable $Y \in \mathcal{U} \cup \mathcal{V}$ ; that is, the range of a variable Y is $\mathcal{R}(Y)$ .

A causal model is a pair, $M = (\mathcal{S}, \mathcal{F})$ , in which $\mathcal{F}$ defines a set of functions, one for each endogenous variable $X \in \mathcal{V}$ , such that $F_X : (\times_{U\in\mathcal{U}}\mathcal{R}(U)) \times (\times_{Y\in \mathcal{V}-\{X\}}\mathcal{R}(Y)) \rightarrow \mathcal{R}(X)$ determines the value of X based on other variables in the model. A causal model is said to be recursive if it is acyclic.

A context, $\vec{u}$ , is a vector that gives a unique value to each exogenous variable $u \in \mathcal{U}$ . A model/context pair $(M, \vec{u})$ is called a situation.

Halpern & Pearl (Reference Halpern and Pearl2005a) extend this basic structural equation model to support modeling of counterfactuals. To represent counterfactual models, the model $M_{\vec{X} \leftarrow \vec{x}}$ defines the new causal model given a vector $\vec{X}$ of endogenous variables in $\mathcal{V}$ and their values $\vec{x}$ over the new signature $\mathcal{S}_{\vec{X}} = (\mathcal{U}, \mathcal{V} - \vec{X}, R|_{\mathcal{V} - \vec{X}})$ . This represents the model M with the values of $\vec{X}$ overridden by $\vec{x}$ . Formally, this model is defined as $M_{\vec{X} \leftarrow \vec{x}} = (\mathcal{S}_{\vec{X}}, \mathcal{F}^{\vec{X} \leftarrow \vec{x}})$ , in which each $F_Y^{\vec{X} \leftarrow \vec{x}}$ in $\mathcal{F}$ is defined by setting the values of $\vec{X}$ to $\vec{x}$ in function $F_Y$ .

3.2 Language

To reason about these structures, in particular, counterfactuals, Halpern and Pearl (Reference Halpern and Pearl2005a) present a simple but powerful language. Given a signature $\mathcal{S} = (\mathcal{U}, \mathcal{V}, \mathcal{R})$ , variables $X \in \mathcal{V}$ and values $x \in \mathcal{R}(X)$ , a formula of the form $X=x$ is called a primitive event, and describes the event in which variable X is given the value x. A basic causal formula is of the form $[Y_1 \leftarrow y_1, \ldots, Y_n \leftarrow y_n]\phi$ , in which $\phi$ is any Boolean combination of primitive events, each $Y_i$ is a variable in $\mathcal{V}$ (endogenous variable), and $y_i \in \mathcal{R}(Y_i)$ . We will follow Halpern & Pearl in abbreviating this formula using $[\vec{Y} \leftarrow \vec{y}]\phi$ , in which $\vec{Y}$ and $\vec{y}$ are vectors of variables and values respectively. A causal formula is a Boolean combination of basic causal formulas. If $\vec{Y}$ is empty, this is abbreviated as just $\phi$ .

3.3 Semantics

Intuitively, a formula $[\vec{Y} \leftarrow \vec{y}]\phi$ for a situation $(M, \vec{u})$ states that $\phi$ would hold in the model if the counterfactual case of $Y_i = y_i$ for each $Y_i \in \vec{Y}$ and $y_i \in \vec{y}$ were to occur. More formally, Halpern and Pearl define $(M, \vec{u}) \models \phi$ to mean that $\phi$ holds in the model and context $(M, \vec{u})$ . The $\models$ relation is defined inductively by defining $(M, \vec{u}) \models [\vec{Y} \leftarrow \vec{y}](X = x)$ as holding if and only if the unique value of X determined from the model $M_{\vec{Y} \leftarrow \vec{y}}$ is x, and defining Boolean combinations in the standard way.

Table 1.

A simple lay model for distinguishing common arthropods

Figure 1

(a) Causal graph for arthropod algorithm defined in Example 3.1 (b) (b) Causal graph for extended arthropod algorithm defined in Example 3.2.

It is important to note that SCMs like this can be used to model correlative machine learning algorithms. It is not the physical features of number of legs, eyes, etc., that cause a real spider to be a spider—it is its genetic makeup that causes this. This genetic makeup causes both the spider’s physical features and it to be a spider. However, here we model that a correlation is found between the variables represent physical features and the type, and the algorithm uses this to predict the arthropod type. However, the causal direction of the prediction model is from physical features to arthropod type because this is the way the prediction is made. The variables representing the physical features cause the decision, even though this does not model the causes in the real world. Of course, a model that represents causes in the real world may offer a better explanatory model, but even in cases where we do not have one, a straightforward mapping from features to outputs fits into our model of contrastive explanation.

4.1 Counterfactual questions

Given two events P and Q, Lipton (Reference Lipton1990) defines a contrastive why-question as:

(1) \begin{equation}\textrm{Why P rather than Q?}\end{equation}

For a counterfactual question, this means that, in some situation, the fact ${P}$ occurred and the explainee is asking why foil ${Q}$ did not occur in that situation instead. To semi-formalize this in structural models, a counterfactual why-question, given a situation $(M, \vec{u})$ , is:

(2) \begin{equation}\textrm{Why $(M, \vec{u}) \models \phi$ rather than $\psi$ ?}\end{equation}

in which $\phi$ is the fact and $\psi$ is the foil. This assumes that $\phi$ is actually true in the situation $(M,\vec{u})$ , and that $\psi$ is not. The linguistic reduction to ‘Why P and not-Q?’ is:

(3) \begin{equation}\textrm{Why $(M, \vec{u}) \models \phi \land \neg\psi$?}\end{equation}

To answer the question in Equation (3), one could argue that an explanation of such a case is a proof of $\phi$ and a counterexample for $\psi$ . However, as argued by Lipton (Reference Lipton1990), this is not really what is asked by ‘Why $\phi$ rather than $\psi$ ?’. The ‘rather than’ is asking for a relationship between the causes of $\phi$ and the causes (or non-causes) of $\psi$ . As a counterexample to the reductionist argument, Lipton notes that we can answer a ‘rather than’ question without knowing all causes of the events. For instance, take the arthropod description from Example 3.1, and a question as to why the algorithm classified a particular image as a Bee rather than a Fly. Assume that we only know the value of one variable in the model: W—the number of wings. We cannot give the cause of $O=Bee$ if we do not know the values of the other variablesFootnote ² . However, we can still give a perfectively satisfactory answer to the question: it is a Bee rather than a Fly because it has four wings instead of two. As such, ‘rather than’ questions must be asking something different to just ‘Why $\phi$ and why $\neg\psi$ ?’, for which we need to know all causes for both $\phi$ and $\psi$ .

These counterfactual questions make sense as why-questions in artificial intelligence. Given the arthropod classification example, a ‘rather than’ question represents an observer asking why the output was a particular arthropod rather some other incompatible foil case; which would presumably often be the answer they were expecting.

In this paper, we assume that in counterfactual questions, $\phi$ and $\psi$ are incompatible. It is clear that questions such as ‘Why $x \leq 5$ rather than $x \geq 0$ , where $x=4$ and therefore both fact and foil are true, do not make sense. However, one could argue that it is possible to ask ‘rather than’ questions with compatible fact and foils over different variables; for example “Why $x=4$ rather than $y=5$ ?’. It is not difficult to find a structural model such that $x=4$ and $y=5$ . However, the value of y in the actual situation must be something other than 5, otherwise the question does not make sense. So, the question is really ‘Why $x=4 \land y=4$ rather than $x=4 \land y=5$ ?’, which is incompatible. For this reason, we make the reasonable assumption that $\phi$ and $\psi$ always refer to the same variables and they are incompatible in the given situation.

4.2 Bi-factual questions

As outlined in Section 2, Ylikoski (Reference Ylikoski2007) argues that some contrastive why-questions can have compatible facts and foils; although he terms a compatible foil as a surrogate. To be compatible, he argues that they must occur as part of two different ‘processes’.

We model this second type of contrastive question, called a bi-factual questions, by modeling the two different processes as two different situations:

(4) \begin{equation}\textrm{Why $(M, \vec{u}) \models \phi$ but $(M', \vec{u}') \models \psi$?}\end{equation}

in which the $(M, \vec{u})$ and $(M', \vec{u}')$ are two different situations, including two different models M and M ^′, $\phi$ is the fact, and $\psi$ is the surrogate. Note the absence of ‘rather than’ in the question. Linguistically, this makes sense because both the fact and the surrogate are actual—there is no hypothetical case.

As a question in explainable AI, this question has a clear interpretation that M and M ^′ refer to two different algorithms and $\vec{u}$ and $\vec{u}'$ define different ‘inputs’ to the algorithms. For the arthropod example, a valid question is why the algorithm produced the output $\phi$ for input image J, while some previous execution of the algorithm produced the different output $\psi$ for different image K (note that $M=M'$ in this example). The observer is trying to understand why the outputs were different, when she expected $\phi$ to be $\psi$ like it was in a previous instance. Another example is the case noted by Wang et al. (Reference Wang, Yang, Abdul and Lim2019), discussed in Section 2.2, of clinicians wanting to compare similar cases with different outcomes.

In the case where $M \neq M'$ , an example is in which model M ^′ is an updated version of M—for example, new data has been feed into a learning approach to produce a more refined model —, and the explainee is asking for why the result has changed between the two models, potentially with $\vec{u} = \vec{u}'$ .

Although not naturally worded as a ‘rather than’ question, it could be argued that the question is actually a ‘rather than’ question in which the person is asking ‘Why $\phi$ this time and $\psi$ last time rather than $\phi$ (or $\psi$ ) both times?’:

\begin{equation*}\begin{gathered}\textrm{Why $(M, \vec{u}) \models \phi$ and $(M', \vec{u}') \models \psi$}\nonumber\\\textrm{ rather than }\\\textrm{$(M, \vec{u}) \models \phi$ and $(M', \vec{u}') \models \phi$ or $(M, \vec{u}) \models \psi$ and $(M', \vec{u}') \models \psi$ ?}\nonumber\end{gathered}\end{equation*}

If we reduce this using the template of ‘P and not-Q’, and simplify, the result is:

(5) \begin{equation}\begin{gathered}\textrm{Why $(M, \vec{u}) \models \phi \land \neg\psi$ but $(M', \vec{u}') \models \psi \land \neg\phi$ ?}\end{gathered}\end{equation}

This is just the same as the question in Equation (4), however, it assumes that the fact and surrogate are incompatible. This assumption is too strong, because a perfectly valid question is why two different situations are producing the same outcome, despite the differences in the situation: the explainee expects the two outcomes to be different and wants an explanation as to why they are the same.

In this section, we have demonstrated a case for two types of contrastive why-question: counterfactual and bi-factual questions. In the remainder of the paper, we use structural causal models to define what answers to these questions look like, starting with how to define contrastive cause (Section 5) and then contrastive explanation (Section 6).

5.1 Non-contrastive cause

Our definition of contrastive cause extends Halpern & Pearl’s definition of actual cause (Halpern & Pearl, Reference Halpern and Pearl2005a). In their definition, causes are conjunctions of primitive events, represented as $\vec{X} = \vec{x}$ , while the events to be described are Boolean combinations of primitive events.

Halpern and Pearl (Reference Halpern and Pearl2005a) define two types of cause: sufficient cause and actual cause. Intuitively, a sufficient cause of an event in a situation is a conjunction of primitive events such that changing the values of some variables in that conjunct would cause the event not to occur. An actual cause is simply a minimal sufficient cause; that is, it contains no unnecessary conjuncts.

More formally, the conjunction of primitive events $\vec{X} = \vec{x}$ is an actual cause of event $\phi$ in a situation $(M, \vec{u})$ if the following three properties hold:

• AC1 $(M, \vec{u}) \models \vec{X} = \vec{x} \land \phi$ —that is, both the event and the cause are true in the actual situation.

• AC2 There is a set $\vec{W} \subseteq \mathcal{V}$ and a setting $\vec{x}'$ of variables $\vec{X}$ such that if $(M, \vec{u}) \models \vec{W} = \vec{w}$ then $(M, \vec{u}) \models [\vec{X} \leftarrow \vec{x}', \vec{W} \leftarrow \vec{w}]\neg \phi$ —that is, if $\vec{X}$ did not have the values $\vec{x}$ and all variables in W remain the same, then event $\phi$ would not have occurredFootnote ³ .

• AC3 $\vec{X}$ is minimal; no subset of $\vec{X}$ satisfies AC1 and AC2—that is, there are no unnecessary primitive events in the conjunction $\vec{X} = \vec{x}$ .

A sufficient cause is simply the first two items above—that is, a non-minimal actual cause.

Throughout the rest of this paper, we use the term partial cause to refer to a subset of conjunctions of an actual cause.

5.2 Contrastive causes for counterfactuals

To define contrastive cause, we adopt and formalize Lipton’s difference condition (Lipton, Reference Lipton1990), which states that we should find causes that are different in the ‘history’ of the two events. We define the ‘history’ as the situation $(M,\vec{u})$ under which the events are evaluated; that is, (M, u) for counterfactual why-questions, and both (M, u) and $(M',\vec{u}')$ for bi-factual why-questions.

The particular explanandum for which we want to define cause is no longer a single event $\phi$ , but a pair of events $\langle \phi, \psi \rangle$ , in which $\phi$ is the fact and $\psi$ is the foil. Similarly, causes will consist of two events instead of one, consistent with the difference condition.

Informally, a contrastive counterfactual cause of a pair of events $\langle \phi, \psi\rangle$ is a pair of partial causes, such that the difference between the two causes is the minimum number of changes required to make $\psi$ become true.

Similar to the HP definition, we can define sufficient contrastive cause by modifying CC1 and CC3 to refer to partial sufficient causes.

This definition is based on the Halpern (Reference Halpern2015) definition of actual cause, as conditions CC1-3 directly access partial causes, which are subsets of actual causes. However, the definition is modular with respect to the underlying definition of actual cause, such that a different definition of actual cause (using structural models), such as the original definition from Halpern and Pearl Halpern & Pearl (Reference Halpern and Pearl2005a), could be substituted, and this would change the semantic interpretation of the above.

The reader may expect to see that CC2 had an additional statement that no part of the hypothetical cause of $\psi$ is true, such as $\bigwedge_{X_i=y_i \in \vec{X} = \vec{y}}X_i\neq y_i$ . However, this is implied by CC4, because all elements of $\vec{X} = \vec{x}$ are true, and each element of $\vec{X} = \vec{y}$ is different from its corresponding value in $\vec{X} = \vec{x}$ . Also note that condition CC3 implies that the foil $\psi$ is feasible in M. That is, it implies that $M \not\models \neg\psi$ . For an infeasible event, there cannot be another situation such $\vec{X} = \vec{y}$ is a cause of $\psi$ , therefore there can be no difference condition. This seems reasonable though: asking why an infeasible foil did not occur should not invoke a difference between the fact and foil, but a description that the foil is infeasible.

Example 5.3. Consider the arthropod example from Example 3.1, asking why an image was categorized as a Bee instead of a Fly. To answer the counterfactual why-question, we take the maximal intersection of two actual causes of $Output = Bee$ and the hypothetical cause of $Output = Fly$ . In this case, the following pairs correspond to the possible contrastive causes:

\begin{align*} &\langle S = \boldsymbol\checkmark , S = \boldsymbol\times\rangle \\& \langle W=4, W=2\rangle. \end{align*}

The image was classified as a Bee instead of a Fly because the image contains a stinger (S) and four wings (W), while for a Fly, it would have required no stinger and two wings. The other actual causes of $\phi$ and $\psi$ , such as $L=6$ , are not contrastive causes because they do not satisfy the difference condition in CC4.

It is difficult to argue that a particular definition of contrastive cause is correct. However, we can at least argue that they abide by some commonly accepted properties; specifically, the properties of an adequate explanation defined by Hesslow (Reference Hesslow1983) (see Section 2.1). This states that, if the counterfactual causes hold in a different situation, so to would the counterfactual events. The following theorem captures this.

Proof. Consider part (a) first. We prove via contradiction. Assume that $(M, \vec{u}) \not\models [\vec{X} \leftarrow \vec{y}]\psi$ . From CC3, $\vec{X} = \vec{y}$ contains partial causes of $\psi$ , so there must be a set of additional causes $\vec{Z} = \vec{z}$ such that $(M, \vec{u}) \models [\vec{X} \leftarrow \vec{y},\vec{Z} \leftarrow \vec{z}]\psi$ . This implies that there is some (maximal) subset $\vec{Z} = \vec{z}' \subseteq \vec{Z} = \vec{z}$ such that $(M,\vec{u}) \not\models \vec{Z} = \vec{z}'$ , and is therefore not in $\vec{X} = \vec{x}$ . However, these two implications mean that CC3 and CC4 hold for $\vec{Z} = \vec{z}'$ . CC5 also holds because $\vec{Z} = \vec{z}'$ is maximal. Therefore, $\vec{Z} = \vec{z}'$ is (one half of) a contrastive cause for $\langle \phi, \psi\rangle$ , and as such, must be part of $\mathcal{C}$ . Because $\vec{X} = \vec{y}$ is maximal, $\vec{Z} = \vec{z}'$ must be in $\vec{X} = \vec{y}$ , so it is not possible that both $(M,\vec{u}) \not\models [\vec{X} \leftarrow \vec{y}]\psi$ and $(M, \vec{u}) \models [\vec{X} \leftarrow \vec{y},\vec{Z} \leftarrow \vec{z}]\psi$ are true. This contradiction shows that part (a) holds. Part (b) holds directly because $\phi$ and $\psi$ are incompatible.

5.3 Contrastive causes in bi-factuals

For bi-factual questions, the definition of ‘history’ is different to that of counterfactual questions, citing two different situations. We define the ‘history’ as the situations $(M,\vec{u})$ of $\phi$ and $(M', \vec{u}')$ of $\psi$ . For the moment, we simplify this by assuming that the two causal models M and M ^′ are the same; e.g. the same algorithm is executed with different inputs from the environment. We drop this assumption later.

Note that BC1 implies $(M, \vec{u}) \models \vec{X} = \vec{x} \land \phi$ (AC1) and similarly for BC2.

A sufficient contrastive cause can be obtained by modifying BC1 and BC2 to refer to partial sufficient causes.

This definition is simpler than that of counterfactual explanation (compare CC3 with BC2), because both the fact and surrogate are actual events, whereas in counterfactual questions, the foil is hypothetical.

Example 5.4. Consider again the arthropod example from Example 3.1, and the contrastive why-question for two images B and F, in which B was categorized as a Bee and F a fly. The situations for these two cases are straightforward to extract from Table 1, as are the causes. To answer the contrastive why-question, we take the maximal intersection actual causes of $Output = Bee$ and $Output = Fly$ under models $(M, \vec{u}_{B})$ and $(M, \vec{u}_{F})$ respectively, which is simply the same as in Example 5.3:

\begin{align*} & \langle S = \boldsymbol\checkmark, S = \boldsymbol\times \rangle \\ & \langle W=4, W=2\rangle.\end{align*}

Note that the difference condition is the same as is in the counterfactual case, however, in this case, there was no need to find a hypothetical situation for the foil.

Proof. The proofs for both parts are similar to the proof for counterfactual causes in Theorem 1, except that we refer to BC2-4 instead of CC3-5.

Now we return to the case in which the two models may be different. For this, we define a restricted cause of $\phi$ under situation $(M, \vec{u})$ , where $M = (\mathcal{S},\mathcal{F})$ , as a pair $(\mathcal{F}', \vec{X} = \vec{x}')$ , in which $\vec{X} = \vec{x}'$ is a sufficient cause of $\phi$ , and $\mathcal{F}' \subseteq \mathcal{F}$ is the smallest subset of $\mathcal{F}$ required to derive $\phi$ . That is, for all $\vec{u}'$ , $(M,\vec{u}') \models \phi$ iff $(M^{\mathcal{F}'},\vec{u}') \models \phi$ , where $M^{\mathcal{F}'}=(S,\mathcal{F}')$ , and therefore all functions $F \setminus F'$ do not influence $\phi$ in any situation. A partial restricted cause is simply $(F^{\phi}, \vec{X} = \vec{x})$ such that $F^{\phi} \subseteq \mathcal{F}'$ and $\vec{X} = \vec{x} \subseteq \vec{X} = \vec{x}'$ .

Note two differences between this and the less general version. First, the definition refers to differences in the functions of the two models. Second, the sets of variables that are referred to are no longer shared between the two models. That is, in the less general definition, the contrastive cause $\langle \vec{X} = \vec{x}, \vec{X} = \vec{y} \rangle$ both pointed to $\vec{X}$ . However, the sets of variables can be different between the two models M and M ^′, so it is possible that some variable in $\vec{Y}$ does not exist in model M, but is a cause of $\psi$ in $(M',\vec{u}')$ . Note that $\textrm{BC4}_\textrm{G}$ also states that $\vec{X} \cap \vec{Y}$ is maximal, meaning that the two parts of a contrastive cause can only cite different variables if at least one of the models does not contain that variable.

In the case where $M=M'$ , this definition is the same as Definition 2 because $F^{\phi}=F^{\psi}=\emptyset$ and $\vec{X}=\vec{Y}$ .

Example 5.5. Consider now the combination of Examples 3.1 (the simple arthropod classification example) and 3.2 (the extended example in which images may come annotated). Let M be the model without the extension and M^′ be the extended model. Asking why $(M,\vec{u}) \models O=Unknown$ and $(M',\vec{u}') \models O=Bee$ , in which $\vec{u}$ and $\vec{u}'$ both correspond to features of a Bee but $L=5$ (five legs) and $A=Bee$ in $\vec{u}'$ , a contrastive cause would be:

\[\begin{array}{ll} \langle (F_O = f, \emptyset), (F_O = f', A=Bee)\rangle,\end{array}\]

in which f and f ^′ refer to the before and after functions for $F_O$ in M and M ^′ respectively, and are hopefully clear from the description. Here, the contrast cites the change in functions and the additional cause $A=Bee$ as the difference condition.

Example 5.6. The more general definition is also useful for reasoning about situations in which the fact and surrogate are the same event. That is, ‘Why $(M,\vec{u}) \models \phi$ but $(M', \vec{u}') \models \phi^{\prime}$ ? This is useful for situations in which an observer wants to understand why the event $\phi$ still occurs despite the model changing. As an example, consider the two simple structural models in Figure 2, with exogenous variables $U_1$ and $U_2$ , and endogenous variables P, Q, R, and S. S depends on all four variables in M, but there is no variable Q in model M^′.

Figure 2

Structural Models for Example 5.6.

For the contrast between $(M, \vec{u}) \models S=0$ and $(M',\vec{u}') \models S=0$ , in which $\vec{u}$ leads to $P=1$ , $Q=0$ , $R=1$ , and $S=0$ and $\vec{u}'$ leads to $P=1$ , $R=1$ , $S=0$ , the contrastive cause would be cited as:

\[\begin{array}{ll} & \langle (F_R = \max(P, Q), \emptyset), (F_R = P, \emptyset)\rangle.\end{array}\]

That is, the difference is in the function $F_R$ , not in any of the variables nor the output.

To explore some properties of this, we introduce notation that allows us to reason about changes in models at a meta level. Recall that a structural model $M = (\mathcal{S}, \mathcal{F})$ consists of a set of signatures $\mathcal{S}$ and a set of functions $\mathcal{F}$ . We define the override of a set of functions $\mathcal{F}$ by another set $\mathcal{F}'$ , denoted $\mathcal{F} \Leftarrow \mathcal{F}'$ being the same as $\mathcal{F}$ , except replacing $F_X$ with $F'_X$ for all variables X such that $F'_X \in \mathcal{F}$ . The notation $M \Leftarrow \mathcal{F}'$ represents the overriding of the functions in M with $\mathcal{F}'$ .

Proof. The proof for this is an extension of the proof for Theorem 2. The only case that requires attention is when variables are added/removed to/from the model. In this case, the model $M \Leftarrow F^{\psi}$ may contain the function $F_X$ , which is in M but not M ^′. However, if the variable X is not in M ^′, then $\psi$ cannot refer to it, so it is effectively redundant in $M \Leftarrow F^{\psi}$ .

5.4 Presuppositions

As noted previously, it is difficult to argue that a particular definition of contrastive cause is correct, but we can show our definition behaves according to some commonly accepted properties. In this section, we show that our definition is consistent with the idea of contrastive explanation as presupposed explanation (Lipton, Reference Lipton1990).

Lipton (Reference Lipton1990) notes that to give an explanation for ‘Why P rather than Q?^′ is to give a to ‘give a certain type of explanation of P, given P or Q, and an explanation that succeeds with the presupposition will not generally succeed without it.’ (Lipton, Reference Lipton1990, p. 251) (emphasis original). Thus, this states that if we assume that P and Q are the only two possible outcomes, and are mutually exclusive, then the actual cause of P under this assumption will refer to exactly those variables in the difference condition.

Formally, the assumption is $M \models \phi \oplus \psi$ —that is, under all models of M, either $\phi$ is true or $\psi$ is true, and not both. Note the absence of a situation $\vec{u}$ . Thus, we can re-phrase a counterfactual question as:

(6) \begin{equation}\textrm{Assuming $M \models (\phi \oplus \psi)$, why $(M, \vec{u}) \models \phi$ ?}\end{equation}

As a shorthand, we use $M^{\phi\oplus\psi}$ to refer to the sub-model of M in which $\phi\oplus\psi$ is always true. That is, the functions in $\mathcal{F}$ are restricted such that assignments to all variables always conform to $\phi\oplus\psi$ .

The set of events $\vec{X} = \vec{x}$ is a presupposed contrastive cause of $\phi$ under situation $(M, \vec{u})$ and assumption $M \models \phi \oplus \psi$ if and only if the following condition holds:

• PAC $\vec{X} = \vec{x}$ is an actual cause of $\phi$ under the situation $(M^{\phi \oplus \psi}, \vec{u})$ .

That is, if we assume that $\phi \oplus \psi$ always holds in a structural model, then an actual cause of $\phi$ in that model under situation $\vec{u}$ is sufficient to identify the different condition. Note here that the cause is not contrastive because it is not a pair—it just refers to the variables in $\vec{X}$ and their values in $\vec{u}$ . However, this is enough for us to propose the following theorem.

Proof. This theorem is effectively stating that if AC1-3 hold assuming $\phi \oplus \psi$ , then CC1-5 hold for some $\vec{y}$ , and vice-versa.

The left-to-right case: For CC1, if $\vec{X} = \vec{x}$ is an actual cause under a restricted model $M^{\phi \oplus \psi}$ , then model M must admit $\vec{X} = \vec{x}$ as (at least) a partial cause for $\phi$ . For CC2, $(M, \vec{u}) \models \neg\psi$ must hold because $\phi$ holds according to AC1, and $\phi$ and $\psi$ are mutually exclusive. For the remainder, we need to show that a $\vec{y}$ exists such that CC3-5 hold. From AC2, we know that there exists some counterfactual situation in which $\phi$ would not have occurred under $M^{\phi\oplus\psi}$ . In such a situation, it must be that $\psi$ occurred, so all such situations would be candidate values for $\vec{y}$ . This implies CC3. In addition, the values in $\vec{y}$ must make $\psi$ true, and therefore must be different from the values in $\vec{x}$ , so CC4 holds. Finally, we prove CC5 (maximality) by contradiction. Assume that $\vec{X}$ is not maximal. This implies there exists some additional variables $\vec{Y}$ not in $\vec{X}$ that must change to make $\psi$ hold under $(M,\vec{u})$ . However, this would also require these variables to change under $M^{\phi \oplus \psi}$ , which would mean that $\vec{X} = \vec{x}$ is not a complete actual cause of $\phi$ , contradicting the definition of PAC. Therefore, $\vec{X}$ must be maximal.

For the right-to-left case, AC1 is implied trivially by CC1: $\vec{X} = \vec{x}$ and $\phi$ hold under $M^{\phi\oplus\psi}$ , and expanding the model without changing the structural equations themselves will not change the $\phi$ . AC2 is implied by CC3: if there is an alternative situation $\vec{u}'$ under M such that $\psi$ holds, then that same situation must exist in $M^{\phi\oplus\psi}$ because $M^{\phi\oplus\psi}$ does not exclude situations in which $\psi$ holds, so any such situation gives us the setting for $\vec{x}'$ that is required for the counterfactual situation in AC2.

For AC3, we need to show that the partial cause $\vec{X} = \vec{x}$ under M is minimal under $M^{\phi\oplus\psi}$ . We prove this by contradiction. Assume that $\vec{X} = \vec{x}$ is not minimal under $M^{\phi\oplus\psi}$ . This means that there is some variable W that has no effect on $\phi$ under $M^{\phi \oplus \psi}$ , but is cited as a contrastive cause. Therefore, some part of the contrastive cause cites the events $(\vec{W} = \vec{w},\vec{W}=\vec{z})$ for some $\vec{w},\vec{z}$ , and that $\vec{W} = \vec{w}$ is a partial cause of $\phi$ under $(M,\vec{u})$ and $\vec{W}=\vec{z}$ is a partial cause of $\psi$ under the hypothetical situation in CC3. However, $\vec{W}=\vec{z}$ must then be a counterfactual case for $\vec{W}$ that satisfies AC2 under $M^{\phi\oplus\psi}$ , meaning that it affects $\phi$ . This is a contradiction for our assumption that $\vec{X} = \vec{x}$ is not minimal.

Proof. The proof is a straightforward extension of the proof from Theorem 4. In brief: the $\vec{y}$ referred to in Theorem 4 is from the surrogate. The two cases on the left of the if and only if are symmetric, so the proof above extends to this.

6.1 Non-contrastive explanation

In Part II (Halpern & Pearl, Reference Halpern and Pearl2005b) of their paper, Halpern & Pearl build on the definition of causation from Part I to provide a definition of causal explanation. They define the difference between causality and explanation as such: causality is the problem of determining which events cause another, whereas explanation is the problem of providing the necessary information in order to establish causation. Thus, an explanation is a fact that, if found to be true, would be a cause for an explanandum, but is initially unknown. As such, they consider that explanation should be relative to an epistemic state. This is in fact a definition of contrastive explanation using epistemic relevance (Slugoski et al.,, Reference Slugoski, Lalljee, Lamb and Ginsburg1993).

Informally, an explanation is defined in their framework as follows. Consider an agent with an epistemic state $\mathcal{K}$ , who seeks an explanation of event $\phi$ . A good explanation should: (a) provide more information than is contained in $\mathcal{K}$ ; (b) update $\mathcal{K}$ in such a way that the person can now understand the cause of $\phi$ ; and (c) it may be a requirement that $\phi$ is true or probableFootnote ⁵ .

Halpern and Pearl (Reference Halpern and Pearl2005b) formalize this by defining $\mathcal{K}$ as a set of contexts, which represents the set of ‘possible worlds’ that the questioning agent considers possible. Therefore, an agent believes $\phi$ if and only if $(M,\vec{u}) \models \phi$ holds for every $\vec{u}$ in its epistemic state $\mathcal{K}$ . A complete explanation effectively eliminates possible worlds of the explainee so that they can now determine the cause. Formally, an event $\vec{X} = \vec{x}$ is an explanation of event $\phi$ relative to a set of contexts $\mathcal{K}$ if the following hold:

• EX1 $(M, \vec{u}) \models \phi$ for each $\vec{u} \in \mathcal{K}$ —that is, the agent believes that $\phi$ .

• EX2 $\vec{X} = \vec{x}$ is a sufficient cause of $\phi$ for all situations $(M, \vec{u})$ where $u \in \mathcal{K}$ such that $(M, \vec{u}) \models \vec{X} = \vec{x}$ .

• EX3 $\vec{X}$ is minimal—no subset of $\vec{X}$ satisfies EX2.

• EX4 $(M, \vec{u}) \models \neg (\vec{X} = \vec{x})$ for some $\vec{u} \in \mathcal{K}$ and $(M, \vec{u}') \models \vec{X} = \vec{x}$ for some (other) $\vec{u}' \in \mathcal{K}$ —that is, before the explanation, the agent is initially uncertain whether the information contained in the explanation is true or not, meaning the explanation meaningfully provides information.

6.2 Contrastive counterfactual explanation

We extend the above definition to contrastive counterfactual causes. As with the Halpern and Pearl definition, it is defined relative to an epistemic state and model, however, as it describes a contrastive cause, the explanation is a pair.

Definition 4 defines a counterfactual contrastive explanation as finding part of a counterfactual cause that satisfies the conditions CE1-4. However, we can think of this in different way: finding partial explanations for each of $\phi$ and $\psi$ and taking the difference between these, where we define a partial explanation as just a subset of an explanation.

Proof. Left-to-right case: (CE1^′) This holds from CE2-4. If $\langle \vec{X} = \vec{x}, \vec{X} = \vec{y}\rangle$ is a sufficient counterfactual cause for $\langle\phi, \psi\rangle$ that is minimal and uncertain, then $\vec{X} = \vec{x}$ must be a partial explanation of $\phi$ under $(M,\vec{u}$ ); that is, the agent believes $\phi$ , some superset of $\vec{X} = \vec{x}$ is an actual cause of $\phi$ , and the agent is uncertain about some of that superset. (CE2^′) The same argument holds, except that $\vec{X} = \vec{y}$ is true under the hypothetical situation $(M_{\vec{W} \leftarrow \vec{w}},\vec{u})$ from CE2; and therefore, this hypothetical situation is a witness for CE2^′. (CE3^′) The difference condition holds because this is a requirement the sufficient counterfactual cause in of CE2. (CE4^′) holds from the maximality condition in CE2. This establishes the left-to-right case.

Right-to-left case: (CE1) This holds directly from CE1^′, because the acceptance of $\phi$ in $\mathcal{K}$ is a condition of an explanation under the original Halpern & Pearl definition, and $\psi$ must be false whenever $\phi$ is true. (CE2) If $\vec{X} = \vec{x}$ and $\vec{X} = \vec{y}$ are partial explanations of $\phi$ under $(M,\vec{u})$ and $\psi$ under $(M_{\vec{W} \leftarrow \vec{w}},\vec{u})$ respectively, then they must be partial causes too. If their intersection is empty and $\vec{X}$ is maximal, then this defines a sufficient cause, so CE2 holds. (CE3) We prove this via contradiction. Assume $\vec{X}$ is not minimal. This implies that there is some strict superset $\vec{Y} \supset \vec{X}$ that satisfies CE1^′-4^′ and CE2. However, if this were the case, then CE4^′ would not hold: $\vec{X}$ would not be maximal over CE1^′-3^′, which is a contradiction, so our assumption is false. (CE4) If $\vec{X} = \vec{x}$ and $\vec{X} = \vec{y}$ are partial explanations under $(M,\vec{u})$ and some hypothetical counterfactual case $(M_{\vec{W} \leftarrow \vec{w}},\vec{u})$ , then the agent must be uncertain about $\vec{X} = \vec{x}$ in $(M,\vec{u})$ and $\vec{X} = \vec{y}$ in $(M_{\vec{W} \leftarrow \vec{w}},\vec{u})$ . This establishes the right-to-left case, and the theorem holds.

6.3 Bi-factual contrastive explanation

For the bi-factual case, an explanation is similar, however, it refers to two epistemic states, $\mathcal{K}$ and $\mathcal{K}'$ , in which $\mathcal{K}$ models the uncertainty of the individual in the situation $(M,\vec{u})$ and $\mathcal{K}'$ models the uncertainty in $(M',\vec{u}')$ .

This is similar to the definition of CE, except that the rules refer to an actual situation $\vec{u}'$ , rather than the hypothetical situation implied by CE2. The more general case in which there are differences between the models is straightforward projection of this.

Definition 6 defines bi-factual explanation as finding part of a counterfactual cause that satisfies the conditions BE1-4. However, we can think of bi-factual explanation in different way: finding partial explanations for each of $\phi$ and $\psi$ and taking the difference between these, where we define partial explanation as just subsets of explanations.

Proof. The proof for this is similar to the proof for Theorem 6, except simpler because we deal only with factual situations and no hypothetical situations.

Left-to-right case: (BE1^′ and BE2^′) These both hold from BE2-4. If $\langle \vec{X} = \vec{x}, \vec{X} = \vec{y}\rangle$ is a sufficient counterfactual cause for $\langle\phi, \psi\rangle$ that is minimal and uncertain, then $\vec{X} = \vec{x}$ and $\vec{X} = \vec{y}$ must be partial explanations of $\phi$ and $\psi$ under $(M,\vec{u})$ and $(M, \vec{u}')$ respectively. (BE3^′) The difference condition holds because this is a requirement of sufficient bi-factual cause in BE2. (BE4^′) holds from the maximality condition in BE2. This establishes the left-to-right case.

Right-to-left case: (BE1) This holds directly from BE1^′ and BE2^′, because the acceptance of $\phi$ in $\mathcal{K}$ and $\neg\psi$ in $\mathcal{K}'$ respectively are conditions of explanations under the original Halpern & Pearl definition. (BE2) If $\vec{X} = \vec{x}$ and $\vec{X} = \vec{y}$ are partial explanations of $\phi$ and $\psi$ under $(M,\vec{u})$ under $(M,\vec{u}')$ respectively, then they must be partial causes too. If their intersection is empty and $\vec{X}$ is maximal, then this defines a sufficient cause, so BE2 holds. (BE3) We prove this via contradiction. Assume $\vec{X}$ is not minimal. This implies that there is some strict superset $\vec{Y} \supset \vec{X}$ that satisfies BE1^′-4^′ and BE2. However, if this were the case, then BE4^′ would not hold: $\vec{X}$ would not be maximal over BE1^′-3^′, which is a contradiction, so our assumption is false. (BE4) If $\vec{X} = \vec{x}$ and $\vec{X} = \vec{y}$ are partial explanations of $\phi$ and $\psi$ under $(M,\vec{u})$ and $(M,\vec{u}')$ respectively, then the agent must be uncertain about $\vec{X} = \vec{x}$ in $(M,\vec{u})$ and $\vec{X} = \vec{y}$ in $(M,\vec{u})$ . This establishes the right-to-left case, and the theorem holds.

6.4 Non-contrastive general explanation

The definitions provided in the previous section merely allow explanations in which the causal model is known to the explainee agent, but the agent is uncertain which context is the real context. A more general definition allows for explanations in which the agent is also uncertain about the causal model, and thus the explanation is about both the causal model and the context.

Halpern and Pearl (Reference Halpern and Pearl2005b) present an extended definition of explanation based on this idea. In this case, an epistemic state $\mathcal{K}$ is now a set of situations $(M, \vec{u})$ instead of a set of just contexts. A general explanation is of the form $(\alpha, \vec{X} = \vec{x})$ , in which $\alpha$ is a causal formula. The first component restricts the set of models, while the second restricts the set of contexts.

A formula-event pair $(\alpha, \vec{X} = \vec{x})$ is an explanation of event $\phi$ relative to a set of situations $\mathcal{K}$ if:

• EX1 $(M, \vec{u}) \models \phi$ for each $(M,\vec{u}) \in \mathcal{K}$ (unchanged).

• EX2 for all situations $(M, \vec{u})$ such that $(M, \vec{u}) \models \vec{X} = \vec{x}$ and $M \models \alpha$ ( $\alpha$ is valid in all contexts consistent with M), $\vec{X} = \vec{x}$ is a sufficient cause of $\phi$ .

• EX3 $(\alpha,\vec{X} = \vec{x})$ is minimal—there is no pair $(\alpha',\vec{X}^{\prime} = \vec{x}') \neq (\alpha,\vec{X} = \vec{x})$ satisfying EX2 such that $\{M'' \in M(\mathcal{K}) \mid M'' \models \alpha'\} \supseteq \{M'' \in M(\mathcal{K}) \mid M'' \models \alpha\}$ and $\vec{X}^{\prime} = \vec{x}' \subseteq \vec{X} = \vec{x}$ , where $M(\mathcal{K}) = \{M \mid (M,\vec{u}) \in \mathcal{K} \textrm{ for some } \vec{u}\}$ .

• EX4 $(M, \vec{u}) \models \neg (\vec{X} = \vec{x})$ for some $(M, \vec{u}) \in \mathcal{K}$ and $(M', \vec{u}) \models \vec{X} = \vec{x}$ for some (other) $(M', \vec{u}') \in \mathcal{K}$ —that is, the agent is uncertain, as before.

In this definition, the two parts of the explanation play different roles. The formula $\alpha$ characterizes the part of the model that is unknown to the agent to just enough information to understand the causes of $\phi$ ; while $\phi$ is an explanation in that restricted set of models.

Example 6.4. As a simple example, consider an agent who does not know how the arthropod system works at all, and confronted with $O=Spider$ , they ask why. An explanation is the pair:

\[ (L=8 \land S=4 \land E=8 \land C=4 \land W=0 \Rightarrow O=Spider, L=8) \]

plus one for all other variables other than L. The formula informs the explainee what the properties of a spider are, but does not need to define the entire model nor even the properties of other arthropods.

However, the $\alpha$ part of the explanation can be arbitrary causal formula. For example, given a 7-legged spider with no annotation, which will cause $V=Pass$ , an explanation could refer to formula such as:

\[ (O=Unknown \land A=Unknown) \Rightarrow [A \leftarrow Spider] (V=Pass), \]

which means that when both variables are unknown, adding an annotation will still give a result of Pass.

6.5 General contrastive explanation

The more general case of contrastive explanation is straightforward to project from this definition. We give just the definition for bi-factual explanation.

The general counterfactual explanation case is straightforward to extend from Definition 8, however, one important point of difference is that the explanation is not a pair, but a triple, $\langle \alpha, \vec{X} = \vec{y}, \vec{X} = \vec{y})$ . There is no requirement for the second formula $\beta$ because there is only one model to characterize.

Example 6.5. Consider the extended arthropod system in the situation in Example 6.1, where there is an image of a spider with 7 legs. In this case, the verification passes because $O=Unknown$ . The agent knows all variables but is unaware of $F_V$ , so does not know the verification procedure, and asks ‘Why $V=Pass$ instead of $V=Fail$ ?^′

In this case, the explanation is a formula expressing the semantics of $F_V$ , and no variables:

\[\langle (O=Unknown \lor A=Unknown \Rightarrow V = Pass), L=7, L=8 \rangle\]

6.6 Example: goal-directed AI planning

Throughout the paper, we have used the two examples of the arthropod system to illustrate ideas. In this section, we consider a different type of AI system: goal-directed planning.

in which $A_{[1-3]}$ are names of the actions, $G_{[1-3]}$ are propositions modeling goals, and $P_{[1-2]}$ are propositions modeling action preconditions. The planner can apply none, one, or many actions.

Figure 3 shows the causal graph for this, in which $U_{[1-5]}$ are exogenous variables. All variables are Boolean. Variables $P_{[1-2]}$ and $G_{[1-3]}$ represent preconditions and goals being true. Variables $A_{[1-3]}$ represent whether an action could be selected for execution given the goals and its precondition. The structural equations are such that action $A_1$ is selected if $G_1$ or $G_3$ is the goal, and its precondition $P_1$ holds; $A_2$ is selected if $G_2$ or $G_3$ is the goal, and its precondition $P_2$ holds; and $A_3$ is selected if precondition $P_2$ needs to be made true. Note that this does not model the cause of the preconditions goals becoming true/false, but the cause of action selection, which makes the graph appear somewhat inverted. The parent node for each action has both the variables it requires to be true to execute the action as well as the variables the action will change; e.g. $A_1$ will be ‘fired’ if $P_1$ is true and $G_1$ is true, which counter-intuitively models that in the actual planning problem, the goal is currently false and should become true. We could also add a node which states whether the goal is true/false and only execute the action if the goal is false, but we omit this for simplicity. Note that $P_2$ is the parent of $A_3$ , modeling that this is $A_3$ ’s intermediate ‘goal’—it makes $P_2$ true, thus enabling $A_2$ to be selected next.

Figure 3

Causal graph for goal-directed planning.

Now consider the case in which $G_1$ and $G_3$ are the goals (while $G_2$ is false) and $P_1$ and $P_2$ are both true, implying that $A_1$ is true and $A_2$ is false. A contrastive question could be: ‘Why $A_1$ rather than $A_2$ ?’, which would be modeled as ‘Why $(M, \vec{u}) \models A_1 \land A_2$ rather than $\neg A_1 \land A_2$ ?’. $\mathcal{K}$ (the epistemic state of the explainee) is such that $G_1$ is known to be true, but the agent is unsure of the other goals and the preconditions.

The contrastive counterfactual cause for this is the pair $\langle (G_1, \neg G_1), (\neg G_2, G_2)\rangle$ . That is, for the $A_2$ to be true instead of $A_1$ (CC3), it would require that the goals $G_1$ and $G_2$ are swapped. CC1-2 hold trivially, and CC4 (the difference conditions) holds because there are no common events. CC5 (maximality) holds because changing the values of $G_1$ or the preconditions $P_1$ and $P_2$ do not satisfy the difference condition CC4.

The contrastive explanation, however, consists only of $\langle(\neg G_2, G_2)\rangle$ —the agent already knows that $G_1$ is true so including $G_1$ would not satisfy both CE3 (the minimality condition) and CE4 (the ‘meaningful’ condition).

The effect of CE4 is that this has no explanation! Intuitively, one may expect that $(\neg P_2, P_2)$ to be offered, however for this to be an explanation, CE4 requires that there is some situation $\vec{u} \in \mathcal{K}$ in which $P_2$ could be true. But this is not possible because the agent knows that $A_2$ is false and $G_2$ is true, which cannot be the case if $P_2$ is true, so no such situation exists. According to the model M, there can be only situation in $\mathcal{K}$ where the goals are all known as $\neg G_1$ , $G_2$ , and $\neg G_3$ , and in that situation $\neg P_1$ and $P_2$ hold. This offers the agent a complete explanation already. This makes sense: the agent does not require an explanation because it can infer the values of $P_1$ and $P_2$ itself.

However, consider the case of a general contrastive explanation in which the agent’s knowledge is missing part of the structure of the causal graph; specifically, that $P_2$ is the precondition of $A_2$ , meaning that the edge $P_2 \rightarrow A_2$ is missing from the graph in Figure 3. Now we have an explanation! In this case, the explanation is $\langle (F_{A_2} = f, \emptyset), (F_{A_2} = f', \neg P_2)\rangle$ , in which f is the definition of $F_{A_2}$ without the precondition, and f ^′ includes the precondition.