論文の概要: Early Abandoning and Pruning for Elastic Distances
- arxiv url: http://arxiv.org/abs/2102.05221v1
- Date: Wed, 10 Feb 2021 02:13:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-11 21:51:20.690995
- Title: Early Abandoning and Pruning for Elastic Distances
- Title(参考訳): 弾性距離の早期放棄と刈り取り
- Authors: Matthieu Herrmann and Geoffrey I. Webb
- Abstract要約: 我々は,プランニングと早期放棄を緊密に統合する新しい総合戦略 "EAPruned" を開発した。
提案手法をDTW, CDTW, WDTW, ERP, MSM, TWEに適用し, NN1のようなシナリオの大幅な高速化を示す。
我々は、時系列分類のための新しいC++ライブラリの一部として実装をリリースし、Python/Numpyバインディングを簡単に使用しました。
- 参考スコア(独自算出の注目度): 6.063782572064742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Elastic distances are key tools for time series analysis. Straightforward
implementations require O(n2)space and time complexities, preventing many
applications from scaling to long series. Much work hasbeen devoted in speeding
up these applications, mostly with the development of lower bounds, allowing to
avoid costly distance computations when a given threshold is exceeded. This
threshold also allows to early abandon the computation of the distance itself.
Another approach, developed for DTW, is to prune parts of the computation. All
these techniques are orthogonal to each other. In this work, we develop a new
generic strategy, "EAPruned", that tightly integrates pruning with early
abandoning. We apply it to DTW, CDTW, WDTW, ERP, MSM and TWE, showing
substantial speedup in NN1-like scenarios. Pruning also shows substantial
speedup for some distances, benefiting applications such as clustering where
all pairwise distances are required and hence early abandoning is not
applicable. We release our implementation as part of a new C++ library for time
series classification, along with easy to usePython/Numpy bindings.
- Abstract(参考訳): 弾性距離は時系列分析の重要なツールです。
簡単な実装では、o(n2)スペースと時間の複雑さが必要であり、多くのアプリケーションが長いシリーズにスケールするのを防ぐ。
これらのアプリケーションのスピードアップに費やす多くの作業は、主に下限の開発に費やされており、与えられたしきい値を超えるとコストのかかる距離計算を避けることができる。
このしきい値はまた、距離自体の計算を早期に放棄することができる。
DTW用に開発された別のアプローチは、計算の一部をプルークするものである。
これらの技法は互いに直交している。
本研究では,早期放棄とプルーニングを緊密に統合する新しい総合戦略である「EAPruned」を開発する。
提案手法をDTW, CDTW, WDTW, ERP, MSM, TWEに適用し, NN1のようなシナリオの大幅な高速化を示す。
プルーニングはまた、いくつかの距離に対してかなりのスピードアップを示し、すべてのペアワイズ距離が必要なクラスタリングのようなアプリケーションにより、早期放棄は適用されない。
時系列分類のための新しいC++ライブラリの一部として、使用しやすいPython/Numpyバインディングとともに実装をリリースします。
関連論文リスト
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳(メタデータ) (2023-12-19T02:27:22Z) - SKI to go Faster: Accelerating Toeplitz Neural Networks via Asymmetric
Kernels [69.47358238222586]
Toeplitz Neural Networks (TNN) は、印象的な結果を持つ最近のシーケンスモデルである。
我々は, O(n) 計算複雑性と O(n) 相対位置エンコーダ (RPE) 多層パーセプトロン (MLP) と減衰バイアスコールの低減を目指す。
双方向モデルの場合、これはスパースと低ランクのToeplitz行列分解を動機付ける。
論文 参考訳(メタデータ) (2023-05-15T21:25:35Z) - RSC: Accelerating Graph Neural Networks Training via Randomized Sparse
Computations [56.59168541623729]
トレーニンググラフニューラルネットワーク(GNN)は、疎グラフベースの操作がハードウェアによって加速することが難しいため、時間を要する。
我々は,サンプリングに基づく近似による時間的複雑性を低減するために,計算精度のトレードオフを検討する。
本稿では,GNNを近似演算でトレーニングする可能性を初めて示すランダム化スパース計算を提案する。
論文 参考訳(メタデータ) (2022-10-19T17:25:33Z) - Training Robust Deep Models for Time-Series Domain: Novel Algorithms and
Theoretical Analysis [32.45387153404849]
時系列分類タスクのための堅牢なDNNを作成するために,RObust Training for Time-Series (RO-TS) と呼ばれる新しいフレームワークを提案する。
時系列アライメントによる和構造を用いた定式化の一般化と利点を示す。
実世界のベンチマーク実験により, RO-TSは, 対戦型トレーニングと比較して, より堅牢なDNNを生成することが示された。
論文 参考訳(メタデータ) (2022-07-09T17:21:03Z) - Planning and Learning with Adaptive Lookahead [74.39132848733847]
ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。
近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。
本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
論文 参考訳(メタデータ) (2022-01-28T20:26:55Z) - Magic Pyramid: Accelerating Inference with Early Exiting and Token
Pruning [19.93342734884434]
本稿では,トークンプルーニングによる幅と深さの計算と,トランスフォーマーモデルによる早期退避を両立させる新しいアイデアであるMagic Pyramid (MP)を提案する。
MPは、入力のサイズに関係なく、2つの一般的なテキスト分類タスクで平均8.06倍のスピードアップを達成することができる。
論文 参考訳(メタデータ) (2021-10-30T11:07:43Z) - Scalable Optimal Transport in High Dimensions for Graph Distances,
Embedding Alignment, and More [7.484063729015126]
最適輸送のためのコスト行列の2つの効率的な対数線形時間近似を提案する。
これらの近似は、複雑な高次元空間に対してもよく機能するエントロピー規則化OTに対する一般的な対数線形時間アルゴリズムを可能にする。
グラフ距離回帰のために,グラフニューラルネットワーク(GNN)と拡張シンクホーンを組み合わせたグラフトランスポートネットワーク(GTN)を提案する。
論文 参考訳(メタデータ) (2021-07-14T17:40:08Z) - Semiring Primitives for Sparse Neighborhood Methods on the GPU [16.56995698312561]
スパース半環プリミティブは、幅広い臨界距離測度をサポートするのに十分な柔軟性を持つことができる。
このプリミティブは、多くの近隣情報検索と機械学習アルゴリズムがスパース入力を受け付けるための基礎的なコンポーネントである。
論文 参考訳(メタデータ) (2021-04-13T17:05:03Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - Early Abandoning PrunedDTW and its application to similarity search [5.614519484892094]
EAPrunedDTW は UCR Suite における類似検索の時間を大幅に改善する。
EAPrunedDTW は UCR Suite における類似性検索の時間を大幅に改善することを示す。
論文 参考訳(メタデータ) (2020-10-11T23:53:25Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。