Dynamic time warping (DTW) é um algoritmo que calcula um alinhamento ótimo entre duas sequências de séries temporais que podem variar em velocidade, duração ou fase. Diferentemente de medidas de distância mais simples, como a distância euclidiana, que compara pontos em índices temporais idênticos, o DTW permite um warping não linear do eixo temporal para encontrar a melhor correspondência possível entre as sequências. Essa propriedade torna o DTW particularmente eficaz para comparar sinais que exibem variabilidade temporal, como palavras faladas em ritmos diferentes, caracteres manuscritos ou leituras de sensores de dispositivos distintos.
O algoritmo foi introduzido na década de 1970 no contexto do reconhecimento de fala, onde se tornou uma técnica fundamental antes da adoção generalizada de modelos de aprendizado de máquina. Seu princípio central é a programação dinâmica: ele constrói uma matriz de custos que acumula as distâncias entre cada par de pontos das duas sequências e, em seguida, encontra o caminho através dessa matriz que minimiza a distância cumulativa total. O caminho de warping resultante indica quais pontos de uma sequência correspondem a quais pontos da outra, e a distância final do DTW é a soma das distâncias ao longo desse caminho ótimo.
Desenvolvimento Histórico
O primeiro trabalho publicado sobre DTW é frequentemente atribuído a Hiroaki Sakoe e Seibi Chiba, que em 1978 formalizaram o algoritmo com restrições para melhorar a eficiência e a robustez. Seu artigo, "Dynamic programming algorithm optimization for spoken word recognition", introduziu a banda de Sakoe-Chiba, uma restrição comum que limita a janela de warping permitida para reduzir o custo computacional e evitar alinhamentos patológicos. Na mesma época, pesquisadores da Xerox PARC e de outras instituições exploraram abordagens semelhantes de programação dinâmica para correspondência de padrões, mas a formulação de Sakoe e Chiba tornou-se a referência padrão.
Durante a década de 1980, o DTW foi o método dominante para reconhecimento de palavras isoladas em sistemas de fala, frequentemente implementado em hardware dedicado. Mais tarde, foi superado por modelos ocultos de Markov (HMMs) e, mais recentemente, por abordagens de aprendizado profundo, como modelos acústicos baseados em redes neurais. No entanto, o DTW permaneceu influente como referência e como ferramenta para alinhar dados de treinamento.
Detalhes Algorítmicos
O algoritmo DTW opera em duas sequências, X = (x1, x2, ..., xn) e Y = (y1, y2, ..., ym), onde cada xi e yj são vetores de características (frequentemente valores escalares ou pontos multidimensionais). O algoritmo constrói uma matriz D de n por m, onde cada célula D(i, j) contém a distância cumulativa do melhor alinhamento que termina nessa célula. A relação de recorrência é:
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
onde d(xi, yj) é uma medida de distância local, tipicamente a distância euclidiana para dados contínuos ou a diferença absoluta para valores escalares. A distância final do DTW é D(n, m), e o caminho de warping ótimo pode ser recuperado por retrocesso a partir dessa célula.
Para melhorar a eficiência e evitar alinhamentos degenerados, várias restrições são comumente aplicadas. A banda de Sakoe-Chiba restringe o caminho de warping a uma banda diagonal de largura fixa, reduzindo o espaço de busca de O(nm) para O(nlargura da banda). O paralelogramo de Itakura, nomeado em homenagem a Fumitada Itakura, usa uma restrição de inclinação que limita a inclinação do caminho. Além disso, condições de contorno exigem que o caminho comece em (1,1) e termine em (n,m), e a monotonicidade garante que os índices nunca diminuam.
Aplicações
O DTW encontrou aplicações em muitos domínios. No reconhecimento de fala, foi usado para comparar palavras faladas com modelos, particularmente para tarefas de vocabulário pequeno. Na análise de séries temporais (um campo relacionado, embora não na lista de slugs fornecida), o DTW é uma ferramenta padrão para agrupamento e classificação, frequentemente superando a distância euclidiana em conjuntos de dados com desalinhamento temporal. Por exemplo, no reconhecimento de gestos a partir de dados de acelerômetro, o DTW pode corresponder a gestos realizados em velocidades diferentes.
Em bioinformática, o DTW foi aplicado para alinhar perfis de expressão gênica ou sequências de proteínas, embora seja menos comum do que algoritmos de alinhamento de sequências como Needleman-Wunsch. Em finanças, o DTW é usado para comparar movimentos de preços de ações ou indicadores econômicos ao longo do tempo. Em robótica, o DTW ajuda a alinhar leituras de sensores de diferentes tentativas para aprendizado por demonstração. O algoritmo também é usado em aumento de dados para gerar exemplos de treinamento sintéticos ao deformar séries temporais existentes.
Variantes e Extensões
Várias variantes do DTW foram desenvolvidas para abordar limitações específicas. O DTW derivativo (DDTW) usa a primeira derivada das sequências em vez dos valores brutos, tornando-o mais robusto a diferenças de deslocamento e escala. O DTW ponderado atribui pesos diferentes a diferentes dimensões dos vetores de características. O Soft-DTW, introduzido em 2017 por Marco Cuturi e Mathieu Blondel, substitui a operação de mínimo por um mínimo suave, tornando a distância diferenciável e, portanto, utilizável como função de perda em pipelines de aprendizado profundo.
O DTW multivariado lida com sequências de múltiplos canais, e o DTW de subsequência encontra a melhor subsequência correspondente dentro de uma sequência mais longa. Para grandes conjuntos de dados, métodos aproximados como o FastDTW usam abordagens multiescala para reduzir a complexidade computacional. Essas extensões mantiveram o DTW relevante na pesquisa moderna, particularmente no contexto de aprendizado de máquina, onde versões diferenciáveis permitem treinamento de ponta a ponta.
Relação com a IA Moderna
Embora o DTW não seja um método de aprendizado profundo, ele permanece relevante na era da inteligência artificial. É frequentemente usado como etapa de pré-processamento para alinhar séries temporais antes de alimentá-las em modelos de redes neurais, como arquiteturas de rede residual ou U-Net para previsão de sequências. No reconhecimento de fala (um conceito não presente na lista de slugs), o DTW ainda é usado para detecção de palavras-chave em ambientes de baixos recursos. Os princípios de programação dinâmica do algoritmo também aparecem em modelos sequência a sequência, onde o alinhamento é aprendido implicitamente por mecanismos de atenção, em vez de explicitamente.
Pesquisadores em instituições como MIT CSAIL e Stanford AI Lab exploraram abordagens híbridas que combinam DTW com aprendizado profundo para tarefas como classificação de séries temporais e detecção de anomalias. A diferenciabilidade do Soft-DTW permitiu sua integração em funções de perda para treinar modelos que exigem alinhamento temporal. No início da década de 2020, o DTW continua sendo uma referência padrão em benchmarks de séries temporais, e sua eficiência computacional permanece um tópico de estudo, com otimizações para hardware GPU e AWS Trainium sendo exploradas.