Model Interpretability through the Lens of Computational Complexity

• URL: http://arxiv.org/abs/2010.12265v2
• Date: Thu, 12 Nov 2020 21:57:06 GMT
• Title: Model Interpretability through the Lens of Computational Complexity
• Authors: Pablo Barcel\'o, Mika\"el Monet, Jorge P\'erez, Bernardo Subercaseaux
• Abstract summary: 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.
• Score: 1.6631602844999724
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In spite of several claims stating that some models are more interpretable than others -- e.g., "linear models are more interpretable than deep neural networks" -- we still lack a principled notion of interpretability to formally compare among different classes of models. We make a step towards such a notion by studying whether folklore interpretability claims have a correlate in terms of computational complexity theory. We focus on local post-hoc explainability queries that, intuitively, attempt to answer why individual inputs are classified in a certain way by a given model. In a nutshell, we say that a class $\mathcal{C}_1$ of models is more interpretable than another class $\mathcal{C}_2$, if the computational complexity of answering post-hoc queries for models in $\mathcal{C}_2$ is higher than for those in $\mathcal{C}_1$. We prove that this notion provides a good theoretical counterpart to current beliefs on the interpretability of models; in particular, we show that under our definition and assuming standard complexity-theoretical assumptions (such as P$\neq$NP), both linear and tree-based models are strictly more interpretable than neural networks. 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. Finally, by applying a finer complexity analysis based on parameterized complexity, we are able to prove a theoretical result suggesting that shallow neural networks are more interpretable than deeper ones.

Related papers

• 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)
• Are Linear Regression Models White Box and Interpretable? [0.0]
  Explainable artificial intelligence (XAI) is a set of tools and algorithms that applied or embedded to machine learning models to understand and interpret the models. Simple models including linear regression are easy to implement, has less computational complexity and easy to visualize the output.
  arXiv  Detail & Related papers  (2024-07-16T21:05:51Z)
• Towards Compositional Interpretability for XAI [3.3768167170511587]
  We present an approach to defining AI models and their interpretability based on category theory. We compare a wide range of AI models as compositional models. We find that what makes the standard 'intrinsically interpretable' models so transparent is brought out most clearly diagrammatically.
  arXiv  Detail & Related papers  (2024-06-25T14:27:03Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• Even-if Explanations: Formal Foundations, Priorities and Complexity [18.126159829450028]
  We show that both linear and tree-based models are strictly more interpretable than neural networks. We introduce a preference-based framework that enables users to personalize explanations based on their preferences.
  arXiv  Detail & Related papers  (2024-01-17T11:38:58Z)
• Algebraic Models for Qualified Aggregation in General Rough Sets, and Reasoning Bias Discovery [0.0]
  The research is motivated by the desire to model skeptical or pessimistic, and optimistic or possibilistic aggregation in human reasoning. The model is suitable for the study of discriminatory/toxic behavior in human reasoning, and of ML algorithms learning such behavior.
  arXiv  Detail & Related papers  (2023-08-30T17:07:54Z)
• Discovering Invariant Rationales for Graph Neural Networks [104.61908788639052]
  Intrinsic interpretability of graph neural networks (GNNs) is to find a small subset of the input graph's features. We propose a new strategy of discovering invariant rationale (DIR) to construct intrinsically interpretable GNNs.
  arXiv  Detail & Related papers  (2022-01-30T16:43:40Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Rationales for Sequential Predictions [117.93025782838123]
  Sequence models are a critical component of modern NLP systems, but their predictions are difficult to explain. We consider model explanations though rationales, subsets of context that can explain individual model predictions. We propose an efficient greedy algorithm to approximate this objective.
  arXiv  Detail & Related papers  (2021-09-14T01:25:15Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Model-agnostic multi-objective approach for the evolutionary discovery of mathematical models [55.41644538483948]
  In modern data science, it is more interesting to understand the properties of the model, which parts could be replaced to obtain better results. We use multi-objective evolutionary optimization for composite data-driven model learning to obtain the algorithm's desired properties.
  arXiv  Detail & Related papers  (2021-07-07T11:17:09Z)

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.