algorithm
動的時間ワーピング

動的時間ワーピングの紹介

動的時間ワーピング （DTW）は、速度が異なる可能性のある2つの時間シーケンス間の類似性を測定するアルゴリズムです。例えば、一方の人が他方よりも速く歩いていたとしても、あるいは観測中に加速や減速があったとしても、DTWを使って歩行の類似点を検出することができました。たとえ人が事前録音されたサンプル音声よりも速くても遅くても、サンプル音声コマンドを他のコマンドと照合するのに使用できます。 DTWは、ビデオ、オーディオ、およびグラフィックスデータの時間的シーケンスに適用できます。実際、線形シーケンスに変換できるデータはDTWで解析できます。

一般に、DTWは、特定の制約を受けて2つの所与の配列間の最適な一致を計算する方法である。しかしここでは簡単な点に固執しましょう。 サンプルとテストの 2つの音声シーケンスがあり、これら2つのシーケンスが一致するかどうかを確認したいとします。ここで、音声シーケンスとは、あなたの声の変換されたデジタル信号を指します。あなたの言葉を表すあなたの声の振幅または頻度かもしれません。仮定しましょう：

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

我々は、これらの2つの配列間の最適な一致を見出したい。

まず、2点間の距離d（x、y）を定義します。ここで、 xとyは2点を表します。また、

d(x, y) = |x - y|     //absolute difference

これらの2つのシーケンスを使って2D行列テーブルを作成しましょう。 サンプルの各点とテストの各点との間の距離を計算し、それらの間の最適な一致を見つける。

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   1  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

ここで、 Table [i] [j]は、以前に観測されたすべての最適距離を考慮して、シーケンスをSample [i]およびTest [j]まで考慮すると、2つのシーケンス間の最適距離を表します。

最初の行については、 Sampleから値を取らない場合、これとTestの距離は無限になります 。だから、最初の行に無限を置く。最初の列も同じです。 Testから値を取らない場合、この値とSampleの間の距離も無限になります。そして、 0と0の間の距離は単に0になります 。我々が得る、

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

今度は、各ステップごとに、懸念される各ポイント間の距離を検討し、それまでに見つかった最小距離を追加します。これにより、その位置までの2つの配列の最適な距離が得られます。私たちの公式は、

Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])

最初のものについては、 d（1,1） = 0 、 Table [0] [0]は最小値を表す。したがって、 Table [1] [1]の値は0 + 0 = 0になります。第2のものについては、 d（1,2） = 0である 。 表[1] [1]は最小値を表します。値は次のとおりです。Table [1] [2] = 0 + 0 = 0 。この方法を続けると、終了後、表は次のようになります。

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |   0  |   0  |   1  |   2  |   4  |   8  |
+------+------+------+------+------+------+------+------+
|   2  |  inf |   1  |   1  |   0  |   0  |   1  |   4  |
+------+------+------+------+------+------+------+------+
|   3  |  inf |   3  |   3  |   1  |   1  |   0  |   2  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |   7  |   7  |   4  |   4  |   2  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  11  |  11  |   7  |   7  |   4  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  15  |  15  |  10  |  10  |   6  |   0  |
+------+------+------+------+------+------+------+------+
|   6  |  inf |  20  |  20  |  14  |  14  |   9  |   1  |
+------+------+------+------+------+------+------+------+

表[7] [6]の値は、これら2つの与えられた配列間の最大距離を表す。ここで、 1はSampleとTestの最大距離を表し、 1は1です。

最後の点から出発点（0、0）に戻ると、水平、垂直、斜めに移動する長い線が得られます。私たちのバックトラッキング手順は以下の通りです：

if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
    i := i - 1
    j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
    i := i - 1
else
    j := j - 1
end if

到達するまでこれを続けます（0、0） 。それぞれの動きには独自の意味があります。

• 水平移動は削除を表します。つまり、私たちのテストシーケンスは、この間隔の間に加速されました。
• 垂直移動は挿入を表します。これは、 テストシーケンスがこの間隔で減速したことを意味します。
• 対角線移動は一致を表します。この期間中、 テストとサンプルは同じでした。

私たちの疑似コードは次のようになります：

Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
    Table[i][0] := infinity
end for
for i from 1 to m
    Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
    for j from 1 to m
        Table[i][j] := d(Sample[i], Test[j])
                       + minimum(Table[i-1][j-1],      //match
                                 Table[i][j-1],        //insertion
                                 Table[i-1][j])        //deletion
    end for
end for
Return Table[n + 1][m + 1]

ローカリティ制約を追加することもできます。つまり、 Sample[i]がTest[j]と一致する場合、 |i - j|ウィンドウパラメータwより大きい。

複雑：

DTWを計算する複雑さはO（m * n）です。ここで、 mとnは各シーケンスの長さを表します。 DTWを計算するためのより高速なテクニックには、PrunedDTW、SparseDTW、およびFastDTWがあります。

アプリケーション：

• 音声認識
• 相関電力解析