Score-based change point detection via tracking the best of infinitely many experts

1. Problemstellung

Das Paper adressiert das Problem der nichtparametrischen Online-Änderungspunkterkennung (Online Change Point Detection).

• Ziel: Eine Folge von Beobachtungen $X_1, \dots, X_T$ wird sequentiell verarbeitet. Zu einem unbekannten Zeitpunkt $\tau^*$ ändert sich die zugrunde liegende Verteilung von einer Dichte $p$ auf eine Dichte $q$ ($q \neq p$). Das Ziel ist es, diesen Zeitpunkt $\tau^*$ so schnell wie möglich zu detektieren, ohne die Daten im Nachhinein (offline) zu analysieren.
• Herausforderung: Im Gegensatz zu vielen bestehenden Ansätzen werden keine starken parametrischen Annahmen über die Verteilungen $p$ und $q$ getroffen (z. B. keine Annahme von Gauß-Verteilungen oder bekannten Parametern). Die Verteilungen sind völlig unbekannt, außer dass ihre Score-Funktionen ($\nabla \log p$ und $\nabla \log q$) glatt sind und durch ein geeignetes Funktionensystem approximiert werden können.
• Kontext: Bisherige Methoden basieren oft auf parametrischen Modellen (z. B. Mittelwertverschiebungen bei Gauß-Verteilungen) oder erfordern die Berechnung von Integralen über hochdimensionale Räume, was rechnerisch extrem aufwendig ist.

2. Methodik

Der vorgeschlagene Algorithmus verbindet Online-Lernen mit Expertenberatung (Online Learning with Expert Advice) und sequentielle Schätzung von Score-Funktionen.

A. Parametrische Approximation und Fisher-Divergenz

Anstatt die Dichten direkt zu schätzen, wird eine Referenzklasse von Dichten $\mathcal{P} = \{p_\theta : \theta \in \mathbb{R}^d\}$ verwendet, die exponentielle Familienform haben:
$$\log p_\theta(x) = \Psi(x)^\top \theta - \Phi(\theta)$$
Um die rechenintensive Berechnung der Normierungskonstante $\Phi(\theta)$ (ein Integral über den gesamten Raum) zu vermeiden, nutzen die Autoren die Fisher-Divergenz als Maß für die Nähe zwischen der wahren Verteilung und dem Modell $p_\theta$.
Mithilfe der ersten Greenschen Identität wird gezeigt, dass die Fisher-Divergenz durch einen Erwartungswert ausgedrückt werden kann, der unverzerrt durch eine Stichprobe geschätzt werden kann, ohne $\Phi(\theta)$ berechnen zu müssen. Dies führt zu einer quadratischen Verlustfunktion der Form:
$$\ell_t(\theta) = \frac{1}{2}\theta^\top A_t \theta - b_t^\top \theta$$
wobei $A_t$ und $b_t$ direkt aus den Beobachtungen $X_t$ und der Funktion $\Psi$ berechnet werden.

B. Tracking des besten Experten (Fixed Share)

Das Problem wird als Online-Spiel formuliert, bei dem ein Lernender (Forecaster) versucht, die kumulierte Verlustfunktion zu minimieren.

1. Exponentiell gewichteter Durchschnitt (EW): Ein Standard-Algorithmus, der gut funktioniert, solange die Verteilung konstant bleibt (vor $\tau^*$). Er verfolgt einen statischen besten Experten $\theta^*$.
2. Fixed Share Forecaster (FS): Um Änderungen zu erkennen, wird eine Variante des „Fixed Share"-Algorithmus (Herbster & Warmuth, 1998) entwickelt, die für unendlich viele Experten (kontinuierlicher Raum $\mathbb{R}^d$) und quadratische Verluste angepasst ist.
   • Der FS-Algorithmus kann sich schnell an Änderungen anpassen, indem er zwischen verschiedenen Experten „umschaltet".
   • Er verfolgt eine Kombination von Experten, was ihm erlaubt, nach einer Änderung sofort auf einen neuen optimalen Parameter $\theta^*_{post}$ zu wechseln.

C. Teststatistik

Die Kernidee ist der Vergleich der kumulierten Verluste der beiden Forecaster:
$$\hat{S}_t = \hat{L}^{EW}_{1:t} - \hat{L}^{FS}_{1:t}$$

• Vor dem Änderungspunkt ($t \le \tau^*$): Beide Algorithmen performen ähnlich gut, da die Verteilung stabil ist. $\hat{S}_t$ bleibt klein.
• Nach dem Änderungspunkt ($t > \tau^*$): Der FS-Algorithmus passt sich schnell an die neue Verteilung an und erzielt einen niedrigeren Verlust. Der EW-Algorithmus bleibt jedoch „kleben" und verfolgt weiterhin den alten Parameter. Die Differenz $\hat{S}_t$ wächst schnell.
• Entscheidung: Sobald $\hat{S}_t$ einen Schwellenwert $z$ überschreitet, wird ein Änderungspunkt detektiert.

3. Wichtige Beiträge

1. Neuer Algorithmus für nichtparametrische Detektion: Entwicklung eines Algorithmus, der keine parametrischen Annahmen über $p$ und $q$ macht, sondern nur auf der Approximation der Score-Funktionen basiert.
2. Fixed Share für unendliche Expertenklassen: Herleitung einer effizienten, rekursiven Implementierung des Fixed Share-Algorithmus für den Fall unendlich vieler Experten (kontinuierlicher Raum) mit quadratischen Verlusten. Dies umgeht die rechenintensive Integration über den Parameterraum.
3. Theoretische Garantien: Herleitung nicht-asymptotischer, hochwahrscheinlicher Schranken für die Teststatistik $\hat{S}_t$:
   • Vor der Änderung: $\hat{S}_t$ ist mit hoher Wahrscheinlichkeit durch logarithmische Terme in $T$ und $\tau^*$ beschränkt (geringe False-Alarm-Rate).
   • Nach der Änderung: $\hat{S}_t$ wächst linear mit der Zeit (bzw. quadratisch in Bezug auf die Divergenz der Verteilungen), was eine schnelle Detektion garantiert.
4. Effizienz: Der Algorithmus hat eine rechnerische Komplexität von $O(d^3 T^2)$ (bei konstanter Lernrate), was ihn für praktische Anwendungen geeignet macht.

4. Ergebnisse

Die Autoren evaluieren den Algorithmus (Algorithm 3.1) an synthetischen und realen Datensätzen und vergleichen ihn mit state-of-the-art Methoden (FLH, FALCON, KLIEP, M-Statistik).

• Synthetische Daten: Bei Gaußschen Sequenzen mit Mittelwert- und Varianzverschiebungen (univariat und multivariat) erreicht der vorgeschlagene Algorithmus die kürzesten Detektionsverzögerungen (Average Detection Delay) bei gleichzeitig null oder sehr wenigen False Alarms. Er übertrifft insbesondere Methoden, die auf Kerneln basieren (wie M-Statistik), bei multivariaten Daten signifikant.
• Reale Daten:
  • Human Activity Detection (WISDM): Der Algorithmus detektiert Aktivitätswechsel schneller als die Konkurrenz und hält die False-Alarm-Rate niedrig.
  • Spracherkennung (CENSREC-1-C): Auch bei verrauschten Sprachdaten zeigt der Algorithmus eine überlegene Leistung.
  • Raumbelegung (Room Occupancy): Der Algorithmus erkennt Änderungen in Temperatur, Feuchtigkeit und CO2-Level effektiv.
• Vergleich: Der Algorithmus ist robuster gegenüber Hyperparameter-Tuning als einige Kernel-basierte Methoden und bietet eine bessere Balance zwischen Detektionsgeschwindigkeit und False Alarms.

5. Bedeutung und Fazit

Das Paper stellt einen signifikanten Fortschritt in der Theorie und Praxis der Online-Änderungspunkterkennung dar.

• Theoretische Tiefe: Die Verbindung von Online-Learning mit unendlichen Expertenklassen und Score-basierten Methoden bietet einen neuen, rigorosen Rahmen für nichtparametrische Detektion.
• Praktische Anwendbarkeit: Durch die Vermeidung von Integralberechnungen und die Nutzung von Score-Funktionen ist der Algorithmus auf hochdimensionale und komplexe Daten anwendbar, wo klassische parametrische Ansätze versagen.
• Robustheit: Die Methode ist weniger anfällig für Modellfehler, da sie keine spezifische Verteilungsform annimmt, sondern nur die Glattheit der Score-Funktionen voraussetzt.

Zusammenfassend bietet das Paper einen effizienten, theoretisch fundierten und empirisch überlegenen Ansatz zur schnellen Erkennung von Verteilungsänderungen in Echtzeit-Datenströmen.