On the (un) interpretability of Ensembles: A Computational Analysis

Authors: Shahaf Bassan, Guy Amir, Meirav Zehavi, Guy Katz
Primary area: interpretability and explainable AI
Keywords: explainable AI, XAI, explainability

Abstract:
Despite the widespread adoption of ensemble models, it is widely acknowledged within the ML community that they offer limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of decision trees (e.g., boosted-trees) are usually regarded as black-boxes. Although this reduced interpretability is widely acknowledged, the topic has received only limited attention from a theoretical and mathematical viewpoint.  In this work, we provide an elaborate analysis of the interpretability of ensemble models through the lens of *computational complexity* theory. In a nutshell, we explore different forms of explanations, and analyze whether obtaining explanations for ensembles is strictly computationally less tractable than for their constituent base models. We show that this is indeed the case for ensembles that consist of interpretable models, such as decision trees or linear models; but this is not the case for ensembles consisting of more complex models, such as neural networks. Next, we perform a fine-grained analysis using parameterized complexity to measure the impact of different problem parameters on an ensemble's interpretability. Our findings reveal that even if we shrink the *size* of all base models in an ensemble substantially, the ensemble as a whole remains intractable to interpret. However, an analysis of the *number* of base models yields a surprising dynamic --- while ensembles consisting of a limited number of decision trees can be interpreted efficiently, ensembles that consist of a small (even *constant*) number of linear models are computationally intractable to interpret.

Decision: reject
Reviewer scores: 3, 8, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730459384162

thread_type:
official_review

<thread_object>
creator: reviewer_dqgk

<content>
summary:
The paper studies the computational complexity of computing explanations of ensembles.

strengths:
The paper is mostly well written and easy to follow even if you do not have a strong background in computational complexity theory -- the last time I had to deal with this was when I was a student. Given that, I would not consider myself as an expert in this area -- i.e. you should take all my comments with a pinch of salt.

However, checking the proofs for correctness is beyond my level of expertise.

weaknesses:
Given that the paper is purely theoretical, I think it would be nice to highlight the consequences/recommendations for practitioners—e.g., limiting the number of models or the size of the base models, etc. Also, I would be interested in having an algorithm (even a naive one) that can be applied to ensembles for which the stated properties are fulfilled—although this might be too much for a conference paper.


Minor:
"while ensembles consisting of a limited number of decision trees can be interpreted efficiently, ensembles that consist of a small (even constant) number of linear models are computationally intractable to interpret" -- when first reading this (abstract) I had trouble understanding the difference between "limited number" vs. "small". Eventually it became clear throughout the paper -- I think rephrasing this statement would make it more clear for the average reader (e.g. "... , but limiting the number of linear models does not make the problem tractable" or smth. similar).

questions:
What do you consider the major takeaway or recommendation for practitioners?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730462391225

thread_type:
official_review

<thread_object>
creator: reviewer_h6p8

<content>
summary:
The paper provides an analysis of the computational complexity of ensemble models’ interpretability. The authors investigate whether explaining ensemble models is inherently more computationally demanding than explaining individual models. The authors find that explaining ensembles made of interpretable base models, e.g., decision trees, is computationally more expensive than the base models. However, there is no gap in the computational complexity between explaining expressive, uninterpretable models, e.g., neural networks, and their ensembles.

The paper also studies the parameterized complexity of explaining ensembles, examining how specific factors, e.g., the size or the number of base models, affect interpretability. The results show that reducing the size of the base models in the ensemble does not make the ensemble interpretable. The effect of the number of base models on the interpretability depends on their type, i.e., linear models or decision trees. Ensembles with a small number of decision trees can be interpreted efficiently, while a small number of linear models in an ensemble makes it computationally intractable to interpret.

strengths:
1- The manuscript provides original work based on a theoretical foundation.

2- The paper shows differences between linear model ensembles and decision tree ensembles in parameterized complexity results, which reveals that not all ensembles are equally hard to interpret.

weaknesses:
1- The paper’s contribution is marginal and provides evidence for the already-known un-interpretability of ensemble models, as the authors mention in line 530: “Our work provides mathematical evidence for the folklore belief: “ensembles are not interpretable”.” However, the paper succeeds in showing that not all ensembles are equally hard to interpret.

2- The paper lacks motivation for the targeted problem and why the contribution can be significant. It can be helpful if the introduction is expanded to include examples of how the findings can impact research or practice in explainable AI.

3- The authors claim that the main focus of the paper was on understanding the complexity of ensemble models and their impact on model interpretability. However, the explanations of the compared models were not evaluated or compared using explainability-related metrics, e.g., fidelity, robustness, or using a user-based evaluation. Therefore, it can be helpful to clarify explicitly that the focus is on the theoretical computational complexity of explanations, not an evaluation of interpretability in general.

questions:
Why can the findings of this work be significant to researchers in the domain of interpretability and explainable AI if the findings are already “folklore belief”?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714426709

thread_type:
official_review

<thread_object>
creator: reviewer_42bg

<content>
summary:
The paper theoretically studies the class of ensemble models from an interpretability perspective. Specifically, the paper discusses the computational complexity associated with different kinds of "interpretability queries" (i.e. SHAP, counterfactuals) and different kind of ensemble models (deep ensembles, tree ensembles, etc.). The paper finds evidence that ensembles are in fact less interpretable than base models. This is substantiated by an extensive list of theoretical results.

strengths:
- The subject matter is an important research area within machine learning, making this research highly relevant. The focus aligns well with ongoing discussions and research questions (TreeSHAP + Tree vs. TreeSHAP + Forest). The paper adds a good contribution to explainability and theoretical foundations in AI. 
- A clear strengths of this paper are the theoretical contributions, of which there are many. While I have problems with the presentation of the results, they are very interesting and like the authors say "give theoretical merit to the folklore saying that ensembles are less interpretable than base models". I do very much like the paper because of this. I particularly like the additional results for the decision tree classes (FBDDs) and the non-SHAP related explanation queries.
- All in all, while the paper is very technical, the writing is strong and precise.

weaknesses:
- **The paper is too technical**, which could lead to the ICLR audience might missing the core contributions. It contains many acronyms that are not generally known, making it difficult for readers to follow along. Furthermore, one theoretical result follows another without putting the results well into context or grounding it. At the moment the paper contains 8 Theorems and 8 propositions making it 16 theoretical results on 6 pages. Lines 246-258 are just a proof sketch right where the central part of the paper could be. This may hinder the audience from fully appreciating the significance and implications of each result within the broader field. The appendix is quite long (44 pages give or take) and contains a lot of details missing in the main text. This reinforces the impression that the contribution may not be well suited to a conference paper and would maybe better fit a journal like JMLR.
- While the paper is sound and provides a plethora of proofs, I am **missing** some **empirical validation** or at least **illustrative examples**. The work stays very abstract. I acknowledge that computational complexity results do not necessarily need "experiments", however they do help a lot in grounding the theoretical results for practitioners or uncover edge cases.
- The paper does not contain a limitations section.

questions:
- How can you make the paper more approachable provided an additional page?
- I highly suggest, you move technical proof sketches out of the main paper and put the results better into context and tell the reader why result X is meaningful for model class B. You may further streamline the paper by moving more minor results into the appendix all together.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721165071

thread_type:
official_review

<thread_object>
creator: reviewer_guue

<content>
summary:
The paper presents an expanded framework for analyzing the complexity of interpreting ensemble models in comparison to their constituent base models and to each other. The authors investigate three broad categories of base models—FBDDs (generalized trees), linear models, and multilayer perceptrons (MLPs)—alongside three families of interpretability metrics (referred to as 'explainability queries'): Sufficient Reasons, Contrastive Reasons, and SHAP values. This framework encompasses a wide range of interpretability approaches commonly used in machine learning. The authors provide an in-depth computational analysis of interpretability for these models, demonstrating that the computational costs differ significantly when comparing base models with ensembles, particularly in the cases of linear models and tree ensembles.

To extend this analysis, the authors apply parameterized complexity techniques to explore how model size and the number of base models affect the computational complexity. One key insight from this parametric perspective is that, while increasing the number of models in a linear model ensemble does not impact interpretability tractability, limiting the number of trees in a tree ensemble can render interpretation computationally feasible.

strengths:
* The authors offer a well-rounded perspective that reflects a wide range of approaches used in the field. They introduce a comprehensive and formal framework for analysing interpretability complexity across different model types and interpretability metrics.
 This makes the work broadly applicable and useful for various ML subfields, especially formal analysis on interpretability methods.
* The use of parameterized complexity to analyze the effect of model size and the number of base models adds depth to the analysis. This aspect of the work allows for a nuanced view of interpretability that reveals under what conditions interpretability is tractable, which is particularly innovative and sheds more insight on formal complexity of interpretability in ensembles of different classes.
* The paper is well-structured, coherent, and logically organized. The authors thoughtfully delegate details to Appendices, where they provide comprehensive and easy to follow proofs. Furthermore, including proof sketches in the main text is an excellent choice, as it allows readers to understand the core ideas without extensive back-and-forth with the Appendices.

weaknesses:
While there are no major weaknesses in the scope, there is always room for expansion. For instance, discussing the interpretability of regression models versus classifiers more extensively, exploring continuous domains and fundamental differences (which is actaully touched on in an Appendix), and extending metrics to observational SHAP and other interpretability metrics. However, the current scope is already comprehensive, and these suggestions could serve as directions for future work. To be fair, extending it in any above-mentioned directions could end up costing the clarity.

questions:
Given the assumption of feature independence for Shap values, is the work still includes methods like interventional TreeSHAP, which are proved to be computing SHAP values under the same assumption [1], while leveraging the tree structures in the ensemble rather than computing the intractable original SHAP formula? Is such methods that are computing exact SHAP values not directly from the original SHAP formula something to be considered in your work?

[1] Laberge, Gabriel, and Yann Pequignot. "Understanding interventional treeshap: How and why it works." arXiv preprint arXiv:2209.15123 (2022).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730754233570

thread_type:
official_review

<thread_object>
creator: reviewer_24uh

<content>
summary:
Authors develop a theoretical basis for evaluation of the interpretability of different ensembles (voting or weighted-voting) with different base models: linear, decision tree and neural network. Authors examine computational complexity of deriving different types of the explanations for ensembles and compare them to single base learners, and provide mathematical guarantees. Authors focus on 3 types of explainability: Sufficient Reason Feature Selection (SRFS), Contrastive Explanations (CF), Shapley Value Feature Attributions (SVFA). Authors analyze a parametrized complexity to show how different parameters such as base-model size, number of base learners affect ensemble interpretability.

strengths:
- The paper provides computational complexity analysis for ensembles of different type of base models with mathematical guarantees (and proofs).
- Authors reviewed different explainability queries

weaknesses:
- Besides mathematical proofs and guarantees, the contribution of the paper is very questionable. The conclusions authors made are well-known. For example, weighted voting of neural networks can be expressed as a bigger neural network with another linear layer, which is still a neural network, therefore, complexity gap should not be high (if any). Similarly, ensembles with a constant number of linear models can be shown (for specific ensemble type) as a neural network of two layers with non-linear activation (for classification), which is for interpretable.
- In my opinion, the most interesting part of the paper is hidden in the appendix part and needs restructuring.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1731472861218

thread_type:
official_comment

<thread_object>
creator: area_chair_ehqb

<content>
title:
authors - reviewers discussion open until November 26 at 11:59pm AoE

comment:
Dear authors & reviewers,

The reviews for the paper should be now visible to both authors and reviewers. The discussion is open until November 26 at 11:59pm AoE.

Your AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1732019428420

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of the rebuttal phase

comment:
We thank the reviewers once again for their insightful feedback and for recognizing the significance of our work.

Due to the many discussions, we will provide a short overview on the author-reviewer discussions -

1. 3 out of 5 reviewers (GUuE, 42Bg, and dQgK) provided positive feedback on the paper, with scores of 8, 6, and 6, respectively. Reviewer dQgK (score: 6) expressed openness to increasing their score. Reviewer 42Bg (score: 6) indicated that addressing certain accessibility concerns in a revised manuscript could lead to a higher score. We incorporated most of these suggested changes into the manuscript. However, the reviewer has not yet responded to the updated submission.

2. Reviewer 24uH initially assigned a score of "3", citing two concerns that we addressed in our rebuttal. As a result, the reviewer raised their score to a "6". However, on the last day of the (original) rebuttal period, the reviewer raised a new set of concerns and reverted the score back to "3". *We believe we have effectively addressed these issues.* For example, a key concern about the applicability of our results to continuous domains was resolved when we clarified that our findings are indeed relevant to such domains. The reviewer has not yet responded to these points following our rebuttal.



3. Finally, reviewer h6P8 initially questioned the significance of studying ensemble (un)-interpretability. We responded with a detailed explanation of its importance, addressing overlooked aspects of the folklore claim that our computational complexity framework can address, as well as important practical implications relevant to explainable AI. This led the reviewer to raise their score.




Overall, while all reviewers acknowledged the significance of the theoretical aspects of our work, a primary pertaining concern is our paper’s accessibility. During the rebuttal period, we made significant revisions to address this concern and are committed to incorporating further adjustments, as outlined in individual threads, in the final version.


We sincerely appreciate the reviewers' detailed and valuable feedback, which has helped us improve our work!
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper provides an analysis of the interpretability of ensemble models from a computational point of view. In general, the reviewers found the paper hard to understand, more like a summary of a longer journal paper. There were several important reasons mentioned by one or more reviewers not to accept the paper: a narrow focus in the way the problem is set up, that may not be of general interest; little novelty in the main results; and little impact in what is new, at least concerning practical impact in interpretability and explainable AI.