🤖 machine learning

Soft-MSM: Differentiable Context-Aware Elastic Alignment for Time Series

Ce papier présente Soft-MSM, une fonction de perte d'alignement élastique différentiable et consciente du contexte qui lisse la distance Move-Split-Merge pour permettre une optimisation basée sur le gradient, démontrant des performances supérieures en matière de regroupement et de classification de séries temporelles par rapport aux méthodes existantes telles que Soft-DTW.

Auteurs originaux : Christopher Holder, Anthony Bagnall

Publié 2026-05-04

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Christopher Holder, Anthony Bagnall

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de comparer deux chansons. L'une est jouée légèrement plus vite, l'autre légèrement plus lentement. Si vous tentez de les aligner note pour note, du début à la fin (comme avec une règle rigide), elles sembleront complètement différentes car les battements ne correspondent pas.

Dynamic Time Warping (DTW) est comme un auditeur intelligent qui étire et comprime la chronologie des chansons afin que les battements s'alignent parfaitement, vous permettant de voir qu'il s'agit en réalité de la même chanson. C'est excellent pour comparer des données temporelles, comme les battements cardiaques, les cours boursiers ou les capteurs de mouvement.

Cependant, il y a un problème : cet « auditeur intelligent » est un peu rigide. Il prend une décision soudaine et tranchée sur la manière d'étirer le temps. Dans le monde de l'IA moderne, qui apprend en effectuant des ajustements minuscules et fluides (comme un sculpteur qui ébrèche lentement la pierre), cette prise de décision soudaine constitue un obstacle. L'IA se perd car elle ne peut pas calculer la « pente » nécessaire pour s'améliorer.

Voici Soft-MSM, la nouvelle méthode présentée dans cet article.

Le problème de l'ancienne méthode

L'article se concentre sur une manière très intelligente et spécifique de comparer le temps, appelée MSM (Move-Split-Merge). Imaginez MSM comme un auditeur ultra-avancé qui ne se contente pas d'étirer le temps ; il comprend également le contexte de la musique.

Move (Déplacement) : Déplacer simplement une note légèrement.
Split (Division) : Si une note est trop longue, elle peut être divisée en deux.
Merge (Fusion) : Si deux notes sont trop proches, elles peuvent être fusionnées.

MSM excelle dans cette tâche, surpassant souvent l'« auditeur intelligent » standard (DTW) dans des tâches comme le regroupement de données similaires. Mais, comme le DTW original, il prend des décisions « dures ». Il dit : « Cette note est définitivement une division » ou « Ceci est définitivement une fusion ». Parce que ces décisions sont nettes et soudaines, elles ne peuvent pas être utilisées pour entraîner des modèles d'IA modernes qui ont besoin d'un retour d'information continu et fluide pour apprendre.

La solution : Soft-MSM

Les auteurs ont créé Soft-MSM. Imaginez prendre cet auditeur ultra-intelligent (MSM) et lui donner une vision « floue ». Au lieu de prendre une décision soudaine et tranchée sur le fait de diviser ou de fusionner une note, Soft-MSM dit : « Il y a 60 % de chances que ce soit une division et 40 % de chances que ce soit une fusion ».

Cette « flouité » est mathématiquement lisse. Elle permet à l'IA de voir la pente de la colline et de savoir exactement dans quelle direction pousser les données pour améliorer la comparaison. Elle transforme une montagne déchiquetée et infranchissable en une colline lisse et praticable.

Comment ils l'ont fait

Pour rendre cela fonctionnel, les auteurs ont dû inventer un nouveau mécanisme de « gardien ».

L'ancien gardien : Le MSM original possédait une porte qui était soit entièrement ouverte, soit entièrement fermée, basée sur des règles strictes.
Le nouveau gardien : Ils l'ont remplacé par une « porte lisse » qui s'ouvre progressivement. Cela permet aux mathématiques de circuler dans le système sans se briser, permettant à l'IA de calculer les gradients (la direction de l'amélioration) à travers la logique complexe de « division et fusion ».

Ce qu'ils ont découvert

Les chercheurs ont testé cette nouvelle méthode sur 112 ensembles de données différents (une grande variété de données temporelles). Voici ce qu'ils ont découvert :

Meilleure moyenne : Lorsqu'ils tentaient de trouver la forme « moyenne » d'un groupe de séries temporelles similaires (comme trouver le signal moyen d'un arbitre de cricket), Soft-MSM créait une moyenne beaucoup plus propre et plus précise que les méthodes précédentes. Elle ne se perdait pas à cause du bruit.
Meilleur regroupement (Clustering) : Lorsqu'ils utilisaient Soft-MSM pour regrouper des éléments similaires, cela fonctionnait nettement mieux que les meilleures méthodes précédentes (comme Soft-DTW). C'était comme avoir un meilleur algorithme de tri pour un tas de vêtements en désordre.
Meilleure classification : Lorsqu'ils utilisaient ces moyennes pour deviner à quelle catégorie appartenait une nouvelle donnée, Soft-MSM était plus précis.

Le compromis

L'article note un petit prix à payer pour cette fluidité. Le MSM original était une « métrique » parfaite (il suivait des règles mathématiques strictes concernant la distance). Soft-MSM sacrifie cette rigidité mathématique parfaite pour gagner la capacité d'être utilisé dans un apprentissage basé sur des gradients fluides. Cependant, les auteurs soutiennent que pour la plupart des tâches pratiques d'IA, la capacité d'apprendre de manière fluide est bien plus précieuse que d'être une métrique parfaite.

En résumé

L'article présente Soft-MSM, un nouvel outil qui rend une méthode puissante de comparaison de séries temporelles (MSM) compatible avec l'IA moderne à apprentissage fluide. En remplaçant les décisions nettes et soudaines par des décisions probabilistes et fluides, il permet aux ordinateurs d'apprendre de meilleurs modèles dans les données temporelles, aboutissant à de meilleures moyennes, de meilleurs regroupements et des prédictions plus précises. Le code est déjà disponible dans une boîte à outils open source appelée aeon pour que d'autres puissent l'utiliser.

1. Énoncé du problème

L'apprentissage automatique des séries temporelles (TSML) repose fortement sur des mesures de distance pour gérer les désalignements temporels entre les séquences. Les distances élastiques, telles que la Dynamic Time Warping (DTW) et Move-Split-Merge (MSM), résolvent ce problème en trouvant des chemins d'alignement optimaux qui étirent ou compressent les axes temporels.

La limitation des distances élastiques : Bien qu'efficaces pour des tâches telles que le clustering et la classification, les distances élastiques traditionnelles sont non différentiables. Cela empêche leur utilisation directe en tant que fonctions de perte dans l'optimisation par gradient (par exemple, réseaux de neurones, moyennage itératif).
La limitation des solutions existantes : Soft-DTW a été introduit pour rendre la DTW différentiable en remplaçant le minimum dur dans sa récursion par un opérateur de soft-minimum lisse. Cependant, Soft-DTW ne peut pas être directement étendu à d'autres distances élastiques comme MSM. MSM est souvent supérieur à la DTW en performance car il utilise des coûts de transition conscients du contexte (pénalités de division/fusion) qui dépendent de l'ordre local de trois valeurs. La nature par morceaux de la fonction de coût de MSM crée des régions non lisses que les approches standard de soft-minimum ne peuvent pas facilement différencier.

2. Méthodologie : Soft-MSM

Les auteurs proposent Soft-MSM, une relaxation lisse et différentiable de la distance Move-Split-Merge. Le défi principal était de rendre le coût de transition de MSM différentiable tout en préservant sa structure consciente du contexte.

Innovations techniques clés :

Surrogat de porte lisse pour les coûts de transition :
- La fonction de coût MSM originale applique une pénalité fixe $c$ si un point $x$ se situe entre les voisins $y$ et $z$ , et une pénalité supplémentaire sinon. Il s'agit d'une fonction par morceaux avec des frontières non différentiables.
- Solution : Les auteurs introduisent une fonction de porte entre lisses $g(x, y, z)$ utilisant une approximation de type tangente hyperbolique :
  $g(x, y, z) = \frac{1}{2} \left( 1 - \frac{u}{\sqrt{u^2 + \epsilon}} \right), \quad \text{où } u = (x-y)(x-z)$
- Cette porte passe lisse de 1 (lorsque $x$ est entre $y$ et $z$ ) à 0 (sinon), permettant aux gradients de traverser la frontière de décision.
- Le coût de transition est redéfini comme suit :
  $\text{trans}_\gamma(x, y, z; c) = c + (1 - g(x, y, z)) \cdot \text{softmin}_\gamma((x-y)^2, (x-z)^2)$
- Ils remplacent également la différence absolue dans la distance locale par une différence au carré pour assurer la différentiabilité en $x=y$ .
Récursions avant et arrière :
- Passage avant : Calcule la matrice de coût accumulée $C$ en utilisant un opérateur de soft-minimum ( $\text{softmin}_\gamma$ ) au lieu du minimum dur, intégrant les nouveaux coûts de transition lisses.
- Passage arrière : Dérive la matrice d'alignement lisse $A$ et le Jacobien (gradient) par rapport aux séries temporelles d'entrée. Le gradient est décomposé en contributions provenant des arêtes diagonales (correspondance), verticales (division) et horizontales (fusion), pondérées par les probabilités d'alignement.
Propriétés théoriques :
- Différentiabilité : Prouvé comme étant continûment différentiable pour $\gamma > 0$ et $\epsilon > 0$ .
- Comportement limite : Lorsque $\gamma \to 0$ et $\epsilon \to 0$ , Soft-MSM converge ponctuellement vers la récursion MSM standard (avec des écarts au carré).
- Métricité : Soft-MSM n'est pas une métrique (il viole l'identité des indiscernables et peut être négatif). Pour y remédier, les auteurs proposent une formulation corrigée par divergence (analogue à la divergence Soft-DTW) pour assurer la non-négativité et une distance nulle à soi-même.
- Complexité : Maintient la même complexité temporelle et spatiale $O(m^2)$ que la MSM standard.

3. Contributions clés

Premier MSM différentiable : La première formulation d'une version différentiable de la distance Move-Split-Merge, permettant son utilisation dans l'apprentissage par gradient.
Nouvelle porte lisse : Une dérivation mathématique d'une fonction de porte lisse qui gère les pénalités de division/fusion dépendantes du contexte de MSM sans perdre les avantages structurels de la distance originale.
Gradients sous forme fermée : Dérivation de la transformation Jacobienne permettant l'optimisation directe des séquences de séries temporelles en utilisant Soft-MSM.
Implémentation : La méthode est implémentée dans la boîte à outils open-source aeon, soutenant la reproductibilité.

4. Résultats expérimentaux

Les auteurs ont évalué Soft-MSM sur 112 jeux de données de séries temporelles UCR dans trois scénarios principaux :

A. Moyennage des séries temporelles (Barycentre)

Objectif : Trouver une série temporelle représentative (barycentre) qui minimise la somme des distances à un ensemble de séries d'entrée.
Comparaison : Barycentre Soft-MSM (Soft-MBA) vs. Barycentre MSM standard (MBA) et Barycentre MBA à sous-gradient stochastique (SSG-MBA).
Résultat : Soft-MBA a obtenu une perte Fréchet MSM plus faible que le MBA et le SSG-MBA sur 97,2 % à 100 % des jeux de données (selon le paramètre de lissage $\gamma$ ). Il a nettement surpassé les contreparties dures, démontrant que la relaxation différentiable conduit à une meilleure convergence et à une perte plus faible.

B. Clustering de séries temporelles

Objectif : Utiliser k-means avec des centroïdes élastiques.
Comparaison : Soft-MBA vs. Barycentre Soft-DTW (Soft-DBA), k-Shape et k-means Euclidien.
Résultat :
- Soft-MBA a nettement surpassé Soft-DBA en précision de clustering et en Indice Rand Ajusté (ARI).
- Soft-MBA était compétitif avec k-Shape (une base de référence forte), malgré l'utilisation d'une mesure de similarité fondamentalement différente.
- Soft-MBA a montré une plus grande robustesse au paramètre de lissage $\gamma$ par rapport à Soft-DBA.

C. Classification par centroïde le plus proche

Objectif : Classifier les séries temporelles en fonction de la distance aux prototypes de classe (barycentres).
Résultat : Les classificateurs utilisant des prototypes Soft-MBA ont atteint une précision et une précision équilibrée nettement supérieures à ceux utilisant des prototypes Soft-DBA.
Analyse qualitative : Sur le jeu de données CRICKETX, Soft-MBA a produit des prototypes de classe plus lisses et plus interprétables (capturant clairement le signal des "six points") par rapport aux prototypes bruyants générés par d'autres méthodes.

5. Signification et impact

Combler le fossé : Soft-MSM comble avec succès le fossé entre les distances élastiques à haute performance (comme MSM) et les cadres modernes d'apprentissage profond basés sur le gradient.
Supériorité sur Soft-DTW : Les résultats suggèrent que pour de nombreuses tâches de séries temporelles, MSM est une mesure de distance supérieure à DTW, et le rendre différentiable donne de meilleurs résultats que d'utiliser simplement Soft-DTW.
Applicabilité large : La méthode ouvre la voie à l'utilisation de pertes basées sur MSM dans :
- La prévision de séries temporelles profondes.
- Les modèles génératifs pour l'augmentation de données.
- L'alignement et la segmentation faiblement supervisés.
- L'apprentissage de représentations (par exemple, Series2Vec).
Biais inductif : Il fournit un nouveau biais inductif basé sur les opérations "move, split, and merge" (déplacement, division et fusion), particulièrement utile pour les données de séries temporelles constantes par morceaux ou pilotées par des événements.

En conclusion, Soft-MSM est une avancée significative dans l'apprentissage automatique des séries temporelles, offrant une distance élastique différentiable et consciente du contexte qui surpasse les approches existantes basées sur Soft-DTW dans les tâches de moyennage, de clustering et de classification.