論文の概要: Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves

• arxiv url: http://arxiv.org/abs/2505.23431v1
• Date: Thu, 29 May 2025 13:25:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 18:14:07.870024
• Title: Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
• Title（参考訳）: k-DTWによる学習改善:曲線の新しい異性度尺度
• Authors: Amer Krivošija, Alexander Munteanu, André Nusser, Chris Schwiegelshohn,
• Abstract要約: k$-Dynamic Time Warping(k$-DTW)と呼ばれる多角曲線に対する新しい相似性尺度を導入する。 $k$-DTW は Dynamic Time Warping (DTW) よりも強いメトリック特性を持ち、Fr'echet 距離よりも外れ値に対して堅牢である。 1+varepsilon)$-approximation algorithm for $k$-DTW。
• 参考スコア（独自算出の注目度）: 48.84313029960523
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces $k$-Dynamic Time Warping ($k$-DTW), a novel dissimilarity measure for polygonal curves. $k$-DTW has stronger metric properties than Dynamic Time Warping (DTW) and is more robust to outliers than the Fr\'{e}chet distance, which are the two gold standards of dissimilarity measures for polygonal curves. We show interesting properties of $k$-DTW and give an exact algorithm as well as a $(1+\varepsilon)$-approximation algorithm for $k$-DTW by a parametric search for the $k$-th largest matched distance. We prove the first dimension-free learning bounds for curves and further learning theoretic results. $k$-DTW not only admits smaller sample size than DTW for the problem of learning the median of curves, where some factors depending on the curves' complexity $m$ are replaced by $k$, but we also show a surprising separation on the associated Rademacher and Gaussian complexities: $k$-DTW admits strictly smaller bounds than DTW, by a factor $\tilde\Omega(\sqrt{m})$ when $k\ll m$. We complement our theoretical findings with an experimental illustration of the benefits of using $k$-DTW for clustering and nearest neighbor classification.
• Abstract（参考訳）: 本稿では,多角曲線に対する新しい相似性尺度である$k$-Dynamic Time Warping(k$-DTW)を紹介する。 k$-DTW は動的時間ウォーピング (DTW) よりも強い計量特性を持ち、多角曲線の相似性測度の2つのゴールド標準である Fr\'{e}chet 距離よりも外れ値に強い。 1+\varepsilon)$-approximation algorithm for $k$-DTW by a parametric search for the $k$-th largest matched distance。 我々は、曲線に対する最初の次元自由学習境界を証明し、さらに理論的な結果を学習する。 $k$-DTW は曲線の中央値学習の問題に対して DTW よりも小さいサンプルサイズを認め、そこでは曲線の複雑性に依存するいくつかの因子が $k$ に置き換えられるが、関連するラデマッハとガウスの複素量に対して驚くべき分離を示す: $k$-DTW は DTW よりも厳密に小さな境界を $\tilde\Omega(\sqrt{m})$ で表す。 我々は,クラスタリングと近傍の分類に$k$-DTWを使うことの利点を実験的に示すことによって,理論的知見を補完する。

関連論文リスト

• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards [6.932056534450556]
  AdaOFUL と VARA という2つのアルゴリズムを,重み付き報酬の存在下でのオンラインシーケンシャルな意思決定のために提案する。 AdaOFULは、$widetildemathcalObigの最先端の後悔境界を達成する。 VarA は $widetildemathcalO(dsqrtHmathcalG*K)$ のより厳密な分散を考慮した後悔境界を達成する。
  論文  参考訳（メタデータ） (2023-03-09T22:16:28Z)
• Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error [8.615625517708324]
  サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。 本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
  論文  参考訳（メタデータ） (2023-02-23T19:13:30Z)
• Adversarially Robust Learning with Tolerance [8.658596218544774]
  本稿では,距離摂動集合に対する寛容逆PAC学習の問題点について考察する。 自然摂動・平滑アルゴリズムの変種であるPACは、$gamma$-tolerant adversarial setにおいて、VC次元が$v$の任意の仮説クラス$mathcalH$を学習する。 また,2次元に線形依存したサンプル境界を求める学習手法を提案する。
  論文  参考訳（メタデータ） (2022-03-02T03:50:16Z)
• Policy Optimization Using Semiparametric Models for Dynamic Pricing [1.3428344011390776]
  商品の市場価値が観測された特徴と市場ノイズに線形である状況的動的価格問題について検討する。 一般化線形モデルからの半パラメトリック推定と未知のリンクとオンライン意思決定を組み合わせた動的統計的学習と意思決定ポリシーを提案する。
  論文  参考訳（メタデータ） (2021-09-13T23:50:01Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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