論文の概要: 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は近接探索に非常に有効であることが証明された。

関連論文リスト

• Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal [18.93478528448966]
  本稿では,Longth Scale Balancing (LB)について紹介する。 LBは、長いスケールを維持しながら、長いスケールの候補値を追加し、探索とエクスプロイトのバランスをとる。 LB はオラクルの後悔からわずか$log g(T) 離れている。
  論文  参考訳（メタデータ） (2024-10-14T11:17:00Z)
• More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning [58.626683114119906]
  本研究では,分散強化学習(DistRL)がオンラインとオフラインのRLの2次境界を得ることができることを示す。 我々の結果は、低ランク MDP とオフライン RL に対する最初の2階境界である。
  論文  参考訳（メタデータ） (2024-02-11T13:25:53Z)
• Light Schrödinger Bridge [72.88707358656869]
  我々は,軽量でシミュレーション不要で理論的に正当化されたSchr"odinger Bridgesソルバを開発した。 我々の光解法は密度推定に広く用いられているガウス混合モデルに類似している。 この類似性に着想を得て、光解法がSBの普遍近似であることを示す重要な理論的結果も証明した。
  論文  参考訳（メタデータ） (2023-10-02T13:06:45Z)
• Improving Offline RL by Blending Heuristics [33.810026421228635]
  Heuristic Blendingは、値ブートストラップに基づくオフラインRLアルゴリズムの性能を改善する。 HubLは、4つの最先端ブートストラップベースのオフラインRLアルゴリズムのポリシー品質を一貫して改善する。
  論文  参考訳（メタデータ） (2023-06-01T03:36:06Z)
• Local Branching Relaxation Heuristics for Integer Linear Programs [39.40838358438744]
  LNS(Large Neighborhood Search)は最適化問題の解法として一般的なアルゴリズムである。 本稿では,整数プログラム(ILP)におけるLNSの効率的かつ効率的な線形性の設計に焦点をあてる。 提案した緩和 LB-RELAX とその変種は,LB の線形計画法を用いて近傍を選択する。
  論文  参考訳（メタデータ） (2022-12-15T22:53:09Z)
• Isotuning With Applications To Scale-Free Online Learning [19.52475623314373]
  私たちは、高速で適応性があり、いつでも、スケールフリーなオンライン学習アルゴリズムを設計するために、文学のいくつかのツールを拡張し、組み合わせています。 最初の、そして主要なツールである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)
• Improving Semi-supervised Federated Learning by Reducing the Gradient Diversity of Models [67.66144604972052]
  Federated Learning(FL)は、ユーザのプライバシを維持しながらモバイルデバイスのコンピューティングパワーを使用する、有望な方法だ。 テスト精度に影響を与える重要な問題は、異なるユーザーからのモデルの勾配の多様性であることを示す。 本稿では,FedAvg平均化を代替するグループモデル平均化手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T03:36:07Z)
• Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
  量子アルゴリズムは、しばしばデータベースのような方法で格納された情報にアクセスするために量子RAM(QRAM)を使用する。 本稿では,Clifford+Tゲートの並列性を利用して,効率的なクエリ時間を大幅に短縮する手法を提案する。 理論的には、フォールトトレラントバケットの量子RAMクエリは古典的なRAMの速度とほぼ一致する。
  論文  参考訳（メタデータ） (2020-02-21T14:50:03Z)
• Exact Indexing of Time Series under Dynamic Time Warping [1.3300217947936062]
  シーケンス拡張とLB_Keoghをシームレスに組み合わせた新しい下界距離LB_Keogh+を提案する。 不等長列に使用することができ、計算複雑性が低い。 LB_Keogh+に基づいて、DTWの下での時系列の正確なインデックスを考案する。
  論文  参考訳（メタデータ） (2020-02-11T03:34:48Z)

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

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