Sequential Change Detection Under Markov Setup With Unknown Prechange And Postchange Distributions

1. Problématique

L'article aborde le problème de la détection de changement séquentielle (Sequential Change Detection) dans un contexte où les distributions statistiques des données avant et après le changement sont inconnues.

Contrairement aux travaux antérieurs qui supposaient souvent des sources indépendantes et identiquement distribuées (i.i.d.) ou des distributions connues, ce travail se concentre sur des sources markoviennes stationnaires et ergodiques d'ordre fini. Le défi principal est de concevoir un algorithme capable de détecter un changement de régime (d'une distribution pré-changement $\mu_0$ à une distribution post-changement $\mu_1$) sans connaître a priori ni $\mu_0$ ni $\mu_1$, tout en garantissant des performances optimales asymptotiques.

2. Méthodologie

Les auteurs proposent une extension de l'algorithme de Page (CUSUM) et des travaux antérieurs de Jacob, Bansal et Malik, adaptés aux sources avec mémoire (Markov). La méthodologie se décompose en trois étapes clés :

A. Estimation de la distribution pré-changement ($\mu_0$)

Puisque $\mu_0$ est inconnue, l'algorithme utilise une phase d'apprentissage initiale (séquence de formation) de longueur $n_0$.

• À partir des $n_0$ premiers symboles $x_1, \dots, x_{n_0}$, une estimation empirique $\hat{\mu}_0$ est calculée.
• Pour une source markovienne d'ordre 1, cette estimation repose sur les fréquences d'apparition des symboles et des paires de symboles (transitions) :
  $$\hat{\mu}_0(b, a) = \frac{N(b, a | x_1^{n_0})}{n_0 - 1}$$
  $$\hat{\mu}_0(b) = \frac{N(b | x_1^{n_0})}{n_0}$$
• L'hypothèse est que $n_0$ est suffisamment grand pour que $\hat{\mu}_0$ converge vers $\mu_0$ (théorème ergodique).

B. Utilisation de codes universels pour la distribution post-changement ($\mu_1$)

Pour la distribution post-changement $\mu_1$ (inconnue), l'algorithme ne tente pas de l'estimer paramétriquement. Il utilise à la place un code universel fortement ponctuel (Strongly Pointwise Universal Code), noté $L(\cdot)$, tel que les codes Lempel-Ziv (LZ-77, LZ-78) ou le Context Tree Weighting (CTW).

• La longueur du code $L(x)$ sert d'estimateur de la négative de l'entropie, remplaçant le terme $\log \mu_1(x)$ dans le rapport de vraisemblance classique.

C. Le Test CUSUM Modifié

L'algorithme proposé (Test 3) fonctionne comme suit :

1. Phase d'estimation : Collecter $n_0$ échantillons pour calculer $\hat{\mu}_0$.
2. Phase de détection : Pour chaque nouvelle séquence de longueur $n$ ($x_{n_0+1}, \dots, x_{n_0+n}$), calculer la statistique de test :
   $$\max_{1 \le k \le n} \left( -L(x_{n_0+k}^{n_0+n}) - \log \hat{\mu}_0(x_{n_0+k}^{n_0+n}) - n\lambda \right) \ge \log \gamma$$
   où :
   • $L(\cdot)$ est la longueur du code universel (estimation de $\mu_1$).
   • $\log \hat{\mu}_0(\cdot)$ est l'estimation de la distribution pré-changement.
   • $\lambda$ est un paramètre de dérive (drift) choisi tel que $D(\mu_0 || \hat{\mu}_0) < \lambda < D(\mu_1 || \hat{\mu}_0)$.
   • $\gamma$ est le seuil de décision.

Si l'inégalité est satisfaite, le test s'arrête et un changement est déclaré.

3. Contributions Clés

1. Extension au cadre Markovien : L'article généralise les résultats de 2022 (conçus pour des sources i.i.d.) aux sources markoviennes stationnaires et ergodiques satisfaisant les conditions de mélange de Berk.
2. Double inconnue : C'est l'une des premières approches traitant simultanément l'incertitude sur les distributions pré et post-changement dans un cadre markovien, en combinant l'estimation empirique pour $\mu_0$ et le codage universel pour $\mu_1$.
3. Preuve d'optimalité asymptotique : Les auteurs démontrent que leur test est asymptotiquement optimal lorsque le taux de fausse alarme tend vers zéro.

4. Résultats Théoriques et Preuves

Les auteurs établissent plusieurs bornes et théorèmes fondamentaux :

• Borne sur la probabilité de fausse alarme (Lemme 3) :
  La probabilité que le test s'arrête alors qu'aucun changement ne s'est produit (sous $\mu_0$) est bornée par :
  $$P_0(\text{erreur}) \le \frac{\alpha}{\beta_1 (2^{\lambda - \log \beta_1 - 1}) \beta_2} + \epsilon_0$$
  où $\beta_1, \beta_2 \to 1$ et $\epsilon_0 \to 0$ lorsque la taille de l'échantillon d'apprentissage $n_0 \to \infty$. Cela montre que l'erreur peut être contrôlée arbitrairement en augmentant $n_0$.

• Arrêt presque sûr sous l'hypothèse alternative (Lemme 4) :
  Sous la distribution post-changement $\mu_1$, le test s'arrête avec une probabilité de 1, à condition que $\lambda < D(\mu_1 || \hat{\mu}_0)$.

• Optimalité Asymptotique (Théorème 6) :
  Le temps d'arrêt moyen $E_1(M)$ du test proposé satisfait, lorsque le seuil $\gamma \to \infty$ :
  $$E_1(M) \sim (1+\vartheta) \inf_{S \in \mathcal{S}_\gamma} E_1(S)$$
  où $\inf E_1(S)$ est la borne inférieure théorique (critère de Lorden) pour tout test de détection de changement. Le terme $\vartheta$ peut être rendu arbitrairement proche de 0.
  Cela signifie que le test proposé atteint la limite de performance optimale connue pour les sources markoviennes, même avec des distributions inconnues.

5. Signification et Impact

• Rigueur Mathématique : L'article fournit une analyse rigoureuse des performances en utilisant les conditions de mélange de Berk et la convergence rapide (1-quick convergence) des rapports de vraisemblance, essentiels pour les processus dépendants.
• Applicabilité Réelle : En éliminant la nécessité de connaître les distributions a priori, cette méthode est directement applicable à des scénarios réels complexes tels que la surveillance de la qualité industrielle, la détection de pannes dans les réseaux de communication, ou la cybersécurité, où les modèles de bruit et de signal changent dynamiquement et sont mal définis.
• Fondation pour le Futur : Les auteurs suggèrent que leurs résultats pourraient être étendus au cadre plus général de Lai (affaiblissant l'hypothèse d'indépendance entre les régimes pré et post-changement), ouvrant la voie à des applications sur des processus encore plus complexes.

En résumé, cet article réussit à combiner l'estimation non-paramétrique (empirique) et le codage universel pour résoudre un problème de détection de changement difficile dans un cadre markovien, prouvant que l'optimalité asymptotique est maintenue malgré l'incertitude totale des distributions.