Vis enkel innførsel

dc.contributor.authorWäldchen, Stephan
dc.contributor.authorMacdonald, Jan
dc.contributor.authorHauch, Sascha
dc.contributor.authorKutyniok, Gitta Astrid Hildegard
dc.date.accessioned2022-02-24T13:20:00Z
dc.date.available2022-02-24T13:20:00Z
dc.date.issued2021-01-21
dc.description.abstractFor a d-ary Boolean function Φ: {0, 1}<sup>d</sup> → {0, 1} and an assignment to its variables x = (x<sub>1</sub>, x<sub>2</sub>, . . . , x<sub>d</sub>) we consider the problem of finding those subsets of the variables that are sufficient to determine the function value with a given probability δ. This is motivated by the task of interpreting predictions of binary classifiers described as Boolean circuits, which can be seen as special cases of neural networks. We show that the problem of deciding whether such subsets of relevant variables of limited size k ≤ d exist is complete for the complexity class NP<sub>PP</sub> and thus, generally, unfeasible to solve. We then introduce a variant, in which it suffices to check whether a subset determines the function value with probability at least δ or at most δ − γ for 0 < γ < δ. This promise of a probability gap reduces the complexity to the class NP<sub>BPP</sub>. Finally, we show that finding the minimal set of relevant variables cannot be reasonably approximated, i.e. with an approximation factor d<sub>1</sub>−α for α > 0, by a polynomial time algorithm unless P = NP. This holds even with the promise of a probability gap.en_US
dc.identifier.citationWäldchen, Macdonald, Hauch, Kutyniok. The computational complexity of understanding binary classifier decisions. The journal of artificial intelligence research. 2021;70:351-3987en_US
dc.identifier.cristinIDFRIDAID 1997769
dc.identifier.doi10.1613/JAIR.1.12359
dc.identifier.issn1076-9757
dc.identifier.issn1943-5037
dc.identifier.urihttps://hdl.handle.net/10037/24133
dc.language.isoengen_US
dc.publisherAI Access Foundationen_US
dc.relation.journalThe journal of artificial intelligence research
dc.rights.accessRightsopenAccessen_US
dc.rights.holder©2021 AI Access Foundation. All rights reserved.en_US
dc.titleThe computational complexity of understanding binary classifier decisionsen_US
dc.type.versionpublishedVersionen_US
dc.typeJournal articleen_US
dc.typeTidsskriftartikkelen_US
dc.typePeer revieweden_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel