Logic Programming for XAI: A technical perspective1 Laura State1,2 1 Department of Computer Science, University of Pisa, Largo B. Pontecorvo, 3, 56127 Pisa, Italy 2 Scuola Normale Superiore, Piazza dei Cavalieri, 7, 56126 Pisa, Italy Abstract 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 different 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. 1. Introduction 3. Explanations do not account for time-evolving models Artificial Intelligence (AI) systems have a huge impact 4. Explanations are not sufficiently evaluated, nor on our lives. As much as they positively shape the world, specific to the end user for example by supporting scientific discoveries, they bring responsibility, specifically when applied to social We will cover each of the points in sec. 3. But first, a data. As shown in many application contexts, they are quick overview on current approaches in XAI is given, as susceptible to social biases. Even more, they have the well as an introduction to Counterfactual Explanations potential to increase and systematise the harm done to and Logic Programming (sec. 2). The technical proposal, already marginalised societal groups. focusing on challenge 2 and 3, is put forward in sec. 4. An example is commercial facial recognition systems, found to be negatively biased against darker-skinned fe- Why logic? Technical aspects of the posed questions males (error rate up to 34.7% compared to 0.8% for lighter- can be addressed by Logic. As such, we present an ap- skinned males) [1]. Next to important questions about plication scenario for Logic Programming. It is an in- bias and ethical values of AI systems, we need to discuss herently interpretable and verifiable approach, and can their accountability, as the tragic case of the Uber car easily incorporate prior knowledge. It also supports meta- overrunning a pedestrian suggests [2]. reasoning, and reasoning under constraints [3] [4] [5]. One main challenge we thereby face is the opaqueness of these systems. As their internal logic is not understand- Running Example A loan application scenario, in- able to humans, they are considered Black Boxes. cluding an applicant with specific features such as age, This work is putting forward a proposal on how to con- and the loan amount asked for. The algorithmic decision struct explanations for Black Boxes, which help us to reduces to a binary classification problem (grant/deny address above questions. It thereby builds upon the field loan). It is a relevant, real-world example [6] [7] [8]. of Explainable Artificial Intelligence (XAI) or equivalently Interpretable Machine Learning, and Logic Programming. After surveying the field of XAI, we pose the following 2. Related work challenges, which are forming the base of the proposal: 2.1. Explainable Artificial Intelligence 1. A canonical definition of an explanation and its The field of XAI can be described along 3 main dimen- desiderata is missing sions [9] [10]. First, we distinguish between construct- 2. Prior knowledge is not exploited in the explana- ing Transparent/White Box (WB) models, and (post-hoc) tion process explanations for Black Boxes (BB). WB are based on in- herently interpretable approaches such as linear models, 1st Workshop on Machine Ethics and Explainability - The Role of decision trees, or rule lists/sets. BB describe a wide set Logic Programming, September 2021, Virtual Only of models, all of them being not interpretable, or not ac- Envelope-Open laura.state@di.unipi.it (L. State) cessible. Second, explanations for BB models are either © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 1 CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 Original Contribution. local or global. Local approaches focus on single data Explanation or Interpretation? Explanations are 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 fol- any model) or model-specific (applicable to certain mod- lowing definition is adopted “the ability to explain or to els only). E.g. LIME is model-agnostic, TREEPAN in its present in understandable terms to a human” 2 [16]. original form model-specific. This concept focuses on local (first), model-agnostic ex- Explanation to whom? The receiver of an explana- planation methods for Black Boxes. tion is a specific person, in most cases a lay user [14]. What constitutes an explanation that manages to trans- 2.2. Counterfactuals port its content well, can be learnt from literature in the Social Sciences. Main points are that explanations Counterfactuals (CF) give an answer to ”what-if” ques- should be social/interactive, contrastive, selective, and tions. Conceptually, they highlight the smallest feature that probabilities do not matter much [17] [18]. changes that are necessary to alter the (undesired) predic- tion. A common approach to generate CF is the following Explanation of what? Not only does the audience of optimisation problem. Denoting the CF by 𝑥 ′ , the origi- the explanation matter, but also its specific purpose, defin- nal (factual) data point by 𝑥, the prediction of the CF as ′ ′ ing further form and content. Purposes can be loosely 𝑓𝑤 (𝑥 ) and the new (desired) prediction as 𝑦 , it reads grouped into the following: moral/ethical [19] [20], [21], 𝑎𝑟𝑔 min max 𝜆(𝑓𝑤 (𝑥 ′ ) − 𝑦 ′ )2 + 𝑑(𝑥, 𝑥 ′ ) (1) including safety concerns [16] and efforts to increase 𝑥 𝜆 trust in the user [11], legal motivations [6], or under- 𝜆 denotes a tuning parameter. The distance 𝑑(., .) needs standing/debugging [20] [22] [16]. to be chosen carefully, a standard choice is the Manhattan Distance weighted by the Median Absolute Deviation. The approach was first put forward in [6]. 3.2. Prior Knowledge Prior knowledge is rarely incorporated into the expla- 2.3. Logic Programming nation process. An example where this matters is the generation of CF, including some advice to change the Relevant approaches are: Constraint Logic Programming (unfavourable) outcome. Prior knowledge that needs to and Meta-Reasoning. Both build on Logic Programs (LP), be considered can be a real-world constraint, or a user- bringing forward the following advantages as declara- based preference. Exemplary approaches put forward tive paradigms: a strict separation of knowledge and are [23] [24]. The term real-world constraints is used in inference, no encoded directionalities, as well as inter- our work to refer to the subset of constraints that encode pretability and verifiability [3] [4] [5]. knowledge about the world. These considerations are also relevant in our loan appli- Constraint Logic Programming (CLP) Augmenting cation scenario. Consider the following 3 LP by constraints to solve optimisation problems. They Applicant 𝑎𝑔𝑒 = 45 ∧ 𝑗𝑜𝑏 = 𝑛𝑜𝑛𝑒 ∧ 𝑎𝑚𝑜𝑢𝑛𝑡 = 10𝑘 are classified based on constraint type: (non-) linear, by Factual 𝑎𝑔𝑒 > 40 ∧ 𝑗𝑜𝑏 = 𝑛𝑜𝑛𝑒 ∧ 𝑎𝑚𝑜𝑢𝑛𝑡 > 5𝑘 the number of involved variables (arity), by preference, CF 𝑎𝑔𝑒 ≤ 40 ∧ 𝑗𝑜𝑏 = 𝑛𝑜𝑛𝑒 ∧ 𝑎𝑚𝑜𝑢𝑛𝑡 ≤ 5𝑘 or by domain: e.g. integer on finite domains [4] [5]. The CF suggests to the applicant to decrease the age and the loan amount, while the feature ”job” stays constant. Meta-Reasoning Enables reasoning over LP, and in- While decreasing the age is invalidating a real-world tegration of knowledge. Standard Meta-Reasoning ap- constraint, decreasing the loan amount could also be im- proaches such as meta-interpreters [5] can be augmented possible for the applicant, depending on the intended use by theories and operators over the programs [13]. of the loan (user-based constraint). 3. Main Challenges 3.3. Changing Models Explanations do not take into account that a model (and 3.1. Defining Explanations thus the explanation) can change over time. However, A canonical definition of explanations and its desiderata 2 Emphasis added. in the domain of XAI is missing, see also [14] [15]. We 3 Adapted from LORE [25]. The form is the same, content is don’t attempt to do so, but rather want to point to the changed. LORE provides each a local factual and a counterfactual following facets: rule as explanation. this is not realistic in deployment. The model can change sation problem over the distance between the factual and if the training data distribution shifts, e.g. by new incom- the CF 4 , subject to the following constraints 5 : ing data points, and retraining, or by adjustments at the model itself, e.g. following a new regulation. Explana- • the prediction is opposite to the factual prediction tions need, therefore, to be extended by a time dimension. (binary decision problem) In the loan application scenario, it would be important • restricting the domain/range to see which parts of an explanation change over time, • restricting feasibility (immutable/actionable), in- specifically if we want to provide counterfactuals as ac- cluding encoding relations/monotonicity tionable advice. As pointed out by [26], the danger is • enforcing diversity/sparsity that although recommendations are followed, the model does not alter its prediction because it changed as well. Whereas the first constraint is absolutely necessary, oth- ers depend on the use-case of the CF. When focusing on understanding/debugging the model, no other con- 3.4. Customisation + Evaluation straints, or a restricted set (e.g. domain/range) suffices. Customisation Explanations are, in their final version, This also holds, if we want to learn about bias in the de- user-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, oth- Consider 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 field yet: considering the case of CF explanations, a recent Range Constraints Restricting the numerical range in one or both directions, by absolute numbers or relative survey found that only 21% of the approaches are vali- to a constant (line 1/2). Another option (line 3) allows 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. 2| initial_payment_CF #<= 0.2 * loan_amount. In our loan application scenario, an ideal evaluation 3| (loan_duration_CF mod 3) #= 0. would involve human subject experiments with the ap- plicant, the bank clerk, and the manager separately. Feasibility Constraints Immutable features (line 1), actionable depending on its previous value such as age 4. The (technical) path forward in our scenario (line 2) or depending on the change of another feature. In our scenario, this could be the first In this section, we put forward concrete ideas to address instalment to be paid, that needs to increase if the total two of the above challenges (3.2 and 3.3). It is out of scope loan amount (now a variable) does (line 3-7). of this proposal to answer to the full set of challenges. 1| birthplace_CF #= birthplace_F. 2| age_CF #>= age_F. 4.1. Prior Knowledge 3| dependency(loan_amount_CF, loan_amount_F, To compute CF that incorporate prior knowledge, we 4 Optimal encoding of distance is an open problem. As a start, revisit CLP. The CF generation is encoded as an optimi- (a combination 5 of) the 𝐿1 , 𝐿2 or 𝐿𝑖𝑛𝑓 norm can be used. Loosely based on [7]. 4| instalment_CF, instalment_F) :- 18| lowincome(applicant) :- theory(fact_t1). 5| ((loan_amount_CF - loan_amount_F) #> 0 19| theory(fact_t2). 6| -> instalment_CF #> instalment_F 20| savings(applicant) :- theory(fact_t2). 7| ; instalment_CF #>= instalment_F). 21| highincome(applicant) :- theory(fact_t2). Our approach is inspired by (1) [24] [30] (using SAT/ According to the rules and facts at 𝑡1, the applicant will causal framework) and (2) [23] [31] [32] [33] (using ILP/ not receive a loan (deny). The following changes can MILP). However, there are two main points that distin- be advised, based on information available at 𝑡1, e.g. by guishes the approach put forward: first, the focus is generating a CF: to increase the income (line 2/3), or to buy a car (line 4/5). Whereas increasing the income will clearly on creating explanations for any BB. Approaches change the prediction at 𝑡2 (line 9/10), buying a car will (1) are generally agnostic, but the model internals need not, as we observe a change in this rule (line 11/12). We to be known, in (2) only linear or additive models are update the facts at 𝑡2 according to the first advice and considered. Second, to the best of our knowledge, this is check this outcome by posing the following query, which the first approach using LP to generate CF. returns P e r s o n = a p p l i c a n t . 1| cf_condition(Person) :- 4.2. Changing Models 2| solve(deny(Person), union(rule_t1, fact_t1)), This problem can be addressed by Meta-Reasoning. The 3| solve(grant(Person), union(rule_t2, fact_t2)). standard meta-interpreter is extended by theories [13]. Although we presented only a toy example, that is re- We introduce the meta-interpreter (line 1-8). Also, we 6 stricted in applicability, we could demonstrate the impor- will need the union operator (line 9-14) . tance of reasoning over time. As a possible next step, we 1| solve(true, _). propose integrating [25] or [8], and reasoning directly 2 | s o l v e ( ( G 1 , G 2 ) , T ) : - s o l v e ( G 1 , T ) , s o l v e ( G 2 , 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) :- This paper presented two concrete ideas that apply LP 8| clause(A, theory(T)). to address challenges in XAI. Specifically, we proposed a 9| solve(A, union(T1, T2)) :- CLP-based approach to generate CF that can incorporate 10| clause_in_th(A, B, T1), prior knowledge, and a Meta-Reasoning approach to ac- 11| solve(B, union(T1, T2)). count for changes in models and explanations. 12| solve(A, union(T1, T2)) :- As such, they can be seen as one answer to the GDPR, 13| clause_in_th(A, B, T2), 14| solve(B, union(T1, T2)). to provide ”meaningful information about the logic in- volved” [34] to any person under an automated decision. Now, let us look at a simple toy example. We specify To summarise, we want to point out two aspects of the two different time points (𝑡1/𝑡2), each defined by a set field of XAI: first, it is a highly interdisciplinary endeavour of rules (line 1-15) and facts (line 16-21), mirroring the that will only manage to address the challenges of AI, and change of the model/applicant over time. its own, by calling to participation scholars from Com- 1| theory(rule_t1). puter Science, Social Sciences, Law and others. Second, 2| grant(Person) :- theory(rule_t1), explanations are always context-dependent, addressing a 3| highincome(Person), savings(Person). specific problem, user group, and purpose. This needs 4| grant(Person) :- theory(rule_t1), to be considered when they are constructed, used, and 5| car(Person), savings(Person). evaluated. 6| deny(Person) :- theory(rule_t1), 7| lowincome(Person), savings(Person). 8| theory(rule_t2). Acknowledgments 9| grant(Person) :- theory(rule_t2), 10| highincome(Person), savings(Person). I want to thank my supervisors Salvatore Ruggieri and 11| grant(Person) :- theory(rule_t2), Franco Turini for many fruitful discussions and advice. 12| car(Person), highincome(Person). This work is supported by the project “NoBias - Artificial 13| deny(Person) :- theory(rule_t2), Intelligence without Bias,” which has received funding 15| lowincome(Person), savings(Person). from the European Union’s Horizon 2020 research and 16| theory(fact_t1). innovation programme, under the Marie Skłodowska- 17| savings(applicant) :- theory(fact_t1). Curie (Innovative Training Network) grant agreement 6 no. 860630. Code contributed by F. Turini. References I learnt to stop worrying and love the social and behavioural sciences, CoRR abs/1712.00547 (2017). [1] J. Buolamwini, T. Gebru, Gender shades: Intersec- [18] T. Miller, Explanation in artificial intelligence: In- tional accuracy disparities in commercial gender sights from the social sciences, Artif. Intell. 267 classification, in: FAT, volume 81 of Proceedings of (2019) 1–38. Machine Learning Research, PMLR, 2018, pp. 77–91. [19] E. Ntoutsi, P. Fafalios, U. Gadiraju, V. Iosi- [2] BBC News, Tech, Uber’s self-driving operator fidis, W. Nejdl, M. Vidal, S. Ruggieri, F. Turini, charged over fatal crash, 2020. URL: https://www. S. Papadopoulos, E. Krasanakis, I. Kompatsiaris, bbc.com/news/technology-54175359. K. Kinder-Kurlanda, C. Wagner, F. Karimi, M. Fer- [3] A. Cropper, S. Dumancic, Inductive logic pro- nández, H. Alani, B. Berendt, T. Kruegel, C. Heinze, gramming at 30: a new introduction, CoRR K. Broelemann, G. Kasneci, T. Tiropanis, S. Staab, abs/2008.07912 (2020). Bias in data-driven artificial intelligence systems [4] S. J. Russell, P. Norvig, Artificial Intelligence: A - an introductory survey, Wiley Interdiscip. Rev. Modern Approach, 2 ed., Pearson Education, 2003. Data Min. Knowl. Discov. 10 (2020). [5] K. Apt, From logic programming to Prolog, Prentice [20] D. Pedreschi, F. Giannotti, R. Guidotti, A. Monreale, Hall, London New York, 1997. S. Ruggieri, F. Turini, Meaningful explanations of [6] S. Wachter, B. D. Mittelstadt, C. Russell, Coun- black box AI decision systems, in: AAAI, AAAI terfactual explanations without opening the black Press, 2019, pp. 9780–9784. box: Automated decisions and the GDPR, CoRR [21] M. J. Kusner, J. R. Loftus, C. Russell, R. Silva, Coun- abs/1711.00399 (2017). terfactual fairness, in: NIPS, 2017, pp. 4066–4076. [7] A. Karimi, G. Barthe, B. Schölkopf, I. Valera, [22] P. Lertvittayakumjorn, L. Specia, F. Toni, FIND: A survey of algorithmic recourse: definitions, human-in-the-loop debugging deep text classifiers, formulations, solutions, and prospects, CoRR in: EMNLP (1), Association for Computational Lin- abs/2010.04050 (2020). guistics, 2020, pp. 332–348. [8] M. Setzu, R. Guidotti, A. Monreale, F. Turini, D. Pe- [23] B. Ustun, A. Spangher, Y. Liu, Actionable recourse dreschi, F. Giannotti, Glocalx - from local to global in linear classification, in: FAT, ACM, 2019, pp. explanations of black box AI models, Artif. Intell. 10–19. 294 (2021) 103457. [24] A. Karimi, G. Barthe, B. Balle, I. Valera, Model- [9] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Gi- agnostic counterfactual explanations for conse- annotti, D. Pedreschi, A survey of methods for ex- quential decisions, in: AISTATS, volume 108 of plaining black box models, ACM Comput. Surv. 51 Proceedings of Machine Learning Research, PMLR, (2019) 93:1–93:42. 2020, pp. 895–905. [10] C. Molnar, Interpretable Machine Learn- [25] R. Guidotti, A. Monreale, S. Ruggieri, D. Pedreschi, ing, 2019. https://christophm.github.io/ F. Turini, F. Giannotti, Local rule-based expla- interpretable-ml-book/. nations of black box decision systems, CoRR [11] M. T. Ribeiro, S. Singh, C. Guestrin, ”why should abs/1805.10820 (2018). I trust you?”: Explaining the predictions of any [26] S. Barocas, A. D. Selbst, M. Raghavan, The hidden classifier, in: KDD, ACM, 2016, pp. 1135–1144. assumptions behind counterfactual explanations [12] M. W. Craven, J. W. Shavlik, Extracting tree- and principal reasons, in: FAT*, ACM, 2020, pp. structured representations of trained networks, in: 80–89. NIPS, MIT Press, 1995, pp. 24–30. [27] M. T. Keane, E. M. Kenny, E. Delaney, B. Smyth, [13] A. Brogi, P. Mancarella, D. Pedreschi, F. Turini, The- If only we had better counterfactual explanations: ory construction in computational logic, in: ICLP Five key deficits to rectify in the evaluation of coun- Workshop on Construction of Logic Programs, Wi- terfactual XAI techniques, CoRR abs/2103.01035 ley, 1991, pp. 241–250. (2021). [14] B. D. Mittelstadt, C. Russell, S. Wachter, Explain- [28] SWI Prolog, Website swi-prolog, 2021. URL: https: ing explanations in AI, in: FAT, ACM, 2019, pp. //www.swi-prolog.org/. 279–288. [29] Eclipse, Website eclipse, 2021. URL: https:// [15] Z. C. Lipton, The mythos of model interpretability, eclipseclp.org/. Commun. ACM 61 (2018) 36–43. [30] A. Karimi, B. Schölkopf, I. Valera, Algorithmic re- [16] F. Doshi-Velez, B. Kim, Towards a rigorous sci- course: from counterfactual explanations to inter- ence of interpretable machine learning, 2017. ventions, in: FAccT, ACM, 2021, pp. 353–362. arXiv:1702.08608. [31] C. Russell, Efficient search for diverse coherent [17] T. Miller, P. Howe, L. Sonenberg, Explainable AI: explanations, in: FAT, ACM, 2019, pp. 20–28. beware of inmates running the asylum or: How [32] K. Kanamori, T. Takagi, K. Kobayashi, H. Arimura, DACE: distribution-aware counterfactual explana- tion 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 protec- tion regulation, 2016. URL: https://gdpr.eu/ article-15-right-of-access/.