Anomaly detection using surprisals

Der Artikel stellt ein einheitliches Framework zur Anomalieerkennung vor, das Anomalien als Beobachtungen mit ungewöhnlich niedriger Wahrscheinlichkeit definiert und deren Erkennung durch die Schätzung der oberen Schwänze einer Surprisal-Verteilung mittels robuster empirischer oder Extremwert-Methoden auf komplexe Daten anwendbar macht.

Das Wesentliche

Hier ist eine einfache, bildhafte Erklärung der Forschungsarbeit von Hyndman und Frazier, als würde man sie einem Freund beim Kaffee erzählen.

Das große Rätsel: Wie findet man die "Falschen" in der Menge?

Stellen Sie sich vor, Sie sind auf einer riesigen Party. Die meisten Gäste tanzen, lachen und verhalten sich genau so, wie man es von einer Party erwartet. Aber dann gibt es jemanden, der im Keller sitzt und Stille hält, oder jemanden, der mitten im Tanzsaal eine Eisscholle trägt.

In der Statistik nennen wir diese Ausreißer Anomalien. Das Problem ist: Die meisten Methoden, um diese Ausreißer zu finden, sind wie ein sehr starrer Sicherheitsbeamter.

• Entweder sagt er: "Wenn du nicht genau wie alle anderen aussiehst, bist du verdächtig." (Das funktioniert gut, wenn alle gleich sind, aber scheitert, wenn die Party seltsam ist).
• Oder er schaut nur auf die Ränder des Raumes: "Wer am Rand steht, ist verdächtig." (Das verpasst aber jemanden, der mitten im Raum steht, aber eine völlig verrückte Farbe trägt).

Die Autoren dieses Papiers haben eine neue, kluge Methode entwickelt, die auf dem Konzept des "Überraschens" (Surprisal) basiert.

---

1. Das Konzept: Der "Überraschungs-Meter"

Stellen Sie sich vor, Sie haben eine Vorhersage-App für das Wetter.

• Wenn die App sagt "Sonnig" und die Sonne scheint, sind Sie nicht überrascht. Der "Überraschungs-Meter" steht auf 0.
• Wenn die App "Sonnig" sagt und es schneit, sind Sie total überrascht. Der Meter steht auf 100.

In der Statistik nennen wir diesen Wert Surprisal.

• Niedriger Wert: Das passiert oft, es ist normal.
• Hoher Wert: Das passiert selten, es ist verdächtig.

Das Geniale an dieser Methode ist: Es ist egal, warum es überraschend ist. Ob es schneit, weil der Winter kommt, oder weil ein Vulkan ausgebrochen ist – der Meter zeigt einfach an: "Hey, das hier ist unwahrscheinlich!"

2. Das Problem: Wir kennen die Party nicht genau

Normalerweise versuchen Statistiker, die genaue Form der Party zu verstehen (Wie viele Leute tanzen? Wie laut ist die Musik?). Aber oft ist das Modell falsch. Vielleicht denken wir, die Party ist eine ruhige Weinprobe, dabei ist es ein Rockkonzert. Wenn wir dann jemanden suchen, der "anders" ist, basieren wir auf falschen Annahmen.

Die Autoren sagen: "Macht euch nicht verrückt wegen der genauen Form der Party!"

Statt zu versuchen, die ganze Party perfekt zu modellieren, tun sie Folgendes:

1. Sie berechnen für jeden Gast den Überraschungs-Wert (basierend auf einem grob geschätzten Modell).
2. Dann schauen sie sich nur die Liste der Überraschungs-Werte an.

Das ist wie folgt: Statt zu versuchen, jedes einzelne Gesicht auf der Party zu beschreiben, machen Sie eine Liste: "Wer war am überraschendsten?" und sortieren diese Liste.

3. Die zwei Werkzeuge: Der Zähler und der Kristallball

Sobald Sie die Liste der Überraschungs-Werte haben, müssen Sie entscheiden: "Ist dieser Wert hoch genug, um als Ausreißer zu gelten?" Dafür nutzen die Autoren zwei Werkzeuge:

Werkzeug A: Der Zähler (Empirische Methode)

Stellen Sie sich vor, Sie zählen einfach: "Von 1000 Gästen waren 990 normal, und 10 hatten einen hohen Überraschungs-Wert."
Wenn Sie also einen Gast mit einem Wert haben, der höher ist als bei 99% der anderen, dann ist er ein Ausreißer.

• Vorteil: Sehr einfach, braucht keine komplizierte Mathematik.
• Nachteil: Wenn die Party sehr klein ist, ist das Zählen ungenau.

Werkzeug B: Der Kristallball (Extreme Value Theory / GPD)

Was, wenn die Party riesig ist und wir jemanden suchen, der noch verrückter ist als alle bisherigen? Wir können nicht warten, bis er kommt.
Hier nutzen die Autoren einen mathematischen "Kristallball" (die Generalized Pareto Distribution).

• Dieser Ball schaut sich die extremsten Werte der Liste an und sagt: "Basierend auf der Spitze der Liste, wie wahrscheinlich ist es, dass noch jemand noch verrückter kommt?"
• Der Clou: Dieser Kristallball funktioniert auch dann gut, wenn unser ursprüngliches Modell der Party (z.B. "es ist eine Weinprobe") falsch war. Solange die Reihenfolge der verrücktesten Gäste stimmt, funktioniert der Kristallball.

4. Warum ist das so genial? (Die Analogie des "Schiefen Hauses")

Stellen Sie sich vor, Sie bauen ein Haus, um Gäste zu empfangen.

• Die alte Methode: Sie bauen ein perfektes, symmetrisches Haus. Wenn jemand durch die Wand bricht, ist er ein Ausreißer. Aber wenn das Haus eigentlich schief gebaut sein sollte (weil der Boden schief ist), dann sehen Sie normale Gäste als Ausreißer an, weil sie nicht in Ihr perfektes Modell passen.
• Die neue Methode (Surprisal): Sie bauen ein Haus, das vielleicht schief ist. Aber Sie haben einen Überraschungs-Melder an der Tür.
  • Wenn jemand hereinkommt, der völlig unpassend ist (z.B. ein Elefant in einem Wohnzimmer), löst der Melder aus.
  • Es ist egal, ob das Haus schief ist oder nicht. Der Melder reagiert darauf, dass der Elefant im Kontext dieses Hauses extrem unwahrscheinlich ist.

Die Autoren zeigen in ihren Tests (z.B. mit französischen Sterberaten oder Cricket-Spieler-Daten), dass diese Methode selbst dann funktioniert, wenn das zugrundeliegende Modell völlig falsch ist. Sie finden echte Ausreißer (wie Kriege oder Epidemien in den Sterbedaten), die andere Methoden übersehen würden.

Zusammenfassung in einem Satz

Statt zu versuchen, die Welt perfekt zu verstehen, messen wir einfach, wie überraschend ein Ereignis ist, und nutzen dann einfache Zählregeln oder mathematische Kristallbälle, um zu entscheiden, was so überraschend ist, dass wir es als "Ausreißer" markieren sollten – und das funktioniert auch dann, wenn unsere Vorstellung von der Welt nicht 100% stimmt.

Das Ergebnis: Eine robustere, fairere und einfachere Art, das "Verrückte" in Daten zu finden, egal ob es sich um Wetter, Sport oder Menschenleben handelt.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Anomaly detection using surprisals" von Rob J. Hyndman und David T. Frazier auf Deutsch.

1. Problemstellung

Herkömmliche Methoden zur Anomalieerkennung (Outlier Detection) leiden oft unter zwei Hauptproblemen:

1. Ad-hoc-Regeln und starke Annahmen: Viele Verfahren basieren auf willkürlichen Schwellenwerten oder treffen starke Verteilungsannahmen (z. B. Normalverteilung), die in der Praxis oft nicht zutreffen.
2. Fokus auf Randereignisse: Die meisten Methoden konzentrieren sich auf Ereignisse in den Extrembereichen (Tails) einer Verteilung. Sie übersehen jedoch „Inlier-Anomalien", die in Lücken zwischen den Modi (Multimodalität) oder in anderen Bereichen niedriger Dichte auftreten, aber nicht unbedingt in den äußersten Rändern liegen.

Zudem ist es schwierig, Anomalien in komplexen, multivariaten oder nicht-euklidischen Datenräumen zu definieren, ohne starke Modellannahmen zu treffen.

2. Methodik: Der Surprisal-Ansatz

Die Autoren schlagen ein einheitliches Framework vor, das Anomalien als Beobachtungen mit einer ungewöhnlich niedrigen Wahrscheinlichkeit unter einem (möglicherweise fehlerhaft spezifizierten) Modell definiert.

Kernkonzepte:

• Surprisal (Überraschung): Für jede Beobachtung $y_i$ wird der Surprisal-Wert $s_i$ berechnet als negativer Logarithmus der generalisierten Dichte $f(y_i)$:
  $$s_i = -\log f(y_i)$$
  Ein hoher Surprisal-Wert bedeutet eine niedrige Dichte und somit eine „überraschende" (potenziell anomale) Beobachtung.
• Anomalie-Score: Anstatt die Dichte direkt zu bewerten, wird die Wahrscheinlichkeit berechnet, einen Surprisal-Wert zu erhalten, der mindestens so groß ist wie der beobachtete Wert. Dies wird als $p_i = \Pr(S \ge s_i)$ definiert, wobei $S$ die Zufallsvariable des Surprisals ist.
• Dimensionsreduktion: Das Problem der Anomalieerkennung in einem komplexen, möglicherweise multivariaten Raum wird auf die Schätzung des oberen Endes einer eindimensionalen Surprisal-Verteilung reduziert.

Schätzung der Tail-Wahrscheinlichkeiten ($p_i$):
Da die wahre Verteilung $F$ oft unbekannt ist, werden drei Ansätze zur Schätzung von $p_i$ vorgeschlagen, wobei die Autoren zwei robuste Methoden hervorheben, die auch bei fehlerhafter Modellspezifikation funktionieren:

1. Empirischer Schätzer: Nutzung der empirischen Verteilungsfunktion der beobachteten Surprisal-Werte. $p_i$ ist der Anteil der Surprisals, die größer oder gleich $s_i$ sind.
2. Extreme-Value-Schätzer (GPD): Anpassung einer Generalisierten Pareto-Verteilung (GPD) an die größten Surprisal-Werte, um die Tail-Wahrscheinlichkeiten zu extrapolieren.
3. (Referenz): Berechnung basierend auf der angenommenen Verteilung $F$ (wird als weniger robust angesehen, wenn $F$ falsch ist).

3. Theoretische Grundlagen und Beiträge

A. Robustheit gegenüber Fehlspezifikation (Empirischer Ansatz)
Die Autoren leiten Bedingungen her, unter denen der empirische Schätzer auch dann funktioniert, wenn das angenommene Modell $f$ nicht der wahren Verteilung entspricht.

• Assumption 2.1: Es muss eine streng monoton steigende Transformation $h(\cdot)$ existieren, die die wahren Surprisals $S$ mit den gefitteten Surprisals $\hat{S}$ im oberen Tail verknüpft ($S = h(\hat{S})$).
• Ergebnis: Solange die Reihenfolge (Ranking) der Surprisals im Tail korrekt ist, liefert der empirische Schätzer eine zuverlässige Schätzung der wahren Tail-Wahrscheinlichkeit. Dies wird durch die Dvoretzky–Kiefer–Wolfowitz-Ungleichung gestützt, die endliche Stichproben-Konfidenzgarantien liefert.
• Implikation: Das Modell muss nicht die genaue Form des Tails treffen, sondern nur die Lage der niedrigen Dichtebereiche korrekt identifizieren.

B. Extreme Value Theory (GPD-Ansatz)
Für den GPD-Ansatz werden Bedingungen hergeleitet, die sicherstellen, dass die Maxima der Surprisal-Werte in die Familie der generalisierten Extremwertverteilungen (GEV) fallen.

• Drei Szenarien werden betrachtet: Sub-Gaußsch, Sub-Exponentiell und Polynomiale Tails.
• Theorem 3.1: Zeigt, dass unter diesen Bedingungen die Verteilung der maximalen Surprisals gegen eine GEV-Verteilung konvergiert, was die Anpassung einer GPD rechtfertigt.
• Robustheits-Aspekt: Es ist sicherer, eine Verteilung mit schwereren Tails anzunehmen (z. B. Student-t statt Normalverteilung), als umgekehrt. Eine Unterschätzung der Tail-Schwere führt zu langsamer Konvergenz und ungenauen Anomalieerkennung, während eine Überschätzung nur geringe Kosten verursacht.

C. Anwendung auf bedingte Verteilungen
Das Framework lässt sich auf Regressionsmodelle und bedingte Verteilungen erweitern. Hier wird der Surprisal basierend auf $f(Z | X)$ berechnet, wobei $Z$ das Ziel und $X$ die Kovariaten sind. Dies ermöglicht die Erkennung von Anomalien, die spezifisch für die Beziehung zwischen Variablen sind, nicht nur für die Randverteilungen.

4. Ergebnisse und Anwendungen

Simulationen:

• Normalverteilung vs. t-Verteilung: Selbst wenn Daten aus einer Normalverteilung stammen, aber ein t-Modell zur Berechnung der Surprisals verwendet wird (oder umgekehrt), liefern der empirische Schätzer und die GPD-Methode akkurate Tail-Wahrscheinlichkeiten. Die direkte Berechnung basierend auf dem falschen Modell („Assumed distribution") ist hingegen ungenau.
• Bivariate Gamma-Daten: Bei Verwendung eines falschen bivariaten Normalmodells für Gamma-Daten zeigt sich, dass die GPD-Methode schneller konvergiert als der empirische Schätzer. Die Verwendung einer Student-t-Referenz (schwerere Tails) funktionierte besser als eine Normalverteilung, was die theoretische Empfehlung bestätigt.

Anwendungsfälle:

1. Französische Sterblichkeitsraten (1816–1999):

   • Daten: Zeitreihen nach Alter und Geschlecht.
   • Ergebnis: Das Modell identifizierte Anomalien, die mit historischen Ereignissen korrelieren (Cholera-Ausbrüche 1832/1849, Deutsch-Französischer Krieg 1870, Erster Weltkrieg 1914–1918, Spanische Grippe 1918).
   • Vorteil: Das System filterte zufällige Schwankungen heraus, indem es nur Jahre markierte, in denen mehrere Altersgruppen gleichzeitig anomale Werte zeigten.

2. Test-Cricket „Not Outs":

   • Daten: Schlagmann-Daten (Innings vs. Anzahl der „Not Outs").
   • Modell: Binomialverteilung mit Logit-Link (GAM).
   • Ergebnis: Der englische Bowler Jimmy Anderson wurde als Anomalie identifiziert. Obwohl er kein großer Schlagmann war, hatte er eine ungewöhnlich hohe Anzahl von „Not Outs" (114 in 265 Innings) im Vergleich zur erwarteten Wahrscheinlichkeit.
   • Bedeutung: Das Modell erkannte eine Anomalie, die weder in der reinen Quote noch in der absoluten Zahl auffällig war, sondern im Kontext des statistischen Modells (berücksichtigung der Diskretion und Varianz).

5. Signifikanz und Fazit

• Einheitlichkeit: Das Framework bietet eine einzige, konsistente Metrik (Surprisal) für diskrete, kontinuierliche und gemischte Verteilungen.
• Robustheit: Die Methode ist bemerkenswert robust gegenüber Fehlspezifikationen des zugrunde liegenden Modells, solange die relative Rangfolge der Surprisals im Tail erhalten bleibt.
• Interpretierbarkeit: Anomalien werden durch Wahrscheinlichkeiten ($p_i$) quantifiziert, was eine direkte Kontrolle der False-Positive-Rate ermöglicht.
• Effizienz: Die Berechnung ist linear in der Stichprobengröße; die Tail-Schätzung erfordert nur Sortieren (empirisch) oder schnelle GPD-Anpassungen.
• Software: Die Methoden sind im R-Paket weird implementiert.

Zusammenfassend stellen die Autoren einen theoretisch fundierten, flexiblen und robusten Ansatz vor, der das Problem der Anomalieerkennung von komplexen multivariaten Räumen auf die Schätzung der Tail-Wahrscheinlichkeiten einer eindimensionalen Surprisal-Verteilung reduziert. Dies ermöglicht die Erkennung von Anomalien in Bereichen niedriger Dichte, die von traditionellen Methoden oft übersehen werden.