論文の概要: Bagging is an Optimal PAC Learner
- arxiv url: http://arxiv.org/abs/2212.02264v1
- Date: Mon, 5 Dec 2022 13:43:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 19:21:23.014526
- Title: Bagging is an Optimal PAC Learner
- Title（参考訳）: Baggingは最適なPAC学習者である
- Authors: Kasper Green Larsen
- Abstract要約: Baggingは、Hannekeのアルゴリズムが20年前から使われており、ほとんどの学部の機械学習コースで教えられている。
我々は,ハネケのアルゴリズムを20年前から実践しており,ほとんどの学部の機械学習コースで教えられていることを示す。
- 参考スコア（独自算出の注目度）: 12.411844611718958
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Determining the optimal sample complexity of PAC learning in the realizable
setting was a central open problem in learning theory for decades. Finally, the
seminal work by Hanneke (2016) gave an algorithm with a provably optimal sample
complexity. His algorithm is based on a careful and structured sub-sampling of
the training data and then returning a majority vote among hypotheses trained
on each of the sub-samples. While being a very exciting theoretical result, it
has not had much impact in practice, in part due to inefficiency, since it
constructs a polynomial number of sub-samples of the training data, each of
linear size.
In this work, we prove the surprising result that the practical and classic
heuristic bagging (a.k.a. bootstrap aggregation), due to Breimann (1996), is in
fact also an optimal PAC learner. Bagging pre-dates Hanneke's algorithm by
twenty years and is taught in most undergraduate machine learning courses.
Moreover, we show that it only requires a logarithmic number of sub-samples to
reach optimality.
- Abstract（参考訳）: 実現可能な環境でのPAC学習の最適サンプル複雑性の決定は、数十年にわたって学習理論の中心的な問題であった。
最後に、Hanneke (2016) によるセミナルな研究は、証明可能な最適なサンプル複雑性を持つアルゴリズムを与えた。
彼のアルゴリズムは、トレーニングデータの慎重に構造化されたサブサンプリングに基づいており、各サブサンプルでトレーニングされた仮説の過半数を返却する。
非常にエキサイティングな理論的な結果であるが、訓練データのサブサンプルの多項式数(各線形サイズ)を構成するため、非効率性のために実際にはあまり影響を与えていない。
本稿では,Breimann (1996) による実用的,古典的ヒューリスティック・バッグング(ブートストラップ・アグリゲーション)が,実際はPAC学習者として最適であることを示す。
バグングはhannekeのアルゴリズムを20年ほど前に発表し、ほとんどの学部の機械学習コースで教えられている。
さらに,最適性を得るためにはサブサンプルの対数しか必要としないことを示す。
関連論文リスト
- Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
我々は、異なる推論構成の最適な混合を見つけるアルゴリズムであるOSCAを提案する。
実験の結果,学習した混合アロケーションでは,最高の単一構成よりも精度がよいことがわかった。
OSCAはシングルターンタスク以外のエージェント処理にも有効であることが示されており、デフォルト設定よりも3倍少ない計算でSWE-Benchの精度が向上している。
論文 参考訳（メタデータ） (2024-10-29T19:17:55Z) - Majority-of-Three: The Simplest Optimal Learner? [17.87433808079955]
ハンネケのアルゴリズムは、多くのERM分類器の多数票を返すため、非常に複雑である。
このアルゴリズムは,その誤差に縛られた最適逆予測を実現する。
我々は、このアルゴリズムが実際に高い確率構造において最適であると推測する。
論文 参考訳（メタデータ） (2024-03-12T18:01:30Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳（メタデータ） (2022-05-12T14:40:18Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Provably Efficient Reward-Agnostic Navigation with Linear Value
Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。
そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文 参考訳（メタデータ） (2020-08-18T04:34:21Z) - Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。
本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。
我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
論文 参考訳（メタデータ） (2020-06-07T00:34:33Z) - Theory and Algorithms for Shapelet-based Multiple-Instance Learning [5.08418565337126]
本稿では,データ単位がバッグと呼ばれるインスタンスから構成されるMultiple-Instance Learning(MIL)の新たな定式化を提案する。
目標は、"shapelet"(またはパターン)との類似性に基づいて、バッグの優れた分類器を見つけることである。
私たちの定式化では、すべての可能なので、したがって無限に多くのシェイプレットを使い、よりリッチな分類器のクラスを生み出す。
論文 参考訳（メタデータ） (2020-05-31T17:10:59Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。