Post-detection inference for sequential changepoint localization

1. Problématique

L'article aborde un défi fondamental mais largement négligé dans l'analyse des changements séquentiels : l'inférence post-détection.
Dans un cadre séquentiel, des observations $X_1, X_2, \dots$ arrivent dans le temps. À un instant inconnu $T$ (le point de changement), la distribution des données passe d'une classe pré-changement $\mathcal{P}_0$ à une classe post-changement $\mathcal{P}_1$. Un algorithme de détection séquentielle $\mathcal{A}$ arrête le processus à un temps d'arrêt $\tau$ (dépendant des données) lorsqu'il détecte un changement.

Le problème central est le suivant : une fois que l'algorithme $\mathcal{A}$ a déclenché une alarme à $\tau$, comment construire un ensemble de confiance pour le point de changement réel $T$ ?

• Défi majeur : Pour les algorithmes avec une longueur moyenne de fonctionnement (ARL) finie (ce qui est le cas standard pour la détection rapide), il est impossible d'obtenir une couverture inconditionnelle (c'est-à-dire que $T \in C$ avec probabilité $1-\alpha$) car l'algorithme peut s'arrêter par erreur avant que le changement ne se produise ($\tau < T$).
• Objectif : Construire un ensemble de confiance $C \subseteq \{1, \dots, \tau\}$ garantissant une couverture conditionnelle :
  $$\mathbb{P}(T \in C \mid \tau \ge T) \ge 1 - \alpha$$
  Cela signifie que l'ensemble de confiance est valide uniquement dans les cas où l'algorithme s'est arrêté après le vrai changement.

2. Méthodologie

Les auteurs proposent un cadre général et non paramétrique pour construire ces ensembles de confiance, agissant comme un « wrapper » (enveloppe) autour de n'importe quel algorithme de détection existant (CUSUM, e-detecteurs, méthodes ML, etc.).

A. Dualité Tests / Intervalles de Confiance

La méthode repose sur l'inversion de tests d'hypothèses. Pour chaque candidat $t \le \tau$, on teste l'hypothèse nulle $H_{0,t}$ : « Le changement s'est produit à l'instant $t$ ».

• Si le test rejette $H_{0,t}$, alors $t$ est exclu de l'ensemble de confiance.
• L'ensemble de confiance est défini comme : $C = \{t \le \tau : H_{0,t} \text{ n'est pas rejeté}\}$.

B. Statistique de Test et Processus E (e-processes)

Pour tester $H_{0,t}$ sans connaître les distributions exactes (cadre non paramétrique), les auteurs utilisent des processus e (e-processes), des outils puissants pour l'inférence valide à tout moment (anytime-valid).

• Processus e avant ($R^{(t)}_n$) : Accumule la preuve en faveur du post-changement $\mathcal{P}_1$ contre le pré-changement $\mathcal{P}_0$ sur la séquence $X_t, \dots, X_{\tau}$.
• Processus e arrière ($S^{(t)}_n$) : Accumule la preuve en faveur du pré-changement $\mathcal{P}_0$ contre le post-changement $\mathcal{P}_1$ sur la séquence $X_1, \dots, X_{t-1}$.
• Statistique $M_t$ : La statistique de test pour l'instant $t$ est le maximum des deux processus e sur les segments pertinents.
  $$M_t = \max \left( \max_{t \le n \le \tau} R^{(t)}_n, \max_{1 \le n \le t-1} S^{(t)}_n \right)$$

C. Approches Universelle et Adaptative

Le papier propose deux stratégies principales pour déterminer le seuil de rejet :

1. Méthode Universelle (Seuil Universel) :

   • Utilise un seuil fixe basé sur une borne théorique (Théorème 1) : $M_t < \frac{2}{\alpha r_t}$, où $r_t$ est un estimateur sans biais de la probabilité que l'algorithme ne s'arrête pas avant $t$ sous l'hypothèse de non-changement.
   • Avantages : Non paramétrique, ne nécessite aucune hypothèse sur la forme des distributions, valide pour tout algorithme de détection.
   • Extension : Peut gérer des classes pré-changement composites ($\mathcal{P}_0$) via l'hypothèse d'une distribution défavorable (LFD - Least Favorable Distribution).

2. Méthode Adaptative (Simulation) :

   • Utilise des simulations de Monte Carlo pour estimer la distribution exacte de la statistique $M_t$ sous l'hypothèse nulle.
   • Permet d'utiliser des seuils adaptatifs (plus serrés) et de gérer des données dépendantes (Markoviennes, etc.).
   • S'applique aux cadres paramétriques (connus ou composites) et permet d'estimer les paramètres pré et post-changement ($\theta_0, \theta_1$) en plus de $T$.

3. Contributions Clés

1. Première méthode générale non asymptotique : C'est la première méthode qui fournit des garanties de couverture non asymptotiques (valides pour des échantillons finis) pour la localisation de changements, indépendamment de l'algorithme de détection utilisé.
2. Indépendance vis-à-vis de l'algorithme de détection : La méthode fonctionne comme une boîte noire. Elle ne nécessite pas de connaître les détails internes de l'algorithme $\mathcal{A}$, ni même qu'il soit basé sur des rapports de vraisemblance.
3. Gestion des classes composites : Extension robuste aux cas où les distributions pré et post-changement sont des classes de distributions (paramétriques ou non) plutôt que des distributions uniques connues.
4. Inférence sur les paramètres : En plus de localiser $T$, la méthode permet de construire des intervalles de confiance pour les paramètres inconnus des distributions pré et post-changement.
5. Validité pour données dépendantes : La méthode adaptative (basée sur la simulation) est capable de gérer des données séquentielles dépendantes, là où les méthodes classiques échouent.

4. Résultats Expérimentaux

Les auteurs valident leur approche sur plusieurs scénarios (simulations et données réelles) :

• Couverture : Les ensembles de confiance obtenus respectent la couverture conditionnelle cible ($1-\alpha$) dans tous les cas, y compris pour des classes composites et des distributions non paramétriques (ex: mélange de Gaussiennes et Cauchy).
• Taille des intervalles : Les intervalles sont de taille raisonnable. La méthode adaptative tend à produire des intervalles légèrement plus étroits que la méthode universelle, mais cette dernière reste compétitive et beaucoup plus simple à implémenter.
• Comparaison avec l'état de l'art : Comparée aux méthodes existantes (comme celles de Wu, 2007), qui sont asymptotiques et limitées aux familles exponentielles avec CUSUM, la méthode proposée évite le sous-recouvrement (undercoverage) observé dans les méthodes asymptotiques et offre une validité en échantillon fini.
• Cas réel : Application réussie sur le jeu de données SST-2 (analyse de sentiments) pour localiser un changement brutal dans la polarité des critiques de films.

5. Signification et Impact

Cet article comble une lacune majeure dans la littérature sur l'analyse séquentielle. Jusqu'alors, la recherche se concentrait presque exclusivement sur la détection (quand s'arrêter ?), négligeant l'inférence (où s'est produit le changement ?).

• Pratique : La méthode est applicable dans des domaines critiques comme le contrôle qualité, la cybersécurité, la finance et l'analyse de réseaux sociaux, où comprendre quand et comment un changement s'est produit est aussi important que de le détecter.
• Théorique : Elle établit un nouveau standard pour l'inférence post-détection, prouvant qu'il est possible d'obtenir des garanties rigoureuses sans hypothèses restrictives sur les données ou l'algorithme de détection, en utilisant la dualité entre tests et ensembles de confiance conditionnels.

En résumé, ce travail fournit la première boîte à outils théoriquement fondée, non paramétrique et largement applicable pour localiser avec confiance un changement après sa détection, quelle que soit la complexité des données ou de l'algorithme utilisé pour la détection initiale.