論文の概要: Boosting Simple Learners

• arxiv url: http://arxiv.org/abs/2001.11704v8
• Date: Fri, 16 Jun 2023 14:06:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-19 18:42:59.211655
• Title: Boosting Simple Learners
• Title（参考訳）: 簡単な学習者を増やす
• Authors: Noga Alon and Alon Gonen and Elad Hazan and Shay Moran
• Abstract要約: i) 複雑さ: 正確な仮説を生成するために弱い仮説がいくつ必要か? 我々は、Freund and Schapireによる古典的下界を回避できる新しいブースティングアルゴリズムを設計する('95, '12)。 半空間と決定切り株を含む、よく研究された論理クラスに対する2つ目の質問に対する肯定的な回答を提供する。
• 参考スコア（独自算出の注目度）: 45.09968166110557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are "rules-of-thumbs" from an "easy-to-learn class". (Schapire and Freund~'12, Shalev-Shwartz and Ben-David '14.) Formally, we assume the class of weak hypotheses has a bounded VC dimension. We focus on two main questions: (i) Oracle Complexity: How many weak hypotheses are needed to produce an accurate hypothesis? We design a novel boosting algorithm and demonstrate that it circumvents a classical lower bound by Freund and Schapire ('95, '12). Whereas the lower bound shows that $\Omega({1}/{\gamma^2})$ weak hypotheses with $\gamma$-margin are sometimes necessary, our new method requires only $\tilde{O}({1}/{\gamma})$ weak hypothesis, provided that they belong to a class of bounded VC dimension. Unlike previous boosting algorithms which aggregate the weak hypotheses by majority votes, the new boosting algorithm uses more complex ("deeper") aggregation rules. We complement this result by showing that complex aggregation rules are in fact necessary to circumvent the aforementioned lower bound. (ii) Expressivity: Which tasks can be learned by boosting weak hypotheses from a bounded VC class? Can complex concepts that are "far away" from the class be learned? Towards answering the first question we {introduce combinatorial-geometric parameters which capture expressivity in boosting.} As a corollary we provide an affirmative answer to the second question for well-studied classes, including half-spaces and decision stumps. Along the way, we establish and exploit connections with Discrepancy Theory.
• Abstract（参考訳）: boostingは、弱い仮説と中程度の不正確な仮説を強力で正確な仮説に組み合わせるという、有名な機械学習アプローチである。 弱仮説が有界キャパシティのクラスに属するという仮定の下での強化について検討する。 この仮定は、弱い仮説は「容易に理解できるクラス」からの「反則」であるという一般的な慣例に触発されている。 (Schapire and Freund~'12, Shalev-Shwartz and Ben-David '14) 形式的には、弱仮説のクラスはVC次元が有界であると仮定する。 主に2つの質問に焦点を合わせます (i)Oracle Complexity: 正確な仮説を生成するには、弱い仮説がいくつ必要か? 我々は,新しいブースティングアルゴリズムを設計し,freund と schapire ('95, '12) による古典下限を回避できることを実証する。 下界は、$\Omega({1}/{\gamma^2})=弱仮説と$\gamma$-marginが時々必要であることを示しているが、新しい手法では、それらが有界VC次元のクラスに属することを条件として、$\tilde{O}({1}/{\gamma})$弱仮説のみを必要とする。 多数決で弱い仮説を集約する以前のブースティングアルゴリズムとは異なり、新しいブースティングアルゴリズムはより複雑な(より深い)集約ルールを使用する。 我々は、上記の下限を回避するために、複雑な集約ルールが実際に必要であることを示すことによって、この結果を補完する。 (ii)表現性: 限定されたvcクラスから弱い仮説を取り入れることで、どのタスクを学習できるのか? クラスから"遠い"複雑な概念を学ぶことができるだろうか? 最初の質問に答えるには, ブースティングの表現率を捉えたコンビネータ・ジオメトリパラメーターを導入する。 半空間と決定の切り株を含む、よく研究されたクラスに対する2つ目の質問に対する肯定的な答えを提供する。 その過程で、離散性理論とのつながりを確立し、活用する。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
  また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。 具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
  論文  参考訳（メタデータ） (2023-11-02T21:10:16Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。 本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
  論文  参考訳（メタデータ） (2023-07-02T19:26:58Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• The Optimal Choice of Hypothesis Is the Weakest, Not the Shortest [0.0]
  1つの戦略は、情報を圧縮する能力と一般化する能力とを同一に、最も短いものを選択することである。 圧縮は性能を最大化するのに必要でも十分でもないことを示す。 これは弱点がはるかに優れたプロキシであることを示し、DeepmindのApperception Engineが効果的に一般化できる理由を説明しています。
  論文  参考訳（メタデータ） (2023-01-30T15:29:40Z)
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes [5.194264506657145]
  比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。 たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。 比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
  論文  参考訳（メタデータ） (2022-11-16T18:38:24Z)
• Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap [64.60460828425502]
  コントラスト学習の下流性能に関する新たな保証を提案する。 我々の新しい理論は、攻撃的なデータ強化の下で、異なるクラス内サンプルのサポートがより重なり合うという知見に基づいている。 本稿では、下流の精度とよく一致した教師なしモデル選択距離ARCを提案する。
  論文  参考訳（メタデータ） (2022-03-25T05:36:26Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。