Skip to Main content Skip to Navigation
Conference papers

Model Interpretability through the Lens of Computational Complexity

Pablo Barceló 1 Mikaël Monet 2 Jorge Perez 3, 1 Bernardo Subercaseaux 3, 1
2 LINKS - Linking Dynamic Data
CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189, Inria Lille - Nord Europe
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.
Complete list of metadata
Contributor : Mikaël Monet Connect in order to contact the contributor
Submitted on : Thursday, December 10, 2020 - 4:12:54 PM
Last modification on : Friday, January 21, 2022 - 3:10:05 AM


Files produced by the author(s)


  • HAL Id : hal-03052508, version 1
  • ARXIV : 2010.12265


Pablo Barceló, Mikaël Monet, Jorge Perez, Bernardo Subercaseaux. Model Interpretability through the Lens of Computational Complexity. NeurIPS 2020, Dec 2020, Held online, United States. ⟨hal-03052508⟩



Les métriques sont temporairement indisponibles