## Model Interpretability through the Lens ...

Document type :

Communication dans un congrès avec actes

Permalink :

Title :

Model Interpretability through the Lens of Computational Complexity

Author(s) :

Barceló, Pablo [Auteur]

Monet, Mikaël [Auteur]

Linking Dynamic Data [LINKS]

Perez, Jorge [Auteur]

Department of Computer Science [Universidad de Chile]

Subercaseaux, Bernardo [Auteur]

Department of Computer Science [Universidad de Chile]

Monet, Mikaël [Auteur]

Linking Dynamic Data [LINKS]

Perez, Jorge [Auteur]

Department of Computer Science [Universidad de Chile]

Subercaseaux, Bernardo [Auteur]

Department of Computer Science [Universidad de Chile]

Conference title :

NeurIPS 2020

City :

Held online

Country :

Etats-Unis d'Amérique

Start date of the conference :

2020-12-07

HAL domain(s) :

Informatique [cs]

Informatique [cs]/Intelligence artificielle [cs.AI]

Informatique [cs]/Complexité [cs.CC]

Informatique [cs]/Intelligence artificielle [cs.AI]

Informatique [cs]/Complexité [cs.CC]

English abstract : [en]

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 ...

Show more >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.Show less >

Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Comment :

36 pages, including 9 pages of main text. This is the author version of the NeurIPS'2020 paper. Except from minor differences that could be introduced by the publisher, the only difference should be the addition of the appendix, which contains all the proofs that do not appear in the main text

Collections :

Source :

Submission date :

2021-11-14T02:07:08Z

##### Files

- https://hal.inria.fr/hal-03052508/document
- Open access
- Access the document

- http://arxiv.org/pdf/2010.12265
- Open access
- Access the document