論文の概要: Early Abandoning PrunedDTW and its application to similarity search

• arxiv url: http://arxiv.org/abs/2010.05371v1
• Date: Sun, 11 Oct 2020 23:53:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-08 13:50:09.098587
• Title: Early Abandoning PrunedDTW and its application to similarity search
• Title（参考訳）: 早期放棄型pruneddtwとその類似性探索への応用
• Authors: Matthieu Herrmann and Geoffrey I. Webb
• Abstract要約: EAPrunedDTW は UCR Suite における類似検索の時間を大幅に改善する。 EAPrunedDTW は UCR Suite における類似性検索の時間を大幅に改善することを示す。
• 参考スコア（独自算出の注目度）: 5.614519484892094
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Dynamic Time Warping ("DTW") distance is widely used in time series analysis, be it for classification, clustering or similarity search. However, its quadratic time complexity prevents it from scaling. Strategies, based on early abandoning DTW or skipping its computation altogether thanks to lower bounds, have been developed for certain use cases such as nearest neighbour search. But vectorization and approximation aside, no advance was made on DTW itself until recently with the introduction of PrunedDTW. This algorithm, able to prune unpromising alignments, was later fitted with early abandoning. We present a new version of PrunedDTW, "EAPrunedDTW", designed with early abandon in mind from the start, and able to early abandon faster than before. We show that EAPrunedDTW significantly improves the computation time of similarity search in the UCR Suite, and renders lower bounds dispensable.
• Abstract（参考訳）: 動的時間ワープ(DTW)距離は、分類、クラスタリング、類似性探索などの時系列解析に広く用いられている。 しかし、その二次時間の複雑さはスケーリングを妨げている。 DTWを早期に放棄するか、あるいは低い境界によって完全に計算をスキップする戦略は、近接探索のような特定のユースケースのために開発されている。 しかし,ベクトル化や近似はさておき,最近PrunedDTWが導入されるまでDTW自体に進展はなかった。 このアルゴリズムは未完成のアライメントを創り出すことができ、後に早期に放棄された。 PrunedDTWの新バージョンである"EAPrunedDTW"を紹介します。 EAPrunedDTW は UCR Suite における類似性探索の計算時間を大幅に改善し,下位境界を許容できることを示す。

関連論文リスト

• OTW: Optimal Transport Warping for Time Series [75.69837166816501]
  動的時間温暖化(DTW)は時系列間の距離を測定するための実用的な選択肢となっている。 最適アライメント行列を正確に計算する必要がある場合、それは避けられない二次時間複雑性に悩まされる。 我々は、OTW(Optimal Transport Warping)と呼ばれる、最適輸送フレームワークに基づく時系列データのための新しいメトリクスを導入する。
  論文  参考訳（メタデータ） (2023-06-01T12:45:00Z)
• Approximating DTW with a convolutional neural network on EEG data [9.409281517596396]
  動的時間ラッピング(DTW)の高速かつ微分可能な近似法を提案する。 提案手法は,計算効率が向上した他のDTW主近似と同等以上の精度が得られることを示す。
  論文  参考訳（メタデータ） (2023-01-30T13:27:47Z)
• Post-Processing Temporal Action Detection [134.26292288193298]
  時間的行動検出(TAD)法は、通常、入力された可変長のビデオを固定長のスニペット表現シーケンスに変換する際に、前処理のステップを踏む。 この前処理ステップは、ビデオを時間的にダウンサンプリングし、推論の解像度を低減し、元の時間分解における検出性能を阻害する。 モデルの再設計や再学習を伴わない新しいモデル非依存のポストプロセッシング手法を提案する。
  論文  参考訳（メタデータ） (2022-11-27T19:50:37Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Early Abandoning and Pruning for Elastic Distances [6.063782572064742]
  我々は,プランニングと早期放棄を緊密に統合する新しい総合戦略 "EAPruned" を開発した。 提案手法をDTW, CDTW, WDTW, ERP, MSM, TWEに適用し, NN1のようなシナリオの大幅な高速化を示す。 我々は、時系列分類のための新しいC++ライブラリの一部として実装をリリースし、Python/Numpyバインディングを簡単に使用しました。
  論文  参考訳（メタデータ） (2021-02-10T02:13:27Z)
• Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW [1.282368486390644]
  動的時間ワープの下で時系列のモチーフを発見するための,最初のスケーラブルな正確な方法を提案する。 我々のアルゴリズムは、DTW計算の99.99%を許容できる。
  論文  参考訳（メタデータ） (2020-09-16T19:35:43Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• FastDTW is approximate and Generally Slower than the Algorithm it Approximates [11.689905300531917]
  動的時間ワープ(DTW)距離測定は、ほとんどのドメインにおいて、ほとんどのタスクに最適な尺度である。 最も引用されているアプローチの1つはFastDTWである。 任意の現実的なデータマイニングアプリケーションでは、近似的なFastDTWは正確なDTWよりもはるかに遅い。
  論文  参考訳（メタデータ） (2020-03-25T07:26:02Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。