論文の概要: 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 として、このハイブリッド規則は一般には一致しない。
関連論文リスト
- Bridging the Gap between Newton-Raphson Method and Regularized Policy
Iteration [13.166738075816493]
規則化されたポリシー反復は、強い凸関数を持つベルマン方程式を滑らかにする条件において、標準ニュートン・ラフソン法と厳密に等価であることを示す。
正規化政策反復が大域的線形収束を持ち、そのレートが$gamma$ (discount factor)であることを証明する。
また、正規化ポリシー反復の修正版、すなわち有限ステップのポリシー評価はニュートン法と等価であり、ニュートンの反復式はトランカットされた反復で解かれることを示す。
論文 参考訳(メタデータ) (2023-10-11T05:55:20Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。