論文の概要: What is Learnable in Valiant's Theory of the Learnable?

• arxiv url: http://arxiv.org/abs/2605.13840v1
• Date: Wed, 13 May 2026 17:58:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:28.227025
• Title: What is Learnable in Valiant's Theory of the Learnable?
• Title（参考訳）: Valiant's Theory of the Learnableに学ぶべきこと
• Authors: Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis,
• Abstract要約: ヴァリアントの1984年の論文は、PAC学習モデルを導入したと広く信じられている。 PAC学習とは異なり、学習者は正のみを受け取り、メンバーシップクエリを発行し、偽陽性のない仮説を出力しなければならない。 クラスが学習可能であることと,ポリサイズ適応型クエリ圧縮方式により,すべての正サンプルが証明可能であることを示す。
• 参考スコア（独自算出の注目度）: 43.09148757729053
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: *Which classes are learnable in it?* For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that $d$-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a $\mathrm{poly}(d) \tilde{O}(1/ε)$ sample and $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ query algorithm, and prove that at least $Ω(d)$ samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.
• Abstract（参考訳）: ヴァリアントの1984年の論文は、PAC学習モデルを導入したと広く信じられているが、実際には、PAC学習とは異なり、学習者は正のみを受け取り、メンバーシップクエリを発行し、偽陽性のない仮説を出力しなければならない。 以前の作業では、クエリなしのケースを含む、バリエーションが特徴だった。 Valiant氏のオリジナルのモデルを再検討し、次のように尋ねる。 * Valiant の Boolean-hypercube 設定を含むすべての有限領域に対して、クラスが学習可能であること、そしてすべての実数可能な正のサンプルがポリサイズ適応的なクエリ圧縮スキームで証明可能であることを示せる。 これは新しいサンプル圧縮の変種であり、学習者はメンバーシップオラクルとの短い相互作用を通じてサンプルを認証する。 我々の特徴は、Valiantモデルにおける学習容易性は、PACモデルにおける学習容易性と、メンバーシップクエリを含まないValiantモデルの変種との間に厳密に挟み合っていることを示している。 これは、メンバシップクエリを導入することで、サンプルや計算の複雑さだけでなく、学習可能なクラスのセットを変更する、まれなケースの1つです。 次に,モデルから任意の領域への自然な拡張について検討する。 正確なキャラクタリゼーションは得られないが、我々の手法は容易に一般化し、同じ厳密なサンドイッチが持続することを示す。 最後に、クエリなしでは学習できない$d$次元のハーフスペースがクエリーで学習可能であることを示す: $\mathrm{poly}(d) \tilde{O}(1/ε)$ sampleと$\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ query algorithmを与え、少なくとも$Ω(d)$ sampleやクエリーが必要であることを証明する。 我々の知る限り、これはヴァリアントのモデルにおけるハーフスペースに対する最初のアルゴリズムである。 これらの結果は、ヴァリアントの学習可能性の概念の背後にある驚くほど豊かな理論を明らかにし、学習理論に独立した関心を持つかもしれないアイデアを紹介した。

関連論文リスト

• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。 この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。 この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
  論文  参考訳（メタデータ） (2026-05-10T14:28:05Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• Refereed Learning [4.024083217094761]
  提案手法では,精度のレベルが同等のコストで得られるものよりもはるかに高い参照学習プロトコルを示す。 for all $varepsilon>0$ and ambient dimension $d$, our learner makes only one query to the ground truth function。 学習者は,まず,効率よくサンプリングできない分布から,プローバーを用いて,学習者がサンプルを採取できる技術を開発した。
  論文  参考訳（メタデータ） (2025-10-06T23:07:31Z)
• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。 そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
  論文  参考訳（メタデータ） (2025-02-14T18:41:53Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Distributional PAC-Learning from Nisan's Natural Proofs [0.0]
  Lambda-circuitsを学習するために、$Lambdaの回路境界の自然な証明は効率的なアルゴリズムを暗示する。 我々は、この意味を$Lambda notsupseteq AC0[p]$、ランダムな例のみを用いて任意の例分布を学習する学習アルゴリズムに一般化できるかどうか検討する。
  論文  参考訳（メタデータ） (2023-10-05T16:13:29Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• 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)

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

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