論文の概要: A Parameterized Theory of PAC Learning
- arxiv url: http://arxiv.org/abs/2304.14058v1
- Date: Thu, 27 Apr 2023 09:39:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-28 13:58:27.597006
- Title: A Parameterized Theory of PAC Learning
- Title（参考訳）: PAC学習のパラメータ化理論
- Authors: Cornelius Brand, Robert Ganian, Kirill Simonov
- Abstract要約: おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。
我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
- 参考スコア（独自算出の注目度）: 19.686465068713467
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Probably Approximately Correct (i.e., PAC) learning is a core concept of
sample complexity theory, and efficient PAC learnability is often seen as a
natural counterpart to the class P in classical computational complexity. But
while the nascent theory of parameterized complexity has allowed us to push
beyond the P-NP ``dichotomy'' in classical computational complexity and
identify the exact boundaries of tractability for numerous problems, there is
no analogue in the domain of sample complexity that could push beyond efficient
PAC learnability.
As our core contribution, we fill this gap by developing a theory of
parameterized PAC learning which allows us to shed new light on several recent
PAC learning results that incorporated elements of parameterized complexity.
Within the theory, we identify not one but two notions of fixed-parameter
learnability that both form distinct counterparts to the class FPT -- the core
concept at the center of the parameterized complexity paradigm -- and develop
the machinery required to exclude fixed-parameter learnability. We then
showcase the applications of this theory to identify refined boundaries of
tractability for CNF and DNF learning as well as for a range of learning
problems on graphs.
- Abstract（参考訳）: おそらくおよそ正しい(すなわち、PAC学習は標本複雑性理論の中核概念であり、PAC学習性は古典的な計算複雑性においてクラスPと自然に相反するものとしてしばしば見なされる。
しかし、パラメータ化複雑性の初期の理論により、古典的な計算複雑性におけるP-NP ``dichotomy'' を超えて、多くの問題に対するトラクタビリティの正確な境界を特定できるようになったが、効率的なPAC学習可能性を超えることができるサンプル複雑性の領域に類似性はない。
このギャップを埋めるために、パラメータ化されたPAC学習の理論を開発し、パラメータ化された複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができる。
この理論では、パラメータ化複雑性パラダイムの中心にあるFPTクラスと異なる相違点を形成する固定パラメータ学習性の概念を1つではなく2つ同定し、固定パラメータ学習性を排除するために必要な機械を開発する。
次に,CNF と DNF 学習におけるトラクタビリティの洗練された境界と,グラフ上での学習問題について,この理論の適用例を示す。
関連論文リスト
- Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
No-Free-Lunch(NFL)定理は、最適化プロセスに関係なく問題とデータ非依存の一般化誤差を定量化する。
我々は、様々な量子学習アルゴリズムを、特定の観測可能条件下で量子力学を学習するために設計された3つの学習プロトコルに分類する。
得られたNFL定理は, CLC-LP, ReQu-LP, Qu-LPにまたがるサンプルの複雑性を2次的に低減することを示した。
この性能差は、非直交量子状態のグローバル位相に関する情報を間接的に活用するために、量子関連学習プロトコルのユニークな能力に起因している。
論文 参考訳（メタデータ） (2024-05-12T09:05:13Z) - A Theory of Unsupervised Speech Recognition [60.12287608968879]
教師なし音声認識(英語: Unsupervised speech Recognition, ASR-U)は、音声のみの音声とテキストのみのコーパスから自動音声認識システムを学習する問題である。
本稿では,ランダム行列理論とニューラル・タンジェント・カーネルの理論に基づいて,ASR-U系の特性を研究するための一般的な理論的枠組みを提案する。
論文 参考訳（メタデータ） (2023-06-09T08:12:27Z) - Learnability with PAC Semantics for Multi-agent Beliefs [38.88111785113001]
推論と帰納の緊張は、おそらく哲学、認知、人工知能といった分野において最も根本的な問題である。
Valiant氏は、学習の課題は推論と統合されるべきである、と認識した。
古典的な包含よりも弱いが、クエリに応答する強力なモデル理論のフレームワークを可能にする。
論文 参考訳（メタデータ） (2023-06-08T18:22:46Z) - Balancing Explainability-Accuracy of Complex Models [8.402048778245165]
我々は,コリレーションの影響に基づき,複雑なモデルに対する新しいアプローチを提案する。
独立機能と依存機能の両方のシナリオに対するアプローチを提案する。
従属特徴に対する提案手法の複雑さの上限を提供する。
論文 参考訳（メタデータ） (2023-05-23T14:20:38Z) - 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) - Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior:
From Theory to Practice [54.03076395748459]
メタラーニング文学の中心的な疑問は、目に見えないタスクへの一般化を保証するために、いかに正規化するかである。
本稿では,Rothfussらによって最初に導かれたメタラーニングの一般化について述べる。
PAC-Bayesian per-task 学習境界におけるメタラーニングの条件と程度について,理論的解析および実証事例研究を行った。
論文 参考訳（メタデータ） (2022-11-14T08:51:04Z) - Quantum Parameterized Complexity [1.01129133945787]
パラメータ化複雑性クラスの範囲の量子アナログを導入する。
このフレームワークは、QMAハード問題のパラメータ化バージョンの複雑さの豊富な分類を公開している。
論文 参考訳（メタデータ） (2022-03-15T15:34:38Z) - Demystify Optimization and Generalization of Over-parameterized
PAC-Bayesian Learning [20.295960197612743]
PAC-Bayesianは、後部分布における仮説の重み付け平均としてトレーニングエラーを表現できる分析フレームワークである。
PAC-Bayes学習を適用すると、収束結果がカーネルリッジ回帰の解に一致することを示す。
我々はさらに、非確率的ニューラルネットワークに対するラデマッハ複雑性に基づくバウンダリを改良した、均一なPAC-ベイズ一般化バウンダリを特徴付ける。
論文 参考訳（メタデータ） (2022-02-04T03:49:11Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳（メタデータ） (2020-06-09T19:59:29Z) - Provably Efficient Exploration for Reinforcement Learning Using
Unsupervised Learning [96.78504087416654]
強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。
本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-15T19:23:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。