## AI帮你理解科学

## AI 精读

AI抽取本论文的概要总结

微博一下：

# Model Interpretability through the lens of Computational Complexity

NIPS 2020, (2020)

EI

关键词

摘要

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

代码：

数据：

简介

- Assume a dystopian future in which the increasing number of submissions has forced journal editors to use machine-learning systems for automatically accepting or rejecting papers.
- The authors 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.

重点内容

- Assume a dystopian future in which the increasing number of submissions has forced journal editors to use machine-learning systems for automatically accepting or rejecting papers
- Under standard complexity assumptions, the computational problems associated to our interpretability queries are strictly less complex for free binary decision diagrams (FBDDs) than they are for multilayer perceptrons (MLPs)
- We show that for FBDDs, the queries minimum-change-required and counting-completions can be solved in polynomial time, while for MLPs these queries are, respectively, nondeterministic polynomial time (NP)-complete and #P-complete
- The need for model interpretability in machine learning has been heavily advocated during the last few years, with works covering theoretical and practical issues [3, 19, 23, 26, 27]
- Darwiche and Hirth [8] use variations of the notion of sufficient reason to explore the interpretability of Ordered BDDs (OBDDs)
- The FBDDs that we consider in our work generalize OBDDs, and our results for sufficient reasons over FBDDs can be seen as generalizations of the results in [8]

结果

- The authors instantiate the framework on three important classes of Boolean models and explainability queries, and present the main theorems comparing such models in terms of c-interpretability.
- The authors prove these results where for each query Q and class of models C the authors pinpoint the exact complexity of the problem Q(C).
- Comparing perceptrons and MLPs. the query COUNTCOMPLETIONS is #P-complete for perceptrons, the authors can still show that the complexity goes down to PTIME if the authors assume the weights and biases to be integers given in unary; this is commonly called pseudo-polynomial time.
- This result establishes a difference between perceptrons and MLPs in terms of CC, as this query remains #P-complete for the latter even if weights and biases are given as integers in unary.
- Another difference is established by the fact that COUNTCOMPLETIONS for perceptrons can be efficiently approximated, while this is not the case for MLPs. To present this idea, the authors briefly recall the notion of fully polynomial randomized approximation scheme (FPRAS [21]), which is heavily used to refine the analysis of the complexity of #P-hard problems.
- 5 Parameterized results for MLPs in terms of number of layers In Section 4.1 the authors proved that the query MINIMUMCHANGEREQUIRED is NP-complete for MLPs. a careful inspection of the proof reveals that MCR is already NP-hard for MLPs with only a few layers.
- This is not something specific to MCR: all lower bounds for the queries studied in the paper in terms of MLPs hold for a small, fixed number of layers.
- One of them is the use of a more sophisticated complexity analysis that is not so much focused on the worst case complexity study propose here, but on identifying relevant parameters that characterize more precisely how difficult it is to interpret a particular class of models in practice.

结论

- In order to avoid the difficulties of defining a general notion of interpretability [23], the authors have used explainability queries and their complexity as a formal proxy.
- Even though the notion of complexity-based interpretability gives a precise way to compare models, the results show that it is still dependent on the particular set of queries that one picks.

- Table1: Summary of our complexity results

基金

- Acknowledgments and Disclosure of Funding Barceló and Pérez are funded by Fondecyt grant 1200967

研究对象与分析

papers: 20

3. We only accept 1 out of 20 papers that do not cite any other paper from our own journal. In order to increase your chances next time, please add more references

引用论文

- E. Allender. A note on the power of threshold circuits. In 30th Annual Symposium on Foundations of Computer Science. IEEE, 1989.
- S. Arora and B. Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
- A. B. Arrieta, N. Díaz-Rodríguez, J. D. Ser, A. Bennetot, S. Tabik, A. Barbado, S. Garcia, S. Gil-Lopez, D. Molina, R. Benjamins, R. Chatila, and F. Herrera. Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion, 58:82–115, 2020.
- G. Berbeglia and G. Hahn. Counting feasible solutions of the traveling salesman problem with pickups and deliveries is# P-complete. Discrete Applied Mathematics, 157(11):2541–2547, 2009.
- O. Biran and C. V. Cotton. Explanation and Justification in Machine Learning: A Survey. 2017.
- J. F. Buss and T. Islam. Simplifying the weft hierarchy. Theoretical Computer Science, 351(3):303–313, 2006.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
- A. Darwiche and A. Hirth. On the reasons behind decisions. arXiv preprint arXiv:2002.09284, 2020.
- A. Darwiche and P. Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229–264, 2002.
- F. Doshi-Velez and B. Kim. A Roadmap for a Rigorous Science of Interpretability. CoRR, abs/1702.08608, 2017.
- R. G. Downey and M. R. Fellows. Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM Journal on Computing, 24(4):873–921, Aug. 1995.
- R. G. Downey and M. R. Fellows. Fundamentals of parameterized complexity, volume 4.
- R. G. Downey, M. R. Fellows, and K. W. Regan. Parameterized circuit complexity and the W hierarchy. Theoretical Computer Science, 191(1-2):97–115, Jan. 1998.
- M. Fellows, D. Hermelin, M. Müller, and F. Rosamond. A purely democratic characterization of W[1]. In Parameterized and Exact Computation, pages 103–1Springer Berlin Heidelberg.
- M. R. Fellows, J. Flum, D. Hermelin, M. Müller, and F. A. Rosamond. Combinatorial circuits and the W-hierarchy. 2007.
- J. Flum and M. Grohe. Parameterized complexity theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006.
- M. Goldmann and M. Karpinski. Simulating threshold circuits by majority circuits. SIAM Journal on Computing, 27(1):230–246, 1998.
- P. Gopalan, A. Klivans, R. Meka, D. Štefankovic, S. Vempala, and E. Vigoda. An FPTAS for #knapsack and related counting problems. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 817–826. IEEE, 2011.
- R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi. A survey of methods for explaining black box models. ACM Comput. Surv., 51(5).
- D. Gunning and D. Aha. DARPA’s explainable artificial intelligence (XAI) program. AI Magazine, 40(2):44–58, 2019.
- M. R. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. TCS, 43:169–188, 1986.
- J. A. King. Approximation algorithms for guarding 1.5 dimensional terrains. PhD thesis, 2005.
- Z. C. Lipton. The mythos of model interpretability. Queue, 16(3):31–57, 2018.
- J. Marques-Silva, T. Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. arXiv preprint arXiv:2008.05803, 2020.
- T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence, 267:1–38, Feb. 2019.
- C. Molnar. Interpretable machine learning. 2019. https://christophm.github.io/interpretable-ml-book/.
- W. J. Murdoch, C. Singh, K. Kumbier, R. Abbasi-Asl, and B. Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences, 116(44):22071–22080, 2019.
- T. D. Nguyen, K. E. Kasmarik, and H. A. Abbass. Towards interpretable deep neural networks: An exact transformation to multi-class multivariate decision trees. arXiv, pages arXiv–2003, 2020.
- R. Rizzi and A. I. Tomescu. Faster FPTASes for counting and random generation of Knapsack solutions. Information and Computation, 267:135–144, 2019.
- W. Shi, A. Shih, A. Darwiche, and A. Choi. On tractable representations of binary neural networks. arXiv preprint arXiv:2004.02082, 2020.
- A. Shih, A. Choi, and A. Darwiche. Formal verification of Bayesian network classifiers. In International Conference on Probabilistic Graphical Models, pages 427–438, 2018.
- A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining Bayesian network classifiers. arXiv preprint arXiv:1805.03364, 2018.
- A. Shih, A. Darwiche, and A. Choi. Verifying binarized neural networks by Angluin-style learning. In International Conference on Theory and Applications of Satisfiability Testing, pages 354–370.
- C. Umans. The minimum equivalent DNF problem and shortest implicants. Journal of Computer and System Sciences, 63(4):597–611, 2001.
- I. Wegener. BDDs—design, analysis, complexity, and applications. Discrete Applied Mathematics, 138(1-2):229–251, 2004.
- 1. Create nodes v1,..., vn, where node vi is labeled with φi The node vn will be the root of T, and for 2 ≤ i ≤ n, connect vi to vi−1 with an edge labeled with 1. Node v1 is connected to a leaf labeled true through an edge labeled with 1. We will denote the path created in this step as π.
- 2. For every vertex φi create a decision tree Ti equivalent to the boolean formula
- 2. Add a new output gate that is a binary majority between the old output gate and the node u.
- 3. Replace every small sub-circuit S by its equivalent monotone DNF formula, consisting of one large OR-gate and many large AND-gates.
- 4. Relabel every large OR-gate, of fan-in ≤ 23d created in the previous step to be a majority gate with the same inputs, but to which one wires as well parallel edges from the input node u.
- 5. Relabel every large AND-gate g, of fan-in ≤ 3d, to be a majority gate. If g had edges from gates g1,..., g, then replace each edge coming from a gi by k + 1 parallel edges, and finally, wire (k + 1) − 1 nodes in N to g.
- 2. Add an extra input, that we call v1, to MC. This means that if MC had dimension n, then MC has dimension n + 1. 8Please excuse us for using left superscripts.
- 3. Create nodes v2,..., vt, all having a bias of 0, and for each 1 ≤ i < t, connect node vi to node vi+1 with an edge of weight 1.
- 4. Let r be the root of MC, and let m be its fan-in. We connect node vt to r with an edge of weight m. Moreover, if the bias of r in MC was b, we set it to be b − m in MC.
- 5. Observe that MC is layerized. To make it a valid MLP (where all the neurons of a layer are connected to all the neurons of the adjacent layers), we do as in the proof of Lemma 13 by adding dummy null weights.
- 2. The instance 0n+1 is negative for MC
- 1. Add a new layer with n + 1 input nodes x1,..., xn+1, below what previously was the layer of 2n input nodes x1,..., xn, x1,..., xn.
- 2. For every 1 ≤ i ≤ n, connect input node xi with its corresponding node xi in the second layer, making xi a unary majority, with the same outgoing edges it had as an input node. This enforces xi = xi.
- 3. Create a new root r for the circuit, and let r be a binary majority between the input node xn+1 and the previous root r.
- 4. Replace each previous input node xi by a majority gates mi that has n + 1 − 2k incoming edges from xn+1, and one incoming edge from each xj with j ∈ {i, n + 1}. The outgoing edges are preserved.

标签

评论

数据免责声明

页面数据均来自互联网公开来源、合作出版商和通过AI技术自动分析结果，我们不对页面数据的有效性、准确性、正确性、可靠性、完整性和及时性做出任何承诺和保证。若有疑问，可以通过电子邮件方式联系我们：report@aminer.cn