License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.21
URN: urn:nbn:de:0030-drops-153125
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15312/
Go to the corresponding LIPIcs Volume Portal

Cooper, Martin C. ; Marques-Silva, João

On the Tractability of Explaining Decisions of Classifiers

pdf-format:
LIPIcs-CP-2021-21.pdf (0.8 MB)

Abstract

Explaining decisions is at the heart of explainable AI. We investigate the computational complexity of providing a formally-correct and minimal explanation of a decision taken by a classifier. In the case of threshold (i.e. score-based) classifiers, we show that a complexity dichotomy follows from the complexity dichotomy for languages of cost functions. In particular, submodular classifiers allow tractable explanation of positive decisions, but not negative decisions (assuming P≠NP). This is an example of the possible asymmetry between the complexity of explaining positive and negative decisions of a particular classifier. Nevertheless, there are large families of classifiers for which explaining both positive and negative decisions is tractable, such as monotone or linear classifiers. We extend tractable cases to constrained classifiers (when there are constraints on the possible input vectors) and to the search for contrastive rather than abductive explanations. Indeed, we show that tractable classes coincide for abductive and contrastive explanations in the constrained or unconstrained settings.

BibTeX - Entry

@InProceedings{cooper_et_al:LIPIcs.CP.2021.21,
  author =	{Cooper, Martin C. and Marques-Silva, Jo\~{a}o},
  title =	{{On the Tractability of Explaining Decisions of Classifiers}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15312},
  URN =		{urn:nbn:de:0030-drops-153125},
  doi =		{10.4230/LIPIcs.CP.2021.21},
  annote =	{Keywords: machine learning, tractability, explanations, weighted constraint satisfaction}
}

Keywords: machine learning, tractability, explanations, weighted constraint satisfaction
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI