Dynamic Time Warping

Auch genannt: DTW
Kategorie: Learning & autonomy › Learning from demonstration
Schlagwörter: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

Ein Algorithmus der dynamischen Programmierung, der zwei Zeitreihen unterschiedlicher Geschwindigkeit oder Länge ausrichtet, indem er die ordnungserhaltende Paarung ihrer Samples mit der geringsten Gesamtdistanz findet.

Definition

Dynamic Time Warping (DTW) vergleicht zwei Sequenzen, die einem ähnlichen Muster folgen, aber mit unterschiedlicher Geschwindigkeit, etwa zwei Demonstrationen derselben Bewegung, bei denen ein Bediener innehielt und der andere sich schnell bewegte. Statt Sample i mit Sample i zu vergleichen, sucht DTW einen Warping-Pfad, eine Paarung von Samples der beiden Sequenzen, die an beiden Anfängen beginnt, an beiden Enden endet und nie in der Zeit zurückgeht. Jedes Sample kann einem oder mehreren Samples der anderen Sequenz zugeordnet werden, sodass Dehnungen und Stauchungen in der Zeit von der Ausrichtung aufgefangen werden. Die DTW-Distanz ist die Gesamtkosten entlang des besten Pfades, und der Pfad selbst zeigt, welche Zeitpunkte einander entsprechen.

Der Standardalgorithmus füllt eine Kostenmatrix durch dynamische Programmierung. Mit einer lokalen Distanz d(i, j) zwischen Sample i der einen und Sample j der anderen Sequenz ergeben sich die kumulierten Kosten als D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1)), und Rückverfolgung ab der letzten Zelle liefert den Pfad. Das kostet Zeit und Speicher proportional zum Produkt der beiden Längen. Sakoe und Chiba (1978) machten die Methode für die Erkennung gesprochener Wörter populär und führten ein Band um die Diagonale ein, das begrenzt, wie weit die Ausrichtung abdriften darf; das Itakura-Parallelogramm ist eine verwandte Beschränkung. Solche Fenster beschleunigen die Berechnung und verhindern pathologische Verzerrungen, bei denen ein Sample einem langen Abschnitt der anderen Sequenz zugeordnet wird.

In der Robotik sind mehrere Varianten wichtig. Subsequence DTW lockert die Start- und Endbedingungen, sodass eine kurze Anfrage dem am besten passenden Abschnitt einer langen Trajektorie zugeordnet werden kann, was die Suche in großen Logs unterstützt. Derivative DTW richtet nach lokalen Steigungen statt nach Rohwerten aus. Soft-DTW, 2017 von Cuturi und Blondel eingeführt, ersetzt das Minimum durch eine geglättete Version, sodass die Ausrichtungskosten differenzierbar sind und als Trainingsverlust dienen können. DTW richtet nur in der Zeit aus: Die Merkmale müssen vergleichbar und meist normalisiert sein, und die resultierende Distanz ist keine echte Metrik, da sie die Dreiecksungleichung nicht erfüllt.

Warum es wichtig ist

Roboterdaten kommen selten mit einheitlicher Geschwindigkeit an. Demonstrationen, ausgeführte Trajektorien und Sensoraufzeichnungen unterscheiden sich im Timing, und DTW ist das Standardwerkzeug, um sie auf eine gemeinsame Zeitachse zu bringen, bevor man sie mittelt, vergleicht, abruft oder bewertet.

Wichtige Anwendungen

Ausrichten mehrerer Demonstrationen vor dem Mitteln oder dem Anpassen von Bewegungsprimitiven
Vergleich ausgeführter Robotertrajektorien mit Referenztrajektorien
Abrufen passender Abschnitte aus großen Trajektorien- oder Sensorlogs
Gesten- und Aktivitätserkennung aus Bewegungs- oder Inertialdaten
Bewertung von Navigationspfaden gegenüber Referenzpfaden mit normalisierten DTW-Metriken
Synchronisieren von Sensordatenströmen, die mit unterschiedlichen Raten aufgezeichnet wurden

In der Praxis

Ein Team sammelt zehn kinästhetische Demonstrationen einer Gießbewegung, jede mit anderer Dauer und Pausen an verschiedenen Stellen. Um eine einzige Referenz für ein Bewegungsprimitiv zu erstellen, wählt es eine Demonstration als Vorlage, richtet jede andere Demonstration mit DTW auf normalisierten Gelenkpositionen und der Endeffektorgeschwindigkeit an ihr aus und tastet alle anhand der Warping-Pfade auf die Zeitachse der Vorlage um. Das Mitteln der ausgerichteten Trajektorien ergibt eine saubere mittlere Bewegung und eine Varianz pro Zeitschritt, die zeigt, wo die Demonstrationen übereinstimmen. Ein Sakoe-Chiba-Band verhindert, dass die Ausrichtung Pausen zu einzelnen Samples zusammenfallen lässt. Später durchsucht derselbe Subsequence-DTW-Code die gespeicherten Trajektorien der Flotte nach Abschnitten, die am besten zu einer kurzen Anfragebewegung passen.

Häufige Missverständnisse

Die DTW-Distanz ist eine Metrik — sie erfüllt die Dreiecksungleichung nicht, was für Indexierungs- und Clustering-Verfahren wichtig ist, die eine Metrik voraussetzen
DTW behandelt jeden Unterschied zwischen Sequenzen — es fängt Unterschiede im Timing auf, nicht Versätze oder Skalierungen der Werte, daher müssen Merkmale meist zuerst normalisiert werden
Unbeschränktes DTW liefert die beste Ausrichtung — ohne Fenster kann es ein einzelnes Sample langen Abschnitten der anderen Sequenz zuordnen und so Verzerrungen ohne physikalische Bedeutung erzeugen
DTW ist für den praktischen Einsatz zu langsam — Bänder, untere Schranken und Näherungsverfahren machen es schnell genug für viele Echtzeit- und Großanwendungen

Wer das wissen sollte

Forscher im Lernen aus Demonstrationen
Ingenieure, die Robotertrajektorien und Logs analysieren
Entwickler von Gesten- und Aktivitätserkennung
Forscher, die Navigations- und Manipulations-Policies bewerten

Videos

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

Open Source Robotics