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

Titel: Score-based Change Point Detection via Tracking the Best of Infinitely Many Experts

Auteurs: Anna Markovich en Nikita Puchkin (HSE University)

---

1. Probleemstelling

Het artikel richt zich op het probleem van online veranderingpuntdetectie (online change point detection). Het doel is om het moment ($\tau^*$) te detecteren waarop de onderliggende verdeling van een stroom van i.i.d. waarnemingen ($X_1, \dots, X_T$) verandert, en dit zo snel mogelijk te doen naarmate de data binnenkomt.

• Situatie: De waarnemingen $X_1, \dots, X_{\tau^*}$ worden gegenereerd uit een onbekende dichtheid $p$, en $X_{\tau^*+1}, \dots, X_T$ uit een andere onbekende dichtheid $q$ ($p \neq q$).
• Uitdaging: De auteurs willen een niet-parametrische aanpak ontwikkelen. Dit betekent dat ze geen sterke aannames maken over de vorm van $p$ en $q$ (zoals dat ze Gaussisch zijn of een mean-shift ondergaan).
• Beperkingen van bestaande methoden: Veel bestaande methoden zijn parametrisch (veronderstellen een specifieke familie van verdelingen) of vereisen de berekening van ingewikkelde integralen (zoals de log-partitiefunctie $\Phi(\theta)$) die in hoge dimensies onberekenbaar zijn.

2. Methodologie

De kern van de voorgestelde oplossing is een algoritme dat sequentiële voorspelling met advies van experts (online learning with expert advice) combineert met online convex optimalisatie.

A. Benadering via Score-functies en Fisher-divergentie

In plaats van de dichtheden $p$ en $q$ direct te schatten, benaderen de auteurs deze met een parametrische referentieklassie van verdelingen $\mathcal{P} = \{p_\theta : \theta \in \mathbb{R}^d\}$ van het vorm:
$$\log p_\theta(x) = \Psi(x)^\top \theta - \Phi(\theta)$$
Om de lastige berekening van $\Phi(\theta)$ (een integraal over de ruimte) te vermijden, gebruiken ze de Fisher-divergentie als maat voor de afstand tussen de geschatte en de ware verdeling.
Deze divergentie kan worden herschreven met behulp van de Green's eerste identiteit, wat leidt tot een verliesfunctie die alleen afhangt van de waarnemingen en de gradienten van de score-functies:
$$\ell_t(\theta) = \frac{1}{2}\theta^\top A_t \theta - b_t^\top \theta$$
Waarbij $A_t$ en $b_t$ direct uit de data ($X_t$) en de functie $\Psi$ worden berekend. Dit maakt het verlies kwadratisch en berekenbaar zonder integratie.

B. Tracking van de Beste Expert (Fixed Share)

Het algoritme vergelijkt twee voorspellers:

1. Exponentially Weighted Average (EWA) Forecaster: Deze probeert de beste statische expert $\theta$ te vinden voor de hele reeks tot nu toe. Deze presteert goed zolang er geen verandering is, maar reageert traag op veranderingen.
2. Fixed Share (FS) Forecaster: Een aangepaste versie van het algoritme van Herbster en Warmuth (1998), specifiek ontwikkeld voor een oneindig aantal experts (continu parameterbereik) en kwadratische verliezen. Deze voorspeller kan snel schakelen naar een nieuwe expert als de onderliggende verdeling verandert.

Het Teststatistiek:
Het algoritme berekent de cumulatieve verliezen van beide voorspellers, $\hat{L}^{EW}_{1:t}$ en $\hat{L}^{FS}_{1:t}$. De teststatistiek is het verschil:
$$\hat{S}_t = \hat{L}^{EW}_{1:t} - \hat{L}^{FS}_{1:t}$$

• Voor $\tau^*$: Beide voorspellers presteren vergelijkbaar, dus $\hat{S}_t$ blijft klein.
• Na $\tau^*$: De EWA-voorspeller blijft vastzitten in de oude verdeling, terwijl de FS-voorspeller snel aanpast. Hierdoor groeit $\hat{S}_t$ snel.
• Beslissing: Als $\hat{S}_t$ een vooraf bepaald drempelwaarde $z$ overschrijdt, wordt een veranderingpunt gemeld.

C. Computationale Complexiteit

Het algoritme is efficiënt geïmplementeerd met recursieve formules voor de voorspellingen. Met een constante leersnelheid ($\eta$) is de complexiteit per tijdstap $O(d^3 t)$, wat leidt tot een totale complexiteit van $O(d^3 T^2)$. Dit is aanzienlijk sneller dan brute-force benaderingen.

3. Belangrijkste Bijdragen

1. Niet-parametrisch Algoritme: Een nieuw algoritme voor online veranderingpuntdetectie dat geen specifieke aannames maakt over de vorm van de verdelingen $p$ en $q$, behalve dat hun score-functies glad zijn en goed benaderd kunnen worden.
2. Oneindige Expert-klassie: De ontwikkeling van een Fixed Share-voorspeller die werkt met een oneindig aantal experts (continu parameterbereik) en kwadratische verliezen, in plaats van alleen voor eindige verzamelingen.
3. Theoretische Garantie: Afleiding van niet-asymptotische, hoge-kansgrenzen (high-probability bounds) voor de teststatistiek.
   • In het pre-veranderingsregime is $\hat{S}_t$ begrensd door een term van de orde $O(\log^3 \tau^*)$.
   • In het post-veranderingsregime groeit $\hat{S}_t$ lineair met de tijd na de verandering, wat een snelle detectie garandeert.
4. Unbiased Schatting: Het gebruik van Green's identiteit om een zuivere schatting van de Fisher-divergentie te verkrijgen zonder de partitiefunctie te hoeven berekenen.

4. Resultaten

De auteurs hebben hun algoritme (Algorithm 3.1) getest op zowel synthetische als real-world datasets en vergeleken met state-of-the-art methoden zoals FLH, FALCON, KLIEP en M-statistic.

• Synthetische Data: Op Gaussische sequenties (met veranderingen in gemiddelde en variantie, zowel univariaat als multivariaat) presteerde het algoritme over het algemeen beter dan de concurrenten, met name in termen van detectievertraging (Detection Delay) en valse alarmen (False Alarms). Het kon veranderingen vaak binnen enkele observaties detecteren.
• Real-world Data:
  • Menselijke Activiteit (WISDM dataset): Het algoritme detecteerde veranderingen in bewegingsdata van smartphones sneller en met minder valse alarmen dan de andere methoden.
  • Spraakdetectie (CENSREC-1-C): Zelfs bij aanwezigheid van ruis (SNR 15 en 20) behaalde het algoritme de beste resultaten in detectievertraging.
  • Kamerbezettingsdetectie: Op data van temperatuur, vochtigheid en CO2-niveaus presteerde het algoritme vergelijkbaar met de snelste concurrent (FALCON), maar met een lager aantal valse alarmen.

5. Betekenis en Conclusie

Dit werk is significant omdat het de brug slaat tussen online learning (tracking the best expert) en niet-parametrische statistische detectie.

• Praktische toepasbaarheid: Door de vermijding van de berekening van $\Phi(\theta)$ (de log-partitiefunctie) wordt het algoritme toepasbaar op complexe, hoge-dimensionale data waar eerdere methoden faalden.
• Robuustheid: De methode is robuust tegenover verschillende soorten verdelingsveranderingen (gemiddelde, variantie, complexere verschuivingen) zonder dat de gebruiker het type verandering hoeft te specificeren.
• Theoretische diepgang: De paper levert rigoureuze theoretische bewijzen voor de prestaties van het algoritme, wat zeldzaam is in het veld van niet-parametrische online detectie.

Kortom, de auteurs presenteren een efficiënt, theoretisch onderbouwd en praktisch effectief algoritme voor het real-time detecteren van veranderingen in datastromen, zonder de beperkende aannames van traditionele parametrische modellen.