論文の概要: Under-bagging Nearest Neighbors for Imbalanced Classification
- arxiv url: http://arxiv.org/abs/2109.00531v1
- Date: Wed, 1 Sep 2021 14:10:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-03 14:06:19.223510
- Title: Under-bagging Nearest Neighbors for Imbalanced Classification
- Title(参考訳): 不均衡分類のためのアンダーバッグニーバー
- Authors: Hanyuan Hang, Yuchao Cai, Hanfang Yang, Zhouchen Lin
- Abstract要約: 我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 63.026765294759876
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose an ensemble learning algorithm called
\textit{under-bagging $k$-nearest neighbors} (\textit{under-bagging $k$-NN})
for imbalanced classification problems. On the theoretical side, by developing
a new learning theory analysis, we show that with properly chosen parameters,
i.e., the number of nearest neighbors $k$, the expected sub-sample size $s$,
and the bagging rounds $B$, optimal convergence rates for under-bagging $k$-NN
can be achieved under mild assumptions w.r.t.~the arithmetic mean (AM) of
recalls. Moreover, we show that with a relatively small $B$, the expected
sub-sample size $s$ can be much smaller than the number of training data $n$ at
each bagging round, and the number of nearest neighbors $k$ can be reduced
simultaneously, especially when the data are highly imbalanced, which leads to
substantially lower time complexity and roughly the same space complexity. On
the practical side, we conduct numerical experiments to verify the theoretical
results on the benefits of the under-bagging technique by the promising AM
performance and efficiency of our proposed algorithm.
- Abstract(参考訳): 本稿では,不均衡な分類問題に対して,<textit{under-bagging $k$-nearest neighbors} (\textit{under-bagging $k$-NN})というアンサンブル学習アルゴリズムを提案する。
理論面では、新しい学習理論分析を開発することにより、適切に選択されたパラメータ、すなわち、近隣の$k$、期待されるサブサンプルサイズ$s$、バッグングラウンド$B$、アンダーバッグング$k$-NNの最適収束率は、リコールの算術平均(AM)の軽度な仮定の下で達成できることが示される。
さらに、比較的小さな$B$では、期待されるサブサンプルサイズ$s$は、各バッグラウンドでのトレーニングデータ$n$よりもはるかに小さくなり、特にデータが高度に不均衡な場合、近接する$k$の数は同時に減少し、時間的複雑さが著しく減少し、空間的複雑さがほぼ同じになることを示す。
実用面では、提案アルゴリズムの有望なAM性能と効率により、アンダーバッグング手法の利点に関する理論的結果を検証するための数値実験を行う。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。
本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。
我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
論文 参考訳(メタデータ) (2020-06-07T00:34:33Z) - Attribute-Efficient Learning of Halfspaces with Malicious Noise:
Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
本稿では,雑音下でのmathbbRd$における等質スパース半空間の計算的学習について述べる。
サンプルの複雑さは$tildeObig(frac 1 epsilon s2 log5 d big)$であり、属性効率も楽しめます。
論文 参考訳(メタデータ) (2020-06-06T04:57:39Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Best-item Learning in Random Utility Models with Subset Choices [40.17224226373741]
我々は、$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて、$n$アイテムのプールから最も価値のあるアイテムをPACで学習する問題を考察する。
そのようなRUMの新たな性質を最小限の利点と呼び、アイテムのペアを分離する複雑さを特徴づけるのに役立つ。
一般RUMの学習アルゴリズムとして,アイテムの相対的な数と階層的除去と,新しいPACサンプルの複雑性保証を併用した学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-19T03:57:16Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳(メタデータ) (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。