ダイナミックタイムワーピング

時系列分析において、動的時間ワーピング( DTW ) は、速度が異なる可能性がある 2 つの時間的シーケンス間の類似性を測定するアルゴリズムです。たとえば、一方の人がもう一方の人よりも速く歩いている場合でも、または観察の過程で加速と減速があった場合でも、DTW を使用して歩行の類似性を検出できます。DTW は、ビデオ、オーディオ、およびグラフィックス データの時間的シーケンスに適用されており、実際、1 次元シーケンスに変換できるデータはすべて DTW を使用して分析できます。よく知られているアプリケーションは、異なる発話速度に対処するための自動音声認識です。その他のアプリケーションには、話者認識やオンライン署名認識があります。部分的な形状マッチングアプリケーションでも使用できます。

一般的に、DTW は、特定の制限とルールに基づいて、 2 つの指定されたシーケンス (時系列など) 間の最適な一致を計算する方法です。

• 最初のシーケンスのすべてのインデックスは、他のシーケンスの1つ以上のインデックスと一致する必要があり、その逆も同様です。
• 最初のシーケンスの最初のインデックスは、他のシーケンスの最初のインデックスと一致している必要があります (ただし、一致している必要があるのはそれだけではありません)
• 最初のシーケンスの最後のインデックスは、他のシーケンスの最後のインデックスと一致している必要があります (ただし、一致している必要があるのはそれだけではありません)
• 最初のシーケンスのインデックスから他のシーケンスのインデックスへのマッピングは単調増加でなければならず、その逆も同様です。つまり、が最初のシーケンスのインデックスである場合、インデックスがインデックスと一致し、インデックスがインデックスと一致するような2つのインデックスが他のシーケンスに存在してはなりません。その逆も同様です。${\displaystyle j>i}$${\displaystyle l>k}$${\displaystyle i}$${\displaystyle l}$${\displaystyle j}$${\displaystyle k}$

シーケンスとの各一致を、各ステップが のいずれかとなるように、から への行列のパスとしてプロットできます。この定式化では、可能な一致の数はDelannoy 数であることがわかります。 ${\displaystyle 1:M}$${\displaystyle 1:N}$${\displaystyle M\times N}$${\displaystyle (1,1)}$${\displaystyle (M,N)}$${\displaystyle (0,1),(1,0),(1,1)}$

最適な一致は、すべての制約とルールを満たし、コストが最小となる一致によって示されます。コストは、一致したインデックスの各ペアの値間の絶対差の合計として計算されます。

シーケンスは時間次元で非線形に「ワープ」され、時間次元の特定の非線形変動とは無関係に類似性の尺度が決定されます。このシーケンス アライメントメソッドは、時系列分類でよく使用されます。DTW は、指定された 2 つのシーケンス間の距離のような量を測定しますが、三角不等式が成立することを保証するものではありません。

2 つのシーケンス間の類似性測定 (いわゆる「ワーピング パス」が生成される) に加えて、このパスに従ってワーピングすることにより、2 つの信号を時間的に揃えることができます。元のポイント セットX (オリジナル)、Y (オリジナル) を持つ信号は、 X (ワープ)、Y (ワープ)に変換されます。これは、遺伝子シーケンスとオーディオ同期に応用されています。関連技術では、この技術を使用してさまざまな速度のシーケンスを平均化できます (平均シーケンス セクションを参照)。

これは概念的にはNeedleman-Wunschアルゴリズムと非常に似ています。

この例では、2 つのシーケンスsとt が離散シンボルの文字列である場合の動的タイム ワーピング アルゴリズムの実装を示します。2 つのシンボルxとyの場合、d(x, y)はシンボル間の距離です (例: d(x, y)= ) 。 ${\displaystyle |xy|}$

int DTWDistance(s: 配列 [1..n], t: 配列 [1..m]) {
    DTW := 配列 [0..n, 0..m]
    
    i := 0 から n まで
        j := 0 から m まで
            DTW[i, j] := 無限大
    DTW[0, 0] := 0
    
    i := 1 から n まで
        j := 1 から m まで
            コスト := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j ], // 挿入
                                        DTW[i, j-1], // 削除
                                        DTW[i-1, j-1]) // 一致
    
    DTW[n, m]を返す
}

最適な位置合わせにおける と の 間DTW[i, j]の距離はどこでしょうか。s[1:i]t[1:j]

場合によっては、局所性制約を追加する必要があります。つまり、 がs[i]と一致する場合t[j]、 はウィンドウ パラメータ wより大きくないことを要求します。${\displaystyle |ij|}$

上記のアルゴリズムを簡単に修正して、局所性制約（差異）を追加することができます。マークされた)。ただし、上記の変更は、 がwより大きくない、つまり、終点が対角線からウィンドウの長さ内にある場合にのみ機能します。アルゴリズムを機能させるには、ウィンドウ パラメーターw を次のように調整する必要があります(コード内の (*) でマークされた行を参照)。 ${\displaystyle |nm|}$${\displaystyle |nm|\leq w}$

int DTWDistance(s: 配列 [1..n], t: 配列 [1..m], w: 整数）{
    DTW := 配列 [0..n, 0..m]

    w := max(w, abs(nm))// ウィンドウサイズを調整します (*)

    i := 0 から n まで
        j:= 0 から m まで
            DTW[i, j] := 無限大
    DTW[0, 0] := 0
    i := 1 から n まで
        j := max(1, iw) から min(m, i+w) まで
            DTW[i, j] := 0

    i := 1 から n まで
        j :=の場合max(1, iw) から min(m, i+w) まで
            コスト := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j ], // 挿入
                                        DTW[i, j-1], // 削除
                                        DTW[i-1, j-1]) // 一致
    DTW[n, m]を返す
}

DTW アルゴリズムは、あるシリーズの既存の要素と別のシリーズの既存の要素を離散的に一致させます。つまり、シーケンス内のセグメントの時間スケーリングは許可されません。他の方法では、連続的なワーピングが可能です。たとえば、相関最適化ワーピング (COW) は、シーケンスを均一なセグメントに分割し、線形補間を使用して時間的にスケーリングして、最も一致するワーピングを生成します。セグメント スケーリングでは、セグメントを上下に時間スケーリングすることで新しい要素が作成される可能性があり、DTW の生の要素の離散的な一致よりも感度の高いワーピングが生成されます。

DTW アルゴリズムの時間計算量はで、 と は2 つの入力シーケンスの長さです。50 年続いた二次の時間制限は 2016 年に破られました。Gold と Sharir によるアルゴリズムにより、長さ の 2 つの入力シーケンスに対して時間と空間で DTW を計算できるようになりました。^{[2]このアルゴリズムは、異なる長さのシーケンスにも適応できます。この改善にもかかわらず、}強い指数時間仮説が失敗しない限り、 の形式の強く二次以下の実行時間は存在できないこと が示されました。^{[3] [4]}${\displaystyle O(NM)}$${\displaystyle N}$${\displaystyle M}$${\displaystyle O({N^{2}}/\log \log N)}$${\displaystyle N}$${\displaystyle O(N^{2-\epsilon })}$${\displaystyle \epsilon >0}$

DTW の動的計画法アルゴリズムは単純な実装ではスペースを必要としますが、Hirschberg のアルゴリズムを使用するとスペースの消費を減らすことができます。 ${\displaystyle O(NM)}$${\displaystyle O(\min(N,M))}$

DTWを計算するための高速技術としては、PrunedDTW、^[5]、 SparseDTW、^[6]、 FastDTW、^[7]、MultiscaleDTW ^{[8] [9]などがある。}

一般的なタスクである類似時系列の検索は、LB_Keogh ^[10] 、 LB_Improved ^[11]、LB_Petitjean ^[12]などの下限値を使用することで高速化できます。ただし、Early AbandonおよびPruned DTWアルゴリズムでは、下限値が提供する高速化の度合いが低下し、場合によっては効果がなくなることがあります。

調査では、WangらはLB_Improved下限値がLB_Keogh下限値よりもわずかに良い結果を報告し、他の手法は非効率的であることを発見しました。^[13]この調査に続いて、LB_Keoghよりも常に厳密でありながら計算効率も高いLB_Enhanced下限値が開発されました。^[14] LB_Petitjeanは線形時間で計算できる最も厳密な下限値として知られています。^[12]

動的時間ワーピングの平均化は、配列セットの平均配列を見つける問題です。NLAAF ^{[15]は、 DTWを使用して2つの配列を平均化する正確な方法です。2つ以上の配列の場合、問題は}多重アライメントの問題に関連し、ヒューリスティックが必要です。DBA ^[16]は現在、DTWと一貫して配列セットを平均化する参照方法です。COMASA ^[17]は、DBAをローカル最適化プロセスとして使用して、平均配列の検索を効率的にランダム化します。

最近傍分類器は、距離測定として動的時間ワーピングを使用すると最先端の性能を達成することができる。^[18]

従来のダイナミックタイムワーピング（ADTW）は、DTW のバリエーションで、DTW が許容するアラインメントの許容度をより適切に制御するために設計されています。^[19]従来の DTW がアラインメントを制限するために使用するウィンドウは、ステップ関数を導入します。パスのワーピングはウィンドウ内では許可されますが、ウィンドウを超えることはできません。対照的に、ADTW は、パスがワーピングされるたびに発生する追加ペナルティを使用します。任意の量のワーピングが許可されますが、各ワーピングアクションは直接的なペナルティを引き起こします。ADTW は、ベンチマークの時系列分類タスクのセットに最近傍分類器として適用された場合、ウィンドウ処理を使用した DTW を大幅に上回ります。^[19]

関数データ解析では、時系列は時間の滑らかな（微分可能な）関数の離散化とみなされます。観測されたサンプルを滑らかな関数で見ることで、連続数学を利用してデータを解析することができます。^[20]時間ワープ関数の滑らかさと単調性は、たとえば時間変動ラジアル基底関数を積分することで得られ、1次元微分同相写像になります。^[21]最適な非線形時間ワープ関数は、関数セットからワープ平均までの距離の尺度を最小化することで計算されます。ワープ関数の粗さペナルティ項は、たとえば曲率の大きさを制限することで追加できます。結果として得られるワープ関数は滑らかで、その後の処理が容易になります。このアプローチは、音声の動きのパターンと変動性の解析にうまく適用されています。^{[22] [23]}

もう一つの関連するアプローチは隠れマルコフモデル（HMM）であり、HMMを介して最も可能性の高いパスを検索するために使用されるビタビアルゴリズムは確率的DTWと同等であることが示されている。^{[24] [25] [26]}

DTWおよび関連するワーピング法は、通常、データ分析の前処理または後処理ステップとして使用されます。観測されたシーケンスに、値のランダムな変動、観測されたシーケンスの形状、およびランダムな時間的ずれの両方が含まれている場合、ワーピングはノイズに過剰適合し、偏った結果につながる可能性があります。値（垂直）と時間パラメータ化（水平）の両方にランダムな変動がある同時モデル定式化は、非線形混合効果モデルの例です。^[27]人間の動作分析では、同時非線形混合効果モデリングは、DTWと比較して優れた結果を生み出すことが示されています。^[28]

• Python バインディングを備えた tempo C++ ライブラリは、Early Abandoned および Pruned DTW だけでなく、Early Abandoned および Pruned ADTW と DTW 下限 LB_Keogh、LB_Enhanced、および LB_Webb も実装します。
• UltraFastMPSearch Javaライブラリは、高速ワーピングウィンドウチューニングのためのUltraFastWWSearchアルゴリズム^[29]を実装しています。
• lbimproved C++ ライブラリは、GNU General Public License (GPL) に基づいて高速最近傍検索アルゴリズムを実装します。また、動的な時間ワーピングの C++ 実装と、さまざまな下限も提供します。
• FastDTW ライブラリは、DTW の Java 実装であり、標準の DTW アルゴリズムのO ( N ² ) 要件とは対照的に、O ( N ) の時間とメモリの複雑さで最適またはほぼ最適なアライメントを提供するFastDTW 実装です。FastDTW は、より粗い解像度からソリューションを再帰的に投影し、投影されたソリューションを改良するマルチレベル アプローチを使用します。
• FastDTW フォーク (Java) が Maven Central に公開されました。
• time-series-classification (Java) Weka で DTW を使用して時系列分類を行うパッケージ。
• DTW スイートは、さまざまな再帰ルール (ステップ パターンとも呼ばれます)、制約、および部分文字列の一致を含む、DTW アルゴリズム ファミリ メンバーを包括的にカバーする Python (dtw-python) および R パッケージ (dtw) を提供します。
• mlpy Python ライブラリはDTW を実装します。
• pydtw Python ライブラリは、LB_Keogh 下限を含むマンハッタンおよびユークリッド風味の DTW 測定を実装します。
• cudadtw C++/CUDA ライブラリは、CUDA 対応アクセラレータで一般的な UCR-Suite に類似した、ユークリッド風味の DTW とz正規化ユークリッド距離のサブシーケンス アライメントを実装します。
• JavaML 機械学習ライブラリは DTW を実装します。
• ndtw C# ライブラリは、さまざまなオプションを使用して DTW を実装します。
• Sketch-a-Char は、LaTeX シンボル分類プログラムの一部として Greedy DTW (JavaScript で実装) を使用します。
• MatchBox は、オーディオ信号のメル周波数ケプストラム係数を一致させるために DTW を実装します。
• シーケンス平均化：DBAのGPL Java実装。^[16]
• ジェスチャー認識ツールキット|GRT C++ リアルタイム ジェスチャー認識ツールキットは DTW を実装します。
• PyHubs ソフトウェア パッケージは、DTW 分類器と最近傍分類器、およびそれらの拡張機能 (ハブネス認識分類器) を実装します。
• simpledtw Python ライブラリは、古典的なO ( NM ) 動的プログラミング アルゴリズムを実装し、Numpy に基づいています。任意の次元の値をサポートし、距離にカスタム ノルム関数を使用します。MIT ライセンスの下でライセンスされます。
• tslearn Python ライブラリは、時系列コンテキストで DTW を実装します。
• cuTWED CUDA Python ライブラリは、驚異的なスピードアップを実現する線形メモリのみを使用して、最先端の改良されたTime Warp Edit Distanceを実装します。
• DynamicAxisWarping.jl は、DTW および FastDTW、SoftDTW、GeneralDTW、DTW 重心などの関連アルゴリズムの Julia 実装です。
• Multi_DTW は、2 つの 1 次元配列または 2 次元音声ファイル (2 次元配列) を一致させる DTW を実装します。
• dtwParallel（Python）パッケージには、現在のDTWライブラリで利用可能な主要な機能と、並列化、類似度（カーネルベース）値の計算、異なるタイプの特徴（カテゴリ、実数値など）を持つデータの考慮などの新しい機能が組み込まれています。^[30]

発話速度が異なると、発話パターンと時間軸の間に非線形の変動が生じるため、これを除去することが必要である。^{[31] DPマッチングは、時間正規化効果を利用する}動的計画法（DP）に基づくパターンマッチングアルゴリズムであり、時間軸の変動は非線形の時間ワーピング関数を使用してモデル化される。任意の2つの発話パターンを考えると、一方の時間軸を他方の時間軸と最大限一致するようにワープすることで、タイミングの違いを取り除くことができる。さらに、ワーピング関数が任意の値をとれるようにすると、^{異なるカテゴリに属する​​単語間の区別が}非常に難しくなる。そのため、異なるカテゴリに属する​​単語間の区別を強化するために、ワーピング関数の傾きに制限が課された。

不安定なクロックは、単純な電力解析を破るために使用されます。この防御に対抗するためにいくつかの手法が使用されていますが、そのうちの 1 つが動的タイム ワーピングです。

動的タイムワーピングは金融や計量経済学において、予測と現実世界のデータとの比較の質を評価するために使用されます。^{[32] [33] [34]}

• レーベンシュタイン距離
• 弾性マッチング
• 配列アライメント
• 多重配列アライメント
• ワグナー・フィッシャーアルゴリズム
• ニードルマン・ヴンシュアルゴリズム
• フレシェ距離
• 非線形混合効果モデル

• Pavel Senin、ダイナミック タイム ワーピング アルゴリズムのレビュー
• ヴィンツィク、TK (1968)。 「動的計画法による音声識別」。キベルネティカ。4：81～88。
• Sakoe, H.; 千葉 (1978)。「音声単語認識のための動的計画法アルゴリズムの最適化」IEEE Transactions on Acoustics, Speech, and Signal Processing 26 ( 1): 43–49. doi :10.1109/tassp.1978.1163055. S2CID  17900407。
• Myers, CS; Rabiner, LR (1981)。 「連結語認識のためのいくつかの動的タイムワーピングアルゴリズムの比較研究」。Bell System Technical Journal。60 ( 7): 1389–1409。doi : 10.1002 /j.1538-7305.1981.tb00272.x。ISSN 0005-8580。S2CID  12857347  。
• Rabiner, Lawrence; Juang, Biing-Hwang (1993)。「第 4 章: パターン比較テクニック」。音声認識の基礎。ニュージャージー州エングルウッド クリフス: PTR Prentice Hall。ISBN 978-0-13-015157-5。
• Müller, Meinard (2007)。ダイナミックタイムワーピング。音楽とモーションの情報検索、第 4 章、69-84 ページ( PDF)。Springer。doi :10.1007/978-3-540-74048-3。ISBN 978-3-540-74047-6。
• Rakthanmanon, Thanawin (2013 年 9 月)。「ビッグ データ時系列への対応: 動的タイム ワーピングによる数兆の時系列サブシーケンスのマイニング」。ACM Transactions on Knowledge Discovery from Data 。7 ( 3): 10: 1–10 :31。doi  : 10.1145/2513092.2500489。PMC 6790126。PMID 31607834。