Fugu-MT 論文翻訳(概要): Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory

論文の概要: Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory

arxiv url: http://arxiv.org/abs/2007.16135v1
Date: Fri, 31 Jul 2020 15:31:05 GMT
ステータス: 処理完了
システム内更新日: 2022-11-04 07:19:21.810205
Title: Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory
Title（参考訳）: 時間ワープ編集距離の改善 --線形メモリにおける並列動的プログラム
Authors: Garrett Wright
Abstract要約: 改良時間ワープ編集距離アルゴリズムを提案する。このアルゴリズムは並列化可能であり、線形ストレージのみを必要とする。挑戦的な問題のスピードアップは驚くべきことです。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Edit Distance is a classic family of dynamic programming problems, among which Time Warp Edit Distance refines the problem with the notion of a metric and temporal elasticity. A novel Improved Time Warp Edit Distance algorithm that is both massively parallelizable and requiring only linear storage is presented. This method uses the procession of a three diagonal band to cover the original dynamic program space. Every element of the diagonal update can be computed in parallel. The core method is a feature of the TWED Longest Common Subsequence data dependence and is applicable to dynamic programs that share similar band subproblem structure. The algorithm has been implemented as a CUDA C library with Python bindings. Speedups for challenging problems are phenomenal.
Abstract（参考訳）: 編集距離(edit distance)は、動的プログラミング問題の古典的なファミリーであり、タイムワープ編集距離(time warp edit distance)は、計量と時間弾性の概念を用いて問題を洗練する。大規模並列化と線形記憶のみを必要とする,改良されたタイムワープ編集距離アルゴリズムを提案する。この方法は、オリジナルの動的プログラム空間をカバーするために3対角帯の行列を用いる。対角線更新のすべての要素は並列に計算できる。コア法(core method)は、twed long common subsequence data dependenceの特徴であり、類似のバンドサブプロブレム構造を共有する動的プログラムに適用できる。このアルゴリズムはPythonバインディングを備えたCUDA Cライブラリとして実装されている。挑戦的な問題のスピードアップは驚くべきことです。

関連論文リスト

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)
DeepSpeed Ulysses: System Optimizations for Enabling Training of Extreme Long Sequence Transformer Models [34.74093040678323]
我々は,高度に効率的かつスケーラブルなLDMトレーニングを実現するための,新しい,ポータブルで効果的な方法論であるDeepSpeed-Ulyssesを紹介した。 DeepSpeed-Ulyssesは、そのコアでシーケンス次元に沿って入力データを分割し、効率的なオール・ツー・オールの集合通信を用いて注意を払っている。実験の結果、DeepSpeed-Ulyssesは既存のSOTAベースラインの4倍のシーケンス長で2.5倍高速であることがわかった。
論文参考訳（メタデータ） (2023-09-25T20:15:57Z)
DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention [53.02648818164273]
動的双線形低ランク注意(DBA)という,効率的かつ効果的な注意機構を提案する。 DBAは入力感度の動的射影行列によってシーケンス長を圧縮し、線形時間と空間の複雑さを実現する。様々なシーケンス長条件のタスクに対する実験は、DBAが最先端のパフォーマンスを達成することを示す。
論文参考訳（メタデータ） (2022-11-24T03:06:36Z)
Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
論文参考訳（メタデータ） (2022-06-27T10:54:24Z)
Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting--Full Version [50.43914511877446]
本稿では,高い効率と精度を確保するために,三角形,可変特性に着目した注意点を提案する。我々はTriformerが精度と効率の両方で最先端の手法より優れていることを示す。
論文参考訳（メタデータ） (2022-04-28T20:41:49Z)
IDEA-Net: Dynamic 3D Point Cloud Interpolation via Deep Embedding Alignment [58.8330387551499]
我々は、点方向軌跡(すなわち滑らかな曲線)の推定として問題を定式化する。本稿では,学習した時間的一貫性の助けを借りて問題を解消する,エンドツーエンドのディープラーニングフレームワークであるIDEA-Netを提案する。各種点群における本手法の有効性を実証し, 定量的かつ視覚的に, 最先端の手法に対する大幅な改善を観察する。
論文参考訳（メタデータ） (2022-03-22T10:14:08Z)
Parallel Training of GRU Networks with a Multi-Grid Solver for Long Sequences [1.9798034349981162]
本稿では,GRU(Gated Recurrent Unit)ネットワークのための並列学習手法を提案する。 MGRITはシーケンスを複数の短いサブシーケンスに分割し、異なるプロセッサ上のサブシーケンスを並列に訓練する。 HMDB51データセットにおいて、各ビデオが画像シーケンスである実験結果から、新しい並列トレーニングスキームがシリアルアプローチよりも最大6.5$times$スピードアップを達成することを示した。
論文参考訳（メタデータ） (2022-03-07T11:32:44Z)
Elastic Product Quantization for Time Series [19.839572576189187]
本稿では,時間ゆらぎの時間系列の効率的な類似度に基づく比較に製品量子化を用いることを提案する。提案手法は, 時系列アプリケーションにおける弾性測度を, 高効率(メモリ使用量と時間の両方)で置き換える手法として現れる。
論文参考訳（メタデータ） (2022-01-04T09:23:06Z)
Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
トランスフォーマーベースのモデルは、自己アテンションモジュールの二次空間と時間的複雑さのために、長いシーケンスを処理するのに効率的ではない。我々はLinformerとInformerを提案し、低次元投影と行選択により2次複雑性を線形(モジュラー対数因子)に還元する。理論的解析に基づいて,Skeinformerを提案することにより,自己注意の促進と,自己注意への行列近似の精度の向上を図ることができる。
論文参考訳（メタデータ） (2021-12-10T06:58:05Z)
Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
論文参考訳（メタデータ） (2020-02-10T10:11:31Z)

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