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

1. Il Problema: Rilevamento Online di Punti di Cambiamento Non Parametrico

Il lavoro affronta il problema del rilevamento online dei punti di cambiamento (online change point detection). Si considera una sequenza di vettori aleatori indipendenti $X_1, \dots, X_T$ in uno spazio euclideo. L'obiettivo è identificare il momento $\tau^*$ in cui la distribuzione sottostante cambia da una densità $p$ a una densità $q \neq p$, il più rapidamente possibile, senza conoscere a priori né $\tau^*$ né le forme di $p$ e $q$.

A differenza della maggior parte degli approcci esistenti che si basano su:

• Assunzioni parametriche forti (es. distribuzioni Gaussiane, shift della media).
• Metodi offline (che analizzano l'intera serie storica dopo la raccolta dei dati).

Questo paper si concentra su un setup non parametrico e sequenziale, dove non si fanno ipotesi specifiche su come $q$ differisca da $p$, ma si assume solo che i "punteggi" (score functions) $\nabla \log p$ e $\nabla \log q$ siano lisci e approssimabili bene.

2. Metodologia Proposta

L'algoritmo proposto combina l'apprendimento online con consigli di esperti (online learning with expert advice) e la stima sequenziale della funzione di punteggio (score function estimation).

A. Modellazione e Divergenza di Fisher

Invece di stimare direttamente le densità $p$ e $q$ (che richiederebbe il calcolo di integrali complessi su spazi ad alta dimensione), l'algoritmo utilizza una classe di riferimento parametrica di densità esponenziali $P = \{p_\theta : \theta \in \mathbb{R}^d\}$ definita come:
$$\log p_\theta(x) = \Psi(x)^\top \theta - \Phi(\theta)$$
Dove $\Psi(x)$ è una mappa fissa (es. polinomi o funzioni base).
Per evitare il calcolo del termine di normalizzazione $\Phi(\theta)$ (che è intrattabile numericamente), la vicinanza tra la densità target e il modello $p_\theta$ è misurata tramite la Divergenza di Fisher:
$$F(p, p_\theta) = \frac{1}{2} \mathbb{E}_{X \sim p} \|\nabla \log p(X) - \nabla \log p_\theta(X)\|^2$$
Utilizzando l'identità di Green, gli autori costruiscono una funzione di perdita quadratica $\ell_t(\theta)$ che è una stima non distorta della divergenza di Fisher, basata solo sui dati osservati $X_t$.

B. Previsione con Esperti Infiniti e Fixed Share

Il cuore dell'algoritmo risiede nel confronto tra due strategie di previsione online:

1. Exponentially Weighted Average (EWA): Un predittore che si adatta alla migliore esperta statica $\theta^*$ su tutto l'intervallo passato. Funziona bene finché la distribuzione non cambia.
2. Fixed Share (FS): Una variante dell'algoritmo "Fixed Share" di Herbster e Warmuth, adattata per un numero infinito di esperti (spazio continuo $\mathbb{R}^d$) e funzioni di perdita quadratiche. Questo predittore è progettato per "inseguire la migliore esperta" che può cambiare nel tempo, permettendo di adattarsi rapidamente a nuovi regimi.

C. Statistica di Test

L'algoritmo calcola una statistica di test $S_t$ come la differenza cumulativa delle perdite tra i due predittori:
$$S_t = \hat{L}^{EW}_{1:t} - \hat{L}^{FS}_{1:t}$$

• Regime pre-cambiamento ($t \le \tau^*$): Entrambi i predittori performano in modo simile, quindi $S_t$ rimane piccolo.
• Regime post-cambiamento ($t > \tau^*$): Il predittore EWA rimane "bloccato" sul vecchio regime, mentre il predittore FS si adatta rapidamente al nuovo regime. Di conseguenza, la differenza $S_t$ cresce rapidamente.
• Decisione: Se $S_t$ supera una soglia predefinita $z$, viene segnalato un punto di cambiamento.

3. Contributi Chiave

1. Algoritmo Non Parametrico Online: Proposta di un metodo che non richiede assunzioni parametriche rigide sulle distribuzioni sottostanti, basandosi invece sulla stima dello score tramite divergenza di Fisher.
2. Estensione del Fixed Share a Esperti Infiniti: Sviluppo di una versione dell'algoritmo Fixed Share per spazi di parametri continui ($\mathbb{R}^d$) con funzioni di perdita quadratiche, risolvendo problemi computazionali che limitavano le applicazioni precedenti (come quelle basate sulla discesa del gradiente online).
3. Garanzie Teoriche Non Asintotiche: Derivazione di limiti di probabilità alta (high-probability bounds) per la statistica di test sia nel regime pre-cambiamento (limitando i falsi allarmi) che post-cambiamento (garantendo la rilevazione). Questi risultati si basano su recenti progressi nella concentrazione delle martingale non limitate.
4. Efficienza Computazionale: L'algoritmo è implementabile in modo efficiente (complessità $O(d^3 T^2)$ con tasso di apprendimento costante), rendendolo praticabile per serie temporali di dimensioni ragionevoli.

4. Risultati Sperimentali

Gli autori hanno valutato l'algoritmo (denominato Algorithm 3.1) su dataset sintetici e reali, confrontandolo con metodi dello stato dell'arte come:

• FLH (Follow-the-Leading-History).
• FALCON (approccio contrastivo).
• KLIEP (stima dell'importanza relativa).
• M-statistic (basato su Kernel Maximum Mean Discrepancy).

Risultati principali:

• Dati Sintetici: L'algoritmo ha dimostrato tempi di rilevamento (detection delay) molto brevi e zero falsi allarmi in scenari di shift di media e varianza, sia univariati che multivariati.
• Rilevamento Attività Umana (WISDM): Su dati di accelerometri da smartphone, l'algoritmo ha superato gli altri metodi con un ritardo medio di rilevamento di ~15.43 osservazioni contro ~16.29-25.9 degli altri, mantenendo un solo falso allarme.
• Rilevamento Occupazione Stanza e Voce: Ha mostrato prestazioni robuste anche in presenza di rumore e in scenari complessi, superando o eguagliando i competitori con un numero inferiore di falsi positivi.

5. Significato e Impatto

Questo lavoro è significativo perché colma il divario tra la teoria dell'apprendimento online (tracking the best expert) e il rilevamento pratico di cambiamenti in distribuzioni complesse e non parametriche.

• Flessibilità: Rimuove la necessità di specificare il tipo di cambiamento (es. solo media o solo varianza), rendendo il metodo applicabile a una vasta gamma di scenari reali.
• Robustezza Teorica: Fornisce garanzie matematiche rigorose su tempi di rilevamento e probabilità di errore, un aspetto spesso carente nelle soluzioni puramente empiriche.
• Innovazione Metodologica: L'uso della divergenza di Fisher combinata con un predittore "Fixed Share" per spazi continui rappresenta un avanzamento tecnico che supera le limitazioni computazionali dei metodi basati sulla verosimiglianza (likelihood) tradizionale.

In sintesi, il paper propone una soluzione elegante e teoricamente fondata per il rilevamento di anomalie e cambiamenti strutturali in tempo reale, particolarmente utile in contesti dove i modelli parametrici sono inadeguati o troppo costosi da calcolare.