Graphical time warping (GTW) é uma estrutura para alinhar conjuntamente múltiplos pares de séries temporais ou sequências. Diferentemente do dynamic time warping (DTW), que alinha cada par de forma independente, minimizando apenas a distância entre as duas sequências de um dado par, o GTW considera tanto a precisão do alinhamento de cada par de sequências quanto a similaridade entre os pares. Essa otimização conjunta permite que o GTW alcance melhor desempenho de alinhamento quando se espera similaridade entre os pares, generalizando o DTW como um caso especial.
A estrutura é aplicável a qualquer dado estruturado com séries temporais ou sequências interdependentes. As aplicações incluem análise de propagação de sinais em dados de bio-imagem time-lapse, identificação de assinaturas, cálculo de profundidade estereoscópica binocular e alinhamento de perfis de cromatografia líquida acoplada à espectrometria de massas (LC-MS) na análise de dados de proteômica. Nesses contextos, sequências adjacentes ou relacionadas frequentemente exibem padrões de warping semelhantes, que o GTW explora para melhorar a qualidade do alinhamento.
Formulação
O GTW formula o problema de alinhamento conjunto como uma minimização sobre um conjunto de caminhos de warping. Dados \(N\) pares de séries temporais \((x_n, y_n)\) para \(n = 1, 2, ..., N\), cada par tem um caminho de warping correspondente \(P_n\). Alguns pares de caminhos de warping são conhecidos por serem semelhantes, denotados pelo conjunto \(Neib\). O objetivo é minimizar:
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
Aqui, \(cost(P_n)\) é a distância entre \(x_n\) e \(y_n\) após o alinhamento com a função de warping \(P_n\). O termo \(dist(P_m, P_n)\) mede a distância entre dois caminhos de warping, definida como a área da região delimitada por \(P_m\) e \(P_n\). O hiperparâmetro \(\kappa\) equilibra o termo de custo de alinhamento e o termo de distância da função de warping. A força da similaridade pode ser específica da aplicação; para diferentes pares relacionados \((m, n)\), diferentes parâmetros \(\kappa_{(m,n)}\) podem ser definidos.
Relação com o Dynamic Time Warping
O dynamic time warping é uma técnica clássica para alinhar duas séries temporais, encontrando um caminho de warping ótimo que minimiza a distância cumulativa. O DTW trata cada par de forma independente, resolvendo um problema de caminho mais curto em uma grade. O GTW estende isso acoplando múltiplos caminhos de warping por meio de uma penalidade em suas distâncias aos pares. Quando \(\kappa = 0\), o GTW se reduz ao DTW independente para cada par. Quando \(\kappa > 0\), os caminhos de warping são incentivados a serem semelhantes, o que é benéfico quando as sequências subjacentes compartilham distorções temporais comuns.
Solução via Fluxo Máximo
O GTW transforma o problema de caminho mais curto equivalente ao DTW em um problema de fluxo máximo no grafo dual. As restrições ou similaridades entre os caminhos de warping são modeladas como arestas ou capacidades adicionais. Essa formulação em grafo dual permite que a otimização conjunta seja resolvida usando algoritmos padrão de fluxo máximo. No entanto, para grandes conjuntos de dados, algoritmos genéricos de fluxo máximo tornam-se demorados e intensivos em memória.
Para abordar a escalabilidade, um algoritmo eficiente chamado Bidirectional pushing with Linear Component Operations (BILCO) foi desenvolvido especificamente para o GTW. O BILCO explora a estrutura do grafo dual e alcança uma melhoria média de 10 vezes tanto no tempo computacional quanto no uso de memória em comparação com algoritmos genéricos de fluxo máximo de última geração em aplicações de GTW.
Aplicações
O GTW foi aplicado em vários domínios onde surgem séries temporais interdependentes:
- Análise de propagação de sinais em bio-imagem time-lapse: Pixels adjacentes frequentemente mostram padrões de propagação semelhantes, tornando o GTW adequado para rastrear frentes de onda ou sinais celulares.
- Identificação de assinaturas: Assinaturas manuscritas podem ser tratadas como sequências; alinhar múltiplas assinaturas conjuntamente melhora o reconhecimento.
- Cálculo de profundidade estereoscópica binocular: Mapas de disparidade de imagens esquerda e direita podem ser alinhados com o GTW para melhorar a estimativa de profundidade.
- Alinhamento de perfis LC-MS em proteômica: Perfis cromatográficos e espectrométricos de múltiplas amostras se beneficiam do alinhamento conjunto para corrigir deslocamentos de tempo de retenção.
Essas aplicações compartilham a propriedade de que as sequências não são independentes, mas exibem correlações espaciais ou temporais que o GTW explora.