動的時間伸縮法（DTW）は、速度、持続時間、または位相が異なる可能性のある2つの時系列シーケンス間の最適なアライメントを計算するアルゴリズムである。ユークリッド距離などの単純な距離尺度が同一の時間インデックスで点を比較するのとは異なり、DTWは時間軸の非線形なワーピングを可能にし、シーケンス間の最良の一致を見つける。この特性により、DTWは、異なる速度で話される音声単語、手書き文字、または異なるデバイスからのセンサー読み取りなど、時間的変動を示す信号の比較に特に効果的である。
このアルゴリズムは1970年代に音声認識の文脈で導入され、Machine learningモデルが広く採用される前の基礎的な技術となった。その中核原理は動的計画法であり、2つのシーケンスからのすべての点のペア間の距離を蓄積するコスト行列を構築し、この行列を通る累積距離の合計を最小化する経路を見つける。結果として得られるワーピング経路は、一方のシーケンスのどの点が他方のどの点に対応するかを示し、最終的なDTW距離はこの最適経路に沿った距離の合計である。
歴史的発展
DTWに関する最も初期の発表された研究は、しばしば桜井宏明と千葉誠一に帰属され、彼らは1978年に効率と堅牢性を向上させるための制約を伴うアルゴリズムを形式化した。彼らの論文「音声単語認識のための動的計画法アルゴリズムの最適化」は、計算コストを削減し病的なアライメントを防ぐための許容ワーピングウィンドウを制限する一般的な制約であるSakoe-Chibaバンドを導入した。ほぼ同時期に、Xerox PARCや他の機関の研究者もパターンマッチングのための類似の動的計画法アプローチを探求したが、桜井と千葉の定式化が標準的な参照となった。
1980年代を通じて、DTWは音声システムにおける孤立単語認識の支配的な方法であり、しばしば専用ハードウェアで実装された。その後、隠れマルコフモデル（HMM）や、より最近ではDeep learningアプローチ（Neural networkベースの音響モデルなど）によって取って代わられた。しかし、DTWはベンチマークとして、またトレーニングデータを整列させるためのツールとして影響力を持ち続けた。
アルゴリズムの詳細
DTWアルゴリズムは、X = (x1, x2, ..., xn)とY = (y1, y2, ..., ym)の2つのシーケンスで動作し、各xiとyjは特徴ベクトル（多くの場合、スカラー値または多次元点）である。アルゴリズムはn行m列の行列Dを構築し、各セルD(i, j)はそのセルで終わる最良のアライメントの累積距離を含む。漸化式は次のとおりである：
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
ここで、d(xi, yj)は局所距離尺度であり、連続データには典型的にユークリッド距離、スカラー値には絶対差が使用される。最終的なDTW距離はD(n, m)であり、最適なワーピング経路はそのセルからバックトラッキングすることで回復できる。
効率を改善し、退化したアライメントを避けるために、いくつかの制約が一般的に適用される。Sakoe-Chibaバンドはワーピング経路を固定幅の対角バンドに制限し、探索空間をO(nm)からO(nバンド幅)に削減する。Fumitada Itakuraにちなんで名付けられたItakura平行四辺形は、経路の急峻さを制限する傾斜制約を使用する。さらに、境界条件は経路が(1,1)で始まり(n,m)で終わることを要求し、単調性はインデックスが決して減少しないことを保証する。
応用
DTWは多くの領域で応用を見出している。音声認識では、特に小語彙タスクのために、話された単語をテンプレートと比較するために使用された。時系列解析（関連分野であるが、提供されたスラッグリストには含まれない）では、DTWはクラスタリングと分類のための標準的なツールであり、時間的ミスアライメントを持つデータセットではユークリッド距離をしばしば上回る。例えば、加速度計データからのジェスチャ認識では、DTWは異なる速度で実行されたジェスチャをマッチングできる。
バイオインフォマティクスでは、DTWは遺伝子発現プロファイルやタンパク質配列の整列に適用されてきたが、Needleman-Wunschのような配列アライメントアルゴリズムほど一般的ではない。金融では、DTWは株価の動きや経済指標を時間とともに比較するために使用される。ロボティクスでは、DTWは模倣学習のために異なる試行からのセンサー読み取りを整列させるのに役立つ。このアルゴリズムはまた、既存の時系列をワーピングして合成トレーニング例を生成するためのData Augmentationにも使用される。
変種と拡張
特定の制限に対処するために、DTWのいくつかの変種が開発されてきた。微分DTW（DDTW）は生の値の代わりにシーケンスの一次導関数を使用し、オフセットとスケーリングの違いに対してより堅牢にする。重み付きDTWは特徴ベクトルの異なる次元に異なる重みを割り当てる。2017年にMarco CuturiとMathieu Blondelによって導入されたSoft-DTWは、min操作をソフト最小値に置き換え、距離を微分可能にし、Deep learningパイプラインの損失関数として使用可能にする。
多変量DTWは複数のチャネルを持つシーケンスを処理し、部分シーケンスDTWはより長いシーケンス内で最良のマッチング部分シーケンスを見つける。大規模データセットについては、FastDTWなどの近似法がマルチスケールアプローチを使用して計算複雑性を削減する。これらの拡張により、DTWは現代の研究、特に微分可能なバージョンがエンドツーエンドのトレーニングを可能にするMachine learningの文脈で関連性を維持している。
現代のAIとの関係
DTWはDeep learning手法ではないが、Artificial intelligenceの時代においても関連性を保っている。これはしばしば、時系列をNeural networkモデル（Residual Network (ResNet)やU-Netなどのシーケンス予測アーキテクチャ）に供給する前に整列させる前処理ステップとして使用される。Speech recognition（スラッグリストにはない概念）では、DTWは低リソース設定でのキーワードスポッティングに今も使用されている。このアルゴリズムの動的計画法の原理は、アテンションメカニズムを通じてアライメントが暗黙的に学習されるSequence-to-Sequence (Seq2Seq)モデルにも現れる。
MIT CSAILやStanford AI Labなどの機関の研究者は、時系列分類や異常検出などのタスクのためにDTWとDeep learningを組み合わせたハイブリッドアプローチを探求してきた。Soft-DTWの微分可能性により、時間的アライメントを必要とするモデルのトレーニングのためのLoss Functionsへの統合が可能になった。2020年代初頭の時点で、DTWは時系列ベンチマークの標準的なベースラインであり続け、その計算効率は研究のトピックであり、GPUやAWS Trainiumハードウェア向けの最適化が探求されている。