The computational complexity of understanding binary classifier decisions

DOI10.1613/JAIR.1.12359MaRDI QIDQ5856459zbMATH OpenOpenAlexFDO

Authors Stephan Wäldchen, Jan Macdonald, Sascha Hauch, Gitta Kutyniok

Publication date 26 March 2021

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.09163

zbMATH Keywords

machine learningneural networkssatisfiabilityprobabilistic reasoning

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Recommendations

• On the reasons behind decisions
• Probabilistic learning and Boolean functions
• Computational limitations on learning from examples
• The hardness of the expected decision depth problem
• Learning functions of \(k\) relevant variables

Cites work

• scientific article; zbMATH DE number 1216123 (Why is no real title available?)
• scientific article; zbMATH DE number 500950 (Why is no real title available?)
• scientific article; zbMATH DE number 872005 (Why is no real title available?)
• scientific article; zbMATH DE number 3078997 (Why is no real title available?)
• A linear approximation method for the Shapley value
• An efficient explanation of individual classifications using game theory
• Assessing heuristic machine learning explanations with model counting
• Binary Decision Diagrams
• Consequence finding algorithms
• Deep learning
• Geometric algorithms and combinatorial optimization
• Graph-Based Algorithms for Boolean Function Manipulation
• Neocognition: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position
• Neural networks and deep learning. A textbook
• On the Complexity of Cooperative Solution Concepts
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Stochastic Boolean satisfiability
• The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
• The complexity of logic-based abduction
• The computational complexity of understanding binary classifier decisions

Cited in

(15)

• On computing probabilistic abductive explanations
• The computational complexity of understanding binary classifier decisions
• On the reasons behind decisions
• On the failings of Shapley values for explainability
• Towards formal XAI: formally approximate minimal explanations of neural networks
• scientific article; zbMATH DE number 1946851 (Why is no real title available?)
• On Tackling Explanation Redundancy in Decision Trees
• Tractability of explaining classifier decisions
• The mathematics of artificial intelligence
• Formal explanations of black-box ranking functions
• A uniform language for safety, robustness and explainability
• Logic explained networks
• On computing probabilistic explanations for decision trees
• Feature necessity \& relevancy in ML classifier explanations
• Classification of binary vectors by stochastic complexity.

Describes a project that uses

Uses Software

• DeepPose
• AlexNet
• DeepFace
• ImageNet

This page was built for publication: The computational complexity of understanding binary classifier decisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856459)