El warping temporal gráfico (GTW, por sus siglas en inglés) es un marco para alinear conjuntamente múltiples pares de series temporales o secuencias. A diferencia del warping temporal dinámico (DTW), que alinea cada par de forma independiente minimizando únicamente la distancia entre las dos secuencias de un par dado, el GTW considera tanto la precisión de alineación de cada par de secuencias como la similitud entre pares. Esta optimización conjunta permite que el GTW logre un mejor rendimiento de alineación cuando se espera similitud entre pares, generalizando el DTW como un caso especial.
El marco es aplicable a cualquier dato estructurado con series temporales o secuencias interdependientes. Las aplicaciones incluyen el análisis de propagación de señales en datos de bioimagen con lapso de tiempo, la identificación de firmas, el cálculo de profundidad estéreo binocular y la alineación de perfiles de cromatografía líquida-espectrometría de masas (LC-MS) en el análisis de datos de proteómica. En estos contextos, las secuencias adyacentes o relacionadas suelen exhibir patrones de warping similares, que el GTW aprovecha para mejorar la calidad de la alineación.
Formulación
El GTW formula el problema de alineación conjunta como una minimización sobre un conjunto de caminos de warping. Dados \(N\) pares de series temporales \((x_n, y_n)\) para \(n = 1, 2, ..., N\), cada par tiene un camino de warping correspondiente \(P_n\). Se sabe que algunos pares de caminos de warping son similares, denotados por el conjunto \(Neib\). El objetivo es minimizar:
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
Aquí, \(cost(P_n)\) es la distancia entre \(x_n\) y \(y_n\) después de la alineación con la función de warping \(P_n\). El término \(dist(P_m, P_n)\) mide la distancia entre dos caminos de warping, definida como el área de la región delimitada por \(P_m\) y \(P_n\). El hiperparámetro \(\kappa\) equilibra el término de costo de alineación y el término de distancia de la función de warping. La fuerza de similitud puede ser específica de la aplicación; para diferentes pares relacionados \((m, n)\), se pueden establecer diferentes parámetros \(\kappa_{(m,n)}\).
Relación con el warping temporal dinámico
El warping temporal dinámico es una técnica clásica para alinear dos series temporales encontrando un camino de warping óptimo que minimice la distancia acumulativa. El DTW trata cada par de forma independiente, resolviendo un problema de camino más corto en una cuadrícula. El GTW extiende esto acoplando múltiples caminos de warping mediante una penalización en sus distancias por pares. Cuando \(\kappa = 0\), el GTW se reduce al DTW independiente para cada par. Cuando \(\kappa > 0\), se fomenta que los caminos de warping sean similares, lo cual es beneficioso cuando las secuencias subyacentes comparten distorsiones temporales comunes.
Solución mediante flujo máximo
El GTW transforma el problema de camino más corto equivalente al DTW en un problema de flujo máximo en el grafo dual. Las restricciones o similitudes entre caminos de warping se modelan como aristas o capacidades adicionales. Esta formulación de grafo dual permite resolver la optimización conjunta utilizando algoritmos estándar de flujo máximo. Sin embargo, para conjuntos de datos grandes, los algoritmos genéricos de flujo máximo resultan lentos y consumen mucha memoria.
Para abordar la escalabilidad, se desarrolló un algoritmo eficiente llamado empuje bidireccional con operaciones de componentes lineales (BILCO, por sus siglas en inglés), específicamente para el GTW. BILCO explota la estructura del grafo dual y logra una mejora promedio de 10 veces tanto en tiempo computacional como en uso de memoria en comparación con los algoritmos genéricos de flujo máximo de última generación en aplicaciones de GTW.
Aplicaciones
El GTW se ha aplicado en varios dominios donde surgen series temporales interdependientes:
- Análisis de propagación de señales en bioimagen con lapso de tiempo: Los píxeles adyacentes suelen mostrar patrones de propagación similares, lo que hace que el GTW sea adecuado para rastrear frentes de onda o señales celulares.
- Identificación de firmas: Las firmas manuscritas pueden tratarse como secuencias; alinear múltiples firmas conjuntamente mejora el reconocimiento.
- Cálculo de profundidad estéreo binocular: Los mapas de disparidad de imágenes izquierda y derecha se pueden alinear con el GTW para mejorar la estimación de profundidad.
- Alineación de perfiles LC-MS en proteómica: Los perfiles cromatográficos y espectrométricos de masas de múltiples muestras se benefician de la alineación conjunta para corregir los cambios en el tiempo de retención.
Estas aplicaciones comparten la propiedad de que las secuencias no son independientes, sino que exhiben correlaciones espaciales o temporales que el GTW aprovecha.