Dynamic Time Warping

Também chamado: DTW
Categoria: Learning & autonomy › Learning from demonstration
Tags: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

Um algoritmo de programação dinâmica que alinha duas séries temporais de velocidades ou comprimentos diferentes encontrando o pareamento de suas amostras que preserva a ordem e tem a menor distância total.

Definição

O dynamic time warping (DTW) compara duas sequências que seguem um padrão semelhante, mas em velocidades diferentes, como duas demonstrações do mesmo movimento em que um operador fez uma pausa e o outro se moveu depressa. Em vez de comparar a amostra i com a amostra i, o DTW busca um caminho de alinhamento (warping path), um pareamento de amostras das duas sequências que começa nos dois inícios, termina nos dois finais e nunca volta no tempo. Cada amostra pode ser pareada com uma ou várias amostras da outra sequência, de modo que esticamentos e compressões no tempo são absorvidos pelo alinhamento. A distância DTW é o custo total ao longo do melhor caminho, e o próprio caminho diz quais instantes se correspondem.

O algoritmo padrão preenche uma matriz de custos por programação dinâmica. Com uma distância local d(i, j) entre a amostra i de uma sequência e a amostra j da outra, o custo acumulado é D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1)), e retroceder a partir da célula final recupera o caminho. Isso leva tempo e memória proporcionais ao produto dos dois comprimentos. Sakoe e Chiba (1978) popularizaram o método para reconhecimento de palavras faladas e introduziram uma faixa em torno da diagonal que limita o quanto o alinhamento pode se desviar; o paralelogramo de Itakura é uma restrição relacionada. Essas janelas aceleram o cálculo e evitam alinhamentos patológicos em que uma amostra é pareada com um trecho longo da outra.

Várias variantes importam em robótica. O subsequence DTW relaxa as condições de início e fim para que uma consulta curta possa ser pareada com o segmento mais adequado de uma trajetória longa, o que permite a recuperação em grandes registros. O derivative DTW alinha pelas inclinações locais em vez dos valores brutos. O Soft-DTW, apresentado por Cuturi e Blondel em 2017, substitui o mínimo por uma versão suave para que o custo de alinhamento seja diferenciável e possa ser usado como perda de treinamento. O DTW alinha apenas no tempo: as características precisam ser comparáveis e geralmente normalizadas, e a distância resultante não é uma métrica verdadeira, porque não satisfaz a desigualdade triangular.

Por que importa

Os dados de robôs raramente chegam em uma velocidade comum. Demonstrações, trajetórias executadas e gravações de sensores diferem na temporização, e o DTW é a ferramenta padrão para colocá-los em uma linha do tempo comum antes de calcular médias, comparar, recuperar ou pontuar.

Principais aplicações

Alinhar várias demonstrações antes de calcular a média ou ajustar primitivas de movimento
Comparar trajetórias executadas pelo robô com trajetórias de referência
Recuperar segmentos correspondentes em grandes registros de trajetórias ou de sensores
Reconhecimento de gestos e atividades a partir de dados de movimento ou inerciais
Pontuar caminhos de navegação em relação a caminhos de referência com métricas DTW normalizadas
Sincronizar fluxos de sensores gravados em taxas diferentes

Na prática

Uma equipe coleta dez demonstrações cinestésicas de um movimento de despejar, cada uma com duração diferente e pausas em lugares diferentes. Para construir uma única referência para uma primitiva de movimento, eles escolhem uma demonstração como modelo, alinham cada uma das outras a ela com DTW sobre posições de juntas normalizadas e a velocidade do efetuador final, e reamostram todas na linha do tempo do modelo usando os caminhos de alinhamento. A média das trajetórias alinhadas dá um movimento médio limpo e uma variância por passo de tempo que mostra onde as demonstrações concordam. Uma faixa de Sakoe-Chiba impede que o alinhamento reduza pausas a amostras únicas. Mais tarde, o mesmo código de subsequence DTW procura nas trajetórias armazenadas da frota os segmentos que melhor correspondem a um movimento de consulta curto.

Equívocos comuns

A distância DTW é uma métrica — ela não satisfaz a desigualdade triangular, o que importa para métodos de indexação e agrupamento que a pressupõem
O DTW lida com qualquer diferença entre sequências — ele absorve diferenças de temporização, não deslocamentos nem escalas nos valores, então as características geralmente precisam ser normalizadas antes
O DTW sem restrições dá o melhor alinhamento — sem uma janela ele pode parear uma única amostra com trechos longos da outra sequência, produzindo alinhamentos sem significado físico
O DTW é lento demais para uso prático — faixas, limites inferiores e métodos aproximados o tornam rápido o suficiente para muitos usos em tempo real e em grande escala

Quem deve saber

Pesquisadores de aprendizado por demonstração
Engenheiros que analisam trajetórias e registros de robôs
Desenvolvedores de reconhecimento de gestos e atividades
Pesquisadores que avaliam políticas de navegação e manipulação

Tecnologias relacionadas

Soft-DTW
Faixa de Sakoe-Chiba
Subsequence DTW
FastDTW
tslearn

Termos relacionados

Projetos relacionados

PlotJuggler: Fast time-series visualization tool for ROS topics, rosbags, and robot debugging

Vídeos

How DTW (Dynamic Time Warping) algorithm works: Thales Sehn Körting