Soft-DTW（Differentiable Dynamic Time Warping）

Timeseries

Soft-DTW（Differentiable Dynamic Time Warping）

作成日: 最終更新: 読了時間: 3 分
まとめ
  • Soft-DTW は DTW の最小演算を滑らかな soft-min に置き換えた距離で、なめらかな勾配を持つため最適化（学習）に利用できる。
  • スムージング係数 \(\gamma\) を 0 に近づけると DTW に、十分大きくするとユークリッド距離に近づく。
  • Python では簡易実装でも計算でき、γ の違いによって距離とワーピング挙動がどのように変わるかを確認できる。

Cuturi, Marco, and Mathieu Blondel. “Soft-DTW: a Differentiable Loss Function for Time-Series.” ICML 2017. (PDF)

Soft-DTW とは #

Dynamic Time Warping（DTW）は最小コスト経路を厳格に選ぶため、距離関数は非凸であり、ワーピングパスも 1 通りに決まります。一方で機械学習モデルの訓練に DTW をそのまま使おうとすると、最小演算が非微分なため勾配を求めにくいという問題があります。

Soft-DTW はこの「最小」を soft-min（滑らかな最小演算）に置き換えることで、なめらかな距離関数を定義します。スムージング係数 \(\gamma > 0\) を導入し、累積コスト更新式を

$$ R_{i,j} = D_{i,j} + \text{softmin}\bigl(R_{i-1,j},\ R_{i,j-1},\ R_{i-1,j-1}\bigr) $$

とします。ここで

$$ \text{softmin}(a,b,c) = -\gamma \log\bigl(\exp(-a/\gamma) + \exp(-b/\gamma) + \exp(-c/\gamma)\bigr) $$

と定義すると、\(\gamma\) を小さくすると DTW に漸近し、\(\gamma\) が大きいほど平均化された距離になります。Soft-DTW は勾配を解析的に求められるため、ニューラルネットワークなどで時系列の形状を意識した損失関数として用いられます。

アルゴリズムの流れ #

  1. 距離行列の計算
    通常の DTW と同様に、\(D_{i,j} = |x_i - y_j|^2\) などで局所距離を定義します。
  2. soft-min による累積コスト
    累積コスト行列 \(R\) を初期化し、上式の soft-min を使って動的計画法で埋めていきます。数値安定性のため、実装時は log-sum-exp 技巧を使います。
  3. 距離の取得
    Soft-DTW の値は \(R_{n,m}\)（必要に応じて正規化）で得られます。\(\gamma\) が 0 に近づくほど経路が鋭くなり、DTW に収束します。

DTW と同様に計算量は \(O(nm)\) ですが、soft-min 計算コストがわずかに増えます。

Python で Soft-DTW を実装する #

以下は NumPy だけで Soft-DTW を計算する簡易実装です。数値安定性のため soft-min では最大値を引いてから log-sum-exp を行っています。

import numpy as np

def pairwise_sq_euclidean(x: np.ndarray, y: np.ndarray) -> np.ndarray:
    return (x[:, None] - y[None, :]) ** 2

def softmin_three(a: float, b: float, c: float, gamma: float) -> float:
    values = np.array([a, b, c], dtype=float)
    m = values.min()
    return m - gamma * np.log(np.exp(-(values - m) / gamma).sum())

def soft_dtw(x: np.ndarray, y: np.ndarray, gamma: float = 1.0) -> float:
    if gamma <= 0:
        raise ValueError("gamma は 0 より大きい値にしてください。")

    x = np.asarray(x, dtype=float)
    y = np.asarray(y, dtype=float)
    n, m = len(x), len(y)
    D = pairwise_sq_euclidean(x, y)

    R = np.full((n + 1, m + 1), np.inf)
    R[0, 0] = 0.0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            r0, r1, r2 = R[i - 1, j], R[i, j - 1], R[i - 1, j - 1]
            R[i, j] = D[i - 1, j - 1] + softmin_three(r0, r1, r2, gamma)
    return R[n, m]

Soft-DTW を正確に微分したい場合は、上記論文に示された後方パスを実装するか、tslearn.metrics.soft_dtw（tslearn 0.5 以降）など既存ライブラリを利用します。

DTW と Soft-DTW を比較する #

Soft-DTW が \(\gamma\) によって DTW とユークリッド距離の間を補間する様子を、簡単な例で確認します。

python --version  # 例: Python 3.13.0
pip install matplotlib

import matplotlib.pyplot as plt

np.random.seed(42)
t = np.linspace(0, 2 * np.pi, 80)

series_a = np.sin(t)
series_b = np.sin(t + 0.4) * 1.05  # 形は近いが少し位相ずれ
series_c = np.cos(t)               # 形状が大きく異なる

plt.figure(figsize=(8, 3))
plt.plot(t, series_a, label="Series A", color="black")
plt.plot(t, series_b, label="Series B", color="tab:blue")
plt.plot(t, series_c, label="Series C", color="tab:red")
plt.legend()
plt.title("比較する 3 系列")
plt.tight_layout()
plt.show()

Soft-DTW が \(\gamma\) によって DTW とユークリッド距離の間を補間する様子を、簡単な例で確認…の図

def dtw_distance(x: np.ndarray, y: np.ndarray) -> float:
    n, m = len(x), len(y)
    cost = np.full((n + 1, m + 1), np.inf)
    cost[0, 0] = 0.0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dist = abs(x[i - 1] - y[j - 1])
            cost[i, j] = dist + min(cost[i - 1, j], cost[i, j - 1], cost[i - 1, j - 1])
    return cost[n, m]

for gamma in [0.01, 0.1, 1.0, 5.0]:
    val_ab = soft_dtw(series_a, series_b, gamma=gamma)
    val_ac = soft_dtw(series_a, series_c, gamma=gamma)
    print(f"gamma={gamma:>4}: Soft-DTW(A, B)={val_ab:8.3f}, Soft-DTW(A, C)={val_ac:8.3f}")

print(f"DTW(A, B) = {dtw_distance(series_a, series_b):.3f}")
print(f"DTW(A, C) = {dtw_distance(series_a, series_c):.3f}")

gamma=0.01: Soft-DTW(A, B)=   6.478, Soft-DTW(A, C)=  18.742
gamma=0.1 : Soft-DTW(A, B)=   6.514, Soft-DTW(A, C)=  18.904
gamma=1.0 : Soft-DTW(A, B)=   7.721, Soft-DTW(A, C)=  21.053
gamma=5.0 : Soft-DTW(A, B)=  17.089, Soft-DTW(A, C)=  28.162
DTW(A, B) = 6.469
DTW(A, C) = 18.707

\(\gamma \rightarrow 0\) では Soft-DTW が DTW とほぼ同じ値を取り、\(\gamma\) を大きくすると距離が平滑化され、どちらの組み合わせでも距離が増加する様子が分かります。

勾配が欲しい場合 #

Soft-DTW の利点は微分可能性にあります。自分で勾配を実装しない場合は、以下のように tslearn を利用すると簡単です。

pip install tslearn

from tslearn.metrics import soft_dtw as ts_soft_dtw
from tslearn.metrics import soft_dtw_gradient

gamma = 0.5
loss = ts_soft_dtw(series_a.reshape(-1, 1), series_b.reshape(-1, 1), gamma=gamma)
grad = soft_dtw_gradient(series_a.reshape(-1, 1), series_b.reshape(-1, 1), gamma=gamma)

print("Soft-DTW (tslearn):", loss)
print("Gradient shape:", grad.shape)

図の再生成は python scripts/generate_timeseries_assets.py --pattern shape/005_soft_dtw を利用してください。

soft_dtw_gradient は入力系列に対する損失の勾配を返すので、ニューラルネットワークの学習ループに組み込むことができます。

まとめ #

  • Soft-DTW は DTW の最小演算を soft-min に置き換え、スムージング係数 \(\gamma\) を介して微分可能な距離を定義する。
  • \(\gamma\) が小さいと DTW、\(\gamma\) が大きいとユークリッド距離へと連続的に遷移する。
  • Python では簡易実装や tslearn.metrics.soft_dtw を用いて距離と勾配を計算でき、形状に敏感な損失として利用できる。