Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithm

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.

The Hoeffding functional decomposition (HFD) breaks down a regression function into a 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 Hoeffding (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 it 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., 2019), and often leads to sparse decompositions essentially involving main effects and second-order interactions, which are intrinsically transparent. Later, Chastaing et al. (2012) and Idrissi et al. (2025) extended the validity of the decomposition for unbounded supports of the input distribution. Unfortunately, the practical estimation of the Hoeffding decomposition is a notoriously difficult problem (Hooker, 2007;Chastaing et al., 2012), and consequently, the HFD has long remained an abstract theoretical tool. Recently, Lengerich 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) is a fast algorithm to compute Shapley values for tree ensembles, and is implemented in the highly popular xgboost package. Recently, Herren and Hahn (2022), 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 are required to recover tractable algorithms, such as TreeSHAP 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 TreeHFD algorithm to precisely estimate the Hoeffding decomposition of a tree ensemble, when only a data sample is 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