1: path[] <- new array
2: i =rows(dtw)
3: j =columns(dtw)
4: while(i>1) & (j>1)do5: if (i == 1) then
6: j = j-17: elseif (j == 1) then
8: i = i-19: else10: if dtw(i-1;j) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1; j-1)} then
11: i = i-112: elseif dtw(i;j-1) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1;j-1)} then
13: j = j-114: else15: i = i-1; j = j-116: end if17: path:add(i;j)
18: end if19: end while20: return path
この問題は、DTW(例)を介してどのように解決されるのでしょうか。
合計で50,000,000回の比較をDTWアルゴリズムで行いましたが、その計算量はO(N^2)です。つまり、非常にざっくりと5 * 10^11(5000億)回の素数計算が行われたことになる。
今、新しいバーが 来た。また5000億回の計算をしたんだ。
一番外側の元素の200 000から、履歴で実行することにしました。大体、20万回5000億回ずつ計算すると1回になる。合計で10^17回の計算ですね。
仮にトリッキーな最適化があったとしても、2桁以上の利得は得られないでしょう。つまり、最大で10^15回の計算をしなければならないのです。
この課題をDTWで解決する方法(例)。
もし差し支えなければ、この問題の解決策をコードで示してください。実用的な興味というより、スポーツ的な興味です。
まともな神経の持ち主なら、結果を待てないようなアルゴリズムを実装することはないだろう。
同じピアソンQCでも、DTWは計算量がO(N^2)なので不向きでしょう。しかし、複雑さO(N * log(N))のPearson QC計算の アルゴリズムの重要な最適 化があり、この問題を合理的な時間で解決できる可能性があるのです。本アルゴリズムの実装はCodebaseに掲載されています。提起された問題を解決するためには、同じアルゴリズムをZigZag変換されたZVRの集合に適用することが残されています。
まともな神経の持ち主なら、結果を待てないようなアルゴリズムを実装することはないだろう。
同じピアソンQCでも、DTWは計算量がO(N^2)なので不向きでしょう。しかし、複雑さO(N * log(N))のPearson QC計算のアルゴリズムの重要な最適化があり、この問題を合理的な時間で解決できる可能性があるのです。本アルゴリズムの実装はCodebaseに掲載されています。提起された問題を解決するためには、同じアルゴリズムをZigZag変換されたZVRの集合に適用することが残されています。
まずは著者が抱えている問題とその答えを読み取るべきでしょう。
試してみました。私も使い方がよくわかりません。出力は、変換パスまたは変換後のデータのいずれかでなければならない。
アルゴリズムの出力は「累積コスト行列」(図に示した単なる局所距離行列ではない)で、このメソッドは右下のセルの値を返す(構造上、行列全体の中で最大となる)。今、道を見つけるには、セル(n,m)からセル(1,1)に向かって移動し、そのたびに最も低い値のオプションを選択すればよい。
OK、ありがとうございます、非常に明確でした、もう一つ質問です:データを正規化または並べ替える必要性はありますか、それは結果に影響しますか?