Frédéric Koriche

UAI Conference 2025 Conference Paper

Probabilistic Explanations for Regression Models

• Frédéric Koriche
• Jean-Marie Lagniez
• Chi Tran

Formal explainability is an emerging field that aims to provide mathematically guaranteed explanations for the predictions made by machine learning models. Recent work in this area focuses on computing “probabilistic explanations” for the predictions made by classifiers based on specific data instances. The goal of this paper is to extend the concept of probabilistic explanations to the regression setting, treating the target regressor as a black box function. The class of probabilistic explanations consists of linear functions that meet a sparsity constraint, alongside a hyperplane constraint defined for the data instance being explained. While minimizing the precision error of such explanations is generally $\text{NP}^{\text{PP}}$-hard, we demonstrate that it can be approximated by substituting the precision measure with a fidelity measure. Optimal explanations based on this fidelity objective can be effectively approached using Mixed Integer Programming (MIP). Moreover, we show that for certain distributions used to define the precision measure, explanations with approximation guarantees can be computed in polynomial time using a variant of Iterative Hard Thresholding (IHT). Experiments conducted on various datasets indicate that both the MIP and IHT approaches outperform the state-of-the-art LIME and MAPLE explainers.

UAI Conference 2023 Conference Paper

Approximating probabilistic explanations via supermodular minimization

• Louenas Bounia
• Frédéric Koriche

Explaining in accurate and intelligible terms the predictions made by classifiers is a key challenge of eXplainable Artificial Intelligence (XAI). To this end, an abductive explanation for the predicted label of some data instance is a subset-minimal collection of features such that the restriction of the instance to these features is sufficient to determine the prediction. However, due to cognitive limitations, abductive explanations are often too large to be interpretable. In those cases, we need to reduce the size of abductive explanations, while still determining the predicted label with high probability. In this paper, we show that finding such probabilistic explanations is NP-hard, even for decision trees. In order to circumvent this issue, we investigate the approximability of probabilistic explanations through the lens of supermodularity. We examine both greedy descent and greedy ascent approaches for supermodular minimization, whose approximation guarantees depend on the curvature of the “unnormalized” error function that evaluates the precision of the explanation. Based on various experiments for explaining decision tree predictions, we show that our greedy algorithms provide an efficient alternative to the state-of-the-art constraint optimization method.

AAAI Conference 2022 Conference Paper

Trading Complexity for Sparsity in Random Forest Explanations

• Gilles Audemard
• Steve Bellart
• Louènas Bounia
• Frédéric Koriche
• Jean-Marie Lagniez
• Pierre Marquis

Random forests have long been considered as powerful model ensembles in machine learning. By training multiple decision trees, whose diversity is fostered through data and feature subsampling, the resulting random forest can lead to more stable and reliable predictions than a single decision tree. This however comes at the cost of decreased interpretability: while decision trees are often easily interpretable, the predictions made by random forests are much more difficult to understand, as they involve a majority vote over multiple decision trees. In this paper, we examine different types of reasons that explain “why” an input instance is classified as positive or negative by a Boolean random forest. Notably, as an alternative to prime-implicant explanations taking the form of subset-minimal implicants of the random forest, we introduce majoritary reasons which are subset-minimal implicants of a strict majority of decision trees. For these abductive explanations, the tractability of the generation problem (finding one reason) and the optimization problem (finding one minimumsized reason) are investigated. Unlike prime-implicant explanations, majoritary reasons may contain redundant features. However, in practice, prime-implicant explanations for which the identification problem is DP-complete - are slightly larger than majoritary reasons that can be generated using a simple linear-time greedy algorithm. They are also significantly larger than minimum-sized majoritary reasons which can be approached using an anytime PARTIAL MAXSAT algorithm.

KR Conference 2021 Conference Paper

On the Computational Intelligibility of Boolean Classifiers

• Gilles Audemard
• Steve Bellart
• Louenas Bounia
• Frédéric Koriche
• Jean-Marie Lagniez
• Pierre Marquis

In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries, we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees, Boolean multilayer perceptrons, and binarized neural networks.

ECAI Conference 2020 Conference Paper

Learning Variable Ordering Heuristics with Multi-Armed Bandits and Restarts

• Hugues Wattez
• Frédéric Koriche
• Christophe Lecoutre
• Anastasia Paparrizou
• Sébastien Tabary

In constraint-based applications, the user is often required to be an expert as, for a given problem instance, many parameters of the used solver must be manually tuned to improve its efficiency. Clearly, this background knowledge burdens the spread of constraint programming technology to non-expert users. In order to alleviate this issue, the idea of “autonomous” constraint solving is to adjust the solver parameters and to efficiently handle any problem instance without manual tuning. Notably, the choice of the variable ordering heuristic can lead to drastically different performances. A key question arises then: how can we find the best variable ordering heuristic for a problem instance, given a set of available heuristics provided by the solver? To answer this question, we propose an algorithmic framework that combines multi-armed bandits and restarts. Each candidate heuristic is viewed as an arm, and the framework learns to estimate the best heuristic using a multi-armed bandit algorithm. The common mechanism of restarts is used to provide feedback for reinforcing the bandit algorithm. Based on a thorough experimental evaluation, we demonstrate that this framework is able to find the best heuristic for most problem instances; notably, it outperforms the state-of-the-art in terms of time and solved instances.

KR Conference 2020 Conference Paper

On Tractable XAI Queries based on Compiled Representations

• Gilles Audemard
• Frédéric Koriche
• Pierre Marquis

One of the key purposes of eXplainable AI (XAI) is to develop techniques for understanding predictions made by Machine Learning (ML) models and for assessing how much reliable they are. Several encoding schemas have recently been pointed out, showing how ML classifiers of various types can be mapped to Boolean circuits exhibiting the same input-output behaviours. Thanks to such mappings, XAI queries about classifiers can be delegated to the corresponding circuits. In this paper, we define new explanation and/or verification queries about classifiers. We show how they can be addressed by combining queries and transformations about the associated Boolean circuits. Taking advantage of previous results from the knowledge compilation map, this allows us to identify a number of XAI queries that are tractable provided that the circuit has been first turned into a compiled representation.

ICML Conference 2018 Conference Paper

Compiling Combinatorial Prediction Games

• Frédéric Koriche

In online optimization, the goal is to iteratively choose solutions from a decision space, so as to minimize the average cost over time. As long as this decision space is described by combinatorial constraints, the problem is generally intractable. In this paper, we consider the paradigm of compiling the set of combinatorial constraints into a deterministic and Decomposable Negation Normal Form (dDNNF) circuit, for which the tasks of linear optimization and solution sampling take linear time. Based on this framework, we provide efficient characterizations of existing combinatorial prediction strategies, with a particular attention to mirror descent techniques. These strategies are compared on several real-world benchmarks for which the set of Boolean constraints is preliminarily compiled into a dDNNF circuit.

AIJ Journal 2017 Journal Article

Constraint acquisition

• Christian Bessiere
• Frédéric Koriche
• Nadjib Lazaar
• Barry O'Sullivan

Constraint programming is used to model and solve complex combinatorial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist the non-expert user in the modeling task. This paper presents the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose Conacq, a system that uses a concise representation of the learner's version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated.

IJCAI Conference 2017 Conference Paper

Constraint-Based Symmetry Detection in General Game Playing

• Frédéric Koriche
• Sylvain Lagrue
• Éric Piette
• Sébastien Tabary

Symmetry detection is a promising approach for reducing the search tree of games. In General Game Playing (GGP), where any game is compactly represented by a set of rules in the Game Description Language (GDL), the state-of-the-art methods for symmetry detection rely on a rule graph associated with the GDL description of the game. Though such rule-based symmetry detection methods can be applied to various tree search algorithms, they cover only a limited number of symmetries which are apparent in the GDL description. In this paper, we develop an alternative approach to symmetry detection in stochastic games that exploits constraint programming techniques. The minimax optimization problem in a GDL game is cast as a stochastic constraint satisfaction problem (SCSP), which can be viewed as a sequence of one-stage SCSPs. Minimax symmetries are inferred according to themicrostructure complement of these one-stage constraint networks. Based on a theoretical analysis of this approach, we experimentally show on various games that the recent stochastic constraint solver MAC-UCB, coupled with constraint-based symmetry detection, significantly outperforms the standard Monte Carlo Tree Search algorithms, coupled with rule-based symmetry detection. This constraint-driven approach is also validated by the excellent results obtained by our player during the last GGP competition.

ECAI Conference 2016 Conference Paper

An Improved CNF Encoding Scheme for Probabilistic Inference

• Anicet Bart
• Frédéric Koriche
• Jean-Marie Lagniez
• Pierre Marquis

We present and evaluate a new CNF encoding scheme for reducing probabilistic inference from a graphical model to weighted model counting. This new encoding scheme elaborates on the CNF encoding scheme ENC4 introduced by Chavira and Darwiche, and improves it by taking advantage of log encodings of the elementary variable/value assignments and of the implicit encoding of the most frequent probability value per conditional probability table. From the theory side, we show that our encoding scheme is faithful, and that for each input network, the CNF formula it leads to contains less variables and less clauses than the CNF formula obtained using ENC4. From the practical side, we show that the C2D compiler empowered by our encoding scheme performs in many cases significantly better than when ENC4 is used, or when the state-of-the-art ACE compiler is considered instead.

ECAI Conference 2016 Conference Paper

Fixed-Parameter Tractable Optimization Under DNNF Constraints

• Frédéric Koriche
• Daniel Le Berre
• Emmanuel Lonca
• Pierre Marquis

Minimizing a cost function under a set of combinatorial constraints is a fundamental, yet challenging problem in AI. Fortunately, in various real-world applications, the set of constraints describing the problem structure is much less susceptible to change over time than the cost function capturing user's preferences. In such situations, compiling the set of feasible solutions during an offline step can make sense, especially when the target compilation language renders computationally easier the generation of optimal solutions for cost functions supplied "on the fly", during the online step. In this paper, the focus is laid on Boolean constraints compiled into DNNF representations. We study the complexity of the minimization problem for several families of cost functions subject to DNNF constraints. Beyond linear minimization which is already known to be tractable in the DNNF language, we show that both quadratic minimization and submodular minization are fixed-parameter tractable for various subsets of DNNF. In particular, the fixed-parameter tractability of constrained submodular minimization is established using a natural parameter capturing the structural dissimilarity between the submodular cost function and the DNNF representation.

UAI Conference 2016 Conference Paper

Online Forest Density Estimation

• Frédéric Koriche

Online density estimation is the problem of predicting a sequence of outcomes, revealed one at a time, almost as well as the best expert chosen from a reference class of probabilistic models. The performance of each expert is measured with the log-likelihood loss. The class of experts examined in this paper is the family of discrete, acyclic graphical models, also known as Markov forests. By coupling Bayesian mixtures with symmetric Dirichlet priors for parameter learning, and a variant of “Follow the Perturbed Leader” strategy for structure learning, we derive an online forest density √ estimation algorithm that achieves a regret of Õ( T ), with a per-round time complexity that is quasi-quadratic in the input dimension. Using simple and flexible update rules, this algorithm can be easily adapted to predict with Markov trees or mixtures of Markov forests. Empirical results indicate that our online algorithm is a practical alternative to the state-of-the-art batch algorithms for learning tree-structured graphical models.

ECAI Conference 2014 Conference Paper

Symmetry-Driven Decision Diagrams for Knowledge Compilation

• Anicet Bart
• Frédéric Koriche
• Jean-Marie Lagniez
• Pierre Marquis

In this paper, symmetries are exploited for achieving significant space savings in a knowledge compilation perspective. More precisely, the languages FBDD and DDG of decision diagrams are extended to the languages Sym-FBDDX, Yand Sym-DDGX, Yof symmetry-driven decision diagrams, where X is a set of "symmetry-free" variables and Y is a set of "top" variables. Both the time efficiency and the space efficiency of Sym-FBDDX, Yand Sym-DDGX, Yare analyzed, in order to put those languages in the knowledge compilation map for propositional representations. It turns out that each of Sym-FBDDX, Yand Sym-DDGX, Ysatisfies CT (the model counting query). We prove that no propositional language over a set X∪ Y of variables, satisfying both CO (the consistency query) and CD (the conditioning transformation), is at least as succinct as any of Sym-FBDDX, Yand Sym-DDGX, Yunless the polynomial hierarchy collapses. The price to be paid is that only a restricted form of conditioning and a restricted form of forgetting are offered by Sym-FBDDX, Yand Sym-DDGX, Y. Nevertheless, this proves sufficient for a number of applications, including configuration and planning. We describe a compiler targeting Sym-FBDDX, Yand Sym-DDGX, Yand give some experimental results on planning domains, highlighting the practical significance of these languages.

IJCAI Conference 2013 Conference Paper

Knowledge Compilation for Model Counting: Affine Decision Trees

• Frédéric Koriche
• Jean-Marie Lagniez
• Pierre Marquis
• Samuel Thomas

Counting the models of a propositional formula is a key issue for a number of AI problems, but few propositional languages offer the possibility to count models efficiently. In order to fill the gap, we introduce the language EADT of (extended) affine decision trees. An extended affine decision tree simply is a tree with affine decision nodes and some specific decomposable conjunction or disjunction nodes. Unlike standard decision trees, the decision nodes of an EADT formula are not labeled by variables but by affine clauses. We study EADT, and several subsets of it along the lines of the knowledge compilation map. We also describe a CNF-to-EADT compiler and present some experimental results. Those results show that the EADT compilation-based approach is competitive with (and in some cases is able to outperform) the model counter Cachet and the d-DNNF compilationbased approach to model counting.

ICML Conference 2013 Conference Paper

Rounding Methods for Discrete Linear Classification

• Yann Chevaleyre
• Frédéric Koriche
• Jean-Daniel Zucker

Learning discrete linear functions is a notoriously difficult challenge. In this paper, the learning task is cast as combinatorial optimization problem: given a set of positive and negative feature vectors in the Euclidean space, the goal is to find a discrete linear function that minimizes the cumulative hinge loss of this training set. Since this problem is NP-hard, we propose two simple rounding algorithms that discretize the fractional solution of the problem. Generalization bounds are derived for two important classes of binary-weighted linear functions, by establishing the Rademacher complexity of these classes and proving approximation bounds for rounding methods. These methods are compared on both synthetic and real-world data.

AIJ Journal 2010 Journal Article

Learning conditional preference networks

• Frédéric Koriche
• Bruno Zanuttini

Conditional preference networks (CP-nets) have recently emerged as a popular language capable of representing ordinal preference relations in a compact and structured manner. In this paper, we investigate the problem of learning CP-nets in the well-known model of exact identification with equivalence and membership queries. The goal is to identify a target preference ordering with a binary-valued CP-net by interacting with the user through a small number of queries. Each example supplied by the user or the learner is a preference statement on a pair of outcomes. In this model, we show that acyclic CP-nets are not learnable with equivalence queries alone, even if the examples are restricted to swaps for which dominance testing takes linear time. By contrast, acyclic CP-nets are what is called attribute-efficiently learnable when both equivalence queries and membership queries are available: we indeed provide a learning algorithm whose query complexity is linear in the description size of the target concept, but only logarithmic in the total number of attributes. Interestingly, similar properties are derived for tree-structured CP-nets in the presence of arbitrary examples. Our learning algorithms are shown to be quasi-optimal by deriving lower bounds on the VC-dimension of CP-nets. In a nutshell, our results reveal that active queries are required for efficiently learning CP-nets in large multi-attribute domains.

IJCAI Conference 2009 Conference Paper

• Frédéric Koriche
• Bruno Zanuttini

We investigate the problem of eliciting CP-nets in the well-known model of exact learning with equivalence and membership queries. The goal is to identify a preference ordering with a binary-valued CP-net by guiding the user through a sequence of queries. Each example is a dominance test on some pair of outcomes. In this setting, we show that acyclic CP-nets are not learnable with equivalence queries alone, while they are learnable with the help of membership queries if the supplied examples are restricted to swaps. A similar property holds for tree CP-nets with arbitrary examples. In fact, membership queries allow us to provide attributeefficient algorithms for which the query complexity is only logarithmic in the number of attributes. Such results highlight the utility of this model for eliciting CP-nets in large multi-attribute domains.

ECAI Conference 2008 Conference Paper

Online Rule Learning via Weighted Model Counting

• Frédéric Koriche

Online multiplicative weight-update learning algorithms, such as Winnow, have proven to behave remarkably for learning simple disjunctions with few relevant attributes. The aim of this paper is to extend the Winnow algorithm to more expressive concepts characterized by DNF formulas with few relevant rules. For such problems, the convergence of Winnow is still fast, since the number of mistakes increases only linearly with the number of attributes. Yet, the learner is confronted with an important computational barrier: during any prediction, it must evaluate the weighted sum of an exponential number of rules. To circumvent this issue, we convert the prediction problem into a Weighted Model Counting problem. The resulting algorithm, SharpNow, is an exact simulation of Winnow equipped with backtracking, caching, and decomposition techniques. Experiments on static and drifting problems demonstrate the performance of the algorithm in terms of accuracy and speed.

ECAI Conference 2004 Conference Paper

Bias Windowing for Relational Learning

• Frédéric Koriche

CSL Conference 2001 Conference Paper

A Logic for Approximate First-Order Reasoning

• Frédéric Koriche

Abstract In classical approaches to knowledge representation, reasoners are assumed to derive all the logical consequences of their knowledge base. As a result, reasoning in the first-order case is only semi-decidable. Even in the restricted case of finite universes of discourse, reasoning remains inherently intractable, as the reasoner has to deal with two independent sources of complexity: unbounded chaining and unbounded quantification. The purpose of this study is to handle these difficulties in a logic-oriented framework based on the paradigm of approximate reasoning. The logic is semantically founded on the notion of resource, an accuracy measure, which controls at the same time the two barriers of complexity. Moreover, a stepwise technique is included for improving approximations. Finally, both sound approximations and complete ones are covered. Based on the logic, we develop an approximation algorithm with a simple modification of classical instance-based theorem provers. The procedure yields approximate proofs whose precision increases as the reasoner has more resources at her disposal. The algorithm is interruptible, improvable, dual, and can be exploited for anytime computation. Moreover, the algorithm is flexible enough to be used with a wide range of propositional satisfiability methods.