48 citations · 232 across the 19 of their papers we have counts for
21 papers
On Computing Probabilistic Abductive Explanations
Yacine Izza, Xuanxiang Huang, Alexey Ignatiev +3
The most widely studied explainable AI (XAI) approaches are unsound. This is the case with well-known model-agnostic explanation approaches, and it is also the case with approaches…
Feature Necessity & Relevancy in ML Classifier Explanations
Xuanxiang Huang, Martin C. Cooper, Antonio Morgado +2
Given a machine learning (ML) model and a prediction, explanations can be defined as sets of features which are sufficient for the prediction. In some applications, and besides ask…
Provably Precise, Succinct and Efficient Explanations for Decision Trees
Yacine Izza, Alexey Ignatiev, Nina Narodytska +2
Decision trees (DTs) embody interpretable classifiers. DTs have been advocated for deployment in high-risk applications, but also for explaining other complex classifiers. Neverthe…
Efficient Explanations for Knowledge Compilation Languages
Xuanxiang Huang, Yacine Izza, Alexey Ignatiev +3
Knowledge compilation (KC) languages find a growing number of practical uses, including in Constraint Programming (CP) and in Machine Learning (ML). In most applications, one natur…
Efficient Explanations With Relevant Sets
Yacine Izza, Alexey Ignatiev, Nina Narodytska +2
Recent work proposed -relevant inputs (or sets) as a probabilistic explanation for the predictions made by a classifier on a given input. -relevant sets are significant becau…
Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay
Joao Marques-Silva, Thomas Gerspacher, Martin C. Cooper +2
Recent work proposed the computation of so-called PI-explanations of Naive Bayes Classifiers (NBCs). PI-explanations are subset-minimal sets of feature-value pairs that are suffici…
Strengthening neighbourhood substitution
Martin C. Cooper
Domain reduction is an essential tool for solving the constraint satisfaction problem (CSP). In the binary CSP, neighbourhood substitution consists in eliminating a value if there…
Steepest ascent can be exponential in bounded treewidth problems
David A. Cohen, Martin C. Cooper, Artem Kaznatcheev +1
We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variabl…
Variable elimination in binary CSPs
Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux
We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We study variable-elimination rules…
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Clement Carbonnel, David A. Cohen, Martin C. Cooper +1
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of…
Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +1
The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variab…
Binarisation for Valued Constraint Satisfaction Problems
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +3
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the alge…
Simple epistemic planning: generalised gossiping
Martin C. Cooper, Andreas Herzig, Faustine Maffre +2
The gossip problem, in which information (known as secrets) must be shared among a certain number of agents using the minimum number of calls, is of interest in the conception of c…
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
Martin C. Cooper, Stanislav Živný
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding pa…
Variable and value elimination in binary constraint satisfaction via forbidden patterns
David A. Cohen, Martin C. Cooper, Guillaume Escamocher +1
Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (val…
On Backdoors To Tractable Constraint Languages
Clement Carbonnel, Martin C. Cooper, Emmanuel Hebrard
In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the pr…
Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
Martin C. Cooper, Stanislav Živný
The minimisation problem of a sum of unary and pairwise functions of discrete variables is a general NP-hard problem with wide applications such as computing MAP configurations in…
An Algebraic Theory of Complexity for Discrete Optimisation
David A. Cohen, Martin C. Cooper, Paidi Creed +2
Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a su…
A Dichotomy for 2-Constraint Forbidden CSP Patterns
Martin C. Cooper, Guillaume Escamocher
Although the CSP (constraint satisfaction problem) is NP-complete, even in the case when all constraints are binary, certain classes of instances are tractable. We study classes of…
The tractability of CSP classes defined by forbidden patterns
David A. Cohen, Martin C. Cooper, Páidí Creed +1
The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort…
Hybrid tractability of soft constraint problems
Martin C. Cooper, Stanislav Zivny
The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems…