Dynamic Time Warping

• Detto anche: DTW
• Categoria: Learning & autonomy › Learning from demonstration
• Tag: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

Un algoritmo di programmazione dinamica che allinea due serie temporali con velocità o lunghezze diverse trovando l'abbinamento dei loro campioni che preserva l'ordine e ha la distanza totale minima.

Definizione

Il dynamic time warping (DTW) confronta due sequenze che seguono un andamento simile ma a velocità diverse, come due dimostrazioni dello stesso movimento in cui un operatore ha fatto una pausa e l'altro si è mosso in fretta. Invece di confrontare il campione i con il campione i, il DTW cerca un percorso di allineamento (warping path), un abbinamento dei campioni delle due sequenze che parte da entrambi gli inizi, termina in entrambe le fini e non torna mai indietro nel tempo. Ogni campione può essere abbinato a uno o più campioni dell'altra sequenza, così che allungamenti e compressioni nel tempo vengono assorbiti dall'allineamento. La distanza DTW è il costo totale lungo il percorso migliore, e il percorso stesso dice quali istanti si corrispondono.

L'algoritmo standard riempie una matrice dei costi con la programmazione dinamica. Con una distanza locale d(i, j) tra il campione i di una sequenza e il campione j dell'altra, il costo cumulativo è D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1)), e risalire a ritroso dalla cella finale restituisce il percorso. Questo richiede tempo e memoria proporzionali al prodotto delle due lunghezze. Sakoe e Chiba (1978) hanno reso popolare il metodo per il riconoscimento delle parole pronunciate e hanno introdotto una banda attorno alla diagonale che limita quanto l'allineamento possa scostarsi; il parallelogramma di Itakura è un vincolo correlato. Queste finestre accelerano il calcolo ed evitano allineamenti patologici in cui un campione viene abbinato a un lungo tratto dell'altra sequenza.

Diverse varianti contano in robotica. Il subsequence DTW rilassa le condizioni di inizio e fine così che una query breve possa essere abbinata al segmento più adatto di una traiettoria lunga, il che permette la ricerca in grandi log. Il derivative DTW allinea sulle pendenze locali invece che sui valori grezzi. Il Soft-DTW, introdotto da Cuturi e Blondel nel 2017, sostituisce il minimo con una versione smussata così che il costo di allineamento sia differenziabile e possa essere usato come loss di addestramento. Il DTW allinea solo nel tempo: le feature devono essere confrontabili e di solito normalizzate, e la distanza risultante non è una vera metrica perché non soddisfa la disuguaglianza triangolare.

Perché è importante

I dati dei robot arrivano raramente a una velocità comune. Dimostrazioni, traiettorie eseguite e registrazioni dei sensori differiscono nella temporizzazione, e il DTW è lo strumento standard per metterli su una linea temporale comune prima di farne la media, confrontarli, recuperarli o valutarli.

Applicazioni principali

• Allineare più dimostrazioni prima di farne la media o di adattare primitive di movimento
• Confrontare le traiettorie eseguite dal robot con traiettorie di riferimento
• Recuperare segmenti corrispondenti da grandi log di traiettorie o di sensori
• Riconoscimento di gesti e attività da dati di movimento o inerziali
• Valutare percorsi di navigazione rispetto a percorsi di riferimento con metriche DTW normalizzate
• Sincronizzare flussi di sensori registrati a frequenze diverse

In pratica

Un team raccoglie dieci dimostrazioni cinestetiche di un movimento di versamento, ciascuna con una durata diversa e pause in punti diversi. Per costruire un unico riferimento per una primitiva di movimento, sceglie una dimostrazione come modello, allinea a essa ciascuna delle altre con il DTW su posizioni dei giunti normalizzate e velocità dell'end effector, e ricampiona tutte sulla linea temporale del modello usando i percorsi di allineamento. La media delle traiettorie allineate dà un movimento medio pulito e una varianza per passo temporale che mostra dove le dimostrazioni concordano. Una banda di Sakoe-Chiba impedisce che l'allineamento riduca le pause a singoli campioni. In seguito, lo stesso codice di subsequence DTW cerca nelle traiettorie memorizzate della flotta i segmenti che corrispondono meglio a un breve movimento di query.

Idee sbagliate comuni

• La distanza DTW è una metrica — non soddisfa la disuguaglianza triangolare, il che conta per i metodi di indicizzazione e clustering che la presuppongono
• Il DTW gestisce qualsiasi differenza tra sequenze — assorbe le differenze di temporizzazione, non gli scostamenti o le scale nei valori, quindi le feature di solito vanno prima normalizzate
• Il DTW senza vincoli dà l'allineamento migliore — senza una finestra può abbinare un solo campione a lunghi tratti dell'altra sequenza, producendo allineamenti senza significato fisico
• Il DTW è troppo lento per l'uso pratico — bande, limiti inferiori e metodi approssimati lo rendono abbastanza veloce per molti usi in tempo reale e su larga scala

Chi dovrebbe saperlo

• Ricercatori di apprendimento da dimostrazione
• Ingegneri che analizzano traiettorie e log dei robot
• Sviluppatori di riconoscimento di gesti e attività
• Ricercatori che valutano policy di navigazione e manipolazione

Tecnologie correlate

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

Termini correlati

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

Progetti correlati

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

Video

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