論文の概要: Uniform Computability of PAC Learning

• arxiv url: http://arxiv.org/abs/2601.18663v1
• Date: Mon, 26 Jan 2026 16:39:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:08.942302
• Title: Uniform Computability of PAC Learning
• Title（参考訳）: PAC学習における一様計算可能性
• Authors: Vasco Brattka, Guillaume Chirache,
• Abstract要約: Wehrauch複雑性を用いたPAC学習の計算可能性の均一性について検討した。 我々は,肯定的,否定的,あるいは完全な情報によって表される閉じた概念クラスに焦点を当てる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study uniform computability properties of PAC learning using Weihrauch complexity. We focus on closed concept classes, which are either represented by positive, by negative or by full information. Among other results, we prove that proper PAC learning from positive information is equivalent to the limit operation on Baire space, whereas improper PAC learning from positive information is closely related to Weak Kőnig's Lemma and even equivalent to it, when we have some negative information about the admissible hypotheses. If arbitrary hypotheses are allowed, then improper PAC learning from positive information is still in a finitary DNC range, which implies that it is non-deterministically computable, but does not allow for probabilistic algorithms. These results can also be seen as a classification of the degree of constructivity of the Fundamental Theorem of Statistical Learning. All the aforementioned results hold if an upper bound of the VC dimension is provided as an additional input information. We also study the question of how these results are affected if the VC dimension is not given, but only promised to be finite or if concept classes are represented by negative or full information. Finally, we also classify the complexity of the VC dimension operation itself, which is a problem that is of independent interest. For positive or full information it turns out to be equivalent to the binary sorting problem, for negative information it is equivalent to the jump of sorting. This classification allows also conclusions regarding the Borel complexity of PAC learnability.
• Abstract（参考訳）: Wehrauch複雑性を用いたPAC学習の計算可能性の均一性について検討した。 我々は,肯定的,否定的,あるいは完全な情報によって表される閉じた概念クラスに焦点を当てる。 その結果、正情報からの適切なPAC学習はベール空間上の極限演算と等価であることが証明され、一方、正情報からの不適切なPAC学習は、ウィーク・ケーニッヒのLemmaと密接に関連しており、許容可能な仮説に関する否定的な情報さえも持っている。 任意の仮説が許される場合、正の情報から不適切なPAC学習は、まだ有限のDNC範囲にあり、決定論的には計算できないが確率論的アルゴリズムを許さないことを意味する。 これらの結果は、統計的学習の基本理論の構成性の度合いの分類ともみなすことができる。 上記のすべての結果は、VC次元の上限が追加入力情報として提供される場合に保持される。 また、VC次元が与えられていない場合や、有限であることが約束されている場合、あるいは、概念クラスが否定的あるいは完全な情報で表される場合にのみ、これらの結果がどのように影響を受けるかについても検討する。 最後に、VC次元演算自体の複雑さも分類します。 正の情報や全情報については二進選別問題と同値であることが判明し、負の情報については選別の跳躍と同値であることが判明した。 この分類はまた、PAC学習可能性のボレル複雑性に関する結論を与える。

関連論文リスト

• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning [0.0]
  本稿では,計算可能な関数を必要とする計算可能学習(CPAC)について検討する。 最近の研究は計算可能条件下で基礎定理の類似性を回復した。
  論文  参考訳（メタデータ） (2025-11-04T15:12:38Z)
• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。 そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
  論文  参考訳（メタデータ） (2025-02-14T18:41:53Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  我々は、表現不足のバイアスによって破損したデータから学習する問題を考察する。 偏りのないデータの少ない場合、グループワイドのドロップアウト率を効率的に推定できることが示される。 本アルゴリズムは,有限VC次元のモデルクラスに対して,効率的な学習を可能にする。
  論文  参考訳（メタデータ） (2023-06-19T18:25:44Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。 まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。 第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
  論文  参考訳（メタデータ） (2023-02-06T02:52:36Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• Adversarially Robust PAC Learnability of Real-Valued Functions [19.54399554114989]
  脂肪散乱次元のクラスは $ell_p$ 摂動条件で学習可能であることを示す。 そこで本研究では,実関数に対する非依存的な新しいサンプルスキームを提案する。
  論文  参考訳（メタデータ） (2022-06-26T21:27:23Z)
• 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)
• A Theory of Usable Information Under Computational Constraints [103.5901638681034]
  本稿では,複雑なシステムにおける情報推論のための新しいフレームワークを提案する。 我々の基礎はシャノンの情報理論の変分拡張に基づいている。 計算制約を組み込むことで,データから$mathcalV$-informationを確実に推定できることを示す。
  論文  参考訳（メタデータ） (2020-02-25T06:09:30Z)

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

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