# 動的時間伸縮法 ## 定義 動的時間伸縮法(Dynamic Time Warping, DTW)は、2 つの時系列の要素同士を、時間軸の順序を保ったまま伸縮させて対応づけ(アラインメント)、対応づけのコストの総和が最小となるものを不一致度とする手法である。長さの異なる系列を比較でき、時間軸上のシフトや伸縮に頑健である。計算は 2 系列の長さを $n$, $m$ として $O(nm)$ のベルマン再帰で行う。([[@2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series]]) 平滑化版の soft-DTW は、再帰中の最小値を $-\gamma\log\sum e^{-a_i/\gamma}$ に置き換え、全アラインメントのコストの soft-minimum を取る。値と勾配を $O(nm)$ で計算できる微分可能な損失となり、バリセンタ計算・クラスタリング・時系列を出力するモデルの学習に使える。([[@2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series]]) ## 未解決の問い - 平滑化が元の DTW 損失を下げる効果は、どの程度が最適化地形の改善で、どの程度が $\gamma$ と初期化の相互作用か。soft-DTW 論文は実験の傾向を挙げるのみで、因果を分離していない。 - 監視メトリクスのような運用系列(欠損・不規則標本化・多変量)で、soft-DTW 損失は UCR 単変量系列と同様の利得を示すか。 ## 未編纂の観察 - [クラスタリングの距離尺度] DTW の重心(平均系列)は、微分できない最小値と局所解のため求めにくい。soft-DTW は平滑化と勾配で DBA・劣勾配法より低い DTW 損失を得る。一方 k-Shape は SBD 専用にレイリー商の最大化でセントロイドを閉形式で求める。距離を変えるか、重心の最適化を変えるかという別の解き方である。(Source: [[@2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series]], [[@2016__SIGMOD Record__k-Shape - Efficient and Accurate Clustering of Time Series]]) ## 関連 - 概念: [[時系列クラスタリング]] / [[時系列類似度検索]] - ソース: [[@2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series]] / [[@2016__SIGMOD Record__k-Shape - Efficient and Accurate Clustering of Time Series]] - 人物: [[Marco Cuturi]] / [[Mathieu Blondel]] ## 出典 - [[@2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series]] - [[@2016__SIGMOD Record__k-Shape - Efficient and Accurate Clustering of Time Series]]