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

We appreciate the reviewer's insightful comments and have provided our responses below.

What are the major takeaways and recommendations for practitioners?

We thank the reviewer for emphasizing the need to better highlight this point, which will enhance the paper’s applicability. We will provide a brief description here, and provide an elaborate discussion of this matter in our final draft. In our response, we will slightly simplify complexity notations by referring to problems like NP-Hard, $\Sigma^P_2$-Hard, etc. as “exponentially hard”. While these classes differ in difficulty, it is widely believed none admit polynomial-time solutions.

(1) When a practitioner attempts to provide explanations over an arbitrary ensemble:

In general terms, before getting into more specific parameterized results, we prove that computing many types of explanations for ensembles is exponential with respect to their size. This is in stark contrast to the ability to provide explanations over (interpretable) base models, where computing explanations is polynomial (usually - linear) with respect to their size. This fundamentally shows a strict difference between ensembles and their base models and provides lower bounds over the capability of generating many types of explanations for ensembles.

For example, this can help a practitioner compare the interpretability of a decision tree with, say, $X$ nodes - where explaining its decisions scales nearly linearly with the number of nodes - with an ensemble of, say, $Y$ decision trees, each having $Z$ nodes, where the runtime grows approximately exponentially with respect to the size of the ensemble. The exponential increase in complexity for ensembles means that the difficulty of interpreting them escalates rapidly, which must be factored in when striving for interpretability.

(2) When a practitioner tries to interpret an ensemble with very small base models:

Since ensembles are exponentially hard to interpret, a practitioner might consider different ways to simplify the ensemble to enhance its interpretability. Our first parameterized result demonstrates that even when the ensemble comprises very small base models (e.g., a tree ensemble consisting of decision trees with just 2-3 nodes), the overall ensemble remains exponentially hard to interpret. This finding indicates that, in practice, reducing the size of the base models does not improve interpretability; the ensemble as a whole continues to exhibit exponential complexity for generating explanations, relative to its size. This is yet another negative finding regarding the interpretability of these models, offering evidence for the challenges or potential infeasibility of explaining decisions in this context.

(3) When a practitioner tries to interpret an ensemble with a small number of trees:

However, if a practitioner seeks to simplify an ensemble by focusing on ensembles with a small number of base models, this approach can indeed enhance the interpretability of the ensemble. We demonstrate that this is particularly true for ensembles composed of decision trees (e.g., XGBoost, Random Forest, etc.). For example, if the practitioner considers an ensemble with a very small number of decision trees, even if the individual trees are arbitrarily large, the interpretability of the ensemble remains polynomial with respect to its size - similar to standalone decision trees. Therefore, this scenario provides a positive interpretability outcome.

(4) When a practitioner tries to interpret an ensemble with only 2 linear models

Unlike the previous result, if the ensemble already contains a fixed number of linear base models (commonly just 2 base models), the overall ensemble immediately becomes exponentially difficult to interpret relative to its size. This emphasizes to practitioners that incorporating linear models into an ensemble leads to rapid loss of interpretability, even with as few as 2 linear models that are incorporated in their ensemble.

Can you provide algorithms for which tractable results are fulfilled?

Yes, while most of our findings highlight negative complexity results, emphasizing fundamental lower bounds (i.e., the lack of polynomial-time algorithms) and demonstrating the challenges of generating explanations in various contexts, we also uncover some positive results. Specifically, we show that diverse types of explanations can be efficiently produced in polynomial time for ensembles when limiting the number of decision trees (for models like XGBoost, random forests, etc.), utilizing polynomial-time algorithms. Although these algorithms are currently described in text within the appendix, we agree that presenting them as pseudo-code would enhance the clarity and accessibility of our work. We will make this adjustment in the final version.

Thank you for your thoughtful comments. We appreciate the review, as it has brought attention to several important points in our work that we believe need further emphasis. We hope our response addresses the concerns raised effectively.

In Q1, we will answer why the core issue of the (un)-interpretability of ensembles is inherently nuanced and multifaceted from a computational view, despite often being regarded as “folklore”. In Q2, we will highlight the practical implications of our work for explainable AI. In Q3, we will discuss how our approach differs from other forms of interpretability.

Q1: Why is mathematically analyzing the (un)-interpretability of ensembles interesting if it is already “folklore”?

While the assertion that "ensembles are not interpretable" is indeed a widely held belief, our analysis approaches this question through the lens of computational complexity. This perspective offers a far more nuanced understanding of the topic, uncovering many unexpected insights that go beyond the conventional folklore argument. Simply claiming that "ensembles are not interpretable" fails to address key aspects regarding the interpretability of ensembles that our computational complexity framework is capable of answering. Some of these questions are:

1. Although ensembles are often considered "less interpretable" than their base models, the precise mathematical nature of this gap remains unclear - are they polynomially harder to interpret, or are they exponentially harder? This is a critical and fundamental question with potentially far-reaching implications. Our results provide an in-depth and nuanced analysis of this issue.

2. How does the interpretability of ensembles vary across different types of explanations? We demonstrate that there can be a significant disparity between explanation types (we analyze 5 different common forms of explanations) - are some explanations harder to obtain than others?

3. How does the interpretability of ensembles vary across different model types, such as decision trees, linear models, and neural networks? Our findings once again highlight the intricate cases of this complexity analysis.

4. How do various attributes of an ensemble influence its interpretability? How does the size of the base models impact interpretability? How does the number of base models affect interpretability? Which is "more interpretable": an ensemble with a few large models or one with many smaller models? Does the answer depend on other factors, such as the type of base models or the explanation method used?

5. The former question also has practical significance and touches on a practitioner's ability to simplify an ensemble to enhance its interpretability. Specifically, if an ensemble (initially uninterpretable) is modified by significantly reducing the size of each base model, does it suddenly become interpretable? Additionally, does reducing the number of base models make the entire ensemble more interpretable? Could the answer to this also depend on the types of base models used and the forms of explanations applied?

Our work addresses these questions, offering a significantly deeper and more detailed mathematical understanding of ensemble interpretability, extending far beyond the initial folklore notion that ensembles are inherently (un)-interpretable. We agree with the reviewer that these aspects, along with the overall contributions of our work, should be more prominently highlighted, and we will incorporate these revisions into the final draft.

Thank you for providing detailed clarifications and responses to the questions raised. After reviewing the authors' responses, I found that some of my concerns were adequately addressed, and several of the arguments presented were convincing. Therefore, I raised the paper's rating. However, I still believe that the paper's contribution offers limited practical implications for researchers in the field of interpretability and explainable AI.

We thank the reviewer for the valuable comments. See our response below.

The main paper includes too many technical results. How can you make the paper more approachable?

We appreciate the reviewers' many suggestions on potential ways to restructure the paper. We agree that the structure of our current draft can be improved to better emphasize the main results and their implications while reducing the focus on technical details. We believe that we can address these adjustments effectively in the final version, especially with the additional page available. Specifically, we plan to:

1. Move proof sketches to the appendix: Following the reviewer’s suggestion, we will instead position our proof sketches at the beginning of each proof in the appendix, and not in the main text. This will preserve the main paper's focus on fundamental ideas, corollaries, and implications, ensuring the overall flow remains unaffected. Essentially, this structure enables readers to choose their level of engagement: they can focus on the main text to understand the key corollaries, review the proof sketches provided at the beginning of each proof in the appendix, or engage fully with proofs for a deeper exploration of the paper's technical details.

2. Reduce the number of corollaries: Some of the corollaries in our paper can be combined together to emphasize one larger point. This can reduce the total number of propositions and corollaries (which, as was highlighted by the reviewer, is quite high) and will leave more space to discuss ideas, examples, and implications.

3. Improve discussion on practical implications: Based on the reviewers' feedback, we will refine our paper to place greater emphasis on discussing the practical implications of our findings. These include both the fundamental lower bounds - such as the lack of polynomial-time algorithms of interpreting ensembles (under standard complexity assumptions), which holds both generally, as well as under even highly simplified configurations like ensembles with constant base-model sizes or a constant number of linear models, as well as the more optimistic complexity results, which demonstrate the feasibility of poly-time computations for generating diverse explanations on ensembles of decision trees when the number of trees is reduced. To underscore these points, we will include specific examples that clearly illustrate our arguments. Based on suggestions from reviewer dQgK, we will also include pseudocode to present some of these results, enhancing their accessibility.

4. Adding illustrative examples: Based on the reviewers' feedback and the additional page allowance, we will include illustrative examples in our work to enhance the applicability of some results. We will specifically achieve this using a running example. For instance, we will provide examples such as an ensemble of decision trees with $X$ models of size $Y$, among others, including ensembles of different types of models (such as containing decision trees, linear models, etc.). In this manner, we will highlight the differences in complexity across various types of explanations in diverse scenarios. This approach will enable us to specify the parameters of the ensembles and demonstrate how they influence complexity across various configurations.

The paper does not contain a limitations section

Although our work does not include a dedicated limitations section, we address various limitations of our framework throughout the main text. These include: (1) the restriction of our framework, like other works in this area, to specific explanation forms and model types, and (2) the potential to extend our approach to various additional settings and domains, many of which are preliminarily discussed in the appendix. In the final draft, we plan to incorporate an explicit limitations section, given the additional page allowance.

We appreciate the reviewer’s detailed and insightful comments. Please find our responses below.

Extension to diverse setting configurations

We agree that exploring additional settings where our results could apply presents compelling directions for future research. As the reviewer noted, we have already touched on some of these topics in the appendices. Importantly, the fundamental nature of sufficient and contrastive explanations does not change in terms of complexity when transitioning from classification to regression, as a subset $S$ can be defined to ensure the prediction remains or changes within a $\delta$ range [1, 2]. However, this is not necessarily the case for SHAP, which indeed warrants further investigation in future studies. We thank the reviewer for highlighting the matter and will make sure to emphasize it further in the final version.

Extension of complexity results for interventional SHAP

We agree with the reviewer’s comment and acknowledge that including a discussion on interventional SHAP will add valuable insights to the final draft. We note that interventional SHAP aligns with conditional expectation SHAP when the feature independence assumption holds [3]. Consequently, the results of our framework apply to this scenario as well. We note that while interventional SHAP was indeed shown to be computationally feasible for diverse tree-based models, this tractability diminishes when moving to classification tasks, unlike in regression settings (see [4,5]). However, our work indeed provides a parameterized extension of this finding, by demonstrating that reducing the number of decision trees that participate in the ensemble - whether in the classification or the regression setting - enables polynomial-time computations of explanations for the ensemble. Since this result holds for SHAP under conditional expectations and assuming the feature independence assumption, it also directly applies to interventional SHAP, due to the intersection of the two definitions in this configuration. We recognize the importance of this observation and will address it in the final version of the paper. Thank you for highlighting this!

[1] Verix: Towards Verified Explainability of Deep Neural Networks (Wu et al., Neurips 2023)

[2] Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation (Izza et al., KR 2024)

[3] The Many Shapley Values for Model Explanation (Sundararajan et al., ICML 2020)

[4] On the Tractability of SHAP Explanations (Van den Broeck et al., JAIR 2022)

[5] Updates on the Complexity of SHAP Scores (Huang et al., IJCAI 2024)

Thank you for your comments. We value the review, as it has provided us with valuable guidance on improving the clarity of our paper and highlighted several important aspects that should indeed be made more explicit. We hope that our response clarifies the concerns that were raised.

A specific concern that was mentioned regarding two different results being considered trivial

The reviewer labels two specific results as trivial: (1) adding a linear layer to a neural network, which shows no complexity gap between neural networks and their ensembles. While this is indeed straightforward (as we explicitly say in the paper), it occupies only a significantly minor part of our proofs (only a few lines), while the bulk of the paper concerns numerous non-trivial cases and highly non-trivial proofs. (2) Reducing ensembles of linear models to neural networks, is claimed to lead to trivial conclusions about interpreting ensembles with a constant number of linear models. We will clarify why this implication does not hold. For our detailed response:

(1) Regarding the first point, it is correct that the lack of a complexity gap between neural networks and ensembles is not surprising, and we did not present it as such; the proof is indeed brief. Your point about adding a linear layer aligns directly with the proof we used, which we explicitly describe in the paper. The reason we emphasize this point is to highlight the contrast between interpretable models, which show a strict complexity gap between individual models and ensembles, and more expressive models, where this gap vanishes, clarifying differences in interpretability behavior. That said, following the reviewers' feedback, we will emphasize this more clearly in the final version.

(2) We respectfully disagree with the reviewer’s second argument but appreciate them raising it, as it allows us to clarify this point further in the final version. While an ensemble of a constant number of linear models can indeed be reduced to a neural network, this does not imply that such ensembles are computationally hard to interpret.

Proving the computational hardness of interpreting an ensemble of a constant number of linear models by leveraging the hardness of interpreting neural networks would (hypothetically) require a reduction in the reverse direction. Specifically, one would need to be able to reduce any neural network to a constant-sized ensemble of linear models. However, this approach is impractical because neural networks are substantially more expressive, and reducing them to an ensemble of linear models would require exponential time and space. This makes such a reduction unachievable within the constraint of a constant number of linear models. This is contrary to the reviewer's suggested reduction. If the implication that was made was valid, we could make the same argument about decision trees and linear models, as they too can be reduced in polynomial time to neural networks. However, this is indeed not the case - providing explanations for these models can be done in polynomial time (and is not computationally hard) - because the reverse reduction does not hold.

Contrary to claims of triviality, our results show that proving that interpreting ensembles of a constant k number of linear models is computationally hard requires highly technical reductions (see, e.g., Lemma 22). Notably, this holds even for a very small k, such as k=2 for most explainability queries, and k=5 for the MSR query, demonstrating that ensembles with as few as 2 linear models can be intractable to interpret. That said, following the reviewer's feedback, we recognize that these points should be clarified more effectively in the revised text, and we will make the necessary updates accordingly.

We thank the reviewer for raising their score to a 6. We hope we have thoroughly addressed all your concerns and would be happy to respond to any further questions.

Dear reviewers,

The authors have provided individual responses to your reviews. Can you acknowledge you have read them, and comment on them as necessary? The discussion will come to a close very soon now:

• Nov 26: Last day for reviewers to ask questions to authors.
• Nov 27: Last day for authors to respond to reviewers.

Your AC