La distance de dynamic time warping (DTW) est un algorithme qui calcule un alignement optimal entre deux séquences de séries temporelles pouvant varier en vitesse, en durée ou en phase. Contrairement aux mesures de distance plus simples telles que la distance euclidienne, qui comparent des points à des indices temporels identiques, la DTW permet une déformation non linéaire de l'axe temporel pour trouver la meilleure correspondance possible entre les séquences. Cette propriété rend la DTW particulièrement efficace pour comparer des signaux présentant une variabilité temporelle, comme des mots prononcés à des vitesses différentes, des caractères manuscrits ou des lectures de capteurs provenant de différents appareils.
L'algorithme a été introduit dans les années 1970 dans le contexte de la reconnaissance vocale, où il est devenu une technique fondatrice avant l'adoption généralisée des modèles de apprentissage automatique. Son principe central est la programmation dynamique : il construit une matrice de coûts qui accumule les distances entre chaque paire de points des deux séquences, puis trouve le chemin à travers cette matrice qui minimise la distance cumulative totale. Le chemin de déformation résultant indique quels points d'une séquence correspondent à quels points de l'autre, et la distance DTW finale est la somme des distances le long de ce chemin optimal.
Développement historique
Les premiers travaux publiés sur la DTW sont souvent attribués à Hiroaki Sakoe et Seibi Chiba, qui ont formalisé l'algorithme en 1978 avec des contraintes pour améliorer l'efficacité et la robustesse. Leur article, "Dynamic programming algorithm optimization for spoken word recognition", a introduit la bande de Sakoe-Chiba, une contrainte courante qui limite la fenêtre de déformation autorisée pour réduire le coût de calcul et prévenir les alignements pathologiques. À la même époque, des chercheurs de Xerox PARC et d'autres institutions ont exploré des approches similaires de programmation dynamique pour la correspondance de motifs, mais la formulation de Sakoe et Chiba est devenue la référence standard.
Au cours des années 1980, la DTW était la méthode dominante pour la reconnaissance de mots isolés dans les systèmes vocaux, souvent implémentée sur du matériel dédié. Elle a ensuite été supplantée par les modèles de Markov cachés (HMM) et, plus récemment, par des approches de apprentissage profond telles que les modèles acoustiques basés sur les réseaux de neurones. Cependant, la DTW est restée influente comme référence et comme outil pour aligner les données d'entraînement.
Détails algorithmiques
L'algorithme DTW opère sur deux séquences, X = (x1, x2, ..., xn) et Y = (y1, y2, ..., ym), où chaque xi et yj sont des vecteurs de caractéristiques (souvent des valeurs scalaires ou des points multidimensionnels). L'algorithme construit une matrice n par m D, où chaque cellule D(i, j) contient la distance cumulative du meilleur alignement se terminant à cette cellule. La relation de récurrence est :
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
où d(xi, yj) est une mesure de distance locale, typiquement la distance euclidienne pour des données continues ou la différence absolue pour des valeurs scalaires. La distance DTW finale est D(n, m), et le chemin de déformation optimal peut être récupéré en revenant en arrière à partir de cette cellule.
Pour améliorer l'efficacité et éviter les alignements dégénérés, plusieurs contraintes sont couramment appliquées. La bande de Sakoe-Chiba restreint le chemin de déformation à une bande diagonale de largeur fixe, réduisant l'espace de recherche de O(nm) à O(nlargeur de bande). Le parallélogramme d'Itakura, nommé d'après Fumitada Itakura, utilise une contrainte de pente qui limite la raideur du chemin. De plus, les conditions aux limites exigent que le chemin commence à (1,1) et se termine à (n,m), et la monotonie garantit que les indices ne diminuent jamais.
Applications
La DTW a trouvé des applications dans de nombreux domaines. En reconnaissance vocale, elle était utilisée pour comparer des mots prononcés à des modèles, en particulier pour des tâches à petit vocabulaire. Dans l'analyse de séries temporelles (un domaine connexe, bien que non inclus dans la liste de slugs fournie), la DTW est un outil standard pour le regroupement et la classification, surpassant souvent la distance euclidienne sur des ensembles de données avec un désalignement temporel. Par exemple, dans la reconnaissance de gestes à partir de données d'accéléromètre, la DTW peut faire correspondre des gestes effectués à des vitesses différentes.
En bioinformatique, la DTW a été appliquée pour aligner des profils d'expression génique ou des séquences protéiques, bien qu'elle soit moins courante que les algorithmes d'alignement de séquences comme Needleman-Wunsch. En finance, la DTW est utilisée pour comparer les mouvements de prix d'actions ou des indicateurs économiques au fil du temps. En robotique, la DTW aide à aligner les lectures de capteurs de différents essais pour l'apprentissage par démonstration. L'algorithme est également utilisé dans la augmentation de données pour générer des exemples d'entraînement synthétiques en déformant des séries temporelles existantes.
Variantes et extensions
Plusieurs variantes de la DTW ont été développées pour répondre à des limitations spécifiques. La DTW dérivée (DDTW) utilise la première dérivée des séquences au lieu des valeurs brutes, ce qui la rend plus robuste aux différences de décalage et d'échelle. La DTW pondérée attribue différents poids à différentes dimensions des vecteurs de caractéristiques. La Soft-DTW, introduite en 2017 par Marco Cuturi et Mathieu Blondel, remplace l'opération min par un minimum doux, rendant la distance différentiable et donc utilisable comme fonction de perte dans les pipelines de apprentissage profond.
La DTW multivariée gère des séquences avec plusieurs canaux, et la DTW de sous-séquence trouve la meilleure sous-séquence correspondante dans une séquence plus longue. Pour les grands ensembles de données, des méthodes approximatives telles que FastDTW utilisent des approches multi-échelles pour réduire la complexité computationnelle. Ces extensions ont maintenu la pertinence de la DTW dans la recherche moderne, en particulier dans le contexte du apprentissage automatique où les versions différentiables permettent un entraînement de bout en bout.
Relation avec l'IA moderne
Bien que la DTW ne soit pas une méthode de apprentissage profond, elle reste pertinente à l'ère de l'intelligence artificielle. Elle est souvent utilisée comme étape de prétraitement pour aligner des séries temporelles avant de les introduire dans des modèles de réseaux de neurones, tels que les architectures réseau résiduel ou U-Net pour la prédiction de séquences. En reconnaissance vocale (un concept non inclus dans la liste de slugs), la DTW est encore utilisée pour la détection de mots-clés dans des contextes à faibles ressources. Les principes de programmation dynamique de l'algorithme apparaissent également dans les modèles séquence à séquence, où l'alignement est appris implicitement par des mécanismes d'attention plutôt que de manière explicite.
Des chercheurs d'institutions comme MIT CSAIL et Stanford AI Lab ont exploré des approches hybrides combinant la DTW avec le apprentissage profond pour des tâches telles que la classification de séries temporelles et la détection d'anomalies. La différentiabilité de la Soft-DTW a permis son intégration dans les fonctions de perte pour entraîner des modèles nécessitant un alignement temporel. Au début des années 2020, la DTW continue d'être une référence standard dans les benchmarks de séries temporelles, et son efficacité computationnelle reste un sujet d'étude, avec des optimisations pour le matériel GPU et AWS Trainium étant explorées.