Résumé technique : CHASM – Détection en ligne de points de rupture dans la dépendance temporelle et inter-variable

Définition du problème

L'article aborde le défi de la détection en ligne de points de rupture dans les séries temporelles multivariées, en se concentrant spécifiquement sur les changements de dépendance temporelle et inter-variable plutôt que sur les changements de statistiques marginales (par exemple, la moyenne ou la variance). Dans de nombreuses applications (finance, neurosciences, climat), le processus générateur sous-jacent est un processus autorégressif vectoriel (VAR) où la matrice de transition $\Theta$ encode la dynamique du système. Un changement dans $\Theta$ peut être subtil et ne pas se manifester dans la distribution marginale des variables individuelles, rendant les méthodes standard qui surveillent les statistiques marginales inefficaces.

Le problème est formulé comme la détection d'un point de rupture unique $\tau$ dans un flux d'observations $x_t \in \mathbb{R}^d$ où la matrice de transition passe de $\Theta_0$ à $\Theta_1$. La méthode doit opérer dans un régime en ligne, traitant chaque observation en temps constant avec une mémoire indépendante de la longueur de la séquence, sans s'appuyer sur des hypothèses paramétriques concernant la distribution du bruit.

Méthodologie : CHASM

Les auteurs proposent CHASM (Complex Hungarian-Aligned Spectrum Monitoring), une méthode non supervisée et non paramétrique qui surveille les valeurs propres dominantes d'un opérateur de dynamique estimé de manière récursive. L'approche se compose de trois étapes principales :

1. Estimation en ligne de la dynamique

CHASM utilise les Moindres Carrés Récursifs (RLS) pour estimer la matrice de transition $\Theta_n$ en ligne, correspondant à une version en ligne de la Décomposition en Modes Dynamiques (DMD).

• L'estimateur utilise un facteur d'oubli $\rho \in (0, 1]$ pour pondérer les observations récentes, permettant à l'algorithme de s'adapter aux changements.
• Contrairement aux méthodes qui régularisent lors de l'estimation (par exemple, via une pénalisation $\ell_1$), CHASM laisse l'estimation sans contrainte et applique une troncature de rang comme étape post-estimation.
• À chaque étape, l'algorithme calcule la décomposition spectrale tronquée de $\Theta_n$, en conservant les $r$ valeurs propres dominantes $\lambda_n \in \mathbb{C}^r$. Cela transforme le flux réel multivarié en une séquence de résumés spectraux complexes.

2. Alignement optimal des valeurs propres

Un défi critique dans la surveillance des valeurs propres est l'invariance par permutation des décompositions spectrales ; les solveurs numériques ne garantissent pas un ordre cohérent des valeurs propres d'un pas de temps à l'autre, ce qui entraîne des discontinuités artificielles.

• CHASM résout ce problème en formulant l'alignement des vecteurs de valeurs propres consécutifs $\lambda_{n-1}$ et $\lambda_n$ comme un problème de transport optimal.
• Les auteurs démontrent que le couplage optimal est une application de permutation qui minimise la distance de Wasserstein 2 au carré entre les mesures empiriques des valeurs propres.
• Cela est résolu efficacement via un problème d'affectation linéaire (en utilisant l'algorithme hongrois ou ses variantes), réduisant la complexité de factorielle à polynomiale ($O(r^3)$). Cela garantit que les trajectoires des valeurs propres individuelles sont continues et interprétables.

3. Détection de points de rupture multivariée complexe

La séquence alignée de vecteurs de valeurs propres est traitée comme une série temporelle multivariée à valeurs complexes.

• La méthode suit les différences du premier ordre (vitesse spectrale) $v_n = \lambda_n - \lambda_{n-1}$. En stationnarité, ces vitesses fluctuent autour de zéro ; un point de rupture induit un décalage directionnel cohérent.
• Pour gérer la nature complexe des données, CHASM étend le schéma de Moyenne Mobile Pondérée Exponentiellement Multivariée (MEWMA). Il construit un vecteur augmenté $z_n = (v_n, v_n^*)$ pour tenir compte à la fois de la covariance hermitienne et de la pseudo-covariance (impropre) de la séquence complexe.
• Une statistique de détection $D_n^2$ est définie comme la distance de Mahalanobis au carré de l'état augmenté par rapport à sa moyenne. Un point de rupture est déclaré lorsque $D_n^2$ dépasse un seuil $h$.

Contributions clés

1. Surveillance directe de l'opérateur : CHASM est la première méthode de détection en ligne de points de rupture à suivre directement le spectre de l'opérateur (valeurs propres) d'un opérateur de dynamique, plutôt que de s'appuyer sur des erreurs de reconstruction indirectes ou des fonctionnels scalaires qui peuvent éliminer des informations structurelles.
2. Alignement de valeurs propres complexes : L'article introduit une méthode novatrice pour aligner des vecteurs de valeurs propres complexes consécutifs via un transport optimal (affectation linéaire), résolvant l'ambiguïté de permutation inhérente aux décompositions spectrales numériques.
3. Schéma de détection à valeurs complexes : Il propose une extension de MEWMA au domaine complexe, utilisant des vecteurs augmentés pour capturer l'ensemble des statistiques du second ordre (covariance et pseudo-covariance) des vitesses spectrales.
4. Garanties théoriques : Les auteurs établissent la consistance et caractérisent le biais de l'estimateur DMD en ligne sous le modèle VAR canonique avec des hypothèses minimales (moments finis, aucune distribution de bruit paramétrique). Ils révèlent un compromis entre la précision de l'estimation et la sensibilité de détection contrôlé par le facteur d'oubli $\rho$.
5. Performance empirique : CHASM démontre des performances compétitives ou supérieures par rapport aux références modernes (incluant des méthodes basées sur les sous-espaces, de haute dimension et bayésiennes) à travers diverses distributions de bruit synthétiques (Gaussien, à queues lourdes, contaminé) et modalités réelles (mouvement, image, texte, vidéo).

Résultats

• Données synthétiques : CHASM atteint systématiquement les scores F1 les plus élevés sur des processus VAR bivariés et de haute dimension avec diverses distributions de bruit (incluant la loi de Student $t$ et la contamination de Huber). Il maintient sa robustesse même lorsque le rang est mal spécifié ou que la dynamique est de plein rang, là où les concurrents reposant sur des hypothèses de parcimonie (par exemple, Tian & Safikhani) se dégradent.
• Données réelles : La méthode est évaluée sur cinq jeux de données : HASC (accélérométrie), CIFAR-100 (images), 20 Newsgroups (texte), UCF-Crime (vidéo) et WikiSection (texte au niveau des tokens). CHASM est la seule méthode à performer de manière cohérente sur toutes les modalités, excellant particulièrement dans des contextes de dynamiques temporelles non linéaires (UCF-Crime) et de changements i.i.d. par morceaux (CIFAR-100, 20 Newsgroups).
• Efficacité : L'algorithme opère avec une complexité temporelle de $O(d^2 r)$ et une complexité spatiale de $O(d^2)$ par étape, le rendant adapté aux flux de données de haute dimension. Il évite le coût cubique des décompositions spectrales complètes en utilisant des mises à jour tronquées par rang.

Importance et affirmations

L'article affirme que CHASM fournit une approche directe, interprétable et computationnellement efficace pour détecter les changements dans la structure dynamique des séries temporelles multivariées. En surveillant directement le spectre de l'opérateur, il capture les changements de stabilité et de comportement oscillatoire que les statistiques marginales manquent.

Les auteurs soulignent que la méthode est non supervisée et ne nécessite aucune hypothèse distributionnelle au-delà de moments finis, la rendant facilement déployable dans divers domaines scientifiques où les caractéristiques du bruit sont inconnues ou non gaussiennes. Bien que l'analyse théorique soit ancrée dans le cadre VAR, les résultats empiriques démontrent que CHASM se généralise efficacement à des contextes non VAR, y compris des données complexes de vidéo et de texte, suggérant son utilité en tant qu'outil polyvalent pour la surveillance des systèmes dynamiques. Le travail met en évidence l'importance de traiter l'invariance par permutation des valeurs propres et les propriétés statistiques spécifiques des séquences à valeurs complexes dans les tâches de détection en ligne.