Author name cluster

Martin Cooper

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

AAMAS Conference 2026 Conference Paper

Axiomatic Foundations of Counterfactual Explanations

Leila Amgoud
Martin Cooper

Explaining autonomous and intelligent systems is critical in order to improve trust in their decisions. Counterfactuals have emerged as one of the most compelling forms of explanation. They address “why not” questions by revealing how decisions could be altered. Despite the growing literature, most existing explainers focus on a singletype ofcounterfactualandarerestrictedtolocal explanations, focusing on individual instances. There has been no systematic study of alternative counterfactual types, nor of global counterfactuals that shed light on a system’s overall reasoning process. This paper addresses the two gaps by introducing an axiomatic framework built on a set of desirable properties for counterfactual explainers. It proves impossibility theorems showing that no single explainer can satisfy certain axiom combinations simultaneously, and fully characterizes all compatible sets. Representation theorems then establish five one-to-one correspondences between specific subsets of axioms and the families of explainers that satisfy them. Each family gives rise to a distinct type of counterfactual explanation, uncovering five fundamentally different types of counterfactuals. Some of these correspond to local explanations, while others capture global explanations. Finally, the framework situates existing explainers within this taxonomy, formally characterizes their behavior, and analyzes the computational complexity of generating such explanations.

PDF

AAAI Conference 2022 Conference Paper

Tractable Explanations for d-DNNF Classifiers

Xuanxiang Huang
Yacine Izza
Alexey Ignatiev
Martin Cooper
Nicholas Asher
Joao Marques-Silva

Compilation into propositional languages finds a growing number of practical uses, including in constraint programming, diagnosis and machine learning (ML), among others. One concrete example is the use of propositional languages as classifiers, and one natural question is how to explain the predictions made. This paper shows that for classifiers represented with some of the best-known propositional languages, different kinds of explanations can be computed in polynomial time. These languages include deterministic decomposable negation normal form (d-DNNF), and so any propositional language that is strictly less succinct than d-DNNF. Furthermore, the paper describes optimizations, specific to Sentential Decision Diagrams (SDDs), which are shown to yield more efficient algorithms in practice.

PDF Details

NeurIPS Conference 2020 Conference Paper

Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay

Joao Marques-Silva
Thomas Gerspacher
Martin Cooper
Alexey Ignatiev
Nina Narodytska

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 sufficient for the prediction, and have been computed with state-of-the-art exact algorithms that are worst-case exponential in time and space. In contrast, we show that the computation of one PI-explanation for an NBC can be achieved in log-linear time, and that the same result also applies to the more general class of linear classifiers. Furthermore, we show that the enumeration of PI-explanations can be obtained with polynomial delay. Experimental results demonstrate the performance gains of the new algorithms when compared with earlier work. The experimental results also investigate ways to measure the quality of heuristic explanations.

PDF Details

KR Conference 2020 Conference Paper

Lightweight Parallel Multi-Agent Epistemic Planning

Martin Cooper
Andreas Herzig
Frédéric Maris
Elise Perrotin
Julien Vianey

We study a simple version of multi-agent epistemic planning where the number of parallel steps has to be minimized. We prove that this extension of classical planning is in PSPACE. We propose an encoding in PDDL and present some experiments providing evidence that this encoding allows us to solve practical problems. The types of problems we can encode include problems in which one agent can teach another agent how to perform a task and communication problems where some information must not be revealed to some agents.

PDF Details DOI

AAAI Conference 2015 Conference Paper

Binarisation via Dualisation for Valued Constraints

David Cohen
Martin Cooper
Peter Jeavons
Stanislav Zivny

Constraint programming is a natural paradigm for many combinatorial optimisation problems. The complexity of constraint satisfaction for various forms of constraints has been widely-studied, both to inform the choice of appropriate algorithms, and to understand better the boundary between polynomial-time complexity and NP-hardness. In constraint programming it is well-known that any constraint satisfaction problem can be converted to an equivalent binary problem using the so-called dual encoding. Using this standard approach any fixed collection of constraints, of arbitrary arity, can be converted to an equivalent set of constraints of arity at most two. Here we show that this transformation, although it changes the domain of the constraints, preserves all the relevant algebraic properties that determine the complexity. Moreover, we show that the dual encoding preserves many of the key algorithmic properties of the original instance. We also show that this remains true for more general valued constraint languages, where constraints may assign different cost values to different assignments. Hence, we obtain a simple proof of the fact that to classify the computational complexity of all valued constraint languages it suffices to classify only binary valued constraint languages.

PDF Details

AAAI Conference 2012 Conference Paper

A Dichotomy for 2-Constraint Forbidden CSP Patterns

Martin Cooper
Guillaume Escamocher

Novel tractable classes of the binary CSP (constraint satisfaction problem) have recently been discovered by studying classes of instances defined by excluding subproblems described by patterns. The complete characterisation of all tractable classes defined by forbidden patterns is a challenging problem. We demonstrate a dichotomy in the case of forbidden patterns consisting of two constraints.

PDF Details

AAAI Conference 2008 Conference Paper

Virtual Arc Consistency for Weighted CSP

Martin Cooper
Marti Sanchez

Optimizing a combination of local cost functions on discrete variables is a central problem in many formalisms such as in probabilistic networks, maximum satisfiability, weighted CSP or factor graphs. Recent results have shown that maintaining a form of local consistency in a Branch and Bound search provides bounds that are strong enough to solve many practical instances. In this paper, we introduce Virtual Arc Consistency (VAC) which iteratively identifies and applies sequences of cost propagation over rational costs that are guaranteed to transform a WCSP in another WCSP with an improved constant cost. Although not as strong as Optimal Soft Arc Consistency, VAC is faster and powerful enough to solve submodular problems. Maintaining VAC inside branch and bound leads to important improvements in efficiency on large difficult problems and allowed us to close two famous frequency assignment problem instances.

PDF Details

AIJ Journal 2004 Journal Article

Arc consistency for soft constraints

Martin Cooper
Thomas Schiex

The notion of arc consistency plays a central role in constraint satisfaction [R. Dechter, Constraint Processing, Morgan Kaufmann, San Mateo, CA, 2003]. It is known since the introduction of valued and semi-ring constraint networks in 1995 that the notion of local consistency can be extended to constraint optimisation problems defined by soft constraint frameworks based on an idempotent cost combination operator. This excludes non-idempotent operators such as + which define problems which are very important in practical applications such as Max-CSP, where the aim is to minimise the number of violated constraints. In this paper, we show that using a weak additional axiom satisfied by most existing soft constraints proposals, it is possible to define a notion of soft arc consistency that extends the classical notion of arc consistency and this even in the case of non-idempotent cost combination operators. A polynomial time algorithm for enforcing this soft arc consistency exists and its space and time complexities are identical to that of enforcing arc consistency in CSPs when the cost combination operator is strictly monotonic (for example Max-CSP). A directional version of arc consistency, first introduced by M. C. Cooper [Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets and Systems 134 (3) (2003) 311–342] is potentially even stronger than the non-directional version, since it allows non-local propagation of penalties. We demonstrate the utility of directional arc consistency by showing that it not only solves soft constraint problems on trees, but that it also implies a form of local optimality, which we call arc irreducibility.

Details DOI

IJCAI Conference 2003 Conference Paper

A Maximal Tractable Class of Soft Constraints

David Cohen
Martin Cooper
Peter Jeavons
Andrei Krokhin

Many optimization problems can be expressed us ing some form of soft constraints, where different measures of desirability arc associated with differ ent combinations of domain values for specified subsets of variables. In this paper we identify a class of soft binary constraints for which the prob lem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time al gorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as "as near as possible" or "as soon as possible after", as well as crisp constraints such as "greater than'1.

PDF