Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations⋆
arXiv:2605.08688v1 [cs.AI] 9 May 2026
Leopoldo Bertossi⋆⋆ Carleton University, Canada & IMFD, Chile
Abstract. We establish, from the point of view of Explainable AI (XAI), connections between Consistency-Based Diagnosis (CBD), on one side, and Actual Causality and Causal Responsibility, on the other. CBD has received little attention from the XAI community. Connections between these two areas could have a fruitful impact on XAI and Explainable Data Management.
1
Introduction
Explainable AI (XAI), and in particular Explainable Machine Learning, have become relevant areas of research in AI. Actual Causality, first proposed by Joe Halpern and Judea Pearl [17], and Causal Responsibility, first proposed by Hana Chockler and Joe Halpern [14], have been applied in XAI, to provide explanations for outcomes from machine-learning (ML) models [6, 7, 13]. They have also been applied in Explainable Data Management (XDM), to provide explanations for query answering [22, 4, 5] (see [8] for a survey of some approaches). Causality has gained prominence in ML, both for explaining and interpreting learned models, but also for learning itself [20, 25]. A more classic area of AI is Model-Based Diagnosis (MBD) [26]. It deals with providing explanations for the results from models found in knowledge representation. One of its prominent forms, Consistency-Based Diagnosis (CBD), proposed by Ray Reiter [24], is typically applied to obtain diagnoses for a system that exhibits an unintended behavior. CBD has an interesting role to play in XAI. Abduction, or sufficient explanations, is another form of MBD that has found its way into XAI [1, 15, 19, 13]; and also in XDM [5, 12, 11]. Since there is larger body of recent research on the use of abduction in XAI , we do not consider abduction in this work. CBD has received much less attention. In this work we explore connections between actual causality and CBD. They haven’t received much attention; and we think the two areas can profit from each other. Actually, in [4], an early connection allowed us to design algorithms for obtaining causal explanations in XDM, and to obtain complexity results for CBD. For reasons of space, and to best convey intuitions, we unveil and formulate ⋆
Dedicated to the memory of Joseph Y. Halpern, a great scholar, a universal researcher. ⋆⋆ Emeritus Professor. Adjunct Professor Western University, Canada. [email protected]
interesting connections by means of examples. However, it should become clear how to formulate things in general terms. We also show how the established connections can be exploited in technical terms. Exploring them in more depth is is part of ongoing work. In this work we stick to the propositional case, that is, logical specifications, features, classifiers, and models on which CBD is performed are all written in propositional logic or are binary. In Section 2, we review and present actual causality and responsibility as used to explain outcomes from classification models, those usually learnt in machine learning. In Section 3, we show how a typical problem of CBD can be recast as one of actual causality, and how responsibility could become a new ingredient in CBD. On the basis of CBD problems we give a precise definition of actual causality, and responsibility. Furthermore, we show how the CBD problem could be represented by means on a Structural Causal Model [23]. In Section 4, we proceed the other way around. We take a classification problem that would be normally approached via actual causality and responsibility (or some other attribution method of XAI), and formulate it a CBD problem. In Section 5, we show an example of how CBD can borrow techniques to actual causality, and the other way around.
2
Actual Causality and Responsibility in XAI
The goal of this section is twofold. We describe and illustrate, by means of an example, the main concepts of actual causality; and we also show how to apply them in XAI, in this case, to obtain explanations from a ML-based classifier. Precise definitions in the context of CBD are given in Section 3. The basic idea behind actual causality [17, 18] is that of performing counterfactual interventions on the values of variables of a model, changing their values in order to detect if there are changes in other variables, typically the output of the model. The interventions lead to counterfactual and actual explanations. Example 1. Consider a classifier C an in Figure 1(a) that has been learned from training data. After that, it can be complex enough for us to have an idea about what is going on inside. C may well be (or treated as) a black-box classifier, but we can use C’s input/output relation. For an input entity e = ⟨x1 , x2 , x3 , x4 ⟩ ∈ {0, 1}4 , with four binary feature values, the label L(e) ∈ {0, 1} is returned. X1 X2 X3 X4
C
1 0 0 1
L
Fig. 1. (a) A Binary Classifier.
X1 X2 X3 X4
C
L
0
(b) Particular Input/Output.
2
0 0 0 1
X1 X2 X3 X4
C
L
1
0 1 0 1
X1 X2 X3 X4
C
L
0
1 0 0 1
X1 X2 X3 X4
L
C
0
1 As X1 shown in Figure 1(b), with input e = ⟨1, 0, 0, 1⟩, we obtain label 0. We 0 X1 0 X2an explanation, as feature values L 0 in e that want C 0 are X2 actual causes for the outcome. 0 X3 C from 0 toL1?1 Do changes of (interventions on) feature values the label 0 Xchange 3 1 X 4
1
X4
1 1 0 1
X1 X2 X3 X4
0 0 0 1
X1 X2 X3 X4
0 1 0 1
X1 X2 L 0 C X3 As X4 shown in Figure 2(a), the change on x1 from 1 to 0 changes the label. The
L
C
1
Fig. 2. (a) Successful Intervention.
L
C
0
(b) Unsuccessful Intervention.
value x1 = 1 is said to be a counterfactual cause for the initial label: A change on x1 alone already changes the label. Now, let’s concentrate on x2 . Figure 2(b) shows x2 = 0 is not a coun1 Xthat 1 0 aX2moment, and consider the terfactual cause for L = 0. Let’s keep it value for L 0 C 1 X3 3(a). following unsuccessful intervention on x3 , x4 in Figure
1 0 1 0
X1 X2 X3 X4
C
L
0
+
contingency set
Fig. 3. (a) Unsuccessful Intervention.
+
contingency set
0
X4
1 1 1 0
X1 X2 X3 X4
C
L
(b) Successful Intervention.
1 X1 1 XIf, 2 L changes, 1 in additionCto those two we change again x2 to 1, we are now 1 X3 successful, as shown in Figure 3(b). We say that x2 = 0 is an actual cause for the 0 X4
original label, and Γ = {x3 = 0, x4 = 1} is a contingency set (CS) for x2 = 0: In order for the change on x2 to change the label, it needs an additional, contingent set of changes. However, those two contingent changes alone do not change the label. We say that e′ = ⟨0, 0, 0, 1⟩ and e′′ = ⟨1, 1, 1, 0⟩ are counterfactuals (counterfactual versions) of the original entity e. ■ The causal responsibility of an actual cause is a numerical quantification of its strength as a cause. It is based on the number of additional changes an actual cause needs to change the label. Actually, for an actual cause x = v, its responsibility is defined by Resp(x) := 1/(1+|Γ |), where Γ is a minimum-size CS for x. Feature values that are not actual causes have, by definition, responsibility 0. Example 2. (ex. 1 cont.) Since x1 = 1 in e does not need additional changes, Γ = ∅ is its minimum CS, and then, its responsibility is Resp(x1 ) = 1, the maximum possible responsibility. If we assume that Γ = {x3 = 0, x4 = 1}, as above, is a minimum CS for x2 = 0, Resp(x2 ) = 1/(1 + 2) = 1/3. ■
3
1
Actual causality provides counterfactual explanations to observations. In general terms, they are “components” of a system that are a cause for an observed behavior. Counterfactual causes are actual causes with an empty CS. Accordingly, counterfactual causes are strong causes in that they, by themselves, explain the observation. Actual causes that are not counterfactual causes are weaker causes, they require the company of other components to explain the observation. In some applications of actual causality, there may be variables that are declared endogenous, while the others are exogenous. The former are of interest for causality purposes. In particular, only endogenous variables can be actual causes and members of CSs. In our example, we could have declared x3 as exogenous; for example, if we know that its value has to be 0, no matter what. This value is not subject to interventions. In that case, x3 could not have been a member of the CS any longer. We would have to look for contingencies somewhere else. The choice of endogenous/exogenous variables is application dependent. See [23, sec. 5] for a relevant discussion. Actual causality and responsibility can be applied without necessarily knowing “the internals” of the classifier, which can be (or be treated as) a “black box”. Only the input/output relation is needed. Responsibility has become, as more generally called in XAI, an attribution score. The kind of explanations obtained are local in that they apply to values in a single input entity. As defined, responsibility does not provide a global explanation for the behavior of the classifier. The computation of the responsibility score in explainable ML is known to be intractable, already in the binary case [7]. Above we introduced responsibility in a binary setting. When feature values are not binary, its definition has to be extended. This was done, analyzed and experimented with in [6] (see also [9]).
3
Consistency-Based Diagnosis as Actual Causality
We will first introduce and illustrate consistency-based diagnosis (CBD) [24, 16] by means of an example. After that, we will show how to cast it as an actual causality problem related to classification. If we are confronting a system that is exhibiting an unexpected or abnormal behavior, we want to obtain a diagnosis for this, i.e. some sort of explanation. Diagnoses are obtained from a model of the system. Example 3. Figure 4(a) shows a very simple Boolean circuit with an And-gate, A, and an Or-gate, O. The input variables are a, b, c, the intermediate output variable for A is x, and the final, output variable is d; all of them taking values 0 or 1. The intended meaning of the propositional variable a is “input a is true” (or takes value 1), etc. With the indicated inputs and output, the circuit seems to be behaving as expected. Figure 4(b) shows an unintended behavior: with those inputs, the output should be 1. We need a diagnosis for the abnormal behavior of the circuit. Diagnoses have to be characterized; for this we need a model. 4
and gate 1 0 1
a b c
A
1
x
O or gate
d
0
1
(x = 0)
1
Fig. 4. (a) Boolean Circuit.
a b c
A
x
O
d
0
(b) Faulty Boolean Circuit.
In this example, a logical model of the circuit, when it works properly, is a set of propositional formulas: {(x ←→ (a ∧ b)), (d ←→ (x ∨ c))}. However, our circuit at hand, by working abnormally, is not modeled by these formulas. Furthermore, the observation, Obs = {a, ¬b, c, ¬d}, indicating that a and c are true, but b and d are false, is mutually inconsistent with this ideal model: there is no assignment of truth values to the propositional variables that makes the combination true. From their combination we cannot logically obtain any useful information. We may want instead a model that allows failures, or abnormal behaviors. From such a model, we could try to obtain explanations for them. A better, more flexible model that allows failures, and specifies how components behave under normal conditions is: M = {¬abA −→ (x ↔ (a ∧ b)), ¬abO −→ (d ↔ (x ∨ c))}.
(1)
The first formula says “When A is not abnormal, it works as an And-gate”, etc. Here, abA and abO are new propositional variables. This is a “weak model of failure” in that it specifies how things behave under normal conditions, but not under abnormal ones. This is common kind of models under CBD [16]. Model M assumes that the only potentially faulty components are, in this case, the gates (but not the wires connecting them), a modeling choice. Now gates could be abnormal (or faulty), and Obs ∪ M is a perfectly consistent set of formulas. When one specifies, in addition, that the gates are not abnormal, we reobtain that: {a, ¬b, c, ¬d} ∪ M ∪ {¬abA, ¬abO} is inconsistent.
(2)
Then, something has to be abnormal, and it is through consistency restoration that we will be able to characterize and compute diagnoses. If we make gate O abnormal in (2), we restore consistency, that is, in contrast to (2), Obs ∪ M ∪ {¬abA, abO} is consistent (underlying the change made). Accordingly, and by definition, ∆ = {abO} is a diagnosis. Similarly, ∆′ = {abO, abA} is a diagnosis, because making every gate abnormal also restores consistency: Obs ∪ M ∪ {abA, abO} is consistent. We may consider ∆ as a “better” diagnosis than ∆′ , because it makes fewer assumptions; it is more informative by providing narrower and more focused diagnosis. ∆ is a minimal diagnosis in that it is not set-theoretically included in any other diagnosis. It is also a minimum diagnosis in that it has a minimum 5
cardinality.
3.1
■
CBD as a Causal Problem
Now, we are going to cast the CBD problem as an actual causality problem, and as applied to a classification problem. We do this by appealing to our example. Example 4. (ex. 3 cont.) The classification problem is that of deciding if an input -with a model- is satisfiable or not. The model is M in (1). Our classifier, with its binary inputs and output, is shown in Figure 5. It consists of model M plus a SAT solver that verifies if M is consistent with the input e, whose last component, d, stands for the output of the circuit. SAT ? e = ⟨abA, abO, a, b, c, d⟩
¬abA −→ (x ↔ (a ∧ b))
−→ (propositional feature vector)
¬abO −→ (d ↔ (x ∨ c))
−→ yes/no
+ SAT solver
Fig. 5. A Consistency Classifier
As we saw in Example 3, with e = ⟨0, 0, 1, 0, 1, 0⟩, representing ⟨¬abA, ¬abO, a, , ¬b, c, ¬d⟩, the classifier returns “no” (or 0). Then, we can apply actual causality by first declaring “features” abA, abO as endogenous, subject to interventions, while the others, a, b, c, d, are exogenous. They provide context and are not subject to interventions. By counterfactually intervening e, producing e′ = ⟨0, 1, 1, 0, 1, 0⟩, indicating that abO is true, we manage to change the classifier’s output to yes. This does not happen with abA though. Then, “abO = 0” is a counterfactual cause. Intervening both abO and abO also changes the output, but this set of changes includes one that is already a counterfactual cause. Accordingly, abA is neither a counterfactual nor an actual cause. Now we can apply responsibility to our CBD scenario: Resp(abO) := 1, and Resp(abA) := 0. ■ Our example suggests a correspondence between actual causes with their minimal/minimum contingency sets and minimal/minimum diagnoses. To formulate this connection, we need a formal definition of actual cause, which in Section 2 we did not provide. We do this now, but grounding the general definition in the CBD setting. 3.2
Revisiting the Connection
Let us start with a weak model of failure of a system, as in Example 3, that is, a specification in propositional logic, M, of the form: M = {¬abC1 → φ1 , ¬abC2 → φ2 , . . . ¬abCn → φn }, 6
(3)
for n potentially faulty components C = {C1 , . . . , Cn } in the system. No abCi propositional variables appear in the consequents of the implications. This is what makes the model a weak model; nothing is said about how the system behaves under abnormality. This is not the only kind of specifications in CBD. They could also have ab atoms in places of the formulas. However, those we are considering are common, and enjoy of some good properties. See [16, sec. 7] for a discussion. In we also have an observation, Obs, a set of non-ab-literals, i.e. inputs and outputs, we may consider the system is not working properly in that: M ∪ Obs ∪ {¬abC i | i = 1, . . . , n} is inconsistent.
(4)
A diagnosis is a subset ∆ of {abC 1 , abC 2 , . . . , abC n } such that the assumption that they are true restores the consistency in (4), that is, M ∪ Obs ∪ ∆ ∪ {¬abC | C ∈ C and abC ∈ / ∆} is consistent.
(5)
A minimal diagnosis ∆ is a diagnosis, such that no proper subset of ∆ is also a diagnosis. In general, we want minimal diagnoses. They are the most informative ones. Sometimes we concentrate on the subclass of minimum diagnoses, those with minimum cardinality. Approaching the CBD problem as one about actual causality, (4) becomes a natural scenario for performing counterfactual interventions on the ¬ab literals, the only ones declared as endogenous; to detect if they falsify the inconsistency, returning to the expected consistency. On this basis, and according to [17], we can give the following definition. Definition 1. For a diagnosis setting ⟨C, M, Obs⟩ as in (4): (a) An atom abC i is a counterfactual cause iff M ∪ Obs ∪ {abC i } ∪ {¬abC j | j = 1, . . . , i − 1, i + 1, . . . n} is consistent. (b) An atom abC i is an actual cause iff there is Γ ⊆ ({abC | C ∈ C} ∖ {abC i }), such that: (b1) M ∪ Obs ∪ {¬abC i } ∪ Γ ∪ {¬abC | C ∈ C, abC ∈ / (Γ ∪{abC i })} is inconsistent, but (b2) M ∪ Obs ∪ {abC i } ∪ Γ ∪ {¬abC | C ∈ C, abC ∈ / (Γ ∪ {abC i })} is consistent. Γ is called a contingency set for abC i . (c) The responsibility of an actual cause abC is Resp(abC ) := 1/(1 + |Γ |), with Γ a minimum contingency set for abC . A non-actual cause has responsibility 0. ■ Notice that the definition can be applied with a model of which we only know the normal input/output behavior. Notice also that every counterfactual cause is also an actual cause with empty contingency set. The following proposition holds. Proposition 1. For a diagnosis setting ⟨C, M, Obs⟩: (a) A literal abC is a counterfactual cause iff ∆ = {abC } is a diagnosis. (b) A literal abC is an actual cause with minimal contingency set Γ iff abC belongs to a minimal diagnosis ∆, and Γ = ∆ ∖ {abC }. ■ 7
Example 5. (example 3 cont.) We had {a, ¬b, c, ¬d} ∪ M ∪{¬abA, ¬abO} as inconsistent. Switching ¬abO into abO, reestablishes consistency: {a, ¬b, c, ¬d} ∪ M ∪ {¬abA, abO} is consistent. Then, abO is a counterfactual cause for the malfunctioning of the circuit. However, when we switch abA, {a, ¬b, c, ¬d} ∪ M ∪ {abA, ¬abO} is still inconsistent. Accordingly, abA is not a counterfactual cause. It is not an actual cause either: its only potential contingency set Γ = {abO} does not satisfy condition (b1) in Definition 1(b). ■ We restrict Proposition 1 to minimal diagnoses, because for models of the form (3), every superset of a diagnosis is a diagnosis [16, sec. 7]. However, not every superset of a contingency set is a contingency set for a tuple, due to condition (b1) in Definition 1. Furthermore, the minimal diagnoses are those of interest. 3.3
Causal Structural Models
Those who are more familiar with causality represented by structural models [23] may be missing them here. Actually, the diagnosis problems can also be cast in those terms. A purely logical model, as in the previous examples, does not distinguish causal directions, or between causes and effects. They can be better represented by a structural model that takes the form of a (directed) causal network. a b abA
abO
c
x
d
d = (‐abO ^ (c v x)) v (abO ^ ‐c ^ ‐x)
x = (‐abA ^ a ^ b) v (abA ^ (‐a v –b)
Fig. 6. Causal Network
Example 6. (ex. 4 cont.) The causal network in Figure 6 represents our possibly faulty circuit. In it, abA, abO are endogenous variables, which can be subject to counterfactual interventions; in this case, making AbA and AbO true or false. Variables x and d are endogenous, and have structural equations associated to them, as shown in Fig. 6, capturing the circuit’s logic. They are used unidirectionally, consistently with the edge directions. In this case, we use by choice -contrary to the weak model of failure in Figure (5)- equations that also specify the behaviour under abnormal conditions. ■
4
CBD for Explainable Boolean Classification
To fix and convey the main ideas, we concentrate here on Boolean-circuit classifiers that take Boolean features as inputs, and return a binary label, 1 or 0. 8
The Tractability of SHAP-Score over Deterministic and Decomposable Boolean Circuits The Tractability of SHAP-Score over Deterministic and Decomposable Boolean Circuits
O=0 ∧
∧ X1
∨
X1
z
∨
1
∧
y
¬
¬ X2
X3
x ∧
X4
0
X2
1
X3
0
X4
Figure 1: A deterministic and decomposable Boolean Circuit as a classifier. Figure 1: A deterministic and decomposable Boolean Circuit as a classifier.
Fig. 7. Boolean Classification Circuit et al. (2018a,b, 2019b); Peharz et al. (2020). We provide an example et of al. a deterministic and Peharz et al. (2020). We provide an example of a deterministic and (2018a,b, 2019b); decomposable Boolean circuit next (and give the formal definition indecomposable Section 2). Boolean circuit next (and give the formal definition in Section 2).
Example 7. Consider the Boolean circuit in Figure 7(a).1 The set of propositional input features is F = {x , x , x , x }. The output, O, is at the top node. The circuit on the right-hand side shows variables for the gate outputs. The BC can be logically specified: B = {(¬x ←→ y), (y ∧ x ∧ x ←→ x), (x ∨ x ←→ z), (x ∧ z ←→ O). As shown in Figure 7(b), with B and input entity e with:
Example 1 We want to classify papers submitted to a conference as rejected (Boolean Example 1 We want to classify papers submitted to a conference as rejected (Boolean value 0) or accepted (Boolean value 1). Papers are described by features and 1valuefg 2,0)dtror,3nf 4 na,(Boolean value 1). Papers are described by features fg, dtr, nf and na, accepted which stand for “follows guidelines”, “deep theoretical result”, “new framework” and “nice “follows guidelines”, “deep theoretical result”, “new framework” and “nice applications”, respectively. The Boolean classifier for the papers iswhich given stand by thefor Boolean applications”, respectively. The Boolean classifier for the papers is given by the Boolean circuit in Figure 1. The input of this circuit are the features fg, dtr , nf and na, each of 2 4 circuit in Figure are the features2fg, dtr, nf and na, each of which can take value either 0 or 1, depending on whether the feature is present (1)1.or The input of3 this circuit which can take value either 0 or 1, depending on whether the feature is present (1) or absent (0). The nodes 1 with labels ¬, ∨ or ∧ are logic gates, and the associated Boolean absent value of each one of them depends on the logical connective represented by its(0). labelThe and nodes the with labels ¬, ∨ or ∧ are logic gates, and the associated Boolean Boolean values of its inputs. The output value of the circuit is given value by theoftopeach nodeone in the of them depends on the logical connective represented by its label and the figure. Boolean values of its inputs. The output value of the circuit is given by the top node in the 1 2 3 4 The Boolean circuit in Figure 1 is said to be decomposable, because for each ∧-gate, the figure. sets of features of its inputs are pairwise disjoint. For instance, in the case the top node TheofBoolean circuit in Figure 1 is said to be decomposable, because for each ∧-gate, the in Figure 1, the left-hand side input has {fg} as its set of features, while sets its of right-hand features ofside its inputs are pairwise disjoint. For instance, in the case of the top node input has {dtr, nf, na} as its set of features, which are disjoint. Also,inthis circuit to Figure 1, isthesaid left-hand side input has {fg} as its set of features, while its right-hand side be deterministic, which means that for every ∨-gate, two (or more) of its inputs cannot be input has {dtr, nf, na} as its set of features, which are disjoint. Also, this circuit is said to given value 1 by the same Boolean assignment for the features. For instance, in the case be deterministic, which means that for every ∨-gate, two (or more) of its inputs cannot be of the only ∨-gate in Figure 1, if a Boolean assignment for the features gives value 1 to its given value 1 by the same Boolean assignment for the features. For instance, in the case left-hand side input, then feature dtr has to be given value 1 and, thus, such an assignment the it only in Figure 1, if a Boolean assignment for the features gives value 1 to its gives value 0 to the right-hand side input of the ∨-gate. In the sameofway, can∨-gate be shown left-hand side sideinput input,ofthen feature dtr has to be given value 1 and, thus, such an assignment that if a Boolean assignment for the features gives value 1 to the right-hand gives value 0 to the right-hand side input of the ∨-gate. In the same way, it can be shown this ∨-gate, then it gives value 0 to its left-hand side input.
e(x ) := 1, e(x ) := 0, e(x ) := 1, e(x ) := 0,
we obtain y = 1, x = 0, z = 0, and the output O(e) = 0.
(6)
■
We want to find input values as actual causes for the observed output. To approach the problem as CBD, we consider the output as something unexpected that ifwe a Boolean assignment for theto features gives value 1 tothe the right-hand under normal circumstances. Since have no reason assume that logicalside input of Readers who are not familiar with knowledge compilation can simply think about this ∨-gate, then itdegives value 0 to its left-hand side input. terministic and decomposable circuits as a tool for are establishing in a uniform manner the gates of the classifier working abnormally; we assume they are not faulty. Readers who are not familiar with knowledge compilation can simply think about deAccordingly, and departing from Section 3, we allow theas inputs to the classifier terministic and decomposable circuits a tool for establishing in a uniform manner the 3 to be faulty in that they do not produce the “expected output”, in this case, 3 Ō = 1, the complementary literal of O. We denote the original classifier with B(x1 , x2 , x3 , x4 ; O), indicating that, with inputs x1 , x2 , x3 , x4 , it returns actually, it becomes- the binary value O. Example 8. (ex. 7 cont.) We want to explain the output O = 0 by identifying the input values that are most relevant for the outcome. As in Section 3, we introduce, for each input features xi , a corresponding propositional variable ab(xi ), standing for “xi takes an abnormal value”. With them, we have the base model of failure: M := B(x1 , x2 , x3 , x4 ; o) ∪ {(¬ab(x1 ) ←→ x1 ), (¬ab(x2 ) ←→ ¬x2 ), (¬ab(x3 ) ←→ x3 ), (¬ab(x4 ) ←→ ¬x4 )},
1
(7)
A deterministic and decomposable Boolean circuit (d-DBC) used in [2]. d-DBCs can encode decision trees, several classes of binary decision diagrams, binary neural networks [10], etc.
9
where the polarity of the variables on the RHSs of the double implications correspond to those in (6). That set in the second disjunct becomes the “observed inputs under normal circumstances”. Depending on the truth values of the ab(xi ) in the double implications, the corresponding values of the associated RHSs, are meant to be the inputs to B(x1 , x2 , x3 , x4 ; o). From this model not much can be obtained: We do not have observations for the classifier, everything is conditional. However, the extended model: T = {¬ab(x1 ), ¬ab(x2 ), ¬ab(x3 ), ¬ab(x4 )} ∪ M ∪ {Ō} (8)
is inconsistent. In fact, under the assumption of normality, the inputs to the circuit becomes as in (6), and then, the circuits evaluates to O = 0, but in T we are requesting the output to be its opposite, i.e. Ō = 1. Now, we can again proceed as in Section 3, obtaining from T diagnoses that contain abnormality propositional atoms. Accordingly, ∆ ⊆ {ab(xi ) | xi ∈ F} is a diagnosis if, changing in T the ¬ab(xi ) into ab(xi ) when ab(xi ) ∈ ∆, restores consistency. Notice that due to the formulas (¬ab(x1 ) ←→ x1 ), etc., declaring ab(xi ) to be true also changes the value of xi to its inverse, which is what we do in actual causality. With ∆ = {ab(x2 )}, that is, changing in T , ¬ab(x2 ) into ab(x2 ), we obtain the new input value x2 = 1, and the obtain B(1, 1, 1, 0; 1), whose output does not collide with the intended one at the very right of (8). ∆ is a diagnosis. ■
Notice that because of these double implications, model M in (7) is not a weak model of failure anymore. Using only left-to-right arrows does not produce the intended changes of input values. If we want a weak model, we could drop the right-to-left arrows, modifying the definition of diagnosis, as follows: ∆ ⊆ {ab(xi ) | xi ∈ F} is a diagnosis if, changing in T the ¬ab(xi ) into ab(xi ) and the associated inputs xi into their inverses, restores consistency. Notice that the method just presented does not need the internals of the classifier, and could be applied with a black-box binary classifier C(x1 , x2 , x3 , x4 ; O).
5
Exploiting Connections
In this section we show and example of how known techniques and results for CBD can be used to investigate applications of actual causality and resposibility. This, in the context of Explainable Data Management, where, more specifically, we want to explain how a Boolean query Q, successfully answered by a database D, becomes true. In this case, we want explanations in terms of which DB tuples contribute to the positive answer, and by how much. The latter is answered by means of an attribution score, which, in our case, turns out to be causal responsibility (for more on the subject and other attribution scores in XDM, see [9]). For illustration purposes, we consider Boolean conjunctive queries, i.e. of the form ¯ 1 (x̄1 ) ∧ · · · ∧ Pn (x̄n )), which is fully existentially quantified. Q : ∃(P 10
Example 9. Consider the database D = {R(c, b), R(a, d), R(b, a), R(e, f ), S(a), S(b), S(c), S(d)}, whose elements are called tuples. Every ground atom written in the language of D’s schema, can be seen as a propositional variable, which is true when τ ∈ D, and false otherwise. Now, the query Q : ∃x∃y(S(x) ∧ R(x, y) ∧ S(y)) becomes true in D; and the join in it can be satisfied with different combinations of tuples in D. For example, by the tuples S(c), R(c, b), S(b). We want to identify the tuples that are actual causes for Q to be true. For example, if S(b) is deleted from D, as an intervention, this particular instantiation of the join becomes false. In more general terms, Q is true in D, and we want to invalidate Q by intervening tuples; here, by deleting tuples (adding tuples to D will not invalidate a conjunctive query). By doing so, we can identify tuples as actual causes. However, instead of tuple interventions in relation to the query at hand, we can reduce the problem to a CBD problem. Since we want invalidate the query, the query is transformed into its negation, which becomes a denial integrity constraint on D, namely, κ : ¬∃x∃y(S(x) ∧ R(x, y) ∧ S(y)), which prohibits the satisfaction of the query join. It holds that Q is satisfied by D iff κ is violated by D, which should be considered the faulty behavior under normal conditions. Accordingly, we specify a weak model of failure: D ∪ {∀x∀y(¬AbS (x)∧¬AbR(x, y) ∧ ¬AbS (y) −→
(9)
((S(x) ∧ R(x, y) ∧ S(y)) → false)}.
The model includes an abnormality predicate for each relational predicate, and an always false propositional atom false. This formula says that when the tuples are not abnormal, they do not participate in the violation of the IC κ. That is, under normality assumptions, the database does not make the query true. Here, the observation is Q itself, which, being true in D, combined with (9) produces an inconsistent theory when the AbS - and AbR-atoms in (9) are all false. According to CBD, for the combinations of S- and R-atoms that make the join true, some of those abnormality atoms have to be true. In particular, at least one of Ab S (c), Ab R (c, b), Ab R (b) has to be true. The tuples whose associated abnormality atoms become true are the actual causes for the query. From the minimal diagnoses that contain a tuple, we can compute minimal contingency sets for it, and eventually, its responsibility. ■ In [4], this kind of reduction from actual causality for QA in DBs to CBD turned out to be useful to obtain algorithmic and complexity results for responsibility in DBs. This was achieved via algorithms based on computing diagnoses as hitting-sets of conflicts in CBD [24];2 and also via results for minimum-size DB repairs for the inconsistency associated to the denial constraints [3, 21]; 2
A conflict in CBD is a set of negative ab-literals whose conjunction is inconsistent with the CBD model plus the observation.
11
minimum-size due to the need for minimum-size contingency sets that underlie responsibility.
6
Conclusions
We have barely started to scratch the surface of the connections between consistency-based diagnosis and actual causality, and their applications to XAI and XDM. The connections are interesting per se, and could be extended in different directions. Going beyond the propositional setting would be interesting, and useful. Related to this, in [6] (see also [9]), the responsibility attribution score was extended to the non-binary case. The extension is not trivial, and deserves more investigation. Similar challenges should appear around a connection to CBD. Several computational techniques and results have been introduced and established in actual causality cum responsibility, on one side, and CBD on the other; following independent paths. For example, it would be interesting to investigate the meaning and applicability of the notion of kernel diagnosis [16] when applied to actual causality. It would also be interesting to investigate its connections to the core of database repairs [11], and closer connections with sufficient (or abductive) explanations [16, sec. 6]. By applying actual causality in a CBD setting, we have been able to use the quantitative responsibility score to identify the most relevant (elements) of diagnoses. It would be interesting to develop algorithms for computing early, or only, highly relevant diagnoses or elements thereof. Such an idea was already proposed in [16, sec. 8], but without relation to responsibility. Instead they propose using additional domain or probabilistic knowledge. This could also be interesting in a setting where responsibility is applied.3 Acknowledgements: L. Bertossi has been financially supported by the IMFD, Chile; and NSERC-DG 2023-04650, Canada.
References [1] Audemard, G., Lagniez, J.-M., Marquis, P. and Szczepanski, N. On the Computation of Example-Based Abductive Explanations for Random Forests. Proc. IJCAI 2024, pp. 3679-3687. [2] Arenas, M., Barcelo, P., Bertossi, L. and Monet, M. On the Complexity of SHAPScore-Based Explanations: Tractability via Knowledge Compilation and NonApproximability Results. J. Mach. Learn. Res., 2023, 24(63):1-58. [3] Bertossi, L. Database Repairing and Consistent Query Answering. Synthesis Lectures in Data Management. Morgan & Claypool, 2011. [4] Bertossi, L. and Salimi, B. From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back. Theory of Computing Systems, 2017, 61(1):191232. 3
For responsibility under database integrity constraints, which goes along these lines, see [5, 8].
12
[5] Bertossi, L. and Salimi, B. Causes for Query Answers from Databases: Datalog Abduction, View-Updates, and Integrity Constraints. Int. J. Approximate Reasoning, 2017, 90:226-252. [6] Bertossi, L., Li, J., Schleich, M., Suciu, D. and Vagena, Z. Causality-Based Explanation of Classification Outcomes. Proc. 4th WS Data Management for EndTo-End Machine Learning (SIGMOD-DEEM), 2020, pp. 6:1-6:10. [7] Bertossi, L. Declarative Approaches to Counterfactual Explanations for Classification. Theory and Practice of Logic Programming, 2023, 23(3):559–593. [8] Bertossi, L. From Database Repairs to Causality in Databases and Beyond. TLDKS, Springer LNCS 14160, 2023, pp. 119-131. [9] Bertossi, L. Attribution-Scores in Data Management and Explainable Machine Learning. Invited tutorial paper in Proc. ADBIS’23, Springer LNCS 13985, 2023, pp. 16-33. [10] Bertossi, L. and León, J. E. Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation. Proc. JELIA’23, Springer LNCS 14281, 2023, pp. 49-64. [11] Bertossi, L. and Pardal, N. Sufficient Explanations in Databases and their Connections to Database Repairs. arXiv paper 2511.15623. [12] Bienvenu, M., Figueira, D. and Lafourcade, P. Shapley Revisited: Tractable Responsibility Measures for Query Answers. Proc. ACM on Management of Data, 2025, 3(2)112, pp. 1–26. [13] Biradar, G., Izza, Y., Lobo, E., Viswanathan, V. and Zick, Y. Axiomatic Aggregations of Abductive Explanations. In Proc. AAAI 2024, 2024. [14] Chockler, H. and Halpern, J. Responsibility and Blame: A Structural-Model Approach. J. Artif. Intell. Res., 2004, 22:93-115. [15] Darwiche, A. Logic for Explainable AI. Proc. LICS 2023, pp. 1-11. [16] de Kleer, J., Mackworth, A. and Reiter, R. Characterizing Diagnoses and Systems. Artif. Intell., 1992, 56(2-3):197-222. [17] Halpern, J. and Pearl, J. Causes and Explanations: A Structural-Model Approach. Part I: Causes. The British Journal for the Philosophy of Science, 2005, 56(4):843-887. [18] Halpern, J. Actual Causality. MIT Press, 2016. [19] Huang, X., Cooper, M. C. Morgado, A., Planes, J. and Marques-Silva, J. Feature Necessity and Relevancy in Machine Learning Explanations. J. Automated Reasoning, 2026, 70(1):4. [20] Janzing, D., Minorics, L. and Blöbaum, P. Feature Relevance Quantification in Explainable AI: A Causal Problem. Proc. 23rd International Conference on Artificial Intelligence and Statistics (AISTATS) 2020, PMLR: Vol. 108. [21] Lopatenko, A. and Bertossi, L. Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Proc. ICDT, 2007, Springer LNCS 4353, pp. 179-193. Extended version in arXiv paper 1605.07159. [22] Meliou, A., Gatterbauer, W., Moore, K. F. and Suciu, D. The Complexity of Causality and Responsibility for Query Answers and Non-Answers. Proc. VLDB 2010, pp. 34-41. [23] Pearl, J. Causality: Models, Reasoning and Inference. Cambridge University Press, 2nd Ed., 2009. [24] Reiter, R. A Theory of Diagnosis from First Principles. Artificial Intelligence, 1987, 32(1):57-95. [25] Schölkopf, B. Causality for Machine Learning. In Probabilistic and Causal Inference: The Works of Judea Pearl, 2022, pp. 765-804.
13
[26] Struss, P. Model-Based Problem Solving. In Handbook of Knowledge Representation, Chap. 4, Elsevier, 2008, pp. 395-465.
14