論文の概要: A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
- arxiv url: http://arxiv.org/abs/2608.30246v1
- Date: Mon, 31 Aug 2026 04:56:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.235933
- Title: A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
- Title（参考訳）: 非PAC学習者によるZFCにおけるVC次元のボレル概念クラス
- Abstract要約: 統計的学習の基本的な定理は、適切な可測性仮定の下では、有限Vapnik--Chervonenkis(VC)次元は全ての適切な一貫した学習規則がほぼ正しい(PAC)ことを保証している。
集合論的な仮定を余分に必要とせず、基本定理における追加の正則性仮定は一般に省略できないことを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on $[0,1]$ of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.
- Abstract（参考訳）: 統計的学習の基本的な定理は、適切な可測性仮定の下では、有限Vapnik--Chervonenkis(VC)次元は全ての適切な一貫した学習規則がほぼ正しいことを保証している。
Blumer, Ehrenfeucht, Haussler, Warmuth は連続的仮説を仮定して、概念クラスの「幸福」条件は省略できないことを示した。
連続的仮説は不要であることを示す。
Zermelo--Fraenkel 集合論と Axiom of Choice (ZFC) だけで研究し、VC次元 1 の$[0,1] のボレル集合の概念クラスを構築し、PAC ではない適切な一貫した学習規則を構築する。
より正確には、適切なボレル確率測度と目標概念に対して、この規則は、外的確率測度の標本の集合上で、サンプルサイズ毎に真のリスクを負う。
したがって、有限VC次元と個々の概念のボレル可測性は、すべての適切な一貫した学習規則がPACであることを保証するのに十分ではない。
この結果は、余分な集合論的な仮定を必要とせず、基本定理における追加の正則性仮定は一般に省略できないことを示している。
関連論文リスト
- Strategic PAC Learnability via Geometric Definability [69.34283267701421]
戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。
中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。
仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。
難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
論文 参考訳（メタデータ） (2026-05-13T12:21:56Z) - Null Measurability at the Symmetrization Interface in VC Learning [0.15229257192293197]
近年の統計学習の基本的な定理における可測性の再検討は、ゴーストギャップ上のボレル可測性を課している。
標準対称性証明で実際に使用されている片側ゴーストギャップインタフェースでは、この要件は必要以上に強くなっていることを示す。
結果は、有限VCからPAC学習可能性への対称性化経路に必要な測定可能性仮説を弱める。
論文 参考訳（メタデータ） (2026-04-27T22:10:34Z) - Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。
一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。
一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
論文 参考訳（メタデータ） (2026-02-24T06:15:59Z) - Reconstruction of finite Quasi-Probability and Probability from Principles: The Role of Syntactic Locality [0.0]
準確率は物理学の様々な分野に分布するが、その概念的基礎は未だ不明である。
構造的整合性要件から準確率とその条件計算を導出する原理的枠組みを開発する。
論文 参考訳（メタデータ） (2026-02-12T19:00:08Z) - Learning Conditional Averages [52.361762722359366]
本稿では,PACフレームワークにおける条件平均学習の問題を紹介する。
ターゲットのコンセプトそのものを学ぶのではなく、各インスタンスの平均ラベルをその周辺で予測することが目標だ。
より一般的には、PAC学習をいくつかのドメインで発生する学習タスクをキャプチャする設定に拡張する。
論文 参考訳（メタデータ） (2026-02-12T13:20:29Z) - Partial Feedback Online Learning [88.27143767009376]
我々は、偏見フィードバックオンライン学習と呼ばれる新しい学習プロトコルについて研究する。
各インスタンスは許容できるラベルのセットを許可するが、学習者は1ラウンドごとに許容できるラベルを1つだけ観察する。
論文 参考訳（メタデータ） (2026-01-29T09:39:11Z) - Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning [0.0]
本稿では,計算可能な関数を必要とする計算可能学習(CPAC)について検討する。
最近の研究は計算可能条件下で基礎定理の類似性を回復した。
論文 参考訳（メタデータ） (2025-11-04T15:12:38Z) - Measurability in the Fundamental Theorem of Statistical Learning [0.0]
統計的学習の基本定理は、仮説空間がPAC学習可能であることと、そのVC次元が有限であることは同値である。
本稿では、実数 O-極小展開上で定義された仮説空間のPAC学習可能性について十分な条件を示す。
この仮説空間のクラスは、ReLUやシグモイド関数のようなよく用いられる活性化関数を使用する二項分類のためのすべての人工ニューラルネットワークをカバーする。
論文 参考訳（メタデータ） (2024-10-14T08:03:06Z) - Fat Shattering, Joint Measurability, and PAC Learnability of POVM
Hypothesis Classes [8.594140167290098]
我々は、PAC学習性に必要な条件と十分な条件を整合させることにより、量子測定クラスの学習可能性を特徴づける。
有限次元POVMクラスであっても、前処理におけるVC次元の一般化上界は、しばしば無限大であることが示される。
有限次元ヒルベルト空間上で定義されるすべての測定クラスがPAC学習可能であることを示す。
論文 参考訳（メタデータ） (2023-08-21T18:38:24Z) - Do PAC-Learners Learn the Marginal Distribution? [19.54058590042626]
PAC Learning の基本定理は、概念クラス $H$ の学習可能性は$H$ における経験的エラーの $textituniform convergence$ と等価であると主張している。
この研究は、PAC学習、一様収束、分布自由設定を超えた密度推定の関連を再考する。
論文 参考訳（メタデータ） (2023-02-13T11:42:58Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳（メタデータ） (2022-12-08T11:57:30Z) - Unifying different notions of quantum incompatibility into a strict
hierarchy of resource theories of communication [60.18814584837969]
我々は、POVM、チャネル、機器の非互換性の異なる概念を統一するq-compatibilityの概念を導入する。
我々は、情報理論資源の観点から、各非互換性の概念が何を構成しているかを正確に特定することができる。
論文 参考訳（メタデータ） (2022-11-16T21:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。