論文の概要: Universal consistency and rates of convergence of multiclass prototype
algorithms in metric spaces
- arxiv url: http://arxiv.org/abs/2010.00636v2
- Date: Wed, 21 Apr 2021 16:43:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 07:54:10.900081
- Title: Universal consistency and rates of convergence of multiclass prototype
algorithms in metric spaces
- Title（参考訳）: 距離空間における多クラスプロトタイプアルゴリズムの普遍的一貫性と収束率
- Authors: L\'aszl\'o Gy\"orfi and Roi Weiss
- Abstract要約: プロトNNは、普遍的に一貫した規則を持つ任意の距離空間において普遍的に一貫したものである。
我々は、$k$-NNとProto-NNをハイブリッド化する第2のプロトタイプルールが、同様の計算上の利点を享受しながら、$k$-NNと同じレートを達成することを示す。
- 参考スコア（独自算出の注目度）: 1.116812194101501
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study universal consistency and convergence rates of simple
nearest-neighbor prototype rules for the problem of multiclass classification
in metric paces. We first show that a novel data-dependent partitioning rule,
named Proto-NN, is universally consistent in any metric space that admits a
universally consistent rule. Proto-NN is a significant simplification of
OptiNet, a recently proposed compression-based algorithm that, to date, was the
only algorithm known to be universally consistent in such a general setting.
Practically, Proto-NN is simpler to implement and enjoys reduced computational
complexity.
We then proceed to study convergence rates of the excess error probability.
We first obtain rates for the standard $k$-NN rule under a margin condition and
a new generalized-Lipschitz condition. The latter is an extension of a recently
proposed modified-Lipschitz condition from $\mathbb R^d$ to metric spaces.
Similarly to the modified-Lipschitz condition, the new condition avoids any
boundness assumptions on the data distribution. While obtaining rates for
Proto-NN is left open, we show that a second prototype rule that hybridizes
between $k$-NN and Proto-NN achieves the same rates as $k$-NN while enjoying
similar computational advantages as Proto-NN. However, as $k$-NN, this hybrid
rule is not consistent in general.
- Abstract（参考訳）: 距離速度の多クラス分類問題に対する簡易近接プロトタイプルールの普遍的一貫性と収束率について検討する。
まず、新しいデータ依存分割規則であるProto-NNが、普遍的に一貫した規則を持つ任意の距離空間において普遍的に一貫していることを示す。
proto-nnは、最近提案された圧縮ベースのアルゴリズムであるoptinetの大幅な単純化であり、これまでそのような一般的な設定で普遍的に一貫性があることが知られている唯一のアルゴリズムであった。
実際、Proto-NNは実装が簡単で、計算の複雑さが減る。
次に,過大な誤差確率の収束率について検討する。
まず、マージン条件と新しい一般化Lipschitz条件の下で、標準$k$-NN規則のレートを得る。
後者は、最近提案された$\mathbb R^d$ から計量空間への修正・リプシッツ条件の拡張である。
修正リプシッツ条件と同様に、新しい条件はデータ分布上の任意の有界性仮定を避ける。
Proto-NNの取得レートは未公開であるが、$k$-NNとProto-NNをハイブリッド化する第2のプロトタイプルールが、Proto-NNと同じような計算上の利点を享受しながら、$k$-NNと同じレートを達成することを示す。
しかし、$k$-nn として、このハイブリッド規則は一般には一致しない。
関連論文リスト
- Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。
多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
論文 参考訳（メタデータ） (2024-09-08T13:08:45Z) - Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [13.642712817536072]
問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。
私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
論文 参考訳（メタデータ） (2024-08-20T01:24:54Z) - Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
固定学習率$eta$の勾配降下はスムーズな関数を表す局所最小値しか見つからないことを示す。
また、$n$のデータポイントのサポートの厳密な内部で、$widetildeO(n-4/5)$のほぼ最適MSE境界を証明します。
論文 参考訳（メタデータ） (2024-06-10T22:57:27Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - First detection probability in quantum resetting via random projective
measurements [0.0]
一般量子系における「興味のある状態」の最初の検出時間の確率分布を$F_r(t)$で計算する。
F_r(t)sim t2$ が$p(0)ne 0$ であることを示す。
論文 参考訳（メタデータ） (2023-05-24T13:15:01Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。
分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。
十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文 参考訳（メタデータ） (2022-02-05T01:59:09Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - On Uniform Convergence and Low-Norm Interpolation Learning [25.96459928769678]
経験的誤差と人口的誤差の差を均一に有界に表すことは,標準球における学習を全く示さないことを示す。
我々は、最小限のノルム補間器の整合性は、わずかに弱いが標準的概念、つまり標準球におけるゼロエラー予測器の一様収束で説明できると主張している。
論文 参考訳（メタデータ） (2020-06-10T16:49:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。