論文の概要: Do PAC-Learners Learn the Marginal Distribution?

• arxiv url: http://arxiv.org/abs/2302.06285v1
• Date: Mon, 13 Feb 2023 11:42:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-14 15:47:15.200597
• Title: Do PAC-Learners Learn the Marginal Distribution?
• Title（参考訳）: PAC-Learnerは配偶者の分布を学習しているか?
• Authors: Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
• Abstract要約: 我々はPAC-Learningの変種について検討し、この変種は敵が既知の限界分布の族に制限される。 テレビ学習はPAC学習と等価であることを示す。
• 参考スコア（独自算出の注目度）: 24.80812483480747
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a foundational variant of Valiant and Vapnik and Chervonenkis' Probably Approximately Correct (PAC)-Learning in which the adversary is restricted to a known family of marginal distributions $\mathscr{P}$. In particular, we study how the PAC-learnability of a triple $(\mathscr{P},X,H)$ relates to the learners ability to infer \emph{distributional} information about the adversary's choice of $D \in \mathscr{P}$. To this end, we introduce the `unsupervised' notion of \emph{TV-Learning}, which, given a class $(\mathscr{P},X,H)$, asks the learner to approximate $D$ from unlabeled samples with respect to a natural class-conditional total variation metric. In the classical distribution-free setting, we show that TV-learning is \emph{equivalent} to PAC-Learning: in other words, any learner must infer near-maximal information about $D$. On the other hand, we show this characterization breaks down for general $\mathscr{P}$, where PAC-Learning is strictly sandwiched between two approximate variants we call `Strong' and `Weak' TV-learning, roughly corresponding to unsupervised learners that estimate most relevant distances in $D$ with respect to $H$, but differ in whether the learner \emph{knows} the set of well-estimated events. Finally, we observe that TV-learning is in fact equivalent to the classical notion of \emph{uniform estimation}, and thereby give a strong refutation of the uniform convergence paradigm in supervised learning.
• Abstract（参考訳）: 本稿では,Valiant と Vapnik と Chervonenkis' Probably Aough Correct (PAC)-Learning の基本的な変種について検討する。 特に、3倍の $(\mathscr{p},x,h)$ のpac-learnability が、敵の$d \in \mathscr{p}$ の選択に関する \emph{distributional} 情報を推測する学習者能力とどのように関係しているかを考察する。 この目的のために、"unsupervised" の概念である \emph{tv-learning} を導入し、クラス $(\mathscr{p},x,h)$ が与えられたとき、学習者に、自然なクラス条件の全変動メトリックに関してラベルなしサンプルから$d$を近似するよう求める。 古典的な配布のない環境では、テレビラーニングはパックラーニングと同値であることを示す: つまり、どんな学習者も$d$の最大値に近い情報を推測しなければならない。 一方、この特徴は一般に$\mathscr{P}$に対して分解され、PAC-Learningは「Strong」と「Weak」テレビ学習と呼ばれる2つの近似変種に厳密に挟まれており、大まかに言えば、$D$の最も関連する距離を$H$に対して推定する教師なし学習者に対応するが、学習者 \emph{knows} がよく推定された事象の集合であるかどうかが異なる。 最後に,テレビ学習は古典的な概念である 'emph{uniform Estimation} と等価であり,教師付き学習における一様収束パラダイムの強い反感を与える。

関連論文リスト

• On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning [57.18649648182171]
  我々は、MI-PLLの文脈において、これまで研究されていない問題に対処するためのコントリビューションを行っている。 最小限の仮定をしながら、クラス固有のMI-PLLのリスク境界を導出する。 我々の理論は、$sigma$が学習の不均衡に大きな影響を及ぼすというユニークな現象を明らかにしている。
  論文  参考訳（メタデータ） (2024-07-13T20:56:34Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss [33.18537822803389]
  L2$ と $Psi_p$ の位相が我々の仮説クラス $mathscrF$, $mathscrF$ に同値であるときにいつでも、$mathscrF$ は弱準ガウス類であることを示す。 以上の結果から, 混合への直接的な依存は高次項に還元されるため, この問題は実現可能か否かを判断できる。
  論文  参考訳（メタデータ） (2024-02-08T18:57:42Z)
• The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
  マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。 本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
  論文  参考訳（メタデータ） (2023-07-22T18:02:53Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。 注目すべきは,上界が決定論的学習者によって達成できることである。
  論文  参考訳（メタデータ） (2022-10-06T06:49:48Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
  ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。 我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
  論文  参考訳（メタデータ） (2021-04-19T16:35:38Z)
• On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms [10.66048003460524]
  構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
  論文  参考訳（メタデータ） (2021-02-11T21:28:55Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning [39.51923275855131]
  非ロマンスな学習者を用いて、仮説クラスを頑健に学習できる還元を与える。 $mathcalA$への呼び出しの数は、例ごとに許容される逆の摂動の数に対数的に依存する。
  論文  参考訳（メタデータ） (2020-10-22T20:28:35Z)

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

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