Julie Descamps

Yiran Zhao

Jing Yu

Guobao Xu

Yoan Léger

Gabriel Loget

Neso Sojic

Anti-Stokes Photoinduced Electrochemiluminescence at a Photocathode

Anti

Photoinduced electrochemiluminescence (PECL) is a research field that combines absorption and emission photoelectrochemistry, i.e., photoelectrochemistry at illuminated semiconductors (SCs) and electrochemiluminescence (ECL). [1][2][3] ECL is the emission of light caused by the excited state of a luminophore generated by redox reactions at an electrode surface. [START_REF] Sojic | Analytical Electrogenerated Chemiluminescence: From Fundamentals to Bioassays[END_REF] Most applications of ECL rely on the use of model ECL luminophores such as tris(bipyridine)ruthenium(II) complex ([Ru(bpy) 3 ] 2+ ), or luminol (3-aminophthalhydrazide), and their analogs. [5][6][7] ECL has become a powerful analytical method, especially for immunoassays and clinical diagnosis, [8,9] and is promising for bio-imaging. [10][11][12][13] On the other hand, in photoelectrochemistry at illuminated SCs, a depleted SC absorbs photons to generate minority charges carriers that participate in redox reactions at the solid/liquid interface. [14][START_REF] Memming | Semiconductor Electrochemistry[END_REF][START_REF] Tan | Prog. Inorg. Chem[END_REF] PECL couples these two concepts together by employing absorption at a depleted SC to emit ECL, which enables Stokes or anti-Stokes-type photon conversion (depending on the SC bandgap, the excitation wavelength, and the ECL system employed). [3] Anti-Stokes PECL is based on the use of a narrow-bandgap SC as a photoelectrode, which is challenging due to poor stability in operation conditions. [START_REF] Bard | [END_REF]18] However, progress made on photoelectrode materials and SC protection strategies recently allowed to promote considerable progress in PECL. For instance, the infrared (IR)-to-visible conversion of photons by anti-Stokes PECL was demonstrated with [Ru(bpy) 3 ] 2+ /TPrA, [19,20] and the luminol/H 2 O 2 systems at n-type Si (n-Si) based photoanodes. [21] In this approach, Si is particularly prone to anodic corrosion processes and requires the use of protection strategies, i.e., its coverage by an oxide and a metal thin film [19,20] or the covalent grafting of an organic monolayer. [21] An anodic ECL system was also investigated using more stable oxide-based n-type SCs photoanodes (BiVO 4

or -Fe 2 O 3 ), but the higher bandgap value of such materials only allowed Stokes-type PECL conversion. [22,23] Nevertheless, several narrow bandgap SCs are relatively stable in the photocathodic regime, which makes their use as photocathodes an important and straightforward alternative for stable anti-Stokes PECL. This strategy has been unexplored since the mid-seventies when anti-Stokes cathodic PECL was proposed with a diphenylanthracene derivative through ion annihilation pathway. [3] In this communication, we report the cathodic PECL at hydrogenated p-type Si (p-Si) using a coreactant mechanism where [Ru(bpy) 3 ] 2+ acts as a luminophore and benzoyl peroxide (BPO) as a sacrificial coreactant, as depicted in Figure 1a. In our experiments, p-Si was selected because of its availability, its narrow bandgap, and its stability at cathodic bias. [24][25][26][27][28] Indeed, as opposed to anodic bias, no dramatic degradation is expected for freshly hydrogenated (treated by a 10% HF solution) Si electrodes rapidly immersed in the electrolyte and used under cathodic bias. [24][25][26][27][28] Si has a bandgap of 1.12 eV (Figure 1b, blue line), meaning that it can absorb incident photons with a wavelength shorter than 1.1 µm. [29] Therefore, we employed an IR light-emitting diode (LED, λ LED = 850 nm) as an excitation source, as shown in Figure 1b. We selected this incident wavelength because it corresponds to a high external quantum yield for Si photocathodes, [28,30] and it is far enough from the ECL emission band. Under illumination, free electrons (e -) are photogenerated within the Si layer and can diffuse towards the depletion region of the p-Si to participate to the electrochemical reaction. At the p-Si/electrolyte interface, they reduce BPO to BPO

•-and [Ru(bpy) 3 ] 2+ to [Ru(bpy) 3 ] + . BPO

•irreversibly decomposes, giving a strongly reactive radical [31,32] that oxidizes [Ru(bpy) 3 ] + with a highly exergonic electron transfer leading to its excited state [Ru(bpy) 3 ] 2+* . On Figure 1a, a stepwise dissociative electron transfer reaction of BPO is represented but some previous reports described also the possibility of concerted dissociative electron-transfer reaction of BPO. [33][34][35][36] The luminophore returns then to the ground state by emitting a photon at λ ECL = 630 nm (Figure 1b, red line). During our experiments, the ECL spectra are recorded continuously with a spectrometer coupled to an optical fiber, as shown in Figure 1c (see ESI for more details). p-Si was first studied by cyclic voltammetry from 0 to -2 V (all potentials are referred vs. an Ag wire quasi reference electrode) under IR irradiation (6.6 mW cm -2 ) and in the dark.

The cyclic voltammograms (CVs) of Figure 2a show that while a relatively low current density is recorded in the dark (dark curve, < -0.69 mA cm -2 ), a wave with a higher photocurrent density appears from -0.69 V under illumination (red curve). As shown in Figure 2b, a strong light emission is detected under illumination from -1.24 V, demonstrating the PECL activity of this photocathode. The ECL spectra recorded during the CVs [37] show an emission band centered at 630 nm typical to the metal-to-ligand charge transfer excited state [Ru(bpy) 3 ] 2+ * (Figure 2c). In order to compare this PECL behavior with that of ECL, further experiments were performed in the same conditions except that heavily doped non-photoactive n + -Si electrodes (essentially behaving as a conductor) were studied in the dark (blue curve). The blue curves of Figures 2a,b show that, in this case, a strong cathodic wave associated with ECL emission can be observed at much more negative potentials. It is also clearly visible by comparing the ECL spectra collected on both SCs during the CVs (Figure 2c). This highlights the effect of the photovoltage generated in the depleted p-Si, which shifts the emission onset potential. This is clearly illustrated by the fact that the potential of maximum emission is shifted by a considerable value of +0.51 V for PECL at the p-Si photocathode when compared with ECL at the n + -Si cathode. A comparative study done on a series of 7 p-Si photocathodes and 5 n + -Si cathodes revealed that the onset potential values for emission can vary within a relatively large 200 mV potential range. This behavior is attributed to difference in the state of the Si surface, which can be altered during its handling in air between the chemical hydrogenation and the electrochemical study. The PECL stability was then studied under potentiostatic control (E app = -1.6 V) by alternatively turning the IR LED (P = 6.6 mW cm -2 ) on for 5 min and off for 1 min for an overall time of 30 min. We checked the potential heating effect of the LED and the temperature of the electrolyte solution was constant for 30 min. under LED illumination. The chronoamperogram (CA) shows that the photocurrent density (Figure 2d) and the PECL signals (Figure 2e) are stable for 25 min. and instantly responds to illumination condition. These results show that stable PECL emission can be generated for 25 min. at hydrogenated p-Si-based photocathodes. The ECL instability observed after 25 minutes may be related to some sideproducts generated by the continuous reduction of BPO or to the accumulation of these side-products that may quench the ECL emission.

To conclude, we have reported the first example of cathodic PECL using [Ru(bpy) 3 ] 2+ as a luminophore. The emission occurs through a reductive-oxidation pathway with BPO employed as a sacrificial co-reactant. We have shown that hydrogenated p-Si can be used for anti-Stokes PECL for converting invisible IR light (λ LED = 850 nm) to visible light (λ ECL = 630 nm) with satisfying stability in operation. This study demonstrates that the use of a photocathode represents a relatively simple and reliable alternative for upconversion PECL when employed with cathodic ECL systems, which is promising for future development in PECL.

-

  Stokes photoinduced electrochemiluminescence (PECL) converts infrared photons to visible photons and is usually triggered at a narrow bandgap protected photoanode. Here, we report the first example of PECL with the model [Ru(bpy) 3 ] 2+ / benzoyl peroxide system at a bare p-type Si photocathode. The reported PECL system, which allows to notably decrease the cathodic potential required for ECL generation should open new opportunities for imaging and light-addressable devices.

Figure 1 .

 1 Figure 1. a) Scheme showing the photoinduced charge transfer process and the reaction mechanism occurring at the Si photocathode, initiated by the absorption of IR light (λLED) and leading to the emission of ECL (λECL). b) Normalized spectra of: emission of the LED used in this work (brown), PECL emission (red), and bandgap position of p-Si (blue). c) Scheme of the photoelectrochemical setup employed for the study of PECL.

Figure 2 . 2 M

 22 Figure 2. a) CVs recorded under IR illumination on p-Si (red) and in the dark on p-Si (black) and on n + -Si (blue). b) Corresponding ECL intensity profiles. Scan rate: 50 mV s -1 . c) ECL spectra recorded as a function of potential recorded in the dark on n + -Si (blue) and under IR illumination on p-Si (red). d) Chronoamperogram recorded at -1.6 V at p-Si while imposing successive ON/OFF cycles with the LED. e) Corresponding ECL intensity profiles. The measurements were performed in 1 mM [Ru(bpy)3] 2+ + 10 mM BPO + 0.2 M TBAPF6 in acetonitrile.

Acknowledgements

This work was funded by ANR (LiCORN, ANR-20-CE29-0006). J. Y. acknowledges the China Scholarship Council for her PhD fellowship. N. S. and G. X. thank the support from the CAS President's International Fellowship Initiative (PIFI).

Conflicts of interest

There are no conflicts to declare.


Ryma Boumazouza
email: boumazouza@cril.fr

Fahima Cheikh-Alili

Bertrand Mazure
email: bertrand.mazure@univ-artois.fr

Karim 2021 Tabia
email: karim.tabia@univ-artois.fr

ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanations

Keywords: Computing methodologies → Artificial intelligence, Machine learning XAI, Symbolic explanations, Score-based explanation, Model-Agnostic, Satisfiability testing

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

In the last decades, the growth of data and widespread usage of Machine Learning (ML) in multiple sensitive fields (e.g. healthcare, criminal justice) and industries emphasized the need for explainability methods. These latter can be grouped into pre-model (ante-hoc), in-model, and post-model (post-hoc). We mainly focus on posthoc methods where we distinguish two types of explanations: [START_REF] Abío | A parametric approach for smaller and better encodings of cardinality constraints[END_REF] symbolic explanations (e.g. [START_REF] Shih | A Symbolic Approach to Explaining Bayesian Network Classifiers[END_REF], [START_REF] Ignatiev | On Relating Explanations and Adversarial Examples[END_REF]) that are based on symbolic representations used for explanation, verification and diagnosis purposes ( [START_REF] Reiter | A theory of diagnosis from first principles[END_REF], [START_REF] Rymon | An se-tree-based prime implicant generation algorithm[END_REF], [START_REF] Ignatiev | On Relating Explanations and Adversarial Examples[END_REF]), and (2) numerical feature-based methods that provide insights into how much each feature contributed to an outcome (e.g. SHAP [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF], LIME [START_REF] Tulio Ribeiro | Why should i trust you?" Explaining the predictions of any classifier[END_REF]). Intuitively, these two categories of approaches try to answer two different types of questions: Symbolic explanations tell why a model predicted a given label for an instance (eg. sufficient reasons) or what would have to be modified in an input instance to have a different outcome (counterfactuals). Numerical approaches, on the other hand, attempt to answer the question to what extent does a feature influence the prediction.

The existing symbolic explainability methods are model-specific (can only be applied to specific models for which they are intended) and cannot be applied agnostically to any model, which is their main limitation. In the other hand, feature-based methods such as Local Interpretable Model-Agnostic Explanations (LIME) [START_REF] Tulio Ribeiro | Why should i trust you?" Explaining the predictions of any classifier[END_REF] and SHapley Additive exPlanations (SHAP) [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF] provide the features' importance values for a particular prediction. These values provide an overall information on the contribution of features individually but do not really allow answering certain questions such as: "What are the feature values which are sufficient in order to trigger the prediction whatever the values of the other variables? " or "Which values are sufficient to change in the instance 𝑥 to have a different prediction?". This type of questions is fundamental for the understanding, and, above all, for the explanations to be usable. For example, if a user's application is refused, the user will naturally ask the question: "What must be changed in my application to be accepted? ". We cannot answer this question in a straightforward manner with the features-based explanations. Thus, the major objective of our contribution is to provide both symbolic explanations and scorebased ones for a better understanding and usability of explanations. It is declarative and does not require the implementation of specific algorithms since its based on well-known Boolean satisfiability concepts, allowing to exploit the strengths of modern SAT solvers. We model our explanation enumeration problem and use modern SAT technologies to enumerate the explanations. The approach provides two complementary types of symbolic explanations for the prediction of a data instance 𝑥: Sufficient Reasons (𝑆𝑅 𝑥 for short) and Counterfactuals (𝐶𝐹 𝑥 for short). In addition, it provides score-based explanations allowing to assess the influence of each feature on the outcome. The main contributions of our paper are :

(1) A declarative and model-agnostic approach allowing to provide 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 explanations based on SAT technologies ; (2) A set of fine-grained properties allowing to analyze and select explanations and a set of scores allowing to assess the relevance of explanations and features w.r.t the suggested properties ;

(3) An experimental evaluation providing an evidence of the feasibility and efficiency of the proposed approach ;

PRELIMINARIES AND NOTATIONS

Let us first formally recall some definitions used in the remainder of this paper. For the sake of simplicity, the presentation is limited to binary classifiers with binary features. We explain negative predictions where the outcome is 0 within the paper but the approach applies similarly1 to explain positive predictions. A decision function describes the classifier's behavior independently from the way it is implemented. We define it as a function 𝑓 : 𝑋 → 𝑌 mapping each instantiation 𝑥 of 𝑋 to 𝑦=𝑓 (𝑥). A data instance 𝑥 is the feature vector associated with an instance of interest whose prediction from the ML model is to be explained. We use interchangeably in this paper 𝑓 to refer to the classifier and its decision function.

Definition 2.2. (SAT : The Boolean Satisfiability problem)

Usually called SAT, the Boolean satisfiability problem is the decision problem, which, given a propositional logic formula, determines whether there is an assignment of propositional variables that makes the formula true.

The logic formulae are built from propositional variables and Boolean connectors "AND" (∧), "OR" (∨), "NOT" (¬). A formula is satisfiable if there is an assignment of all variables that makes it true. It is said inconsistent or unsatisfiable otherwise. For example, the formula (𝑥 1 ∧ 𝑥 2 ) ∨ ¬𝑥 1 where 𝑥 1 and 𝑥 2 are Boolean variables, is satisfiable since if 𝑥 1 takes the value false, the formula evaluates to true. A complete assignment of variables making a formula true is called a model while a complete assignment making it false is called a counter-model. Definition 2.3. (CNF (Clausal Normal Form)) A CNF is a set of clauses seen as a conjunction. A clause is a formula composed of a disjunction of literals. A literal is either a Boolean variable 𝑝 or its negation ¬𝑝. A quantifier-free formula is built from atomic formulae using conjunction ∧, disjunction ∨, and negation ¬. An interpretation 𝜇 assigns values from {0, 1} to every Boolean variable. Let Σ be a CNF formula, 𝜇 satisfies Σ iff 𝜇 satisfies all clauses of Σ.

Over the last decade, many achievements have been made to modern SAT solvers2 that can handle now problems with several million clauses and variables, allowing them to be efficiently used in many applications. Note that we rely on SAT-solving to explain a black-box model where we encode the problems of generating our symbolic explanations as two common problems related to satisfiability testing which are enumerating minimal reasons why a formula is inconsistent and minimal changes to a formula to restore the consistency. Indeed, in the case of an unsatisfiable CNF, we can analyze the inconsistency by enumerating sets of clauses causing the inconsistency (called Minimal Unsatisfiable Subsets and noted MUS for short), and other sets of clauses allowing to restore its consistency (called Minimal Correction Subsets, MCS for short). The enumeration of MUS/MCS are well-known problems dealt with in many areas such as knowledge base reparation. Several approaches and tools have been proposed in the SAT community for their generation (e.g. [START_REF] Grégoire | Boosting a Complete Technique to Find MSS and MUS Thanks to a Local Search Oracle[END_REF][START_REF] Mark | Algorithms for computing minimal unsatisfiable subsets of constraints[END_REF]).

ASTERYX: A GLOBAL OVERVIEW

Our approach is based on associating a symbolic representation that is (almost) equivalent to the decision function of the model to explain. An overview of our approach is depicted on Figure 1. Given a classifier 𝑓 , our approach proceeds as follows:

• Step 1 (Encoding into CNF the classifier): This comes down to associating an equivalent symbolic representation Σ 𝑓 to 𝑓 . Σ 𝑓 will serve to generate symbolic explanations in the next step. The encoding is done either using model encoding algorithms if available and if the encoding is tractable, or using a surrogate approach as described in Section 4. • Step 2 (SAT-based modeling of the explanation enumeration problem): Once we have the CNF representation Σ 𝑓 and the input instance 𝑥 whose prediction by 𝑓 is to be explained, we model the explanation generation task as a partial maximum satisfiability problem, also known as Partial Max-SAT [START_REF] Biere | Handbook of satisfiability[END_REF]. This step, presented in Section 5, aims to provide two types of symbolic explanations: 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 .

They respectively correspond to Minimal Unsatisfiable Subsets (MUS) and Minimal Correction Subsets (MCS) in the SAT terminology. • Step 3 (Explanation and feature relevance scoring): This step aims to assess the relevance of explanations by associating scores evaluating those explanations with regard to a set of properties presented in Section 6. Moreover, this step allows to assess the relevance of features using scoring functions and to evaluate their individual contributions to the outcome. The following sections provide insights for each step of our approach.

ENCODING THE CLASSIFIER INTO CNF

This corresponds to Step 1 in our approach and it aims to encode the input ML model 𝑓 into CNF in order to use SAT-solving to enumerate our symbolic explanations. Two cases are considered: Either an encoding of classifier 𝑓 into an equivalent symbolic representation exists (non agnostic case), in which case we can use it, or we consider the classifier 𝑓 as a black-box and we use a surrogate model approach to approximate it in the vicinity of the instance to explain 𝑥 (agnostic case). A direct encoding of the classifier 𝑓 into CNF is possible for some machine learning models such as Binarized Neural Networks (BNNs) [START_REF] Narodytska | Verifying properties of binarized deep neural networks[END_REF] and Naive and Latent-Tree Bayesian networks [START_REF] Shih | Compiling Bayesian Network Classifiers into Decision Graphs[END_REF]. We mainly focus in this paper on the agnostic option used when no direct CNF encoding exists for 𝑓 or if the encoding is intractable.

Surrogate model encoding into CNF

We propose an approach using a surrogate model 𝑋1 handicapped-infants 𝑋2 water-project-cost-sharing 𝑋3 adoption-of-the-budget-resolution 𝑋4 physician-fee-freeze 𝑋5 el-salvador-aid 𝑋6 religious-groups-in-schools 𝑋7 anti-satellite-test-ban 𝑋8 aid-to-nicaraguan-contras

𝑓

𝑋9

mx-missile 𝑋10 immigration 𝑋11 synfuels-corporation-cutback 𝑋12 education-spending 𝑋13 superfund-right-to-sue 𝑋14 crime 𝑋15 duty-free-exports 𝑋16 export-administration-act-south-africa Assume an input instance 𝑥=(1,1,1,0,0,0,1,1,1,0,0,0,0,1,0,1) whose prediction is to be explained. As a surrogate model, we trained a random forest classifier RF 𝑓 composed of 3 decision trees (decision tree 1 to 3 from left to right in Fig. 2) on the vicinity of the input sample 𝑥. In this example, RF 𝑓 achieved an accuracy of 91.66% (RF 𝑓 is said locally faithful to 𝑓 as it has a high accuracy in the vicinity of the instance 𝑥 to explain).

The CNF encoding of a classifier 𝑓 (or its surrogate 𝑓 𝑆 ) should guarantee the equivalence of the two representations stated as follows :

Definition 4.2. (Equivalence of a classifier and its CNF encoding) A binary classifier 𝑓 (resp. 𝑓 𝑆 ) is said to be equivalently encoded as a CNF Σ 𝑓 (resp. Σ 𝑓 𝑆 ) if the following condition is fulfilled:

𝑓 (𝑥)=1 (resp. 𝑓 𝑆 (𝑥)=1) iff 𝑥 is a model of Σ 𝑓 (resp. Σ 𝑓 𝑆 ).
Namely, data instances 𝑥 predicted positively (𝑓 (𝑥)=1) by the classifier are models of the CNF encoding the classifier. Similarly,

CNF encoding of random forests

When we adopt the surrogate approach and use a random forest 𝑓 𝑆 to agnostically approximate a classifier 𝑓 , encoding the random forest in CNF amounts to encoding the decision trees individually and then encoding the combination rule (majority voting rule).

-Encode in CNF every decision tree: The internal nodes of a decision tree 𝐷𝑇 𝑖 represent a binary test on one of the features 4 . The leaves of a decision tree, each is annotated with the predicted class (namely, 0 or 1). A decision tree in our case represents a Boolean function.

As shown on Example 4.3, the Boolean function encoded by a decision tree can be captured in CNF as the conjunction of the negation of paths leading from the root node to leaves labelled 0.

-Encode in CNF the combination rule: Let 𝑦 𝑖 be a Boolean variable capturing the truth value of the CNF associated to a decision tree 𝐷𝑇 𝑖 . Hence, the majority rule used in random forests to combine the predictions of 𝑚 decision trees can be seen as a cardinality constraint 5 [29] that can be stated as follows:

𝑦 ⇔ ∑ 𝑖=1..𝑚 𝑦 𝑖 ≥ 𝑡, (1)
where 𝑡 is a threshold (usually 𝑡= 𝑚 2 ). Cardinality constraints have many CNF encodings (e.g. [START_REF] Abío | A parametric approach for smaller and better encodings of cardinality constraints[END_REF][START_REF] Bailleux | Efficient CNF encoding of boolean cardinality constraints[END_REF][START_REF] Sinz | Towards an optimal CNF encoding of boolean cardinality constraints[END_REF]). To form the CNF corresponding to the entire random forest, it suffices to conjuct the 𝑚 CNFs associated to the equivalences between 𝑦 𝑖 and the CNF of the decisions trees, and, the CNF of the combination rule.

𝐷𝑇 1 𝑦 1 ⇔ (𝑋 5 ) ∧ (¬𝑋 5 ∨ ¬𝑋 15 ∨ 𝑋 4 ) 𝐷𝑇 2 𝑦 2 ⇔ (𝑋 4 ) ∧ (¬𝑋 4 ∨ ¬𝑋 11 ∨ 𝑋 16 ) 𝐷𝑇 3 𝑦 3 ⇔ (𝑋 9 ∨ 𝑋 14 ) ∧ (𝑋 9 ∨ ¬𝑋 14 ∨ 𝑋 5 ) ∧ (¬𝑋 9 ∨ 𝑋 12 ) ∧ (¬𝑋 9 ∨ ¬𝑋 12 ∨ ¬𝑋 11 ) Majority vote 𝑦 ⇔ (𝑦 1 ∧𝑦 2 ) ∨ (𝑦 1 ∧𝑦 3 ) ∨ (𝑦 2 ∧𝑦 3 ) ∨ (𝑦 1 ∧𝑦 2 ∧𝑦 3 )
In this example, each decision tree (𝐷𝑇 𝑖 , 𝑖=1..3) represents a Boolean function whose truth value is captured by Boolean variable 𝑦 𝑖 . The random forest 𝑅𝐹 𝑓 Boolean function is captured by the variable 𝑦. Note that the encoding of 𝑅𝐹 𝑓 is provided in this example in propositional logic in order to avoid heavy notations. Direct encoding to CNF could easily be obtained using for example Tseitin Transformation [START_REF] Grigori S Tseitin | On the complexity of derivation in propositional calculus[END_REF].

GENERATING SUFFICIENT REASONS AND COUNTERFACTUAL EXPLANATIONS

In this section, we present 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 as well as the SAT-based setting we use to generate such explanations where the input is the CNF encoding of a classifier Σ 𝑓 and an input data instance Σ 𝑥 whose prediction is to be explained.

STEP 2: A SAT-based setting for the enumeration of symbolic explanations

Recall that we are interested in two complementary types of symbolic explanations: the sufficient reasons (𝑆𝑅 𝑥 ) which lead to a given prediction and the counterfactuals (𝐶𝐹 𝑥 ) allowing to know minimal changes to apply on the data instance 𝑥 to obtain a different outcome. Our approach to enumerate these two types of explanations is based on two very common concepts in SAT which are MUS and MCS that we will define formally in the following. To restrict the explanations only to clauses that concern the input data 𝑥 and do not include clauses that concern the encoding of the classifier, we use a variant of the SAT problem called Partial-Max SAT [START_REF] Biere | Handbook of satisfiability[END_REF] which can be efficiently solved by the existing tools implementing the enumeration of MUSes and MCSes such as the tool in [START_REF] Grégoire | Boosting MCSes Enumeration[END_REF].

A Partial Max-SAT problem is composed of two disjoint sets of clauses where Σ 𝐻 denotes the hard clauses (those that could not be relaxed) and Σ 𝑆 denotes the soft ones (those that could be relaxed). In our modeling, the set of hard clauses corresponds to Σ 𝑓 and the soft clauses to Σ 𝑥 representing the CNF encoding of the data instance 𝑥 whose prediction 𝑓 (𝑥) is to be explained. Let Σ 𝑥 be the soft clauses, defined as follows :

• Each clause 𝛼 ∈ Σ 𝑥 is composed of exactly one literal (∀𝛼 ∈ Σ 𝑥 , |𝛼 | = 1). • Each literal representing a Boolean variable of Σ 𝑥 corre- sponds to a Boolean variable {𝑋 𝑖 ∈ 𝑋 }.
Recall that since the classifier 𝑓 is equivalently encoded to Σ 𝑓 , then a negative prediction 𝑓 (𝑥)=0 corresponds to an unsatisfiable CNF Σ 𝑓 ∪Σ 𝑥 . Now, given an unsatisfiable CNF Σ 𝑓 ∪Σ 𝑥 , it is possible to identify the subsets of Σ 𝑥 responsible for the unsatisfiability (corresponding to reasons of the prediction 𝑓 (𝑥)=0), or the ones allowing to restore the consistency of Σ 𝑓 ∪Σ 𝑥 (corresponding to counterfactuals allowing to flip the prediction and get 𝑓 (𝑥)=1).

Sufficient Reason Explanations (𝑆𝑅 𝑥 )

We are interested here in identifying minimal reasons why the prediction is 𝑓 (𝑥)=0. This is done by identifying subsets of clauses causing the inconsistency of the CNF Σ 𝑓 ∪Σ 𝑥 (recall that the prediction 𝑓 (𝑥) is captured by the truth value of Σ 𝑓 ∪Σ 𝑥 ). Such subsets of clauses encoding the input 𝑥 are sufficient reasons for the prediction being negative. We formally define the SR 𝑥 explanations as follow:

Definition 5.1. (SR 𝑥 explanations) Let 𝑥 be a data instance and 𝑓 (𝑥)=0 its prediction by the classifier 𝑓 . A sufficient reason explanation x of 𝑥 is such that:

i. x ⊆ 𝑥 (x is a part of 𝑥) ii. ∀ x, x ⊂ x : 𝑓 ( x)=𝑓 (𝑥) (x

suffices to trigger the prediction)

iii. There is no partial instance x ⊂ x satisfying i and ii (minimality) Intuitively, a sufficient reason x is defined as the part of the data instance 𝑥 such that x is minimal and causes the prediction 𝑓 (𝑥)=0. We now define Minimal Unsatisfiable Subsets :

Definition 5.2. (MUS) A Minimal Unsatisfiable Subset (MUS) is a minimal subset Γ of clauses of a CNF Σ such that ∀ 𝛼 ∈ Γ, Γ\{𝛼 } is satisfiable.
Clearly, a MUS for Σ 𝑓 ∪Σ 𝑥 comes down to a subset of soft clauses, namely a part of 𝑥 that is causing the inconsistency, hence the prediction 𝑓 (𝑥)=0.

Proposition 5.3. Let 𝑓 be a classifier, let Σ 𝑓 be its CNF representation. Let also 𝑥 be a data instance predicted negatively (𝑓 (𝑥)=0) and let Σ 𝑓 ∪Σ 𝑥 be the corresponding Partial Max-SAT encoding. Let 𝑆𝑅(𝑥, 𝑓 ) be the set of sufficient reasons of 𝑥 wrt. 𝑓 . Let MUS(Σ 𝑓 ,𝑥 ) be the set of MUSes of Σ 𝑓 ∪Σ 𝑥 . Then:

∀x ⊆ 𝑥, x ∈ 𝑆𝑅(𝑥, 𝑓 ) ⇐⇒ x ∈ 𝑀𝑈 𝑆 (Σ 𝑓 ,𝑥 ) (2)
Proposition 5.3 states that each MUS of the CNF Σ 𝑓 ∪Σ 𝑥 is a 𝑆𝑅 𝑥 for the prediction 𝑓 (𝑥)=0 and vice versa. The proof is straightforward. It suffices to remember that the decision function of 𝑓 is equivalently encoded by Σ 𝑓 and that the definition of a MUS on Σ 𝑓 ∪Σ 𝑥 corresponds exactly to the definition of an 𝑆𝑅 𝑥 for 𝑓 (𝑥).

Example 5.4 (Example 4.3 continued). Given the CNF Σ 𝑓 ∪Σ 𝑥 associated to 𝑅𝐹 𝑓 from Example 4.3 and the input 𝑥=(1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1), we enumerate the 𝑆𝑅 𝑥 for 𝑓 (𝑥)=0 (𝑥 is predicted as Democrat). There are three 𝑆𝑅 𝑥 :

• 𝑆𝑅 𝑥 1="𝑋 4 =0 AND 𝑋 5 =0" (meaning that if the features physicianfee-freeze (𝑋 4 ) and el-salvador-aid (𝑋 5 ) are set to 0, then the prediction is 0) ; • 𝑆𝑅 𝑥 2="𝑋 12 =0 AND 𝑋 5 =0" ; • 𝑆𝑅 𝑥 3="𝑋 4 =0 AND 𝑋 12 =0 AND 𝑋 9 =1" ; It is easy to check for instance that if 𝑋 4 =0 and 𝑋 5 =0 then 𝐷𝑇 1 and 𝐷𝑇 2 of Fig. 2 predict 0 leading the random forest to predict 0.

Counterfactual Explanations (𝐶𝐹 𝑥 )

For many applications, knowing the reasons for a prediction is not enough, and one may need to know what changes in the input need to be made to get an alternative outcome. Let us formally define the concept of counterfactual explanation. Definition 5.5. (CF 𝑥 Explanations) Let 𝑥 be a complete data instance and 𝑓 (𝑥) its prediction by the decision function of 𝑓 . A counterfactual explanation x of 𝑥 is such that:

i. x ⊆ 𝑥 (x is a part of x) ii. 𝑓 (𝑥 [ x])= 1-𝑓 (𝑥) (prediction inversion) iii. There is no x ⊂ x such that 𝑓 (𝑥 [ x])=𝑓 (𝑥 [ x]) (minimality)
In definition 5.5, the term 𝑥 [ x] denotes the data instance 𝑥 where variables included in x are inverted. In our approach, CF 𝑥 are enumerated thanks to the Minimal Correction Subset enumeration [START_REF] Grégoire | Boosting MCSes Enumeration[END_REF].

Definition 5.6. (MSS) A Maximal Satisfiable Subset (MSS) Φ of a CNF Σ is a subset (of clauses) Φ ⊆ Σ that is satisfiable and such that ∀ 𝛼 ∈ Σ \ Φ, Φ ∪ {𝛼} is unsatisfiable. Definition 5.7. (MCS) A Minimal Correction Subset Ψ of a CNF Σ is a set of formulas Ψ ⊆ Σ whose complement in Σ, i.e., Σ \ Ψ, is a maximal satisfiable subset of Σ.
Following our modeling, an MCS for Σ 𝑓 ∪Σ 𝑥 comes down to a subset of soft clauses denoted x, namely a part of 𝑥 that is enough to remove (or reverse) in order to restore the consistency, hence to flip the prediction 𝑓 (𝑥)=0 to 𝑓 (𝑥 [ x])=1.

Proposition 5.8. Let 𝑓 be the decision function of the classifier, let Σ 𝑓 be its CNF representation. Let also 𝑥 be a data instance predicted negatively (𝑓 (𝑥) = 0) and Σ 𝑓 ∪Σ 𝑥 the corresponding Partial Max-SAT encoding. Let 𝐶𝐹 (𝑥, 𝑓 ) be the set of counterfactuals of 𝑥 wrt. 𝑓 . Let MCS(Σ 𝑓 ,𝑥 ) the set of MCSs of Σ 𝑓 ∪ Σ 𝑥 . Then:

∀x ⊆ 𝑥, x ∈ 𝐶𝐹 (𝑥, 𝑓 ) ⇐⇒ x ∈ 𝑀𝐶𝑆 (Σ 𝑓 ,𝑥 ) (3)
Proposition 5.8 states that each MCS of the CNF Σ 𝑓 ∪Σ 𝑥 represents a 𝐶𝐹 x⊆𝑥 for the prediction 𝑓 (𝑥)=0 and vice versa.

Example 5.9 (Example 5.4 cont'd). Given the CNF Σ 𝑓 ∪Σ 𝑥 associated to 𝑅𝐹 𝑓 from Example 4.3 and the input 𝑥=(1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1), we enumerate the counterfactual explanations to identify the minimal changes to alter the voteDemocrat to Republican. There are four CF 𝑥 :

• 𝐶𝐹 𝑥 1="𝑋 4 =0 AND 𝑋 12 =0" (meaning that in order to force the prediction to be 1, it is enough to alter 𝑥 by setting only the variables physician-fee-freeze (𝑋 4 ) and education-spending (𝑋 12 ) to 1 while keeping the remaining values unchanged); • 𝐶𝐹 𝑥 2="𝑋 5 =0 AND 𝑋 12 =0" ; • 𝐶𝐹 𝑥 3="𝑋 5 =0 AND 𝑋 9 =1" ; • 𝐶𝐹 𝑥 4="𝑋 4 =0 AND 𝑋 5 =0" ; It is easy to see that the four CF 𝑥 allow to flip the negative prediction associated to 𝑥. Indeed, in Fig. 3, the pink lines show the branches of the trees that are fixed by the current input instance 𝑥. Clearly, according to 𝐶𝐹 𝑥 1="𝑋 4 =0 AND 𝑋 12 =0", if we set 𝑋 4 =1 and 𝑋 12 =1 then this will force 𝐷𝑇 2 and 𝐷𝑇 3 to predict 1 making the prediction of the random forest flip to 1.

NUMERICALLY ASSESSING THE RELEVANCE OF SYMBOLIC EXPLANATIONS AND FEATURES

The number of symbolic explanations from Step 2 can be large and a question then arises which explanations to choose or which explanations are most relevant? 6 We try to answer this question by defining some desired properties of an explanation score. Hence, in order to select the most relevant 7 explanations and features, we propose to use some natural properties and propose some examples of scoring functions to assign a numerical score to an explanation and to a feature value of the input data.

Properties of symbolic explanations and scoring functions

Let us use 𝐸 (𝑥, 𝑓 ) to denote the set of explanations (either SR 𝑥 or CF 𝑥 ) for an input instance 𝑥 predicted negatively by the classifier 𝑓 . An explanation is denoted by 𝑒 𝑖 where 𝑖 = 1, .., |𝐸 (𝑥, 𝑓 )| and 𝐸 (𝑥, 𝑓 ) is a non empty set. The neighborhood of 𝑥 within the radius 𝑟 is formally defined as 𝑉 (𝑥, 𝑟 ): {𝑣 ∈ 𝑋 | diff(𝑥, 𝑣) ⩽𝑟 } 8 . Given an explanation 𝑒 𝑖 , let size(𝑒 𝑖 ) denote the number of variables composing it, and Extent(𝑒 𝑖 , 𝑥, 𝑟 ) be the set of data instances defined as : {𝑣 ∈𝑉 (𝑥, 𝑟 ) | 𝑓 (𝑣)=𝑓 (𝑥) and for 𝑒 𝑖 ∈𝐸 (𝑣, 𝑓 )}. Intuitively, Extent(𝑒 𝑖 , 𝑥, 𝑟 ) denotes the set of data instances from the neighborhood of 𝑥 that are negatively predicted by 𝑓 and sharing the explanation 𝑒 𝑖 .

In the following we propose three natural properties that can be used to capture some aspects of our symbolic explanations :

-Parsimony (PAR) : The parsimony is a natural property allowing to select the simplest or shortest explanations (namely, explanations involving less features). Hence, the parsimony score of an 6 An inconsistent Boolean formula can potentially have a large set of explanations (MUSes and MCSes). More precisely, for a knowledge base containing 𝑘 clauses, the number of MUSes and MCSes can be in the worst case exponential in 𝑘 [START_REF] Mark | Algorithms for computing minimal unsatisfiable subsets of constraints[END_REF]. 7 Of course, the relevance depends on the user's interpretation and the context. 8 diff(x,v) denotes a distance measure that returns the number of different feature values between 𝑥 and 𝑣.

explanation 𝑒 𝑖 should be inversely proportional to it's size. Formally, given a data instance 𝑥, its set of explanations 𝐸 (𝑥, 𝑓 ) : For two explanations 𝑒 1 and 𝑒 2 from 𝐸 (𝑥, 𝑓 ): PAR(𝑒 1 )> PAR(𝑒 2 ) iff size(𝑒 1 )<size(𝑒 2 ) . An example of a scoring function satisfying the parsimony property is :

𝑆 P A R (𝑒 𝑖 ) = 1 𝑠𝑖𝑧𝑒 (𝑒 𝑖 ) (4)
-Generality (GEN ) : This property aims to reflect how much an explanation can be general to a multitude of data instances, or in the opposite, reflect how much an explanation is specific to the instance. Intuitively, the generality of an explanation should be proportional to the number of data instances it explains. Given a data instance 𝑥, its set of explanations 𝐸 (𝑥, 𝑓 ), its neighborhood 𝑉 (𝑥, 𝑟 ) and two explanations 𝑒 1 and 𝑒 2 from 𝐸 (𝑥, 𝑓 ): GEN (𝑒 1 )> GEN (𝑒 2 ) iff |Extent(𝑒 1 , 𝑥, 𝑟 )|>|Extent(𝑒 2 , 𝑥, 𝑟 )|. An example of a scoring function capturing this property is :

𝑆 G E N (𝑥, 𝑟, 𝑒 𝑖 ) = |𝐸𝑥𝑡𝑒𝑛𝑡 (𝑒 𝑖 , 𝑥, 𝑟 )| |𝑉 (𝑥, 𝑟 )| (5)
Intuitively, this scoring function assesses the proportion of data instances in the neighborhood of the instance 𝑥 that are negatively predicted and that share the explanation 𝑒 𝑖 .

-Explanation responsibility (RESP) : This property allows to answer the question how much an explanation is responsible for the current prediction. Intuitively, if there is a unique explanation, then this latter is fully responsible. Hence, the responsibility of an explanation should be inversely proportional to the number of explanations in 𝐸 (𝑥, 𝑓 ). Given two different data instances 𝑥 1 and 𝑥 2 and their explanation sets 𝐸 (𝑥 1 , 𝑓 ) and 𝐸 (𝑥 2 , 𝑓 ) respectively and 𝑒 𝑘 ∈ 𝐸 (𝑥 1 , 𝑓 )∩𝐸 (𝑥 2 , 𝑓 ): RESP(𝑥 1 , 𝑒 𝑘 )< RESP(𝑥 2 , 𝑒 𝑘 ) iff |𝐸 (𝑥 1 , 𝑓 )|>|𝐸 (𝑥 2 , 𝑓 )|. For a given data instance 𝑥, the responsibility of 𝑒 𝑖 ∈𝐸 (𝑥, 𝑓 ) could be evaluated using the following scoring function :

𝑆 R E S P (𝑥, 𝑒 𝑖 ) = 1 |𝐸 (𝑥, 𝑓 )| (6)
Note that the scoring function of Eq. 6 assigns the same score to every explanation in 𝐸 (𝑥, 𝑓 ). To decide among the explanations in 𝐸 (𝑥, 𝑓 ), one can calculate a responsibility score for 𝑒 𝑖 in the neighborhood of 𝑥. An example of a scoring function capturing this property, would be :

𝑆 R E S P (𝑥, 𝑟, 𝑒 𝑖 ) = max (𝑆 R E S P (𝑣, 𝑒 𝑖 )) 𝑣 ∈𝑉 (𝑥,𝑟 ) |𝑒 𝑖 ∈𝐸 (𝑣,𝑓 ) (7)
These properties make it possible to analyze and if necessary select or order the symbolic explanations according to a particular property. Of course, we can define other properties or variants of these properties (e.g. relative parsimony to reflect the parsimony of one explanation compared to the parsimony of the rest of the explanations). The properties can have a particular meaning or a usefulness depending on the applications and users. It would be interesting to study the links and the interdependence between these properties. Let us now see properties allowing to assess the relevance of the features reflecting their contribution to the prediction.

Properties of features-based explanations and scoring functions

Let us define Cover(𝑋 𝑘 ,𝑥) as the set of explanations from 𝐸 (x, 𝑓 ) where the feature 𝑋 𝑘 is involved (namely Cover(𝑋 𝑘 ,𝑥)={𝑒 𝑖 |𝑋 𝑘 ∈𝑒 𝑖 for 𝑒 𝑖 ∈𝐸 (𝑥, 𝑓 )}). We consider the following properties :

-Feature Involvement (F I) : This property is intended to reflect the extent of involvement of a feature within the set of explanations. The intuition is that a feature that participates in several explanations of the same instance 𝑥 should have a higher importance compared to a less involved feature. Given a data instance 𝑥, its set of explanations 𝐸 (𝑥, 𝑓 ), and two features 𝑋 1 and 𝑋 2 :

F I(𝑋 1 ,𝑥)> F I(𝑋 2 ,𝑥) iff |Cover(𝑋 1 ,𝑥)|>|Cover(𝑋 2 ,𝑥)|.
An example of a scoring function capturing this property is :

𝑆 F I (𝑋 𝑘 , 𝑥) = |𝐶𝑜𝑣𝑒𝑟 (𝑋 𝑘 , 𝑥)| |𝐸 (𝑥, 𝑓 )| (8)
-Feature Generality (F G) : This property captures at what extent a feature is frequently involved in explaining instances in the vicinity of the sample to explain. Given a sample 𝑥, its vicinity 𝑉 (𝑥, 𝑟 ) and the explanation set 𝐸 (𝑉 (𝑥, 𝑟 ), 𝑓 ) defined as 𝐸 (𝑣, 𝑓 )

𝑣 ∈𝑉 (𝑥,𝑟 )

, we have:

F G(𝑋 1 )> F G(𝑋 2 ) iff | 𝐶𝑜𝑣𝑒𝑟 (𝑋 1 , 𝑣)| 𝑣 ∈𝑉 (𝑥,𝑟 ) > | 𝐶𝑜𝑣𝑒𝑟 (𝑋 2 , 𝑣)| 𝑣 ∈𝑉 (𝑥,𝑟 )
. An example of a scoring function capturing this property could be :

𝑆 F G (𝑋 𝑘 ) = | 𝐶𝑜𝑣𝑒𝑟 (𝑋 𝑘 , 𝑣)| 𝑣 ∈𝑉 (𝑥,𝑟 ) |𝐸 (𝑉 (𝑥, 𝑟 ), 𝑓 )| (9)
-Feature Responsibility (F R) : This property is intended to reflect the responsibility or contribution of a feature 𝑋 𝑖 within the set of symbolic explanations of 𝑥. Intuitively, the responsibility of a feature should be inversely proportional to the size of the explanations where it is involved (the shortest the explanation, the highest the responsibility value of its variables). Given two features 𝑋 1 , 𝑋 2 with non empty covers:

F R(𝑋 1 )> F R(𝑋 2 ) iff 𝑎𝑔𝑔𝑟 (𝑠𝑖𝑧𝑒 (𝑒 𝑗 )) 𝑒 𝑗 ∈𝐶𝑜𝑣𝑒𝑟 (𝑋 1 ,𝑥) < 𝑎𝑔𝑔𝑟 (𝑠𝑖𝑧𝑒 (𝑒 𝑗 )) 𝑒 𝑗 ∈𝐶𝑜𝑣𝑒𝑟 (𝑋 2 ,𝑥)
where 𝑎𝑔𝑔𝑟 stands for an aggregation function (e.g. min, max, 𝐴𝑉 𝐺, etc.). An example of a scoring function satisfying this property is :

𝑆 F R (𝑋 𝑘 ) = 1 𝐴𝑉 𝐺 (𝑠𝑖𝑧𝑒 (𝑒 𝑗 ))
𝑒 𝑗 ∈𝐶𝑜𝑣𝑒𝑟 (𝑋 𝑘 ,𝑥) [START_REF] Grégoire | Boosting MCSes Enumeration[END_REF] Note that this is a non-exhaustive list of properties that one could be interested in order to select and rank explanations or features according to their contributions. In addition to the different explanation scores presented above, one can aggregate them (e.g., by averaging) to get an overall score depending on the user needs.

EMPIRICAL EVALUATION 7.1 Experimentation set-up

We evaluated our approach on a widely used standard ML dataset: the MNIST 9 handwritten digit database composed of 70,000 images of size 28 × 28 pixels. The images were binarized using a threshold 𝑇 = 127. In addition, we used three other publicly available datasets 9 http://yann.lecun.com/exdb/mnist/ (SPECT, MONKS and Breast-cancer). We trained "one-vs-all" binary neural network (BNN) 10 classifiers on the MNIST database to recognize digits (0 to 9) using the pytorch implementation 11 of the Binary-Backpropagation algorithm BinaryNets [START_REF] Hubara | Binarized Neural Networks[END_REF]. Neural network classifiers were trained on the rest of the datasets. Those classifiers are considered as the input black-box models we are interested in explaining their outcomes.

All experiments have been conducted on Intel Core i7-7700 (3.60GHz ×8) processors with 32Gb memory on Linux.

Results

We report the following results by setting the following parameters 𝑛𝑏_𝑡𝑟𝑒𝑒𝑠 = 10 and 𝑚𝑎𝑥_𝑑𝑒𝑝𝑡ℎ = 24 for the random forest classifier trained on the vicinity of an input sample 𝑥 as the surrogate model. The experiments were conducted on an average of 1500 instances picked randomly from the MNIST database. The predictions are made using 12 the "one-vs-all" BNN classifiers trained to recognize the 0,2,5,6 and 8 digits. Due to the limited number of pages, we only present the results for radius 250 with an average of 200 neighbors around 𝑥 for MNIST. As for the rest, we consider all instances as neighbors (radius equal to the number of features).

Evaluating the CNF encoding feasibility. We report our results regarding the size of the generated CNF formulae. We use the Tseitin Transformation [START_REF] Grigori S Tseitin | On the complexity of derivation in propositional calculus[END_REF] to encode the propositional formulae into an equisatisfiable CNF formulae. Table 1 shows that the generated random forest classifiers provide interesting results in term of fidelity (high accuracy of the surrogate models) and tractability (size of the CNF encoding).In Table 1, the size of CNF is expressed as number of variables/number clauses. We can see that the number of variables and clauses of CNF formulae remains reasonable and easily handled by the current SAT-solvers which confirms the feasibility of the approach.

Evaluating the enumeration of symbolic explanations. The objective here is to assess the practical feasibility of the enumeration (scalability) of 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 explanations. For the enumeration of 𝐶𝐹 𝑥 , we use the EnumELSRMRCache tool 13 implementing the boosting algorithm for MCSes enumeration proposed in [START_REF] Grégoire | Boosting MCSes Enumeration[END_REF] 10 defined as a neural networks with binary weights and activations at run-time 11 available at: https://github.com/itayhubara/BinaryNet.pytorch 12 the results for the other digits are similar but can not be reported here because of space limitation 13 available at http://www.cril.univ-artois.fr/enumcs/ We observe within Table 2 that the average run-time remains reasonable (note that the times shown in Table 2 relate to the time taken to list all the explanations. The solver starts to find the first explanations very promptly) and that the approach is efficient in practice for medium size BNN classifiers (as shown in the experiments for BNNs with around 800 variables). We also observe that the number of 𝐶𝐹 𝑥 may be challenging for a user to understand, hence the need for scoring them to filter them out and find the ones with the strongest influence on the prediction.

Illustrating 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 explanations for MNIST data set. We trained two "one-vs-all" 14 BNNs 𝑓 8 and 𝑓 0 to recognize the eight and zero digits. They have respectively achieved an accuracy of 97% and 99%.

The "a" column in the different figures shows the input images (resp. representing the digit 5 and 1). Those data samples were negatively predicted. The model 𝑓 8 (resp. 𝑓 0 ) recognizes that the input image in the 1 𝑠𝑡 line (resp. the 2 𝑛𝑑 ) is not an 8-digit (resp. a 0-digit). Figure 4a shows an example of a single 𝑆𝑅 𝑥 explanation highlighting the 14 A "one-vs-all" BNN 𝑓 𝑖 returns a positive prediction for an input image representing the "i" digit, and negative one otherwise.

sufficient pixels for the models 𝑓 8 and 𝑓 0 to trigger a negative prediction. Figure 4b shows an example of 𝐶𝐹 𝑥 explanations showing the pixels to invert in the input images to make the models 𝑓 8 and 𝑓 0 predict them positively. In addition, one could recognize in the "c" column of Fig. 4b a pattern of the 8-digit for the first image, and 0 for the second. It gives us a kind of "pattern/template" of the images that the model would positively predict.

Figure 5 shows heatmaps corresponding to the Feature Involvement (FI) scores (column "b-c") and Feature Responsibility (FR) (column "d-e") scores of the different input variables implicated in the 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 . Visually, they are simpler, clearer and easier to understand and use. We used around 100 data samples to compare the most important features according to the F I score of our approach and those of SHAP ("f" column of Fig. 5). The results coincide from 20% to 46% of cases, which is visually confirmed in our figures.

RELATED WORKS

Explaining machine learning systems has been a hot research topic recently. There has been hundreds of papers on ML explainability but we will be focusing on the ones closely related to our work.

In the context of model-agnostic explainers where the learning function of the input model and its parameters are not known (black-box), we can cite some post-hoc explanations methods such as: LIME (Local Interpretable Model-agnostic Explanations) [START_REF] Tulio Ribeiro | Why should i trust you?" Explaining the predictions of any classifier[END_REF] which explain black-box classifiers by training an interpretable model 𝑔 on samples randomly generated in the vicinity of the data instance. We follow an approach similar to LIME, the difference is that we encode our surrogate model into a CNF to generate symbolic explanations. The authors in [START_REF] Tulio Ribeiro | Anchors: Highprecision model-agnostic explanations[END_REF] proposed a High-precision model agnostic explanations called ANCHOR. It is based on computing a decision rule linking the feature space to a certain outcome, and consider it as an anchor covering similar instances. Something similar is done in SHAP (SHapley Additive exPlanations) [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF] that provides explanations in the form of the game theoretically optimal called Shapley values. Due to its computational complexity, other model-specific versions have been proposed for linear models and deep neural networks (resp LinearSHAP and DeepSHAP) in [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF]. The main difference with this rule sets/feature-based explanation methods and the symbolic explanations we propose is that ours associates a score w.r.t to some relevance properties, in order to assess to what extent the measured entity is relevant as explanation or involved as features in the sufficient reasons or in the counterfactuals.

Recently, some authors propose symbolic and logic-based XAI approaches that can be used for different purposes [START_REF] Darwiche | Three Modern Roles for Logic in AI[END_REF]. We can distinguish the compilation-based approaches where Boolean decision functions of classifiers are compiled into some symbolic forms. For instance, in [START_REF] Chan | Reasoning about Bayesian Network Classifiers[END_REF][START_REF] Shih | A Symbolic Approach to Explaining Bayesian Network Classifiers[END_REF] the authors showed how to compile the decision functions of naive Bayes classifiers into a symbolic representation, known as Ordered Decision Diagrams (ODDs). We proposed in a previous work [START_REF] Boumazouza | A Symbolic Approach for Counterfactual Explanations[END_REF] an approach designed to equip such symbolic approaches [START_REF] Shih | A Symbolic Approach to Explaining Bayesian Network Classifiers[END_REF] with a module for counterfactual explainability. There are some ML models whose direct encoding into CNF is possible. For instance, the authors in [START_REF] Narodytska | Verifying properties of binarized deep neural networks[END_REF] proposed a CNF encoding for Binarized Neural Networks (BNNs) for verification purposes. In [START_REF] Shi | On Tractable Representations of Binary Neural Networks[END_REF], the authors propose a compilation algorithm of BNNs into tractable representations such as Ordered Binary Decision Diagrams (OB-DDs) and Sentential Decision Diagrams (SDDs). The authors in [START_REF] Shih | Compiling Bayesian Network Classifiers into Decision Graphs[END_REF] proposed algorithms for compiling Naive and Latent-Tree Bayesian network classifiers into decision graphs. In [START_REF] Audemard | On Tractable XAI Queries based on Compiled Representations[END_REF], the authors dealt with a set of explanation queries and their computational complexity once classifiers are represented with compiled representations. However, the compilation-based approaches are hardly applicable to large sized models, and remain strongly dependent on the type of classifier to explain (non agnostic). Our approach can use those compilation algorithms to represent the whole classifier when the encoding remains tractable, but in addition, we propose a local approximation of the original model using a surrogate model built on the neighborhood of the instance at hand.

Recent works in [START_REF] Ignatiev | Abductionbased explanations for machine learning models[END_REF][START_REF] Ignatiev | On Relating Explanations and Adversarial Examples[END_REF] deal with some forms of symbolic explanations referred to as abductive explanations (AXp) and contrastive explanations (CXp) using SMT oracles. In [START_REF] Ignatiev | SAT-Based Rigorous Explanations for Decision Lists[END_REF], the authors explain the prediction of decision list classifiers using a SAT-based approach. Explaining random forests and decision trees is dealt with for instance in [START_REF] Audemard | On Tractable XAI Queries based on Compiled Representations[END_REF] and [START_REF] Ignatiev | On Relating 'Why?' and 'Why Not?[END_REF][START_REF] Izza | On Explaining Decision Trees[END_REF] respectively. The main difference with our work, is that we are proposing an approach that goes from the model whose predictions are to be explained to its encoding and goes beyond the enumeration of symbolic explanations by defining some scoring functions w.r.t some relevance properties. Different explanation scores have been proposed in the literature. Authors in [START_REF] Bertossi | Declarative Approaches to Counterfactual Explanations for Classification[END_REF] used the counterfactual explanations to define an explanation responsibility score for a feature value in the input. In [START_REF] Bertossi | Score-Based Explanations in Data Management and Machine Learning[END_REF], the authors used the answer-set programming to analyze and reason about diverse alternative counterfactuals and to investigate the causal explanations and the responsibility score in databases.

CONCLUDING REMARKS AND DISCUSSIONS

We proposed a novel model agnostic generic approach to explain individual outcomes by providing two complementary types of symbolic explanations (sufficient reasons and counterfactuals) and scores-based ones. The objective of the approach is to explain the predictions of a black-box model by providing both symbolic and score-based explanations with the help of Boolean satisfiability concepts. The approach takes advantage of the strengths of already existing and proven solutions, and of the powerful practical tools for the generation of MCS/MUS. The proposed approach overcomes the complexity of encoding a ML classifier into an equivalent logical representation by means of a surrogate model to symbolically approximate the original model in the vicinity of the sample of interest. The presentation of the paper was limited to the explanation of negative predictions to exploit the concepts of MUS and MCS and use a SAT-based approach. For positively predicted instances, we can simply work on the negation of the symbolic representation (CNF) of 𝑓 (namely ¬Σ 𝑓 ). The enumeration of the explanations is done in the same way as for negative predictions.

To the best of our knowledge, our approach is the first that generates different types of symbolic explanations and fine-grained score-based ones. In addition, our approach is agnostic and declarative. Another advantage of our approach is the local faithfulness [START_REF] Tulio Ribeiro | Why should i trust you?" Explaining the predictions of any classifier[END_REF] to the instance to be explained.As future works, we intend to extend our approach for multi-label (ML) classification tasks to explain predictions in a multi-label setting.

Definition 2 . 1 .

 21 (Binary classifier) A Binary classifier is defined by two sets of binary variables: A feature space 𝑋 = {𝑋 1 ,..,𝑋 𝑛 } where |𝑋 |=𝑛, and a binary class variable denoted 𝑌 .

Figure 1 :

 1 Figure 1: A global overview of the proposed approach

Example 4 . 1 .

 41 As a running example to illustrate the different steps, we trained a Neural Network model 𝑓 on the United Stated Congressional Voting Records Data Set 3 . In this example, the label Republican corresponds to a positive prediction, noted 1 while the label Democrat corresponds to a negative prediction, noted 0. The trained Neural Network model 𝑓 achieves 95.74% accuracy. An input 𝑥 consists of the following features :

Figure 2 :

 2 Figure 2: A random forest trained on the neighborhood of 𝑥

Example 4 . 3 (

 43 Example 4.1 continued). Let us continue with the random forest classifier of Example 4.1. The following formulae illustrate the encoding steps applied to 𝑅𝐹 𝑓 :

Figure 3 :

 3 Figure 3: The random forest paths set by 𝑥

  (a) Example of 𝑆𝑅 𝑥 explanations. (b) Example of 𝐶𝐹 𝑥 explanations.

Figure 4 :

 4 Figure 4: Data samples from MNIST database and their respective symbolic explanations.

Figure 5 :

 5 Figure 5: Heatmaps in columns (b-c) representing the (FI) score, and (d-e) the (FR) computed over the 𝑆𝑅 𝑥 and 𝐶𝐹 𝑥 of the samples data from MNIST (column a) in comparaison to heatmaps of the SHAP values (column f).

  , we construct the neighborhood of 𝑥, noted 𝑉 (𝑥, 𝑟 ), by sampling data instances within a radius 𝑟 of 𝑥. In case the data set is not available, we can draw new perturbed samples around 𝑥. Once the vicinity of 𝑥 sampled, we train a random forest on the data set composed of (𝑥 𝑖 , 𝑓 (𝑥 𝑖 )) for 𝑖=1..𝑝 where 𝑥 𝑖 is a sampled data instance, 𝑝 is the number of sampled instances. Each 𝑥 𝑖 is labeled with the prediction 𝑓 (𝑥 𝑖 ) since the aim is to ensure that the surrogate model 𝑓 𝑆 is locally (in 𝑥's neighborhood) faithful to 𝑓 .

	𝑆 which is i) as
	faithful as possible to the initial model 𝑓 (ensures same predictions)
	and ii) allows to obtain a tractable CNF encoding. More precisely,
	we use the surrogate model 𝑓 𝑆 to approximate the classifier 𝑓 in
	the neighborhood of the instance to be explained. Note that one
	can approximate the classifier 𝑓 on the whole data set if this latter
	is available. A machine learning model that can guarantee a good
	trade-offs between faithfulness and giving a tractable CNF encoding
	is the one of random forests [12]. As we will see in our experimental
	study, random forests allow to obtain a good level of faithfulness
	(in general around 95%) while giving compact CNF encodings in
	terms of the number of clauses and variables. Given a data instance
	𝑥 whose prediction by the original model 𝑓 is to be explained and
	a data set

Table 1 :

 1 Evaluating the scalability of the CNF encoding.

		MNIST_0	MNIST_2	MNIST_5	MNIST_6	MNIST_8	SPECT	MONKS	Breast_cancer
	avg acc of RF	98%	93%	99%	96%	95%	99%	98%	82%
	min size CNF	1744/4944	1941/5452	2196/6102	1978/5534	1837/5178	2495/7174	2351/6714	5094/14184
	avg size CNF	1979/5540	2172/6050	2481/6856	2270/6293	2059/5727	2758/7921	2883/8146	6069/16907
	max size CNF	2176/6066	2429/6760	2789/7694	2558/7028	2330/6408	3088/8844	3451/9694	7053/19586
	min enc_runtime (s)	0.83	0.88	0.92	0.82	0.74	1.07	1.66	2.02
	avg enc_runtime (s)	1.05	1.06	1.11	0.92	0.86	1.214	1.56	2.5
	max enc_runtime (s)	1.51	1.92	1.56	1.31	1.32	1.5	2.03	3.42

Table 2 :

 2 Evaluating the enumeration of counterfactual explanations.

	with a timeout

will be discussed in the "Concluding remarks and discussions" Section.

A SAT solver is a program for deciding the satisfiability of Boolean formulae encoded in conjunctive normal form.

Available at https://archive.ics.uci.edu/ml/datasets/congressional+voting+records.

Remember that all the features in our case are binary.

In our case this constraint means that at least 𝑡 decision trees predicted the label 1.

ACKNOWLEDGMENTS

The authors would like to thank the Région Hauts-de-France and the University of Artois for supporting this work.


Ryma Boumazouza
email: ryma.boumazouza@univ-artois.fr

Fahima Cheikh
email: cheikh@univ-artois.fr

Bertrand Mazure
email: bertrand.mazure@univ-artois.fr

Karim Tabia
email: karim.tabia@univ-artois.fr

A Model-Agnostic SAT-based approach for Symbolic Explanation Enumeration (Preprint version)

Keywords: Explainable Artificial Intelligence (XAI), Symbolic explanations, Model-Agnostic, Satisfiability testing

We propose a generic agnostic approach allowing to generate different and complementary types of symbolic explanations. More precisely, we generate explanations to locally explain a single prediction by analyzing the relationship between the features and the output. Our approach uses a propositional encoding of the predictive model and a SAT-based setting to generate two types of symbolic explanations which are Sufficient Reasons and Counterfactuals. The experimental results on imagee classification task show the feasibility of the proposed approach and its effectiveness in providing Sufficient Reasons and Counterfactual explanations.

Introduction

Modern machine learning (ML) and deep learning methods are nowadays widely used in many sensitive fields and industries. However, despite the good predictive performance of the ML models, there are critical applications that fundamentally require trust like applications applied to medicine, driverless cars and law enforcement. Therefore, it becomes increasingly important to explain the behavior of those models and their output to enhance trust in the model predictions and their adoption in real world applications. This leads to a rapid growth in attention to eXplainable AI (XAI). The XAI methods can be grouped into premodel (ante-hoc), in-model, and post-model (post-hoc) methods. In the latter, we identify two types of explanations: (1) symbolic (knowledge-driven) methods that are based on logical representations used for explanation (e.g. [START_REF] Shih | A symbolic approach to explaining bayesian network classifiers[END_REF], [START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF]), verification and diagnostic purposes (e.g. [START_REF] Reiter | A theory of diagnosis from first principles[END_REF], [START_REF] Rymon | An se-tree-based prime implicant generation algorithm[END_REF], [START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF]), and (2) numerical featurebased methods that provide insights into how much each feature contributed to that outcome (e.g. SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF], LIME [START_REF] Ribeiro | why should i trust you?" explaining the predictions of any classifier[END_REF]). The main limitation to the existing explainability methods based on symbolic representations is the fact that they are generally intended to specific models and cannot be applied to any model (non agnostic). In the other hand, feature-based methods such as LIME [START_REF] Ribeiro | why should i trust you?" explaining the predictions of any classifier[END_REF] and SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF] try to assess the amount of contribution of features into the predictions but fail at answering certain questions such as What are the feature values which are sufficient in order to trigger the prediction whatever the values of the other variables ? or Which values are sufficient to change in the instance x to have a different prediction ? To address the problem of answering this type of fundamental questions, we propose in this paper an approach to provide "different" and "complementary" types of symbolic explanations: the Sufficient Reasons (SRx for short) and the Counterfactuals (CF x for short). The main advantage of our approach is the fact of being model-agnostic, where we try to learn accurate yet simple models to emulate the given black-box. In the other hand, the approach is based on rigorous and well-known Boolean satisfiability concepts that allow us to exploit the availability of efficient SAT solvers. Accordingly, our approach is declarative and does not require the implementation of specific algorithms. We evaluate the feasibility and efficiency of our approach on image classification task.

Preliminaries and notations

We first introduce the necessary notations and recall some definitions used in the remainder of this paper. For the sake of simplicity, we will limit the presentation to binary classifiers with binary features. We also focus only on negative predictions where the outcome is 0. As for explaining positive predictions where the outcome is 1, the approach applies similarly as discussed in the Conclusion. A decision function describes the classifier's behavior independently from the way it is implemented. We define it as a function f : X → Y mapping each instantiation x of X to y=f (x). A data instance x is the feature vector associated with an instance of interest whose prediction from the ML model is to be explained. We use interchangeably in this paper f to designate the classifier and its decision function. Let us now define the representation framework we use.

Definition 2. (SAT :

The Boolean Satisfiability problem) Usually called SAT, the Boolean satisfiability problem is the decision problem, which, given a propositional logic formula, determines whether there is an assignment of propositional variables that makes the formula true.

The logic formulas are built from propositional variables and Boolean connectors "AND" (∧), "OR" (∨), "NOT" (¬). A formula is satisfiable if there is an assignment of all variables that makes it true. It is said inconsistent or unsatisfiable otherwise. A complete assignment of variables making a formula true is called a model while a complete assignment making it false is called a countermodel. Definition 3. (CNF (Clausal Normal Form)) is a set of clauses seen as a conjunction. A clause is a formula composed of a disjunction of literals. A literal is either a Boolean variable p or its negation ¬p. A quantifier-free formula is built from atomic formulae using conjunction ∧, disjunction ∨, and negation ¬. An interpretation µ assigns values from {0, 1} to every Boolean variable. Let Σ be a CNF formula, µ satisfies Σ iff µ satisfies all clauses of Σ.

Thanks to the achievements that the SAT field had known in the recent years, the modern SAT solvers1 have gained in performance and efficiency where they can handle now problems with several million clauses and variables. Recall that we use a SAT oracle to generate our formal symbolic explanations. We encode the explanation generation problem as two common problems related to SATsolving which are enumerating minimal reasons why a formula is inconsistent and minimal changes to a formula in order to restore its consistency. Indeed, in the case of an unsatisfiable CNF, we can analyze the inconsistency by enumerating sets of clauses causing the inconsistency (called Minimal Unsatisfiable Subsets (MUS)), and other sets of clauses allowing to restore its consistency (called Minimal Correction Subsets (MCS)). The enumeration of MUS/MCS are well-known problems dealt with in many areas such as knowledge-base reparation. Several approaches and tools have been proposed in the SAT community for their generation (e.g [START_REF] Liffiton | Algorithms for computing minimal unsatisfiable subsets of constraints[END_REF], [START_REF] Grégoire | Boosting a complete technique to find mss and mus thanks to a local search oracle[END_REF]).

Overview of the proposed approach

The objective of our approach is explaining the prediction made by a classifier for a given input data instance x. It associates a logical representation that is almost equivalent to the decision function of the model to explain. Figure 1 represents an overview of the proposed approach. Given a predictive model f , our approach proceeds as follows:

-Step 1 (CNF encoding of the classifier): the goal is to encode f into an equivalent symbolic representation Σ f . The generation of symbolic explanations in the next step is done using Σ f . The encoding is done either by the means of model encoding algorithms if they are available and the encoding remains tractable, or using a surrogate modeling approach as described in Section 4. -Step 2 (Explanation problem modeling): This step presented in Section 5 comes down to enumerating two types of symbolic explanations: SRx and CF x. This task is formulated as a partial maximum satisfiability problem Partial Max-SAT [START_REF] Biere | Handbook of satisfiability[END_REF] using the CNF encoding Σ f of f and Σ x of the input instance x. The symbolic explanations respectively correspond to Minimal Unsatisfiable Subsets(MUS) and Minimal Correction Subsets(MCS) of Σ f ∪ Σ x in the SAT terminology.

The SAT solving is already used for providing some forms of symbolic explanations for some specific ML [START_REF] Boumazouza | A symbolic approach for counterfactual explanations[END_REF][START_REF] Ignatiev | Sat-based rigorous explanations for decision lists[END_REF][START_REF] Izza | On explaining random forests with sat[END_REF]. The novelty in our approach is the fact of being model-agnostic and succeeding in generating formal explanations based on rigorous concepts.

CNF encoding of classifiers

The starting point of our approach is the encoding of the input ML model f into a logical representation (CNF). This step is necessary in order to use a SAT oracle for the enumeration of the symbolic explanations. Mainly, two cases are considered: (1) an encoding of classifier f into an equivalent logical representation exists, in which case we can use it (e.g. Binarized Neural Networks (BNNs) [START_REF] Narodytska | Verifying properties of binarized deep neural networks[END_REF], Naive and Latent-Tree Bayesian network [START_REF] Shih | Compiling bayesian network classifiers into decision graphs[END_REF]). ( 2) We consider the classifier f as a black-box and we use a surrogate model approach to approximate it in the vicinity of the instance to explain x (Agnostic option). The surrogate models are used to explain individual predictions of black-box ML models. We set the focus on the agnostic option in this paper. This latter is applied when no direct CNF encoding exists for f or if the encoding is intractable.

Surrogate model encoding into CNF

The approach proposed uses a surrogate model mainly characterized by its faithfulness to the initial model f (ensures same predictions) and its tractable logical representation (CNF). To ensure the local faithfulness to f , we use a surrogate model f S trained on data instances in the vicinity of the data instance x whose prediction from the model needs to be explained. We construct the vicinity of x noted V (x, r) by sampling new data instances within a radius r of x if the dataset is available 2 .

A model that can guarantee a good trade-offs between faithfulness and giving a tractable CNF encoding is the one of random forests [START_REF] Ho | Random decision forests[END_REF]. As shown in our experimental study, the random forest accuracy reflects a good level of faithfulness and its CNF encoding size remains tractable. The CNF encoding f S of a classifier f should guarantee the equivalence of the two representations stated as follows : Definition 4. (Equivalence of a classifier and its CNF encoding) A binary classifier f (resp. f S ) can be equivalently encoded as a CNF Σ f (resp.

Σ f S ) s.t. f (x)=1 (resp. f S (x)=1) iff x is a model of Σ f (resp. Σ f S ).
Namely, data instances x predicted positively (f (x)=1) by the classifier are models of the CNF encoding the classifier. Similarly, data instances x predicted negatively (f (x)=0) are countermodels of the CNF encoding the classifier.

CNF encoding of random forests

In this work, we adopted the random forest3 as the surrogate model f S . Its associated CNF encoding resumes in i) encoding the decision trees individually and then ii) encoding the combination rule (which is a majority voting rule). Encode in CNF every decision tree : Remember that all the features in our case are binary. Thus, each internal node of a decision tree DT i represents a binary test on one of the features. The result of a test is either true or false. For the leaves of a decision tree, each one is annotated with the predicted class (namely, 0 or 1). The Boolean function encoded by a decision tree can be captured in CNF as the conjunction of the negation of paths leading to leaves labelled 0. Encode in CNF the combination rule : Let y i be a Boolean variable capturing the truth value of the CNF associated to a DT i . Hence, the majority rule used in random forests to combine the predictions of m decision trees can be seen as a cardinality constraint 4 [20] that can be stated as follows :

y ⇔ i=1..m y i ≥ t, (1)
where t is a threshold (usually t= m 2 ). To form the CNF corresponding to the entire random forest, it suffices to conjuct the m CNFs associated to the decisions trees, and, the CNF of the combination rule.

Generating symbolic explanations

This section will cover the presentation of both Sufficient Reasons and Counterfactuals explanations as well as the SAT-based setting we use to generate such explanations. This corresponds to Step 2 within the Fig. 1. This step takes as input the CNF encoding of a classifier Σ f and a sample data instance Σ x .

A SAT-based setting for the enumeration of explanations

We propose two complementary types of symbolic explanations: the Sufficient Reasons which are a minimal subset of the input data, that if fixed, lead to a given prediction and the Counterfactuals which are a minimal subset of the input data that we can act on to obtain a different outcome. The enumeration of those symbolic explanations in our approach is based on two very common concepts in SAT which are MUS and MCS (defined formally in the following). We use a variant of the SAT problem called Partial-Max SAT [START_REF] Biere | Handbook of satisfiability[END_REF] in order to restrict the explanations only to clauses encoding the input data x and do not include clauses that encode the classifier f . The Partial-Max SAT problem can be efficiently solved by the existing tools implementing the enumeration of MUSes and MCSes such as the tool in [START_REF] Grégoire | Boosting mcses enumeration[END_REF]. It is composed of two disjoint sets of clauses where Σ H denotes the hard clauses (those that could not be relaxed) and Σ S denotes the soft ones (those that could be relaxed). Concretely in our approach, the set of hard clauses corresponds to Σ f and the soft clauses to Σ x . The CNF Σ x encoding the data instance x is formed by unit clauses where each clause α ∈ Σ x is composed of exactly one literal (∀α ∈ Σ x , |α| = 1) and each literal representing a Boolean variable of Σ x corresponds to a Boolean variable {X i ∈ X} where X is the feature space of f . Thanks to this Partial-MAX SAT setting, it is possible to both identify the subsets of Σ x responsible for the unsatisfiability of a given CNF Σ f ∪Σ x (corresponding to SRx of f (x)=0), and the subsets allowing to restore the consistency of Σ f ∪Σ x (corresponding to CF x allowing to change the prediction to f (x)=1).

Sufficient Reason Explanations (SR x )

We are trying to find explanations that identify the relevant variables that could justify why the prediction is negative. This is carried out by identifying a subset of our input which causes the inconsistency of the CNF formula Σ f ∪Σ x (recall that the prediction f (x) is captured by the truth value of Σ f ∪Σ x ). The identified subsets of the input x represent Sufficient Reasons for the prediction to be negative. We formally define the Sufficient Reasons explanations as follow: Definition 5. (SR x explanations) Let x be a data instance and f (x)=0 its prediction by the classifier f . A sufficient reason explanation x of x is such that:

1. x ⊆ x (x is a part of x) 2. ∀x, x ⊂ x : f (x)=f (x) (x suffices to trigger the prediction) 3. There is no partial instance x ⊂ x satisfying 1 and 2 (minimality)

Intuitively, a sufficient reason x is defined as the part of the data instance x such that x is minimal and causes the prediction f (x)=0. Namely, to explain the classification it is "sufficient" to observe those features with disregard to the others. We define now the Minimal Unsatisfiable Subsets :

Definition 6. (MUS) A Minimal Unsatisfiable Subset (MUS) is a minimal subset Γ of clauses of a CNF Σ such that ∀ α ∈ Γ , Γ \{α} is satisfiable.
A MUS for Σ f ∪Σ x comes down to a subset of soft clauses, namely a part of x that is causing the inconsistency, hence the prediction f (x)=0. Proposition 1. Let f be a classifier, let Σ f be its CNF representation. Let also x be a data instance predicted negatively (f (x) = 0) and Σ f ∪Σ x the corresponding Partial Max-SAT encoding. Let SR(x, f ) be the set of Sufficient Reasons of x wrt. f . Let MUS(Σ f,x ) be the set of MUses of Σ f ∪ Σ x . Then:

∀x ⊆ x, x ∈ SR(x, f ) ⇐⇒ x ∈ M U S(Σ f,x ) (2)
Proposition 1 states that each MUS of the CNF Σ f ∪Σ x is a Sufficient Reason for the prediction f (x)=0 and vice versa.

Counterfactual Explanations (CF x )

We are also interested in another type of explanation which would allow us to figure out what changes can be made to the input data in order to alter the initial outcome. Let us formally define the concept of counterfactual explanation.

Definition 7. (CF x Explanations) Let x be a complete data instance and f (x) its prediction by the decision function of f . A counterfactual explanation x of x is such that:

1. x ⊆ x (x is a part of x) 2. f (x[x])= 1-f (x) (prediction inversion) 3. There is no x ⊂ x such that f (x[x])=f (x[x]) (minimality)
In definition 7, the term x[x] denotes the data instance x where variables included in x are inverted. In our approach, Counterfactuals are enumerated thanks to the Minimal Correction Subset enumeration [START_REF] Grégoire | Boosting mcses enumeration[END_REF].

Definition 8. (MCS) A Minimal Correction Subset Ψ of a CNF Σ is a set of formulas Ψ ⊆ Σ whose complement in Σ, i.e., Σ \ Ψ , is a maximal satisfiable subset of Σ.
Following our modeling, an MCS for Σ f ∪Σ x comes down to a subset of soft clauses denoted x, namely a part of x that is enough to remove (or reverse) in order to restore the consistency, hence to alter the prediction f (x)=0 to f (x[x])=1.

Proposition 2. Let f be the decision function of the classifier, let Σ f be its CNF representation. Let also x be a data instance predicted negatively (f (x) = 0) and Σ f ∪Σ x the corresponding Partial Max-SAT encoding. Let CF x(x, f ) be the set of counterfactuals of x wrt. f . Let MCS(Σ f,x ) the set of MCSs of

Σ f ∪ Σ x . Then: ∀x ⊆ x, x ∈ CF x(x, f ) ⇐⇒ x ∈ M CS(Σ f,x ) (3)
Proposition 2 states that each MCS of the CNF Σ f ∪Σ x represents a CF x⊆x for the prediction f (x)=0 and vice versa.

Empirical evaluation

Experimentation set-up The black-box models considered are "one-vs-all" binary neural networks (BNNs) 5 trained on the widely used MNIST database 6 . MNIST is composed of 70,000 images of size 28 × 28 pixels. We use the pytorch implementation 7 of the Binary-Backpropagation algorithm "BinaryNets" [START_REF] Hubara | Binarized neural networks[END_REF] to train the BNN classifiers (one per digit from 0 to 9) on the binarized images (threshold T = 127). All experiments have been conducted on Intel Core i7-7700 (3.60GHz ×8) processors with 32Gb memory on Linux.

Results

The surrogate model considered is a random forest (RF) classifier trained on the vicinity of the input sample using the hyper-parameters nb trees = 10 and max depth = 24. We try out different values for the radius r but we only present the results for r = 250 with an average of 200 neighbors around x due to the limited number of pages. The black-box models (BNNs) trained to recognize the "0","2","5","6" and "8" digits are used as predictive models 8 . Around 1000 to 1500 images were picked randomly from the MNIST database for the experimental study conducted on each classifier.

Evaluating the CNF encoding in practice : We are interested in evaluating the size of the CNF encoding using the setting mentioned above. We use the Tseitin Transformation [START_REF] Tseitin | On the complexity of derivation in propositional calculus[END_REF] to encode the propositional formulae into an equisatisfiable CNF formulae. The size of this latter is linear in the size of the original formulae. The results are presented in Table 1. The high accuracy of f S shows that the generated RF classifier provide interesting results in term of fidelity. The number of variables/clauses of the CNF indicates that the logical representation remains tractable and makes the logical representation easily handled by the current SAT-solvers which confirms the feasibility of the approach. Evaluating the feasibility of the enumeration of explanations : We want to assess the practical feasibility of the enumeration of Sufficient Reasons and Counterfactual explanations. To enumerate the CF x, we use the EnumELSRM-RCache tool 1 with a timeout set to 600s. Thanks to the duality between MUSes and MCSes, the enumeration of SRx can be done by computing the minimal hitting set of CF x. However, the results in this paper only cover the enumeration of CF x due to the page limitation.

In Table 1, we report the average run-time (enumtime) needed to enumerate all the explanations within the timeout whereas in reality the solver manages to find explanations instantly in the majority of cases. Accordingly, the enumeration time remains reasonable and shows the practical feasibility of the enumeration of such explanations for medium size classifiers (like the BNNs used). Additionally, we notice that the number of CF x enumerated is significant and that it quickly becomes unmanageable for a user to process the result. This reinforces the need for quality metrics to filter the generated explanations.

SR x and CF x for MNIST : We use the "one-vs-all" BNN f 8 trained to recognize the eight "8" digit (positive prediction for an image representing "8", negative otherwise) that has achieved an accuracy of 97%. Fig. 2 shows a few data samples negatively predicted by f 8 . Heatmaps in the 3 rd column of Fig. 2 show examples of CF x highlighting the necessary changes to be made on the input data sample in order to alter the outcome of f 8 from negative to positive. We can visually distinguish a sort of pattern of the digit "8" highlighting the pixels we need to act on. This actually matches the definition of CF x. Although the underlying mechanisms of our approach and SHAP differ which may lead to very different explanations for the same input, we can see that our explanations are visually simpler, clearer and easier to understand and use compared to SHAP explanations in the last column.

Concluding remarks and Discussions

We try to explain individual outcomes of black-box models by the mean of a novel model agnostic generic approach presented within this paper in order to provide two complementary types of explanations: Sufficient reasons and Counterfactuals. The approach is based on the Boolean satisfiability concepts which allow us to take advantage of the strengths of already existing and proven solutions, and the powerful practical tools for the generation of MCS/MUS. We use the notion of surrogate model to overcome the complexity of encoding a ML classifier into an equivalent logical representation. It is a local encoding since we approximate the original model in the vicinity of the sample of interest. The same mechanism is used to explain positively predicted instances. It suffices to work with the negation of the representation of f (¬f ) to enumerate the explanations in a similar way. We intend in future works to assess the relevance of explanations and features individually w.r.t a set of properties allowing to evaluate explanations in ways that are closer to how users consume them.

Definition 1 .

 1 (Binary Classifier) A Binary Classifier is defined by two sets of variables: A feature space X= {X 1 ,...,X n } where |X| = n, and a binary class variable denoted Y . Both the features and the class variable take values in {0,1}.

Fig. 1 .

 1 Fig. 1. A global overview of the proposed approach

Fig. 2 .

 2 Fig.2. Data samples from MNIST predicted negatively by f8 in the 1 st column. The heatmap of the: 2 nd column represent the variables involved by the explanations, the 3 th and 4 th columns, a single counterfactual and sufficient reason explanation. The last column is the SHAP values of the variables contributing positively to the prediction.

Table 1 .

 1 Evaluating[START_REF] Audemard | On tractable xai queries based on compiled representations[END_REF] the encoding into the logical representation and (2) the enumeration of explanations for different classifiers used to locally explain MNIST images.

		MNIST 0	MNIST 2	MNIST 5	MNIST 6	MNIST 8
	avg acc of RF	98%	93%	99%	96%	95%
	min size CNF	1744/4944	1941/5452	2196/6102	1978/5534	1837/5178
	avg size CNF	1979/5540	2172/6050	2481/6856	2270/6293	2059/5727
	max size CNF	2176/6066	2429/6760	2789/7694	2558/7028	2330/6408
	min enc runtime (s)	0.83	0.88	0.92	0.82	0.74
	avg enc runtime (s)	1.05	1.06	1.11	0.92	0.86
	max enc runtime (s)	1.51	1.92	1.56	1.31	1.32
	min #CFs	10	13	10	15	6
	avg #CFs	35790	63916	99174	79520	4846
	max #CFs	285219	546005	633416	640868	65554
	min enumtime (s)	0.005	0.11	0.006	0.11	0.008
	avg enumtime (s)	21.49	42.11	77.72	50.86	2.35
	max enumtime (s)	234.18	600	600	531.16	35.08

A SAT solver is a program for establishing the satisfiability of Boolean formulas encoded in conjunctive normal form.

Random Forests are used for XAI purposes in some works such was[1,

[START_REF] Choi | On symbolically encoding the behavior of random forests[END_REF][START_REF] Izza | On explaining random forests with sat[END_REF] 4 In our case this constraint means that at least t decision trees predicted the label 1.

defined as a neural networks with binary weights and activations at run-time

MNIST: handwritten digit databse, available at http://yann.lecun.com/exdb/mnist/

available at: https://github.com/itayhubara/BinaryNet.pytorch

results for the other digits are similar but not be reported because of space limitation 1 implementing the boosting algorithm for MCSes enumeration proposed in[START_REF] Grégoire | Boosting mcses enumeration[END_REF]

Acknowledgment : This work was supported by the Région Hauts-de-France.