Anomaly detection using surprisals

Ce papier propose un cadre unifié pour la détection d'anomalies basé sur les surprisales, qui réduit le problème complexe à l'estimation de la queue d'une distribution univariée et offre des garanties statistiques robustes même en cas de mauvaise spécification du modèle.

L'essentiel

🕵️‍♂️ Détecter l'Inattendu : Une nouvelle méthode pour repérer les anomalies

Imaginez que vous êtes un gardien de zoo. Votre travail consiste à surveiller des milliers d'animaux. La plupart se comportent de manière prévisible : les lions dorment, les singes sautent, les girafes mangent des feuilles. Mais soudain, vous voyez un lion qui essaie de voler un singe, ou un singe qui fait du yoga sur une branche. C'est une anomalie.

Le problème, c'est que les méthodes traditionnelles pour détecter ces anomalies sont souvent comme des règles rigides : "Si l'animal mesure plus de 2 mètres, c'est bizarre" ou "Si l'animal est rouge, c'est suspect". Ces règles fonctionnent mal si l'animal est un peu plus grand que la moyenne mais pas énorme, ou s'il est d'une couleur inhabituelle mais pas rouge.

Les auteurs de ce papier, Rob Hyndman et David Frazier, proposent une nouvelle approche basée sur un concept fascinant : la "Surprise" (ou Surprisal).

1. Le concept de "Surprise" : Mesurer l'étonnement

Au lieu de mesurer la taille ou la couleur, cette méthode demande une seule question à chaque observation : "À quel point cela est-il surprenant ?"

• L'analogie du livre de cuisine : Imaginez que vous avez un livre de cuisine très fiable qui vous dit ce que les gens cuisinent d'habitude.
  • Si vous voyez quelqu'un faire une omelette, ce n'est pas surprenant (probabilité élevée, "surprise" faible).
  • Si vous voyez quelqu'un faire une omelette avec des bananes, c'est un peu surprenant.
  • Si vous voyez quelqu'un faire une omelette avec des pneus de voiture, c'est extrêmement surprenant (probabilité très faible, "surprise" élevée).

Dans ce papier, ils calculent mathématiquement ce niveau de "surprise" pour chaque donnée. Plus la "surprise" est grande, plus l'observation est potentiellement une anomalie.

2. Le problème : Et si notre livre de cuisine est faux ?

Le défi, c'est que nous ne connaissons jamais la "vérité" absolue. Nous utilisons un modèle (notre livre de cuisine) qui peut être imparfait.

• Si notre modèle dit que les gens ne mangent jamais de bananes, mais qu'en réalité, ils en mangent souvent, notre modèle est faux.
• Les anciennes méthodes échouent souvent ici : si votre modèle est faux, il va soit ignorer de vraies anomalies, soit crier au loup pour des choses normales.

La grande innovation de ce papier : Ils montrent que même si votre modèle est imparfait (voire "faux"), vous pouvez toujours trouver les vraies anomalies, à condition de ne pas faire confiance aveuglément au modèle pour calculer la probabilité exacte.

3. La solution : Deux méthodes pour vérifier la "Surprise"

Une fois qu'ils ont calculé le niveau de "surprise" de chaque observation, ils utilisent deux techniques astucieuses pour décider si c'est vraiment une anomalie :

A. La méthode du "Classement" (Empirique)
Imaginez que vous avez une liste de 1000 personnes classées par ordre de "surprise", du moins surpris au plus surpris.

• Au lieu de dire "Cette personne a un score de 9,5, donc c'est bizarre", vous dites : "Cette personne est dans le top 1% des plus surprises".
• L'analogie : C'est comme une course. Peu importe si votre chronomètre est un peu décalé (le modèle est imparfait), tant que l'ordre des coureurs est correct, vous savez qui est arrivé dernier. Si quelqu'un est dans le top 1% des plus lents, c'est un record, même si votre montre n'est pas parfaite.

B. La méthode des "Extrêmes" (Théorie des valeurs extrêmes)
Parfois, il n'y a pas assez de données pour faire un classement précis. Alors, ils regardent seulement les cas les plus extrêmes (les plus "surprenants").

• L'analogie : Imaginez que vous étudiez les vagues à la plage. Vous ne pouvez pas prédire chaque vague, mais vous savez que les plus grosses vagues suivent une certaine loi mathématique (comme une courbe spécifique). Même si votre modèle de la mer n'est pas parfait, si vous regardez les 10 plus grosses vagues, vous pouvez prédire à quel point la prochaine pourrait être géante.
• Ils utilisent une formule mathématique (la distribution de Pareto généralisée) pour estimer la probabilité que la "surprise" soit encore plus grande que ce qu'on a vu.

4. Pourquoi c'est génial ? (Les résultats)

Les auteurs ont testé leur méthode sur deux exemples concrets :

1. Les taux de mortalité en France : Ils ont détecté des années où la mortalité a explosé (guerres, épidémies de choléra, grippe espagnole) même en utilisant un modèle statistique imparfait. Leurs "radars de surprise" ont sonné au bon moment.
2. Le Cricket : Ils ont cherché des batteurs de cricket qui avaient un nombre anormal de fois où ils n'ont pas été éliminés ("not out"). Ils ont trouvé Jimmy Anderson, un joueur qui, bien que n'étant pas un grand batteur, réussissait à rester à la batte très longtemps grâce à sa défense. C'était une anomalie que les méthodes classiques auraient manquée.

En résumé

Ce papier nous dit : "Ne vous inquiétez pas si votre modèle n'est pas parfait."

Au lieu de chercher à prédire exactement ce qui va se passer, ils se concentrent sur l'ordre de la surprise.

• Si vous avez un modèle approximatif, vous pouvez quand même trier vos données du "moins surprenant" au "plus surprenant".
• Ensuite, vous regardez simplement les extrêmes de cette liste.
• Cela permet de repérer des anomalies cachées (comme des pics de mortalité ou des joueurs de cricket atypiques) sans avoir besoin de connaître la vérité absolue sur le monde.

C'est comme si vous aviez un détecteur de mensonges qui ne vous dit pas exactement ce que la personne pense, mais qui vous dit avec certitude : "Hé, celle-ci est beaucoup plus bizarre que les autres !" Et c'est souvent tout ce dont on a besoin pour détecter une anomalie.

Résumé technique

Voici un résumé technique détaillé de l'article « Anomaly detection using surprisals » de Rob J. Hyndman et David T. Frazier, rédigé en français.

1. Problématique

Les méthodes de détection d'anomalies actuelles souffrent souvent de deux limites majeures :

1. Manque de fondement théorique : Elles reposent fréquemment sur des règles ad hoc ou des hypothèses distributionnelles fortes qui ne sont pas vérifiées en pratique.
2. Biais vers les queues de distribution : La plupart des approches se concentrent sur les événements extrêmes (les queues), manquant ainsi les anomalies dites « inliers » qui se situent dans des zones de faible densité entre des modes (par exemple, dans des distributions multimodales).

De plus, les méthodes basées sur la distance peinent à gérer les distributions asymétriques ou à queues lourdes. L'objectif de cet article est de proposer un cadre unifié et robuste pour la détection d'anomalies, capable de fonctionner même lorsque le modèle de probabilité sous-jacent est mal spécifié.

2. Méthodologie

L'approche proposée transforme le problème de détection d'anomalies (potentiellement multivarié) en un problème univarié d'estimation de la queue d'une distribution de surprisale.

A. Définition de la Surprisale

Pour une observation $y_i$ issue d'une distribution $F$ de densité généralisée $f$, la surprisale est définie comme :
$$s_i = -\log f(y_i)$$
Une valeur élevée de $s_i$ indique une observation peu probable (surprenante). Contrairement aux scores de log-likelihood classiques, le terme « surprisale » met l'accent sur le caractère inhabituel de l'observation.

B. Calcul du Score d'Anomalie

Au lieu d'estimer directement la probabilité dans l'espace des données, l'article propose de calculer la probabilité d'observer une surprisale supérieure ou égale à celle observée :
$$p_i = \Pr(S \ge s_i) = 1 - G(s_i^-)$$
où $G$ est la fonction de répartition de la variable aléatoire $S = -\log f(Y)$. Une observation est considérée comme une anomalie si $p_i < \alpha$ (où $\alpha$ est le taux de faux positifs souhaité).

C. Estimation des Probabilités de Queue

Puisque la vraie distribution $F$ est inconnue, les auteurs proposent trois approches pour estimer les $p_i$, en utilisant une distribution supposée $F$ (qui peut être mal spécifiée) pour calculer les $s_i$, puis en estimant la queue de la distribution des $s_i$ :

1. Approche Empirique : Utilisation de la fonction de répartition empirique des surprisales observées.
   • Condition de validité : L'hypothèse 2.1 stipule que la vraie distribution et la distribution ajustée doivent avoir un ordre de queue similaire (une transformation strictement croissante relie les deux dans la queue supérieure). Si l'ordre est préservé, l'estimateur empirique offre des garanties de confiance finies (via l'inégalité de Dvoretzky–Kiefer–Wolfowitz).
2. Approche par Théorie des Valeurs Extrêmes (GPD) : Ajustement d'une Distribution de Pareto Généralisée (GPD) aux $k$ plus grandes valeurs de surprisale.
   • Fondement théorique : Sous des conditions faibles sur les queues de la surprisale (sous-Gaussienne, sous-exponentielle ou à moments polynomiaux), le maximum des surprisales converge vers une loi de valeurs extrêmes (Gumbel, Fréchet ou Weibull inversé).
   • Robustesse : Cette méthode est particulièrement robuste si le modèle supposé sous-estime la lourdeur de la queue (modèle à queue lourde appliqué à des données à queue légère), mais moins si le modèle sous-estime la lourdeur réelle.

D. Distributions Conditionnelles

Le cadre s'étend aux modèles conditionnels (ex: régression). La surprisale est calculée sur la distribution conditionnelle $f(Z|X)$. Les résultats théoriques restent valables pour des vecteurs de conditionnement fixes, permettant de détecter des anomalies dans les résidus ou les combinaisons de variables explicatives et de réponse.

3. Contributions Clés

• Cadre Unifié : Définition d'une anomalie comme une observation de faible probabilité, applicable aux données univariées, multivariées, discrètes, continues ou mixtes.
• Robustesse à la Mauvaise Spécification : Démonstration que l'on peut utiliser un modèle incorrect pour calculer les surprisales, tant que l'ordre relatif des valeurs extrêmes est préservé (pour la méthode empirique) ou que les conditions de convergence des valeurs extrêmes sont respectées (pour la méthode GPD).
• Garanties Théoriques :
  • Preuve que l'estimateur empirique conserve l'ordre de la queue sous une transformation monotone.
  • Établissement de conditions (Assumptions 3.1 à 3.3) assurant la convergence des surprisales vers des lois de valeurs extrêmes, justifiant l'usage du GPD.
• Gestion des Fausses Positives : Le cadre permet de contrôler strictement le taux de faux positifs en fixant un seuil sur les probabilités de queue estimées.

4. Résultats Expérimentaux

Les auteurs valident leur approche via des simulations et deux applications réelles :

• Simulations :
  • Données Normales vs t de Student : Même en utilisant une densité $t(4)$ pour calculer les surprisales de données générées par une loi Normale (et vice-versa), les estimateurs empiriques et GPD restent précis.
  • Données Bivariées Gamma : L'approche GPD converge plus vite que l'approche empirique pour les petits échantillons. L'utilisation d'un modèle de référence à queue plus lourde (Student-t) que la vraie distribution (Gamma) donne de meilleurs résultats qu'un modèle à queue plus légère (Normale), confirmant la règle de prudence : « mieux vaut surestimer la lourdeur de la queue ».
• Applications Réelles :
  • Mortalité Française (1816-1999) : Détection d'anomalies temporelles et par âge. Le modèle a correctement identifié des pics de mortalité liés à des événements historiques majeurs (guerres, épidémies de choléra, grippe espagnole) sans nécessiter de connaissance a priori de ces événements.
  • Cricket Test (Not Outs) : Analyse de la proportion de « not outs » (non éliminés) des batteurs. Le modèle a identifié Jimmy Anderson comme une anomalie statistique : bien que son taux de non-élimination ne soit pas extrême en soi, sa performance est inattendue compte tenu de son grand nombre d'innings et de son profil de batteur défensif, ce que le modèle a su capturer.

5. Signification et Conclusion

Ce travail apporte une contribution significative à la statistique appliquée en offrant une méthode de détection d'anomalies interprétable, évolutive et théoriquement fondée.

• Avantages pratiques : La méthode sépare la spécification du modèle (qui peut être approximatif) de l'estimation des probabilités de queue (qui est robuste). Elle évite les pièges des méthodes basées sur la distance dans les espaces de haute dimension ou asymétriques.
• Implémentation : Les auteurs ont développé le package R weird pour faciliter l'application de ces méthodes.
• Conclusion : En convertissant un problème complexe multivarié en un problème univarié de gestion de la queue d'une distribution de surprisale, l'approche permet de détecter des anomalies significatives même en présence d'une forte mauvaise spécification du modèle, rendant la détection d'anomalies plus fiable dans des contextes réels complexes.