Dynamische Zeitverzerrung (DTW) ist ein Algorithmus, der eine optimale Ausrichtung zwischen zwei Zeitreihensequenzen berechnet, die sich in Geschwindigkeit, Dauer oder Phase unterscheiden können. Im Gegensatz zu einfacheren Distanzmaßen wie der euklidischen Distanz, die Punkte zu identischen Zeitindizes vergleicht, ermöglicht DTW eine nichtlineare Verzerrung der Zeitachse, um die bestmögliche Übereinstimmung zwischen den Sequenzen zu finden. Diese Eigenschaft macht DTW besonders effektiv für den Vergleich von Signalen mit zeitlicher Variabilität, wie gesprochene Wörter mit unterschiedlichen Sprechgeschwindigkeiten, handgeschriebene Zeichen oder Sensordaten verschiedener Geräte.
Der Algorithmus wurde in den 1970er Jahren im Kontext der Spracherkennung eingeführt, wo er zu einer grundlegenden Technik wurde, bevor maschinelles Lernen-Modelle weit verbreitet waren. Sein Kernprinzip ist die dynamische Programmierung: Er konstruiert eine Kostenmatrix, die die Distanzen zwischen jedem Punktpaar der beiden Sequenzen akkumuliert, und findet dann den Pfad durch diese Matrix, der die gesamte kumulative Distanz minimiert. Der resultierende Verzerrungspfad zeigt an, welche Punkte in einer Sequenz welchen Punkten in der anderen entsprechen, und die endgültige DTW-Distanz ist die Summe der Distanzen entlang dieses optimalen Pfads.
Historische Entwicklung
Die früheste veröffentlichte Arbeit zu DTW wird oft Hiroaki Sakoe und Seibi Chiba zugeschrieben, die 1978 den Algorithmus mit Einschränkungen zur Verbesserung von Effizienz und Robustheit formalisierten. Ihr Papier „Dynamic programming algorithm optimization for spoken word recognition" führte das Sakoe-Chiba-Band ein, eine gängige Einschränkung, die das zulässige Verzerrungsfenster begrenzt, um Rechenkosten zu reduzieren und pathologische Ausrichtungen zu verhindern. Etwa zur gleichen Zeit erforschten Wissenschaftler bei Xerox PARC und anderen Institutionen ähnliche dynamische Programmieransätze für den Musterabgleich, aber Sakoe und Chibas Formulierung wurde zur Standardreferenz.
In den 1980er Jahren war DTW die dominierende Methode für die Erkennung isolierter Wörter in Sprachsystemen und wurde oft auf dedizierter Hardware implementiert. Später wurde es durch verborgene Markov-Modelle (HMMs) und in jüngerer Zeit durch Deep-Learning-Ansätze wie neuronale Netze-basierte akustische Modelle ersetzt. DTW blieb jedoch einflussreich als Benchmark und als Werkzeug zur Ausrichtung von Trainingsdaten.
Algorithmische Details
Der DTW-Algorithmus arbeitet mit zwei Sequenzen, X = (x1, x2, ..., xn) und Y = (y1, y2, ..., ym), wobei jedes xi und yj Merkmalsvektoren sind (oft Skalarwerte oder mehrdimensionale Punkte). Der Algorithmus erstellt eine n-mal-m-Matrix D, wobei jede Zelle D(i, j) die kumulative Distanz der besten Ausrichtung enthält, die an dieser Zelle endet. Die Rekursionsbeziehung lautet:
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
wobei d(xi, yj) ein lokales Distanzmaß ist, typischerweise die euklidische Distanz für kontinuierliche Daten oder die absolute Differenz für Skalarwerte. Die endgültige DTW-Distanz ist D(n, m), und der optimale Verzerrungspfad kann durch Rückverfolgung von dieser Zelle rekonstruiert werden.
Um die Effizienz zu verbessern und degenerierte Ausrichtungen zu vermeiden, werden häufig mehrere Einschränkungen angewendet. Das Sakoe-Chiba-Band begrenzt den Verzerrungspfad auf ein diagonal verlaufendes Band fester Breite und reduziert den Suchraum von O(nm) auf O(nBandbreite). Das Itakura-Parallelogramm, benannt nach Fumitada Itakura, verwendet eine Steigungsbeschränkung, die die Steilheit des Pfads begrenzt. Zusätzlich erfordern Randbedingungen, dass der Pfad bei (1,1) beginnt und bei (n,m) endet, und Monotonie stellt sicher, dass Indizes niemals abnehmen.
Anwendungen
DTW findet Anwendungen in vielen Bereichen. In der Spracherkennung wurde es verwendet, um gesprochene Wörter mit Vorlagen zu vergleichen, insbesondere für Aufgaben mit kleinem Vokabular. In der Zeitreihenanalyse (ein verwandtes Feld, das nicht in der bereitgestellten Slug-Liste enthalten ist) ist DTW ein Standardwerkzeug für Clustering und Klassifikation und übertrifft oft die euklidische Distanz bei Datensätzen mit zeitlicher Fehlausrichtung. Beispielsweise kann DTW bei der Gestenerkennung aus Beschleunigungsmesserdaten Gesten abgleichen, die mit unterschiedlichen Geschwindigkeiten ausgeführt werden.
In der Bioinformatik wurde DTW zur Ausrichtung von Genexpressionsprofilen oder Proteinsequenzen angewendet, obwohl es weniger verbreitet ist als Sequenzalignierungsalgorithmen wie Needleman-Wunsch. Im Finanzwesen wird DTW verwendet, um Aktienkursbewegungen oder Wirtschaftsindikatoren im Zeitverlauf zu vergleichen. In der Robotik hilft DTW, Sensordaten aus verschiedenen Versuchen für das Lernen durch Demonstration auszurichten. Der Algorithmus wird auch in Datenaugmentierung verwendet, um synthetische Trainingsbeispiele durch Verzerrung bestehender Zeitreihen zu erzeugen.
Varianten und Erweiterungen
Mehrere Varianten von DTW wurden entwickelt, um spezifische Einschränkungen zu adressieren. Derivative DTW (DDTW) verwendet die erste Ableitung der Sequenzen anstelle der Rohwerte, was es robuster gegenüber Offset- und Skalierungsunterschieden macht. Gewichtetes DTW weist verschiedenen Dimensionen der Merkmalsvektoren unterschiedliche Gewichte zu. Soft-DTW, eingeführt 2017 von Marco Cuturi und Mathieu Blondel, ersetzt die Min-Operation durch ein weiches Minimum, wodurch die Distanz differenzierbar wird und somit als Verlustfunktion in Deep-Learning-Pipelines verwendet werden kann.
Multivariates DTW behandelt Sequenzen mit mehreren Kanälen, und Teilsequenz-DTW findet die beste übereinstimmende Teilsequenz innerhalb einer längeren Sequenz. Für große Datensätze verwenden approximative Methoden wie FastDTW mehrskalige Ansätze, um die Rechenkomplexität zu reduzieren. Diese Erweiterungen haben DTW in der modernen Forschung relevant gehalten, insbesondere im Kontext von maschinellem Lernen, wo differenzierbare Versionen ein End-to-End-Training ermöglichen.
Beziehung zur modernen KI
Obwohl DTW keine Deep-Learning-Methode ist, bleibt es im Zeitalter der künstlichen Intelligenz relevant. Es wird oft als Vorverarbeitungsschritt verwendet, um Zeitreihen auszurichten, bevor sie in neuronale Netze-Modelle wie Residualnetzwerke oder U-Net-Architekturen für Sequenzvorhersage eingespeist werden. In der Spracherkennung (ein Konzept, das nicht in der Slug-Liste enthalten ist) wird DTW weiterhin für Keyword-Spotting in ressourcenarmen Umgebungen verwendet. Die Prinzipien der dynamischen Programmierung erscheinen auch in Sequenz-zu-Sequenz-Modellen, wo die Ausrichtung implizit durch Aufmerksamkeitsmechanismen gelernt wird, anstatt explizit zu sein.
Forscher an Institutionen wie MIT CSAIL und Stanford AI Lab haben hybride Ansätze untersucht, die DTW mit Deep Learning für Aufgaben wie Zeitreihenklassifikation und Anomalieerkennung kombinieren. Die Differenzierbarkeit von Soft-DTW hat seine Integration in Verlustfunktionen für das Training von Modellen ermöglicht, die zeitliche Ausrichtung erfordern. Ab den frühen 2020er Jahren bleibt DTW ein Standard-Baseline in Zeitreihen-Benchmarks, und seine Recheneffizienz bleibt ein Forschungsthema, wobei Optimierungen für GPU- und AWS Trainium-Hardware untersucht werden.