Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithm
Authors: Clement Benard
Venue: NeurIPS 2025 poster ()
Keywords: explainability
gradient boosted trees
random forests
functional ANOVA decomposition
Hoeffding decomposition
Shapley values
Primary area: general_machine_learning
TL;DR: The introduced TreeHFD algorithm estimates the Hoeffding or ANOVA functional decomposition of tree ensembles from a data sample, and therefore provides an efficient explainability method through a set of low dimensional functions.

Abstract: Tree ensembles have demonstrated state-of-the-art predictive performance across a wide range of problems involving tabular data. Nevertheless, the black-box nature of tree ensembles is a strong limitation, especially for applications with critical decisions at stake. The Hoeffding or ANOVA functional decomposition is a powerful explainability method, as it breaks down black-box models into a unique sum of lower-dimensional functions, provided that input variables are independent. In standard learning settings, input variables are often dependent, and the Hoeffding decomposition is generalized through hierarchical orthogonality constraints. Such generalization leads to unique and sparse decompositions with well-defined main effects and interactions. However, the practical estimation of this decomposition from a data sample is still an open problem. Therefore, we introduce the TreeHFD algorithm to estimate the Hoeffding decomposition of a tree ensemble from a data sample. We show the convergence of TreeHFD, along with the main properties of orthogonality, sparsity, and causal variable selection. The high performance of TreeHFD is demonstrated through experiments on both simulated and real data, using our treehfd Python package (https://github.com/ThalesGroup/treehfd). Besides, we empirically show that the widely used TreeSHAP method, based on Shapley values, is strongly connected to the Hoeffding decomposition.

Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithm
Clément Bénard
Thales cortAlx-Labs. SINCLAIR AI Lab
avenue Augustin Fresmel, 91 120 Palaiseau, France clement- benard@thalesgrooug com com
Abstract
Tree ensembles have demonstrated state-of-the-art predictive performance across wide range of problems involving tabular data. Nevertheless, the black-box nature of tree ensembles is strong limitation, especially for applications with critical decisions stake. The Hoeffding or ANOVA functional decomposition a powerful explainability method, as it breaks down black-box models into unique sum of snwer-dimensional functions, provided that input variables are independent. In standard learning settings, imput variables are often dependent, and the Hoeffding decomposition generalized through hierarchical orthogonality constraints. Such generalization leads to unique and sparse decompositions with well-defined main effects and interactions. However, the practical estimation of this decomposition from data sample is still an open problem. Therefore, we introduce the TreeHFD algorithm to estimate the Hoeffding decomposition sample. We show the convergence of TreeHFD, along with the main properties orthogonality, sparsity, and causal variable selection. The high performance of TrecHFD is demonstrated through experiments on both simulated and real data, using our treehfd Python package (https:/github.com wtwpe//u..oooomaaaeeeettae ThalesGroup/rreehhi) Besides, empirically show that the widely used TreeSHAP method, based Shapley values, is strongly connected to the Hoeffding decomposition.
tree ensemble from a data
1
Introduction
Tree ensembles have demonstrated remarkable predictive performance to tackle supervised learning problems with tabular data, the past decades. In particular, gradient boosted trees (Friedman
2001 Chen and Guestrin (016) and random forests (Breiman (001) are probably the most successful algorithms to build tree ensembles. Recently, the extensive benchmark of Grinsztajn et al. (022) has shown that tree ensembles still outperform deep neural networks on tabular data, and are therefore state-of-the-at on wide range problems. However, tree ensembles suffer from major limitation with their lack of interpretability. Indeed, the prediction mechanism of a tree ensemble typically computes thousands of operations for single prediction, making impossible to grasp how inputs are combined to generate predictions. Such black-box problem is shared by most machine learning algorithms, and serious obstacle when critical decisions are at stake, which the case for industrial or healthcare applications, for example. The field of eXplainable AI, often called XAI, develops methods to explain predictions of learning algorithms, and has raised a strong interest the community over the past few years (Guidotti et al. 2018)) Speith 2022 Amoukou (023). The two main approaches to obtain explainable algorithms are transparent models and post-hoe explanations. In the first case, the model structure is constrained to have limited complexity, in order to keep a clear relation between the inputs and the output of the algorithm. However, transparent models usually have limited accuracy, because of the strong constraints on their structure. The second type methods provides explanations through post-treatments of the initial black-box model. A
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

popular example is variable importance, which quantifies the influence of each input variable on the algorithm output (Lundberg and Lee, 2017: Williamson et al. 202T). Although variable importance often provides highly relevant insights, it only gives partial information about the relation between the inputs and the output of the black box. On the other hand, functional decompositions have recently gained considerable momentum an alternative approach to obtain more precise explainable methods than transparent models or variable importance (Bordt and von Luxburg. 2023 Hiabu et al., [023] Idrissi et al. 2025). The principle is to break down a black-box model into sum of functions with subsets of input variables as arguments. All functional components of one or two variables can be represented, and are therefore intrinsically transparent, while the accuracy of the initial black box is preserved. However, numerous functional decompositions can be obtained for the same black-bor model, leading to different representations and interpretations. Therefore, the theoretical formulation of a functional decomposition must be clearly stated, to provide representations of the initial black box with clear properties, and enable precise conclusions about the underlying relation between the inputs and the output of the studied model. The Hoeffding decomposition (Hoeffding. 1948). extended by [Stone (1994) and and|Hooker (2007). and Shapley values (Lundberg and Lee| 2017 Bordt and von Luxburg 2023) provide theoretical frameworks to obtain such well-defined decompositions.
Hoeffding functional decomposition. The Hoeffding functional decomposition (HFD) breaks down a regression function into sum of functions with variable subsets as arguments, and involves one functional component for each possible variable subset. Originally introduced in the seminal article of [Hoffdding] (1948) for independent input variables, the decomposition is unique and all functions are orthogonal. In the case of dependent input variables, a major breakthrough was done by Stone (1994) and Hooker (2007) to generalize the Hoeffding decomposition through hierarchical orthogonality constraints, which imply that two functions are orthogonal if one of the two variable subset arguments is included in the other one. Hence, the decomposition is still unique for dependent inputs, and a functional component is null if is possible to break down the target function using only lower-order terms. This property provides a clear definition of interactions following the reluctance principle Yu et al. 2219). and often leads to sparse decompositions essentially involving main effects and second-order interactions, which intrinsically transparent. Later, Chastaing al. (2012) and Idrissi et al. (2025) extended the validity of the decomposition for unbounded supports of the imput distribution. U Unfortunately, the practical estimation of the Hoeffding decomposition is notoriously difficult problem (Hooker) 2007] Chastaing et al., (2012), and consequently, the HFD has long remained an abstract theoretical tool. Recently, [Lnnerrch et al. (2020) proposed an algorithm to estimate this decomposition when the target function is a tree ensemble, and the input distribution is known. However, only a data sample is often available in practice, and the estimation of the input distribution for moderate or large dimensions is a very difficult task.
Shapley values. Shapley values build on game theory to define variable importance algorithms with attractive properties. Initially introduced by Owen (2014) and Lundberg and Lee (2017) for machine learning applications, Shapley values are now widely used to interpret both tree ensembles and neural networks. In particular, TreeSHAP (Lundberg et al. 2020 Yu et al. 2022 Muschalik et al.) 2024b) a fast algorithm to compute Shapley values for tree ensembles, and is implemented in the highly popular xgboost package. Recently, |errenn and Hahn 2002)) Bordt and von Luxburg (2023). and Hiabu et al. (2023) made strong connections between functional decompositions of black-box models and Shapley values- see the Supplementary Material. However, all these approaches inherit the estimation obstacles of Shapley values (Kumar et al., 2020), and heuristics with approximations required to recover tractable algorithms, such THeeSHAP with interactions, in the case of tree ensembles. Although TreeSHAP has become a highly popular and successful XAI method, it is also
criticized for the lack of theoretical understanding of the estimated values (Amoukou) 2023 Chap. 3).
Contributions, The goal of this article is to introduce the TrecHFD algorithm to precisely estimate the Hoeffding decomposition of a tree ensemble, when only a data sample available and the input distribution is unknown. Importantly, the theoretical analysis of TreeHFD shows the algorithm convergence, and exhibits the main properties of the obtained decomposition, providing a clear understanding of the resulting representation. To our best knowledge, TreeHFD is the first algorithm to provide accurate estimates of the Hoeffding functional decomposition in standard machine learning settings, where input variables are dependent and the input distribution is unknown. Additionally, we show that the functional decomposition induced by TreeSHAP closely related to the HFD, through several experiments on both simulated and real data. This new result mitigates the main flaw of
2

---

TreeSHAP, since we connect the estimated values to well-defined theoretical quantities. However, TreeSHAP generates quite noisy functional components, and main effects can be entangled with interactions, which undermines the provided explanations. In the second section, the Hoeffding decomposition is formalized in the case of tree ensembles through discretization of the orthogonality constraints, which enforces that the decomposition components are also unique and piecewise constant. These two characteristics are the cornerstone to build efficient estimates of the decomposition, without the input distribution. Then, we state the main properties of the HFD for tree ensembles, mainly about the component orthogonality. the sparsity of the decomposition, the causal variable selection, and its accuracy to approximate the HFD of the underlying regression function. In the third section, we introduce the TreeHFD algorithm, defined as a least square problem with a linear complexity with respect to the sample size, and implemented in the treehfd Python package) Then, we show the convergence of TreeHFD. Finally, we conduct extensive experiments in the last section, to show the high performance of TreeHFD, and the close connections between TreeSHAP and the HFD.
2 Hoeffding functional decomposition of tree ensembles
We first formalize the original Hoeffding decomposition of square-integrable function in Theorem I While this decomposition has many valuable theoretical properties, its practical estimation from data sample is still an open question, as explained in the introduction. However, [engerich et al. (2000) take advantage of the piecewise constant form of tree ensembles to introduce an estimate of the HFD, provided that the distribution of the input variables is known. We overcome this limitation by introducing the Hoeffding decomposition of tree ensembles. We first formalize this decomposition and then derive its main theoretical properties.
in Theorem 2
2.1 Mathematical definition
We consider a standard supervised learning setting with a real random input vector of dimension N and a real random output Y. defined in the following assumptions. We also denote by Vi = (1..... p) the variable index, by ( the subvector of X with only the components in J Vp- and by P, the set of all subsets of Vz- Initially, (Stone (9994) and Hooker (2007) defined the HFD for distributions of input variables with a hyperrectangle as support. In fact, it coincides with the theoretical analyses of tree ensembles, which also often assume this type of support for input distributions (Scornet et al. 2015 Wager and Athey] 2018), and a mild assumption practice. We therefore focus such hyperrectangle supports, and take [0, 1]P without loss of generality.
The input vector X takes values on [O, 1]". and admits a density f that is bounded by strictly positive constants C₁, C2 > that is, for all [0, 1)", 6 S (xx S C2.
Assumption 1.
Assumption 2. The output Y is defined by Y = m(X) + s, where [0, 1|2 - R is a square- integrable function, and e is an independent noise.
The underlying regression function m estimated using a tree ensemble. More precisely, we denote by I" the prediction function of a tree ensemble built with M e NN trees, from given realization of a training dataset of fixed sample size, and from a realization of the tree randomizations. In the sequel, the function T' is thus considered as deterministic function of a new query point X, which avoids the repetitions that theoretical results are stated conditional on the training dataset. Furthermore, we define T(X) = E, Tx)), where T₃ is the prediction function of the ε-th tree, multiplied by an aggregation coefficient. Such coefficient is typically the learning rate for boosted tree ensembles, or 1/M for random forests. We also denote by Tur = f1, M) the tree index. Now, we state the original HFD introduced by [Stone (1994) and Hooker (007)) in the context of Assumption [
Theorem (Hoeffding Decomposition (Stone 1994 Hooker 2007)). If Asssupption is satisfied, and y is a qquare-integrad real function defined on [0. 1P, then there exists unique set functions ( such that for all J E Pp, I C. with + J, () (x ()("") -. and
v(X) = Σ (x())
JEP
In particular, if the input variables are further assumed to be mutually independent, the components of the decomposition take an explicit form as the Möbius transform of the conditional expectations, that is (()(((()) -ier(-1)))1 [[(X) ("), for all J Pp. However, this formula does
3

---

x()
4
4
(1,2)
A4
A
(1)
4
4
4 A X
Figure 1: Example of the partition of [0. 2 by a tree T7 (left side), and the associated Cartesian tree
partitions A," {A1 AA AA (1))
AA J. A {A (2) (2)
_22 AA²) and A A (right side).
not hold in the general case of dependent inputs, which makes the estimation of the Hoeffding decomposition especially difficult. In this general setting, Theorem [ provides the HFD of the regression function mX) and the tree ensemble T(X), respectively denoted by {m() Jeep, and [T(')) which also depend on the distribution f of the input variables X. However, both decompositions are unknown in practice, since and f are unknown, while only a data sample available, and estimating f is a very difficult problem. Our main goal is to provide an efficient explainability method of the tree ensemble T through the HFD of the function T for dependent input variables. Additionally. T often estimates m with a high accuracy, and therefore. the HFD of T also approximates the HFD of the function m, which is highly valuable explain the relation between X and Y. Hence, we build an adaptation of the HFD tailored for tree ensembles. By construction, each tree of ensemble is a piecewise constant function, and therefore discard the variability of the underlying regression function within each cell of the tree partition. Obviously, such approximation is necessary obtain good accuracy, since the trees are learned from finite sample, which cannot capture the data patterns with an arbitrary high accuracy. In the same spirit, we apply piecewise constant approximation the distribution f of the inputs X. However, we use a more fine-grained partition than the original tree partition to efficiently handle the orthogonality constraints: the Cartesian tree partition, introduced in Definition [ and illustrated in Figure 1
TM and variable X with j E Vp. the values of the node splits involving X are collected over all tree nodes to build a sequence of intervals AD), which forms partition of [0, 1]. Then, for any J Pp, A, = =ūeed A is the partition of [0, 1] J1, defined as the Cartesian product of the one-dimensional partitions. Clearly, the function a piecewise constant over A (P)) (to lighten notations, A A("") is written Ae in the sequel).
Definition 1 (Cartesian Tree Partition), For a tree
For a tree E TM. we define the tree HFD as the original HFD applied to the tree prediction function Tr, but with the density f averaged over each cell of the Cartesian tree partition, instead of f. Theorem 2 below shows four critical properties the tree HFD. First, the decomposition can still be written with the input vector X of distribution f. with discretized version of the orthogonality constraints. More importantly, such a decomposition is unique for a given pair of tree Tę and density f. the components of the decomposition are also piecewise constant over the Cartesian tree partitions, and the decomposition is independently defined for each tree. These three ingredients enable the design of consistent estimates of the tree HFD from a data sample, Notice that all proofs are gathered in the Supplementary Material (S-Mat).
will see in the next section.
Theorem 2 (HFD for Tree Ensembles), Let Assumption 7 be satisfied, T T E, be the prediction the associated Cartesian tree partitions of
function of a tree ensemble, and (A(") ) Definition [ Then, T has unique decomposition into a sum of functions {nt JJEP such that Di is piecewise constant over A, for all J E Pp, E TM. and
(J)
T(X) = (X()))))) with T (x(( = -E
(J) (x( and Te(X)= = Σ
(J)
(x(()))
Ti
me
JEP,
FETM
JEP,
and for for all & TM. J P IC J with I + J, A A AT, E(T (J) (X E
=
Besides, Theorem 2 also holds when Assumption iis not satisfied. Indeed, since the number of terminal leaves is finite, the tree ensemble is constant in each direction outside an hyperrectangle,

---

and the tree HFD is also constant in this area. Therefore, even if the input distribution f does not have a bounded support, Theorem I can be applied within this hyperrectangle, and the decomposition is simply extended outside with constant values. Furthermore, if the distribution f takes null values, its average over each cell of a tree partition is strictly positive, as all terminal leaves contain as least can also be applied in this context to state the tree HFD.
one data point, and Theorem T
2.2 Theoretical properties
Orthogonality. One of the main characteristics of the original HFD defined in Theorem I that functions are hierarchically orthogonal, that is Cov(ul") (om(((((((()))) (X (x()) = 0 for I C J and + J. In particular, this property clearly differentiates interaction terms from main effects in the decomposition. For example with p 2, [[x(X) =:::>>000 (x(() + (x(()) and v112)) vanishes by construction. Therefore, (11.2) does not contain main effects, and is a pure interaction, as explained in Lengerich et al. al. (2020), and this property is obviously also true for higher- order interactions. In Theorem BeooremBeelow we show that hierarchical orthogonality still holds for the tree HFD of given tree of the ensemble, whereas it is not necessary the case for the global tree HFD components of the ensemble, because of the discretization across various tree partitions. However, we prove that orthogonality is almost satisfied, provided that the density ʃ of X does not vary too much within each cell of the tree partitions. We will show in the experimental section that orthogonality is almost satisfied in practice. To formalize the result, we denote by || the usual infinite norm of function Y and AA.S the maximum variability of f within each cell of the Cartesian tree partitions A - JEPP,. More precisely, we write A = A. S If(x) f(x))-
Theorem 3. Let Assumption I be satisfied, T = E, be the prediction function of a tree ensemble, A = { } JEP,, JEP,, TNr the associated Cartesian tree partitions, and {m; }JEP, the tree HFD
(J)
defined in Theorem 2
We also consider J E Pp, and I C J with 1 + J. Then, we have
Covlu (J) (x(")), mi (1) (x()) =0 O,
vl E TM,
(it) ( (x()), (
c2 -c1 "1 100 Σ
1lm 11 Inl"llo)AAA
of
Sparsity. The HFD is sparse, since functional component is included in the decomposition only if terms of lower orders are not sufficient to break down the target model. Therefore, we say that the HFD complies with the reluctance principle (Yu et al. 2019 Lengerich et al., 2020), and this is consequence of hierarchical orthogonality. Theorem 4 below shows that the tree HFD preserves this important property, which often leads to sparse decompositions with essentially main effects and second-order interactions, which are intrinsically transparent.
Theorem 4. Under the same assumptions as Theorem [ if the functions Te can be written Tx) = ge(x!()) + he(x(!)) ') for pair of variable sets I, 1' E Pp, with real functions ge, he for all l TM, then for all J E Pp such that J & I and J & I', we have 1i (x 0a.s.
Causal variable selection. We show that the tree HFD achieves the same causal variable selection than the decomposition induced by interventional Shapley values. Such decomposition is introduced by Bordt and von Luxburg (2023). through the generalization of Shapley values to all groups of variables. More precisely, Theorem 4 in Bordt and von Luxburg (2023) shows that each Shapley value function also defines specific functional decomposition, called Shapley
which is in fact the Möbius transform of the value function (Osgood) 1957). The two most popular value functions = (J) for J E P. defining observational SHAP (Lundberg J. )) = (x X
are v((obe)( (J.x ()) = [
and Lee. 2017), and ((
((--) J) f. defining interventional SHAP (Datta et al.
2016 Janzing et al. 2020 2. While ((ob)) (J, ()) is the original proposal from Lundberg and Lee (2017).Janzing et al. (2020) show that interventional SHAP provides the causal effects of the input variables on the output Y. provided quite mild assumptions on the causal structure of the problem. However, Kumar et al. (2020) argue that both observational and interventional SHAP have strong drawbacks. For example, Theorem f does not hold for observational SHAP, since the dependence within input variables may result in non-null components for a variable XQ) even if ' is constant with respect to ( On the other hand, interventional SHAP may be a poor approximation of the true data patterns, even if T is highly accurate for new dataset distributed as the training data. Indeed, because of the dependence between variables, some regions of the input space may have almost no data, and consequently, T(X) may extrapolates with low accuracy in these areas, on
5

---

which (J, highly relies through the marginal expectation (Hooker et al. 2021). In practice, a functional decomposition rarely involves all possible variable subsets, but rather a fraction of them. We define by I the set of exogenous variables, which only have null components in a decomposition (j E V VJ E Pp. ((O()))) = 0}. In the following Theorem 5 we show
{uld)) JEP,, that that the set of exogenous variables is the same for tree HFD and interventional SHAP, which therefore achieves the same causal variable selection.
Theorem 5. Undler the same assumptions as Theorem 3 n is the set of exogenous variables for the tree HFD Te with E Tas, and F for the decomposition of Te induced by interventional SHAP. then we have AA = T.
HFD of the regression functtio. Our main goal is to provide a functional decomposition of the tree ensemble with clear properties, as provided in the previous paragraphs. Furthermore, according to Assumption 2 the output Y is defined by Y m mx + E, where m is the underlying regression function. Therefore. T is an estimate of m. and the tree HFD of T also provides an approximation of the original HFD of the function m. In fact, Theorem o below shows that such approximation is of high accuracy if the Mean Square Error (MSE) of 7 with respect to m is small, and the distribution does not vary too much over each cell of the Cartesian tree partitions, that is AA, f is small, Tree ensembles often have a high accuracy in practice, as shown in the benchmark of Grinsstajn et al.) (2022) for example, and the HFD of T' is thus often a good approximation of the HFD of m.
Theorem 6. Let Assumptions and 2 be satisfied, and {ml JEP, be the HFD of m(X). Then, there exists two constants K1, K2 O, such that for any tree ensemble T = =ee Te of Cartesian tree partitions A and tree HFD {ny H JEPP, we have for J E P.p. ((( m () I ([((m(X)-T(x))))
M
K2
Σ
v [[T]
In Corollary we derive asymptotic conditions on the training of the tree ensemble ''' to obtain a vanishing error of the tree HFD with respect to the HFD of m, inspired from (Meinshausen and Ridgeway 2006). We recall that T is a deterministic function, trained with realization of the training dataset of fixed sample size, throughout the article. Here only, we denote by nr the size of this training dataset, and analyze the tree HFD accuracy when f&y grows for a random training dataset. Corollary 1. Under the same assumptions as Theorem O if the input distribution f is further assumed to be a Lipschitz function, the tree ensemble T is Trz-consistent, all trees are bounded, the tree depth grows to infinity with the sample size nr,, the split of all tree nodes leaves at least a fraction >> O of the observations in each child node, and the optimization of each node split is slightly randomized to have positive probability split with each variable, then we have for J E Pr El(n) (x(x)) - mm (x())))
O.
3 TreeHFD algorithm
We first show that the tree HFD of Theorem can be parametrized with set of real coefficients, and is in fact the minimum of a convex loss function for each tree. Then, the TreeHFD algorithm is defined from an empirical version of this least square problem using a data sample. Finally, we prove the convergence of TreeHID.
least square problem. The tree HFD functions are piecewise constant on the Cartesian tree partitions. For each tree, such partition is easily constructed by collecting the split values of the tree nodes, and deriving the corresponding intervals. Then, for e E TM, J E Ppp we estimate Ne by
(5)
piecewise constant function p! of the form (xx K, y(d)) 1 L(neA for x()) E [0. 1]11,
where ( ,.... ..... () E IR and (A(")) }r are the K,, cells of the Cartesian partition A Next, we define a loss function to quantify the violation of the orthogonality constraints and the error of the
decomposition with respect to each tree of the ensemble. We use Lemma 4.1 from Hooker (2077) to simplify the conditions of orthogonality, transformed into the following constraints: for all j E J and A E A. (J)) EmT (X ())) E A O. Then, we define the theoretical loss function - by (J)
( (D))) E (Tx(
Σ 1 (1 (
+ ΣE
Elu (J) (x())) (X))))A))? 12
JEP,
JEP, AEA(W
and the tree HFD is the unique mínimum of T.*. where L = O. Given the form of the functions 1r minimizing such loss function with respect to { " clearly boils down to least square problem.

---

Algorithm description. The loss function L defined above has a number of terms growing exponentially with the dimension p. and seems intractable practice. In fact, only few variables are involved in the splits of shallow tree of a boosted ensemble. Consequently, only the associated subsets of variables are considered in the loss T. for each tree, and the other components of the tree HFD are null by definition. Additionally, we only consider HFD components involving variable interactions of limited order, and denote by di this hyperparameter. While interactions of order two often occur in practice, it is rarely the case for interactions of higher orders. Therefore, di is typically set to two by default, but it is obviously possible to set greater values in TreeHFD. Then, we define Py (2) C Pp. the set of all possible variable sets collected along the paths of the b-th tree, and of maximum size dj. Overall, only a small fraction of the variable subsets are involved in the loss function of each tree, which can therefore be optimized at small computational cost. Next, we assume that we have access to a data sample 2n = {(x,, Y)) independent of the training dataset of T. We define T.,, the empirical counterpart of T estimated with Zn for each tree see proof of Lemma 6 by
K2
Lu
Tx(x))
E
JEP 1=
ΣΣΣ JEP! JEJ k=1 IH
Kny
-
K2
2 E nx
==1
Notice that for P!! with |J|= 1, we get J -1= D. In these cases, we set by convention that the involved indicator functions always take value one, and the corresponding terms in L,, simply enforce that all HFD components have zero mean. Hence, the set of functions {u defined as the minimum of I. through the optimization of the parameters {B8 Jk.J. Although the loss L,, has a quite complex form, its computation only requires to collect the list of cells in which each data point falls. Then, simple counts give all the necessary coefficients to express T., as a quadratic function of the parameters {33) (3a JK... In practice we can use the available efficient software to solve quadratic programs. Indeed, the parameters ( JK,J are stacked together to form a single vector B3. Then, the loss L,, is translated into a constraint matrix Cn. where each square term gives a row of C,, and each element of the row is the coefficient of the corresponding 8k in the square term of L,, The target vector Zn is defined by (X, for the constraints of the first part of Ln, and by the null value for the orthogonality constraints. Also notice that many constraint rows part of L,, since many data points fall in the same collection of cells, where T, is constant. These rows can thus be deduplicated and multiplied with appropriate weights to compact C, Finally, the functions (J (3) ), are defined from the parameters Si, which solve 3 = argming I| 3l where || ll2 is the Euclidean distance. Then, the least, square problem is solved for each tree of the ensemble, and the estimated tree HFD component uon of I' is given by uin
identical for the first
(J) > Mo.e
())
Computational complexity. The computational complexity of solving the above least square problem depends on the number of cells and variable subsets, and thus on the tree depth, but not on the sample size n or directly on the dimension p. Additionally, the construction of the matrix C, has a linear complexity with respect to the sample size n. and C, is highly sparse by design, which greatly reduces the cost of the least square problem. Overall, the computational complexity of TrecHFD is linear with respect to n, does not depend on p for shallow trees, and grows exponentially with the tree depth for large p. Therefore, TrecHFD is highly efficient for ensembles of shallow trees, such as boosted tree ensembles.
Additional algorithm details. We specify four additional details and extensions for TreeHFD algorithm. First, we can increase the efficiency of TreeHFD for deep trees that are typically involved in random forests, by introducing two hyperparameters dr and dy to control tree depth and the number of variable subsets. Since deep splits in random forest trees are often not significant (Duroux) and Scornet, 2018). we use a preprocessing step before computing the Cartesian tree partitions, where node splits are pruned whenever they exceed a given tree depth threshold, provided by the hyperparameter dr. Then, the original tree predictions are averaged in each cell of the new partition to define the new prediction function of the tree. Additionally, when the tree depth is large. the number of variable subsets pb may become very high. Consequently, only the variable subsets at the first dy levels of the tree are extracted to build P to control its size, and thus the computational complexity of TreeHFF for deep trees, while focusing on the most influential variables. Secondly, by construction of the Cartesian tree partitions, some cells may contain no training data, since the
7

---

x
x
Figure 2: Main effects of the decompositions for (()) and (²), Solid lines provide the theoretical functions, with the HFD green, int. SHAP red, and obs. SHAP in orange. Green and red points are respectively the values provided by TreeHFD and TreeSHAP with interactions for xgboost.
Cartesian partitions are finer than the original tree ones. Hence, L,, does not depend on the (( parameters of such empty cells. Once the reduced S is computed, the parameter of each empty cell is set to the same value as the largest neighboring nonempty cell. For this specific reason, is critical to break down the decomposition by tree, whereas merging all tree partitions with a unique cost function is highly inefficient. Thirdly, TreeHFD can also easily handle categorical and discrete variables, as fully explained in the S-Mat. Finally, TreeHFD algorithm also applies to classification problems for boosted tree ensembles, where the logit of each class is continuous output that can be handled as the regression case. TrecHFD also applies to binary classification for all tree ensembles.
show the convergence of the TreeHFD algorithm towards the theoret- ical tree HFD formalized in Theorem 2 when the sample size grows. Therefore, TreeHFD provides clear decomposition of the initial tree ensemble, which satisfies all the properties of orthogonality, sparsity, causal variable selection, and accuracy, stated in the theorems of the previous section. In the sequel. we show that these properties are satisfied in practice, through several batches of experiments. We highlight that Theorem 7 stated for deterministic tree ensemble T, trained with fixed set of points, and for a growing size of 2n, used to fit TreeHFD from T.
Algorithm convergence.
Theorem 3, If Assumption is satisfied, the hyperparaaeeeers dj, dr, and dy dyee set to the tree depth, {p (.n.JJEP, is the minimum of Ln
compact set for E TM,, and {TE "JEP, is the tree (J)
HFD of (XX) defined in Theorem then for all Ppp we have p pa.
(J) P ni
Experiments
We first analyze analytical case to better understand the behavior of TrecHFD, and then evaluate TreeHFD performance with real datasets, using treehfd package The main competitor of TrecHFD the decomposition induced by Shapley values, which implemented in xgboost as extension of TreeSHAP (Lundberg et al.) 2020): Bordt and von Luxburg. 2023). Although the proposal of Lengerich al. (2020) major step to estimate the HFD of tree ensembles, it requires to know the input distribution, and is therefore not adapted to our setting where only data sample is available.
Analytical case. We consider a Gaussian random vector X of dimension p 6. where each component has unit variance and all pairs of variables have the same correlation = 1/2. Then, (4), and ~ (0, 0.5²). We study this analytical case because sinusoidal and linear functions are quite difficult approximate with piecewise constant estimates, and it is possible to compute the analytical decompositions and introduce strong correlations within input variables, in the case of a Gaussian input vector. the S-Mat, we state the analytical functional decompositions of mXX) provided by the HFD, interventional SHAP, and observational SHAP. Notice that for the HFD, the correlation between (1) and (2) (respectively (3) and (4) introduces main effects for these variables, to purify interactions. As expected from Theorem 5 the same functional components are null for the HFD and interventional SHAP, whereas observational SHAP have non-null components for all variable subsets, because of the input dependence. It is clear that all components of observational SHAP mix all terms
the output Y is defined by Y m (X) + where m(X) sin(2 + X (1) (1)

---

Table MSE for TreeHFD and TreeSHAP with respect the specified target decompositions.
Algorithm
Target
17()
17(3
r7(4)
.7(6)
17
171..2
1)3.4)
Others
TreeHFD xgboost
HFD
0.02
0.01
0.02
0.02
0.002
0.002
0.04
0.04
I 0.01
TreeHFD RF
HFD
0.15
0.02
0.01
0.03
0.004
0.003
0.10
0.29
S 0.01
Tre xgboost
HFD
0.06
0.23
0.13
0.12
0.002
0.002
0.35
0.27
S 0.02
TreeSHAP xgboost
int. SHAP
0.49
0.16
0.24
0.25
0.002
0.002
0.77
0.82
S 0.01
TreeSHAP xgboost obs. SHAP 0.35
0.73
0.51
0.51
0.50
0.50
0.68
0.60
NA
Table Dataset characteristics and performance of TreeHFD and TreeSHAP.
Dataset
p
Accuracy Residual MSE
Orthogonality
Local Variability
xgboost
TreeHFD
TreeHFD TreeSHAP
TreeHFD TreeSHAP
Abalone
4176
9
50%
1%
0.05
0.85
0.009
0.09
Airfoil
1503
5
95%
2%
0.02
0.24
2.10-5
0.04
Bike Sharing
17389
8
87%
3%
0.004
0.13
3.10
0.1
Housing
20640
8
83%
1%
0.05
0.55
7.10
0.05
Concrete
1030
8
94%
0.4%
0.003
0.33
0.01
0.05
Nutrition
2278
7
20%
3%
0.03
0.43
0.01
0.06
Parkinson
5875
19
96%
1%
0.07
0.18
0.02
0.1
Power Plant
9568
4
97%
0.1%
NA
0.9
0.006
0.02
Superconduc.
21263
81
92%
1%
NA
NA
0.007
0.2
of the original function m, and it is therefore difficult understand the influence of each input from such a decomposition. Next, we fit boosted tree ensemble on a training dataset 2, of size n 5000, using xgboost with M 100 trees, and the default value for the other parameters. Then, we fit TreeHFD on the tree ensemble using 2,, and display the result in Figure 2 Finally. we estimate the Mean Square Error (MSE) each TrecHFD component, using the analytical formulas and an independent testing dataset. Besides, we perform the same experiment with TreeSHAP, and also using random forests (RF) instead of xgboost. Results are averaged over ten repetitions, and reported in T where standard deviations are negligible and thus omitted. Hence, it is clear from Table that Tre based on xgboost provides highly accurate estimates the HFD, and outperforms the decomposition provided by TreeSHAP. This result is quite expected since TreeSHAP is not explicitly designed to target the HFD. However, Table also highlights surprising phenomenon: TreeSHAP more accurately estimates the HED than the theoretical decompositions induced by interventional SHAP and observational SHAP. This implies that TreeSHAP has strong connections with the HFD, and the real data cases will further confirm this trend. Importantly, the obtained TreeHFD components are almost hierarchically orthogonal, with correlation coefficients between interactions and the associated main effects of about 0.05 smaller. We provide all experimental settings in the S-Mat, including additional experiments with various sample sizes, tree depths, and comparisons with glex (Hiabu al., 2023) and EBM (Nori al.) 2019). In particular, show that TreeHFD is not very sensitive to tree depth, and thus remains highly efficient for shallow trees.
Real data cases. We assess the performance of TreeHFD using nine real public datasets from the UCI repository (Kelly et al.) 2024), with the main characteristies summarized in Tablee2|see the S-Mat for all details about the displayed metrics. We first show that TreeHFD with interactions of second order (i.e. d, 2) successfully estimates the HFD of the fitted xgboost models, since the TrecHFD residual MSE is about 1% of the output variance for all tested datasets, reported in Table 2 and hierarchical orthogonality is well approximated by TrecHFD, Indeed, we compute the correlation coefficients between the interaction components and their associated main effects, and report the maximum absolute value for each dataset in Table for both TreeHFD and TreeSHAP. Hence, the results show that the maximum absolute correlation for each dataset is about 0.05 for TrecHFD or smaller, whereas it is frequently above 0.5 for TreeSHAP. Therefore, TreeHFD components are almost hierarchical orthogonal, whereas main effects and interactions can be strongly entangled for Tre.SHAP. By construction, TreeHFD inherits the eventual overfitting of the initial tree ensemble, as for the "Nutrition" dataset. Furthermore, we show that TreeSHAP generates quite noisy decompositions, which can be problematic for local interpretations. Indeed, slight perturbation of

---

]ew05
Tendi-
De-02
36-05
J0-03-
Longitude
Labiude
Figure 3: For the "Housing" dataset, main effects "Longiuude" and "Latitude" in the decompositions of respectively TreeHFD in blue and TreeSHAP with interactions in red.
the input may result in a large change in the output decomposition values. This phenomenon clearly undermines the local explanations provided by TreeSHAP. We quantify local variability the mean variance of functional component over the nearest neighbors of each point, and averaged over all main components see the S-Mat for a formal definition. The obtained metric is reported in Table and shows that TreeHFD is locally much more stable than TreeSHAP for all tested cases.
Housing dataset. We focus on the California Housing dataset (Kelly housing prices with various characteristics. We fit xgboost and TreeHFD, and display the main resulting components in Figure 3
2024), which gathers
We see that the "Longitude" component of TreeHFD clearly identifies the peak in housing prices, corresponding to the San Francisco Bay Area (-122225'), whereas TreeSHAP does not really detect it. Indeed, TreeSHAP decomposition is quite noisy, and the main effect of the "Longitude" variable is entangled with the interaction between "Longitude" and "I "Latitude" variables. For TreeSHAP, this interaction function has a variance of 16% of the total variance [X) of the tree ensemble output, whereas it is only 4% in the case of TreeHFD, because interactions are purified. From another perspective, the absolute correlation coefficients between the two main effects and the interaction are about 0.05 for TreeHFD, close to the targeted null value of hierarchical orthogonality, whereas it is about 0.20 for TreeSHAP. Additionally, TreeSHAP hides in this interaction that house prices are lower in northern and eastern California, as shown by TreeHFD.
Additional datasets. The same analysis for the "Bike Sharing" and "Superconductivity" datasets (Kelly et al., 2024) is provided in the S-Mat. In the first case, the dataset gathers the number of bikes rented by hour from a US bike renting system, along with time and weather information. TreeHFD and TreeSHAP generate close decompositions of the bike rentals, but SHAP values are quite noisy, and can therefore be misleading when predictions are analyzed one by one. The identified patterns can be easily interpreted. For example, there are renting peaks at the beginning and the end of the day, when people commute to work, and a strong interaction between the variables "Hour" and "Week day", since the peak of bike rentals is in the middle of the day during the weekend. There is also a drop of bike rentals when it is too hot or too cold, as expected. Finally, the "Superconduuctiitt" dataset shows the high performance of TrecHFD for a quite large input dimension of 81.
5 Conclusion
We have introduced the TreeHFD algorithm to estimate the Hoeffding decomposition tree ensemble from data sample, which therefore provides efficient explainability method. To our best knowledge, TrecHFD is the first algorithm to accurately estimate the HFD in standard machine learning settings, where only data sample is available. Furthermore, strong connections between TreeSHAP and the HFD. In future work, conducting a thcoretical analysis of this connection will deepen the understanding of the widely used TreeSHAP method.
have empirically established
The main limitation of TreeHFD is the high computational complexity for large tree depths, which can be efficiently mitigated using pruning, controlled by two hyperparameters. Additionally, TreeHFD requires the access to the internal tree structures, as provided by most open source software, but not always by proprictary tools.
Limitations.
10

---

Acknowledgments and Disclosure of Funding
We thank the reviewers for their insightful comments and suggestions. Clément Bénard has received support from the GATSBII project (ref. ANR-24-CE23-66-53 funded by the ANR (french National Research Agency), and the FaRADAI project (ref. 101 103386), funded by the European Commission under the European Defence Fund
References
Amoukou, (2023). Trustworthy machine learning: explainability and distribution-frer uncer- luinty quantification. PhD thesis, Université Paris-Saclay.
Bénard, C., Da Veiga, S., and Scornet, E. (2022). Mean decrease accuracy for random forests: inconsistency, and practical solution via the Sobol-MDA, Biometrika, 109:881-900.
Bordt, S. and von Luxburg, U. (2023). From Shapley values to generalized additive models and back. In International Conference on Artificial Intelligence and Statistics, pages 709-745. PMLR.
Breiman, I.. (2001). Random forests. Machine Learning, 45:5-32.
Chastaing, G., Gamboa, F., and Prieur, C. (2012). Generalized Hoeffding-Sobol decomposition for dependent variables application to sensitivity analysis. Electronic Journal of Statistics, 6:2420- 2448.
Chen, T. and Guestrin, C. (2016). XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785-794, New York. ACM.
Datta, A., Sen, S., and Zick, Y. (2016). Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems. In 2016 IEEE symposium on security and privacy (SP), pages 598-617. IEEE.
Duroux, R. and Scomet, E. (2018). Impact of subsampling and tree depth random forests. ESAIM: Probability and Statistics, 22:96-128.
Friedman, J. (2001). Greedy function approximation: A gradient boosting machine. Annals of Statistics, pages 1189-1232.
Grinsztajn, L., Oyallon, E., and Varoquaux, G. (2022). Why do tree-based models still outperform deep learning typical tabular data? Advances in Neural Information Processing Systems, 35:507-524 520.
Guidotti, R., Monreale, A., Ruggieri, S., Turini, F., Giannotti, F., and Pedreschi, D. (2018). A survey of methods for explaining black box models. ACM Computing Surveys, 51:1-42.
Herren, A. and Hahn, P. R. (2022). Statistical aspects of shap: Functional anova for model interpreta- tion. arXiv preprint arXiv:2208.099:
Hiabu, M., Meyer, J. T., and Wright, M. N. (2023). Unifying local and global model explanations by functional decomposition of low dimensional structures. In International Conference on Artificial Intelligence and Statistics, pages 7040-7060. PMLR.
Hoeffding, W. (1948). A Class of Statistics with Asymptotically Normal Distribution. The Annals of Mathematical Statisties, 19:293 325.
Hooker, G. (2007). Generalized functional anova diagnostics for high-dimensional functions of dependent variables. Journal of Computational and Graphical Statistics, 16:709-732.
Hooker, G., Mentch, L.,, and Zhou, S. (2021). Unrestricted permutation forces extrapolation: variable importance requires at least one more model, or there is no free variable importance. Statistics and Computing, 31:1-16.

---

Idrissi, M. I., Bousquet, N., Gamboa, F., looss, B., and Loubes, J.-M. (2025). Hoeffding decom- position of functions of random dependent variables. Journal of Multivariate Analysis, page 105444.
Janzing, D., Minorics, L., and Blöbaum, P. (2020). Feature relevance quantification in explainable ai: A causal problem. In International Conference on Artificial Intelligence and Statistics, pages 2907-2916. PMLR.
Kelly, M., Longjohn, R., and Nottingham, K. (2024). The UCI machine learning repository.
Kumar, I. E., Venkatasuuramaanian S., Scheidegger, C., and Friedler, S. (2020). Problems with Shapley-value-basee explanations as feature importance measures. International Conference on Machine Learning, pages 5491-5500. PMLR.
Lengerich, B., Tan. S., Chang, C.-H., Hooker, G., and Caruana, R. (2020). Purifying interaction effects with the functional anova: An efficient algorithm for recovering identifiable additive models. In International Conference on Artificial Intelligence and Statistics, pages 22122 PMLR.
Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee, S.-L. (2020). From local explanations to global understanding with explainable ai for trees. Nature Machine Intelligence, 2:56-67.
Lundberg, S. M. and Lee, S.-1. (2017). A unified approach to interpreting model predictions. Advances in Neural Information Processing Systems, 30.
Meinshausen, N. and Ridgeway, G. (2006). Quantile regression forests. Journal of machine learning research, 7(6).
Muschalik. M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Hammer, B., and Hüllermeier, E. (2024a). shapiq: Shapley Interactions for Machine Learning. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track.
Muschalik, M., Fumagalli, F., Hammer, B., and Hüllermeier, E. (2024b). Beyond TreeSHAP: Efficient computation of any-order Shapley interactions for tree ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 14388-14396.
Nori, H., Jenkins, S., Koch, P., and Caruana, R. (2019). Interpretml: unified framework for machine learning interpretability, arXiv preprint arXiv: arXiv:/909.000 19tp::99900955.
Osgood, C. E. (1957). The measurement of meaning. Urbana: University of Illinois Press.
Owen, A. B. (2014). Sobol'indee indices and Shapley value. SIAM/ASA Journal on Uncertainty Quantifi- cation, 2:245-251.
Scornet, E., Biau, G., and Vert, J.-P. (2015). Consistency of random forests. The Annals of Statistics, 1117716-7441..
Speith, T. (2022). A review of taxonomies of explainable artificial intelligence (XAI) methods. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 2239-2250.
Stone, C. J. (1994). The use of polynomial splines and their tensor products multivariate function estimation. The Annals of Statistics, 22:118-171,
Van der Vaart, A. (2000). Asymptotic Statistics, volume 3. Cambridge University Press.
Wager, S. and Athey, S. (2018). Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113:1228-122 1242.
Williamson, B., Gilbert, P., Simon, N., and Carone, M. (2021). general framework for inference on algorithm-agnostic variable importance. Journal of the American Statistical Association, pages 1-38.
Wright, M. N. and Ziegler, A. (2017). ranger: A fast implementation of random forests for high dimensional data in C++ and R. Journal of Statistical Software, 77:1-17.
12

---

Yang, Z., Zhang, A., and Sudjianto, A. (2021). GAMI-Net: An explainable neural network based on generalized additive models with structured interactions. Pattern Recognition, 120:108192.
Yu, G., Bien, J. and Tibshirani, R. (2019). Reluctant interaction modeling. arXiv:1907.08414.
arXiv preprint
Yu, P., Bifet, A., Read, J., and Xu, C. (2022). Linear TreeShap. In Advances in Neural Information Processing Systems, volume 35, pages 18-25828. Curran Associates, Inc.
13

---

Supplementary Material (S-Mat)
A Categorical and discrete variables
Discrete and categorical variables are straightforward handle in TreeHFD algorithm, even if we focus on continuous inputs for the sake of clarity. Indeed, discrete variables are considered as numeric ones by the initial tree ensemble. For example, if variable X()) takes values in {0.2, 0.4, 0.8). a tree can typically build the partition { 0.3), [0.3. 0.6). [0.6, 1]}, with splits at the middle of two values of x Then, the associated distribution is constant in each cell, and the values are given by the weights of the initial discrete distribution. For categorical variables, we follow the approach of two of the main tree ensemble implementations, xgboost (Chen and Guestrin (016) for boosted trees and ranger (Wright and Ziegler (0177) for random forests, using onc-hot-encoding to get binary discrete variables, naturally handled by TreeHFD as explained before.
B Additional experiments and settings
Experiments were conducted with a standard computer machine with Ubuntu OS and the following main characteristics; Intel Core i5 CPU (2.30 GHz) with 6 cores and 16 GB of RAM. Notice that we use xgboost software in the experiments, accordance with its Apache License 2.0.
B.1 Competitors
Shapley values. As mentioned in the introduction, Herren and Hahn (2022). Bordt and von Luxburg (2023), and Hiabu al. (2023) made strong connections between functional decompositions of black- box models and Shapley values. In particular, [Bordt and von Luxburg (2023) introduce n--Shalley values a generalization to all subgroups of variables, which then induces functional decomposition. On the other hand, Herren and Hahn (2022) and Hiabu et al. (2023) respectively show how to connect observational SHAP and interventional SHAP functional decompositions with practical estimates. Additionally, Linear THAP (Yu et al. (022) and TreeSHAP-IQ (Muschalik et al., [222bb a) improve the computational complexity of the original TreeSHAP implementation (Lundberg et al. 2020), and target the same quantities. TreeSHAP-IQ can also provide high-order interactions.
Overall, these algorithms target observational SHAP interventional SHAP, but not the Hoeffding functional decomposition, and are therefore not direct competitors of TreeHFD, with the notable exception of TreeSHAP, discussed in the article. Although SHAP values have demonstrated great success to explain machine learning algorithms, Kumar et al.) (202)) show that both observational SHAP and interventional SHAP have quite strong limitations, while the HFD is an interesting al- ternative to overcome these problems. In particular, TreeHFD shares the causal variable selection of interventional SHAP, but based on the original distribution of the inputs, whereas interven- tional SHAP may extrapolate in areas where the tree ensemble has low accuracy. Furthermore, observational SHAP introduces functional components for exogenous variables because of the input dependence, and can thus generate decompositions with very high number of components, which are hardly interpretable.
In the next section, we run the analytical case with the algorithm from Hiabu et al. (2023), imple- mented in the R-package glex available online, which provides efficient estimates of the functional decompositions induced by interventional SHAP, as we will see. We do not run experiments with the promising Tre-SHAP-IQ algorithm because it computes the same quantities as TreeSHAP im- plemented in xgboost for main effects and second-ordes interactions, and the computational time of TreeSHAP-IQ is high. Indeed, although its computational complexity is highly improved over the original TreeSHAP, TreeSHAP- is designed to explain specific prediction, and consequently. predictions are not vectorized in shapiq implementation (Muschalik et al., (024a), which does not use compiled language. Therefore, shapiq is efficient to compute single prediction, which takes only a few seconds for the analytical case (with the machine described at the beginning of the section), but running all predictions one by one with n 5000 takes several hours for one of the ten repetitions, while it takes less than one minute with our treehfd implementation or TreeSHAP with xgboost.
14

---

Table 3: Analytical functional decompositions (C' - exp( 21 - p)))) For |J| 1, functions have x arguments, and (x, 2) for J = 2.
Interventional SHAP
J
HFD
Observational SHAP
0
2 p
2p
2p sin(2 + p(1 + p) - 1) Csin(2Tpa) + p(1 + p)
{1}
sin (
+ 1 11)
p
sin sin(2 - p
(2), (3,13),4)
(x -1)
Itp
-P
(6)
0
0
Csin(27pp + 2p (x² -1)
{1,2), (3,4)
PT+0
P 1-
1+p (x²
22 + xxx2
p
2(1.2), ((3,4) +
Others
( #
Generalized additive models. The scope of the article to estimate the HFD of black-box tree ensembles from data sample, to provide an efficient post-hoc XAI method. Therefore, generalized additive models (GAMs) are out of the article scope, since they build transparent models the first place. However, they also provide models in the same form of sums of low-order functions of the input variables. Hence, we mention two powerful and widely used GAMs: Explainable Boosting Machines (EBM) (Nori et al., (2019), and GAMI-NET (Yang et al. (021). Both methods exhibit high predictive performance, quite often on par with boosted tree ensembles, but their targeted theoretical decomposition is unknown, which makes their interpretation more difficult.
EBM also takes advantage of boosted trees to provide GAMs with interactions of order two. In the next section, we run experiments to show that EBM can also estimate the HFD with a high accuracy. In a similar way as TreeSHAP, EBM seems to have strong connections with the HFD. However, we will see in the analytical case that EBM can introduce functional components for exogenous variables, because of the input dependence. Therefore, EBM does not share the sparsity and causal variable selection properties of Tre and TreeSHAP. EBM can also generate different decompositions than TreeHFD, and also face instability issues when the input dimension is quite large, as shown in the experiments with the "Suuercondductivity"" dataset in Subsection B.3
GAMI-NET uses neural networks to also provide GAMs with second-order interactions. However, interactions are included only if variables have main effects. Although experiments show that GAMI- NET is highly accurate (Yang et al., (02T). often does not target the HFD. For example, in the analytical case, if the Gaussian input vector is slightly modified to make X (3) and X (4) independent, then these two variables do not have main effects, and their interaction term will be set as null in GAMI-NET, instead of X (3) X in the updated HFD.
B.2
Analytical case
Analytical decompositions. In Table we provide the analytical functional decompositions of mX) provided by the HFD, interventional SHAP, and observational SHAP (Bordt and von Luxburg Theorem 4). For the sake of clarity, some formulas are not displayed in the table and are given below. As mentioned in the article, the correlation between X (1) and (2) introduces a main effect for these two variables in the HFD, which is of increasing magnitude with the correlation whereas the variability of (1.22) reduces as p increases. This is consequence of the orthogonality constraints leading to pure interactions in the HFD, since (!) (?) alone can partially estimate the term (2), because of their correlation. Symmetrically, variables (3) and x have the same behavior. Notice that constant main effects are also introduced for these variables in the case of
2023
interventional SHAP. As claimed in the article, the decomposition of observational SHAP is hard to interpret, since all components mix all terms of the initial function, because of the input dependence.
The main interactions of observational SHAP decomposition are given by
((1,2) (z. =) = Co + Cmain (x² + =?) )++ + Cinter: X Cpsin
((3.4) (z, 2) = Co + Cmain (x² + 22 + Cinter 2 C₁ sin (1 2Tp
(x + 2) 1
- sin - -C, sin(2
15

---

-1-
x
X
Figure 4: For the analytical case, main effects of the decompositions for ( and ( Solid lines provide the theoretical functions, with the HFD in green, int. SHAP in red, and obs. SHAP in orange. Green and red points are respectively the values provided by TreeHFD and TreeSHAP with interactions for xgboost.
Table 4: Cumulated MSE of the HFD components for TreeHFD and TreeSHAP with increasing sample sizes, for the analytical case (with the standard deviations brackets).
Sample size
100
500
1000
2000
3000
5000
10000
Tre
1.94 (0.4)
0.79 (0.1)
0.55 (0.05)
0.37 (0.03)
0.28 (0.02)
0.21 (002)
0.14 (0.07)
THAP
2.38 (0.7)
1.32 (0.2)
1.26
(0.09)
1.20 (0.09)
1.20 (0.08)
1.24 (0.10)
1.27 (0.0))
where
Co = 2p² +
P
(1
2p²
Cmain
(1 p) -p(1 ((1+p).
12
1+ 2p
1 1 p
Cinter 1 (1+ p)2
2p²
C =e=e--0(11p))
c,=e - 120))
20
We do not provide the other high-order interaction terms for observational SHAP to avoid tedious formulas, since these functions are not really meaningful and take the same form as d(1 and (3344)
Additional figures. We provide additional figures for the main case of TreeHFD combined with xgboost, presented in the article in Section|] for n = 5000, M = 100 trees, and the default values for the other xgboost parameters. Notice that the obtained tree ensemble has a proportion of output explained variance of 90% (noise variance is 5% of V[Y)), and that the TreeHFD residual MSE is 2% of ([T(X). Hence, Figure provides provides the main effects estimated by TrecHFD and TreeSHAP for (3) and X (o), and J the interaction function of (!) and (2) estimated by TrecHFD. We finally specify that one run of TreeHFD for this analytical case with n 5000 and M 100 trees takes less than minute with our treehfd implementation.
Sample size. We repeat the same experiments for the analytical case of Section with the sample size varying from n 100 to = 10000. We report the results in Table|4 which displays the cumulated MSE over all components for TreeHFD and TreeSHAP based on xgboost, for each sample size. In the case of TreeHFD, the cumulated MSE decreases as the sample size increases, as expected from the convergence result of Theorem 7 whereas TreeSHAP MSE is quite constant for n 2 1000. This suggests that Tre does not converge towards the HFD, although it more accurately estimates the HFD than the decomposition induced by observational and interventional SHAP.
Tree depth. Tre relies on the discretization provided by the Cartesian tree partitions. The number of cells for each tree is direct consequence of the tree depth. Hence, we analyze the cumulated MSE for the analytical case with xgboost and the settings Section 4 but varying tree depths (instead of the default value of 6 used in the article). The results are displayed in Table 5 and
16

---

X2
3
X1
Figure 5: For the analytical case, interaction function of ( and ( estimated by TreeHFD.
Table 5: Cumulated MSE the HFD components for TreeHID with xgboost for various tree depths, for the analytical case (with the standard deviations in brackets).
Tree depth
2
3
4
Cumulated MSE
1.49 (0:05)
0.34 (002))
0.26 (0.3)
0.20 (0.02)
0.19 (001)
0.20 (0o1) 0.26 (0.02)
show that even for very shallow trees (a depth of 3 for example), TreeHFD performance is high, and is overall not very sensitive to the tree depth. Only in the case of a tree depth of 1, interactions are not estimated and the cumulated MSE is strongly degraded.
TreeHFD with random forests. As briefly stated in the article, perform the same experiment using random forests with the ranger implementation instead of xgboost, combined with TreeHFD, and results are reported in Table [1. The number of trees is still set to 100, and tree depth is limited to ten, i.e. dr = dy 10 in TreeHFD, since the reduction of the forest accuracy small compared fully grown trees for this value. We observe that the accuracy is reduced in the case of TrecHFD based on random forests compared to xgboost for the main effect of X involving sinusoidal very surprising because the
function and also for the interaction components. Such behavior greedy forest construction, which considers variable one by one for the split optimizations.
Comparisons with glex. We run the analytical case with the same settings than in the article using the algorithm from Hiabu et al. (2023). implemented in the R-package glex. The results are displayed in Table along with the values of Table T obtained for TrecHFD and TreeSHAP to enable comparisons. We do not display standard deviations, since they are negligible compared to the raw MSE values, as in Table I As expected, glex is an efficient estimate of the decomposition induced by interventional SHAP, and strongly outperforms TreeSHAP for this specific task. Consequently. glex does not provide good estimates of the HFD. The MSE of glex for interventional SHAP is similar the MSE of TreeHFD for the HFD for main effects. However, the MSE of glex higher for interaction components than the MSE of TreeHFD. As already mentioned, interventional SHAP is more difficult to estimate accurately than the HFD, because the value function involves expectations with respect to input distributions that are different from the original one (Kumar al. 2020).
Comparisons with EBM. We run the analytical case with the same settings than in the article, using the EBM algorithm (Nori al. 2019) with the default parameters. The results are displayed in Table 6 and show that EBM has an accuracy close TrecHFD to estimate the HFD, even slightly
17

---

Table MSE for glex, EBM. TreeHFD, and TreeSHAP with respect to the specified target decom- positions, for the analytical case.
Algorithm
Target
7/()
(13)
1)
17
77
1
x)
Others
TreeHFD xgboost
HFD
0.02
0.01
0.02
0.02
0.002
0.002
0.04
0.04
S 0.01
EBM
HFD
0.03
0.01
0.01
0.01
0.02
0.01
0.03
0.03
S 0.01
glex -xxx-xxg xgboost
HFD
0.49
0.47
0.46
0.47
0.003
0.003
1.2
S 0.02
TreeHHAP xgboost
int. SHAP
0.49
0.16
0.24
0.25
0.002
0.002
0.77
0.82
S 0.01
glex xgboost
int. SHAP
0.03
0.01
0.01
0.01
0.003
0.003
0.13
0.12
S 0.02
22
X55
X
Figure 6: For the analytical case, main effects of EBM decompositions for (() and (() Solid lines provide the theoretical functions, with the HFD in green and obs. SHAP in orange (int. SHAP is also null and hidden by the HFD). Blue points are the values provided by EBM decomposition.
better for several components, but uses 25000 boosting rounds instead of the arbitrary number of 100 rounds for the xgboost model, broken down by TreeHFD. More importantly, the two main effect components of (5) and (() that are null the analytical HFD, have MSE ten times higher for EBM than for Tre and TreeSHAP. The components generated by EBM are displayed in Figure 6 which shows that EBM introduces non-null functions for these components, because of the correlation between (5) and ( and the other input variables. We deepen this analysis by running the analytical case with EBM for increasing sample sizes. providdss the cumulated MSE for X (5) and (6) components for both EBM and TrecHFD for these various sample sizes, averaged over ten repetitions. While the MSE of TreeHFD decreases as the sample size increases as expected from Theorems
and 7 the MSE of EBM is quite constant. Therefore, it seems that EBM does not converge towards the HFD, and does not share the properties of sparsity and causal variable selection that Tre and TreeSHAP exhibit.
B.3 Real data cases
We first provide the definitions of the metrics involved in Table Then, analyze the "Supercon- ductivity" and "Bike sharing" datasets. The first one shows the high performance of TreeHFD with a quite large input dimension, while the second dataset is example where TreeHFD and TreeSHAP generate close decompositions. Therefore, the decompositions of the two algorithms can be similar or different depending the data properties.
Table Cumulated MSE (5) and (0) components for EBM and TreeHFD with respect to the HFD, for the analytical case with increasing sample size (standard deviations in brackets).
Sample size n
10000
20000
30000
40000
TreeHIFD xgboost
0.0020 (4.10-1>
0.0011 (1.10"1)
6.1 10-4 a.10-1, 5.5 10 a.10-1)
EBM
0.029 (0.006) 0.025 (0.022)
0.024 (0.002)
0.025 (0.002)
18

---

1e-05
0e+00
-Se (04
11e103
10000
20000
30000
40000
10000
20000
30000
Number Rooms
Population
Figure 7: For the "Housing" dataset, main effects of the number of rooms and population in the house block in the decompositions of respectively TreeHFD in blue and TreeSHAP in red.
B.3.1 Definition of performance metrics
Accuracy. The accuracy of xgboost models are the proportion of output explained variance, estimated by 10-fold cross-validation.
Residual MSE The residual error of TreeHFD is defined as the MSE of TreeHFD predictions with respect to the tree ensemble predictions, normalized by the output variance V[7(X)]. This ratio gives the magnitude of TreeHFD errors with respect to the original tree ensemble.
Hierarchical orthogonality. We evaluate the hierarchical orthogonality of the functional decom- positions provided by TreeHFD and TreeSHAP, through the nine real data cases. For each dataset, we consider interaction components with a non-negligible influence in the decompasition, and thus select components with a variance of least 1% the output variance V[T(X). Then, we compute the correlation coefficients between the interaction components and their associated main effects, and report the maximum absolute value for each dataset Table 2 for both TrecHFD and TreeSHAP. We only consider interactions with nonl variance, since the correlation coefficient is undefined otherwise. When there is no interaction component above the threshold of 1%, we display "NA" in Table 2 We also recall that functional decomposition is hierarchically orthogonal when all these correlations are null.
Local variability. We quantify the local variability of the algorithms using the following procedure. We consider a given input variable, and for each observation of the dataset, we retrieve the ten nearest neighbors with respect to this variable, and compute the variance of the predictions from the associated component of the decomposition over these ten points. Then, the average variance over all observations of the dataset is derived, and normalized by the global variance of the functional component. Finally, this metric is averaged across all main effects. The obtained metric is reported Table in the "Local Variability" columns, and shows that TreeHFD is locally much more stable than TreeSHAP for all tested datasets. Notice that the metric is not very sensitive to the number of neighbors, and we get similar results using 5 or 20 instead 10.
B.3.2 Analysis of additional datasets
Housing dataset. For the "Housing" dataset presented in the article, provide the additional Figure 7 for the main effects of the number of rooms and population in the house block, estimated by TreeHFD and TAP. We observe quite strong differences between the two algorithms.
Superconductivity dataset. The "Superconductivity"" dataset (Kelly et al. 2024) is built from the extraction of features from the chemical formula of 21263 superconductors, based on various characteristics, such as thermal conductivity, atomic radius, valence, electron affinity, and atomic mass. The output to be predicted the superconducting critical temperature. We first fit a xgboost model with all default parameters and 100 trees, and then, TrecHFD is run with d₁ 2 to estimate the
19

---

20-
10-
10-
-00-
100
200
1.0
200
300
400
range atomic_ radlus
rtomii_radiuus
range_ ThermalCoonuuutiiity
Figure 8: For the "Supercoonuuctivity" dataset, main effects of X (28) and (68) in the decompositions of respectively Tre in blue and TreeSHAP in red.
2
-2
-4
100
tange
200
Bermal
8
300
500
Figure 9: For the "Superconduutivity" dataset, interaction between (10) and (68) in the decompo- sition, obtained with TreeHFD on the left, and TreeSHAP on the right.
HFD of the resulting ensemble. The xgboost model has a proportion output explained variance of 92% in this case, and the TreeHFD residual MSE is 1% of V[[[X]]. Then, display the resulting decomposition Figures & and Again, we observe that TreeSHAP decomposition is quite noisy. On the other hand, TrecHFD exhibits clear functional relations for both main effects and interactions, although the input dimension of is quite large with 81 variables. We also observe that TreeHFD and TreeSHAP provide quite different decompositions, and the targeted quantities only clearly defined for TreeHFD.
Finally, we run a last experiment to illustrate that EBM and TreeHFD can also generate different decompositions, and EBM can be unstable. We randomly split the dataset in two halves, and compute both EBM and TrecHFD decompositions with each subsample. Figure I0] shows the resulting component for (68), with EBM on the left and TrecHFD on the right. While the obtained TrecHFD component is stable across the two subsamples, it is not the case for EBM, which provides different functions.
Bike Sharing dataset. The "Bike sharing" dataset (Kelly et al.) 2024) gathers data from US bike renting system 2011 and 2012. The number bikes rented by hour is collected, along with time (hour, week day, holiday, season) and weather information (normalized feeling temperature, humidity, wind speed, weather conditions). We apply the same procedure than the proportion of output explained variance of the boosted tree ensemble is 87%, and the TreeHFD residual MSE is 3% the output variance (X). Finally, predictions are computed for HFD components, and displayed in Figures]
other datasets, and
and 12 along with comparisons with the decomposition
20

---

5
(00)
100
200
300
400
100
202
200
400
rango_ _ango_Theraaneeee ChnduaCCnnuulll
rango Tho.maaannnnnutllllyyyyyy
Figure 10: For the "Sunercooduuctivtty" dataset, main effect of ( in the decompositions of respectively EBM on the left and TreeHFD the right. The components obtained for the two subsamples are displayed in orange and brown on the same graph.
200
-700
-700
Temperature
Figure 11: For the "Bike Sharing" dataset, main effects of "Hour" and "Temperature" in the decom- positions of respectively TreeHFD in blue and TreP in red.
induced by TrePSHAP with interactions. We see that TreeHFD and TreeSHAP generate close decompositions, but SHAP values quite noisy, and therefore be misleading when predictions are analyzed one by one. Besides, the identified patterns can be easily interpreted. Indeed, there are renting peaks at the beginning and the end of the day, when people commute to work. Regarding the temperature, there a drop of bike rentals when it is too hot or too cold, as expected. The main interaction term between the variables "Hour" and "Week day", and illustrated in Figure [2 During the weekend (days 0 and 6), the peak of bike rentals is in the middle of the day, instead of the morning and the evening for working days.
Figure 12: For the "Bike Sharing" dataset, interaction between "Hour" and "Week day", for TrecHFD on the left, and TreeSHAP on the right, both based on xgboost.
21

---

C Proofs of theorems
C.1 Proof of Theorem
For J E Ppp we denote by ((J) the marginal density of x For & E Tir, we also introduce the density ft p(.)) defined as the density f(J) averaged over each cell of the partition A& and then the random vector Z )) that admits density se For J Vp, we simply write Ze and fe to lighten notations.
The comerstone of the proof of Theorem 2 is to apply the HFD of Theorem D to each tree Te(Ze), and to show that the discretized orthogonality constraints can also written using X.
Lemma (Tree HFD). Assumption iis is satisfied, then for E Jas, the tree prediction function (Z)) has a unique decomposition as the sum of the functions {N ' IJeP, defined by
Ta(e)) = Σ>'
( (Z)))
JEPs
and such that for all J E P.P. I J with 7 J, Elmi (Z
())
(J)
O. Additionally, for E Pyr
the function Ti (J) is piecewise constant over the partition A,
Lemma 2. If Assumption is satisfied, and for i TM and J E Ppp P4
(J) is a function defined on [0, 1] Jl and is piecewise constant on A!). then C such that I + J and E A we have
Elu (X())) E A] = Elul" ( E A].
Proof of Theorem 2 Let Assumption ! be satisfied. We proceed in two steps, to first show the existence the decomposition, and then its uniqueness.
Existence. For each tree E Tas, we apply Lemma | to get the HFD for ZZzZ), i.e., a unique decomposition the sum of the piecewise constant functions {mé "JEP,, defined by
(e(Ze) = Σ
(3) (Z) (Z)
JEP
and such that for all J Pp. TC with # J. Em (J) 1 0. Next, recall that the
random vectors z have the same distribution support [0, 1| as the vectors x()) and consequently
{nl (3) (x well-defined. Then, according to Lemma 2 the orthogonality constraints implies
that, for C with I + J and A
Eim (J)
) A
Therefore, we obtain the existence of the decomposition
T(X) Σ
T (x()))
JEP
M Σ 8=11
with (x(1))
()),
Tx(X)
Σ
me
(J)
(X
JEP,
and such that for all l JE with + J, A E A B(yé (J) (x ( E A 0.
and where (n) (] (x())) are piecewise constant on associated partitions.
Uniqueness. Notice that the functions (n)"), are not required to be piecewise constant, the decomposition is not unique the general case, because the orthogonality constraints are weakened
compared to the original HFD formulation. Indeed, we can directly apply Theorem to the function T(X) get another decomposition, where the resulting components may not be piecewise constant, depending on the variations of the density f.
On the other hand, if the functions {mg (J) satisfy the decomposition and are piecewise constant, then according to Lemma]] [ the functions {m) (5)) are also the HFD of the trees for the vectors Z where the orthogonality constraints are transformed thanks Lemma Since each HFD tree decomposition is unique, the target global decomposition is unique.
22

---

Proof of Lemmal 7 We consider given tree L E TM.. Since, the tree prediction function Tş is piecewise constant on [0, 1]", T, is square-integralle Then, we can directly apply Theorem from Chastaing et al. (2012) to the function Tz to get the existence of unique set of functions (d)) (Te JEP, such that the Hoeffding decomposition holds, i.e.,
Tz( = Σ
(Z) 11) mi
(J)
JEPp
and for all J E Pp. I J with 1 + J. Elyi (z) (1) (1) 0.
Now, we show that the functions above, we have
(d) constant over A! Let A be cell of Ac. Using the HFD
(Ze E A| Σ
Bime ( (Z) (Z) A].
JEP,
By definition Ti is constant over the cell A, and therefore
B (Z,) A] = Tx()),
with E A. On the other hand, Zg has density fe. which is constant over A. Consequently, the density of Zu conditional on Ze takes the value [A], where the operator Vol[]] gives the volume of given cell. Then, we have for J E Pp.
Ze E A|= = [ (3) (x()) B[me (J) (2)
Vol[A] dx Vol[A(-J]] f
1
(x())))
me
Vol[A] A Ni
f A(
( (x = Elmé ())
(lin)((z)) (z) (z) E A
Vol[Au)
Then, we have another decomposition of Ty as the sum of the functions M (J) defined as
(J)
(x(1)) = Σ
Elue
(J) (2 E AA
Me
AEA
Indeed, combining the above equations, have
Tx(x)= = Σ 4 (x())
JEP
Next, we can show that for all I J with I * J, Elu (J) (Z( |
|z = 0, since
Eln (Z)()((()))
17) 1 Σ
Eim (J) (Z (J) ) A))((Z))) E AlZ
AEAD
Eime
|2 1= 0,
by definition of the HFD. Finally, since this decomposition unique, we have for all J Pa. (J) and therefore, the functions mi are piecewise constant over A!
Mi (y =
havee
Let Assumption be satisfied. For & E TM and J E Pp. we consider square- integrable function fi (J) defined on [0, 1]2 and piecewise constant on A With f(}) the marginal
Proof of Lemma
distribution of (J), we can expand
Elu (J) [X (J) X E A
1
Elu (J) (
((X E AU))
P( E AlI) I Jo.Ju (anl--iixAA -IIX
1
14 (3)
1
Σ
Mh (x())) dx(d)
(3)
P(X E A(T)
AEA AXACO
23

---

We introduce a list of vector points X A x A for A E A Since ug is piecewise constant over the partition A 1 we can write
Blu ( X (
E 1 P(X E AC)
Σ
Me (xx2))
1))
J JAXAI)) (x)())))
AEA
1 P(X E AD)
Σ AEA
( (x )se (x) VollA x A"),
where the last equality follows from the definition of l( the average of f(J) over each cell of the
partition. Similarly, (( E AA = P(Z!" E A) and we get
Biut ( ( E A P E A
Σ He ( E A A
AEAU
Σ
S (3) (x (P(
(J)
EAX 10) E EA
AEAD
(z( E 1
which gives the final result.
C.2 Proof of Theorem 3
(n) Proof of Theorem 3 We apply Theorem to get the tree HFD in JeP,, EETy of T(X. We consider tree & Tar variable set J E E and additional set I C with 1 # J.
For the first result of Theorem
we have
Cov(ne (J) (X()),
x) =E(n (2) (x (J) )m) me (x(())
(1(((
= Σ Eiue (3) (x(()))) (1) (X"')XX'
E A)P(X E).
AEA
Since np is constant over each cell of A by construction, the above covariance writes
Covint (J) ))( (1) (xx)))
Σ
"e (1)
(x) Ix( E AIP((x E A),
AEA
with (A) the value of ni (r())
(1)
(x) for x E A. Finally, using the discretized orthogonality constraints,
conclude that mi and M/ are orthogonal, i.e., Cov(ni )
(x("), ,1 ((x())
For the second part of Theorem we consider given point ((4) E [0, 1] The cell of A(
containing X is denoted by A Since Ti (J) is constant over each cell A of A we write ni (J) (A) this constant value.
Then, we can write
Eine (J) (J) IX x Σ
(3) "'(AA4"))XXX A A( =x0 x0)),
Mi
AEA
Bing (J) (J)
(1) E
- =
Σ
() (A x A(X e A(x e AT))
me
According to Theorem 2 the second equation is null, since n (J) constraints. Therefore, we can write
satisfy the hierarchical orthogonality
Elyg (1) ()()) = 1 Σ
di (1 x (P E = -xx0=xx?
DEA
-P(X(UVD E E
24

---

and get
Ti (A x A
Elue (2) (X
-xx00xxx0 -xx""==>>> = Σ
AEA P(X A!n | E =xx E A
=x0')
Next, we expand the involved probabilities using the density f(J of the vector ( to obtain
P(( EAX A = SAMAU )()
P(X E EA = S Jatix(oaauunn (x)))x)))
P(X xxx) SA (X XD (1) (dx
Soluann (x((x )dx((v)))
We recall that the maximum variability of the density f over cell of the tree partitions is defined by
A = sup sup [f(x) f(x').
REURAAXNEAA
Since f() is marginal density of f, have A A.j A.f- Additionally, f is bounded by positive constants 61, 02 > 0 according to Assumption i.e o S (x)(( S c2. Then, we can bound the above integrals follows. First,
Houjonn (x)())))) (. ( $ 1//,,
and
P(X E A = / -AUTAOOAAI (())(x))) S (o)
Then, we separate the variables ((() and (!) in the integral of the right hand side of the following line to get
Vol(a
/ (()))))
(AXASD) (x01) )ddx
S AXA (()(())))dZ(
SAXACO (x ) - (1))xx))))
JANaOD ( + Vol AJ)
s p(( EAX A + V AT))
Similarly, we also have
Vol(A()) Saaaee
Σ SACa (XLD,
AEAUID
Σ
f ( + A...Vol(AA x AD)
AEAUU)) AXAUD
JAU (x)))())) + DA, Vol(AA()
< p((X)) E A + Voll
25

---

Overall, we obtain
P(X E AIX =x0 ( - - -(( E EAX x 10D
folara ny ((0) x ("dxuurr 1 100 (VV E (DD)
-P(X(") E Ax A
S JALAIIA (1) (
1
|P(X E EA AU1) Ao P E A
ei Vol(At))
-P(X() E Ax AX) E A VolAA
1
(ALOVAAXX)))PE E A - -P(' E EA A Vol(A())
Vol(
AA. Vol(A))((X") E A - E EX A4)
C1
Vol(A
A
C1
where the last step follows from e1 Vol(A()) S P(X()) E ALD S voVo)() Finally, using Equation 2
(A ( 02 -2 A
Elu
(J)
(X("))XXX)
x6
Σ
Vol(A1))
61
C2 a
(A (A x Voll())
A
AEA
< AAAs
C2 C1 E le
(J)
(U) u e 1
where U is a uniform variable on [0, 1110 Therefore, we have
Bim (J) (
C2 c Iime (
We now conclude the proof by the analysis of the targeted covariance using Jensen's incquality, the triangle inequality, and the above inequality,
(( (x = E1n
||| = EL (3) "V (x)))) 1I
| (1)
'11
S 11, 100 M
El )| x 11
22-991000
2
| 11
Σ
M
(J) |100)
AA.
E=1
which concludes the proof.
C.3 Proof of Theorem
Proof of Theorem 4 We consider a pair of variable sets 1, E Pp and the prediction function of
a tree ensemble 7 == E Tr, such that Tj has a decomposition Tx(X) = ge (x + (x(")) for a pair of functions gr, hgg Since Te is piecewise constant over Ar, we can average the functions ge and he over each cell of Ae, and the decomposition of T3 still holds. Therefore, we have
26

---

TX(X) (x( + (x("))) with and by two piecewise constant functions over Ar. Now, we can apply the tree HFD of Theorem 2 to the functions ge. and hy, get
96 (x
=En
)
n
JCI
he (x
())
Σ JCP
The 1
(
where (n) Jecr and "
JCr piecewise constant functions the Cartesian tree partitions of I and satisfy the orthogonality constraints. By construction, we have
T(X)= Σ (3)
(x()) Σ The (x()))
The
JCP
which defines the tree HFD of (X) using the uniqueness property of the tree HFD. In particular, for
J C I In I', the tree HFD component associated with J is given by fle (J) + +1/
(J). Then, we conclude
that for all J E Pp such that J & T and J & I', the tree HFD component o) of T satisfies almost
surely
17 (2) ( ()) = O.
C.4 Proof of Theorem 5
Proof of Theorem 5 Let {ol JEP, the Shapley- -GM decomposition induced by the interventional SHAP value function
Tus {n JEP, be the tree HFD defined in Theorem and
(Bordt and von Luxburg
2023). defined by the marginal expectation
(int) (J) (x x(-
Then, we can define the sets of exogenous variables for the two functional decompositions as
FA = {j ejel Vo LJ Pp: (J-HH) = 0}
(JUGH) 0}. r, E &J E P
By definition, we have
TX(X Σ
of (
(X()).
JCVAN,
We directly apply Theorem 4to get that for J &f Vp TT:
(J)
U1 = 0.
Therefore, we have I', T' Altemaaively, we also have
(X(X) Σ (J)
(X())). m
JCVAT
First, notice that the interventional value function writes, for A E P
(int) (A,x(A) (A)) (x())
x(==))]==
Σ Ei (X((A))) x())))).
JEVATR
Then, we consider j E T,, and Vp such that and apply Theorem 4 from Bordt and von Luxburg (2023) to get
111) (A, x(1
ACI
Σ
(-1) (A, (()))
ACMU)
Σ (-1)01111066)
Σ
Elm (3) ( x(M(UUM)))
AC/V)
JCVATD
27

---

In the last sum of the above equation, we have j E F4 and J C Vo \ Fn. Therefore, J (AU =
J A and J (AU {i}) \ A. Hence.
(x(1))
Σ ((-1)11146 + (-11) (lint) (A, (A,x(A1
ACRO)
Σ [(-1) "
x(1)
ACRO)
= O.
Consequently. j E F, and then Fa C T,,, Overall, we obtain F' T..
C.5 Proof of Theorem
We first recall the bounds of the distribution f of X in Assumption 1 there exists C1, C2 O such that for all x E [0, IP, e1 S f(x) V c2. For E Pp. and / C J with + J, we also denote by f())0(x)
the distribution of ( conditional ( x(1, and use the same notation for all conditional distributions.
Lemma (Lemma 3.1 from (Stone 1994)). If Assumption 7 is satisfied, v is square-integrable function defined on [0, 1|", and { jy is the original HFD of v, then we have
2
B Blu(X) 2
JEPs
(J) Lemma 4. If Assumption is satisfied, (I( }J is the original HFD of Te( and {Me JJ is the tree HFD of Tx(),, then we have for Ppp
T(l) f()
(()
where (5(")) the HFD of (Z)), with
(()
52 = Σ ((()
((
JEP;
Lemma 5. If Assumption 7 is satisfied, then there exists a constant K such that for any tree Te. we have
E (J)
- _ E(T
JEP
where (T("), 35 is the original HFD TX)), and {Tl (n) is the tree HFD of Te(X..
Proof of Theorem 6 We first split the MSE of interest using the original HFD (T(J) of T(X), follows
E[(n () - m ()) (X E[((n - -x)) ( (x())(())))))))))))))))))))))))) (m)) (x(())))
Recall that for two real numbers a, b, we have (a + 6)2 < 2(a² + 122). Hence, we have -m (2) (x())) 2F(( (x(1) - -()) (x(1)))
B((1"") -
+ (E
m (J) (((()))))))
The core of the proof is thus to bound the two terms of the right hand side of the above inequality. We first focus on (n) (x(())) - -r( (x))))) If we denote by (I tree Ti(X). the HFD uniqueness implies that
}, the original HFD of each
M
(()) = Σ ( (x())
8-1
28

---

Consequently,
M
B((1| (0) (x - ((
Σ
(
())) T (x )
M
(x(x)) T )
(x()) - (x
=
2,1==1
(x)))))))
T )3}}
6,0==1
using Stuchy-Schwarre inequality at the last step. Finally, apply Lemma 3 to obtain that there exists a constant K₂ > such that
M
B[(n (1 - (x00
K2 2
A
VE(T(X)3))
For the second term (E(((()) - m ()(( we use again the HFD uniqueness to get that
the original HFD of T(X) (X) is given by (T())(x()) - m m))) (x)))) We apply Lemma 3 to T(X) m (X) to get that there exists a constant K1 > 0 such that
B((T") - m (2) (X
2 Ex(m(() - T (
We combine the two last inequalities to obtain the final result, that is
M
(x())) m (x())(())) K [[(((X) - T(X)) -(x))) K2
Σ E=1
v [(T)(
2
Proof of Lemma 4
By construction, we have
Σ
T
JEP,
Therefore, we simply need to show that the orthogonality constraints of the tree HFD are satisfied by (nl (J) J, to obtain the final result using the uniqueness of the tree HFD. Hence, we write for I C J with I J.
(())
= T
8 50 (z)
E
= T!! (J)
|2
since ((2)(Z()) () satisfies the orthogonality constraints by definition. Next, recall that conditional
on Z (T) Z (J) has density f( I) and (J) conditional on x()) has density (()l)) which are both
positive. Therefore, for x( (1) E [ö, 1 we have
(()
E
E
Z (1) = x00]
(1)) (z) 11
ETTT"((X()) (( I (((0))
= =x"] (( (OIN x²() (x1)=xx
( E (J) (x(")))) = =x00] = 0,
S 5
since " satisfies the orthogonality constraints of the original HFD.
29

---

Proof of Lemma 5
We consider that Assumption is satisfied, and we apply Lemma 4 to get that (J)
- f(J)
Mi = T(())
56
{( ")
where (r is the original HFD of (X),, (TT J is the tree HFD of (X)), and ( is the HFD of (g())) with
f(
55 = Σ T(U)
-1).
JEPp St
Hence, we have
B((nk) (3) (x(1)) - (x())) =R. (T( (x())) (x())
1100 (x -1) 8% (x()))
f())((())
- ]1 +B (640) (00 (xl))) I
2
<IE
2E | )y
- -1)0 (I( (xx
{( ((0)((10))
We apply Cauchy-Schwartz inequality, and obtain E((T) (3) (x()) (x()) (x()))
2 (X)) - -1 + (6
(x()
IE T )
First, we bound E.
(x - ]
2
We define // f(J) ,! and then,
(())((()) -1 -
ge d (x()))
(())))
((4)) (x()))
Using Assumption construction, we have
|
which also implies that C1 S f (x(x)) S C22 and 19 (x(()))))) < Das by
(())
g (x(())
AAA
(
C1
and consequently,
E
T
(x())
((()) (X(())))
-1) 9
s of
A
(1)))))
Next, we use Lemma
and get
E 22
(10)) ((
11) S A of (x)))
K
JEP
with K₂ K1=(1 (1
+1
Similarly, we use Lemma 3 again to get
(26 2 K E Σ
JEP
JEP
Since
(J) (x (x()))
Eb0 2) (z) 20) E (. ((((((())) (x)
CI E15 (2(1)
>
C2
30

---

we get
1y <
ممية C2 K E
Σ JEP
IT! ( 11)
JEP
Then, using Cauchy- Schhwrt- inequality, notice that
B[(
Σ
IT|
)
Σ
EiIT! (
( (x()
JEPp
L
Σ
E
I,JEP,
2d K[T,(()))
We finally obtain
Σ
[x 23, k
JEPp
Overall, combine the previous incqualities state that
K (v | oी
B((T) (0)
- (x))
(x())))
EXT(
+
A
22p K (X)=
of
$ A A of
K1
(1 2"
C2 (X)
which gives the final result.
C.6 Proof of Corollary
Proof of Corollary
7 We first apply Theorem
6 to get
M (Σ Em1
K A. VET()))) 9.
()) ml (J)
X (1))) < -
where expectations are also taken with respect to the random training data of 7 of size ny. Now, we show that both terms of the above inequality converges towards zero when ny grows. For the first term, we use that 7 is Lo-consistent by assumption, that is [m(m(() T
0. Next,
analyze the second term. By definition, have
A
sup sup [f(x) f(x)). AEURÁ XX'EA
Since the distribution f is assumed to be Lipchitz function with constant that we write K3 > 0, we have
A K3 sup sup ||x-x') x'|- AEULAEX
Following the notation of Scornet et al. (2015). we define the diameter of a cell C [0,1] by
dia
sup xx'EA
and obtain
A S Kg sup diam(A). AEULA,
By assumption, the input distribution / strictly positive on [0, 1|2 each node split leaves at least a fraction 7 >> O of the observations in each child node, and the optimization of node splits is slightly randomized to have positive probability to split with all variables. Then, following (Meinshausen and Ridgeway) 2006 Lemma 2) and (Bénard al. 2022
Lemma 5), the number of splits along each
31

---

direction grows to infinity when nr grows, and the gap between two consecutive splits cannot vanish too fast. Therefore, we get that in probability.
sup (i)
AEU:A,
ny 150000
Finally, since all trees are bounded, we obtain that the second term of the initial inequality converges towards zero, and ultimately
((())) - m - (((()()))) - O.
~T-20
C.7 Proof of Theorem 7
Lemma 6. If Assumption is satisfied, for g(d)... , R. we have Ln P,P La.
Proof of Theorem 7 We consider a tree & E TM, and that Assumption Dis satisfied. From Lemma 6 for 3
KK, R. we have
(3) Ln - L*
Additionally, the set of functions {1) Jep, is the tree HFD of (X),, which belongs to the class of
functions parameterized by { ,...,,8 K. J. according to Theorem Therefore, L is a convex
B(1)
k J.. that has a unique minimum at fnz ( "JEP, where L* = O. Since the optimization of L, is done over compact set, the pointwise convergence above implies the uniform convergence of I., over this compact set. Finally, we can apply Theorem 5.7 from Van der Vaart 2000) conclude that for all J E Ppp. we have
positive function of the parameters (8(
(J) ME
Pn.
Proof of Lemma 6
Using the law of large numbers, we have
(X. Σ
1) 2 P. ([(((( - Σ ue
( (1))
71
JEP
JEPp
E. P(X E Al (x((n)) E (
vl Ox Eaf
1
Me E P(X E (
Then, we combine these limits to state the convergence of the empirical loss I, as follows.
Ln
P,
(Tx(
Σ me
(J)
(1
JEP
Knys
K2 Σ
ΣΣΣ
[V (P((/))) E A M=1
3 P(X(") E 1 E (brr)))2
JEP JEJ k=1
=E (Tx Σ 4 (1()))
JEP
Kng
+ ΣΣΣΣ JEP, JEJ 1=1
Elub (l (X)I E A PPPPUXX E Al
and finally, obtain that
In P (T
Σ JEP,
( (x())))
ΣΣΣ
Elu (J) (X
Me
JEP, JEJ AEADW
= I.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Sections and 3 for the theoretical claims and introduced algorithm, and Section 4 for the experimental claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Sections 2 and carefully analyze the theoretical properties of the introduced algorithm, in partieular the approximation with respect to the target HFD. Section provides experiments with the errors of the introduced algorithm in practical cases. The limitation paragraph in the conclusion highlights the main limitations of the introduced algorithm.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLmitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
33

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
See Assumptions defined in Section 2 and the proofs in the Supplementary
Material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The introduced algorithm is fully described in Section 3 and we provided all details about the experiments in Section 4 and the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
34

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide the code with instructions reproduce the experiments of the article. Real datasets are available online on the UCI repository (Kelly et al. 2024).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
httppppwwl.pgguuu.p/pppppppspeel ltiips.cc/pullcc/guicc.
CodeSubmii ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ys]]
Justification:
See Section of ff the article and Section B of the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Experiments with simulated data are run multiple times to compute the standard deviations of all metrics, which are displayed in Tables and for example. Notice that for Tables and [ all standard deviations are small with respect to the associated metric values, and are therefore omitted for the sake of clarity.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: See Section B of the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::///// h/tpprip////rrps.eeeee http://s......uuulttttttcccccuaa
Answer:
[Yes]
Justification:
We conducted this work following the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The article states that black-box models, such as tree ensembles, may have negative societal impacts in critical domains (e.g.. healthcare or industry). The article expected to have a positive societal impact, since it introduces new XAI algorithm, in order to improve explainability of machine learning models for safe use in these critical domains.
Justification:
36

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The article deals with XAI methods for tree ensembles, which do not have high risk of misuse. Experiments are conducted with existing open datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
See Section B of the Supplementary Material.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
37

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thooe cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce the treeHFD software package, which has a specific documenta- tion provided in the package.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The article does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The article does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
38

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
This research work was conducted without using LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
39


Reviews:
[{"review_id": "pqca5D0GPD", "reviewer": "Reviewer_cnRC", "summary": "This paper introduces TreeHFD, an algorithm designed to compute the Hoeffding Functional Decomposition (HFD) for tree ensemble models such as gradient boosted trees and random forests. The HFD is an explainability method that provides a unique decomposition of a function into a sum of main effects (univariate functions) and interaction terms (multivariate functions). However, its practical estimation, particularly in the common machine learning setting with dependent input variables and an unknown data distribution, is a challenging task. The authors propose an algorithm that takes a trained tree ensemble and a dataset as input, and formulate a loss function for each tree composed of two parts: a mean squared error term to ensure the decomposition accurately reconstructs the tree's predictions, and a penalty term to enforce the hierarchical orthogonality that defines pure interactions. This objective is then solved as a standard least-squares problem. The authors provide theoretical justification for their approach, namely the uniqueness of their proposed TreeHFD, the near-orthogonality of the final components, the sparsity of the decomposition, the algorithm's convergence, and its ability to perform causal variable selection. They also empirically demonstrate that TreeHFD accurately estimates the HFD on synthetic data.", "questions": "1. Please expand the analysis on at least one or two more datasets, showing how TreeHFD captures main effects and interactions.", "limitations": "Mentioned in the weaknesses:\nThe algorithm's computational cost is dependent on the number of cells in the Cartesian tree partition, which can increase exponentially with tree depth. The authors propose using hyperparameters ($d_T$, $d_V$) to prune deep trees or limit the number of variables considered as a practical solution. This approach, however, feels somewhat ad-hoc. The paper uses XGBoost as an ensemble (where the default depth is 6) , but for other ensembles that require deep trees, such as those in a standard Random Forest, this pruning could lead to accuracy degradation.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The authors define the HFD specifically for tree ensembles, introducing a \"Cartesian tree partition\" input space splitting, which helps with the discretization of the orthogonality constraints.\n- The proposed work is grounded on mild assumptions, namely that the input distribution has bounded density on a hyperrectangle support, which is often a reasonable assumption for tree-based models.\n- The proposed TreeHFD algorithm is not merely a heuristic. The authors define a TreeHFD by adapting the classic HFD framework to the piecewise-constant nature of tree-based models. They formally derive its essential properties, such as uniqueness, orthogonality, sparsity, and causal variable selection.\n- The experimental evaluation is well-structured. The use of an analytical case with a known ground-truth HFD provides a clear demonstration of TreeHFD's accuracy. The qualitative analysis of the California Housing dataset coincides with common sense, although it might benefit from more analysis on the other variables and their interactions.\n\nWeaknesses:\n- The algorithm's computational cost is dependent on the number of cells in the Cartesian tree partition, which can increase exponentially with tree depth. The authors propose using hyperparameters ($d_T$, $d_V$) to prune deep trees or limit the number of variables considered as a practical solution. This approach, however, feels somewhat ad-hoc. The paper uses XGBoost as an ensemble (where the default depth is 6) , but for other ensembles that require deep trees, such as those in a standard Random Forest, this pruning could lead to accuracy degradation.", "was_revised": true, "final_justification": "The authors answered all my questions and concerns. However, I am still concerned that a fixed tree depth of 12 might be a restrictive hyperparameter for tasks with greater complexity. Given strengths I previously mentioned, I will maintain my original score.", "rebuttal": "Thank you for taking the time to write this review, and for the relevant comments and suggestions. In particular, the question about additional datasets will clearly improve the article. We also address the comment about the computational complexity of TreeHFD.\n\n\n\n**Additional real datasets to illustrate TreeHFD.** We agree that analyzing several real data cases is essential to show the practical performance of an XAI method. In fact, we originally used three datasets to illustrate TreeHFD: the California Housing dataset, the Superconductivity dataset, and the Bike Sharing dataset. Because of the 9-page limit, we moved the results for the last two datasets to Appendix B.3.2 (pages 18-20). If the paper is accepted, we will use the additional page to move these relevant examples back to the core of the article. More precisely, the Superconductivity dataset highlights the good performance of TreeHFD for a quite large input dimension of 81, and the Bike Sharing case shows that the patterns identified by TreeHFD can be easily interpreted, as explained in the last paragraph of page 18.\n\n\n**Computational complexity of TreeHFD for large tree depths.** The TreeHFD algorithm has a high computational complexity when the tree depth is large,  as also highlighted by Reviewer iKso. This is clearly stated in lines 294-296 of the article, and further details are provided in Section A of the Appendix. We will also take advantage of a potential additional page to move this important discussion to the core of the article. \n\nXGBoost tree ensembles most often use shallow trees, with a depth between 3 and 8, which is easily handled by TreeHFD. The second main type of tree ensembles is random forests, which use fully-grown trees, where TreeHFD may indeed become inefficient. However, it is frequently mentioned in the literature that splits at the bottom of trees are not significant in random forests, and that reducing tree depth barely impacts accuracy [1]. The main convergence result of random forests does not hold for fully-grown trees, but requires an asymptotic regime where the number of terminal leaves is not too large with respect to the sample size [2]. From a practical point of view, we compare the accuracy of random forests with default parameters to the case where tree depth is limited to 12, for all real datasets of Section 4. We display the performance in the table below, and observe that the loss of accuracy is very small in all cases, except two (accuracy is defined as the proportion of output explained variance). This shows that the required pruning preprocessing of TreeHFD for tree ensembles with large depths is not a strong limitation, although it may indeed induce a small reduction of forest accuracy in specific cases.\n\n| Dataset | Tree depth (Fully-grown RF) | Accuracy (Fully-grown RF) |  Accuracy (RF with tree depth of 12) |\n|:----------:|:--------------------------------------:|:-----------------------------------:|:-------------------------------------------------:|\n| Abalone | 33 | 0.56 | 0.56 |\n| Airfoil | 14 | 0.90 | 0.90 |\n| Bike Sharing | 33 | 0.81 | 0.74 |\n| Housing | 31 | 0.81 | 0.78 |\n| Concrete | 22 | 0.91 | 0.90 |\n| Nutrition | 28 | 0.32 | 0.33 |\n| Parkinson | 34 | 0.79 | 0.74 |\n| Power Plant | 18 | 0.97 | 0.96 |\n| Superconductivity | 49 | 0.93 | 0.91 |\n\n\n**References**\n\n[1] Duroux, R., & Scornet, E. (2018). Impact of subsampling and tree depth on random forests. ESAIM: Probability and Statistics, 22:96-128.\n\n[2] Scornet, E., Biau, G., and Vert, J.-P. (2015). Consistency of random forests. The Annals of Statistics, 43:1716–1741."}, {"review_id": "2obrQSueDJ", "reviewer": "Reviewer_iKso", "summary": "The paper introduces TreeHFD, a post-hoc explanation method for tree ensemble models that estimates the Hoeffding Functional Decomposition (HFD) directly from data without requiring knowledge of the input distribution. HFD breaks the model prediction into a sum of orthogonal components over variable subsets, enabling interpretable representations of main effects and interactions. TreeHFD ensures key properties like uniqueness, sparsity, near-orthogonality, and causal variable selection. It outperforms TreeSHAP in terms of stability and interpretability, and the authors show empirically that TreeSHAP closely approximates the HFD but suffers from entangled and noisy components.", "questions": "The paper’s focus is restricted to regression problems, where the output variable is continuous and modeled as $Y = m(X) + \\epsilon$. How could it be applied to the classification tasks?", "limitations": "TreeHFD operates directly on the structure of the trained tree ensemble and thus requires full access to the internal components of each tree, including split variables, split thresholds, and leaf values. It is not a huge limitation in explainability, but should be briefly discussed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper studies an important aspect in explainability by fining the Hoeffding functional decomposition for dependent data. The Hoeffding functional decomposition is a functional decomposition with extra constraints of zero-mean functions and orthogonality; this paper puts forward a way to construct such a decomposition for tree ensembles in polynomial time, which is a drastic improvement over the recursive construction in exponential time. That is why the paper is of significant importance. \n\nA key limitation of TreeHFD is its scalability with respect to the complexity of the trees in the ensemble.  Although the algorithm is efficient in terms of sample size, the complexity of the decomposition grows with the tree depth, the number of interaction terms, and the number of splits, which can become computationally intensive for deep or large ensembles unless pruning is applied. To keep the decomposition tractable, the authors restrict the order of interactions to at most two by setting the interaction hyperparameter d_I =2, meaning that only main effects and pairwise interactions are modeled. This setting seems to be consistently used across all experiments in the paper. While this promotes interpretability and computational efficiency, it may overlook higher-order interactions that could be relevant in some domains, and is in contrast with the efficiency claims in the paper. \n\nIn addition, the paper assumes that input features lie within the unit hypercube $[0,1]^p$ with a density bounded away from zero and infinity. While this assumption simplifies the theoretical analysis—ensuring well-behaved integrals, uniqueness of the decomposition, and control over orthogonality—it does not naturally hold in many real-world datasets where features vary in scale or distribution. Although normalization can map features to the $[0,1]$ range, this transformation may not have been used in the original trained model and   could obscure relationships in the original feature space. Moreover, the assumption of a uniformly bounded density may be unrealistic in high-dimensional or highly skewed settings, potentially limiting the robustness of the decomposition and its convergence guarantees.\n\nAnother limitation lies in the way the paper assumes the tree ensemble prediction function is constructed as a simple sum of the outputs from individual trees, i.e., $T = \\sum_\\ell T_\\ell$. While this assumption holds in some models like random forests (up to averaging), it does not directly apply to boosting algorithms like XGBoost, where each tree output is scaled by a learning rate. This assumption appears throughout the main theorems and derivations, yet the paper does not explicitly clarify whether these scaling factors are absorbed into the definition of $T_\\ell$ or how they impact the theoretical validity of the decomposition. Clarifying this point seems to be essential for a broader applicability of the paper. \n\nFor readers unfamiliar with the Hoeffding Functional Decomposition (HFD), the paper could benefit from a brief exposition of the classical case—where input features are assumed to be independent—and the recursive formulation used to construct the decomposition. This would not only make the paper more accessible to a broader audience, but also highlight the difficulty of constructing HFD even for independent features. \n\nI am willing to raise my score if these concerns are adequately addressed.", "was_revised": true, "final_justification": "I think the paper puts forward an interesting way of computing Hoefdding decomposition (also known as functional ANOVA decomposition) for tree ensemble models, which is critical in interpretable machine learning.", "rebuttal": "Thank you for the detailed review, which provides many relevant comments and suggestions. This will help us improve the article, especially the clarity of several points. \n\n**Ensemble defined as the sum of individual trees.** The scaling factors involved in the aggregation of trees (e.g., inverse of number of trees in random forests, and learning rate for boosted ensembles) are indeed absorbed in the definition of each tree predictor $T_{\\ell}$. This is stated lines 130-132 of the article. Therefore, all the developed theory applies to xgboost tree ensembles. We will rephrase these sentences to improve clarity of this definition.\n\n\n**HFD for independent inputs.** We agree that a brief presentation of the HFD for independent variables will improve the accessibility of the article. We will include it in Section 2.1 of the revised  article. Thank you for this suggestion.\n\n\n**Assumptions for the input distribution.** We assume that the input variables lie in the unit hypercube, as is often done in the theoretical analysis of tree ensembles [3, 5]. Importantly, the unit cube is chosen for its simplicity and without loss of generality, since all the developed theory also hold for any hyperrectangle support. Indeed, the HFD for dependent inputs stated in Theorem 1 holds for any hyperrectangle support, as explained at the end of page 126 of [4], and in Theorem 1 from [1]. This is also the case for our theoretical analysis.\nIn particular, datasets with features that greatly vary in scale are included in this assumption. In fact, this assumption of bounded support is not very restrictive. Finally, we agree that the assumption of positive bounds of the distribution is slightly more restrictive, but strongly alleviates the mathematical analysis. We will add these comments in the revised version of the article. \n\n\n**Classification case.** The extension of TreeHFD for XGBoost models to classification problems is straightforward. Indeed, the predicted logits for each class are continuous outputs, and can therefore be handled as the regression case to obtain the HFD of the logit for each class. However, in the case of random forests, classification problems are solved using majority votes, where each tree outputs a predicted class. In this case, it seems that the HFD defined by Stone and Hooker does not directly apply. The specific case of binary classification can be treated as a regression problem, and TreeHFD naturally applies in this case for all tree ensembles. Hence, we will also add this discussion in the revised version of the article. Thank you again for the suggestion.\n\n\n**Access to the internal tree structures.** Indeed, TreeHFD needs to access the internal structure of the trees, which is rarely a limitation, since all main software packages for tree ensembles provide an API to retrieve tree structures. It may not be possible in specific cases, such as pre-trained models or proprietary tools. We will add this comment in a dedicated limitation paragraph.\n\n\n**Order of interactions.** We only include main effects and second-order interactions in TreeHFD decompositions, since they are sufficient to break down the initial xgboost models for all tested datasets, as shown by the small residuals in Table 2. If relevant for specific cases, we could easily add third-order interactions in TreeHFD for shallow trees. However, for higher-order interactions, the Cartesian tree partitions may suffer from the curse of dimensionality. Overall, notice that interactions of order three or higher cannot be represented, and are therefore not really useful to build explainable models. Consequently, we focus the experimental section on main effects and second-order interactions. We will further emphasize the limitation of TreeHFD for high-order interactions in the article.\n\n\n**Computational complexity of TreeHFD for large tree depths.** The TreeHFD algorithm has a high computational complexity when the tree depth is large,  as also highlighted by Reviewer cnRC. This is clearly stated in lines 294-296 of the article, and further details are provided in Section A of the Appendix. If the article is accepted, we will take advantage of the additional page to move this important discussion to the core of the article. \n\nXGBoost tree ensembles most often use shallow trees, with a depth between 3 and 8, which is easily handled by TreeHFD. The second main type of tree ensembles is random forests, which use fully-grown trees, where TreeHFD may indeed become inefficient. However, it is frequently mentioned in the literature that splits at the bottom of trees are not significant in random forests, and that reducing tree depth barely impacts accuracy [2]. The main convergence result of random forests does not hold for fully-grown trees, but requires an asymptotic regime where the number of terminal leaves is not too large with respect to the sample size [3]. From a practical point of view, we compare the accuracy of random forests with default parameters to the case where tree depth is limited to 12, for all real datasets of Section 4. We display the performance in the table below, and observe that the loss of accuracy is very small in all cases, except two (accuracy is defined as the proportion of output explained variance). This shows that the required pruning preprocessing of TreeHFD for tree ensembles with large depths is not a strong limitation, although it may indeed induce a small reduction of forest accuracy in specific cases.\n\n| Dataset | Tree depth (Fully-grown RF) | Accuracy (Fully-grown RF) |  Accuracy (RF with tree depth of 12) |\n|:----------:|:--------------------------------------:|:-----------------------------------:|:-------------------------------------------------:|\n| Abalone | 33 | 0.56 | 0.56 |\n| Airfoil | 14 | 0.90 | 0.90 |\n| Bike Sharing | 33 | 0.81 | 0.74 |\n| Housing | 31 | 0.81 | 0.78 |\n| Concrete | 22 | 0.91 | 0.90 |\n| Nutrition | 28 | 0.32 | 0.33 |\n| Parkinson | 34 | 0.79 | 0.74 |\n| Power Plant | 18 | 0.97 | 0.96 |\n| Superconductivity | 49 | 0.93 | 0.91 |\n\n\n**References**\n\n[1] Chastaing, G., Gamboa, F., and Prieur, C. (2012). Generalized Hoeffding-Sobol decomposition for dependent variables - application to sensitivity analysis. Electronic Journal of Statistics, 6:2420 – 2448.\n\n[2] Duroux, R., & Scornet, E. (2018). Impact of subsampling and tree depth on random forests. ESAIM: Probability and Statistics, 22:96-128.\n\n[3] Scornet, E., Biau, G., and Vert, J.-P. (2015). Consistency of random forests. The Annals of Statistics, 43:1716–1741.\n\n[4] Stone, C. J. (1994). The use of polynomial splines and their tensor products in multivariate function estimation. The Annals of Statistics, 22:118–171.\n\n[5] Wager, S. and Athey, S. (2018). Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113:1228–1242."}, {"review_id": "oqLMF41LRf", "reviewer": "Reviewer_Ngv6", "summary": "The authors introduce TreeHFD, an algorithm estimating the Hoeffding Functional Decomposition (HFD) of tree ensembles in cases where only data samples are available. HFD decomposes a function prediction into a sum of lower-order functions over variable subsets and thereby naturally enables explainability through the main effects and low-order interactions. This approach is applied by the authors to tree ensembles with unknown input distribution by discretising the orthogonality constraints. Besides theoretical analysis of the method and resulting algorithm, the authors conduct simulations and experiments with TreeHFD and establish a connection to the functional decomposition provided by TreeSHAP.", "questions": "- The whole model development and experimental setting revolves around regression. However, tree ensembles provide also SOTA prediction methods in the classification setting. To what extent can treeHFD be also applied/extended to this use case?\n- Could treeHFD also be used for feature selection? Could it, for example, be employed to prune noisy trees with many irrelevant variables?\n- Figure 2: Why are no orange points from the respective estimation with TreeSHAP included?\n- Table 2: Why are there NA values for the orthogonality of the datasets \"Power Plant\" and \"Superconduct.\"?\n- Housing Dataset: The authors write that TreeShap does not detect the peak, however, I would argue that it does (just to lower extent than treeHFD). Can the authors elaborate on this observation? Also, how would the main effects for TreeSHAP without interactions look like in this example?", "limitations": "Partially. While the authors claim in the checklist that they are discussed in Section 4 with the experiments, I cannot find them there. Instead I would have preferred a separate statement on the current limitations of TreeHFD and in which scenarios it fails.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Interesting novel application of the HFD to tree ensembles in the practically relevant case of an available data sample but unknown input data distribution\n- Extensive theoretical analysis of the HFD for tree ensembles incl. the convergence of the proposed algorithm\n- Extensive experiments on both simulated and real-world data, including comparisons to relevant competitive approaches\n\nWeaknesses\n- Intuitive example for the application of treeHFD is missing. Given that it presents an XAI method to make effects of a black-box model more transparent, an example with real world data with large p and resulting interpretations would showcase its practical relevance.\n- No description of the difference between interventional and observational SHAP is provided. Although is only a compared method, this would be valuable to understand the experimental section better.\n- SHAP can be used to provide local explanations for a given data sample. TreeHFD could also evaluate the global functional decomposition at given inputs, however, exemplary evaluations of this scenario are not presented.\n- No details on the computational complexity of the algorithm are discussed (running times, scaling to higher-order interactions etc.). Similarly, it is not discussed in which scenarios treeHFD fails.", "was_revised": true, "final_justification": "I keep my score", "rebuttal": "Thank you for your positive comments and relevant suggestions, often shared by other reviewers. We will improve the article accordingly.\n\n\n**Intuitive real examples to illustrate TreeHFD.** In section 4, we illustrate TreeHFD with a real data case, the California Housing dataset, which exhibits patterns that are easy to interpret. However, we agree that other intuitive examples should be analyzed to show the practical performance of TreeHFD, especially cases with higher dimensions and strong interactions, as also mentioned by Reviewer cnRC. In fact, we originally used three datasets to illustrate TreeHFD: the California Housing dataset, the Superconductivity dataset, and the Bike Sharing dataset. Because of the 9-page limit, we moved the results for the last two datasets to Appendix B.3.2 (pages 18-20). If the paper is accepted, we will use the additional page to move back these relevant examples to the core of the article. More precisely, the Superconductivity dataset highlights the good performance of TreeHFD for a quite large input dimension of 81, and the Bike Sharing case shows that the patterns identified by TreeHFD can be easily interpreted, as explained in the last paragraph of page 18. Overall, we believe that these examples together are convincing to show the practical efficiency of TreeHFD.\n\n\n**SHAP definitions.** The definitions of observational and interventional SHAP are briefly given in the paragraph “causal variable selection” of Section 2.2. However, there are no details in the experimental section. We will refer to the definitions of Section 2.2 in Section 4, and add complete formulas of SHAP values in Appendix B.1 to improve the understanding of the experimental section.\n\n\n**Computational complexity.** The analysis of TreeHFD complexity is provided in lines 282-287 of the article. In the revised version, we will move this discussion in a separate paragraph with additional details to improve clarity, as also suggested by Reviewer QYXH. More precisely, the first step of TreeHFD is to build the constraint matrix $\\mathbf{C}_n$ from the tree partitions and data sample for each tree. This is done with a linear complexity with respect to the sample size $n$, since we only need to count the number of points falling in each cell of the Cartesian tree partitions. Once this matrix is computed, the computational complexity of the optimization problem only depends on the size of the matrix $\\mathbf{C}_n$, which only depends on the size of the Cartesian tree partitions, and not on the sample $n$ or dimension $p$. For example, if $p$ is very large, the number of variables and interactions involved in the decomposition of a given tree is bounded by the number of nodes in the tree, which only depends on the tree depth. We highlight that $\\mathbf{C}_n$ is highly sparse by design, and we can therefore use efficient solvers of sparse QP problems, such as $\\texttt{osqp}$ package. Finally, notice that we provide an example of running time of TreeHFD in Appendix B.1 (lines 533-537).\n\n\n**Separate limitation paragraph.** The limitations of the introduced TreeHFD algorithm are spread across all sections. We agree that it is better to write a specific paragraph to group the main limitations, especially about the inefficiency of TreeHFD for large tree depths (also mentioned by Reviewer cnRC), and the required access to the internal tree structures (mentioned by Reviewer iKso). Thank you for the suggestion.\n\n\n**Local explanations.** TreeHFD can explain a given prediction similarly to SHAP, by the break down of the prediction across all input variables and interactions, which can be displayed efficiently through a waterfall plot. We agree that it would be interesting to present such cases in the article. However, such results over few prediction points only illustrate the algorithms, but cannot be used to assess performance. Because of the page limit, we would rather prioritize the global evaluations of Tables 1 and 2, and add additional real datasets in the potential additional page.\n\n\n**Classification case.** The extension of TreeHFD for XGBoost models to classification problems is straightforward. Indeed, the predicted logits for each class are continuous outputs, and can therefore be handled as the regression case to obtain the HFD of the logit for each class. However, in the case of random forests, classification problems are solved using majority votes, where each tree outputs a predicted class. In this case, it seems that the HFD defined by Stone and Hooker does not directly apply. The specific case of binary classification can be treated as a regression problem, and TreeHFD naturally applies in this case for all tree ensembles. Hence, we will also add this discussion in the revised version of the article. \n\n\n**Feature selection.** TreeHFD can be used for feature selection. For example, an importance measure can be defined for each variable and interaction through the variance of the associated decomposition component. Then, this feature importance can be used for variable selection, when combined with uncertainty quantification methods, to discard irrelevant features. However, such extension is out of scope of the article given the large literature about variable importance and uncertainty quantification, but is definitely an interesting idea for future work.\n\n\n**Details for figures and tables.**  The NA in Table 2 are explained in the third paragraph of Appendix B.3.1 (lines 645-654). In fact, we only consider interactions with a non-negligible variance, otherwise the correlation coefficient is undefined. For these datasets with NA, there is no interactions with the chosen threshold of 1% of the output variance.\n\nIn Figure 2, TreeSHAP is displayed in red. The solid lines in red and orange are the theoretical decomposition components derived from the value functions of respectively interventional and observational SHAP. There is only one version of TreeSHAP algorithm, designed from a heuristic procedure, which does not clearly target interventional or observational SHAP. In our experiments, we show that the decomposition induced by TreeSHAP is closer to the HFD than the two SHAP decompositions. We are not sure that we have properly understood this comment. Let us know if it is not the case.\n\nFor the peak of TreeSHAP for the Housing dataset, we agree that TreeSHAP slightly detects it. However, the peak is small compared to local noise of TreeSHAP decomposition, and it is therefore hard to understand whether it is significant. On the other hand, it is clear for TreeHFD. We will soften this comment in the article, following your remark."}, {"review_id": "812WDQynlE", "reviewer": "Reviewer_QYXH", "summary": "The paper develops a method to approximate the Hoeffding Functional Decomposition (HFD) of tree ensembles. The authors first derive the HFD for tree ensembles with the property that the resulting functionals are piecewise constant. They then show interesting theoretical properties of this HFD including a near hierarchical orthogonality and provide an efficient way of estimating this HFD for tree ensembles.", "questions": "As mentioned above, I wonder whether consistency in Theorem 7 is not very oversimplified. The theorem and proof make sense to me for a fixed partition, but as far as I understand these partitions depend on the trees and these in turn change with the sample size. So basically the HFD for tree ensembles changes with n and it is not even clear to me what the limit should be. So it seems to me that the problem is more complex than what is formalized in Theorem 7. From a statisticians perspective, I would either need more explanation here if I am wrong, or a discussion on what kind of simplyfying assumptions were taken. I think with trees it is absolutely ok to first proof constistency results in a simplified setting.\n\nIf this can be addressed sufficiently, I am happy to increase my grade.\n\nOther than that I only have a few comments:\n- I do not understand the first equality in Lines 780 and 781 (Proof of Theorem 3). Is there a short sentence that can be added to explain this?\n- At the end of that proof I am missing the step where we go from \\eta_{\\ell} to \\eta, in fact the last equations after line 786 seem to suddenly jump from \\eta to \\eta_{\\ell}. It seems like a small step, but I think it should be explained.\n- It could be good to have some description of how we get from L^* to L_n on page 6. The first part is easy to see, but the expression in L_n after the \"+\" appears mysterious at this point.\n- Maybe a naive question from someone who does not understand computational complexity well: Why does the computational complexity not depend on n and p?\n- Line 353 \"hierarchical orthogonality\" --> \"hierarchical orthogonal\"\n- Detail \"under the same assumptions *than* Theorem 3\" sounds a bit weird do me. Maybe \"as in Theorem 3\"?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n-------------------\n- Very interesting and important idea.\n- I enjoyed reading the paper, concepts are well explained and the proofs are overall easy to follow.\n- The idea of approximate hirarchical orthogonality is very nice, as is the fact that the Hoeffding decomposition can be estimated relatively efficiently\n- Great Illustrations and Experiments\n\nWeaknesses\n------------------\n- My biggest concern are about details of the formalization: HFD based on Cartesian Tree Partitions are a smart move, but once we think about consistency of the approach, that somehow means to me that there is a limiting partitioning towards we converge, i.e. something like a limiting tree ensemble. I provide more details below, but if I am not wrong about this, I think this needs to be discussed.", "was_revised": true, "final_justification": "I think this is a great paper with an interesting and useful new method, and solid theory. The authors addressed my questions adequately and also replied to my proof questions in details, which was interesting to read. I also see no unresolved issue and I am thus deciding to leave my score.", "rebuttal": "Thank you for your positive comments, and for taking the time to read the proofs. We are glad that you enjoyed reading the article. We will improve the clarity of the settings of the theoretical analysis thanks to your suggestions.\n\n\n**Theorem $7$.** Your comment about Theorem $7$ is highly relevant, and we realize that the settings of the theoretical analysis are not clear enough. In lines 127-129 of the article, we state that the tree ensemble is trained with a realization of the training data of fixed sample size, and that the ensemble predictor $T$ is thus considered as a deterministic function throughout the article. In fact, we mean that $T$ is trained with a set of deterministic points of fixed size (and implicitly with a fixed random seed of the tree randomizations), to obtain a deterministic function T. Then, TreeHFD is fit for $T$ using another data sample, denoted by $\\mathscr{D}_n$, which is a random object, as usually formalized in learning theory.  In other words, all the theoretical results of the article are stated conditional on the training data of $T$ of fixed sample size. In Theorem $7$, we only analyze the limiting decomposition with respect to the size of $\\mathscr{D}_n$, used to fit TreeHFD for a fixed function $T$ (trained with another dataset of fixed size). We do not introduce a notation for the training data of $T$ to simplify the mathematical formulations. However, we will better explain these settings to improve clarity of the theoretical analysis. Thank you for raising this important point. Also notice that in practice, we use the same dataset to train $T$ and to fit TreeHFD in the experiments, as it gives excellent performance, and splitting the data in two parts hurts accuracy. Using two datasets is a mild assumption to alleviate the theoretical analysis.\n\nTo deepen the discussion for Theorem $7$, this result shows that when the size of $\\mathscr{D}_n$ increases, the decomposition generated by TreeHFD converges towards the decomposition of Theorem $2$ for a given tree ensemble $T$, conditional on the training data of $T$ and the randomizations used to fit $T$. As stated in lines 142-145, the main goal of the article is to explain a given tree ensemble. Theorem $7$ is thus strongly valuable to show that the decomposition obtained by TreeHFD is well-defined by Theorem $2$, as the HFD of the function $T$ with a discretization of the orthogonality constraints. A secondary objective of the article is to show that this decomposition is a good approximation of the original HFD of the underlying regression function $m$. Hence, Theorem $6$ gives strong guarantees about the quality of this approximation. Indeed, we show that the $L_2$ error of each component is bounded by the MSE of the original tree ensemble, and the variations of the input distribution $f$ within each cell of the Cartesian tree partitions. This result is also valid conditional on the training data of $T$, and does not depend on $\\mathscr{D}_n$, which is not used at this stage. Then, we can also study the accuracy of the decomposition of Theorem $2$, when the size of the data sample used to train $T$ increases. It is clear that this error converges towards zero, when the tree ensemble is consistent and the variations of $f$ within each cell  goes to zero. This last condition is verified when the diameter of each cell vanishes asymptotically [2], and the distribution $f$ is a Lipschitz function. Furthermore, the cell diameters vanish when tree depth increases with the sample size and the tree splits cannot be performed too close to the edges of cells, as explained in [1, 3]. \n\nFinally, we will augment the analysis of Theorem $6$ in the article with the above discussion to strengthen the theoretical guarantees about the accuracy of TreeHFD. However, we believe that a thorough analysis of the convergence of TreeHFD towards the HFD of the regression function is out of scope of this 9-page article. Indeed, deriving sufficient conditions for the convergence of tree ensembles is a notoriously difficult problem, which is here combined with the convergence of TreeHFD. In particular, the extension of Theorem $7$ when the size of the sample used to train $T$ also increases, is highly non-trivial, and will involve a sharp analysis of the asymptotic regimes of the number of cells in the initial tree partitions and the sizes of the two data samples. We will also have to separately discuss the cases of random forests and boosted ensembles to derive realistic conditions about their training regimes. Therefore, we think that a complete analysis of this convergence deserves a separate paper.\n\n\n**Proof details.** If you consider the right hand side of the first equation line 780, $\\mathbf{x}_0$ is a fixed value, and the integral is computed with respect to $\\mathbf{x}^{(J)}$. Since $f$ only depends on $\\mathbf{x}^{(J \\setminus I)}$, we can separate the variables in the integral, and isolate the integral of $d \\mathbf{x}^{(I)}$ over $A^{(I)}$, which gives the volume of this cell, and we obtain the left hand side. The same trick is used for line 781. We will add a sentence in the proof to explain this better.\n\nThere is a typo in the last line of the proof of Theorem $3$. Thank you for pointing this out. For $\\eta^{(I)}$, we can directly upper bound the term using $||\\eta^{(I)}||$, and the $\\ell$ index is a typo. However, $\\eta^{(J)}$ must be broken down as the sum of $\\eta_{\\ell}^{(J)}$ to use the inequality of line 785, combined with the triangle inequality. Then, the term $\\sum_{\\ell} || \\eta_{\\ell}^{(J)} ||$ appears. This is a small typo in statement (ii) of Theorem $3$, which should be $\\frac{c_2 - c_1}{c_1^2} ||\\eta^{(I)}|| \\big( \\sum_{\\ell} || \\eta_{\\ell}^{(J)} || \\big) \\Delta_{\\mathcal{A}, f}$.\nThis leaves the scope and interpretation of the result untouched, since statement (ii) shows that the gap to hierarchical orthogonality decreases with the variations $\\Delta_{\\mathcal{A}, f}$ of the input distribution within each cell of the Cartesian tree partitions. We will correct this in the revised version of the article. \n\n\n**Computational complexity.** The analysis of TreeHFD complexity is provided in lines 282-287 of the article. In the revised version, we will move this discussion in a separate paragraph with additional details to improve clarity, as also asked by Reviewer Ngv6. More precisely, the first step of TreeHFD is to build the constraint matrix $\\mathbf{C}_n$ from the tree partitions and data sample for each tree. This is done with a linear complexity with respect to the sample size $n$, since we only need to count the number of points falling in each cell of the Cartesian tree partitions. Once this matrix is computed, the computational complexity of the optimization problem only depends on the size of the matrix $\\mathbf{C}_n$, which only depends on the size of the Cartesian tree partitions, and not on the sample $n$ or dimension $p$. For example, if $p$ is very large, the number of variables and interactions involved in the decomposition of a given tree is bounded by the number of nodes in the tree, which only depends on the tree depth. Since the computational complexity is asymptotic, it does not depend on $p$. \n\n\n**Loss $L_n$.** We will further explain the connection between $L_n$ and $L^{\\star}$, especially by referring to the proof of Lemma 6, where all terms are broken down.\n\n\n**Typos.** Thank you for the two typos. We will correct them in the revised article.\n\n\n**References**\n\n[1] Meinshausen, N. (2006). Quantile regression forests. Journal of Machine Learning Research, 7:983–999.\n\n[2] Scornet, E., Biau, G., and Vert, J.-P. (2015). Consistency of random forests. The Annals of Statistics, 43:1716–1741\n\n[3] Wager, S. and Athey, S. (2018). Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113:1228–1242."}]

Author rebuttal:

Meta-review: The paper introduces a new algorithm for decomposing the fits of regression tree ensembles (outputted, e.g., by random crests or XGBoost) into a sum of main effects (i.e., univariate functions) and interaction effects (i.e., bivariate functions). The authors shows that the proposed method enjoys favorable theoretical properties and establish an interesting link to the popular TreeSHAP heuristic. 

All reviewers agreed that the paper was interesting and had the potential to be impactful. They initially sought clarification on several points related to the scalability and computational complexity (iKSO & Ngv6), the need to access internal tree structures, and the relevance/importance of Theorem 7 (Reviewer QYXH). The reviewers and I found the authors' responses satisfactory but would encourage the authors to make the following revisions to the paper:

  1. Include a summary of the discussion with iKSO about the assumptions surrounding the input distribution and complexity
  2. Clarify the setting of Theorem 7.

I additionally suggest including plain-language summaries of all theoretical results. In the current version, theorems often appear without being cross-referenced or discussed in the preceding exposition. Space permitting, some sign-posting would be helpful for readers.
Decision: Accept (poster)