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

1. Problématique

L'article s'intéresse au problème de la détection de changement de point (Change Point Detection - CPD) en ligne (séquentielle). Le cadre est le suivant :

• On observe une séquence de vecteurs aléatoires $X_1, \dots, X_T$.
• Avant un instant inconnu $\tau^*$, les observations sont i.i.d. selon une densité $p$.
• Après $\tau^*$, elles sont i.i.d. selon une densité différente $q$ ($p \neq q$).
• Objectif : Détecter le moment $\tau^*$ le plus rapidement possible (minimiser le délai de détection) tout en contrôlant le taux de fausses alarmes.
• Contrainte majeure : L'approche doit être non-paramétrique. Les auteurs ne font aucune hypothèse sur la forme de $p$ et $q$ (contrairement aux méthodes paramétriques qui supposent souvent des distributions gaussiennes ou des décalages de moyenne). De plus, les méthodes doivent éviter le calcul coûteux de la fonction de partition (intégrale de normalisation) souvent nécessaire dans les modèles paramétriques classiques.

2. Méthodologie

L'approche proposée combine l'apprentissage en ligne (Online Learning) et l'estimation de scores (Score-based estimation).

A. Cadre d'apprentissage en ligne (Online Learning)

Le problème est reformulé comme un jeu de prédiction avec conseil d'experts :

• Classe d'experts : Une classe de référence de densités paramétriques $\mathcal{P} = \{p_\theta : \theta \in \mathbb{R}^d\}$ de la forme exponentielle : $\log p_\theta(x) = \Psi(x)^\top \theta - \Phi(\theta)$.
• Fonction de perte : Au lieu d'utiliser la perte logarithmique négative (qui nécessite le calcul de $\Phi(\theta)$, une intégrale difficile en haute dimension), les auteurs utilisent la divergence de Fisher.
  • Grâce à l'identité de Green, ils construisent une estimation sans biais de la divergence de Fisher basée uniquement sur les gradients de $\log p_\theta$ et le Laplacien de $\Psi$.
  • La perte au temps $t$ est quadratique : $\ell_t(\theta) = \frac{1}{2}\theta^\top A_t \theta - b_t^\top \theta$, où $A_t$ et $b_t$ sont dérivés des observations $X_t$.

B. Algorithmes de prédiction

Deux prédicteurs sont utilisés et comparés :

1. Prédicteur à Moyenne Pondérée Exponentiellement (EW - Exponentially Weighted) :
   • Il suit le "meilleur expert statique" sur toute la séquence.
   • Il est efficace tant que la distribution ne change pas (régime pré-changement).
2. Prédicteur à Partage Fixe (FS - Fixed Share) :
   • C'est une version adaptée au cas d'un nombre infini d'experts et de pertes quadratiques.
   • Il est conçu pour suivre le "meilleur expert" qui peut changer de stratégie (switch) à un moment donné.
   • Il utilise un prior spécial sur les séquences d'experts (combinaison de rester sur le même expert ou de passer à un nouvel expert tiré d'une distribution a priori).

C. Statistique de test

La détection repose sur la différence de perte cumulative entre les deux prédicteurs :
$$\hat{S}_t = \hat{L}_{1:t}^{EW} - \hat{L}_{1:t}^{FS}$$

• Avant le changement ($t \le \tau^*$) : Les deux prédicteurs performent de manière similaire car la distribution est stationnaire. $\hat{S}_t$ reste faible.
• Après le changement ($t > \tau^*$) : Le prédicteur EW reste "collé" à l'ancien expert optimal (mémoire du passé), tandis que le prédicteur FS s'adapte rapidement à la nouvelle distribution. La perte de FS devient bien inférieure à celle de EW, faisant croître $\hat{S}_t$.
• Décision : Si $\hat{S}_t$ dépasse un seuil $z$, un changement est détecté.

3. Contributions Clés

1. Algorithme Non-Paramétrique en Ligne : Proposition d'un algorithme de détection de changement qui ne nécessite pas de connaître la forme exacte des densités $p$ et $q$, mais seulement que leurs scores (gradients du log) soient lisses et approximables par un système de fonctions.
2. Extension du Fixed Share aux Experts Infinites : Développement d'une version du prédicteur "Fixed Share" (Herbster & Warmuth, 1998) spécifiquement pour un espace d'experts continu ($\mathbb{R}^d$) et des pertes quadratiques, avec des formules de récurrence explicites et efficaces.
3. Bornes Théoriques Non-Asymptotiques :
   • Dérivation de bornes de haute probabilité pour la statistique de test $\hat{S}_t$ dans les régimes pré- et post-changement.
   • Preuve que sous l'hypothèse de nullité (pas de changement), $\hat{S}_t$ est borné par $O(\log^3 \tau^*)$.
   • Preuve qu'après un changement, $\hat{S}_t$ croît rapidement, garantissant une détection rapide.
4. Évitement du Calcul d'Intégrales : L'utilisation de la divergence de Fisher et de l'identité de Green permet d'éviter le calcul numérique de la fonction de partition $\Phi(\theta)$, rendant l'algorithme applicable à des distributions complexes où l'intégrale n'a pas de forme close.

4. Résultats Expérimentaux

Les auteurs ont évalué l'algorithme (désigné Algorithm 3.1) sur des données synthétiques et réelles, en le comparant à quatre méthodes de référence (FLH, FALCON, KLIEP, M-statistic).

• Données Synthétiques (Gaussiennes) :
  • Tests sur des décalages de moyenne et de variance en dimensions 1 et 3.
  • L'algorithme proposé détecte les changements avec un délai très court (parfois < 2 observations) et un taux de fausses alarmes nul, surpassant souvent les concurrents, notamment sur les changements de variance.
• Données Réelles :
  • Détection d'activité humaine (WISDM) : Données d'accéléromètres de smartphones. L'algorithme détecte les changements d'activité avec un délai moyen de 15.43 (contre 16.29 pour FLH et 25.9 pour M-statistic) et moins de fausses alarmes.
  • Détection de parole (CENSREC-1-C) : Données audio avec bruit. L'algorithme maintient une excellente performance même avec un rapport signal/bruit faible (SNR 15), là où d'autres méthodes génèrent des fausses alarmes ou ont des délais élevés.
  • Occupation de pièce (Room Occupancy) : Données de capteurs (température, CO2, etc.). L'algorithme est compétitif avec FALCON en termes de délai, tout en ayant un nombre de fausses alarmes comparable.

5. Signification et Impact

• Robustesse : La méthode est robuste aux changements de distribution complexes (moyenne, variance, forme) sans hypothèse de modèle fort (comme la gaussienneté).
• Efficacité Computationnelle : Bien que la complexité soit en $O(d^3 T^2)$ ou $O(d^3 T^3)$ selon le taux d'apprentissage, elle reste gérable pour des dimensions modérées et offre un compromis performance/coût supérieur aux méthodes à noyaux (Kernel methods) qui nécessitent souvent des fenêtres glissantes et des calculs de matrices de Gram.
• Théorie Solide : L'article fournit des garanties théoriques rigoureuses (bornes non-asymptotiques) sur le comportement de la statistique de test, ce qui est rare pour les méthodes non-paramétriques en ligne.
• Innovation : L'adaptation du concept de "Fixed Share" à un espace d'experts infini via des pertes quadratiques et la divergence de Fisher ouvre une nouvelle voie pour l'apprentissage en ligne adaptatif dans des environnements non stationnaires.

En résumé, cet article propose une solution élégante et théoriquement fondée pour la détection de changements en temps réel, combinant la flexibilité des méthodes non-paramétriques avec la rapidité de convergence des algorithmes d'apprentissage en ligne.