Conditional anomaly detection with soft harmonic functions

1. Problemstellung

Das Paper adressiert das Problem der bedingten Anomalieerkennung (Conditional Anomaly Detection, CAD). Im Gegensatz zur herkömmlichen, unbedingten Anomalieerkennung, die Ausreißer im gesamten Merkmalsraum sucht, geht es bei CAD darum, ungewöhnliche Werte für eine Teilmenge von Variablen (Zielvariable/Label) zu identifizieren, gegeben die Werte der restlichen Variablen (Kontext).

• Ziel: Identifizierung und Rangfolge von Instanzen, bei denen das Label (z. B. eine medizinische Entscheidung oder ein Klassenzuordnung) im Kontext der anderen Attribute unwahrscheinlich oder falsch erscheint.
• Herausforderungen:
  1. Isolierte Punkte: Instanzen, die weit von den meisten Daten entfernt liegen. Hier ist es schwierig, die Anomalie zu bewerten, da keine Nachbarn für den Vergleich existieren.
  2. Randpunkte (Fringe Points): Instanzen am Rand der Klassenverteilung, die aufgrund ihrer geringen Wahrscheinlichkeit fälschlicherweise als Anomalien gelten könnten, obwohl sie zum Kontext passen.
  3. Label-Rauschen: Die Annahme, dass die Trainingsdaten perfekte Labels haben, ist oft falsch; auch historische Daten können fehlerhafte Labels enthalten.

2. Methodik

Die Autoren schlagen einen nicht-parametrischen Ansatz vor, der auf Label-Propagation über einem Ähnlichkeitsgraphen basiert und eine weiche harmonische Lösung (Soft Harmonic Solution) verwendet.

A. Grundlegender Ansatz

Statt ein parametrisches Modell zu lernen, wird ein Ähnlichkeitsgraph $G$ konstruiert, dessen Knoten die Datenpunkte und dessen Kanten die Ähnlichkeit zwischen ihnen darstellen.

• Label-Propagation: Die Information der Labels wird durch den Graphen propagiert. Das Ziel ist es, zu prüfen, ob das Label einer Instanz mit den Labels ihrer Nachbarn übereinstimmt.
• Weiche Harmonische Lösung: Anstatt harte Constraints (wie bei klassischen harmonischen Funktionen, die zu einer gewichteten k-NN-Äquivalenz degenerieren) zu verwenden, werden weiche Constraints eingeführt. Dies erlaubt es, dass sich Labels über den gesamten Mannigfaltigkeits-Struktur des Datensatzes ausbreiten können, auch wenn alle Daten als „gelabelt" betrachtet werden.

B. Anomalie-Score (SoftHAD Score)

Der Anomalie-Score $s_i$ für eine Instanz $i$ wird als absolute Differenz zwischen dem tatsächlichen Label $y_i$ und dem inferierten weichen Label $\ell^*_i$ definiert:
$$s_i = |\ell^*_i - y_i|$$
Ein hoher Score deutet darauf hin, dass das inferierte Label (basierend auf dem Kontext/Nachbarn) stark vom tatsächlichen Label abweicht, was auf eine Anomalie hindeutet.

C. Regularisierung gegen Isolierte und Randpunkte

Um das Problem der isolierten Punkte und Randpunkte zu lösen, wird der Graph-Laplacian $L(W)$ regularisiert:
$$K = L(W) + \gamma_g I$$

• Der Term $\gamma_g I$ wirkt wie ein zusätzlicher „Senken"-Knoten (Sink) mit Label 0, der mit allen anderen Knoten verbunden ist.
• Effekt: Dies reduziert das Vertrauen ($|\ell^*_i|$) in die Vorhersage für alle Punkte, aber besonders stark für isolierte Punkte, die ohnehin nur schwache Verbindungen zu anderen Knoten haben. So werden isolierte Punkte nicht fälschlicherweise als hochanomale Fälle gewertet.

D. Skalierbarkeit: Backbone Graph

Da die Berechnung der inversen Matrix für große Datensätze ($O(n^3)$) zu teuer ist, wird ein Backbone Graph verwendet:

• Die Daten werden quantisiert, und eine kleinere Menge von $k \ll n$ Centroids wird ausgewählt.
• Um die Approximation zu verbessern, erhalten diese Centroids Gewichte (Multiplizitäten), die angeben, wie viele Originaldatenpunkte sie repräsentieren.
• Die Regularisierung und die Matrixoperationen werden so angepasst, dass sie diese Gewichte berücksichtigen, was die Komplexität auf $O(k^3)$ reduziert.

E. Skalierung für Multi-Task-Szenarien

Für Anwendungen mit vielen Aufgaben (z. B. 749 verschiedene medizinische Entscheidungen) werden die Scores linear skaliert, um sie über verschiedene Aufgaben hinweg vergleichbar zu machen (Normierung auf [0, 1] basierend auf Trainingsdaten-Min/Max).

3. Hauptbeiträge

1. Neue Methode: Einführung eines Label-Propagation-Ansatzes auf Ähnlichkeitsgraphen für CAD zur Schätzung der Label-Konfidenz.
2. Spezifische Regularisierung: Entwicklung einer Regularisierung, die die Erkennung von unbedingten Ausreißern und Randpunkten unterdrückt, um Fehlklassifikationen zu minimieren.
3. Kompakte Berechnung: Präsentation einer effizienten Berechnungsmethode unter Verwendung eines gewichteten Backbone-Graphen.
4. Skalierungsansatz: Eine Methode zur Angleichung von Anomalie-Scores über verschiedene Aufgaben hinweg.
5. Validierung: Umfassende Evaluierung auf synthetischen Daten, UCI-Datensätzen und einem realen medizinischen Datensatz.

4. Ergebnisse

Die Methode (SoftHAD) wurde gegen mehrere Baselines getestet: 1-Class SVM, Quadratische Diskriminanzanalyse (QDA), SVM und gewichtetes k-NN.

• Synthetische Daten: SoftHAD erzielte in allen drei synthetischen Datensätzen (D1, D2, D3) die höchsten Übereinstimmungswerte (AUC) mit der wahren Anomalie-Reihenfolge und übertraf alle Baselines deutlich.
• UCI-Datensätze: Auf den Datensätzen Wine Quality, Housing und Auto MPG zeigte SoftHAD entweder die beste oder eine sehr nahe an der besten Leistung.
• Medizinische Daten (EHR): In einem realen Szenario zur Erkennung ungewöhnlicher Patient-Management-Entscheidungen (basierend auf elektronischen Gesundheitsakten) wurde die Methode von klinischen Experten bewertet.
  • SoftHAD übertraf sowohl das gewichtete k-NN als auch SVM-basierte Ansätze (gemessen am AUC).
  • Die Methode war robust gegenüber Variationen der Graphengröße und Regularisierungsparameter.
  • Die Skalierung der Scores verbesserte die Leistung in Multi-Task-Szenarien.

5. Bedeutung und Fazit

Das Paper stellt einen signifikanten Fortschritt in der bedingten Anomalieerkennung dar, insbesondere für hochdimensionale und komplexe Daten wie im Gesundheitswesen.

• Überwindung lokaler Grenzen: Im Gegensatz zu rein lokalen Methoden (wie k-NN) nutzt SoftHAD die globale Struktur der Datenmannigfaltigkeit.
• Robustheit: Durch die Regularisierung werden typische Fehlerquellen (isolierte Punkte, Randeffekte) adressiert.
• Praktische Anwendbarkeit: Die Fähigkeit, mit verrauschten Labels umzugehen und auf großen Datensätzen durch Backbone-Graphen effizient zu skalieren, macht die Methode für reale Anwendungen (z. B. klinische Entscheidungsunterstützung) geeignet.

Die Autoren planen zukünftige Arbeiten, bei denen die Anomalie-Scores nicht unabhängig pro Label, sondern strukturiert gemeinsam berechnet werden, um die Notwendigkeit der Skalierung weiter zu reduzieren.