The Computational Complexity of Understanding Binary Classifier Decisions

Wäldchen, Stephan; Macdonald, Jan; Hauch, Sascha and Kutyniok, Gitta (2021): The Computational Complexity of Understanding Binary Classifier Decisions. In: Journal of Artificial Intelligence Research, Vol. 70: pp. 351-387

Abstract

For a d-ary Boolean function Phi: {0, 1}(d) -> {0, 1} and an assignment to its variables x = (x(1), x(2) , . , x(d)) we consider the problem of finding those subsets of the variables that are sufficient to determine the function value with a given probability delta. 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 NPPP 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 delta or at most delta - gamma for 0 < gamma < delta. This promise of a probability gap reduces the complexity to the class NPBPP. Finally, we show that finding the minimal set of relevant variables cannot be reasonably approximated, i.e. with an approximation factor d(1-alpha) for alpha > 0, by a polynomial time algorithm unless P = NP. This holds even with the promise of a probability gap.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 1076-9757
• Language: English