論文の概要: Computable learning of natural hypothesis classes
- arxiv url: http://arxiv.org/abs/2407.16663v1
- Date: Tue, 23 Jul 2024 17:26:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 16:26:03.306366
- Title: Computable learning of natural hypothesis classes
- Title（参考訳）: 自然仮説クラスの計算可能学習
- Authors: Matthew Harrison-Trainor, Syed Akbari,
- Abstract要約: 最近、PACが学習可能であるが、計算可能でない仮説クラスが与えられた。
計算可能性理論のon-a-cone 機械を用いて、仮説クラスが計算可能リスト化可能であるような軽微な仮定の下では、学習可能な自然仮説クラスは計算可能リスト化可能であることを証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper is about the recent notion of computably probably approximately correct learning, which lies between the statistical learning theory where there is no computational requirement on the learner and efficient PAC where the learner must be polynomially bounded. Examples have recently been given of hypothesis classes which are PAC learnable but not computably PAC learnable, but these hypothesis classes are unnatural or non-canonical in the sense that they depend on a numbering of proofs, formulas, or programs. We use the on-a-cone machinery from computability theory to prove that, under mild assumptions such as that the hypothesis class can be computably listable, any natural hypothesis class which is learnable must be computably learnable. Thus the counterexamples given previously are necessarily unnatural.
- Abstract（参考訳）: 本稿では,学習者に対する計算的要求が存在しない統計的学習理論と,学習者が多項式的に有界でなければならない効率的なPACとの間にある,計算学的にほぼ正しい学習の概念について述べる。
PACを学習できるが計算可能なPACを学習できない仮説クラスが最近与えられたが、これらの仮説クラスは証明、公式、プログラムの数に依存するという意味で非自然あるいは非正則である。
計算可能性理論のon-a-cone 機械を用いて、仮説クラスが計算可能リスト化可能であるような軽微な仮定の下では、学習可能な自然仮説クラスは計算可能リスト化可能であることを証明する。
したがって、以前に与えられた反例は必ずしも非自然である。
関連論文リスト
- Credal Learning Theory [4.64390130376307]
我々は,データ生成分布の変動をモデル化するために,凸集合の確率を用いて,不規則な学習理論の基礎を定めている。
境界は、古典的な結果を直接一般化する有限仮説空間と無限モデル空間の場合に導かれる。
論文 参考訳（メタデータ） (2024-02-01T19:25:58Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。
本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
論文 参考訳（メタデータ） (2023-07-02T19:26:58Z) - 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) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - A Theory of PAC Learnability of Partial Concept Classes [30.772106555607458]
我々は、多種多様な学習タスクをモデル化できるように、PAC学習理論を拡張した。
部分概念クラスのPAC学習性を特徴付け,古典的クラスと根本的に異なるアルゴリズム的ランドスケープを明らかにする。
論文 参考訳（メタデータ） (2021-07-18T13:29:26Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳（メタデータ） (2020-11-04T10:25:13Z) - Empirically Verifying Hypotheses Using Reinforcement Learning [58.09414653169534]
本稿では,仮説検証をRL問題として定式化する。
我々は、世界の力学に関する仮説を前提として、仮説が真か偽かを予測するのに役立つ観測結果を生成することができるエージェントを構築することを目指している。
論文 参考訳（メタデータ） (2020-06-29T01:01:10Z) - L2R2: Leveraging Ranking for Abductive Reasoning [65.40375542988416]
学習システムの帰納的推論能力を評価するために,帰納的自然言語推論タスク(alpha$NLI)を提案する。
新たな$L2R2$アプローチは、Learning-to-rankフレームワークの下で提案されている。
ARTデータセットの実験は、公開リーダボードの最先端に到達します。
論文 参考訳（メタデータ） (2020-05-22T15:01:23Z) - Learning programs by learning from failures [26.955785230358963]
本稿では,障害からの学習という,帰納的論理プログラミング(ILP)アプローチについて述べる。
このアプローチでは、ILPシステムは学習問題を3つの段階(生成、テスト、制約)に分解する。
本稿では,回答セットプログラミングとPrologを組み合わせることで,この手法を実現するILPシステムであるPopperを紹介する。
論文 参考訳（メタデータ） (2020-05-05T14:55:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。