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.

Boosted trees is a dominant ML model, exhibiting high accuracy. However, boosted trees are hardly intelligible, and this is a problem whenever they are used in safety-critical applications. Indeed, in such a context, provably sound explanations for the predictions made are expected. Recent work have shown how subset-minimal abductive explanations can be derived for boosted trees, using automated reasoning techniques. However, the generation of such well-founded explanations is intractable in the general case. To improve the scalability of their generation, we introduce the notion of tree-specific explanation for a boosted tree. We show that tree-specific explanations are provably sound abductive explanations that can be computed in polynomial time. We also explain how to derive a subset-minimal abductive explanation from a tree-specific explanation. Experiments on various datasets show the computational benefits of leveraging tree-specific explanations for deriving subset-minimal abductive explanations.

We define contrastive explanations that are suited to tree-based classifiers. In our framework, contrastive explanations are based on the set of (possibly non-independent) Boolean characteristics used by the classifier and are at least as general as contrastive explanations based on the set of characteristics of the instances considered at start. We investigate the computational complexity of computing contrastive explanations for Boolean classifiers (including tree-based ones), when the Boolean conditions used are not independent. Finally, we present and evaluate empirically an algorithm for computing minimum-size contrastive explanations for random forests.

In the domain of partial classification, recent studies about multiobjective local search (MOLS) have led to new algorithms offering high performance, particularly when the data are imbalanced. In the presence of such data, the class distribution is highly skewed and the user is often interested in the least frequent class. Making further improvements certainly requires exploiting complementary solving techniques (notably, for the rule mining problem). As Constraint Programming (CP) has been shown to be effective on various combinatorial problems, it is one such promising complementary approach. In this paper, we propose a new hybrid combination, based on MOLS and CP that are quite orthogonal. Indeed, CP is a complete approach based on powerful filtering techniques whereas MOLS is an incomplete approach based on Pareto dominance. Experimental results on real imbalanced datasets show that our hybrid approach is statistically more efficient than a simple MOLS algorithm on both training and tests instances, in particular, on partial classification problems containing many attributes.

Classification problems can be modeled as multi-objective optimization problems. MOCA-I is a multi-objective local search designed to solve these problems, particularly when the data are imbalanced. However, this algorithm has been tuned by hand in order to be efficient on particular datasets. In this paper, we propose a methodology to automatically conFigure a multi-objective algorithm for solving a supervised partial classification problem. This methodology is based on a multi-objective approach of automatic algorithm configuration and requires a clear definition of the experimental protocol. Therefore, we present a k-fold cross-validation protocol to train and test the configuration model. To the best of our knowledge, it is the first time that multi-objective automatic algorithm configuration is performed on optimization algorithms to solve classification problems. Experimental results on real imbalanced datasets show that our approach can find efficient configurations of MOCA-I with less effort in comparison with the ones found exhaustively by hand.

In solving combinatorial problems, the advent of multi-core machines has led to the development of new parallel methods offering higher performance as well as better solutions. However, finding the best parallel algorithm on such architectures for a given problem and programming these methods are still challenging tasks today. As a matter of fact, only a few parallel solvers have been designed so far to tackle multi-objective combinatorial optimisation problems. Therefore this paper first proposes a new highly parametric multi-thread and multiobjective local search algorithm dedicated to tackling optimisation problems. Specifically, this new parallel solver incorporates and combines most of methods available in the literature, such as single-walk and multi-walk parallel local search, which can be independent of each other or cooperative by sharing some solutions. In addition, this solver is also capable of making some innovative hybridisations by mixing both single-walk and multi-walk approaches. The major problem is that it then becomes very difficult, if not impossible, for a human expert to determine the best configurations. This obstacle is due to the fact that the number of parameters in parallel methods is excessively too large. Indeed, all configuration possibilities include the combination of two kinds of parameters. The first ones are the parameters of the sequential algorithms within the parallel solver for multi-walk-based methods. The second ones are those controlling the main parallel components such as hybridisation, diversification or choice of communications. Fortunately, automatic algorithm configuration allows this problem to be taken into account. Thus, we use a configurator especially designed for multi-objective problems called MO-ParamILS in order to expose some best parallel configurations for the bi-objective travelling salesman problem.

We present and evaluate DMC, a distributed model counter for propositional CNF formulae based on the state-of-the-art sequential model counter D4. DMC can take advantage of a (possibly large) number of sequential model counters running on (possibly heterogeneous) computing units spread over a network of computers. For ensuring an efficient workload distribution, the model counting task is shared between the model counters following a policy close to work stealing. The number and the sizes of the messages which are exchanged by the jobs are kept small. The results obtained show DMC as a much more efficient counter than D4, the distribution of the computation yielding large improvements for some benchmarks. DMC appears also as a serious challenger to the parallel model counter CountAntom and to the distributed model counter dCountAntom.