論文の概要: Extrapolation Towards Imaginary $0$-Nearest Neighbour and Its Improved
Convergence Rate
- arxiv url: http://arxiv.org/abs/2002.03054v2
- Date: Wed, 11 Nov 2020 01:14:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 22:21:35.912130
- Title: Extrapolation Towards Imaginary $0$-Nearest Neighbour and Its Improved
Convergence Rate
- Title(参考訳): イマジナリー$0$Nearest近傍への外挿と収束率の改善
- Authors: Akifumi Okuno, Hidetoshi Shimodaira
- Abstract要約: そこで我々は,数個の$k ge 1$値から$k=0$まで,未重み付き$k$-NN推定器を外挿する新しいマルチスケール$k$-NN(MS-$k$-NN)を提案する。
提案手法は問合せとその周辺点に適応する最適実数値重みを暗黙的に計算する。
- 参考スコア(独自算出の注目度): 13.985534521589257
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: $k$-nearest neighbour ($k$-NN) is one of the simplest and most widely-used
methods for supervised classification, that predicts a query's label by taking
weighted ratio of observed labels of $k$ objects nearest to the query. The
weights and the parameter $k \in \mathbb{N}$ regulate its bias-variance
trade-off, and the trade-off implicitly affects the convergence rate of the
excess risk for the $k$-NN classifier; several existing studies considered
selecting optimal $k$ and weights to obtain faster convergence rate. Whereas
$k$-NN with non-negative weights has been developed widely, it was also proved
that negative weights are essential for eradicating the bias terms and
attaining optimal convergence rate. In this paper, we propose a novel
multiscale $k$-NN (MS-$k$-NN), that extrapolates unweighted $k$-NN estimators
from several $k \ge 1$ values to $k=0$, thus giving an imaginary 0-NN
estimator. Our method implicitly computes optimal real-valued weights that are
adaptive to the query and its neighbour points. We theoretically prove that the
MS-$k$-NN attains the improved rate, which coincides with the existing optimal
rate under some conditions.
- Abstract(参考訳): k$-nearest neighbor (k$-nn) は教師付き分類の最も単純かつ最も広く使われている方法の1つであり、クエリに最も近い$k$オブジェクトの観測ラベルの重み付け比率を取ることによってクエリのラベルを予測する。
重みとパラメータ $k \in \mathbb{N}$ はバイアス分散トレードオフを規制し、トレードオフは、$k$-NN分類器の余剰リスクの収束率に暗黙的に影響を及ぼす。
非負の重みを持つ$k$-NNは広く開発されているが、バイアス項の根絶や最適収束率の達成には負の重みが不可欠であることが証明された。
本稿では,数個の$k \ge 1$値から$k=0$への非重み付き$k$-NN推定器を外挿し,仮想的な0-NN推定器を与える,新しいマルチスケール$k$-NN(MS-$k$-NN)を提案する。
提案手法は問合せとその周辺点に適応する最適実数値重みを暗黙的に計算する。
理論的には、MS-$k$-NNは、ある条件下での既存の最適速度と一致する改善率に達することを証明している。
関連論文リスト
- Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳(メタデータ) (2023-11-21T18:50:38Z) - Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates
and Model Misspecification [16.0817847880416]
ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。
誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
論文 参考訳(メタデータ) (2022-01-06T08:51:08Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-01T14:10:38Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳(メタデータ) (2021-01-31T16:17:56Z) - Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed
Rewards [24.983866845065926]
我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。
本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。
提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
論文 参考訳(メタデータ) (2020-10-24T10:44:02Z) - Multi-label Contrastive Predictive Coding [125.03510235962095]
差分相互情報(MI)推定器は、コントラスト予測符号化(CPC)のような教師なし表現学習法で広く利用されている。
本稿では,複数の正のサンプルを同時に同定する必要がある多ラベル分類問題に基づく新しい推定器を提案する。
同一量の負のサンプルを用いて複数ラベルのCPCが$log m$boundを超えることができる一方で、相互情報の有意な下限であることを示す。
論文 参考訳(メタデータ) (2020-07-20T02:46:21Z) - 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) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳(メタデータ) (2020-06-29T21:06:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。