Dynamic Time Warping

• También llamado: DTW
• Categoría: Learning & autonomy › Learning from demonstration
• Etiquetas: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

Un algoritmo de programación dinámica que alinea dos series temporales de velocidades o longitudes distintas encontrando el emparejamiento de sus muestras que conserva el orden y tiene la menor distancia total.

Definición

El dynamic time warping (DTW) compara dos secuencias que siguen un patrón similar pero a velocidades distintas, como dos demostraciones del mismo movimiento en las que un operador hizo una pausa y el otro se movió deprisa. En lugar de comparar la muestra i con la muestra i, el DTW busca un camino de alineamiento (warping path), un emparejamiento de muestras de las dos secuencias que empieza en ambos comienzos, termina en ambos finales y nunca retrocede en el tiempo. Cada muestra puede emparejarse con una o varias muestras de la otra secuencia, de modo que los estiramientos y las compresiones en el tiempo los absorbe el alineamiento. La distancia DTW es el coste total a lo largo del mejor camino, y el propio camino indica qué instantes se corresponden.

El algoritmo estándar rellena una matriz de costes mediante programación dinámica. Con una distancia local d(i, j) entre la muestra i de una secuencia y la muestra j de la otra, el coste acumulado es D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1)), y retroceder desde la celda final recupera el camino. Esto requiere un tiempo y una memoria proporcionales al producto de las dos longitudes. Sakoe y Chiba (1978) popularizaron el método para el reconocimiento de palabras habladas e introdujeron una banda alrededor de la diagonal que limita cuánto puede desviarse el alineamiento; el paralelogramo de Itakura es una restricción relacionada. Estas ventanas aceleran el cálculo y evitan alineamientos patológicos en los que una muestra se empareja con un tramo largo de la otra.

Varias variantes importan en robótica. El subsequence DTW relaja las condiciones de inicio y fin para que una consulta corta pueda emparejarse con el segmento que mejor encaja dentro de una trayectoria larga, lo que permite la recuperación en registros grandes. El derivative DTW alinea según las pendientes locales en lugar de los valores brutos. El Soft-DTW, presentado por Cuturi y Blondel en 2017, sustituye el mínimo por una versión suave para que el coste de alineamiento sea diferenciable y pueda usarse como pérdida de entrenamiento. El DTW solo alinea en el tiempo: las características deben ser comparables y normalmente normalizadas, y la distancia resultante no es una verdadera métrica porque no cumple la desigualdad triangular.

Por qué importa

Los datos de los robots rara vez llegan a una velocidad común. Las demostraciones, las trayectorias ejecutadas y las grabaciones de sensores difieren en su temporización, y el DTW es la herramienta estándar para ponerlos en una línea temporal común antes de promediarlos, compararlos, recuperarlos o puntuarlos.

Aplicaciones clave

• Alinear varias demostraciones antes de promediarlas o de ajustar primitivas de movimiento
• Comparar trayectorias de robot ejecutadas con trayectorias de referencia
• Recuperar segmentos coincidentes de grandes registros de trayectorias o de sensores
• Reconocimiento de gestos y actividades a partir de datos de movimiento o inerciales
• Puntuar caminos de navegación frente a caminos de referencia con métricas DTW normalizadas
• Sincronizar flujos de sensores grabados a frecuencias distintas

En la práctica

Un equipo recoge diez demostraciones kinestésicas de un movimiento de verter, cada una con una duración distinta y pausas en lugares distintos. Para construir una única referencia para una primitiva de movimiento, eligen una demostración como plantilla, alinean cada una de las demás con ella mediante DTW sobre posiciones articulares normalizadas y la velocidad del efector final, y remuestrean todas sobre la línea temporal de la plantilla usando los caminos de alineamiento. Promediar las trayectorias alineadas da un movimiento medio limpio y una varianza por paso de tiempo que muestra dónde coinciden las demostraciones. Una banda de Sakoe-Chiba impide que el alineamiento reduzca las pausas a muestras únicas. Más tarde, el mismo código de subsequence DTW busca en las trayectorias almacenadas de la flota los segmentos que mejor coinciden con un movimiento de consulta corto.

Ideas erróneas comunes

• La distancia DTW es una métrica — no cumple la desigualdad triangular, lo que importa para los métodos de indexación y agrupamiento que la presuponen
• El DTW maneja cualquier diferencia entre secuencias — absorbe diferencias de temporización, no desplazamientos ni escalados de los valores, así que las características suelen necesitar normalización previa
• El DTW sin restricciones da el mejor alineamiento — sin una ventana puede emparejar una sola muestra con tramos largos de la otra secuencia, produciendo alineamientos sin significado físico
• El DTW es demasiado lento para el uso práctico — las bandas, las cotas inferiores y los métodos aproximados lo hacen lo bastante rápido para muchos usos en tiempo real y a gran escala

Quién debería saberlo

• Investigadores en aprendizaje por demostración
• Ingenieros que analizan trayectorias y registros de robots
• Desarrolladores de reconocimiento de gestos y actividades
• Investigadores que evalúan políticas de navegación y manipulación

Tecnologías relacionadas

• Soft-DTW
• Banda de Sakoe-Chiba
• Subsequence DTW
• FastDTW
• tslearn

Términos relacionados

• Dynamic Movement Primitive
• Imitation Learning
• Kinesthetic Teaching
• Behavior Cloning
• Success Weighted by Path Length

Proyectos 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