論文の概要: Understanding Aggregations of Proper Learners in Multiclass Classification
- arxiv url: http://arxiv.org/abs/2410.22749v1
- Date: Wed, 30 Oct 2024 07:12:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-31 14:24:11.528383
- Title: Understanding Aggregations of Proper Learners in Multiclass Classification
- Title（参考訳）: 多クラス分類における適切な学習者の集団化の理解
- Authors: Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas,
- Abstract要約: マルチクラスの学習性は、適切な障壁を示すことが知られている。
二項分類の最近の進歩は、適切な学習者の集合を用いて、この要件を満たすことを実証している。
1つのERMが$Omega left(fracd_G ln (1 / delta)epsilonright)$サンプルを必要とすることを示す。
- 参考スコア（独自算出の注目度）: 4.422219522591412
- License:
- Abstract: Multiclass learnability is known to exhibit a properness barrier: there are learnable classes which cannot be learned by any proper learner. Binary classification faces no such barrier for learnability, but a similar one for optimal learning, which can in general only be achieved by improper learners. Fortunately, recent advances in binary classification have demonstrated that this requirement can be satisfied using aggregations of proper learners, some of which are strikingly simple. This raises a natural question: to what extent can simple aggregations of proper learners overcome the properness barrier in multiclass classification? We give a positive answer to this question for classes which have finite Graph dimension, $d_G$. Namely, we demonstrate that the optimal binary learners of Hanneke, Larsen, and Aden-Ali et al. (appropriately generalized to the multiclass setting) achieve sample complexity $O\left(\frac{d_G + \ln(1 / \delta)}{\epsilon}\right)$. This forms a strict improvement upon the sample complexity of ERM. We complement this with a lower bound demonstrating that for certain classes of Graph dimension $d_G$, majorities of ERM learners require $\Omega \left( \frac{d_G + \ln(1 / \delta)}{\epsilon}\right)$ samples. Furthermore, we show that a single ERM requires $\Omega \left(\frac{d_G \ln(1 / \epsilon) + \ln(1 / \delta)}{\epsilon}\right)$ samples on such classes, exceeding the lower bound of Daniely et al. (2015) by a factor of $\ln(1 / \epsilon)$. For multiclass learning in full generality -- i.e., for classes of finite DS dimension but possibly infinite Graph dimension -- we give a strong refutation to these learning strategies, by exhibiting a learnable class which cannot be learned to constant error by any aggregation of a finite number of proper learners.
- Abstract（参考訳）: 多クラス学習性は、適切な学習者によって学べない学習可能なクラスが存在するという、適切な障壁を示すことが知られている。
バイナリ分類は、学習容易性にはそのような障壁はないが、最適学習には同様の障壁があり、一般には不適切な学習者によってのみ達成できる。
幸いなことに、近年のバイナリ分類の進歩は、この要件が適切な学習者の集合を用いて満足できることを示しており、その一部は驚くほど単純である。
適切な学習者の単純なアグリゲーションが、マルチクラス分類における適切な障壁をどの程度克服できるのか?
有限グラフ次元を持つクラスに対して、この質問に対する正の答えを$d_G$とする。
すなわち、Hanneke, Larsen, and Aden-Ali et al の最適二進学習者がサンプル複雑性を$O\left(\frac{d_G + \ln(1 / \delta)}{\epsilon}\right)$とすることを示した。
これにより、ERMのサンプル複雑性が厳格に改善される。
グラフ次元$d_G$のある種のクラスでは、EMM学習者の多数派は$\Omega \left( \frac{d_G + \ln(1 / \delta)}{\epsilon}\right)$サンプルを必要とする。
さらに、単一のERMは$\Omega \left(\frac{d_G \ln(1 / \epsilon) + \ln(1 / \delta)}{\epsilon}\right)$そのようなクラス上のサンプルを必要とし、$\ln(1 / \epsilon)$ の係数で Daniely et al (2015) の下限を超える。
完全一般性の多クラス学習(つまり、有限DS次元のクラスでは無限グラフ次元のクラスの場合)については、有限個の固有学習者の集合によって一定の誤りに学習できない学習可能なクラスを示すことによって、これらの学習戦略に強い反感を与える。
関連論文リスト
- Self-Directed Learning of Convex Labelings on Graphs [11.286983359775512]
本研究では,自己指向型学習システムにおいて,与えられたグラフのクラスタを学習する問題について検討する。
グラフ上の自己指向ノード分類に関して、これまでは成果は存在しなかった。
論文 参考訳（メタデータ） (2024-09-02T19:13:26Z) - Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
アンサンブル学習(英: Ensemble learning)は、弱い学習者を利用して強力な学習者を生み出す方法である。
我々は、マージンの概念を活かした滑らかで凸な目的関数を設計し、強力な学習者がより差別的になるようにした。
そして、我々のアルゴリズムを、多数のデータセットの10倍の大きさのランダムな森林や他の古典的な手法と比較する。
論文 参考訳（メタデータ） (2024-08-06T03:42:38Z) - Efficient Algorithms for Learning Monophonic Halfspaces in Graphs [7.619404259039284]
我々は、教師付き、オンライン、アクティブな設定において、モノフォニックなハーフスペースを学習するためのいくつかの新しい結果を証明した。
我々の主な結果は、モノフォニック半空間は、n = |V(G)|$ の時間において、ほぼ最適に複雑に学習できるということである。
また、概念クラスは遅延$operatornamepoly(n)$で列挙でき、経験的リスクは2ω(G)operatornamepoly(n)$で実行可能であることも示します。
論文 参考訳（メタデータ） (2024-05-01T20:34:12Z) - The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。
PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。
本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
論文 参考訳（メタデータ） (2023-07-22T18:02:53Z) - Agnostic Multi-Group Active Learning [24.97598179536084]
能動的学習の観点から,この問題の変種を考察し,学習者がコレクションの各分布からどの例をラベル付けするかを判断する権限を付与する。
我々の主な課題は、不一致に基づくアクティブラーニングのような標準的なアクティブラーニング技術が、マルチグループラーニングの目的に直接適用されないことである。
既存のアルゴリズムを改良し、多群学習の非依存的な定式化のための一貫した能動的学習アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-06-02T21:24:13Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Classification Under Misspecification: Halfspaces, Generalized Linear
Models, and Connections to Evolvability [39.01599245403753]
特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。
我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。
また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
論文 参考訳（メタデータ） (2020-06-08T17:59:11Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z) - Backward Feature Correction: How Deep Learning Performs Deep
(Hierarchical) Learning [66.05472746340142]
本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。
我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
論文 参考訳（メタデータ） (2020-01-13T17:28:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。