# Soft-DTW: a Differentiable Loss Function for Time-Series Navigation: [[動的時間伸縮法]] | [[時系列クラスタリング]] | [[Marco Cuturi]] | [[Mathieu Blondel]] | [[UCR Time Series Archive]] > [!abstract] 概要 > 本論文では、有名な動的時間伸縮法(DTW)の不一致度を土台とした、時系列間の微分可能な学習損失を提案する。ユークリッド距離と異なり、DTW は可変長の時系列を比較でき、時間軸方向のずれや伸縮に頑健である。DTW を計算するには、通常、動的計画法を用いて 2 つの時系列間の最小コストのアラインメント問題を解く。我々の研究は、soft-DTW と呼ぶ DTW の平滑化された定式化を利用する。soft-DTW はすべてのアラインメントコストの soft-minimum を計算する。本論文では、soft-DTW が微分可能な損失関数であり、その値と勾配の両方を二次の時間・空間計算量で計算できることを示す(DTW の時間計算量は二次だが、空間計算量は線形である)。この正則化が、DTW の幾何のもとで時系列を平均化・クラスタリングする作業に特によく適していることを示し、この作業において我々の提案は既存のベースライン(Petitjean et al., 2011)を大幅に上回る。次に、時系列を出力する機械のパラメータを、正解ラベルとの当てはまりを soft-DTW の意味で最小化することによって調整することを提案する。 ## 論文情報 - **タイトル**: Soft-DTW: a Differentiable Loss Function for Time-Series - **著者**: [[Marco Cuturi]](CREST, ENSAE, Université Paris-Saclay)、[[Mathieu Blondel]]([[NTT]] Communication Science Laboratories) - **媒体**: ICML 2017(Proceedings of the 34th International Conference on Machine Learning, PMLR 70) - **コード**: https://github.com/mblondel/soft-dtw - **データ**: [[UCR Time Series Archive]] の 79 データセット ## 概要 DTW は 2 系列間の最良アラインメントを動的計画法で求める不一致度で、シフトや伸縮への不変性を持つ。一方で最小値を取る演算のため微分不可能で、最適化パイプラインに組み込むと不安定になる。本論文は、DTW の (min, +) 再帰を平滑化した soft-DTW を損失として定義し、順伝播で使った log-sum-exp の結果を再利用する後退再帰により、勾配を二次計算量で求める方法を与える。この勾配を使って、DTW 幾何でのバリセンタ計算、k-means クラスタリング、最近傍セントロイド分類、多段先予測(multistep-ahead prediction)を行う。バリセンタと k-means では、γ が小さいときに DBA と劣勾配法より低い DTW 損失を多くのデータセットで達成した。 ## 問題設定 出力が時系列であるような教師あり学習を対象とする。時間を単なる特徴として連結すると、時間軸上の局所的な伸縮、標本化条件による長さの違い、同期ずれといった実務上の問題に対応できない。生成モデル(潜在変数やマルコフ性の仮定)ではなく、これらの不変性を組み込んだ不一致度を直接定義するのが幾何的な発想である。DTW はその代表だが、微分できないため、バリセンタ計算のような時系列を出力するタスクでは劣勾配法や DBA に頼ることになり、局所解に陥りやすい。 ## 提案手法 **アラインメントコスト**。長さ $n$ と $m$ の系列 $x, y$ に対し、コスト行列 $\Delta(x,y)=[\delta(x_i,y_j)]_{ij}$ とアラインメント行列 $A \in \mathcal{A}_{n,m}$(左上 $(1,1)$ から右下 $(n,m)$ まで $\downarrow, \rightarrow, \searrow$ だけで進む二値行列)の内積 $\langle A,\Delta\rangle$ がそのアラインメントのスコアになる。$|\mathcal{A}_{n,m}|$ はデラノイ数で、$n,m$ に対し指数的に増える。DTW は $\min_A \langle A,\Delta\rangle$、グローバルアラインメントカーネル $k_{GA}^\gamma$ は $\sum_A e^{-\langle A,\Delta\rangle/\gamma}$ である。 **Figure 2: 3 つのアラインメント行列** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig02-alignment-matrices.png]] (図2。長さ 4 と 6 の系列間の 3 つのアラインメント行列。DTW は最適なもの(紫)だけを考慮し、soft-DTW はすべてを考慮する。) **統一アルゴリズム**。平滑化パラメータ $\gamma\ge 0$ を持つ一般化 min 演算子 $\min^\gamma\{a_1,\dots,a_n\}$ を、$\gamma=0$ で $\min_i a_i$、$\gamma>0$ で $-\gamma\log\sum_i e^{-a_i/\gamma}$ と定める。これにより $\mathrm{dtw}_\gamma(x,y):=\min^\gamma\{\langle A,\Delta\rangle, A\in\mathcal{A}_{n,m}\}$ と定義する。$\gamma=0$ で元の DTW、$\gamma>0$ で $-\gamma\log k_{GA}^\gamma$ に一致する。どちらも Algorithm 1 の再帰 $r_{i,j}=\delta(x_i,y_j)+\min^\gamma\{r_{i-1,j-1},r_{i-1,j},r_{i,j-1}\}$ で $O(nm)$ の時間・空間で計算できる(値だけなら空間 $2n$ に削減できるが、後退再帰は行列 $R$ 全体を要する)。数値安定のため log-sum-exp のトリックを用いる。 **微分**。$\gamma=0$ では最適アラインメント $A^\star$ が一意なら勾配は $A^\star$ だが、$A^\star$ が切り替わる点で勾配が不連続になり、勾配降下の性能を損なう。$\gamma>0$ では $\nabla_x \mathrm{dtw}_\gamma(x,y)=\left(\frac{\partial\Delta(x,y)}{\partial x}\right)^T \mathbb{E}_\gamma[A]$ であり、$\mathbb{E}_\gamma[A]$ はギブス分布 $p_\gamma\propto e^{-\langle A,\Delta\rangle/\gamma}$ のもとでの平均アラインメント行列である。$k_{GA}^\gamma$ は $p_\gamma$ の正規化定数に当たる。$\mathbb{E}_\gamma[A]$ を直接ベルマン再帰で求めると $O(n^2m^2)$ の四次計算量になる。 **後退再帰**。順伝播を逆順に連鎖律で辿る(バックプロパゲーション)。$e_{i,j}:=\partial r_{n,m}/\partial r_{i,j}$ とすると、$r_{i,j}$ は $r_{i+1,j}, r_{i,j+1}, r_{i+1,j+1}$ にだけ影響するため、$e_{i,j}=e_{i+1,j}a+e_{i,j+1}b+e_{i+1,j+1}c$ となる。係数 $a,b,c$ は $\exp\frac{1}{\gamma}(r_{i+1,j}-r_{i,j}-\delta_{i+1,j})$ などで、前進で得た $r$ から作れる。$E=[e_{i,j}]$ を求めれば $\nabla_x\mathrm{dtw}_\gamma=(\partial\Delta/\partial x)^T E$ で、$E$ が $\mathbb{E}_\gamma[A]$ に等しい。これが Algorithm 2 で、$\Delta$ 計算後の計算量は時間・空間とも $nm$ である。$\min^\gamma$ の勾配が $1/\gamma$-リプシッツなので、$\delta$ が二乗ユークリッド距離のとき $\mathrm{dtw}_\gamma$ の勾配は $2/\gamma$-リプシッツになる。 **Figure 3: soft-DTW の計算グラフ(前進と後退)** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig03-computational-graph.png]] (図3。soft-DTW の計算グラフの概念図。左が $\mathrm{dtw}_\gamma$ を求める前進パス、右が勾配を求める後退パス。) **バリセンタ・クラスタリング・分類・予測への応用**。 - **平均化(バリセンタ)**: $\min_{x\in\mathbb{R}^{p\times n}}\sum_i \frac{\lambda_i}{m_i}\mathrm{dtw}_\gamma(x,y_i)$(式 4)。DTW の値は系列長にほぼ線形に増えるため $m_i$ で正規化する。ユークリッド幾何と異なり、長さの異なる系列にも使え、図 4 のように直観的な補間が得られる。目的関数は非凸(k-means と同様)で、最適性は保証できない。 - **平滑化の効果**: $\gamma\to\infty$ で $\mathrm{dtw}_\gamma$ は全コストの和に収束し、$\delta$ が凸なら次第に凸に近づく。$\gamma$ が小さいときも局所解を平滑化して、地形を改善すると著者らは考えている。 - **クラスタリング**: 式 5 の k-means エネルギーを、centering と割り当ての両方を $\mathrm{dtw}_\gamma$ で行う Lloyd 法で最小化する。 - **最近傍セントロイド分類**: 各クラスのバリセンタを学習し、最も近いバリセンタのクラスを返す。k-NN に比べ保存量と予測時計算量が小さい。 - **多段先予測**: 先頭 $t$ 点から残りを予測する $\min_\theta\sum_i\mathrm{dtw}_\gamma(f_\theta(x_i^{1,t}), x_i^{t+1,n})$。$f_\theta$ には MLP や RNN を想定する。 ## 新規性 - DTW と GAK を 1 つの再帰(min を $\min^\gamma$ に置き換える)で統一する定式化(著者らの知る限り新規) - 平均アラインメント行列 $\mathbb{E}_\gamma[A]$ を、前進で得た log-sum-exp を再利用する後退再帰により二次計算量で得る方法。編集距離では有限アルファベットゆえ二次の結果が既知だが、連続値の系列では四次の再帰しか知られていなかった。 - soft-DTW を、ニューラルネットワークの出力系列に対する微分可能損失として使うという位置づけ。Wasserstein 距離の平滑化バリセンタや識別器への応用(Cuturi & Doucet 2014、Zhang et al. 2015 など)との類比が述べられている。 ## 実験設定 - **データ**: UCR 分類アーカイブから 79 データセット(天文・地質・医用画像など、長さも多様、最大 60 クラス) - **平均化実験**: データセットごとにランダムに 1 クラスを選び 10 本の時系列でバリセンタを計算。10 回繰り返して平均。最大反復 100 回。soft-DTW は L-BFGS、比較対象は DBA と単純なバッチ劣勾配法。初期化はランダムとユークリッド平均(全系列が同じ長さのときだけ可能)の 2 通り。$\gamma\in\{1,0.1,0.01,0.001\}$ - **k-means**: クラスタ数はクラス数。外側最大 30 反復、内側(バリセンタ)最大 100 反復。soft-DTW は L-BFGS - **分類**: 訓練 50%、検証 25%、テスト 25%。$\gamma$ は $10^{-3}$ から $10$ までの対数等間隔 15 値から選択。最近傍セントロイド分類器で DBA と比較 - **多段先予測**: UCR 既定の訓練/テスト分割を使い、先頭 60% を入力、残り 40% を出力とする(クラスは無視)。1 隠れ層・シグモイド活性の MLP を Chainer の Adam で学習。損失はユークリッドと soft-DTW。ユークリッド初期化(ユークリッド損失で学習した解から開始)も比較。線形モデルや RNN は MLP を上回らなかったと述べる - **実装**: Chainer にカスタム後退パスを実装。自動微分では要素ごとの動的計画が非効率で、log-sum-exp の再利用もできないため ## 実験結果 **バリセンタ(表1、図5)**。ランダム初期化では、$\gamma=0.01$ で DBA に対し 100%、劣勾配法に対し 97.47% のデータセットで soft-DTW が低い DTW 損失を得た。ユークリッド初期化でも $\gamma$ を下げると同じ傾向で、$\gamma=0.001$ で DBA に 89.87%、劣勾配法に 97.47% である。一方、$\gamma=1$ のユークリッド初期化では DBA に対して 3.80% にとどまる。 **Table 1: バリセンタの DTW 損失で soft-DTW が勝つデータセット割合** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/table1-barycenter-dtw-loss.png]] ECG200 での質的比較では、DBA と低 $\gamma$(0.01)の soft-DTW は、データのどの系列にも現れない小さなキンクを持つ疑似的なバリセンタに落ち込むが、$\gamma=1$ では系列によく合う。 **Figure 5: ECG200 でのバリセンタ比較** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig05-barycenter-ecg200.png]] 図4は Gun Point データセットでの 2 系列間の補間で、ユークリッド損失と soft-DTW($\gamma=1$)で得られる補間が視覚的に異なることを示す。 **Figure 4: Gun Point での補間** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig04-interpolation.png]] ユークリッド平均で初期化すると、DTW や低 $\gamma$ の soft-DTW は形状に合うバリセンタを出すことが多いが、データの癖を吸収して過学習しやすい。soft-DTW($\gamma$ が大きい)はずっと滑らかなバリセンタを学習する。 **k-means(表2、図6)**。同様の傾向で、$\gamma$ が小さいほど soft-DTW が DBA・劣勾配法より低い DTW 損失を達成する割合が高い。ランダム初期化の $\gamma=0.001$ で DBA に対し 77.19%、劣勾配法に対し 96.49%。$\gamma=1$ では DBA に対して 15.78% にとどまる。CBF データセットでは、DBA のクラスタセントロイドがデータの細部を吸収するのに対し、soft-DTW($\gamma=1$)はより滑らかな形になる。 **Table 2: k-means の DTW 損失で soft-DTW が勝つデータセット割合** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/table2-kmeans-dtw-loss.png]] **Figure 6: CBF でのクラスタ** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig06-clusters-cbf.png]] **分類(図7)**。最近傍セントロイド分類器で soft-DTW バリセンタを DBA より優位とできたデータセットは図の対角線より上の点であり、soft-DTW が DBA と同等以上なのは 75% のデータセットである。 **Figure 7: 最近傍セントロイド分類の精度比較** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig07-centroid-accuracy.png]] **多段先予測(表3、図1)**。MLP の平均順位は、DTW 損失で評価するとランダム初期化では soft-DTW($\gamma=0.001$)が 1.87、ユークリッドが 3.46。ユークリッド初期化では soft-DTW($\gamma=0.001$)が 1.29、ユークリッドが 4.21 である。ユークリッド損失で評価すると、ユークリッドで学習した MLP が最良(1.05 / 1.70)。予測は多くの場合ユークリッド損失と soft-DTW 損失で一致するが、soft-DTW は急峻な変化をより確信をもって予測する。 **Table 3: MLP の平均順位** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/table3-mlp-rank.png]] **Figure 1: 先頭部分から残りを予測する MLP の出力例(ShapesAll)** ![[_attachments/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series/fig01-mlp-prediction.png]] ## 考察 - $\gamma$ が小さいほど $\mathrm{dtw}_0$(元の DTW)で測った損失も低くなるのは、平滑化が最適化地形を改善するためだと著者らは説明する。ただしこの因果を分離する実験は示されておらず、経験的な観察にとどまる。 - $\gamma$ には両面がある。大きいと滑らかで過学習しにくいバリセンタ、小さいと DTW に近いが局所解に陥りやすい(ECG200 の例)。ユークリッド初期化では、小さい $\gamma$ でデータの癖を吸収する傾向もある。 - soft-DTW 損失は、正解の時間ずれ(小さなシフト)に対して低コストなので、鋭い変化の位置に自信を持った予測を促す。DTW の頑健性を考えると、多くの応用でユークリッドの誤差より soft-DTW の意味での小さな誤差の方が妥当な選択になりうる。 - バリセンタ計算の結果は、非凸性のため最適性を保証できず、割り引いて読む必要があると著者ら自身が述べている。 ## 強み / 弱点・課題 **強み** - 値と勾配が $O(nm)$ の時間・空間で得られ、DTW の頑健性を保ったまま勾配ベースの最適化・学習に載せられる - バリセンタ・k-means で、DBA や劣勾配法より低い DTW 損失(元の $\gamma=0$ の尺度で測っても)を多数のデータセットで達成する - ニューラルネットの損失として組み込め、実装(Chainer のカスタム後退パス)も公開されている **弱点・課題** - 平均化・クラスタリング・予測の目的関数は非凸で、最適性の保証がない - $\gamma$ の選び方に強く依存する(表1、2 で $\gamma=1$ は DBA に負けるケースが多い)。検証で選ぶ手順は分類実験でのみ明示される - 計算量は DTW 同様に二次で、系列が長いと重い。後退パスは行列 $R$ 全体を保持する必要がある(空間 $O(nm)$) - 多段先予測は予備実験で、単純な 1 隠れ層 MLP と UCR の単変量系列のみ。線形モデルと RNN は MLP を上回らなかったと述べるのみで、数値は本文に無い - 評価は UCR アーカイブに限られ、運用データ(監視メトリクス等)での検証はない ## 関連 - 概念: [[動的時間伸縮法]] / [[時系列クラスタリング]] / [[時系列類似度検索]] - 人物・組織: [[Marco Cuturi]] / [[Mathieu Blondel]] / [[NTT]] - データセット: [[UCR Time Series Archive]] - 比較: [[@2016__SIGMOD Record__k-Shape - Efficient and Accurate Clustering of Time Series]](形状ベース距離 SBD とセントロイド計算) ## 出典 - [[.raw/papers/2017__ICML__Soft-DTW-a-Differentiable-Loss-Function-for-Time-Series.pdf]]