論文の概要: 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は、ある条件下での既存の最適速度と一致する改善率に達することを証明している。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳(メタデータ) (2024-11-12T11:30:53Z) - 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) - Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳(メタデータ) (2024-05-24T11:22:19Z) - Nearest Neighbor Sampling for Covariate Shift Adaptation [7.940293148084844]
重みを推定しない新しい共変量シフト適応法を提案する。
基本的な考え方は、ソースデータセットの$k$-nearestの隣人によってラベル付けされたラベル付けされていないターゲットデータを直接扱うことだ。
実験の結果, 走行時間を大幅に短縮できることがわかった。
論文 参考訳(メタデータ) (2023-12-15T17:28:09Z) - 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) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - 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) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳(メタデータ) (2020-06-29T21:06:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。