{'fraction_non_alphanumeric': 0.04597988206729102, 'fraction_numerical': 0.013707943114810961, 'mean_word_length': 4.312596742094788, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 8, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 57, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Declarative Approaches to Counterfactual Explanations for Classification

We propose answer-set programs that specify and compute counterfactual interventions on entities that are input on a classification model. In relation to the outcome of the model, the resulting counterfactual entities serve as a basis for the definition and computation of causality-based explanation scores for the feature values in the entity under classification, namely"responsibility scores". The approach and the programs can be applied with black-box models, and also with models that can be specified as logic programs, such as rule-based classifiers. The main focus of this work is on the specification and computation of"best"counterfactual entities, i.e. those that lead to maximum responsibility scores. From them one can read off the explanations as maximum responsibility feature values in the original entity. We also extend the programs to bring into the picture semantic or domain knowledge. We show how the approach could be extended by means of probabilistic methods, and how the underlying probability distributions could be modified through the use of constraints. Several examples of programs written in the syntax of the DLV ASP-solver, and run with it, are shown.


Introduction
Counterfactual Explanations. Providing explanations to results obtained from machine-learning (ML) models has been recognized as critical in many applications. It has also become an active research direction in explainable ML (Molnar 2020), and the broader area of explainable AI. Explanations become particularly relevant when decisions are automatically made by those models, possibly with serious consequences for stake holders. Since most of those models are algorithms learned from training data, providing explanations may not be easy or possible. These models are or can be seen as black-box models. Even if the components of the models, say their structure, mathematical functions, and parameters, are relatively clear and accessible, characterizing and measuring the relevance of a particular feature value for the classification of an entity may not be that clear from a sheer inspection of the model.
In AI, explanations have been investigated, among other areas, under actual causality (Halpern and Pearl 2005), where counterfactual interventions on a causal structural model are central. They are hypothetical updates on the model's variables, to explore if and how the outcome of the model changes or not. In this way, explanations for an original output are defined and computed. Counterfactual interventions have been used, explicitly or implicitly, with ML models, in particular with classification models (Martens and Provost 2014;Wachter et al. 2017;Russell 2019;Karimi et al. 2020a;Datta et al. 2016;. Counterfactual explanations for query answers from databases have also been investigated (Meliou et al. 2010;Bertossi and Salimi 2017a;Bertossi 2021), an area that is not unrelated to classification results (c.f. Section 4).
In this work we start by introducing and formalizing the notion of counterfactual explanation for the classification of an entity e (think of a finite record of feature values) with a certain label . Counterfactual explanations are alternative versions, e , of e that differ from e by a set of feature values, but are classified with a different label . In this work, "best counterfactual explanations" come in two forms, as sexplanations and c-explanations. The former minimize (under set inclusion) the set of features whose values are changed; while the latter, minimize the number of changed feature values.
Explanation Scores and Responsibility. We use counterfactual explanations to define the x-Resp score, an explanation responsibility score for a feature value of the entity under classification. The idea is to identify and compute the most responsible feature values for the outcome. This score is adapted from the general notion of responsibility used in actual causality (Chockler and Halpern 2004).
More specifically, in this work, we concentrate our interest mostly and mainly on specifying and computing, for a given and fixed classified entity e, all the best explanations as represented as counterfactual entities (that have feature values changed and a different label), where "best" for a counterfactual entity means that the number of changes of feature values (with respect to e) takes a minimum value (the c-explanations mentioned above). At the same time, we are also interested in the maximum-responsibility feature values. These two goals are directly related: The maximum-responsibility feature values (in the original entity e) are exactly those that appear as changed in a best counterfactual entity.
The x-Resp score belongs to the family of feature attribution scores, among which one finds the popular Shap score (Lundberg et al. 2020). While Shap is based on the Shapley value that is widely used in game theory, the x-Resp score is based on actual causality. Experimental results with an extended version (that we briefly describe) of the responsibility score investigated in this work, and comparisons with other scores, in particular, with Shap, are reported in ). However, (Shi et al. 2020;Shih et al. 2018;Choi et al. 2020;Narodytska et al. 2010), opening the possibility of specifying them by means of ASPs.
Answer-Set Programming and Semantic Knowledge. Our declarative approach to counterfactual interventions is particularly appropriate for bringing into the game additional, declarative, semantic knowledge. As we show, we could easily adopt constraints when computing counterfactual entities and scores. In particular, these constraints can be used to concentrate only on actionable counterfactuals (as defined by the constraint). In the loan example, we could omit counterfactual entities or explanations that require from the applicant to reduce his/her age. Imposing constraints in combination with purely procedural approaches is much more complicated. In our case, we can easily and seamlessly integrate logic-based semantic specifications with declarative programs, and use the generic and optimized solvers behind ASP implementations. In this work we include several examples of CIPs specified in the language of the DLV system (Leone et al. 2006) and its extensions, and run on them.
We establish that ASPs are the right declarative and computational tool for our problem since they can be used to: (a) Compute all the counterfactual explanations, in particular, the best ones. (b) Provide through each model of the program all the information about a particular counterfactual explanation. (c) Compute maximum-responsibility scores and the counterfactual explanations associated to them. (d) In many cases, specify as a single program the classifier together with the explanation machinery. (d) Alternatively, call a classifier from the program as an external predicate defined in, say Python. (e) Bring into the picture additional, logic-based knowledge, such as semantic and actionability constraints. (f) Do query answering, under the skeptical and brave semantics, to analyze at a higher level the outcomes of the explanation process. Furthermore, and quite importantly, the ASPs we use match the intrinsic data complexity of the problem of computing maximum-responsibility feature values, as we will establish in this work.
We discuss why and how the responsibility score introduced and investigated early in this work has to be extended in some situations, leading to a generalized probabilistic responsibility score introduced in . After doing this, we show how logical constraints that capture domain knowledge can be used to modify the underlying probability distribution on which a score is defined.
Article Structure and Contents. This paper is structured as follows. In Section 2 we provide background material on classification models and answer-set programs. In Section 3 we introduce counterfactual interventions and the responsibility score. In Section 4, we investigate the data complexity of the computation of maximumresponsibility feature values. In Section 5 we introduce and analyze the CIPs. In Section 6, we consider some extensions of CIPs that can be used to capture additional domain knowledge. In Section 7, and for completeness, we briefly motivate and describe the probabilistic responsibility score previously introduced in . In this regard, we also show how to bring logical constraints into the probabilistic setting of the responsibility score. In Section 8, the discuss related work. In Section 9, we conclude with a discussion and concluding remarks.
This paper is an extended version of the conference paper . This current version, in addition to improving and making more precise the presentation in comparison with the conference version, includes a considerable amount of new material. Section 2, containing background material, is new. In particular, it contains a new example of a decision-tree classifier that is used as an additional running example throughout the paper. Section 4 on the complexity of x-Resp computation is completely new, so as Section 5.2 that retakes complexity at the light of CIPs. This version also contains several examples of the use of the DLV system for specifying and running CIPs. There were no such examples in the conference version. Section 7 is new. It contains two subsections; the first dealing with non-binary features and the need to extend in probabilistic terms the definition of the x-Resp score; and the second, with the combination of probabilistic uncertainty and domain knowledge. We now have the new Section 8 on related work. The final Section 9 has been considerably revised and extended.

Classification models and counterfactuals
In a particular domain we may have a finite set F = {F 1 , . . . , F n } of features (a.k.a. as variables). More precisely, the features F i are functions that take values in their domains Dom(F i ). 1 As is commonly the case, we will assume that these domains are categorical, i.e. finite and without any a priori order structure. These features are used to describe or represent entities in an underlying population (or application domain), as records (or tuples) e formed by the values the features take on the entity. Actually, with a bit of abuse of notation, we represent entities directly as these records of feature values: e = F 1 (e), . . . , F n (e) . A feature F is said to be Boolean or propositional if Dom(F ) = {true, false}, for which we sometimes use {yes, no} or simply, {1, 0}.
A classifier, C, for a domain of entities E is a computable function C : E → L, where L = { 1 , . . . , k } is a set of labels. We classify the entity by assigning a label to it. We do not have to assume any order structure on L. In the example above, we may want to classify entities in the people's population according to how appropriate they are for military service. The set of labels could be L = {good, maybe, noway}, then the classifier could be such, that C( fit, young, false, top ) = good, but C( overweight, old, true, low ) = noway. When the set of labels has two values, typically, {yes, no}, we have a binary or Boolean classifier. In this work we will consider mostly binary classifiers.
Example 2.1 This is a popular example taken from (Mitchell 1997). Consider the set of features F = {Outlook, Humidity, Wind}, with Dom(Outlook) = {sunny, overcast, rain}, Dom(Humidity) = {high, normal}, Dom(Wind) = {strong, weak}. An entity under classification has a value for each of the features, e.g. e = ent(sunny, normal, weak). The problem is about deciding about playing tennis or not under the conditions represented by that entity, which can be captured as a classification problem, with labels yes or no (sometimes we will use 1 and 0, resp.). from that node corresponds to one of the possible values for this attribute. An instance is classified by starting at the root node of the tree, testing the attribute specified by this node, then moving down the tree branch corresponding to the value of the attribute in the given example. This process is then repeated for the subtree rooted at the new node. Figure 3.1 illustrates a typical learned decision tree. This decision tree classifies Saturday mornings according to whether they are suitable for playing tennis. For example, the instance (Outlook = Sunny, Temperature = Hot, Humidity = High, Wind = Strong) would be sorted down the leftmost branch of this decision tree and would therefore be classified as a negative instance (i.e., the tree predicts that PlayTennis = no). This tree and the example used in Table 3.2 to illustrate the ID3 learning algorithm are adapted from (Quinlan 1986).
In general, decision trees represent a disjunction of conjunctions of constraints on the attribute values of instances. Each path from the tree root to a leaf corresponds to a conjunction of attribute tests, and the tree itself to a disjunction of these conjunctions. For example, the decision tree shown in Figure 3.1 corresponds to the expression

Fig. 1. A Decision Tree
The Boolean classifier is given as a decision-tree, as shown in Figure 1. The decision is computed by following the feature values along the branches of the tree. The entity e at hand gets label yes. 2 Of course, a decision tree could be just arbitrarily given, but the common situation is to learn it from training examples, that is from a collection of entities that come already with an assigned label. In more general terms, building a classifier, C, from a set of training data, i.e. a set of pairs T = { e 1 , (e 1 ) , . . . , e M , (e M ) }, with (e i ) ∈ L, is about learning a (computational) model for the label function L for the entire domain of entities, beyond T . We say that L "represents" the classifier C. This supervised learning task is one of the most common in machine learning. (C.f. (Mitchell 1997) or (Flach 2012) for great introductions to the subject.) Classifiers may take many different internal forms. They could be decision trees, random forests, rule-based classifiers, logistic regression models, neural network-based classifiers, etc.
In this work we are not concerned with learning classifiers. We will assume the classifier is given as an input/output computable relation, or that we know how to specify it, for example, trough a logic program. By the same token, we are not dealing here with any kind of program learning. Some classes of classifiers are more "opaque" than others, i.e. with a more complex and less interpretable internal structure and results (Molnar 2020). Hence, the need for explaining the classification outcomes. The decision tree above is clearly a computable function. Since we have the classifier at hand with an explicit and clear specification, we would consider this classifier to be interpretable. In this direction, if we obtain a label for a particular entity at hand, we can inspect the model and explain why we obtained that label, and we could identify the feature values that were relevant for the outcome.
Instead of a decision tree as above, we could have, for example, a very complex neural network. Such a model would be much more difficult to interpret, or use to explain why we got a particular output for a particular input. This kind of models are considered to be black-box models (or al least, opaque) (Rudin 2019).
Assume for a moment that we do not have the explicit classifier in Example 2.1, but we interact only with the box that contains it. We input entity e = ent(sunny, normal, weak), and we obtain the output yes. We want to know what are the feature values in e that influenced the outcome the most. Actually, we want to get a numerical score for each of the entity's feature values, in such a way that the higher the score, the more relevant is the feature value for the outcome.
Different scores may be defined. A popular one is Shap (Lundberg et al. 2020), which has been investigated in detail for some classes of classifiers (Arenas et al. 2021; Van den Broeck et al. 2021). In this work we concentrate on x-Resp, a responsibility score that was introduced, in a somewhat ad hoc manner, in . In this work, we present x-Resp in a causal setting, on the basis of counterfactual interventions and their responsibilities, following the general approach to causal responsibility in (Chockler and Halpern 2004).
Just for the gist, and at the light of the example at hand, we want to detect and quantify the relevance (technically, the responsibility) of a feature value in e = ent(sunny, normal, weak), say for feature Humidity (underlined), by hypothetically intervening its value; in this case, changing it from normal to high, obtaining a new entity e = ent(sunny, high, weak), a counterfactual version of e. If we input this entity into the classifier, we now obtain the label no. This is an indication that the original feature value for Humidity is indeed relevant for the original classification. Through numerical aggregations over the outcomes associated to the alternative, counterfactually intervened entities, we can define and compute the x-Resp score. The details can be found in Section 3. As mentioned in Section 1, these counterfactual entities are also interesting per se, and not only as a basis for the definition and computation of feature attribution scores.

Answer-set programming
As customary, when we talk about answer-set programs, we refer to disjunctive Datalog programs with weak negation and stable model semantics (Gelfond and Lifschitz 1991). Accordingly, an answer-set program Π consists of a finite number of rules of the form where 0 ≤ n, m, k , and A i , P j , N s are (positive) atoms, i.e. of the form Q(t), where Q is a predicate of a fixed arity, say, , andt is a sequence of length of variables or constants. In rule (1), A 1 , . . . , notN k are called literals, with A 1 positive, and notN k , negative. All the variables in the A i , N s appear among those in the P j . The left-hand side of a rule is called the head, and the right-hand side, the body. A rule can be seen as a (partial) definition of the predicates in the head (there may be other rules with the same predicates in the head). The constants in program Π form the (finite) Herbrand universe H of the program. The ground version of program Π, gr(Π), is obtained by instantiating the variables in Π in all possible ways using values from H . The Herbrand base, HB, of Π contains all the atoms obtained as instantiations of predicates in Π with constants in H .
A subset M of HB is a model of Π if it satisfies gr(Π), i.e.: For every ground rule it is a model of Π, and Π has no model that is properly contained in M . M M (Π) denotes the class of minimal models of Π. Now, for S ⊆ HB(Π), transform gr(Π) into a new, positive program gr(Π) S (i.e. without not), as follows: Delete every rule A 1 ∨. . .∨A n ← P 1 , . . . , P m , notN 1 , . . . , notN k for which {N 1 , . . . , N k }∩S = ∅. Next, transform each remaining rule A 1 ∨ . . . ∨ A n ← P 1 , . . . , P m , notN 1 , . . . , notN k into A 1 ∨ . . . ∨ A n ← P 1 , . . . , P m . Now, S is a stable model of Π if S ∈ M M (gr(Π) S ). Every stable model of Π is also a minimal model of Π. Stable models are also commonly called answer sets, and so are we going to do most of the time.
A program is unstratified if there is a cyclic, recursive definition of a predicate that involves negation. For example, the program consisting of the rules a ∨ b ← c, notd ; d ← e, and e ← b is unstratified, because there is a negation in the mutually recursive definitions of b and e. The program in Example 2.2 below is not unstratified, i.e. it is stratified. A good property of stratified programs is that the models can be upwardly computed following strata (layers) starting from the facts, that is from the ground instantiations of rules with empty bodies (in which case the arrow is usually omitted). We refer the reader to (Gelfond and Kahl 2014) for more details.
Query answering under the ASPs comes in two forms. Under the brave semantics, a query posed to the program obtains as answers those that hold in some model of the program. However, under the skeptical (or cautious) semantics, only the answers that simultaneously hold in all the models are returned. Both are useful depending on the application at hand.
We will use disjunctive programs. However, sometimes it is possible to use instead normal programs, which do not have disjunctions in rule heads, and with the same stable models, in the sense that disjunctive rules can be transformed into a set of non-disjunctive rules. More precisely, the rule in (1) can be transformed into the rules: A 1 ← P 1 , . . . , P m , notN 1 , . . . , notN k , notA 2 , . . . , notA n · · · A n ← P 1 , . . . , P m , notN 1 , . . . , notN k , notA 1 , . . . , notA n−1 · This shift operation is possible if the original program is head-cycle free (Ben-Eliyahu and Dechter 1994; Dantsin et al. 2001), as we define now. The dependency graph of a program Π, denoted DG(Π), is a directed graph whose nodes are the atoms of the associated ground program gr(Π). There is an arc from L 1 to L 2 iff there is a rule in gr(Π) where L 1 appears positive in the body and L 2 appears in the head. Π is head-cycle free (HCF) iff DG(Π) has no cycle through two atoms that belong to the head of a same rule.

Example 2.2
Consider the following program Π that is already ground.
The program has two stable models: Each of them expresses that the atoms in it are true, and any other atom that does not belong to it, is false.
These models are incomparable under set inclusion, and they are minimal models in that any proper subset of any of them is not a model of the program.

Fig. 2. Dependency graph DG(Π)
The dependency graph is shown in Figure 2. We can see that the program Π is head-cycle free, because there is no cycle involving both a and b, the atoms that appear in the disjunctive head. As a consequence, the program can be transformed into the following non-disjunctive program This program has the same stable models as the original one. 2 We will return to HCF-programs in Section 5.2.

Counterfactual Explanations and the x-Resp Score
We consider classification models, C, that are represented by an input/output relation. Inputs are the so-called entities, e, which are represented as records, The entities form a population E. The output of a classifier is represented by a label function L that maps entities e to 0 or 1, the binary result of the classification. That is, to simplify the presentation, we concentrate here on binary classifiers, but this is not essential. Furthermore, we consider domains Dom(F i ) with a finite number of categorical values.
In this work, we are not assuming that we have an explicit classification model, and we do not need it. All we need is to be able to invoke it. It could be a "blackbox" model.
The problem is the following: Given an entity e that has received the label L(e), provide an "explanation" for this outcome. In order to simplify the presentation, and without loss of generality, we assume that label 1 is the one that has to be explained. It is the "negative" outcome one has to justify, such as the rejection of a loan application.
Counterfactual explanations are defined in terms of counterfactual interventions that simultaneously change feature values in e, in such a way that the updated record gets a new label. A counterfactual explanation for the classification of e is, then, an alternative entity e that is classified with a label different from that of e. In general, we are interested in counterfactual explanations that are more informative about the role of the feature values in e, which lead to its obtained label. These are the entities that are obtained from e through a minimal counterfactual interventions. Minimality can be defined in different ways, and we adopt an abstract approach, assuming a partial order relation on counterfactual interventions.
Definition 3.1 Consider a binary classifier represented by its label function L, and a fixed input entity e = x 1 , . . . , x n , with F i (e) = x i , 1 ≤ i ≤ n, and L(e) = 1.
. We denote withι(e) the record obtained by applying to e interventionι, i.e. by replacing in e every x is = F is (e), with F is appearing inι, by x is . (b) A counterfactual intervention on e is an interventionι on e, such that L(ι(e)) = 0. The resulting entity e =ι(e) is called a counterfactual entity (for e).
(e) A counterfactual explanationˆ for L(e) is -minimal if its associated counterfactual interventionι(ˆ ) is a -minimal counterfactual intervention on e. 2 Remark 3.1 Counterfactual explanations contain feature values of the original entity e. They contain relevant information about the classification result, and interventions are used to characterize and identify them. For this reason, we will usually call an alternative entity e obtained from e through a counterfactual intervention, a counterfactual explanation as well: The counterfactual explanation in the sense of Definition 3.1(d) can be read-off from e . 2 Several minimality criteria can be expressed in terms of partial orders. We will explicitly consider two of them.
This definition introduces minimality under set inclusion and cardinality, resp. The former minimizes -under set inclusion-the set of features whose values are changed. The latter, the number of features that see their values changed. In the following, we will consider only these minimality criteria, mostly the second (c.f. Section 9 for a discussion).
Example 3.1 Consider three binary features F = {F 1 , F 2 , F 3 }, i.e. they take values 0 or 1. The input/output relation of a classifier C is shown in Table 1. Let e be e 1 in the table.
We want counterfactual explanations for its label 1. Any other record in the table can be seen as the result of an intervention on e 1 . However, only e 4 , e 7 , e 8 are (results of) counterfactual interventions in that they switch the label to 0. entity (id) F 1 F 2 F 3 L e 1 0 1 1 1 e 2 1 1 1 1 e 3 1 1 0 1 e 4 1 0 1 0 e 5 1 0 0 1 e 6 0 1 0 1 e 7 0 0 1 0 e 8 0 0 0 0 Table 1: Classifier C For example, e 4 corresponds to the interventionι 4 = { F 1 , 1 , F 2 , 0 }, in that e 4 is obtained from e 1 by changing the values of F 1 , F 2 into 1 and 0, resp. For telling us that the values F 1 (e 1 ) = 0 and F 2 (e 1 ) = 1 are the joint cause for e 1 to be classified as 1.
There are three counterfactual explanations: Here, e 4 and e 8 are incomparable under s , e 7 ≺ s e 4 , e 7 ≺ s e 8 , andˆ 7 turns out to be s -and c -minimal (actually, minimum). 2 Notice that what matters here is what is intervened, and not how. By taking a projection, the partial order s does not care about the values that replace the original feature values, as long as the latter are changed. Furthermore, given e, it would be good enough to indicate the features whose values are relevant, e.g.ˆ 7 = {F 2 } in the previous example. However, the introduced notation emphasizes the fact that the original values are those we concentrate on when providing explanations.
Every c -minimal explanation is also s -minimal. However, it is easy to produce an example showing that a s -minimal explanation may not be c -minimal.
Notation: An s-explanation for L(e) is a s -minimal counterfactual explanation for L(e). A c-explanation for L(e) is a c -minimal counterfactual explanation for L(e). So as prescribed in Remark 3.1, we will usually use the terms s-explanation and c-explanation to refer to the alternative, intervened entities e that are associated to s-and c-explanations in the sense of Definition 3.2. 2 So far, we have characterized explanations as sets of (interventions on) features. However, one would also like to quantify the "causal strength" of a single feature value in a record representing an entity. Something similar has been done for a single tuple in a database as a cause for a query answer (Meliou et al. 2010), or for a single attribute value in a database tuple (Bertossi and Salimi 2017a;Bertossi 2021). Different scores for feature values have been proposed in this direction, e.g. Shap in (Lundberg et al. 2020) and Resp in . Following (Chockler and Halpern 2004), we will now formulate the latter as the responsibility of a feature value as an actual cause (Halpern and Pearl 2005) for the observed classification.

Definition 3.3
Consider an entity e represented as a record of feature values The explanatory responsibility of a value-explanation v = F (e) is: Adopting the terminology of actual causality (Halpern and Pearl 2005), a counterfactual value-explanation for e's classification is a value-explanation v with x-Resp e,F (v ) = 1. That is, it suffices, without company from other feature values in e, to explain the classification. Similarly, an actual value-explanation for e's classification is a value-explanation v with x-Resp e,F (v ) > 0. That is, v appears in an s-explanationˆ , say as F , v , but possibly in company of other feature values. In this case,ˆ { F , v } is a contingency set for v (c.f. (Halpern and Pearl 2005), and (Meliou et al. 2010) for the case of databases).
Example 3.2 (example 3.1 continued)ˆ 7 , equivalently entity e 7 , is the only c-explanation for e 1 's classification. Its value 1 for F 2 is a counterfactual value-explanation, and its explanatory responsibility is x-Resp e1,F2 (1) := 1. The empty set is its contingency set. Now, entity e 4 shows that the intervened value for F 2 , i.e. 1, needs { F 1 , 0 } as contingency set for the label to switch to 0. 2 In this work we are interested mostly in c-explanations, which are our best explanations, and in maximum-responsibility feature values. Notice that maximum x-Resp scores can be obtained by concentrating only on c-explanations. Maximumresponsibility value-explanations appear in c-explanations, and only in them. C.f. Section 9 for considerations on s-explanations and features with non-maximum responsibility scores.

Complexity of x-Resp Computation
A natural question is about the complexity of computing the x-Resp score. Not only for the obvious reason of knowing the complexity, but also to determine if the ASPbased approach we will present is justified from the complexity point of view. We can shed some light on this matter by taking advantage of complexity results for actual causality in databases (Meliou et al. 2010;Bertossi and Salimi 2017a). It is known that there are Boolean Conjunctive Queries (BCQs), Q, for which deciding if the responsibility of a tuple for Q being true in a database D is above a given threshold is NP -complete, in the size of D (Bertossi and Salimi 2017a).
In our case, given a fixed classifier C, the computational problem is about deciding, for an arbitrary entity e and rational number v , if x-Resp(e ) > v . The complexity is measured as a function of |e |, the size M of cartesian product of the the underlying domains, and the complexity of computing C. (Under our ASP-based approach, M will be associated to the extensional database for the program.) Given a relational database schema S = {R 1 , . . . , R k }, with predicates with arities ar(R i ), we can see each attribute A as a feature that takes values in a finite domain Dom(A). Without loss of generality, we assume the predicates R i do not share attributes (but attributes may share a same domain). Then, we have a sequence of attributes Now, define a binary entity e = F (τ j ) τj ∈D . This entity, containing only 1s, represents the contents of database D, and its length coincides with the number of tuples in D, say |D|. Now, the population of entities is E = {1, 0} |D| , i.e. all the binary sequences with the same length as e . Intuitively, each entity in E represents a sub-instance D e of D, by keeping only the tuples of D that are assigned the value 1. We do not need to consider the insertion of tuples in D, as will be clear soon.
Now, given the fixed BCQ Q, for which D |= Q, define a binary classifier C Q as follows: For e ∈ E , C Q (e) := 1 iff D e |= Q. Notice that this classifier runs in polynomial-time in the length of e. Also, C Q (e ) = 1. The monotonicity of Q allows us to concentrate on sub-instances of D. Only subinstances can invalidate the query, and superinstances will always make it true. In this way, we have reduced the problem of computing the responsibility of a tuple τ j as an actual cause for D |= Q to the problem of computing x-Resp e ,Fj (1).

Theorem 1
There is a binary polynomial-time classifier C over a finite set of binary entities E for which deciding if x-Resp e,F (v ) is above a certain threshold is NP -complete in the size of e plus the size of E. 2 So as in (Bertossi and Salimi 2017a), several other problems in relation to responsibility can be investigated; and it is likely that most (if not all) the results in (Bertossi and Salimi 2017a) can be used to obtain similar results for the x-Resp score.

Counterfactual Intervention Programs
An answer-set program has a possible-world semantics, given in terms of its stable models, which are the intended models of the program (Gelfond and Kahl 2014). A program consists of a set of rules with variables, possibly with negated atoms in a rule body (antecedent) and disjunctions in the head (consequent). This negation is non-monotonic, which is particulary useful for doing commonsense reasoning and specifying persistence of properties. A program has an extensional database consisting of ground atoms (the facts). In our case, the facts will be related to the entity under classification for whose label we want counterfactual explanations. The program specifies the possible interventions. Final, intervened versions of the original entity, that have their label switched, correspond to different stable models of the program.
Entities will be represented by means of a predicate with n + 2 arguments E (·; · · · ; ·). The first one holds a record (or entity) id (which may not be needed when dealing with single entities). The next n arguments hold the feature values. 2 The last argument holds an annotation constant from the set {o, do, , s}. Their semantics will be specified below, by the generic program that uses them.
Initially, a record e = f 1 , . . . , f n has not been subject to interventions, and the corresponding entry in predicate E is of the form E (e,f , o), where e is (with a bit of abuse of notation) a constant used a an entity identifier,f is an abbreviation for f 1 , . . . , f n , i.e. the feature values for entity e; and the annotation constant "o" stands for "original entity".
When the classifier gives label 1 to e, the idea is to start changing feature values, one at a time. The intervened entity becomes then annotated with constant do in the last argument. 3 When the resulting intervened entities are classified, we may not have the classifier specified within the program. For this reason, the program uses a special predicate C(· · · , ·), where the first arguments take the feature values of an entity under classification, and the last argument returns the binary label. This predicate can be explicitly given as a set of facts (c.f. Example 5.1), or can be specified within the program (c.f. Example 5.7), or can be invoked by the program as an external predicate (c.f. Example 5.8), much in the spirit of HEX-programs (Eiter et al. 2019;Eiter et al. 2017). Since the original instance may have to go through several interventions until reaching one that switches the label to 0, the intermediate entities get the "transition" annotation . This is achieved by a generic program.

Counterfactual intervention programs
The generic Counterfactual Intervention Program (CIP) is as follows: P1. The facts of the program are the atoms of the form Dom i (c), with c ∈ Dom i , plus the initial entity E (e,f , o), withf the initial vector of feature values. P2. The transition entities are obtained as initial, original entities, or as the result of an intervention. Here, e is a variable standing for a record id.
P3. The program rule specifying that, every time the entity at hand (original or obtained after a "previous" intervention) is classified with label 1, a new value has to be picked from a domain, and replaced for the current value. The new value is chosen via the non-deterministic "choice operator", well-known in ASP (Giannotti et al. 1997). In this case, the values are chosen from the domains, subject to the condition of not being the same as the current value: E (e, x 1 , x 2 , . . . , x n , do) ∨ · · · ∨ E (e, x 1 , x 2 , . . . , x n , do) ←− E (e,x , ), C(x , 1), In general, for each fixedx , choice(x , y) chooses a unique value y subject to the other conditions in the same rule body. The use of the choice operator can be eliminated by replacing each choice(x , x i ) atom by the atom Chosen i (x , x i ), and defining each predicate Chosen i by means of "classical" rules (Giannotti et al. 1997), as follows: 4 P4. The following rule specifies that we can "stop", hence annotation s, when we reach an entity that gets label 0: We add a em program constraint specifying that we prohibit going back to the original entity via local interventions: The counterfactual explanations can be collected by means of a predicate Expl(·, ·, ·) specified by means of: with i = 1, . . . , n. They collect each value that has been changed in the original instance e, with its position in e (the second argument of the predicate). Actually, each of these is a value-explanation. 2 The program will have several stable models due to the disjunctive rule and the choice operator. Each model will hold intervened versions of the original entity, and hopefully versions for which the label is switched, i.e. those with annotation s. If the classifier never switches the label, despite the fact that local interventions are not restricted, we will not find a model with a version of the initial entity annotated with s. Due to the constraint in P5., none of the models will have the original entity annotated with do, because those models would be discarded (Leone et al. 2006). The definition of the choice operator contains non-stratified negation. The semantics of ASP, which involves model minimality, makes only one of the atoms in a head disjunction true (unless forced otherwise by the program).
From rule P6., we obtain explanations Expl(e 1 , 1, 0), Expl(e 1 , 2, 1), showing the changed values in e 1 . All this in model M 1 . There are other models, and one of them contains E (e 1 , 0, 0, 1, s), the minimally intervened version of e 1 , i.e. e 7 . 2 In the next example we will show how to write and run the counterfactual intervention program for Example 3.1 with the DLV system (Leone et al. 2006). 5 When numerical aggregations and, specially, set operations are needed, we use instead the DLV-Complex system (2009 ) (c.f. Section 9). In Example 5.8 we show a program that can be used with the newer version, DLV2 (Alviano et al. 2017;Alviano et al. 2019), of DLV, which follows the ASP-Core-2 standard (Calimeri et al. 2020).
Notice that the program, except for the fact ent(e,0,1,1,o) in the 10th line, is completely generic, and can be used with any input entity that has been classified with label 1. 6 We could remove it from the program, obtaining program theProgram2.txt, and we could run instead C:\DLV>dlv.exe ent.txt program2.txt > outputFile.txt where ent.txt is the file containing only ent(e,0,1,1,o). . 2 In the previous example, the classifier was given as an input/output relation, that is, as a set of facts inserted directly in the program. In other situations, we may have the classifier invoked from the program as an external predicate. In others, the classifier can be specified directly in the program, as shown in Example 2.1.
Our CIPs compute all the counterfactual versions (or counterfactual explanations) of the original entity e. Each counterfactual version is represented (or characterized) by at least one of the stable models of the CIP; one that contains the counterfactual version of e annotated with "s". There may be more that one stable model associated to a counterfactual version e due to the use of the choice operator. Different choices may end up leading to the same e .
The counterfactual explanations obtained through the CIP are not necessarily s-explanations or c-explanations (c.f. Section 3), as Example 5.2 shows. The CIPs presented so far have (only) minimal models with respect to set-inclusion of the extensions of full predicates, whereas when we compare explanations, we do it at the "attribute (or feature, or argument) level". Of course, s-explanations and c-explanations are all included among the counterfactual explanations, and are represented by stable models of the CIP. We will consider this point in Section 5.3.
Example 5.3 (example 3.1 continued) To show the different kinds of counterfactual versions of an original entity, let us change the classifier we had before by the one shown in Table 2. entity (id) F 1 F 2 F 3 L e 1 0 1 1 1 e 2 1 1 1 1 e 3 1 1 0 0 e 4 1 0 1 1 e 5 1 0 0 0 e 6 0 1 0 1 e 7 0 0 1 0 e 8 0 0 0 1 The changed values appear underlined. In this case, we have three counterfactual versions: (a) e 7 that is cexplanation. Only one value is changed to switch the label to 0. (b) e 3 is an s-explanation, but not a c-explanation. It shows two changes, but not the one for e 7 . (c) e 5 is neither an s-nor a cexplanation. Its changes include those for e 7 and those for e 3 .
The CIP we have so far would return the three of them. With the additional elements for CIP programs to be introduced in Section 5.3, we will be able to obtain only c-explanations. In Section 9, we briefly discuss the case of s-explanations (that may not be c-explanations). 2

Complexity of CIPs
The complexity result obtained in Section 4 makes us wonder whether using ASPprograms for specifying and computing the x-Resp score is an overkill, or, more precisely, whether they have the right and necessary expressive power and complexity to confront our problem. In fact they do. It is known that reasoning with disjunctive answer-set programs (DASP) falls in the second level of the polynomial hierarchy (in data complexity) (Dantsin et al. 2001), and slightly above that by the use of weak constraints (Leone et al. 2006) that we will use in Section 5.3. However, CIPs have the property of being head-cycle free (HCF), which brings down the complexity of a DASP to the first level of the polynomial hierarchy (Dantsin et al. 2001). This is in line with the result in Theorem 1. It is easy to check that CIPs are HCF (c.f. Section 2): The ground chains in the directed graph DG(Π) associated to a CIP Π are, due to rules P2. and P3., of the form: E (e,ā, do) → E (e,ā, ) → E (e,ā , do), withā =ā . They never create a cycle in the head of a ground instantiation of the disjunctive rule. One can also see the HCF property from the fact that the CIPs become repairprograms (Bertossi 2011) for a database w.r.t. the integrity constraint, actually denial constraint, ∀e∀x ¬(E (e,x ) ∧ C(x , 1)). Denial constraints are common in databases, and their repairs and repair-programs have been investigated (Caniupan and Bertossi 2010;Bertossi 2021). C.f. (Bertossi 2011) for additional references.
As a consequence of being HCF, a CIP can be transformed, by means of the shift operation, into an equivalent non-disjunctive ASP (c.f. Section 2). The resulting program has the same answer-sets as the original program. 2

C-explanations and maximum responsibility
As discussed at the end of Section 5.1, an intervened entity of the form E (e, c 1 , . . . , c n , s), that is, representing a counterfactual explanation, may not correspond to an s-or a c-explanation. We are interested in obtaining the latter, and only them, because: (a) They are our "best explanations", and (b) They are used to define and compute the maximum x-Resp scores.
Moving towards computing x-Resp scores, notice that in each of the stable models M of the CIP, we can collect the corresponding counterfactual explanation for e's classification as the setˆ This can be done within a ASP system such as DLV, which allows set construction and aggregation, in particular, counting (Leone et al. 2006). Actually, counting comes handy to obtain the cardinality ofˆ M , by means of: As before, we obtain three models, and each of them shows, in the last atom, the number of changes that were made to obtain the corresponding counterfactual explanation. For example, for the last model, say M 3 , corresponding to entity e 4 , we obtain m(M 3 ) = 2. Similarly for the second one, corresponding to entity e 8 . The first model corresponds to the counterfactual entity e 7 that is a c-explanation, which is shown by the minimum value "1" that predicate inResp takes in its second argument among all the stable models.
We can see that the first model is the one corresponding to a maximum responsibility feature value. 2 In order to obtain only the models associated to c-explanations, we add weak program constraints to the CIP. They can be violated by a stable model of the program (unlike strong program constraints), but the number of violations has to be minimized. In this case, for 1 ≤ i ≤ n, we add to the CIP: 7 Only the stable models representing an intervened version of e with a minimum number of value discrepancies with e will be kept.
Let us now add, at the end of the program the following weak constraints (labeled with (*)): If we run the program with them, the number of changes is minimized, and we basically obtain only the first model above, corresponding to the counterfactual entity e = ent(sunny, high, weak). 2 As can be seen at the light of this example, more complex rule-based classifiers could be defined inside a CIP. It is also possible to invoke the classifier as an external predicate, as the following example shows.
Example 5.8 (example 5.7 continued) The program below calls the classifiers through a predicate that has an external extension, as defined by a Python program. The program has the same facts and the same rules as the the program in Example 5.7, except for a new rule that defines the classification predicate, cls here (and C in the general formulation in Section 5.1), and replaces the internal specification of the classifier: Here, the atom &classifier(X,Y,Z;L) corresponds to the invocation of the external classifier with parameters X,Y,Z, which gets an external value through variable L. The program was run with the version of DLV2 for Linux that supports interaction with Python, and can be downloaded from: https://dlv.demacs.unical.it/publications#h.cgg9mbi41jq9 The program in Python that specifies the classifier is very simple, and it can be invoked in combination with DLV2, as follows: sudo ./dlv2-python-linux-x86_64 program_dlv2.txt def_class.py. Here, program_dlv2.txt is the CIP, and def_class.py is the very simple Python program that specifies the classifier, namely def classifier(X,Y,Z): if (X == "sunny") and (Y == "normal"): return 1 if (X == "overcast"): return 1 if (X == "rain") and (Z == "weak"): return 1 else: return 0 We obtain as answer-set the first one in Example 5.7. 2

Semantic Knowledge
Counterfactual interventions in the presence of semantic conditions requires consideration. As the following example shows, not every intervention, or combination of them, may be admissible (Bertossi and Geerts 2020). In these situations declarative approaches to counterfactual interventions become particularly useful.
Example 6.1 A moving company makes automated hiring decisions based on feature values in applicants' records of the form R = appCode, ability to lift, gender, weight, height, age . Mary, represented by R = 101, 1, F , 160 pounds, 6 feet, 28 applies, but is denied the job, i.e. the classifier returns: L(R ) = 1. To explain the decision, we can, hypothetically, change Mary's gender, from F into M , obtaining record R , for which we now observe L(R ) = 0. Thus, her value F for gender can be seen as a counterfactual explanation for the initial decision.
As an alternative, we might keep the value of gender, and counterfactually change other feature values. However, we might be constrained or guided by an ontology containing, e.g. the denial semantic constraint ¬(R[2] = 1 ∧ R[6] > 80) (2 and 6 indicating positions in the record) that prohibits someone over 80 to be qualified as fit for lifting weight. We could also have a rule, such as (R[3] = M ∧ R[4] > 100 ∧ R[6] < 70) → R[2] = 1, specifying that men who weigh over 100 pounds and are younger than 70 are automatically qualified to lift weight.
In situations like this, we could add to the CIPs we had before: (a) program constraints that prohibit certain models, e.g. ←− R(e, x , 1, y, z , u, w , ), w > 80; (b) additional rules, e.g.
R(e, x , 1, y, z , u, w , ) ←− R(e, x , y, M , z , u, w , ), z > 100, w < 70, that may automatically generate additional interventions. In a similar way, one could accommodate certain preferences using weak program constraints. 2 Causality and responsibility in databases in the presence of integrity constraints was introduced and investigated in (Bertossi and Salimi 2017b).
Example 6.2 (example 5.7 continued) It might be the case that in a particular region, some combinations of weather conditions are never possible, e.g. raining with a strong wind at the same time. When producing counterfactual interventions for the entity e, such a combination should be prohibited. This can be done by imposing a hard program constraint, that we add to the program in Example 5.7: % hard constraint disallowing a particular combination (**) :-ent(E,rain,X,strong,tr).
If we run in DLV-Complex the program with this constraint, but without the weak constraints labeled with (*) in Example 5.7, we obtain only the first model shown in Example 5.7, corresponding to the counterfactual entity e = ent(sunny, high, weak). 2 As the previous example shows, we can easily impose constraints that make the counterfactual entities, or equivalently, the associated explanations, actionable (Ustun et al. 2019;Karimi et al. 2020b). As mentioned in Section 1, for the loan application example, we could impose a hard program constraint (i.e. add it to a CIP) of the form ←− E(e, . . . , age, . . . , o), E(e, . . . , age , . . . , * ), age < age, which prevents decreasing an applicant's age.
Logic-based specifications also allow for compilation of constraints into rules. For example, instead of using a hard constraint, such as (7), we could directly impose the condition on a counterfactual age in the disjunctive counterfactual rule P3., of the form · · · ∨ E (e, x 1 , . . . , x a , . . . , do) ∨ · · · ←− E (e,x , ), C(x , 1), . . . , Dom a (x a ), . . . , x a < x a , . . . , choice(x , x a ), . . . · Here, the subscript a refers to the domain and variables for the Age feature. On this basis, one could only increase the age. If this intervention leads to a successful counterfactual entity (i.e. with a positive label), we could tell the applicant that he/she has to wait to possibly succeed with the loan application.
We could also think of explicitly specifying actionable counterfactual entities, starting with a rule of the form where the new annotation a stands for "actionable", and the rule defines an entity as actionable if it is a counterfactual (final) entity that satisfies some extra conditions. Several possibilities offer themselves in this direction. All of them require simple, symbolic changes in the overall specification. Doing something similar with a purely procedural approach would be much more complex, and would require modifying the underlying code.
Another situation where not all interventions are admissible occurs when features take continuous values, and their domains have to be discretized. The common way of doing this, namely the combination of bucketization and one-hot-encoding, leads to the natural and necessary imposition of additional constraints on interventions, as we will show. Through bucketization, a feature range is discretized by splitting it into finitely many, say N , usually non-overlapping intervals. This makes the feature basically categorical (each interval becoming a categorical value). Next, through one-hot-encoding, the original feature is represented as a vector of length N of indicator functions, one for each categorical value (intervals here) . In this way, the original feature gives rise to N binary features. For example, if we have a continuous feature "External Risk Estimate" (ERE), its buckets could be: [0, 64), [64, 71), [71, 76), [76, 81), [81, ∞). Accordingly, if for an entity e, ERE(e) = 65, then, after one-hot-encoding, this value is represented as the vector [0, 1, 0, 0, 0, 0], because 65 falls into the second bucket.
In a case like this, it is clear that counterfactual interventions are constrained by the assumptions behind bucketization and one-hot-encoding. For example, the vector cannot be updated into, say [0, 1, 0, 1, 0, 0], meaning that the feature value for the entity falls both in intervals [64, 71) and [76, 81). Bucketization and one-hotencoding can make use of program constraints, such as ←− ERE(e, x , 1, y, 1, z , w , ), etc. Of course, admissible interventions on predicate ERE could be easily handled with a disjunctive rule like that in P3., but without the "transition" annotation . However, the ERE record is commonly a component, or a sub-record, of a larger record containing all the feature values for an entity . Hence, the need for a more general and uniform form of specification.
Here we are considering the simple scenario in which the values are treated as unordered and categorical (binary) values. In some applications of bucketization and one-hot-encoding, one assumes and takes advantage of an underlying order inherited from the values in the buckets. Such an order could be adopted and brought into this framework by using additional rules that define that order. Developing the details is somehow outside the scope of this work.

Expectation over interventions for the x-Resp score
The x-Resp introduced in Section 3 could be considered as a first approach to quantifying the relevance of a feature value. However, as the following example shows, we might want to go one step further.
We can see that changing only the original first feature value does not change the label provided by the classifier. Nor does additionally changing the second feature value, except when using the last possibly value, a k , for F 2 . In this case, x-Resp e,F1 (0) = 1 2 , despite the fact that almost all interventions on the second feature value do not change the label.
A similar phenomenon would appear if we had Dom(F 1 ) = {b 1 , · · ·, b k }, with large k , and C(E (e; b 1 , a 1 )) = 1 = C(E (e i ; b j , a 1 )), for j = 1, . . . , k − 1, but C(E (e k ; b k , a 1 )) = 0. In this case, the value b 1 is a counterfactual cause with explanation responsibility 1, despite the fact that most of the interventions of b 1 do not switch the label. A way to compensate for this could be taking the label average over all possible interventions. 2 In order to extend the definition of the x-Resp by considering all possible interventions, we may consider the average of counterfactual labels over a given population, which would assume all entities are equally likely. In more general terms, we may assume the underlying entity population, E, has a probability distribution, P , which we can use to express the extended x-Resp in terms of expected values, as follows.
Consider e ∈ E, an entity under classification, for which L(e) = 1, and a feature F ∈ F. Assume we have: In order to define the "local" responsibility score, make v vary randomly under conditions 1.-5.: If, as so far, label 1 is what has to be explained, then L(e ) = 1, and the numerator is a number between 0 and 1. Here, Γ is fixed. Now we can minimize its size, obtaining the (generalized) responsibility score as the maximum local value; everything relative to distribution P : Resp P e,F (F (e)) := max Resp P (e, F , Γ,w ) This score was introduced, with less motivation and fewer details, and definitely not on a causal basis, in , where experiments are shown, and different probability distributions are considered.

Domain knowledge under uncertainty
Different probability distribution on the entity population E can be considered in the definition and computation of the generalized responsibility score (c.f. Section 7.1). A natural choice is the uniform distribution, P u , that gives equal probability, 1 |E| , to each entity in E. Another natural distribution is the product distribution, P × , that is obtained, under the assumption of independence, as the product of given marginal distributions, p F , of the features F ∈ F: We can also assume we have a sample from the entity population S ⊆ E that is used as a proxy for the latter. In this case, the distributions above become empirical distributions. In the uniform case, it is given by:P u (e) := 1 |S | if e ∈ S , and 0, otherwise. In the case of the product,P × (f 1 , . . . , . A discussion on the use of these distributions in the context of explanation scores can be found in .
In general, one can say that the uniform distribution may not be appropriate for capturing capturing correlations between feature values. One could argue that certain combinations of feature values may be more likely than others; or that certain correlations among them exist. This situation is aggravated by the product distribution due to the independence assumption. For these reasons an empirical distribution may be better for this purpose.
In any way, having chosen a distribution on the population, P , to work with; in particular, to compute the expectations needed for the responsibility score in (8), one could consider modifying the probabilities in the hope of capturing correlations and logical relationships between feature values. In particular, one could introduce constraints that prohibit certain combinations of values, in the spirit of denial constraints in databases, but in this case admitting positive and negative atoms. For example, with propositional features Old standing for "Is older than 20" and OverDr for "Gets an account overdraft above $50K", we may want to impose the prohibition ¬(Old ∧ OverDr), standing for "nobody under 20 gets at overdraft above $50K".
These constraints, which are satisfied or violated by a single entity at a time, are of the form: where F 1 ∪ F 2 ⊆ F, F 1 ∩ F 2 = ∅, and F ,F mean that features F , F take values 1 and 0, resp. The event associated to χ is E (χ) = {e ∈ E |e |= χ}, where e |= χ has the obvious meaning of satisfaction of χ by entity e. In order to accommodate the constraint, given the initial probability space E, P , we can redefine the probability as follows. For E ⊆ E, If χ is consistent with the population, i.e. satisfiable in E, the conditional distribution is well-defined. Now, the probability of χ's violation set is: This definition can be extended to finite and consistent sets, Θ, of constraints, by using P ∧Θ (E ) in (11), with ∧Θ the conjunction of the constraints in Θ. Of course, one could go beyond constraints of the form (10), applying the same ideas, and consider any propositional formula that is intended to be evaluated on a single entity at a time, as opposed to considering combinations of feature values for different entities.
The resulting modified distribution that accommodates the constraints could be used in the computation of any of the scores expressed in terms of expected values or in probabilistic terms.
An alternative approach consists in restricting the (combinations of) interventions in the definitions and computation of the responsibility score, as suggested in Section 6 (and any other score based on counterfactual interventions, as a matter of fact). It is worth performing experimental comparisons between the two approaches.

Related Work
In this worl we consider only local methods in that we are not trying to explain the overall behavior of a classifier, but a particular output on the basis of individual feature values. We also consider model-agnostic methods that can be applied to black-box models, i.e. without the need for an access to the internal components of the model. Of course, these approaches can be applied to open models, i.e. that make all its components transparent for analysis. Actually, in some cases, it is possible to take computational advantage of this additional source of knowledge (more on this below in this section).
There are several approaches to the explanation of outcomes from classification models. These methods can be roughly categorized as those that provide attribution scores and those that provide sufficient explanations. Those in the former class assign a number to each feature value that reflects its relevance for the outcome at hand. x-Resp falls in this category. For comparison with other approaches, we repeat that, in the case of x-Resp, one counterfactually modifies feature values to see if the outcome changes. The score is computed from those changes.
Counterfactual changes are omnipresent in attribution-score-based methods, and they can be used to consider alternative entities to the one under explanation, and a notion of distance between those alternatives and the latter (Martens and Provost 2014;Wachter et al. 2017;Russell 2019;Karimi et al. 2020a;Datta et al. 2016;. Sometimes the counterfactuals are less explicit, as with the popular Shap score (Lundberg et al. 2020), that is based on the Shapley value of game theory. It can be seen as a counterfactual-based score in that all possible combinations of features values (and then, most of the time departing from the initial entity) are considered in a complex aggregation (an average or expected value).
The Shap score is designed as a model-agnostic method. However, for a large class of classifiers whose internal components can be used for the score computation, Shap becomes computable in polynomial-time, while its general computational complexity is #P -hard (Arenas et al. 2021;Van den Broeck et al. 2021). As we showed in this paper, the computation of the x-Resp is NP -hard. Actually, the generalized, probabilistic extension of x-Resp (c.f. Section 7.1), for certain classifiers and probability distributions on the underlying population, x-Resp can be #P -hard ). An investigation of classes of classifiers for which the x-Resp score (deterministic as in this work or probabilistic) can be computed in polynomial time is still open.
The popular LIME score (Ribeiro et al. 2016) is also an attribution score. It appeals to an explainable model that locally approximates the agnostic model around the entity under classification. From the resulting approximation feature scores can be computed.
Sufficient-explanation methods try to identify those (combinations of) feature values that alone determine the outcome at hand, in the sense that, by keeping those values and possibly changing all the others, the outcome remains the same (Ribeiro et al. 2018;Wang et al. 2021). One could say, in some sense, that the outcome is entailed by the values that appear in a sufficient explanation. Identifying those values is reminiscent of performing an abductive diagnosis task, as done with rulebased specifications (Eiter et al. 1997), actually (Ribeiro et al. 2018) does appeal to rule-based methods.
There are some approaches to logic-based explanations for classification. They mostly follow the sufficient-explanation paradigm we mentioned above. More specifically, it has been shown how to "reconstruct" certain classes of classifiers, e.g. random forests, Bayesian classifiers, and binary neural networks, as Boolean circuits (Shih et al. 2018;Shi et al. 2020;Choi et al. 2020). Once a circuit is available, one can use it in particular to obtain explanations for the outcomes of the model using methods that are, in essence, abductive (Darwiche and Hirth 2020). In this context the work presented in Izza and Marques-Silva 2021) is also relevant, in that logic-based encodings of neural networks, boosted trees, and random forests are proposed and exploited for explanation purposes. Abductive and SAT-based approaches are followed. Notice that abductive methods that generate sufficient explanations can also be the basis for score definitions and their computation. Just for the gist, if a feature value appears in the large number of sufficient explanations, then it could be assigned a large individual score.
To the best of our knowledge, none of the approaches described above, and others, are based on logical specifications of the counterfactuals involved in the score definition and computation. Furthermore, these are specifications that can easily adopt domain or desirable logical constraints in a seamless manner, and for com-bined use. Actually, the logic-based representations of complex classifiers that we just mentioned above, could be the starting point for the use of our approach. For example, a Boolean circuit can be represented as a set of rules that becomes a first component of a CIP that does the counterfactual analysis on that basis.

Discussion
This work is about interacting via ASP with possibly external classifiers, and reasoning about their potential inputs and outputs. The classifier is supposed to have been learned by some other means. In particular, this work is not about learning ASPs, which goes in quite a different direction (Law et al. 2019).
In this work we have treated classifiers as black-boxes that are represented by external predicates in the ASP. However, we have also considered the case of a classifier that is specified within the CIP by a set of rules, to define the classification predicate C. This was the case of a deterministic Decision Tree. Basically, each branch from the root to a label can be represented by a rule, with the branching direction at intermediate nodes represented by values in literals in a rule body, and with the label in the rule head. Something similar can be done with Boolean Circuits used as classifiers. Actually, it is possible to represent more involved classifiers as Boolean circuits (c.f. Section 8).
Our CIPs can be easily enhanced with different extensions. For example, the feature domains can be automatically specified and computed from training or test data ), or other sources. As done in  for experimental purposes and using purely procedural approaches, it is possible in our ASP setting to restrict the sizes of the contingency sets, e.g. to be of size 2 (c.f. Section 3). This can be easily done by adding a cardinality condition to the body of the disjunctive intervention rule (which is supported by DLV-Complex and DLV2). Doing this would not lead to any loss of best explanations (as long as they fall within the imposed bound), and may reduce the computational work.
It is also possible to extend CIPs to make them specify and compute the contingency sets (of feature values) that accompany a particular value that has been counterfactually changed (c.f. Section 3). This requires a set-building operation, which is provided by DLV-Complex. Doing this would allow to obtain s-explanations, i.e. with minimal (not necessarily minimum) contingency sets (c.f. Example 5.3). One could try if, by deleting one element from the contingency set, the label changes or not. Again, DLV-Complex could be used here. In (Bertossi and Reyes 2021) a detailed example can be found where this is illustrated at the light of the naive Bayes classifier. This approach was also followed in (Bertossi 2021) to compute contingency sets for individual database tuples as causes for query answers.
Our specification of counterfactual explanations is in some sense ideal, in that the whole product space of the feature domains is considered, together with the applicability of the classifier over that space. This may be impractical or unrealistic. However, we see our proposal as a conceptual and generic specification basis that can be adapted in order to include more specific declarative practices and mechanisms.
For example, restricting the product space can be done in different manners.
One can use constraints or additional conditions in rule bodies. A different approach consists in replacing the product space with the entities in a data sample S ⊆ Π n i=1 Dom(F i ). We could even assume that this sample already comes with classification labels, i.e. S L = { e 1 , L(e 1 ) , . . . , e K , L(e K ) }. This dataset may not be disjoint from the training dataset T (c.f. Section 3). The definition of counterfactual explanation and CIPs could be adapted to these new setting without major difficulties.
The CIPs we have introduced are reminiscent of repair programs that specify and compute the repairs of a database that fails to satisfy the intended integrity constraints (Caniupan and Bertossi 2010). Actually, the connection between database repairs and actual causality for query answers was established and exploited in (Bertossi and Salimi 2017a). ASPs that compute tuple-level and attribute-level causes for query answers were introduced in (Bertossi 2021). Attribute-level causes are close to interventions of feature values, but the ASPs for the former are much simpler that those presented here, because in the database scenario, changing attribute values by nulls is good enough to invalidate the query answer (the "equivalent" in that scenario to switching the classification label here). Once a null is introduced, there is no need to take it into account anymore, and a single "step" interventions are good enough.
Our CIPs are designed to obtain general counterfactual explanations, and in particular and mainly, c-explanations. The latter are associated to minimum-size contingency sets of feature values, and, at the same time, to maximum-responsibility feature values. This is achieved via the weak constraints in (6). If we wanted to obtain the responsibility of a non-maximum-responsibility feature value, that is associated to an s-explanation that is not a c-explanation, we can remove the weak constraints (and by so doing keeping all the models of the CIP), and pose a query under the brave semantics about the values of inv-resp in (4). An approach like this was followed in (Bertossi 2021) for database tuples as causes for query answers.
Apropos query answering, that we haven't exploited in this work, several opportunities offer themselves. For example, we could pose a query under the brave semantics to detect if a particular feature value is ever counterfactually changed, or counterfactually changed in a best explanation. Under the skeptical semantics, we can identify feature values that change in all the counterfactual entities. Fully exploiting query answering is a matter of ongoing work.
In this work we have considered s-and c-explanations, that are associated to two specific and related minimization criteria. However, as done in abstract terms in Section 3, counterfactual explanations could be cast in terms of different optimization criteria (Karimi et al. 2020a;Russell 2019;Schleich et al. 2021). One could investigate the specification and implementation of other forms of preference, the generic in Definition 3.1, by using ASPs as in (Gebser et al. 2011;Brewka et al. 2015).
Specifying and computing the generalized, probabilistic responsibility score of Section 7.1 goes beyond the usual capabilities of ASP systems. However, it would be interesting to explore the use of probabilistic ASPs for these tasks (Baral et al. 2009;Lee and Yang 2017). Along a similar line, probabilistic ASPs could be in principle used to deal with the integration of semantic constraints with underlying probability distributions on the entity population, as described in Section 7.2. This is all matter of ongoing work.