Cl‚ément Carbonnel

Martin C. Cooper, Imane Bousdira, Clément Carbonnel

A classifier is considered interpretable if each of its decisions has an explanation which is small enough to be easily understood by a human user. A DNF formula can be seen as a binary classifier $κ$ over boolean domains. The size of an explanation of a positive decision taken by a DNF $κ$ is bounded by the size of the terms in $κ$, since we can explain a positive decision by giving a term of $κ$ that evaluates to true. Since both positive and negative decisions must be explained, we consider that interpretable DNFs are those $κ$ for which both $κ$ and $\overlineκ$ can be expressed as DNFs composed of terms of bounded size. In this paper, we study the family of $k$-DNFs whose complements can also be expressed as $k$-DNFs. We compare two such families, namely depth-$k$ decision trees and nested $k$-DNFs, a novel family of models. Experiments indicate that nested $k$-DNFs are an interesting alternative to decision trees in terms of interpretability and accuracy.

Christian Bessiere, Clement Carbonnel, Anton Dries et al.

Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QUACQ, that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases.

Clement Carbonnel, David A. Cohen, Martin C. Cooper et al.

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 bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.

Clément Carbonnel

Given a fixed constraint language $Γ$, the conservative CSP over $Γ$ (denoted by c-CSP($Γ$)) is a variant of CSP($Γ$) where the domain of each variable can be restricted arbitrarily. A dichotomy is known for conservative CSP: for every fixed language $Γ$, c-CSP($Γ$) is either in P or NP-complete. However, the characterization of conservatively tractable languages is of algebraic nature and the naive recognition algorithm is super-exponential in the domain size. The main contribution of this paper is a polynomial-time algorithm that, given a constraint language $Γ$ as input, decides if c-CSP($Γ$) is tractable. In addition, if $Γ$ is proven tractable the algorithm also outputs its coloured graph, which contains valuable information on the structure of $Γ$.

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 property allows efficient solving, then a small strong backdoor provides a reasonable decomposition of the original instance into easy instances. An important challenge is the design of algorithms that can find quickly a small strong backdoor if one exists. We present a systematic study of the parameterized complexity of backdoor detection when the target property is a restricted type of constraint language defined by means of a family of polymorphisms. In particular, we show that under the weak assumption that the polymorphisms are idempotent, the problem is unlikely to be FPT when the parameter is either r (the constraint arity) or k (the size of the backdoor) unless P = NP or FPT = W[2]. When the parameter is k+r, however, we are able to identify large classes of languages for which the problem of finding a small backdoor is FPT.