Martin C. Cooper
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Martin C. Cooper has a total of 91 co-authors. Here are the top co-authors by number of shared publications:
David A. Cohen
Royal Holloway, University of London
11 shared publicationsStanislav Živný
University of Oxford
10 shared publicationsPeter G. Jeavons
University of Oxford
8 shared publications- Andrei Krokhin
Durham University Durham University
7 shared publications - Stanislav Živný
University of Oxford, Oxford, United Kingdom
7 shared publications - David A. Cohen
University of London
6 shared publications
Latest Publications
- 29 May 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 86
Explaining Multivariate Decision Trees: Characterising Tractable Languages
We study multivariate decision trees (MDTs), in particular, classes of MDTs determined by the language of relations that can be used to split feature space. An abductive explanation (AXp) of the classification of a particular instance, viewed as a set of feature-value assignments, is a minimal subset of the instance which is sufficient to lead to the same decision. We investigate when finding a single AXp is tractable. We identify tractable languages for real, integer and boolean features. Indeed, in the case of boolean languages, we provide a P/NP-hard dichotomy. We extend this dichotomy to languages defined by formulas whose literals correspond to splits of ordered domains of arbitrary finite size. Experiments indicate that MDTs can provide more compact models than classical decision trees while conserving accuracy and explainability.
- 29 May 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 86
Explaining Multivariate Decision Trees: Characterising Tractable Languages
We study multivariate decision trees (MDTs), in particular, classes of MDTs determined by the language of relations that can be used to split feature space. An abductive explanation (AXp) of the classification of a particular instance, viewed as a set of feature-value assignments, is a minimal subset of the instance which is sufficient to lead to the same decision. We investigate when finding a single AXp is tractable. We identify tractable languages for real, integer and boolean features. Indeed, in the case of boolean languages, we provide a P/NP-hard dichotomy. We extend this dichotomy to languages defined by formulas whose literals correspond to splits of ordered domains of arbitrary finite size. Experiments indicate that MDTs can provide more compact models than classical decision trees while conserving accuracy and explainability.
- 17 April 2026
- Published by Springer Nature
- p. 107-125
Formally Correct Search for Interpretable DNFs
- 11 April 2025
- Published by SAGE Publications in The European Journal on Artificial Intelligence
Analysis of Planning Instances Without Search
In order to prove classical planning instances unsolvable, state-of-the-art planners resort to a state space search. However, we show here that an incomplete, yet computationally efficient criterion is sometimes sufficient to immediately identify as unsolvable a wide range of planning instances. Based on linear and integer programming, we show in this paper how it can be leveraged, should it fail at first. This criterion is the keystone of various techniques we propose to rewrite and enhance the STRIPS model, so as to gather new information about it. If the newly found bits of information is not sufficient to identify the instance as unsolvable, they still constitute human-readable bits of information that can provide additional insight on the planning instance.
- 11 April 2025
- Published by SAGE Publications in The European Journal on Artificial Intelligence
Analysis of Planning Instances Without Search
In order to prove classical planning instances unsolvable, state-of-the-art planners resort to a state space search. However, we show here that an incomplete, yet computationally efficient criterion is sometimes sufficient to immediately identify as unsolvable a wide range of planning instances. Based on linear and integer programming, we show in this paper how it can be leveraged, should it fail at first. This criterion is the keystone of various techniques we propose to rewrite and enhance the STRIPS model, so as to gather new information about it. If the newly found bits of information is not sufficient to identify the instance as unsolvable, they still constitute human-readable bits of information that can provide additional insight on the planning instance.
- 24 March 2025
- Published by SAGE Publications in The European Journal on Artificial Intelligence
Analysis of Planning Instances Without Search
In order to prove classical planning instances unsolvable, state-of-the-art planners resort to a state space search. However, we show here that an incomplete, yet computationally efficient criterion is sometimes sufficient to immediately identify as unsolvable a wide range of planning instances. Based on linear and integer programming, we show in this paper how it can be leveraged, should it fail at first. This criterion is the keystone of various techniques we propose to rewrite and enhance the STRIPS model, so as to gather new information about it. If the newly found bits of information is not sufficient to identify the instance as unsolvable, they still constitute human-readable bits of information that can provide additional insight on the planning instance.
- 24 March 2025
- Published by SAGE Publications in The European Journal on Artificial Intelligence
Analysis of Planning Instances Without Search
In order to prove classical planning instances unsolvable, state-of-the-art planners resort to a state space search. However, we show here that an incomplete, yet computationally efficient criterion is sometimes sufficient to immediately identify as unsolvable a wide range of planning instances. Based on linear and integer programming, we show in this paper how it can be leveraged, should it fail at first. This criterion is the keystone of various techniques we propose to rewrite and enhance the STRIPS model, so as to gather new information about it. If the newly found bits of information is not sufficient to identify the instance as unsolvable, they still constitute human-readable bits of information that can provide additional insight on the planning instance.
- 8 February 2025
- Published by Springer Nature
- p. 21-37
Predicate-Based Explanation of a Reinforcement Learning Agent via Action Importance Evaluation
- 8 February 2025
- Published by Springer Nature
- p. 21-37
Predicate-Based Explanation of a Reinforcement Learning Agent via Action Importance Evaluation
- Open Access
- 10 December 2024
- Published by Wiley in Computational Intelligence
- Vol. 40 (6)
Homomorphisms and Embeddings of STRIPS Planning Models
Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance and a sub‐instance of another instance . One application of such a mapping is to efficiently produce a compiled form containing all solutions to from a compiled form containing all solutions to . We also introduce the notion of embedding from an instance to another instance , which allows us to deduce that has no solution‐plan if is unsolvable. In this paper, we study the complexity of these problems. We show that the first is GI‐complete and can thus be solved, in theory, in quasi‐polynomial time. While we prove the remaining problems to be NP‐complete, we propose an algorithm to build an isomorphism when possible. We report extensive experimental trials on benchmark problems that demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.
- 10 December 2024
- Published by Wiley in Computational Intelligence
- Vol. 40 (6)
Open AccessHomomorphisms and Embeddings of STRIPS Planning Models
Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance and a sub‐instance of another instance . One application of such a mapping is to efficiently produce a compiled form containing all solutions to from a compiled form containing all solutions to . We also introduce the notion of embedding from an instance to another instance , which allows us to deduce that has no solution‐plan if is unsolvable. In this paper, we study the complexity of these problems. We show that the first is GI‐complete and can thus be solved, in theory, in quasi‐polynomial time. While we prove the remaining problems to be NP‐complete, we propose an algorithm to build an isomorphism when possible. We report extensive experimental trials on benchmark problems that demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.
- Open Access
- 16 October 2024
- Published by IOS Press
- p. 770-777
Axiomatic Characterisations of Sample-based Explainers
Explaining decisions of black-box classifiers is both important and computationally challenging. In this paper, we scrutinize explainers that generate feature-based explanations from samples or datasets. We start by presenting a set of desirable properties that explainers would ideally satisfy, delve into their relationships, and highlight incompatibilities of some of them. We identify the entire family of explainers that satisfy two key properties which are compatible with all the others. Its instances provide sufficient reasons, called weak abductive explanations. We then unravel its various sub-families that satisfy subsets of compatible properties. Indeed, we fully characterize all the explainers that satisfy any subset of compatible properties. In particular, we introduce the first (broad family of) explainers that guarantee the existence of explanations and their global consistency. We discuss some of its instances including the irrefutable explainer and the surrogate explainer whose explanations can be found in polynomial time.
- 16 October 2024
- Published by IOS Press
- p. 770-777
Open AccessAxiomatic Characterisations of Sample-based Explainers
Explaining decisions of black-box classifiers is both important and computationally challenging. In this paper, we scrutinize explainers that generate feature-based explanations from samples or datasets. We start by presenting a set of desirable properties that explainers would ideally satisfy, delve into their relationships, and highlight incompatibilities of some of them. We identify the entire family of explainers that satisfy two key properties which are compatible with all the others. Its instances provide sufficient reasons, called weak abductive explanations. We then unravel its various sub-families that satisfy subsets of compatible properties. Indeed, we fully characterize all the explainers that satisfy any subset of compatible properties. In particular, we introduce the first (broad family of) explainers that guarantee the existence of explanations and their global consistency. We discuss some of its instances including the irrefutable explainer and the surrogate explainer whose explanations can be found in polynomial time.
- Open Access
- 16 October 2024
- Published by IOS Press
- p. 786-793
Backward Explanations via Redefinition of Predicates
History eXplanation based on Predicates (HXP), studies the behavior of a Reinforcement Learning (RL) agent in a sequence of agent’s interactions with the environment (a history), through the prism of an arbitrary predicate [21]. To this end, an action importance score is computed for each action in the history. The explanation consists in displaying the most important actions to the user. As the calculation of an action’s importance is #W[1]-hard, it is necessary for long histories to approximate the scores, at the expense of their quality. We therefore propose a new HXP method, called Backward-HXP, to provide explanations for these histories without having to approximate scores. Experiments show the ability of B-HXP to summarise long histories.
- 16 October 2024
- Published by IOS Press
- p. 786-793
Open AccessBackward Explanations via Redefinition of Predicates
History eXplanation based on Predicates (HXP), studies the behavior of a Reinforcement Learning (RL) agent in a sequence of agent’s interactions with the environment (a history), through the prism of an arbitrary predicate [21]. To this end, an action importance score is computed for each action in the history. The explanation consists in displaying the most important actions to the user. As the calculation of an action’s importance is #W[1]-hard, it is necessary for long histories to approximate the scores, at the expense of their quality. We therefore propose a new HXP method, called Backward-HXP, to provide explanations for these histories without having to approximate scores. Experiments show the ability of B-HXP to summarise long histories.
- Open Access
Abductive explanations of classifiers under constraints: Complexity and properties
Abductive explanations (AXp's) are widely used for understanding decisions of classifiers. Existing definitions are suitable when features are independent. However, we show that ignoring constraints when they exist between features may lead to an explosion in the number of redundant or superfluous AXp's. We propose three new types of explanations that take into account constraints and that can be generated from the whole feature space or from a sample (such as a dataset). They are based on a key notion of coverage of an explanation, the set of instances it explains. We show that coverage is powerful enough to discard redundant and superfluous AXp's. For each type, we analyse the complexity of finding an explanation and investigate its formal properties. The final result is a catalogue of different forms of AXp's with different complexities and different formal guarantees.
Open AccessAbductive explanations of classifiers under constraints: Complexity and properties
Abductive explanations (AXp's) are widely used for understanding decisions of classifiers. Existing definitions are suitable when features are independent. However, we show that ignoring constraints when they exist between features may lead to an explosion in the number of redundant or superfluous AXp's. We propose three new types of explanations that take into account constraints and that can be generated from the whole feature space or from a sample (such as a dataset). They are based on a key notion of coverage of an explanation, the set of instances it explains. We show that coverage is powerful enough to discard redundant and superfluous AXp's. For each type, we analyse the complexity of finding an explanation and investigate its formal properties. The final result is a catalogue of different forms of AXp's with different complexities and different formal guarantees.
- Open Access
Axiomatic Characterisations of Sample-based Explainers
Explaining decisions of black-box classifiers is both important and computationally challenging. In this paper, we scrutinize explainers that generate feature-based explanations from samples or datasets. We start by presenting a set of desirable properties that explainers would ideally satisfy, delve into their relationships, and highlight incompatibilities of some of them. We identify the entire family of explainers that satisfy two key properties which are compatible with all the others. Its instances provide sufficient reasons, called weak abductive explanations.We then unravel its various subfamilies that satisfy subsets of compatible properties. Indeed, we fully characterize all the explainers that satisfy any subset of compatible properties. In particular, we introduce the first (broad family of) explainers that guarantee the existence of explanations and their global consistency.We discuss some of its instances including the irrefutable explainer and the surrogate explainer whose explanations can be found in polynomial time.
Open AccessAxiomatic Characterisations of Sample-based Explainers
Explaining decisions of black-box classifiers is both important and computationally challenging. In this paper, we scrutinize explainers that generate feature-based explanations from samples or datasets. We start by presenting a set of desirable properties that explainers would ideally satisfy, delve into their relationships, and highlight incompatibilities of some of them. We identify the entire family of explainers that satisfy two key properties which are compatible with all the others. Its instances provide sufficient reasons, called weak abductive explanations.We then unravel its various subfamilies that satisfy subsets of compatible properties. Indeed, we fully characterize all the explainers that satisfy any subset of compatible properties. In particular, we introduce the first (broad family of) explainers that guarantee the existence of explanations and their global consistency.We discuss some of its instances including the irrefutable explainer and the surrogate explainer whose explanations can be found in polynomial time.