論文の概要: Tight lower bounds for Dynamic Time Warping

• arxiv url: http://arxiv.org/abs/2102.07076v1
• Date: Sun, 14 Feb 2021 05:26:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-16 15:38:58.911742
• Title: Tight lower bounds for Dynamic Time Warping
• Title（参考訳）: ダイナミックタイムワーピングのためのタイトローバウンド
• Authors: Geoffrey I. Webb and Francois Petitjean
• Abstract要約: Dynamic Time Warping (DTW) は時系列の整列と比較のための一般的な類似度尺度である。 多くの代替低い境界が提案され、タイトさと計算効率の間のさまざまなトレードオフが提供されている。 同じ複雑性クラスに4つの新しいDTW下位境界を示す。
• 参考スコア（独自算出の注目度）: 6.063782572064742
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Dynamic Time Warping (DTW) is a popular similarity measure for aligning and comparing time series. Due to DTW's high computation time, lower bounds are often employed to screen poor matches. Many alternative lower bounds have been proposed, providing a range of different trade-offs between tightness and computational efficiency. LB Keogh provides a useful trade-off in many applications. Two recent lower bounds, LB Improved and LB Enhanced, are substantially tighter than LB Keogh. All three have the same worst case computational complexity - linear with respect to series length and constant with respect to window size. We present four new DTW lower bounds in the same complexity class. LB Petitjean is substantially tighter than LB Improved, with only modest additional computational overhead. LB Webb is more efficient than LB Improved, while often providing a tighter bound. LB Webb is always tighter than LB Keogh. The parameter free LB Webb is usually tighter than LB Enhanced. A parameterized variant, LB Webb Enhanced, is always tighter than LB Enhanced. A further variant, LB Webb*, is useful for some constrained distance functions. In extensive experiments, LB Webb proves to be very effective for nearest neighbor search.
• Abstract（参考訳）: Dynamic Time Warping (DTW) は時系列の整列と比較のための一般的な類似度尺度である。 DTWの計算時間が高いため、低い境界はマッチの表示にしばしば使用される。 多くの代替低い境界が提案され、タイトさと計算効率の間のさまざまなトレードオフが提供されている。 LB Keoghは多くのアプリケーションで便利なトレードオフを提供している。 最近の2つの下限、LB ImprovedとLB Enhancedは、LB Keoghよりもかなり狭い。 3つすべてに同じ最悪の場合の計算の複雑さがあります-シリーズ長に関して線形および窓のサイズに関して一定。 同じ複雑性クラスに4つの新しいDTW下位境界を示す。 LB Petitjean は LB Improved よりもかなり密であり、計算オーバーヘッドはわずかである。 LB Webb は LB Improved よりも効率的であり、しばしばより厳密なバウンダリを提供する。 LB Webbは常にLB Keoghよりきつい。 パラメータフリーのLB Webbは通常、LB Enhancedよりもタイトです。 パラメータ化された変種であるLB Webb Enhancedは、常にLB Enhancedよりも厳密である。 LB Webb* は、いくつかの制限された距離関数に有用である。 大規模な実験では、LB Webbは近接探索に非常に有効であることが証明された。

関連論文リスト

• Local Branching Relaxation Heuristics for Integer Linear Programs [39.40838358438744]
  LNS(Large Neighborhood Search)は最適化問題の解法として一般的なアルゴリズムである。 本稿では,整数プログラム(ILP)におけるLNSの効率的かつ効率的な線形性の設計に焦点をあてる。 提案した緩和 LB-RELAX とその変種は,LB の線形計画法を用いて近傍を選択する。
  論文  参考訳（メタデータ） (2022-12-15T22:53:09Z)
• Discrete Langevin Sampler via Wasserstein Gradient Flow [102.94731267405056]
  離散空間におけるワッサーシュタイン勾配流に対応する LB 関数がどのように LB 力学をもたらすかを示す。 シミュレーション時間に関してLBダイナミクスを識別し,新しいアルゴリズムであるLocally Balanced Jump (LBJ)を提案する。
  論文  参考訳（メタデータ） (2022-06-29T20:33:54Z)
• Bitwidth Heterogeneous Federated Learning with Progressive Weight Dequantization [58.31288475660333]
  ビット幅の不均一なフェデレート学習(BHFL)を用いた実用的フェデレーション学習シナリオを提案する。 BHFLは、異なるビット幅のモデルパラメータの集約が深刻な性能劣化をもたらすという、新しい課題をもたらす。 本稿では,低ビット幅の重みをより高ビット幅の重みに段階的に再構成し,最終的に完全精度の重みに再構成する,トレーニング可能な重み決定器を中央サーバに備えたProWDフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-02-23T12:07:02Z)
• Isotuning With Applications To Scale-Free Online Learning [32.79776733870005]
  高速で適応的で、いつでも、スケールフリーなオンライン学習アルゴリズムを設計するためのツールを開発しています。 最初の、そして主要なツールであるisotuningは、後悔のトレードオフのバランスをとるという考え方の一般化です。 第2のツールはオンラインの修正であり、多くのアルゴリズムで中心となる境界を求めることができる。 最後のツールはnullアップデートであり、アルゴリズムが過度に大規模な更新を行うのを防ぐ。
  論文  参考訳（メタデータ） (2021-12-29T14:58:56Z)
• Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Verification [151.62491805851107]
  私たちは、ニューロン毎の分割を完全にエンコードできるバウンド伝搬ベースの検証器である$beta$-crownを開発した。 Beta$-CROWNはLPベースのBaB法よりも3桁近い速さで堅牢性検証が可能です。 BaBを早期に終了することにより、不完全な検証にも使用できます。
  論文  参考訳（メタデータ） (2021-03-11T11:56:54Z)
• Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
  本稿では,ニューラルネットワークバウンダリングのための2つの新しい2重アルゴリズムを提案する。 どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。 実行時間のほんの一部で、既製のソルバよりも優れた境界を得ることができます。
  論文  参考訳（メタデータ） (2021-01-14T19:45:17Z)
• Revisiting convolutional neural network on graphs with polynomial approximations of Laplace-Beltrami spectral filtering [6.111909222842263]
  本稿では,Defferrardで与えられたスペクトルグラフニューラルネットワーク(graph-CNN)を再検討する。 グラフラプラシアンをLB演算子に置き換えることで、LBCNN(Laplace-Beltrami CNN)を開発する。
  論文  参考訳（メタデータ） (2020-10-26T01:18:05Z)
• Improving Semi-supervised Federated Learning by Reducing the Gradient Diversity of Models [67.66144604972052]
  Federated Learning(FL)は、ユーザのプライバシを維持しながらモバイルデバイスのコンピューティングパワーを使用する、有望な方法だ。 テスト精度に影響を与える重要な問題は、異なるユーザーからのモデルの勾配の多様性であることを示す。 本稿では,FedAvg平均化を代替するグループモデル平均化手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T03:36:07Z)
• Accelerated Convergence for Counterfactual Learning to Rank [65.63997193915257]
  IPS重み付き勾配を持つSGD手法の収束速度は、IPS重みによる大きなばらつきに悩まされることを示す。 本稿では,従来のIPS重み付け勾配降下法よりも優れた収束性を有する新しい学習アルゴリズムであるCounterSampleを提案する。 我々は、CounterSampleがより早く収束し、理論的な結果と経験的な結果とを補完することを証明する。
  論文  参考訳（メタデータ） (2020-05-21T12:53:36Z)
• Exact Indexing of Time Series under Dynamic Time Warping [1.3300217947936062]
  シーケンス拡張とLB_Keoghをシームレスに組み合わせた新しい下界距離LB_Keogh+を提案する。 不等長列に使用することができ、計算複雑性が低い。 LB_Keogh+に基づいて、DTWの下での時系列の正確なインデックスを考案する。
  論文  参考訳（メタデータ） (2020-02-11T03:34:48Z)

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

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