Model Interpretability through the Lens of Computational Complexity

被引:0
|
作者
Barcelo, Pablo [1 ,4 ]
Monet, Mikael [2 ]
Perez, Jorge [3 ,4 ]
Subercaseaux, Bernardo [3 ,4 ]
机构
[1] PUC Chile, Inst Math & Computat Engn, Santiago, Chile
[2] Inria Lille, Lille, France
[3] Univ Chile, Dept Comp Sci, Santiago, Chile
[4] Fdn Res Data, Millennium Inst, Santiago, Chile
来源
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 33, NEURIPS 2020 | 2020年 / 33卷
关键词
KNAPSACK;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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 folk-lore 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 C-1 of models is more interpretable than another class C-2, if the computational complexity of answering post-hoc queries for models in C-2 is higher than for those in 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 not equal 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.
引用
收藏
页数:12
相关论文
empty
未找到相关数据