Dynamic time warping : comment fonctionne la déformation temporelle dynamique ?

Le dynamic time warping sert à vérifier les similitudes entre différentes longueurs de séquences de valeurs dans le cadre d’une comparaison de modèles. À cet effet, l’algorithme de déformation temporelle dynamique génère des chemins de déformation qui permettent, grâce au retour sur trace et aux mesures différentielles, de mettre en évidence des similitudes en faisant abstraction de la déformation temporelle ou des différences de vitesse. Ce concept est notamment utilisé dans le cadre de la reconnaissance vocale, de la reconnaissance numérique des signatures ou de l’analyse des marchés financiers.

Que signifie « dynamic time warping » ?

Le terme « dynamic time warping » se traduit, en français, par le concept de « déformation temporelle dynamique ». Si cette technologie peut sembler tout droit sortie de Star Trek, il n’en est rien. En vérité, cet algorithme sert simplement à comparer différentes séquences de temps ou de valeurs. Pour ce faire, il les met en correspondance avant de les confronter les unes aux autres. Grâce au « warping » de ces séquences, terme qui a d’ailleurs donné son nom à l’algorithme, il est possible de mettre en évidence des points communs et des correspondances entre les modèles des différentes séquences, même si leur longueur ou leur vitesse ne sont pas les mêmes.

Par exemple, si deux séquences différentes impliquant de la marche doivent être analysées pour y rechercher des concordances, l’algorithme est capable de reconnaître des modèles identiques, et ce, même en cas de différences dans la vitesse de marche ou la distance parcourue. En ce qui concerne la comparaison des signatures d’une même personne, il est également possible de mettre en lumière des points communs, même si la taille de l’écriture n’est pas la même.

Quel est le but du dynamic time warping ?

Il faut reconnaître qu’à première vue, le DTW a tout d’un concept abstrait sans véritable utilité pratique. Et pourtant : le dynamic time warping remplit une fonction d’analyse importante dans de nombreux domaines d’application, notamment l’étude de séquences vidéo et audio et l’analyse séquentielle de graphiques ou de modèles statistiques, c’est-à-dire de séquences pouvant être reproduites et comparées de manière linéaire. En identifiant les similitudes, le DTW permet le déclenchement d’actions, de signaux ou de fonctions spécifiques.

En outre, la mesure et la reconnaissance de modèles dans des séquences de valeurs permettent d’étudier l’évolution de systèmes similaires, et ce, même sur différentes périodes. L’algorithme de dynamic time warping s’utilise donc également avec des technologies de pointe, telles que l’apprentissage automatique, l’apprentissage supervisé ou les réseaux de neurones artificiels pour entraîner les capacités d’analyse et de réaction des systèmes d’autoapprentissage et évaluer les ensembles de données de manière plus performante.

Comment fonctionne le dynamic time warping ?

Afin d’identifier les modèles et les similarités dans différentes séquences de valeurs, le DTW recherche des correspondances optimales, également appelées « optimal matches » en anglais. Les principes « One-to-many » ou « Many-to-one » peuvent ici s’avérer utiles. Diverses règles et conditions s’appliquent alors :

• Au sein d’une séquence, chaque valeur doit être comparée à une ou plusieurs valeurs de la deuxième séquence (et inversement).
• La première valeur d’une séquence doit être comparée à la première valeur de la deuxième séquence.
• La dernière valeur d’une séquence doit être comparée à la dernière valeur de la deuxième séquence.
• Le mappage de la série de valeurs de la première séquence à la série de valeurs de la deuxième séquence doit augmenter de façon uniforme. Les positions des valeurs de début et de fin des séquences doivent correspondre, sans omission ni doublon.

Pour une correspondance optimale, toutes les spécifications et les conditions doivent être remplies. Pour ce faire, il est possible d’utiliser une fonction de coût. Celle-ci permet de créer une mesure de différence entre les valeurs des séquences. Pour obtenir une correspondance optimale, la fonction de coût doit être aussi faible que possible.

Par ailleurs, l’algorithme crée un chemin de déformation qui est en mesure d’identifier les correspondances optimales dans des séquences de longueurs différentes. Le retour de trace permet de créer ce chemin de déformation, dans lequel l’algorithme met en correspondance une ou plusieurs valeurs d’une séquence avec des points de la deuxième séquence. Malgré cette déformation temporelle, ou plutôt grâce à elle, il est alors possible de mettre en lumière des concordances, même lorsque les séquences n’ont pas la même longueur.

Quels sont les domaines d’application du dynamic time warping ?

Il est possible d’utiliser le dynamic time warping dans tous les domaines où des ensembles de données peuvent être représentés et comparés sous forme de séquences linéaires. Le DTW est donc souvent utilisé comme une étude préalable ou ultérieure dans le cadre de l’analyse des données. Il peut s’agir de données audio, vidéo et alphanumériques, ou encore d’ensembles de données fondés sur le Big Data.

Les exemples suivants comptent également parmi les domaines d’application du DTW :

• La reconnaissance de modèles dans des séquences audio : la reconnaissance vocale constitue un cas d’application de grande importance pour le DTW. Dans ce cas particulier, des modèles linguistiques enregistrés et sauvegardés sont comparés entre eux grâce au DTW. Pour les séquences audio n’ayant pas la même longueur ou la même vitesse, le DTW utilise la déformation temporelle dite « adaptative » pour créer un chemin de déformation. Ce procédé permet d’identifier des concordances au niveau des voyelles et des consonnes, même si elles ne sont pas prononcées à la même vitesse ou si leur longueur est différente.
• La reconnaissance de modèles dans des séquences vidéo : pour ce qui est de la reconnaissance des gestes et de la détection des mouvements, le DTW peut mapper des séquences vidéo, notamment des séquences de mouvements, les unes sur les autres. Cela permet ainsi de comparer ces séquences de mouvements et d’y reconnaître certains modèles, même lorsque leur longueur ou leur vitesse est différente.
• La reconnaissance de modèles dans des données financières : les marchés financiers et les finances des entreprises constituent également d’importants domaines d’application. En utilisant le DTW, il est possible d’établir des prévisions concernant les cycles financiers, les courbes de chiffres d’affaires ou les tendances de la bourse. Le DTW permet, sur différentes périodes, d’identifier et de visualiser certains cycles et certaines tendances similaires ou identiques dans les données relatives au marché et aux entreprises. Cette forme d’étude s’applique aussi bien à des prévisions qu’à des données commerciales et financières recueillies.

Quels outils appliquent le dynamic time warping ?

L’algorithme de DTW est présent dans les bibliothèques de plusieurs logiciels open source. En voici quelques exemples :

• DTW Suite, qui propose des progiciels de programmation pour Python et R ;
• FastDTW, qui propose une implémentation Java pour les algorithmes de DTW ;
• MatchBox, qui propose d’implémenter le DTW à des signaux audio ;
• mlpy et pydtw, qui proposent également des fonctions de DTW en leur qualité de bibliothèques Python pour l’apprentissage automatique ;
• Gesture Recognition, qui propose des algorithmes de DTW pour la reconnaissance des gestes en temps réel.

Pour utiliser le DTW de la manière la plus performante qui soit, il est également possible de recourir aux techniques de calcul rapide suivantes :

• PruneDTW
• SparseDTW
• FastDTW
• MultiscaleDTW

Exemple : l’algorithme de dynamic time warping dans Python

Pour illustrer la complexité du dynamic time warping, nous vous proposons ci-dessous un exemple d’algorithme de DTW en code Python :

def dtw(s, t, window):
    n, m = len(s), len(t)
    w = np.max([window, abs(n-m)])
    dtw_matrix = np.zeros((n+1, m+1))
    
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            dtw_matrix[i, j] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

Trois paramètres sont d’abord renseignés dans la fonction présentée dans l’exemple de code : en premier lieu, les deux signaux qui doivent être analysés sont renseignés dans les paramètres « s » et « t ». En règle générale, les signaux correspondant à des tableaux ou des vecteurs. Le paramètre « window » sert à préciser le nombre d’autres éléments avec lesquels une correspondance est possible.

Dans la fonction, une matrice est d’abord créée, puis initialisée à l’infini avec la valeur correspondante. L’étape centrale du DTW se déroule dans les deux dernières boucles for imbriquées : la valeur enregistrée dans la variable « last_min » est ajoutée aux coûts précédents, enregistrés dans la variable « costs », qui résultent de la distance entre les deux valeurs d’entrée à l’index correspondant.

Cette valeur résulte de valeurs déjà calculées, compte tenu de la programmation dynamique. La plus faible des valeurs voisines déjà calculées au préalable est sélectionnée, puis ajoutée au coût lui aussi calculé précédemment. Lors de cette étape, il s’agit de trancher entre la mise en correspondance directe de deux éléments, l’ajout d’un élément ou la suppression d’un élément.

Une fois la fonction exécutée, elle produit une matrice de distance à partir de laquelle le chemin de déformation peut être lu.

Solutions de substitution au dynamic time warping

Outre le DTW, d’autres solutions de reconnaissance de modèles dans des séquences de valeurs et de temps peuvent être utilisées, notamment :

• le concept de « correlation optimized warping » (COW, déformation optimisée par corrélation) ;
• l’analyse fonctionnelle des données ;
• le modèle de Markov caché ;
• l’algorithme de Viterbi.