論文の概要: Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

• arxiv url: http://arxiv.org/abs/2511.02644v1
• Date: Tue, 04 Nov 2025 15:12:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:06.086024
• Title: Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
• Title（参考訳）: 統計的学習の基本理論の帰納的可表現クラスと計算可能バージョン
• Authors: David Kattermann, Lothar Sebastian Krapp,
• Abstract要約: 本稿では,計算可能な関数を必要とする計算可能学習(CPAC)について検討する。 最近の研究は計算可能条件下で基礎定理の類似性を回復した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Statistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Fundamental Theorem in the computable setting, for instance by introducing an effective VC-dimension. Guided by this, we investigate the connection between CPAC learning and recursively enumerable representable (RER) classes, whose members can be algorithmically listed. Our results show that the effective VC-dimensions can take arbitrary values above the traditional one, even for RER classes, which creates a whole family of (non-)examples for various notions of CPAC learning. Yet the two dimensions coincide for classes satisfying sufficiently strong notions of CPAC learning. We then observe that CPAC learnability can also be characterized via containment of RER classes that realize the same samples. Furthermore, it is shown that CPAC learnable classes satisfying a unique identification property are necessarily RER. Finally, we establish that agnostic learnability can be guaranteed for RER classes, by considering the relaxed notion of nonuniform CPAC learning.
• Abstract（参考訳）: 本稿では,計算可能な関数を必要とする計算可能学習(CPAC)について検討する。 Vapnik-Chervonenkis (VC-) 次元の有限性によってPAC学習可能性を特徴づける統計的学習の基本理論は、もはやこの枠組みにはないことがこれまで見受けられてきた。 最近の研究は、例えば有効なVC次元を導入することで、計算可能な設定で基礎定理の類似性を回復した。 本稿では,CPAC学習と再帰的可算表現性(RER)クラスとの関係について検討する。 以上の結果から,実効的なVC次元は従来の値よりも任意の値を取ることが可能であることが示唆された。 しかし、この2つの次元はCPAC学習の十分強い概念を満たすクラスに一致する。 次に、CPAC学習性は、同じサンプルを実現するRERクラスを包含することでも特徴付けられることを観察する。 さらに、ユニークな識別特性を満たすCPAC学習可能なクラスは、必然的にRERであることが示されている。 最後に、非一様CPAC学習の概念を緩和することにより、RERクラスに対して不可知学習性を保証することを確立する。

関連論文リスト

• A packing lemma for VCN${}_k$-dimension and learning high-dimensional data [1.6114012813668932]
  本研究では,非認識型高アリティPAC学習性は,Husslerパッケージ特性の高アリティバージョンを意味することを示す。 これは古典的なPAC学習性は古典的なハウスラーパッキング特性を意味するという直接的な証明を得ることによってなされる。
  論文  参考訳（メタデータ） (2025-05-21T16:03:12Z)
• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  我々はPAC学習の枠組みの下で対照的な学習について研究する。 本稿では,線形表現の基本概念の対照的な学習について考察する。 我々は,Rademacherの複雑性に基づいた保証を確立し,それとPACの保証を,ある対照的な大マルジン条件下で接続する。
  論文  参考訳（メタデータ） (2025-02-21T21:51:01Z)
• On the Computability of Multiclass PAC Learning [9.507869508188266]
  最近導入された計算可能PAC(CPAC)学習フレームワークでは、学習者と出力する関数の両方が計算可能であることが求められている。 識別器の計算可能次元がCPAC学習を特徴付けることを示す。
  論文  参考訳（メタデータ） (2025-02-10T01:07:23Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
  論文  参考訳（メタデータ） (2023-07-07T21:39:25Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。 本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
  論文  参考訳（メタデータ） (2023-07-02T19:26:58Z)
• Using Representation Expressiveness and Learnability to Evaluate Self-Supervised Learning Methods [61.49061000562676]
  本稿では,学習可能性を評価するためにCluster Learnability (CL)を導入する。 CLは、K-meansで表現をクラスタリングすることによって得られたラベルを予測するために訓練されたKNNのパフォーマンスで測定される。 CLは、他の競合する評価手法よりも分布内モデルの性能と相関することがわかった。
  論文  参考訳（メタデータ） (2022-06-02T19:05:13Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• On computable learning of continuous features [2.278415626131568]
  計算可能距離空間上の二項分類のための計算可能PAC学習の定義を導入する。 また、計算可能なサンプル関数を持つ適切なPAC学習者を認めない仮説クラスを提示する。
  論文  参考訳（メタデータ） (2021-11-24T02:28:21Z)

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

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