What makes an Ensemble (Un) Interpretable?

• URL: http://arxiv.org/abs/2506.08216v1
• Date: Mon, 09 Jun 2025 20:38:04 GMT
• Title: What makes an Ensemble (Un) Interpretable?
• Authors: Shahaf Bassan, Guy Amir, Meirav Zehavi, Guy Katz,
• Abstract summary: Ensemble models are widely recognized in the ML community for their limited interpretability.<n>Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what makes an ensemble (un)-interpretable.
• Score: 6.760285368641258
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of trees (e.g., boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what particularly makes an ensemble (un)-interpretable, including how fundamental factors like the (1) *number*, (2) *size*, and (3) *type* of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for various ensemble configurations. Our analysis uncovers nuanced complexity patterns influenced by various factors. For example, we demonstrate that under standard complexity assumptions like P$\neq$NP, interpreting ensembles remains intractable even when base models are of constant size. Surprisingly, the complexity changes drastically with the number of base models: small ensembles of decision trees are efficiently interpretable, whereas interpreting ensembles with even a constant number of linear models remains intractable. We believe that our findings provide a more robust foundation for understanding the interpretability of ensembles, emphasizing the benefits of examining it through a computational complexity lens.

Related papers

• Loss-Complexity Landscape and Model Structure Functions [56.01537787608726]
  We develop a framework for dualizing the Kolmogorov structure function $h_x(alpha)$.<n>We establish a mathematical analogy between information-theoretic constructs and statistical mechanics.<n>We explicitly prove the Legendre-Fenchel duality between the structure function and free energy.
  arXiv  Detail & Related papers  (2025-07-17T21:31:45Z)
• Inherently Interpretable Tree Ensemble Learning [7.868733904112288]
  We show that when shallow decision trees are used as base learners, the ensemble learning algorithms can become inherently interpretable. An interpretation algorithm is developed that converts the tree ensemble into the functional ANOVA representation with inherent interpretability. Experiments on simulations and real-world datasets show that our proposed methods offer a better trade-off between model interpretation and predictive performance.
  arXiv  Detail & Related papers  (2024-10-24T18:58:41Z)
• Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation [0.9558392439655016]
  The ability to interpret Machine Learning (ML) models is becoming increasingly essential. Recent work has demonstrated that it is possible to formally assess interpretability by studying the computational complexity of explaining the decisions of various models.
  arXiv  Detail & Related papers  (2024-08-07T17:20:52Z)
• Local vs. Global Interpretability: A Computational Complexity Perspective [0.9558392439655016]
  We use computational complexity theory to assess local and global perspectives of interpreting ML models. Our findings offer insights into both the local and global interpretability of these models. We believe that our findings demonstrate how examining explainability through a computational complexity lens can help us develop a more rigorous grasp of the inherent interpretability of ML models.
  arXiv  Detail & Related papers  (2024-06-05T06:23:49Z)
• What makes Models Compositional? A Theoretical View: With Supplement [60.284698521569936]
  We propose a general neuro-symbolic definition of compositional functions and their compositional complexity. We show how various existing general and special purpose sequence processing models fit this definition and use it to analyze their compositional complexity.
  arXiv  Detail & Related papers  (2024-05-02T20:10:27Z)
• Discovering modular solutions that generalize compositionally [55.46688816816882]
  We show that identification up to linear transformation purely from demonstrations is possible without having to learn an exponential number of module combinations. We further demonstrate empirically that meta-learning from finite data can discover modular policies that generalize compositionally in a number of complex environments.
  arXiv  Detail & Related papers  (2023-12-22T16:33:50Z)
• On the Complexity of Bayesian Generalization [141.21610899086392]
  We consider concept generalization at a large scale in the diverse and natural visual spectrum. We study two modes when the problem space scales up, and the $complexity$ of concepts becomes diverse.
  arXiv  Detail & Related papers  (2022-11-20T17:21:37Z)
• Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set [50.67431815647126]
  Post-hoc global/local feature attribution methods are being progressively employed to understand machine learning models. We show that partial orders of local/global feature importance arise from this methodology. We show that every relation among features present in these partial orders also holds in the rankings provided by existing approaches.
  arXiv  Detail & Related papers  (2021-10-26T02:53:14Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Model Interpretability through the Lens of Computational Complexity [1.6631602844999724]
  We study whether folklore interpretability claims have a correlate in terms of computational complexity theory. We show that both linear and tree-based models are strictly more interpretable than neural networks.
  arXiv  Detail & Related papers  (2020-10-23T09:50:40Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors.
  arXiv  Detail & Related papers  (2020-06-10T01:32:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.