Our world is increasingly shaped by Artificial Intelligence systems, from search engines over automated hiring algorithms to self-driving cars. Being also used in high-stake decisions, their impact on the life of individuals is huge. Thus it becomes exceedingly important to sceptically review their limitations. One alarming problem is their uptake and reinforcement of existing social biases, as found in many diferent domains (criminal justice, facial recognition, credit scoring etc). It is complemented by the inherent opaqueness of the most accurate AI systems, making it impossible to understand details of their internal workings. The field of Explainable Artificial Intelligence is trying to address these problems. However, there are several challenges in the field, and we will start this work by pointing them out. We put forward a set of technical pathways, drawing from Logic Programming. Specifically, we propose using Constraint Logic Programming to construct explanations that incorporate prior knowledge, as well as Meta-Reasoning to track model and explanation changes over time.
Artificial Intelligence (AI) systems have a huge impact on our lives. As much as they positively shape the world, for example by supporting scientific discoveries, they bring responsibility, specifically when applied to social data. As shown in many application contexts, they are susceptible to social biases. Even more, they have the potential to increase and systematise the harm done to already marginalised societal groups.
An example is commercial facial recognition systems, found to be negatively biased against darker-skinned females (error rate up to 34.7% compared to 0.8% for lighterskinned males) [1]. Next to important questions about bias and ethical values of AI systems, we need to discuss their accountability, as the tragic case of the Uber car overrunning a pedestrian suggests [2].
One main challenge we thereby face is the opaqueness of these systems. As their internal logic is not understandable to humans, they are considered Black Boxes. struct explanations for Black Boxes, which help us to address above questions. It thereby builds upon the field of Explainable Artificial Intelligence (XAI) or equivalently After surveying the field of XAI, we pose the following challenges, which are forming the base of the proposal: 1. A canonical definition of an explanation and its 2. Prior knowledge is not exploited in the explanadesiderata is missing tion process reasoning, and reasoning under constraints [3] [4] [5].
2.1. Explainable Artificial Intelligence The field of XAI can be described along 3 main dimensions [9] [10]. First, we distinguish between constructing Transparent/White Box (WB) models, and (post-hoc) explanations for Black Boxes (BB). WB are based on inherently interpretable approaches such as linear models, decision trees, or rule lists/sets. BB describe a wide set of models, all of them being not interpretable, or not accessible. Second, explanations for BB models are either
This work is putting forward a proposal on how to con- and the loan amount asked for. The algorithmic decision present in understandable terms to a human” 2 [16].
tion is a specific person, in most cases a lay user [14].
What constitutes an explanation that manages to transport its content well, can be learnt from literature in the Social Sciences. Main points are that explanations should be social/interactive, contrastive, selective, and that probabilities do not matter much [17] [18].
Not only does the audience of the explanation matter, but also its specific purpose, defining further form and content. Purposes can be loosely grouped into the following: moral/ethical [19] [20], [21], (1) including safety concerns [16] and eforts to increase trust in the user [11], legal motivations [6], or understanding/debugging [20] [22] [16]. els only). E.g. LIME is model-agnostic, TREEPAN in its original form model-specific.
This concept focuses on local (first), model-agnostic explanation methods for Black Boxes. 2.2. Counterfactuals Counterfactuals (CF) give an answer to ”what-if” questions. Conceptually, they highlight the smallest feature changes that are necessary to alter the (undesired) prediction. A common approach to generate CF is the following optimisation problem. Denoting the CF by ′, the original (factual) data point by , the prediction of the CF as ( ′) and the new (desired) prediction as ′, it reads
min max ( ( ′) − ′)2 + (, ′ ) denotes a tuning parameter. The distance (., .) needs to be chosen carefully, a standard choice is the Manhattan Distance weighted by the Median Absolute Deviation.
2.3. Logic Programming Relevant approaches are: Constraint Logic Programming and Meta-Reasoning. Both build on Logic Programs (LP), bringing forward the following advantages as declarative paradigms: a strict separation of knowledge and inference, no encoded directionalities, as well as interpretability and verifiability [ 3] [4] [5].
LP by constraints to solve optimisation problems. They are classified based on constraint type: (non-) linear, by the number of involved variables (arity), by preference, or by domain: e.g. integer on finite domains [ 4] [5].
Enables reasoning over LP, and integration of knowledge. Standard Meta-Reasoning approaches such as meta-interpreters [5] can be augmented by theories and operators over the programs [13].
3.1. Defining Explanations A canonical definition of explanations and its desiderata in the domain of XAI is missing, see also [14] [15]. We don’t attempt to do so, but rather want to point to the following facets: local or global. Local approaches focus on single data
points, e.g. LIME [11], global on the level of the whole closely related to interpretability but a distinct concept: model by fitting an interpretable surrogate, e.g. TREPAN interpretability is a (passive) property, whereas an ex[12]. An approach that bridges the gap is GLocalX [8]. planation, or explainability is about an interaction, or Third, explanations can be model-agnostic (applicable to an exchange of information. For interpretability, the folany model) or model-specific (applicable to certain mod- lowing definition is adopted “the ability to explain or to 3.2. Prior Knowledge Prior knowledge is rarely incorporated into the explanation process. An example where this matters is the generation of CF, including some advice to change the (unfavourable) outcome. Prior knowledge that needs to be considered can be a real-world constraint, or a userbased preference. Exemplary approaches put forward are [23] [24]. The term real-world constraints is used in our work to refer to the subset of constraints that encode knowledge about the world. cation scenario. Consider the following 3 These considerations are also relevant in our loan appli
A p p l i c a n t F a c t u a l C F = 45 ∧ = ∧ = 10 > 40 ∧ = ∧ > 5 ≤ 40 ∧ = ∧ ≤ 5 The CF suggests to the applicant to decrease the age and the loan amount, while the feature ”job” stays constant.
While decreasing the age is invalidating a real-world constraint, decreasing the loan amount could also be impossible for the applicant, depending on the intended use of the loan (user-based constraint). 3.3. Changing Models Explanations do not take into account that a model (and thus the explanation) can change over time. However, 2Emphasis added.
3Adapted from LORE [25]. The form is the same, content is changed. LORE provides each a local factual and a counterfactual rule as explanation. this is not realistic in deployment. The model can change if the training data distribution shifts, e.g. by new incoming data points, and retraining, or by adjustments at the model itself, e.g. following a new regulation. Explanations need, therefore, to be extended by a time dimension.
In the loan application scenario, it would be important to see which parts of an explanation change over time, specifically if we want to provide counterfactuals as actionable advice. As pointed out by [26], the danger is that although recommendations are followed, the model does not alter its prediction because it changed as well. sation problem over the distance between the factual and the CF 4, subject to the following constraints 5: • the prediction is opposite to the factual prediction
(binary decision problem) • restricting the domain/range • restricting feasibility (immutable/actionable), in
cluding encoding relations/monotonicity • enforcing diversity/sparsity Whereas the first constraint is absolutely necessary, others depend on the use-case of the CF. When focusing on understanding/debugging the model, no other con3.4. Customisation + Evaluation straints, or a restricted set (e.g. domain/range) sufices. Customisation Explanations are, in their final version, This also holds, if we want to learn about bias in the deuser-specific and thus need to be adapted to the audience cision pipeline. If we are rather interested in actionable [14]. This goes together with the specific purpose of the advice, the full set of the posed constraints can be used. explanation (see 3.1). Real-world constraints are mandatory in these cases, othConsider the loan application scenario. The bank clerk ers depend on the person that is subject to the decision. who is in charge of communicating the loan decision The first constraint is mandatory, but hardest to encode, needs similar information to the applicant. For example, as we cannot call the BB from within the logic program. both might be interested in advice on how to change an A possible solution connects our idea to LORE [25]. This undesired outcome (purpose: moral/ethical, legal). How- method provides local explanations as of logic rules. The ever, the manager of the bank is not interested in receiv- rules are read from a decision tree, which is grown on ing explanations in such details, but rather in summary the local neighbourhood around the instance that is in statistics, or general information about how decisions focus. Using the split criteria put forward by the tree, we were derived (purpose: understanding). Still, explana- can construct regions which hold possible CF, and use tions could be generated under the same framework, e.g. these as inputs for the optimisation problem. local explanations by LORE [25], an aggregation by GLo- For other types of constraints, we provide exemplary calX [8], building upon the former. implementations, based on Prolog/Eclipse [28] [29]. A CF feature is denoted by subscript CF, the original by F.
Evaluation Alarmingly little has been done in this ifeld yet: considering the case of CF explanations, a recent Range Constraints Restricting the numerical range survey found that only 21% of the approaches are vali- itno oanceoonrsbtaontht (dliirneect1i/o2n)s., Abynoabthsoerluoteptniuomnb(leirnseo3r)raellalotiwves dated with human subject experiments [27]. However, the variable to take only very specific values. In the loan the call for evaluations based on this type of experiments application scenario, this could be the total loan duration, is not new, and holds for the whole field [ 16]. If com- encoded in months, allowed to change in multiples of putational evaluation is preferred, attention needs to be three (quarterly). drawn to carefully validate the proxy variables that are used to simulate human behaviour [27]. 1| age_CF #>= 0.
In our loan application scenario, an ideal evaluation 2| initial_payment_CF #<= 0.2 * loan_amount. would involve human subject experiments with the ap- 3| (loan_duration_CF mod 3) #= 0. plicant, the bank clerk, and the manager separately.
To compute CF that incorporate prior knowledge, we 4Optimal encoding of distance is an open problem. As a start, revisit CLP. The CF generation is encoded as an optimi- (a combination of) the 1, 2 or norm can be used. 5Loosely based on [7].
In this section, we put forward concrete ideas to address two of the above challenges (3.2 and 3.3). It is out of scope of this proposal to answer to the full set of challenges. 4.1. Prior Knowledge Feasibility Constraints Immutable features (line 1), actionable depending on its previous value such as age in our scenario (line 2) or depending on the change of another feature. In our scenario, this could be the first instalment to be paid, that needs to increase if the total loan amount (now a variable) does (line 3-7).
1| 2| 3| birthplace_CF #= birthplace_F. age_CF #>= age_F. dependency(loan_amount_CF, loan_amount_F, 4| 5| 6| 7| instalment_CF, instalment_F) :((loan_amount_CF - loan_amount_F) #> 0 -> instalment_CF #> instalment_F ; instalment_CF #>= instalment_F).
Our approach is inspired by (1) [24] [30] (using SAT/ causal framework) and (2) [23] [31] [32] [33] (using ILP/ MILP). However, there are two main points that distinguishes the approach put forward: first, the focus is clearly on creating explanations for any BB. Approaches (1) are generally agnostic, but the model internals need to be known, in (2) only linear or additive models are considered. Second, to the best of our knowledge, this is the first approach using LP to generate CF. 4.2. Changing Models 18| lowincome(applicant) :- theory(fact_t1). 19| theory(fact_t2). 20| savings(applicant) :- theory(fact_t2).
21| highincome(applicant) :- theory(fact_t2).
According to the rules and facts at 1 , the applicant will not receive a loan (deny). The following changes can be advised, based on information available at 1 , e.g. by generating a CF: to increase the income (line 2/3), or to buy a car (line 4/5). Whereas increasing the income will change the prediction at 2 (line 9/10), buying a car will not, as we observe a change in this rule (line 11/12). We update the facts at 2 according to the first advice and check this outcome by posing the following query, which returns P e r s o n = a p p l i c a n t .
1| cf_condition(Person) :2| solve(deny(Person), union(rule_t1, fact_t1)), 3| solve(grant(Person), union(rule_t2, fact_t2)).
This problem can be addressed by Meta-Reasoning. The standard meta-interpreter is extended by theories [13].
We introduce the meta-interpreter (line 1-8). Also, we will need the union operator (line 9-14) 6.
Although we presented only a toy example, that is restricted in applicability, we could demonstrate the importance of reasoning over time. As a possible next step, we 1| solve(true, _). propose integrating [25] or [8], and reasoning directly 2| solve((G1,G2), T) :- solve(G1, T), solve(G2, T). over the extracted BB explanations. 3| solve(A, T) :- clause_in_th(A, B, T), 4| solve(B, T). 5| clause_in_th(A, B, T) :- 5. Conclusion 6| clause(A, (theory(T), B)). 7| clause_in_th(A, true, T) :8| clause(A, theory(T)). 9| solve(A, union(T1, T2)) :10| clause_in_th(A, B, T1), 11| solve(B, union(T1, T2)). 12| solve(A, union(T1, T2)) :13| clause_in_th(A, B, T2), 14| solve(B, union(T1, T2)).
Now, let us look at a simple toy example. We specify two diferent time points ( 1/2 ), each defined by a set of rules (line 1-15) and facts (line 16-21), mirroring the change of the model/applicant over time.
1| theory(rule_t1). 2| grant(Person) :- theory(rule_t1), 3| highincome(Person), savings(Person). 4| grant(Person) :- theory(rule_t1), 5| car(Person), savings(Person). 6| deny(Person) :- theory(rule_t1), 7| lowincome(Person), savings(Person). 8| theory(rule_t2). 9| grant(Person) :- theory(rule_t2), 10| highincome(Person), savings(Person). 11| grant(Person) :- theory(rule_t2), 12| car(Person), highincome(Person). 13| deny(Person) :- theory(rule_t2), 15| lowincome(Person), savings(Person). 16| theory(fact_t1). 17| savings(applicant) :- theory(fact_t1).
This paper presented two concrete ideas that apply LP to address challenges in XAI. Specifically, we proposed a CLP-based approach to generate CF that can incorporate prior knowledge, and a Meta-Reasoning approach to account for changes in models and explanations. As such, they can be seen as one answer to the GDPR, to provide ”meaningful information about the logic involved” [34] to any person under an automated decision. To summarise, we want to point out two aspects of the ifeld of XAI: first, it is a highly interdisciplinary endeavour that will only manage to address the challenges of AI, and its own, by calling to participation scholars from Computer Science, Social Sciences, Law and others. Second, explanations are always context-dependent, addressing a specific problem, user group, and purpose. This needs to be considered when they are constructed, used, and evaluated.
I want to thank my supervisors Salvatore Ruggieri and Franco Turini for many fruitful discussions and advice. This work is supported by the project “NoBias - Artificial Intelligence without Bias,” which has received funding from the European Union’s Horizon 2020 research and innovation programme, under the Marie SkłodowskaCurie (Innovative Training Network) grant agreement no. 860630. DACE: distribution-aware counterfactual explanation by mixed-integer linear optimization, in: IJCAI, ijcai.org, 2020, pp. 2855–2862. [33] Z. Cui, W. Chen, Y. He, Y. Chen, Optimal action extraction for random forests and boosted trees, in: KDD, ACM, 2015, pp. 179–188. [34] European Union, General data protection regulation, 2016. URL: https://gdpr.eu/ article-15-right-of-access/.