International audience

We present and evaluate empirically an XAI protocol for ruling interactions between a tree-based ML model (the AI system) and its user U, in the context of a prediction task. The pieces of knowledge held by U concerning the prediction task are supposed to be representable by a set of classification rules that is reliable and consistent, but (typically) incomplete. The proposed protocol aims to help U decide what to do with each prediction made by AI (accept it, reject it). It also aims to improve the quality of further predictions made by AI thanks to the expertise of U, and, reciprocally, to complete the pieces of knowledge held by U by leveraging the predictions made by AI. Experiments show that the approach can prove valuable in practice.

We elaborate on the notion of rectification of a classifier Σ based on Boolean features, introduced in [10]. The purpose is to determine how to modify Σ when the way it classifies a given instance is considered incorrect since it conflicts with some expert knowledge T. Given Σ and T, postulates characterizing the way Σ must be changed into a new classifier Σ ⋆ T that complies with T were presented. We focus here on the specific case of binary classifiers, i.e., there is a single target concept, and any instance is classified either as positive (an element of the concept), or as negative (an element of the complementary concept). In this specific case, our main contribution is twofold: (1) we show that there is a unique rectification operator ⋆ satisfying the postulates, and (2) when Σ and T are Boolean circuits, we show how a classification circuit equivalent to Σ ⋆ T can be computed in time linear in the size of Σ and T; when Σ is a decision tree (resp. a random forest, a boosted tree) and T is a decision tree, a decision tree (resp. a random forest, a boosted tree) equivalent to Σ ⋆ T can be computed in time polynomial in the size of Σ and T.

An important issue in ML consists in developing approaches exploiting background knowledge T for improving the accuracy and the robustness of learned classifiers C. Delegating the classification task to a Boolean circuit Σ exhibiting the same input-output behaviour as C, the problem of exploiting T within C can be viewed as a belief change scenario. However, usual change operations are not suited to the task of modifying the classifier encoding Σ in a minimal way, to make it complying with T. To fill the gap, we present a new belief change operation, called rectification. We characterize the family of rectification operators from an axiomatic perspective and exhibit operators from this family. We identify the standard belief change postulates that every rectification operator satisfies and those it does not. We also focus on some computational aspects of rectification and compliance.

Recently, Dunne et al. [9,10] introduced the concept of WAF (Weighted Argumentation Framework). Such frameworks extend standard Dung's ones for abstract argumentation by associating weights with attacks. In the WAF setting, weights are used for relaxing extensions, which proves useful when there are too few extensions. In this paper, we exploit weights in a different perspective. We show how to take advantage of attacks weights within an argumentation process for selecting some extensions among Dung's ones, which proves useful when there are too many extensions, in order to improve the inferential power of the argumentation framework.

We present new prudent semantics within Dung's theory of argumentation. Under such prudent semantics, two arguments cannot belong to the same extension whenever one of them attacks indirectly the other one. We argue that our semantics lead to a better handling of controversial arguments than Dung's ones. We compare the prudent inference relations induced by our semantics w.r.t. cautiousness; we also compare them with the inference relations induced by Dung's semantics.

This paper presents new complexity results for propositional closed world reasoning (CWR) from tractable knowledge bases (KBs). Both (basic) CWR, generalized CWR, extended generalized CWR, careful CWR and extended CWR (equivalent to circumscription) are considered. The focus is on tractable KBs belonging to target classes for exact compilation functions: Blake formulas, DNFs, disjunctions of Horn formulas, and disjunctions of renamable Horn formulas. The complexity of inference is identified for all the forms of CWR listed above. For each of them, new tractable fragments are exhibited. Interestingly, the restricted classes of formulas we consider are target classes for exact compilation functions, i.e., every KB can be turned into an equivalent formula from any of these classes. Accordingly, our results suggest knowledge compilation as a valuable, practical approach to deal with the complexity of CWR in some situations.

International audience

Extrait de : Proc. Intern. Conf. on Spoken Language Processing, Banff (Alberta, Canada), October 1992