Wissen was Sie nicht wissen – Klassifikatoren erlauben Eingabeproben abzulehnen

Viele Klassifikationsalgorithmen weisen jedem Sample (Merkmalsvektor) eine Klasse zu, selbst wenn dieses Sample weit von den Trainingsdaten entfernt ist. Diese Eigenschaft ist für praktische Anwendungen problematisch, insbesondere wenn sie sicherheitskritisch sind. Daher ist es wünschenswert, dass Klassifikationsalgorithmen mit «Ich weiss nicht» bzw. «Unbekannt» für Proben, die den Trainingsdaten nicht ähnlich sind, antworten können. In diesem Artikel werden Methoden zur Erreichung dieses Ziels vorgestellt und anhand eines Spielzeugbeispiels verglichen.

Beispiel

Angenommen, ein Obstunternehmen möchte eine Maschine bauen, die Äpfel und Birnen, die über ein Förderband kommen, für den Versand in Kartons verpackt. Die Maschine muss zwischen Äpfeln und Birnen unterscheiden, um sie in die richtige Kiste zu packen. Die für die Klassifizierung gemessenen Eigenschaften sind das Gewicht und die Farbe der Früchte. Das Unternehmen beschliesst, einen linearen Klassifikator mit Trainingsdaten zu trainieren, die aus der Messung einer grossen Stichprobe von Äpfeln und Birnen auf seinen Feldern gewonnen wurden (die Trainingsdaten werden in der Abbildung 1 (rechts) gezeigt) Das Unternehmen bringt den Klassifikator in Produktion und das System scheint gut zu funktionieren.

Nach einigen Wochen beschweren sich Kunden über Tennisbälle in ihren Apfelkisten. Das Unternehmen untersucht das Problem. Sie wissen, dass sich in der Nähe ihrer Felder ein Tennisplatz befindet, und sie stellen fest, dass der trainierte Klassifikator die eingehenden Tennisbälle als Äpfel einstuft – obwohl sie den Trainingsdaten unähnlich sind (siehe Abbildung 2 (rechts)). Wie kann das Unternehmen dieses Problem lösen?

Mögliche Lösungen

1. Neurale Netzwerke

„Klassische“ neuronale Netze sind von Natur aus nicht in der Lage, einem Sample keine Klasse zuzuordnen. Eine Möglichkeit, dieses Problem zu lösen, besteht darin, eine zusätzliche Ablehnungsklasse einzuführen. Um Trainingsmuster für diese Ablehnungsklasse zu erzeugen, wird ein kleinster umgebender Hyperwürfel für die Daten jeder Klasse konstruiert. In den nicht überlappenden Regionen der Hyperwürfel aller Klassen werden Trainingsmuster erzeugt und als Klasse «Unbekannt» gekennzeichnet. Es muss darauf geachtet werden, dass die Anzahl oder Ablehnungsproben in einem guten Verhältnis zu den anderen Trainingsproben stehen, um eine schiefe Verteilung zu vermeiden. Mit den erzeugten Zurückweisungsproben kann das neuronale Netz normal trainiert werden (möglicherweise muss die Netzkapazität erhöht werden). Sie können in Abbildung 3 sehen, dass bei Anwendung dieser Methode der Tennisball NICHT als Apfel oder Birne klassifiziert wird.

2. Bayessche Klassifikatoren mit Gausschen Klassendichten

Angenommen, der Klassifikator verwendet ein generatives Modell mit normalverteilten Klassendichten \( p\left(\mathbf{x}\middle| C_i\right) \) ~ \( N\left(\mathbf{\mu}_\mathbf{i},\mathbf{\Sigma}_\mathbf{i}\right) \). Dann könnte man annehmen, dass der Evidenzterm (berechnet nach dem Gesetz der totalen Wahrscheinlichkeit),

\( p(x)= \sum{p\left({x}\middle| C_i\right)p\left(C_i\right),} \)

verwendet werden kann, um "unwahrscheinliche" Proben im Hinblick auf das Modell zurückzuweisen. Allerdings, \( p(x) \) ist eine Wahrscheinlichkeitsdichte und hat keine absolute Bedeutung. Ihre Werte hängen von der Skalierung der Merkmale ab. Daher wird ein zuverlässigeres Mass benötigt. Eine Idee ist, den Mahalanobis-Abstand des Merkmalsvektors zum Mittelwert einer bestimmten Klasse zu verwenden

\( {d_i(x)}^2=\left(\mathbf{x}-\mathbf{\mu}_\mathbf{i}\right)^\mathbf{T}{\mathbf{\Sigma}_\mathbf{i}}^{-\mathbf{1}}\left(\mathbf{x}-\mathbf{\mu}_\mathbf{i}\right). \)

Dieser Abstand bildet (zumindest in 2d) Ellipsen um den Mittelwert der Verteilung, deren Achsen durch die Verteilungsvarianz skaliert sind. Man kann dann die Wahrscheinlichkeit berechnen, einen Abstand zu beobachten, der grösser als ein bestimmter Wert ist, indem man

\( p\left(D_i>d\right)=\frac{1}{2}\left(1-erf\left(\frac{1}{\sqrt2}d\right)\right). \)

So können Stichproben zurückgewiesen werden, wenn die Wahrscheinlichkeit, dass ein bestimmter Abstand für diese Stichprobe beobachtet wird, unter einem Schwellenwert liegt

\( p\left(D_i>d_i\left(x\right)\right)<\delta \)

Diese Schwellenwerte können der bekannten Drei-Sigma-Regel entsprechen - die Wahl eines Schwellenwerts von \( \delta \) = 0.27 bedeutet beispielsweise, dass 99,73 (3 Sigma) der vom Modell erzeugten Daten innerhalb dieses Bereichs liegen würden. Um das Kriterium auf mehrere Klassen auszuweiten, kann die folgende Beziehung verwendet werden

\( p_{\sigma(x)}=\frac{\underset i \max {p(D_i>d_i(x))p(C_i)}}{\underset i \max {p\left(C_i\right)}} \)

In Abbildung 4 ist zu sehen, dass dieser Tennisball NICHT als Apfel oder Birne klassifiziert werden würde und dass die Entscheidungsbereiche eine elliptische Form haben.

3. Zweistufiger Ansatz (zwei Modelle)

Grundsätzlich ist es auch möglich, Proben zweistufig auszusortieren. In diesem Fall werden zwei Modelle trainiert. Das erste Modell erkennt Samples, die nicht Teil der Trainingsdaten sind, und führt die Zurückweisung durch. Das zweite Modell ist dann ein beliebiger anderer Klassifikator (wie der lineare Klassifikator im anfänglichen Spielzeugbeispiel). Im Folgenden werden die beiden möglichen Ablehnungsmodelle One-Class SVM und Isolation Forests gezeigt. Dennoch kann in dieser Richtung fast jedes Modell verwendet werden, das eine Ausreissererkennung durchführen kann.

3.1. One-class-SVM mit radialem Basisfunktionskern

Eine Möglichkeit, ein Ablehnungsmodell zu trainieren, besteht darin, eine One-Class Support-Vektor-Maschine zu verwenden. Um beliebige Datenverteilungen zu erfassen, kann ein radialer Basisfunktionskern verwendet werden. Abbildung 5 zeigt das Ergebnis der Anwendung der One-Class SVM auf das Spielzeugbeispiel. Auch hier würde der Tennisball abgelehnt.

3.2. Isolation-Forest

Als zweites Beispiel für ein Ablehnungsmodell Abbildung 6 zeigt das Ergebnis des Trainings eines Isolation-Forests für das Spielzeugbeispiel. Der Kerngedanke von Isolation-Forests oder -Trees ist, dass Anomalien mit wenigen Entscheidungen aus den Daten isoliert werden können und daher eine geringe Tiefe in den trainierten Isolations-Trees aufweisen.

In diesem Artikel wurden drei verschiedene Ansätze aufgezeigt, um „Ich weiss nicht“ in Klassifikationsalgorithmen zu integrieren. Welche Methode am besten funktioniert (in Bezug auf Genauigkeit, Anzahl der Dimensionen, Rechenleistung oder Speicherbedarf, Gesamtsystemdesign usw.) hängt von der Anwendung ab. Im Allgemeinen ist es wünschenswert, nur ein Modell trainieren zu müssen, um den Overhead und die Rechenkomplexität gering zu halten. Wenn das Modell jedoch keine Stichproben verwerfen kann, kann ein zweistufiges Verfahren verwendet werden (zum Beispiel Klassendichten sind nicht normalverteilt). Generell sollte man sich immer der Konsequenzen einer Fehlklassifizierung für eine bestimmte Anwendung bewusst sein.