Le Graphical time warping (GTW) est un cadre permettant d'aligner conjointement plusieurs paires de séries temporelles ou de séquences. Contrairement au dynamic time warping (DTW), qui aligne chaque paire indépendamment en minimisant uniquement la distance entre les deux séquences d'une paire donnée, le GTW prend en compte à la fois la précision d'alignement de chaque paire de séquences et la similarité entre les paires. Cette optimisation conjointe permet au GTW d'obtenir de meilleures performances d'alignement lorsque la similarité entre les paires est attendue, généralisant le DTW comme cas particulier.
Le cadre est applicable à toute donnée structurée avec des séries temporelles ou des séquences interdépendantes. Les applications incluent l'analyse de la propagation des signaux dans les données de bio-imagerie en time-lapse, l'identification de signatures, le calcul de profondeur stéréoscopique binoculaire, et l'alignement de profils de chromatographie liquide couplée à la spectrométrie de masse (LC-MS) dans l'analyse de données protéomiques. Dans ces contextes, les séquences adjacentes ou apparentées présentent souvent des motifs de déformation similaires, que le GTW exploite pour améliorer la qualité de l'alignement.
Formulation
Le GTW formule le problème d'alignement conjoint comme une minimisation sur un ensemble de chemins de déformation. Étant donné \(N\) paires de séries temporelles \((x_n, y_n)\) pour \(n = 1, 2, ..., N\), chaque paire a un chemin de déformation correspondant \(P_n\). Certaines paires de chemins de déformation sont connues pour être similaires, notées par l'ensemble \(Neib\). L'objectif est de minimiser :
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
Ici, \(cost(P_n)\) est la distance entre \(x_n\) et \(y_n\) après alignement avec la fonction de déformation \(P_n\). Le terme \(dist(P_m, P_n)\) mesure la distance entre deux chemins de déformation, définie comme l'aire de la région délimitée par \(P_m\) et \(P_n\). L'hyperparamètre \(\kappa\) équilibre le terme de coût d'alignement et le terme de distance des fonctions de déformation. La force de similarité peut être spécifique à l'application ; pour différentes paires liées \((m, n)\), différents paramètres \(\kappa_{(m,n)}\) peuvent être définis.
Relation avec le dynamic time warping
Le dynamic time warping est une technique classique pour aligner deux séries temporelles en trouvant un chemin de déformation optimal qui minimise la distance cumulative. Le DTW traite chaque paire indépendamment, résolvant un problème de plus court chemin dans une grille. Le GTW étend cela en couplant plusieurs chemins de déformation via une pénalité sur leurs distances par paires. Lorsque \(\kappa = 0\), le GTW se réduit à un DTW indépendant pour chaque paire. Lorsque \(\kappa > 0\), les chemins de déformation sont encouragés à être similaires, ce qui est bénéfique lorsque les séquences sous-jacentes partagent des distorsions temporelles communes.
Solution via le flot maximum
Le GTW transforme le problème de plus court chemin équivalent au DTW en un problème de flot maximum dans le graphe dual. Les contraintes ou similarités entre les chemins de déformation sont modélisées comme des arêtes ou des capacités supplémentaires. Cette formulation en graphe dual permet de résoudre l'optimisation conjointe à l'aide d'algorithmes standard de flot maximum. Cependant, pour de grands ensembles de données, les algorithmes génériques de flot maximum deviennent coûteux en temps et en mémoire.
Pour remédier à l'évolutivité, un algorithme efficace appelé Bidirectional pushing with Linear Component Operations (BILCO) a été développé spécifiquement pour le GTW. BILCO exploite la structure du graphe dual et atteint une amélioration moyenne de 10 fois en termes de temps de calcul et d'utilisation de la mémoire par rapport aux algorithmes génériques de flot maximum de pointe dans les applications GTW.
Applications
Le GTW a été appliqué dans plusieurs domaines où des séries temporelles interdépendantes apparaissent :
- Analyse de la propagation des signaux en bio-imagerie time-lapse : Les pixels adjacents montrent souvent des motifs de propagation similaires, ce qui rend le GTW adapté au suivi des fronts d'onde ou des signaux cellulaires.
- Identification de signatures : Les signatures manuscrites peuvent être traitées comme des séquences ; l'alignement conjoint de plusieurs signatures améliore la reconnaissance.
- Calcul de profondeur stéréoscopique binoculaire : Les cartes de disparité des images gauche et droite peuvent être alignées avec le GTW pour améliorer l'estimation de la profondeur.
- Alignement de profils LC-MS en protéomique : Les profils chromatographiques et spectrométriques de masse de plusieurs échantillons bénéficient d'un alignement conjoint pour corriger les décalages de temps de rétention.
Ces applications partagent la propriété que les séquences ne sont pas indépendantes mais présentent des corrélations spatiales ou temporelles que le GTW exploite.