What makes an Ensemble (Un) Interpretable?
Authors: Shahaf Bassan, Guy Amir, Meirav Zehavi, Guy Katz
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 = 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. |
| Researcher Affiliation | Academia | 1The Hebrew University of Jerueslaem 2Cornell University 3Ben-Gurion University of the Negev. Correspondence to: Shahaf Bassan <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Computing HDP (S, k) Input f, x, S, k ... Algorithm 2 Greedy Subset Minimal Sufficient Reason Search Input f, x |
| Open Source Code | No | The text is ambiguous or lacks a clear, affirmative statement of release regarding the authors' own implementation code. While it mentions third-party libraries and solvers, it does not state that their specific methodology's code is publicly available. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity, assuming Boolean inputs and outputs for clarity. It does not conduct experiments on datasets or provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets, therefore no dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity, therefore no specific hardware details are mentioned for experimental setup. |
| Software Dependencies | No | The paper discusses various tools and concepts like SAT solvers, MILP, SMT, and SHAP library in the context of related work and theoretical frameworks, but does not specify software dependencies with version numbers for their own methodology or experimental setup. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity, therefore no experimental setup details like hyperparameters or training configurations are mentioned. |