Dynamic Time Warping
- 又稱: DTW
- 類別: Learning & autonomy › Learning from demonstration
- 標籤: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis
一種動態規劃演算法，藉由找出兩個時間序列樣本之間總距離最小且保持順序的配對，來對齊速度或長度不同的時間序列。
定義
動態時間校正（dynamic time warping，DTW）用來比較兩個遵循相似模式但速度不同的序列，例如同一動作的兩次示範，其中一位操作者停頓了，另一位則動作很快。DTW 不是拿第 i 個樣本與第 i 個樣本比較，而是搜尋一條校正路徑：把兩個序列的樣本配對，從兩者的開頭開始、在兩者的結尾結束，而且在時間上從不倒退。每個樣本都可以與另一個序列中的一個或多個樣本配對，因此時間上的拉伸與壓縮都由對齊吸收。DTW 距離是沿最佳路徑的總成本，而路徑本身則說明哪些時刻彼此對應。
標準演算法以動態規劃填入一個成本矩陣。設一個序列的第 i 個樣本與另一個序列的第 j 個樣本之間的局部距離為 d(i, j)，累積成本為 D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1))，從最後一個格子回溯即可還原路徑。所需的時間與記憶體和兩個長度的乘積成正比。Sakoe 與 Chiba（1978）讓這個方法在口語詞彙辨識中普及，並引入一條沿對角線的帶狀區域，限制對齊能偏離多遠；Itakura 平行四邊形是一種相關的約束。這類視窗能加快計算，並防止病態的校正，也就是一個樣本被配對到另一個序列的一長段。
有幾種變體在機器人領域很重要。子序列 DTW（subsequence DTW）放寬起點與終點條件，讓短查詢能與長軌跡中最吻合的片段配對，有助於從大型日誌中檢索。導數 DTW（derivative DTW）依據局部斜率而非原始值進行對齊。Soft-DTW 由 Cuturi 與 Blondel 於 2017 年提出，以平滑版本取代最小值運算，讓對齊成本可微分，因而可用作訓練損失。DTW 只在時間上對齊：特徵必須可以比較，且通常需要正規化；所得的距離也不是真正的度量，因為它不滿足三角不等式。
為何重要
機器人資料很少以一致的速度產生。示範、已執行的軌跡與感測器記錄在時間上各不相同，而 DTW 是在平均、比較、檢索或評分之前，把它們放到同一條時間軸上的標準工具。
主要應用
- 在平均或擬合運動基元之前對齊多次示範
- 將已執行的機器人軌跡與參考軌跡比較
- 從大型軌跡或感測器日誌中檢索相符的片段
- 根據運動或慣性資料進行手勢與活動辨識
- 以正規化 DTW 指標將導航路徑與參考路徑比較評分
- 同步以不同速率記錄的感測器資料串流
實際應用
一個團隊收集了十次倒水動作的動覺教導示範，每次的時長不同，停頓的位置也不同。為了替運動基元建立單一參考，他們選一次示範作為範本，在正規化的關節位置與末端執行器速度上以 DTW 將其餘每次示範與它對齊，並利用校正路徑把所有示範重新取樣到範本的時間軸上。將對齊後的軌跡取平均，可得到一條乾淨的平均運動以及逐時間步的變異數，顯示各次示範在哪裡一致。Sakoe-Chiba 帶能防止對齊把停頓壓縮成單一樣本。之後，同一套子序列 DTW 程式碼會在整個機隊儲存的軌跡中，搜尋與一段短查詢動作最吻合的片段。
常見誤解
- DTW 距離是一種度量 — 它不滿足三角不等式，這對假設滿足三角不等式的索引與分群方法很重要
- DTW 能處理序列之間的任何差異 — 它吸收的是時間上的差異，而不是數值的偏移或縮放，因此特徵通常需要先正規化
- 無約束的 DTW 能給出最好的對齊 — 沒有視窗時，它可能把單一樣本配對到另一個序列的一長段，產生沒有物理意義的校正
- DTW 太慢，不實用 — 帶狀約束、下界與近似方法讓它快到足以用於許多即時與大規模的應用
誰需要了解
- 研究從示範中學習的研究人員
- 分析機器人軌跡與日誌的工程師
- 手勢與活動辨識開發者
- 評估導航與操作策略的研究人員
相關技術
- Soft-DTW
- Sakoe-Chiba 帶
- 子序列 DTW（subsequence DTW）
- FastDTW
- tslearn
相關術語
- Dynamic Movement Primitive
- Imitation Learning
- Kinesthetic Teaching
- Behavior Cloning
- Success Weighted by Path Length
相關專案
- PlotJuggler: Fast time-series visualization tool for ROS topics, rosbags, and robot debugging
影片
- How DTW (Dynamic Time Warping) algorithm works: Thales Sehn Körting