Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms

Cet article démontre l'impossibilité de calculer exactement le Warping Temporel Dynamique Continu (CDTW) sous la norme euclidienne 2 à l'aide d'opérations algébriques, tout en proposant un algorithme exact pour des normes approchant cette dernière, grâce à des fondements techniques généralisables à d'autres normes et mesures de similarité.

L'essentiel

Le Grand Défi : Comparer deux trajets qui ne vont pas à la même vitesse

Imaginez que vous avez deux amis, Alice et Bob.

• Alice a fait une randonnée en montagne. Elle a pris des photos de son chemin toutes les 10 minutes.
• Bob a fait la même randonnée, mais il a couru par moments et marché par moments. Lui, il a pris des photos toutes les 2 minutes.

Si vous essayez de comparer leurs photos point par point (photo 1 de Alice avec photo 1 de Bob), ça ne va pas marcher. Alice aura peut-être déjà atteint le sommet alors que Bob est encore au début du sentier. C'est le problème classique de la Dynamique Time Warping (DTW) : comment comparer deux courbes (des trajets) qui ont des vitesses différentes ?

La solution classique consiste à "étirer" ou "rétrécir" le temps pour aligner les points. Mais cette méthode a un défaut : elle ne regarde que les points de photos (les sommets) et ignore le chemin réel entre deux photos. Si Alice a fait un détour énorme entre deux photos, la méthode classique ne le voit pas.

La Solution Continue : Le "Fil Invisible"

Les auteurs de ce papier proposent une version améliorée appelée CDTW (Continuous Dynamic Time Warping).
Au lieu de comparer des points isolés, imaginez qu'il y a un fil invisible qui relie Alice et Bob en temps réel. Ce fil doit rester tendu et avancer toujours vers l'avant (on ne peut pas revenir en arrière).

Le but est de trouver la façon la plus "économique" de connecter ce fil entre les deux trajets. Le coût, c'est la somme de toutes les distances entre Alice et Bob à chaque instant, le long de tout le trajet. C'est comme si on calculait la quantité de "fil" nécessaire pour les relier, en tenant compte de la distance réelle parcourue.

Le Problème des "Règles du Jeu" (Les Normes)

Pour mesurer la distance entre Alice et Bob, on utilise des règles mathématiques appelées normes.

• La règle Euclidienne (Norme 2) : C'est la règle classique "à la règle et au compas". C'est la distance en ligne droite. C'est la plus naturelle, mais c'est aussi la plus difficile à calculer pour les ordinateurs dans ce contexte.
• La règle du "Manhattan" (Norme 1) : Imaginez que vous êtes dans une ville avec des rues en grille. Vous ne pouvez pas couper à travers les bâtiments. Vous devez aller tout droit, tourner à 90 degrés, etc. C'est plus simple à calculer.

La Révolution : Pourquoi la règle classique est un cauchemar

C'est ici que le papier devient fascinant. Les chercheurs ont découvert une chose effrayante (ou plutôt, fascinante pour les mathématiciens) :

Si vous essayez de calculer exactement le meilleur chemin avec la règle classique (la distance en ligne droite), vous tombez dans un piège.

Imaginez que le chemin optimal pour relier Alice et Bob nécessite de s'arrêter à un point précis dont les coordonnées sont un nombre transcendantal.

• Analogie : C'est comme si, pour construire le pont parfait entre deux rives, vous deviez couper une planche à une longueur de $\pi$ mètres ou $\sqrt{2}$ mètres. Les ordinateurs, qui fonctionnent avec des nombres "algébriques" (ceux qu'on peut obtenir avec des additions, multiplications et racines carrées simples), ne peuvent pas représenter ces nombres avec une précision infinie.
• Le verdict : Le papier prouve que pour la distance en ligne droite (Norme 2), il est impossible de donner une réponse exacte et parfaite en utilisant uniquement les opérations mathématiques de base d'un ordinateur. Le résultat contient des nombres "magiques" (transcendants) qui échappent aux calculs exacts.

La Solution Astucieuse : Remplacer la Règle par un Polygone

Puisqu'on ne peut pas calculer exactement avec la règle "parfaite" (la ligne droite), les auteurs proposent une astuce de génie : remplacer la règle par un polygone.

Imaginez que vous ne pouvez pas mesurer la distance en ligne droite, mais que vous pouvez mesurer la distance avec un octogone (une forme à 8 côtés) ou un hexagone.

• Si vous utilisez un polygone à 4 côtés (un carré), vous avez la règle du "Manhattan".
• Si vous utilisez un polygone à 1000 côtés, il ressemble presque parfaitement à un cercle (la règle classique).

L'idée clé :

1. On remplace la distance "lisse" (cercle) par une distance "polygonale" (forme géométrique à plusieurs côtés).
2. Avec cette nouvelle règle polygonale, les mathématiques redeviennent "propres" et calculables exactement par l'ordinateur.
3. Plus le polygone a de côtés, plus le résultat est proche de la réalité. On peut donc obtenir une approximation aussi précise que l'on veut (par exemple, à 99,99% de la vérité) sans jamais tomber dans le piège des nombres transcendants.

L'Algorithme : Un Jeu de Piles et de Chemins

Pour trouver le meilleur chemin avec cette nouvelle règle polygonale, les auteurs utilisent une méthode dynamique (un peu comme un jeu de construction).

• Ils divisent l'espace entre les deux trajets en une grille de cases.
• Dans chaque case, ils calculent le "coût" optimal.
• Au lieu de tout recalculer, ils propagent les résultats d'une case à l'autre, comme une vague qui avance.
• Grâce à la forme polygonale, ces "vagues" de coûts sont des formes géométriques simples (des morceaux de paraboles) que l'ordinateur peut manipuler facilement.

En Résumé

Ce papier nous dit trois choses importantes :

1. Le problème : Comparer deux courbes continues avec la distance classique (ligne droite) est mathématiquement impossible à résoudre exactement pour un ordinateur, car cela implique des nombres trop complexes.
2. La découverte : On peut prouver que les chemins optimaux sous la règle classique contiennent des nombres "infiniment complexes" (transcendants).
3. La solution : On peut contourner ce problème en remplaçant la règle de distance par des polygones (des formes à plusieurs côtés). Cela permet de calculer une réponse exacte pour le polygone, qui sert d'approximation ultra-précise pour la règle classique.

C'est comme si, pour mesurer la circonférence d'un cercle parfait, on décidait de mesurer le périmètre d'un polygone à 10 000 côtés. On obtient un résultat parfait pour le polygone, qui est pratiquement indiscernable du cercle, mais que l'ordinateur peut calculer sans se tromper.

Résumé technique

1. Problématique

La Warpping Temporelle Dynamique Continue (CDTW) est une mesure de similarité entre deux courbes polygonales qui surpasse la version discrète (DTW) et la distance de Fréchet en termes de robustesse face aux taux d'échantillonnage différents et aux valeurs aberrantes (outliers). Contrairement au DTW qui ne considère que les sommets, la CDTW intègre les courbes comme des objets continus via une intégrale de chemin le long d'un couplage monotone.

Cependant, le calcul exact de la CDTW en dimension 2 (2D) sous la norme euclidienne ($L_2$) pose des défis majeurs :

• Complexité algorithmique : Les approches existantes reposent souvent sur des heuristiques ou des discrétisations qui dégradent la qualité de la solution ou augmentent le temps de calcul.
• Nature mathématique : Il est incertain si le calcul exact est possible sous la norme $L_2$ car les valeurs impliquées pourraient être transcendantales, échappant ainsi aux modèles de calcul algébrique standard.
• Analyse combinatoire : La complexité temporelle des algorithmes exacts en 1D ($O(n^5)$) n'a pas encore été généralisée de manière satisfaisante en 2D.

2. Méthodologie

Les auteurs adoptent une approche fondée sur l'analyse géométrique de l'espace des paramètres et l'analyse de la complexité algébrique.

A. Géométrie de l'espace des paramètres

L'espace des paramètres est défini comme le produit des longueurs d'arc des deux courbes. Les auteurs caractérisent les chemins optimaux à l'intérieur d'une "cellule" (correspondant à une paire de segments de courbe) en utilisant le concept de vallée :

• Une vallée est une ligne dans l'espace des paramètres où la fonction de coût (distance entre les points des courbes) atteint un minimum local le long des lignes de pente $-1$.
• Ils prouvent que pour toute norme $\|\cdot\|$, il existe une vallée de pente positive. Cela permet de construire des chemins optimaux qui suivent ces vallées ou s'en rapprochent le plus possible.

B. Impossibilité de calcul exact sous la norme $L_2$

Les auteurs analysent la nature des nombres générés par le calcul de la CDTW sous la norme euclidienne ($L_2$) :

• Ils démontrent que le coût optimal et les points de rupture (bending points) des chemins optimaux peuvent être des nombres transcendants (par exemple, impliquant des logarithmes naturels de nombres algébriques).
• En utilisant le théorème de Baker sur les nombres transcendants, ils montrent que ces valeurs ne peuvent pas être calculées exactement dans le modèle de calcul algébrique (ACMQ) qui n'autorise que les opérations arithmétiques de base et l'extraction de racines.

C. Algorithme d'approximation exacte sous des normes polygonales

Pour contourner l'impossibilité du cas $L_2$, les auteurs proposent un algorithme exact pour une large classe de normes dont les ensembles de niveau sont des polygones (notamment les normes $L_1$ et $L_\infty$, et des approximations de $L_2$).

• Approche : Ils utilisent la programmation dynamique pour propager les fonctions de coût optimal à travers la grille des cellules de l'espace des paramètres.
• Fonctions de coût : Sous ces normes polygonales, les fonctions de coût optimal sont des fonctions quadratiques par morceaux.
• Propagation : L'algorithme maintient une pile de pièces quadratiques. Pour chaque cellule, il calcule la vallée, construit un arrangement de lignes (basé sur la géométrie de la norme) et calcule l'enveloppe inférieure des coûts possibles.
• Approximation de $L_2$ : En choisissant un polygone régulier à $k$ côtés comme ensemble de niveau unitaire, ils obtiennent une approximation $(1+\varepsilon)$ de la CDTW sous $L_2$ avec $k \in O(\varepsilon^{-1/2})$.

3. Contributions Clés

1. Preuve d'indécidabilité algébrique pour $L_2$ :

   • Démonstration rigoureuse que la CDTW sous la norme $L_2$ ne peut pas être calculée exactement par des opérations algébriques (racines, additions, multiplications) car les résultats peuvent être transcendants. Cela justifie théoriquement l'utilisation d'approximations ou de normes alternatives.

2. Caractérisation géométrique des chemins optimaux :

   • Établissement de l'existence de vallées de pente positive pour toute norme, généralisant les résultats précédents limités à la norme $L_1$.
   • Fourniture d'une méthode efficace ($O(1)$ ou $O(\log k)$) pour calculer ces vallées pour des normes définies par des polygones.

3. Algorithme exact pour les normes polygonales :

   • Développement d'un algorithme de programmation dynamique qui propage des fonctions quadratiques par morceaux.
   • Preuve que cet algorithme calcule la CDTW exactement pour les normes polygonales.
   • Démonstration que cet algorithme fournit une approximation $(1+\varepsilon)$ pour la norme $L_2$ sans discrétiser les courbes d'entrée (seule la norme est discrétisée).

4. Analyse de complexité et propriétés techniques :

   • Preuve de la continuité des fonctions de coût optimal, essentielle pour la convergence des algorithmes.
   • Analyse préliminaire de la complexité temporelle en 2D, identifiant le problème de la croissance exponentielle potentielle du nombre de pièces quadratiques comme un défi ouvert, bien que l'algorithme soit efficace en pratique pour des $k$ raisonnables.

4. Résultats Principaux

• Théorème d'impossibilité : Il existe des courbes polygonales à sommets entiers pour lesquelles la valeur CDTW sous $L_2$ est un nombre transcendant. Par conséquent, aucun algorithme exact basé uniquement sur des opérations algébriques ne peut résoudre ce problème.
• Algorithme d'approximation : Pour toute $\varepsilon > 0$, il est possible de calculer la CDTW sous $L_2$ avec une erreur relative de $(1+\varepsilon)$ en utilisant une norme définie par un polygone régulier à $k = O(\varepsilon^{-1/2})$ côtés.
• Complexité : La complexité de l'algorithme proposé est bornée par $O(N \cdot k^2 \log(k) \alpha(k))$, où $N$ est le nombre total de pièces quadratiques propagées et $\alpha$ est la fonction d'Ackermann inverse. La borne exacte de $N$ en 2D reste un problème ouvert (contrairement au cas 1D où $N=O(n^5)$).

5. Signification et Impact

Ce travail établit des fondements théoriques solides pour le calcul de la similarité de courbes continues en 2D :

• Limites théoriques : Il clarifie les limites fondamentales du calcul exact sous la norme euclidienne, orientant la recherche vers des méthodes d'approximation ou des modèles de calcul plus puissants (séries de puissances, etc.).
• Nouvelles approches algorithmiques : En proposant un algorithme exact pour les normes polygonales, il offre une voie praticable pour obtenir des garanties d'approximation fortes sans sacrifier la nature continue du problème (contrairement aux méthodes de discrétisation spatiale classiques).
• Généralité : Les techniques développées, notamment l'analyse des vallées et la propagation de fonctions quadratiques, sont généralisables à d'autres mesures de similarité comme la similarité de Fréchet partielle ou la distance de Fréchet lexicographique.

En résumé, l'article résout le problème de l'indécidabilité algébrique pour la CDTW en 2D sous $L_2$ et fournit un cadre algorithmique robuste pour son approximation efficace, comblant ainsi un vide important entre la théorie géométrique et l'algorithmique pratique.