Model Interpretability through the lens of Computational Complexity
Authors: Pablo Barceló, Mikaël Monet, Jorge Pérez, Bernardo Subercaseaux
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We make a step towards such a notion by studying whether folklore interpretability claims have a correlate in terms of computational complexity theory. Our complexity analysis, however, does not provide a clear-cut difference between linear and tree-based models, as we obtain different results depending on the particular post-hoc explanations considered. Our contributions. We formalize the framework described above (Section 2) and use it to perform a theoretical study of the computational complexity of three important types of explainability queries over three classes of models. |
| Researcher Affiliation | Academia | Pablo Barceló1,4, Mikaël Monet2, Jorge Pérez3,4, Bernardo Subercaseaux3,4 1 Institute for Mathematical and Computational Engineering, PUC-Chile 2 Inria Lille, France 3 Department of Computer Science, Universidad de Chile 4 Millennium Institute for Foundational Research on Data, Chile |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code, nor does it explicitly state that source code for the methodology is available. |
| Open Datasets | No | This is a theoretical paper on computational complexity and does not involve training models on datasets. Therefore, it does not provide concrete access information for a publicly available or open dataset for training. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with dataset splits. Therefore, it does not provide specific dataset split information for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational implementation that would require specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity. It does not describe practical experiments with specific setup details, hyperparameters, or training configurations. |