On Translations between ML Models for XAI Purposes

1 Introduction

During the past decades, the main motivation for designing new ML models was to improve the learning performance. More recently, the quest for eXplainable AI (XAI) [Goodman and Flaxman, 2017; Gunning, 2019] has led to consider another goal than pure learning performance when opting for an ML model, namely its ability to offer XAI facilities (see e.g., [Adadi and Berrada, 2018; Miller, 2019; Samek et al., 2019; Guidotti et al., 2019; Srinivasan and Chander, 2020; Molnar, 2019; Lundberg et al., 2020; Rudin et al., 2021]). Beyond predictions, explanations of the predictions are sought for. In the same vein, verification queries enabling to check whether the predictor under consideration behaves as expected are looked for.

A major concern is that the two objectives (accuracy and XAI) can be antagonistic. Thus, predictors with high prediction performance are usually considered as poorly intelligible (see e.g., [Molnar, 2019; Arrieta et al., 2020; Caruana et al., 2020]), even if the lack of algorithms for answering XAI queries in practice does not always come with strong arguments against the existence of such algorithms (the absence of efficient algorithms not implying their impossibility). That mentioned, the need for explanation and verification hampers the further applications of ML machinery, especially when those applications directly affect human beings. Our society now calls for trustworthy AI, hence it is important to investigate approaches for providing ML models with XAI facilities.

In this perspective, our work falls under the so-called formal XAI umbrella [Marques-Silva and Ignatiev, 2022] and is relevant to the model-specific approach to post-hoc explanation. Thus, a predictor is supposed to have been learned and the goal is to equip it with XAI methods, allowing users to reason about the behavior of the predictor, and to understand why instances have been classified as they have been, or not classified as the user would expect. We assume that the learned predictor can be associated with a circuit that has precisely the same behaviour in terms of inputs/outputs (see e.g., [Narodytska et al., 2018; Shih et al., 2018; Shih et al., 2019]). Then, the XAI facilities that are required can be delegated to the corresponding circuit (automated reasoning techniques are usually leveraged to achieve them) [Darwiche and Hirth, 2020; Barcel ´o et al., 2020; Parmentier and Vidal, 2021]. Using such an approach, no approximation of the predictor is performed and as a consequence, rigorous explanations [Ignatiev, 2020] can be derived (i.e., the predictor itself is explained, not a surrogate). This is of utmost importance when ML techniques are considered in safety-critical applications.

For the past few years, many XAI algorithms have been designed and evaluated for various ML models, and the collection of such algorithms is ever-increasing (see [MarquesSilva, 2022] for a recent survey). The research question considered in the present work is about the existence of translations between ML models. The goal is to determine whether or not one can take advantage of XAI algorithms when dealing with ML models other than that for which they have been conceived, provided that a sufficiently efficient translation between the models exists. Addressing this issue amounts to determining how computationally demanding it is to translate a predictor from an input ML model into a predictor from another (output) model for which XAI facilities are available. In this paper, we are interested in equivalence-preserving translations (i.e., the output predictor is equivalent to the input predictor) since we want to guarantee that the explanations computed when rigorous for the output predictor are also rigorous for the input predictor.

To make things concrete, suppose that a predictor fC from a given ML model C (e.g., C is the class BT of boosted trees) has been learned and that we want to derive contrastive explanations (see e.g., [Miller, 2019; Guidotti, 2022]) for instances x classified by fC, but we do not have an XAI algorithm to perform this task. Suppose that a translation τ exists from C to another ML model C ′ (e.g., C ′ is the class BMP of Boolean multilayer perceptrons), and that an XAI algorithm xai (e.g., to derive a contrastive explanation for an instance x) suited to any predictor fC′ from C ′ is available. Then we immediately get an XAI algorithm for the same task but now suited to any predictor fC from C: just compute xai(τ(fC), x).

Computationally speaking, we are interested in two types of translation: polynomial-time translations, and polynomialspace translations. A polynomial-time translation from an ML model C to an ML model C ′ , noted C ≤p C ′ , ensures that any polynomial-time XAI algorithm for C ′ can be turned into a polynomial-time XAI algorithm for C. Polynomial-space translations, noted C ≤s C ′ , guarantee that the output predictor from C is of size polynomial in the size of the input predictor from C ′ . Clearly, if C ≤p C ′ holds then C ≤s C ′ holds as well, but the converse is false in general. Indeed, no assumptions are made on the time needed to produce the output predictor when C ≤s C ′ holds. Polynomial-space translations can be nevertheless useful when no XAI algorithms are available for C, or when the computation time required for achieving the translation can be balanced by considering sufficiently many queries (and explanation queries can indeed be numerous since the instances to be explained are numerous as well). When no polynomial-space translation exists from C ′ to C, there is no way to turn the polynomial-time XAI algorithms for C ′ into polynomial-time XAI algorithms for C.

In this work, we initiate a systematic comparison of ML models, viewed as classes of binary classifiers, with respect to the ≤p and the ≤s relationships. Thus, for the classifiers considered, input variables are over {0, 1} and a classifier maps every assignment to its variables to either 0 or 1. We consider well-known models of binary classifiers, that are conveniently summarized together in [Audemard et al., 2021]. These models are briefly described in this paragraph and in more details in Section 2. Our contributions are spread in the paper as follows. In Section 3, we consider tree-based classifiers that are linear predictors over decision trees (DT). These are sets of decision trees T1, . . . , Tm such that an assignment is mapped to 1 if and only if the sum of the outputs of the decision trees exceeds a certain threshold. We compare random forests (RF): every tree can return +1 or -1; boosted trees with trees Ti associated with weights wi ∈ Q (BT): every tree Ti can return +wi or -wi; and boosted regression trees (BRT), where weights are associated with tree leaves, and every tree can return any number in Q. We show a strong separation between RF and BT (and BRT), in the sense that BT ≤p RF but RF ≰s BT. We also describe a, perhaps unexpected, polynomial-time translation from BRT to BT. In Section 4, we look at network models, with binary neural networks (BNN) and Boolean multilayer perceptrons (BMP). There, we show a close connection between these models and threshold circuits using "small" integer weights (̂ TH) and threshold circuits using any integer weights (TH). We lean on this connection to strongly separate BNN and BMP from tree-based classifiers, and to show that BNN ≤p BMP. In Section 5, we add to the analysis a few other classes of representations of Boolean functions (which can be seen as classes of binary classifiers). Those classes include the wellknown formulas in conjunctive normal form (CNF) and in disjunctive normal form (DNF), and the (less well-known) circuits in decomposable negation normal form (DNNF). These circuits have recently been suggested as useful representations for answering XAI queries [Audemard et al., 2020; Darwiche and Hirth, 2020]. Other related work are discussed in Section 6.

Our results are summarized in Figure 1, presenting a Hasse diagram that can be read as follows for both ≤∈ {≤p, ≤s}:

• an arrow C → C ′ means that C ′ ≤ C but that C ≰ C ′ ,
• a double harpoon C ⇌ C ′ means that C ≤ C ′ and C ′ ≤ C,
• no link between C and C ′ means either that the relationship can be derived by transitivity, or that C ≰ C ′ and C ′ ≰ C.

Notably, most polynomial-time translations pointed out in the following can be envisioned in practice since they run in linear time in the size of the initial classifier. A notable exception is the translation from BMP to BNN, that runs in time at least quadratic in the size of the classifier. Our results are discussed in Section 7. Due to space constraints, many proofs are deferred to the full version of this paper available here: www.cril.fr/expekctation/papers/deColnetMarquis-IJCAI23-full-proof.pdf.

2 Preliminaries

A Boolean variable is a variable over {0, 1}. A literal is a Boolean variable x or its negation x. An assignment a to a set X of Boolean variables is a mapping from X to {0, 1}. We denote by {0, 1}X the set of all assignments to X. A Boolean function over X is a mapping from {0, 1}X to {0, 1}. The symbols ∧, ∨ are used to denote conjunction and disjunction, respectively. A clause is a disjunction of literals and a term is a conjunction of literals. A formula in CNF is a conjunction of clauses and a formula in DNF is a disjunction of terms.

2.1 Tree-BasedModels

Let X be a finite set of Boolean variables and let a be an assignment to X. A decision node labelled by x ∈ X is a node of the form x interpreted as follows: if x is

set to 0 (resp. 1) then follow the dashed (resp. plain) arrow.

Decision tree. A decision tree over X and about a set Y [Breiman et al., 1984; Quinlan, 1986] represents a mapping from {0, 1}X to Y . It is a rooted tree where internal nodes are decision nodes labelled by variables in X, and leaves are elements in Y . We assume wlog that any variable labels at most one node of every root-to-leaf path. DTY denotes the set of decision trees over X about Y . For convenience we write DT = DT{0,1} and DT± = DT{-1,1}. The label of the leaf obtained when following the path consistent with a complete assignment a in the tree T is denoted by T(a).

Random forest. Decision trees can be generalized to tree ensembles, using ensemble learning techniques, such as bagging and boosting. Notably, the random forest method generates multiple decision trees according to a variant of bagging. Thus, a random forest over X [Breiman, 2001] is a finite set of binary decision trees over X in DT±. The random forest classifier composed of the trees T1, T2, . . . , Tm represents the Boolean function over X that evaluates to 1 on a if and only if ∑mi=1 Ti(a) ≥ 0. RF denotes the class of random forests.

Boosted tree. Tree ensembles can also be trained using the boosting technique. Thus, a boosted tree is a random forest whose trees Ti or tree leaves are associated with weights wi in Q. When weights are associated with trees, the classifier corresponding to (T1,w1), . . . , (Tm,wm) represents the Boolean function that evaluates to 1 on a if and only if ∑mi=1 wi · Ti(a) ≥ 0. When the weights are not associated with the trees but with their leaves, we end up with a forest whose trees are from DTQ (equivalently, one can view them as regression trees). The classifier corresponding to T1, . . . , Tm ∈ DTQ represents the Boolean function that evaluates to 1 on a if and only if ∑mi=1 Ti(a) ≥ 0. BT denotes the class of boosted trees with trees associated with weights, and BRT the class of boosted trees with tree leaves associated with weights (aka "boosted regression trees").

Standard learning algorithms for generating boosted trees output predictors from BT (e.g., this is the case of AdaBoost [Freund and Schapire, 1997; Schapire and Freund, 2014]) or they output predictors from BRT (e.g., this is the case of XGBoost [Chen and Guestrin, 2016], LightGBM [Ke et al., 2017] and CatBoost [Prokhorenkova et al., 2018]).

We denote by |T| the number of nodes (including leaves) of the decision tree T . More generally, the size of a classifier C is written |C|. If C is a random forest T1, . . . , Tm, then |C| = ∑mi=1 |Ti|. If C is a boosted tree T1, . . . , Tm, then |C| is ∑mi=1 |Ti| plus the space needed to store the weights in memory. We will often assume that the weights are in Z and are encoded in binary with no limit on the number of bits (note by the way that |wi| denotes the absolute value of wi and not the number of bits in its encoding).

2.2 Network Classifiers

Boolean multilayer perceptrons. A (feedforward) neural network is a directed acyclic graph whose edges are labeled with weights in Q, and nodes (alias neurons) correspond to input variables over Q when their fan-in is 0, and to functions over their weighted inputs otherwise. In a multilayer neural network, the nodes are partitioned in sets L1, . . . ,Ld called layers such that any edge is directed from a node of Li to a node of Li+1 for some i < d. The input layer L1 contains only the input variables. The nodes of the output layer Ld all have fan-out 0 and compute the output vector of the network. For every i < d, the layers Li and Li+1 are supposed fully connected in the sense that all nodes of Li are connected to all nodes of Li+1. A Boolean multilayer perceptron (see e.g., [Anthony, 2001]) is a multilayer neural network whose input variables are Boolean, whose output layer contains a single node, and whose non-input nodes are threshold gates. Formally, a threshold gate over inputs x1, . . . , xn, associated respectively to rational numbers (weights) w1, . . . ,wn, is a function

where sgn(k) = -1 if k < 0 and sgn(k) = 1 otherwise, and θ is a fixed number in Q. If the inputs are variables over {0, 1}, then the function is equivalent to sgn(∑ni=1 w′i ·x′i -θ′ ) where w′i = -wi, θ′ = 2θ - ∑ni=1 wi and x′i = 1 - 2xi takes value in {-1, 1}. So we will often assume that the inputs of the circuits are over {-1, 1}. We denote by BMP the class of all Boolean multilayer perceptrons. We view BMP as a class of representations for Boolean functions: we just have to assume that the output gate returns 0 or 1 instead of 1 or -1 (respectively). 1

Binarized neural network. Binarized neural networks (BNN) [Hubara et al., 2016] can be seen as Boolean multilayer perceptrons whose weights range in {-1, 1}, that is, all threshold gates are of the form yj = sgn(∑ni=1 si,j · xi - θj) where si,j ∈ {-1, 1}. For completeness, we nevertheless consider as well the following more technical but more standard description. Let x = (x1, . . . , xn) and y = (y1, . . . , ym) be respectively the input vector and the output vector of a layer L where all variables xi and yi ranges in {-1, 1}. In a BNN, it is usual to break the threshold gates into three parts, in particular yj is computed as follows, where bj, αj, µj, νj, γj ∈ Q and νj ̸= 0:

1. Linear transformation: compute y′j = ∑ni=1 si,j · xi + bj
2. Batch normalization: compute y′′ j = αj (y′j -µj ) νj +γj
3. Binarization: yj = sgn(y′′ j ).

Assuming αj ̸= 0, one indeed has yj = sgn(∑ni=1 si,j · xi - θj) where θj = µj - bj - νjγj/αj (if αj = 0, then yj is a constant and the gate can be removed from L while modifying parameters of the next layer). It will be simpler to consider that the nodes of a BNN are threshold gates with weights in {-1, 1} than to use the three-step computation. Just as for Boolean multilayer perceptrons, we assume whenever it is convenient that the inputs of the circuits are variables in {-1, 1} and not variables in {0, 1}. We denote by BNN the class of all binarized neural networks, which we again view as a class of representations for Boolean functions.

The size of a BMP or of a BNN classifier C is its number of edges, plus the number of bits needed to write all the weights and thresholds used in threshold gates.

2.3 Translations

A class C of representations for Boolean functions is fully expressive when every Boolean function over finitely many variables has a representation in C. In the following, the classes C and C ′ are fully expressive.

1 An important research strand on Boolean functions considers variables over {-1, 1} instead of {0, 1}. The usual translation is "1 becomes 0, and -1 becomes 1", see for instance [O'Donnell, 2014].

Polynomial-time translations. We say that there is a polynomial-time translation from C ′ to C, denoted by C ≤p C ′ , when there is a polynomial-time algorithm that, for every C ′ ∈ C ′ returns some C ∈ C representing the same function as C ′ . When C ≤p C ′ and C ′ ≤p C hold, we note C ≃p C ′ .

Polynomial-space translations. We say that there is a polynomial-space translation from C ′ to C (or, equivalently, that C is at least as succinct as C ′ ), denoted by C ≤s C ′ , when there is a polynomial p such that, for every C ′ ∈ C ′ , there exists a representation C ∈ C of the same function whose size is |C| ≤ p(|C ′ |). We say that C is strictly more succinct than C ′ when C ≤s C ′ but C ′ ≰s C. We say that C and C ′ are equally succinct, denoted by C ≃s C ′ , when C ≤s C ′ and C ′ ≤s C.

Clearly enough, ≤p and ≤s are reflexive and transitive. Furthermore, C ′ ⊆ C implies C ≤p C ′ and C ≤p C ′ implies C ≤s C ′ .

3 Translations between Tree-BasedModels

In this section, we describe the ≤p and ≤s relationships between the classes of binary classifiers DT, RF, BT, BRT. For most pairs of classes, one side of the relationship is trivial. In particular, it is clear that BRT ≤p BT ≤p RF ≤p DT. It remains to study the other direction. Using a function as simple as majorityn over n variables that evaluates to 1 if and only if at least ⌊n/2⌋ variables are set to 1, we can separate RF from DT in terms of succinctness:

Proposition 1. We have RF ≤p DT and DT ≰s RF.

3.1 Comparing BT and RF

Weights used in boosted trees can, in theory, be arbitrary numbers in Q, but they can all be multiplied by the least common multiple of their denominators without modifying the function represented by the classifier. For reasonable representations of rationals, this only results in a polynomial-size increase on the space needed to store the weights. So, from now on, we assume that all weights are in Z \ {0}.

When the weights w1, . . . ,wn are integers, w1 · T1 + · · · + wm · Tm can be turned into an unweighted sum of decision trees by creating, for every i ≤ m, |wi| clones T 1 i , T 2 i , . . . , T |wi| i of Ti where the sign of a leaf is switched when wi < 0. Indeed, we have that wi · Ti = ∑|wi| j=1 T j i so the boosted tree (T1,w1), . . . , (Tm,wm) is equivalent to the random forest ⋃mi=1 {T 1 i , . . . , T |wi| i }. Clearly this translation is useful only when maxi|wi| is small, but it teaches us that the encoding of integer weights in memory is important. In particular, if the weights were encoded in unary, or if they were encoded in binary with a fixed number of bits, then BT and RF would be equally succinct, even though the translation from BT to RF is impractical. But because we assume that weights are represented in binary with no limit on the number of bits, it turns out that RF ≰s BT. To see this, we lean on a result of Goldmann, H˚astad and Razborov [Goldmann et al., 1992]. Consider the Boolean variables X∪Y := {xi,j | 1 ≤ i ≤ n, 1 ≤ j ≤ 4n} ∪ {yj | 1 ≤ j ≤ 2n} and let:

where x′ = 1 - 2x. Goldmann et al. show that p(X, Y ) is hard to represent with depth-2 threshold circuits (a circuit that has two levels of threshold gates) using small weights.

Proposition 2. [Goldmann et al., 1992, Corollary 7] If p(X, Y ) is computed by a depth-2 threshold circuit with weights bounded by w and size s then sw2 ≥ Ω( 2n/2 n5/2 ).

We use p(X, Y ) to separate BT and RF in terms of succinctness. First, it is easy to represent y′j x′i,2j and y′j x′i,2j+1 by decision trees, so it is easy to represent p(X, Y ) in BT.

Proposition 3. There exists a set of boosted trees of size O(n2 ) that represents p(X, Y ).

But we can also show that, if there was a small random forest representing p(X, Y ), then there would be a small depth2 threshold circuit computing p(X, Y ) using only small weights which, by Proposition 2, cannot be.

Proposition 4. Every random forest representing p(X, Y ) has size Ω( 2n/2 n5/2 ).

Combining Proposition 3 and Proposition 4, we obtain the following.

Proposition 5. We have BT ≤p RF and RF ≰s BT.

3.2 Comparing BRT and BT

We now give a polynomial-time translation from boosted regression trees to boosted trees.

Proposition 6. There is a quadratic-time translation from BRT to BT. Thus BT ≤p BRT.

Proof. Let T1, . . . , Tm be the trees composing C ∈ BRT. Recall that their leaves are labelled by integers. Let Wi be the set of integers distinct from 0 that label leaves of Ti. Note that |Wi| ≤ |Ti|. For every w ∈ Wi, let Ti,w be the decision tree obtained from Ti by changing to 0 the weight of every leaf that is not w. Observe that Ti = ∑w∈Wi Ti,w. Next let T - i,w be the decision tree obtained from Ti,w by replacing every weight 0 by -1 and by replacing every weight w by 1, and let T + i,w be a decision tree that consists of a single leaf labelled by 1. Note that T - i,w and T + i,w are in DT± and that Ti,w = w2 (T - i,w + T + i,w ). Thus ∑mi=1 Ti ≥ 0 is equivalent to

where T0 is the tree consisting of a single leaf labelled by 1. The last inequality corresponds to a classifier C ′ in BT composed of 1 + ∑mi=1 |Wi| trees. For every Ti with i ≥ 1 and every w ∈ Wi, T - i,w is constructed in time O(|Ti|). So constructing the trees in C ′ takes time O(∑i (|Wi| × |Ti|)) ≤ O(∑i |Ti|2 ). Finally, the weights of C ′ are exactly those of C except for the weight of T0 which is a sum of integers computed in time linear in the number of bits needed to write all weights.

To illustrate the translation used in the proof above, consider the tree Ti in Figure 2 and its decomposition. The first line corresponds to the decomposition Ti = Ti,2+Ti,4+Ti,3. We have that Ti,3 is equivalent to

which corresponds to the decomposition Ti,3 = 32 × (T - i,3 + T + i,3 ) where T + i,3 is equivalent to 1.

4 Translations between Network Classifiers

In this section, we describe a close connection between BMP, BNN and the following classes of threshold circuits over X, i.e., Boolean circuits where internal nodes consist only of threshold gates:

• TH: the class of threshold circuits whose weights are integers.
• ̂ TH: the subclass of THusing onlyweights whose absolute value is at most polynomial in the number of variables.
• ̂ TH±: the subclass of ̂ TH using only weights 1 and -1.

It is folklore that ̂ TH and ̂ TH± are equally succinct. Indeed, on the one hand, ̂ TH± ⊂ ̂ TH so ̂ TH ≤p ̂ TH±. On the other hand, for every edge labelled by w > 0 connecting the output of a gate g to the input of a gate p in a circuit C ∈ ̂ TH, one can remove the edge and insert |w| dummy gates between g and p as in Figure 3; the resulting circuit is in ̂ TH± and its number of gates is at most maxw |w| times the number of gates in C. This translation can be done in linear time in the sum of weights in C, so ̂ TH± ≤p ̂ TH. More surprisingly perhaps, every threshold circuit of depth d can be simulated by a threshold circuit of depth 2d in ̂ TH with only a polynomial size increase. We owe this result to Goldmann, H˚astad and Razborov [Goldmann et al., 1992]. It follows that TH, ̂ TH and ̂ TH± are equally succinct.

4.1 BMP and Threshold Circuits

By definition, a Boolean multilayer perceptron is a threshold circuit whose particularity is to be layered, that is, its gates are partitioned into sets L1, . . . ,Ld such that, for every 1 ≤ k ≤ d-1, the inputs of every gate in Lk+1 are only connected to the output of gates in Lk. Recall that the layers are fully connected. It is readily verified that any threshold circuit C can be turned in polynomial time into an equivalent threshold circuit that is layered and fully connected: denoting by d the depth of C and by e its number of edges, we add at most d×e gates computing functions the form y = sgn(x) to make C layered, then we add edges with weight 0 to fully connect successive layers. Thus, the following holds:

Proposition 7. We have BMP ≃p TH.

Interestingly, polynomial-time translations exist also between BMP and ̂ TH± due to the following:

The main difficulty in the proof of Proposition 8 is the relationship ̂ TH ≤p TH. Indeed, the proof that ̂ TH ≤s TH by Goldmann et al. does not directly extend from ≤s to ≤p, partly because it involves probabilistic arguments. We have found a polynomial-time translation from TH to ̂ TH that, unfortunately, does not guarantee that the depths of circuits before and after translation stay within a constant factor (as in the proof of ̂ TH ≤s TH). Thus, our polynomial-time translation may be impractical. Improvements are left for future work, in this paper we only prove the existence of the polynomial-time translation.

4.2 BNN and Small-Weights Threshold Circuits

Consider an internal layer of a BNN whose input is a vector x = (x1, . . . , xn) over {-1, 1} and whose output is a vector of size y = (y1, . . . , ym) over {-1, 1}. Recall that the computation of yj reduces to a single threshold function sgn(∑ni=1 si,jxi - θj) for some si,j ∈ {-1, 1} and some integer θj. So a BNN is a particular threshold circuit that is layered, that is fully connected, and that uses only weights +1 and -1. Now, we show the following proposition:

Proposition 9. There is a polynomial-time procedure that, given a circuit in ̂ TH± of depth d, returns an equivalent BNN composed of at most d + 1 layers. Hence BNN ≃p ̂ TH±.

We need several intermediate results to prove Proposition 9. First, we can easily render a threshold circuit in ̂ TH± layered in polynomial time using the procedure previously described for circuits in TH. So, we have the following proposition:

Proposition 10. Every threshold circuit C ∈ ̂ TH± can be transformed in polynomial time into an equivalent layered threshold circuit C ′ ∈ ̂ TH±.

But then it remains to make the layers fully connected, a task which, since weights 0 are not allowed, requires a bit more work. Consider a layer Lk with k > 1 that is not the last layer (so Lk+1 exists). For every gate g ∈ Lk, we add a clone g′ of g to Lk. We call g an original gate and g′ its clone gate. We ensure that g′ ≡ g by connecting g′ to Lk-1 exactly as g. For every gate p ∈ Lk+1 and every original g ∈ Lk, if g is already connected to p with weight w, then we connect g′ to p with the same weight. If g is not connected to p, then we connect both g and its clone g′ to p with opposite weights. Since g ≡ g′ , gates that were not originally connected to p still contribute 0 to p, while those that were already connected to p now contribute twice their weight. So it only remains to double the value of the threshold of p to preserve the function it computes. This simple trick, illustrated in Figure 4, allows us to fully connect every layer Lk to Lk+1 for k > 1, in exchange for doubling the size of the layers. This leads to the following proposition:

Proposition 11. Every layered circuit C ∈ ̂ TH± whose first layer is fully connected to the second can be transformed in polynomial time into an equivalent layered circuit C ′ ∈ ̂ TH± whose layers are all fully connected.

We cannot proceed as before to fully connect L1 to L2 since cloning input variables is forbidden. So, before using Proposition 11, we insert a new layer between L1 and L2, that is fully connected to L1 and does not modify the function represented. The construction can be found in the full version of the paper.

Proposition 12. Every circuit C ∈ ̂ TM± containing k layers can be transformed in polynomial time into an equivalent circuit C ′ ∈̂ TM± that contains k + 1 layers and whose first layer is fully connected to the second.

Proposition 9 directly follows from Propositions 10, 11 and 12. A first consequence of Proposition 9 is that a polynomialtime translation exists between BNN and BMP.

Proposition 13. We have BNN ≃p BMP.

A second consequence is that a polynomial-time translation exists between BT and BNN or BMP. Indeed, it is easy to transform a decision tree into a Boolean circuit using ∨-gates and ∧-gates which, in turn, using that (a ∨ b) ≡ (a + b ≥ 1) and (a ∧ b) ≡ (a + b ≥ 2), is transformed in linear time into a threshold circuit. So, to construct a threshold circuit equivalent to a boosted tree classifier, it suffices to put a threshold gate using the weights of the trees on top of the threshold circuits representing the trees.

Proposition 14. We have BMP ≤p BT and BNN ≤p BT.

However, we also have that BMP and BNN are exponentially more succinct than BT. To prove this, we use the function parityn over n variables that evaluates to 1 if and only if the number of variables set to 1 is odd. On the one hand, there is a linear-time translation between BT and threshold functions over terms (i.e., conjunctions of literals): it suffices to rewrite every decision tree as a weighted sum of terms as shown in Figure 2. From this translation and the following result of Goldmann, one can prove that parityn is hard to represent in BT.

Proposition 15. [Goldmann, 1997, Theorem 5] Any circuit computing parityn that is a threshold gate over ∧-gates contains at least 14 ( 43 )n/2 ∧-gates for n sufficiently large.

Proposition 16. Every classifier in BT representing parityn has size 2Ω(n) .

On the other hand, parityn can be computed by a threshold circuit using only two layers of O(n) gates and unit weights (see for instance [Jukna, 2014, Exercise 11.10]). So we have:

Proposition 17. We have BT ≰s BMP and BT ≰s BNN.

5 Translations w.r.t. Compilation Languages

The existence of (polynomial-time or polynomial-space) translations between classes of representations is one of the key concerns of knowledge compilation [Darwiche and Marquis, 2002], a research line developed for more than 30 years in AI. The significance of compilation languages pushed the community to confront them to XAI queries (this is discussed in Section 6). Thus, in order to complete the picture, we briefly discuss the feasibility of translations connecting compilation languages to ML models. One of the most important compilation language is the class DNNF of circuits in decomposable negation normal form. We omit the definition of circuits in DNNF (see [Darwiche, 2001]), and only recall that DNNF is strictly more succinct than many other compilation languages [Darwiche and Marquis, 2002; Bova et al., 2016]. In particular, it is known that DNNF ≤p DNF, DNF ≰s DNNF, CNF ≰s DNNF and DNNF ≰s CNF [Darwiche and Marquis, 2002; Bova et al., 2014].

A first separation follows from Proposition 16 and the fact that parityn admits representations of size O(n) in DNNF .

Proposition 18. We have that BT ≰s DNNF.

The separation holds in the other direction as well using a trick to turn any formula in CNF (or DNF) into an equivalent random forest in polynomial time (see [Audemard et al., 2022, Proposition 2]). Thus, we have DNNF ≰s RF.

Finally, for completeness, we can show that RF is exponentially more succinct that the classes of formulas in CNF and DNF by considering the function majorityn (see Proposition 2 in [Audemard et al., 2022]). This function is trivial to represent with a random forest, but requires exponential size formulas in CNF or DNF (see [H˚astad et al., 1995]). As a consequence, we get that CNF ≰s RF and DNF ≰s RF. When the forest is a single tree however, it is known that CNF ≤p DT, DNF ≤p DT, DT ≰s CNF and DT ≰s DNF.

6 Other RelatedWork

In order to achieve useful accuracy/explainability trade-offs when designing ML models, many strategies have been envisioned so far. Explanation by design [Du et al., 2020] is about learning predictors that are considered as intrinsically interpretable, like decision trees or linear models. The key limitation of this approach is that the predictors that are considered are typically not very accurate. In model-agnostic approaches to XAI, the predictor under consideration is associated with a proxy from another ML model, which is considered more explainable in essence. Very popular approaches to XAI including LIME [Ribeiro et al., 2016], SHAP [Lundberg and Lee, 2017], Anchors [Ribeiro et al., 2018], and LORE [Guidotti et al., 2019] are relevant to this research line and approximate the decision surface of a model using an explainable one. The main drawback of such model-agnostic approaches (compared to model-specific ones) is that the explanations they furnish are not rigorous: one can find "counterexamples" for them, i.e., pairs of instances that share the same explanation but are nevertheless classified differently by the predictor [Ignatiev et al., 2019]. Besides, the amount of "counterexamples" can be high when the approaches listed above are used [Ignatiev, 2020].

Leveraging knowledge compilation techniques for XAI purposes has been considered so far in a couple of papers. [Audemard et al., 2020] list a number of XAI queries for multi-label classifiers. On such a basis, the XAI level of an ML model can be represented as the subset of the XAI queries for which polynomial-time algorithms exist (this tractability assumption is standard in AI to separate tasks that are likely to be feasible in practice to those that are not). When such an algorithm exists, the ML model is said to offer the XAI query. [Audemard et al., 2020] and [Huang et al., 2022] present sufficient conditions on the representation language used to encode the predictor that ensure that XAI queries are offered, and they identify a number of compilation languages for which such conditions are satisfied (thus, the predictor can be compiled into them). [Shi et al., 2020] consider the compilation of the decision function of binary neural networks into compiled representations from OBDD [Bryant, 1986] or SDD [Darwiche, 2011] (two subsets of DNNF). Among other things, the authors show how to compute the expected robustness of a neural network (a specific verification query), given an OBDD/SDD representation of it. [Darwiche and Hirth, 2020; Darwiche and Marquis, 2021; Darwiche and Ji, 2022] show how answering various XAI queries can be facilitated when the classifier under consideration has been turned into compiled forms, especially from Decision-DNNF [Huang and Darwiche, 2005] or from SDD (Decision-DNNF is another subset of DNNF). In [Audemard et al., 2021], the XAI level (or "computational intelligibility") of several families of ML models (including decision trees, random forests, decision lists, multi-layer Boolean perceptrons, binary neural networks) has been evaluated. Roughly, this paper has shown that none of the ML models considered in this evaluation, but decision trees, satisfies any XAI queries among those identified; on the opposite, every such query is offered by the decision tree model. [de Colnet and Marquis, 2022] investigates the complexity of enumerating sufficient reasons from representations in Decision-DNNF. However, the issue of determining the existence of sufficiently efficient translations between ML models, which is the core of the current paper, has not been considered in any of those works.

7 Conclusion &Perspectives

In this paper, we have studied the existence of polynomialtime translations and polynomial-space translations between ML models (and other representations) for binary classifiers. For the eleven languages considered, we have drawn the complete map for the relationships ≤p and ≤s.

Let us now explain how one can take advantage of the results above for XAI purposes. Most of the time, when C ≤p C ′ holds, whatever the XAI query, any dedicated algorithm that is efficient enough in practice for predictors in C ′ can be turned into an algorithm for the same query that is efficient enough in practice for predictors in C. Indeed, almost all the polynomial-time translations pointed out in the paper are in fact linear-time translations. 2 The existence of polynomial-time translations between languages for binary classifiers can also be exploited to derive intractability results for XAI queries: if C ≤p C ′ holds, then every XAI query that is NP-hard (in the broad sense) for C ′ also is NP-hard for C. For instance, since every of the nine XAI queries considered in [Audemard et al., 2021] have been shown NP-hard for RF, we can conclude that they are also NP-hard for BT, BRT, BNN, ̂ TH, BMP, TH (the classes BRT, ̂ TH, and TH were not taken into account in [Audemard et al., 2021]). In such a case, when the computational complexities of the XAI queries that are considered are "mild enough", the scalability of the corresponding XAI algorithms may be sufficient in practice. Finally, the "negative results" of the form C ≰s C ′ that we identified are also useful. Indeed, whenever C ≰s C ′ , using algorithms suited to XAI queries for C ′ in order to address the same XAI queries for C is an approach that offers no guarantee of success. Looking for XAI algorithms that are specific to C appears as a better option.

A perspective for future work would be to draw a version of the map for ML models that are not fully expressive. Indeed, limiting the expressiveness of the model is a way to prevent the learned predictor from overfitting the training data. In particular, for random forests, it is common to bound the depth of the decision trees used, and for boosted trees, to consider only decision stumps. We plan on studying RF and BT classifiers based on trees with bounded depth. A first direction is to compare RF classifiers to BT classifiers when both models use trees with depth bounded by a common bound. Another direction is to compare classifiers relevant to the same model but that use trees with different depths.

2 Translations that are more than linear-time (for instance that between BMP and BNN) must be considered more carefully to determine whether they are efficient enough in practice.

Acknowledgments

Many thanks to the anonymous reviewers for their comments and insights. This work has benefited from the supports of the PING/ACK project (ANR-18-CE40-0011), of the AI Chair EXPEKCTATION (ANR-19-CHIA-0005-01) of the French National Research Agency, and of the Austrian Science Fund (FWF) via grant ESP 235 ESPRIT-Programm. It was also partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.