DTWに関する誤解 - ろむめも

Dynamic Time Warping(動的時間伸縮法)

DTW自体は特に時系列データの幅が異なる場合に有効となる、時系列データの類似性を調べる手法です。
なんとなくですが、データの時間方向の伸びを集約し、信号の時間変化や絶対値が似ているかどうかをモデルが持つ状態数分だけ区別できる方法だと認識しています。

DTWの概要
時系列相関 (CCF) の場合は片方を並行移動させているだけなので 2つの系列の周期が異なる場合は相関はでにくい。
DTW では 2つの時系列の各点の距離を総当りで比較した上で、系列同士の距離が最短となるパスを見つける。これが DTW 距離になる。そのため、2つの系列の周期性が違っても / 長さが違っても DTW 距離を定義することができる。
http://sinhrks.hatenablog.com/entry/2014/11/14/232603

今回、そのDTWに関して、以下の論文を読みましたので、その内容をまとめておきます。
http://wearables.cc.gatech.edu/paper_of_week/DTW_myths.pdf

概要

Dynamic Time Warping distance measureは主に言語認識界隈でしられていた技術でした。それは距離を最小化することによって一つの信号を他の信号へ非線形にマッピングする方法です。10年前にDTWはデータマイニングの業界にクラス分類、クラスタリング、あるいは異常検知を含む様々な時系列データの問題への手法として紹介されました。この方法は約3年ぐらい前に流行り、いろいろな問題へ適用されてきました。
DTWには多くの成功があるにも関わらず、まだいろいろな神話があります。その神話は混乱を招き、研究への努力を無駄にしています。本文ではこれまでに行われた最も包括的な時系列実験のセットでこれらの神話を払拭します。

導入

DTWの距離測定にはユークリッド距離が多くの研究で使われていますが、時間軸におけるディストーションへの弱さは無視されています。DTW距離測定を使うことで、ユークリッド距離を使う場合の特定の弱さを解消できると紹介されました。この方法の柔軟性は似ているが局所的に位相がずれている2つの時系列を非線形に整列させることを可能にします。DTWはo(n^2)であるにもかかわらず、時系列データに対する最適な解法として、bioinformatics, medicine, engineering, entertainment等で使われています。

DTWでの研究は、簡単な下限によってDTWが間違わずに分類できることをきっかけに増えてきました。下限には2つのシーケンスの同じ長さと、ワーピング量の制限が必要です。これによってDTWは実際のアプリケーションで利用できます。
しかし、このような偉大な成功にもかかわらず、3つの神話が存在します。

神話1

さまざまな長さのシーケンスを処理するDTWの能力は大きな利点であり、したがって異なる長さのシーケンスを等しい長さに再補間することを必要とする単純な下限は、有用性を限定的にする[18] [27] [28]。
事実、我々が示すように、これを示唆する証拠は文献に存在せず、ことなる長さのシーケンスと、同じ長さに再補間したものでは精度、リコールにおいて統計学的な差は確認されていない。

神話2

ワーピングパスを制約することは必要悪です。それは、DTWを扱いやすくするために音声認識界隈から継承されたものであり、私たちは制約なしでDTWを高速化する方法見つけるべきです。

神話3

DTWのスピードは改善する必要があります。実際、単純な下限を活用した場合、DTWはO(n)で処理ができます。少なくともCPUではスピードアップには限界があります。

これらの神話を払拭し、DTWは異なる長さの時系列データと同じ長さの時系列データのどちらを使った場合においても精度に差はないという事を示すため以下の実験をしました。私たちは1-neaest-neightbor classificationの精度をDTWの全てのwarping window size(1%-100%)を、以下の2つの異なる方法を使って計算しました。

1)シーケンスを同じ長さにするように単純再補間
2)シーケンスの元の長さ

異なる長さのデータの取り扱いが不利になるように、以下の全ての正規化を行い、それらの最も良いデータを使って精度を見積もりました。

距離で正規化しない
最適ワーピングパスの長さで正規化
短い時系列データの長さで正規化
長い時系列データの長さで正規化

結果

データの長さによる結果に差はありませんでした。
再補間を必要とする類似度検索を行うことは存在しない問題を解決していることと同じである。
違う長さのシーケンスを比較できるようにするユーティリティは単なる神話。

じゃあ狭い制約は悪なのか

少ないデータ数では実験的に広い制約をとることの有意なデータは得られませんでした。なので、DTWでは狭い制約を取る必要があることが示唆された。

スピードアップは可能か

大体O(n)でO(n^2)ではない。
数千程度の時系列データでは1秒以内に計算できるので問題ない。

結論

今回の仕事では、ダイナミックタイムワーピング測定のいくつかの神話を指摘し、調査しました。我々は3つの主張を経験的に検証した。我々は、結果がより有用な問題に焦点を当てるのに役立つことを願っています。

例えば、過去10年間にDTWのスピードアップに関する論文が数十件ありましたが、より正確にDTWを作成することが1件しかありませんでした[23]。
同様に、私たちは、この研究で実証したDTWの速度と精度が、研究者にDTWを豊富な新しい問題/領域に適用するよう促してくれるかもしれないと感じています。