論文の概要: 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バインディングとともに実装をリリースします。

関連論文リスト

• Flash Inference: Near Linear Time Inference for Long Convolution Sequence Models and Beyond [7.280765035096294]
  本稿では,LCSMの正確な推定速度を準線形$O(Llog2L)$ timeに高速化する手法を提案する。 私たちはHyenaのコンセプト実装の証明を提供し、標準推論よりも1.6倍のエンドツーエンドの改善が得られます。
  論文  参考訳（メタデータ） (2024-10-16T19:23:46Z)
• 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)
• BayOTIDE: Bayesian Online Multivariate Time series Imputation with functional decomposition [31.096125530322933]
  交通やエネルギーといった現実のシナリオでは、値やノイズが欠けている巨大な時系列データが広く観測され、不規則にサンプリングされる。 多くの計算法が提案されているが、そのほとんどは局所的な地平線で動作する。 ほとんど全ての手法は、観測は通常のタイムスタンプでサンプリングされ、複雑な不規則なサンプル時系列を扱うことができないと仮定する。
  論文  参考訳（メタデータ） (2023-08-28T21:17:12Z)
• 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)
• 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)

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

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