Dynamic Time Warping

Aussi appelé: DTW
Catégorie: Learning & autonomy › Learning from demonstration
Mots-clés: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

Algorithme de programmation dynamique qui aligne deux séries temporelles de vitesses ou de longueurs différentes en trouvant l'appariement de leurs échantillons, respectueux de l'ordre, dont la distance totale est la plus faible.

Définition

La déformation temporelle dynamique (dynamic time warping, DTW) compare deux séquences qui suivent un motif semblable mais à des vitesses différentes, par exemple deux démonstrations du même mouvement où un opérateur a marqué une pause et l'autre s'est déplacé rapidement. Au lieu de comparer l'échantillon i avec l'échantillon i, la DTW cherche un chemin d'alignement, un appariement des échantillons des deux séquences qui part des deux débuts, aboutit aux deux fins et ne revient jamais en arrière dans le temps. Chaque échantillon peut être apparié à un ou plusieurs échantillons de l'autre séquence, si bien que les étirements et les compressions temporels sont absorbés par l'alignement. La distance DTW est le coût total le long du meilleur chemin, et le chemin lui-même indique quels instants se correspondent.

L'algorithme standard remplit une matrice de coûts par programmation dynamique. Avec une distance locale d(i, j) entre l'échantillon i d'une séquence et l'échantillon j de l'autre, le coût cumulé vaut D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1)), et un retour arrière depuis la dernière cellule permet de reconstituer le chemin. Cela demande un temps et une mémoire proportionnels au produit des deux longueurs. Sakoe et Chiba (1978) ont popularisé la méthode pour la reconnaissance de mots parlés et introduit une bande autour de la diagonale qui limite la dérive possible de l'alignement ; le parallélogramme d'Itakura est une contrainte apparentée. De telles fenêtres accélèrent le calcul et empêchent les déformations pathologiques dans lesquelles un échantillon est apparié à un long tronçon de l'autre séquence.

Plusieurs variantes comptent en robotique. Subsequence DTW assouplit les conditions de début et de fin afin qu'une requête courte puisse être appariée au segment le mieux adapté d'une longue trajectoire, ce qui permet la recherche dans de grands journaux. Derivative DTW aligne sur les pentes locales plutôt que sur les valeurs brutes. Soft-DTW, introduite par Cuturi et Blondel en 2017, remplace le minimum par une version lissée, si bien que le coût d'alignement est différentiable et peut servir de perte d'entraînement. La DTW n'aligne que dans le temps : les caractéristiques doivent être comparables et généralement normalisées, et la distance obtenue n'est pas une vraie métrique car elle ne satisfait pas l'inégalité triangulaire.

Pourquoi c'est important

Les données robotiques arrivent rarement à une vitesse commune. Démonstrations, trajectoires exécutées et enregistrements de capteurs diffèrent par leur cadencement, et la DTW est l'outil standard pour les placer sur une échelle de temps commune avant de les moyenner, de les comparer, de les retrouver ou de les noter.

Applications principales

Alignement de plusieurs démonstrations avant d'en faire la moyenne ou d'ajuster des primitives de mouvement
Comparaison des trajectoires exécutées par un robot avec des trajectoires de référence
Recherche de segments correspondants dans de grands journaux de trajectoires ou de capteurs
Reconnaissance de gestes et d'activités à partir de données de mouvement ou inertielles
Notation de chemins de navigation par rapport à des chemins de référence avec des métriques DTW normalisées
Synchronisation de flux de capteurs enregistrés à des fréquences différentes

En pratique

Une équipe recueille dix démonstrations kinesthésiques d'un mouvement de versement, chacune d'une durée différente et avec des pauses à des endroits différents. Pour construire une référence unique pour une primitive de mouvement, elle choisit une démonstration comme gabarit, aligne chacune des autres sur celle-ci par DTW sur les positions articulaires normalisées et la vitesse de l'effecteur terminal, puis rééchantillonne toutes les démonstrations sur l'échelle de temps du gabarit à l'aide des chemins d'alignement. La moyenne des trajectoires alignées donne un mouvement moyen propre et une variance par pas de temps qui montre où les démonstrations concordent. Une bande de Sakoe-Chiba empêche l'alignement de réduire les pauses à des échantillons uniques. Plus tard, le même code de Subsequence DTW parcourt les trajectoires stockées de la flotte à la recherche des segments qui correspondent le mieux à un court mouvement de requête.

Idées reçues

La distance DTW est une métrique — elle ne satisfait pas l'inégalité triangulaire, ce qui compte pour les méthodes d'indexation et de partitionnement qui en supposent une
La DTW gère toute différence entre séquences — elle absorbe les différences de cadencement, pas les décalages ni les changements d'échelle des valeurs, si bien que les caractéristiques doivent généralement être normalisées d'abord
La DTW sans contrainte donne le meilleur alignement — sans fenêtre, elle peut apparier un seul échantillon à de longs tronçons de l'autre séquence, produisant des déformations sans signification physique
La DTW est trop lente pour un usage pratique — les bandes, les bornes inférieures et les méthodes approchées la rendent assez rapide pour de nombreux usages en temps réel et à grande échelle

Qui devrait le savoir

Chercheurs en apprentissage par démonstration
Ingénieurs qui analysent des trajectoires et des journaux de robots
Développeurs de reconnaissance de gestes et d'activités
Chercheurs qui évaluent des politiques de navigation et de manipulation

Technologies associées

Soft-DTW
Bande de Sakoe-Chiba
Subsequence DTW
FastDTW
tslearn

Termes associés

Projets associés

PlotJuggler: Fast time-series visualization tool for ROS topics, rosbags, and robot debugging

Vidéos

How DTW (Dynamic Time Warping) algorithm works: Thales Sehn Körting