論文の概要: A Theory of PAC Learnability of Partial Concept Classes
- arxiv url: http://arxiv.org/abs/2107.08444v2
- Date: Tue, 20 Jul 2021 19:25:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-22 11:19:17.068498
- Title: A Theory of PAC Learnability of Partial Concept Classes
- Title（参考訳）: 部分概念クラスにおけるPAC学習可能性の理論
- Authors: Noga Alon and Steve Hanneke and Ron Holzman and Shay Moran
- Abstract要約: 我々は、多種多様な学習タスクをモデル化できるように、PAC学習理論を拡張した。
部分概念クラスのPAC学習性を特徴付け,古典的クラスと根本的に異なるアルゴリズム的ランドスケープを明らかにする。
- 参考スコア（独自算出の注目度）: 30.772106555607458
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We extend the theory of PAC learning in a way which allows to model a rich
variety of learning tasks where the data satisfy special properties that ease
the learning process. For example, tasks where the distance of the data from
the decision boundary is bounded away from zero. The basic and simple idea is
to consider partial concepts: these are functions that can be undefined on
certain parts of the space. When learning a partial concept, we assume that the
source distribution is supported only on points where the partial concept is
defined.
This way, one can naturally express assumptions on the data such as lying on
a lower dimensional surface or margin conditions. In contrast, it is not at all
clear that such assumptions can be expressed by the traditional PAC theory. In
fact we exhibit easy-to-learn partial concept classes which provably cannot be
captured by the traditional PAC theory. This also resolves a question posed by
Attias, Kontorovich, and Mansour 2019.
We characterize PAC learnability of partial concept classes and reveal an
algorithmic landscape which is fundamentally different than the classical one.
For example, in the classical PAC model, learning boils down to Empirical Risk
Minimization (ERM). In stark contrast, we show that the ERM principle fails in
explaining learnability of partial concept classes. In fact, we demonstrate
classes that are incredibly easy to learn, but such that any algorithm that
learns them must use an hypothesis space with unbounded VC dimension. We also
find that the sample compression conjecture fails in this setting.
Thus, this theory features problems that cannot be represented nor solved in
the traditional way. We view this as evidence that it might provide insights on
the nature of learnability in realistic scenarios which the classical theory
fails to explain.
- Abstract（参考訳）: 我々は、PAC学習の理論を拡張して、学習プロセスを容易にする特別な特性をデータが満たすような、多様な学習タスクをモデル化する。
例えば、決定境界からのデータの距離がゼロから離れたタスクである。
基本的で単純な考え方は部分的概念を考えることである: これらは空間の特定の部分で定義できない関数である。
部分的概念を学習する際には、部分的概念が定義される点のみにソース分布がサポートされると仮定する。
このようにして、より低い次元の表面やマージン条件に横たわるようなデータ上の仮定を自然に表現することができる。
対照的に、そのような仮定が伝統的なpac理論によって表現できるかどうかは明確ではない。
実際、従来のPAC理論では達成できないような、容易に学習できる部分概念クラスを提示する。
これはまた、Attias、Kontorovich、Mansour 2019によって提起された問題も解決する。
部分概念クラスのPAC学習性を特徴付け,従来のものと根本的に異なるアルゴリズム的景観を明らかにする。
例えば、古典的なPACモデルでは、学習は経験的リスク最小化(Empirical Risk Minimization、ERM)へと導かれる。
対照的に、ERMの原理は部分概念クラスの学習可能性を説明するのに失敗する。
実際、非常に簡単に学習できるクラスを実証するが、それらを学ぶアルゴリズムは、無界なVC次元の仮説空間を使わなければならない。
また、この設定では、サンプル圧縮予想が失敗する。
したがって、この理論は従来の方法では表現できない問題や解決できない問題を特徴としている。
我々はこれを、古典理論が説明できない現実的なシナリオにおける学習可能性の性質に関する洞察を提供する証拠として捉えている。
関連論文リスト
- Computable learning of natural hypothesis classes [0.0]
最近、PACが学習可能であるが、計算可能でない仮説クラスが与えられた。
計算可能性理論のon-a-cone 機械を用いて、仮説クラスが計算可能リスト化可能であるような軽微な仮定の下では、学習可能な自然仮説クラスは計算可能リスト化可能であることを証明する。
論文 参考訳（メタデータ） (2024-07-23T17:26:38Z) - ClassDiffusion: More Aligned Personalization Tuning with Explicit Class Guidance [78.44823280247438]
新しい概念を学ぶ際に,意味的保存損失を利用して概念空間を明示的に制御する手法であるClassDiffusionを提案する。
その単純さにもかかわらず、これはターゲット概念を微調整する際のセマンティックドリフトを避けるのに役立つ。
CLIP-T測定値の非効率な評価に対して,BLIP2-T測定値を導入する。
論文 参考訳（メタデータ） (2024-05-27T17:50:10Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - Multiclass Learnability Beyond the PAC Framework: Universal Rates and
Partial Concept Classes [31.2676304636432]
本研究では,有界なラベル数$k$の多クラス分類の問題について,実現可能な設定で検討する。
従来のPACモデルを(a)分布依存学習率、(b)データ依存仮定下での学習率に拡張する。
論文 参考訳（メタデータ） (2022-10-05T14:36:27Z) - When are Post-hoc Conceptual Explanations Identifiable? [18.85180188353977]
人間の概念ラベルが利用できない場合、概念発見手法は解釈可能な概念のための訓練された埋め込み空間を探索する。
我々は、概念発見は特定可能であり、多くの既知の概念を確実に回収し、説明の信頼性を保証するべきであると論じている。
本結果は,人間ラベルのない信頼性の高い概念発見を保証できる厳密な条件を強調した。
論文 参考訳（メタデータ） (2022-06-28T10:21:17Z) - Chaos is a Ladder: A New Theoretical Understanding of Contrastive
Learning via Augmentation Overlap [64.60460828425502]
コントラスト学習の下流性能に関する新たな保証を提案する。
我々の新しい理論は、攻撃的なデータ強化の下で、異なるクラス内サンプルのサポートがより重なり合うという知見に基づいている。
本稿では、下流の精度とよく一致した教師なしモデル選択距離ARCを提案する。
論文 参考訳（メタデータ） (2022-03-25T05:36:26Z) - A Characterization of Multiclass Learnability [18.38631912121182]
DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。
リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。
2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
論文 参考訳（メタデータ） (2022-03-03T07:41:54Z) - Realizable Learning is All You Need [21.34668631009594]
実現可能かつ不可知的な学習可能性の同値性は、学習理論における基本的な現象である。
実現可能かつ不可知な学習可能性の同値性を説明する最初のモデルに依存しないフレームワークを提示する。
論文 参考訳（メタデータ） (2021-11-08T19:00:00Z) - A Low Rank Promoting Prior for Unsupervised Contrastive Learning [108.91406719395417]
提案手法は,従来の低階の促進をコントラスト学習の枠組みに効果的に組み込む新しい確率的グラフィカルモデルを構築する。
我々の仮説は、同じインスタンスクラスに属するすべてのサンプルが、小さな次元の同じ部分空間上にあることを明示的に要求する。
実証的な証拠は、提案アルゴリズムが複数のベンチマークにおける最先端のアプローチを明らかに上回っていることを示している。
論文 参考訳（メタデータ） (2021-08-05T15:58:25Z) - Formalising Concepts as Grounded Abstractions [68.24080871981869]
このレポートは、表現学習が生データから概念を誘導する方法を示しています。
このレポートの主な技術的目標は、表現学習のテクニックが概念空間の格子理論的定式化とどのように結婚できるかを示すことである。
論文 参考訳（メタデータ） (2021-01-13T15:22:01Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳（メタデータ） (2020-06-09T19:59:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。