Dynamic Time Warping

• 別名: DTW
• カテゴリ: Learning & autonomy › Learning from demonstration
• タグ: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

速さや長さの異なる 2 つの時系列を、順序を保ったサンプルどうしの対応づけのうち総距離が最小のものを見つけることで整列する動的計画法のアルゴリズム。

定義

動的時間伸縮法（dynamic time warping、DTW）は、同じようなパターンをたどるが速さの異なる 2 つの系列を比較する。たとえば、同じ動作の 2 回の実演で、一方のオペレータは途中で止まり、もう一方は素早く動いたような場合である。DTW は i 番目のサンプルどうしを比べるのではなく、ワーピングパスを探索する。これは 2 つの系列のサンプルの対応づけで、両方の先頭から始まり、両方の末尾で終わり、時間をさかのぼることはない。各サンプルは相手の系列の 1 つまたは複数のサンプルと対応づけられるので、時間の伸び縮みは整列によって吸収される。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)) であり、最後のセルからバックトラックすることでパスを復元する。これには 2 つの長さの積に比例する時間とメモリがかかる。Sakoe と Chiba（1978）は音声による単語認識でこの手法を広め、整列がどこまでずれてよいかを制限する対角線まわりの帯を導入した。Itakura の平行四辺形は関連する制約である。こうした窓は計算を速め、1 つのサンプルが相手の長い区間に対応づけられるような病的なワーピングを防ぐ。

ロボティクスではいくつかの変種が重要である。部分系列 DTW（subsequence DTW）は開始と終了の条件を緩め、短いクエリを長い軌道の中で最もよく合う区間に対応づけられるようにするもので、大規模なログからの検索を支える。微分 DTW（derivative DTW）は生の値ではなく局所的な傾きで整列する。Soft-DTW は Cuturi と Blondel が 2017 年に導入したもので、最小値を滑らかな版に置き換えることで整列コストを微分可能にし、訓練の損失として使えるようにする。DTW が整列するのは時間だけである。特徴量は比較可能でなければならず、通常は正規化が必要であり、得られる距離は三角不等式を満たさないため真の距離関数ではない。

重要な理由

ロボットのデータが共通の速さで得られることはまれである。実演、実行した軌道、センサーの記録はタイミングが異なり、DTW はそれらを平均、比較、検索、採点する前に共通の時間軸にそろえる標準的な道具である。

主な用途

• 動作プリミティブの平均化やフィッティングの前の複数の実演の整列
• 実行したロボット軌道と参照軌道の比較
• 大規模な軌道ログやセンサーログからの一致する区間の検索
• 動作データや慣性データからのジェスチャー認識と行動認識
• 正規化 DTW 指標によるナビゲーション経路と参照経路の比較採点
• 異なるレートで記録したセンサーストリームの同期

実際の使われ方

あるチームは、注ぐ動作のキネステティックな実演を 10 回集める。どれも長さが異なり、止まる箇所も異なる。動作プリミティブのための単一の参照を作るため、1 回の実演をテンプレートに選び、正規化した関節位置とエンドエフェクター速度に対する DTW でほかの各実演をそれに整列し、ワーピングパスを使って全実演をテンプレートの時間軸に再サンプリングする。整列した軌道を平均すると、きれいな平均動作と、実演どうしが一致する箇所を示すタイムステップごとの分散が得られる。Sakoe-Chiba バンドによって、整列が停止区間を単一のサンプルに潰してしまうのを防ぐ。その後、同じ部分系列 DTW のコードが、フリートに保存された軌道の中から短いクエリ動作に最もよく一致する区間を探す。

よくある誤解

• DTW 距離は距離関数である — 三角不等式を満たさず、それを前提とするインデックスやクラスタリングの手法では問題になる
• DTW は系列間のどんな違いにも対応できる — 吸収するのはタイミングの違いであって、値のオフセットやスケーリングではないので、通常は先に特徴量を正規化する必要がある
• 制約なしの DTW が最良の整列を与える — 窓がないと、1 つのサンプルを相手の系列の長い区間に対応づけてしまい、物理的に意味のないワーピングを生むことがある
• 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