論文の概要: Exact, Parallelizable Dynamic Time Warping Alignment with Linear Memory

• arxiv url: http://arxiv.org/abs/2008.02734v1
• Date: Tue, 4 Aug 2020 15:00:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-03 01:21:01.974613
• Title: Exact, Parallelizable Dynamic Time Warping Alignment with Linear Memory
• Title（参考訳）: 線形メモリによる並列化可能な動的時間ワープアライメント
• Authors: Christopher Tralie, Elizabeth Dempsey
• Abstract要約: 我々は,O(M+N)メモリを用いて,正確な大域的最適DTWアライメントを計算する分割・征服アルゴリズムを提案する。 我々のアルゴリズムは、同じメモリ制約でmin(M, N)の係数まで並列化できるので、十分なGPUで教科書版よりも効率的に実行できる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Audio alignment is a fundamental preprocessing step in many MIR pipelines. For two audio clips with M and N frames, respectively, the most popular approach, dynamic time warping (DTW), has O(MN) requirements in both memory and computation, which is prohibitive for frame-level alignments at reasonable rates. To address this, a variety of memory efficient algorithms exist to approximate the optimal alignment under the DTW cost. To our knowledge, however, no exact algorithms exist that are guaranteed to break the quadratic memory barrier. In this work, we present a divide and conquer algorithm that computes the exact globally optimal DTW alignment using O(M+N) memory. Its runtime is still O(MN), trading off memory for a 2x increase in computation. However, the algorithm can be parallelized up to a factor of min(M, N) with the same memory constraints, so it can still run more efficiently than the textbook version with an adequate GPU. We use our algorithm to compute exact alignments on a collection of orchestral music, which we use as ground truth to benchmark the alignment accuracy of several popular approximate alignment schemes at scales that were not previously possible.
• Abstract（参考訳）: オーディオアライメントは多くのMIRパイプラインにおける基本的な前処理ステップである。 mとnのフレームを持つ2つのオーディオクリップに対して、最も一般的なアプローチであるdynamic time warping(dtw)は、メモリと計算の両方においてo(mn)要件を持ち、合理的なレートでのフレームレベルのアライメントは禁止されている。 これを解決するために、DTWコストの最適アライメントを近似するために、様々なメモリ効率のアルゴリズムが存在する。 しかし、我々の知る限り、二次記憶障壁を破ることを保証する正確なアルゴリズムは存在しない。 本研究では,O(M+N)メモリを用いたDTWアライメントを高精度に計算する分割・征服アルゴリズムを提案する。 実行時はまだO(MN)であり、2倍の計算量増加のためにメモリをオフにしている。 しかし、このアルゴリズムは同じメモリ制約でmin(M, N)の係数まで並列化できるため、十分なGPUを備えた教科書版よりも効率的に動作することができる。 このアルゴリズムを用いてオーケストラ音楽の集合の正確なアライメントを計算し、それまで不可能であったスケールでのいくつかの一般的な近似アライメントスキームのアライメント精度のベンチマークを行う。

関連論文リスト

• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  本稿では, コントラスト損失計算を任意の小ブロックに分割するタイルベースの戦略を提案する。 分散システムの階層構造を活用するためのマルチレベルタイリング戦略も導入する。 SOTAメモリ効率のソリューションと比較すると、同等の速度を維持しながら、メモリの2桁の削減を実現している。
  論文  参考訳（メタデータ） (2024-10-22T17:59:30Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• Fast offset corrected in-memory training [0.0]
  インメモリコンピューティングのための新しいアルゴリズムと改良アルゴリズムを2つ提案する。 Chopped-TTv2 (c-TTv2) と Analog Gradient Accumulation with Dynamic Reference (AGAD) は同じランタイムの複雑さを維持しているが、チョッパーを使用した残りのオフセットに対して正しい。
  論文  参考訳（メタデータ） (2023-03-08T17:07:09Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
  累積記憶は時間空間の複雑さの尺度である。 逐次古典計算と量子回路の両方において、累積メモリの複雑さに関する最初の下位境界を証明した。
  論文  参考訳（メタデータ） (2023-01-13T17:57:02Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
  最適な輸送を計算するための厳密なアルゴリズムは遅くなる。 我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。 我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
  論文  参考訳（メタデータ） (2022-03-07T21:40:14Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute the Word Mover's Distance [0.18275108630751835]
  Word Mover's Distance (WMD) は、2つの文書間の意味的相違を測定するメトリクスである。 我々は、他の多くの文書に対して、ある文書のWMDを計算するための共有メモリ並列アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-14T05:30:18Z)

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

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