Loading…
Towards explainable artificial intelligence
interpreting neural network classifiers with probabilistic prime implicants
Wäldchen, Stephan
In this thesis we develop a framework for interpreting the decisions of highly nonlinear classifier functions with a focus on neural networks. Specifically, we formalise the idea of separating the input parameters into relevant and irrelevant ones as an explicit optimisation problem. First, we describe what is generally understood as a relevance map for classifiers and give an overview over the existing methods to produce such maps. We explain how we used relevance maps to detect artefacts in the PASCAL VOC dataset and track the focus of neural agents playing the Atari video games Breakout and Pinball on a human-like level.
Towards a formal definition of relevance maps, we generalise the concept of prime implicants from abductive logic to a probabilistic setting by introducing δ-relevant sets. For a d-ary Boolean function Φ : {0, 1}d → {0, 1} and an assignment to its variables x = (x1 , x2 , . . . , xd ) we consider the problem of finding those subsets of the variables that are sufficient to determine the function output with a given probability δ. We show that the problem of finding small δ-relevant sets is NP-hard to approximate with a factor d1−α for α > 0. The associated decision problem turns out to be NPPP-complete.
We further generalise δ-relevant sets from the binary to the continuous domain. This leads naturally to a rate-distortion trade-off between the size of the δ-relevant set (rate) and the change in the classifier prediction (distortion). Relevance maps can then be interpreted as greedy approximations of the rate-distortion function. Evaluating this function even approximately turns out to be NP-hard, so we develop a heuristic solution strategy based convex relaxation of the combinatorial problem and assumed density filtering (ADF) for deep ReLU neural networks. This results in our own explanation method which we call Rate-Distortion Explanations (RDE).
To show that the approximations in ADF are necessary, we give a complete characterisation of families of probability distributions that are invariant under the action of ReLU neural network layers. We demonstrate that the only invariant families are either degenerate or amount to sampling. Subsequently, we propose and discuss several benchmark tests and numerical evaluation methods for relevance maps. We compare RDE to a representative collection of established relevance methods and demonstrate that it outperforms competitors for a wide range of tasks.
Finally, we discuss how the knowledge of the true data distribution is crucial for any existing explanation method. We criticise our own method over potential artefacts and introduce a stronger, information theoretical requirement based on the conditional entropy. A novel approach, called Arthur-Merlin-regularisation along with a new framework is developed. The framework is then extended to realistic algorithms and data sets, and we discuss under which assumptions the guarantees still hold.
In dieser Arbeit entwickeln wir ein Framework für die Interpretation der Entscheidungen hochgradig nichtlinearer Klassifizierungsfunktionen mit Schwerpunkt auf neuronalen Netzen. Insbesondere formalisieren wir die Idee der Trennung der Eingabeparameter in relevante und irrelevante Parameter als explizites Optimierungsproblem. Zunächst beschreiben wir, was man allgemein unter einer Relevanzkarte für Klassifikatoren versteht, und geben einen Überblick über die bestehenden Methoden zur Erstellung solcher Karten. Wir erläutern, wie wir Relevanzkarten verwendet haben, um Artefakte im PASCAL-VOC-Datensatz zu finden und um den Fokus neuronaler Agenten beim Spielen der Atari-Videospiele Breakout und Pinball auf einer menschenähnlichen Ebene zu verfolgen.
Auf dem Weg zu einer formalen Definition von Relevanzkarten verallgemeinern wir das Konzept der primären Implikanten aus der abduktiven Logik auf eine probabilistische Umgebung, indem wir δ-relevante Mengen einführen. Für eine d-äre boolesche Funktion Φ : {0, 1}d → {0, 1} und eine Zuordnung zu ihren Variablen x = (x1 , x2 , . . . , xd ) betrachten wir das Problem, diejenigen Teilmengen der Variablen zu finden, die ausreichen, um die Funktionsausgabe mit einer gegebenen Wahrscheinlichkeit δ zu bestimmen. Wir zeigen, dass das Problem, kleine δ-relevante Mengen zu finden, NP-schwer mit einem Faktor d1−α für α > 0 zu approximieren ist. Das zugehörige Entscheidungsproblem erweist sich als NPPP-vollständig. Wir verallgemeinern ferner δ-relevante Mengen von der binären zur kontinuierlichen Domäne. Dies führt auf natürliche Art zu einem Raten-Verzerrungs-Kompromiss zwischen der Größe der δ-relevanten Menge (Rate) und der Veränderung der Klassifikation (Verzerrung).
Relevanzkarten können dann als gierige Approximationen der Raten-Verzerrungs-Funktion interpretiert werden. Diese Funktion auch nur approximativ zu evaluieren ist NP-schwer, daher entwickeln wir eine heuristische Lösungsstrategie, die auf einer konvexen Relaxation des kombinatorischen Problems und dem Assumed Density Filtering (ADF) für tiefe neuronale ReLU-Netze basiert. Dies führt zu unserer eigenen Erklärungsmethode, die wir Rate-Distortion Explanations (RDE) nennen. Um zu zeigen, dass die Näherungen in ADF notwendig sind, geben wir eine vollständige Charakterisierung von Familien von Wahrscheinlichkeitsverteilungen an, die unter ReLU neuronalen Netzwerkschichten invariant sind. Wir zeigen, dass die einzigen invarianten Familien entweder degeneriert sind oder auf Stichproben hinauslaufen.
Anschließend schlagen wir mehrere Benchmark-Tests und numerische Bewertungsmethoden für Relevanzkarten vor und diskutieren sie. Wir vergleichen die RDE mit einer repräsentativen Auswahl etablierter Relevanzmethoden und zeigen, dass sie bei einer Vielzahl von Aufgaben besser abschneidet als die Konkurrenz. Schließlich erörtern wir, warum die Kenntnis der wahren Datenverteilung für jede bestehende Erklärungsmethode entscheidend ist. Wir kritisieren unseren eigenen Ansatz wegen möglicher Artefakte und führen eine stärkere informationstheoretische Anforderung ein, die auf der bedingten Entropie basiert. Es wird ein neuer Ansatz, die Arthur-Merlin-Regularisierung, zusammen mit einem neuen Framework entwickelt. Das Framework wird dann auf realistische Algorithmen und Datensätze ausgeweitet, und wir diskutieren, unter welchen Annahmen die Garantien noch gelten.
