論文の概要: 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性能と効率により、アンダーバッグング手法の利点に関する理論的結果を検証するための数値実験を行う。
関連論文リスト
- Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。
ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。
Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
論文 参考訳(メタデータ) (2024-10-10T06:33:41Z) - 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) - 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) - Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。
分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。
十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文 参考訳(メタデータ) (2022-02-05T01:59:09Z) - 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) - Best-item Learning in Random Utility Models with Subset Choices [40.17224226373741]
我々は、$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて、$n$アイテムのプールから最も価値のあるアイテムをPACで学習する問題を考察する。
そのようなRUMの新たな性質を最小限の利点と呼び、アイテムのペアを分離する複雑さを特徴づけるのに役立つ。
一般RUMの学習アルゴリズムとして,アイテムの相対的な数と階層的除去と,新しいPACサンプルの複雑性保証を併用した学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-19T03:57:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。