論文の概要: Learnability is a Compact Property
- arxiv url: http://arxiv.org/abs/2402.10360v1
- Date: Thu, 15 Feb 2024 23:10:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-19 18:07:30.016107
- Title: Learnability is a Compact Property
- Title(参考訳): 学習能力はコンパクトな特性です
- Authors: Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan,
Shang-Hua Teng
- Abstract要約: 様々な問題の学習性は決定不可能であり、あるいは集合論の標準ZFC公理とは独立である。
仮説クラスを学習する際のサンプルの複雑さは、その有限射影を調べることで検出できることを示す。
不適切な損失関数を持つ実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。
- 参考スコア(独自算出の注目度): 10.909417433031454
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Recent work on learning has yielded a striking result: the learnability of
various problems can be undecidable, or independent of the standard ZFC axioms
of set theory. Furthermore, the learnability of such problems can fail to be a
property of finite character: informally, it cannot be detected by examining
finite projections of the problem.
On the other hand, learning theory abounds with notions of dimension that
characterize learning and consider only finite restrictions of the problem,
i.e., are properties of finite character. How can these results be reconciled?
More precisely, which classes of learning problems are vulnerable to logical
undecidability, and which are within the grasp of finite characterizations?
We demonstrate that the difficulty of supervised learning with metric losses
admits a tight finite characterization. In particular, we prove that the sample
complexity of learning a hypothesis class can be detected by examining its
finite projections. For realizable and agnostic learning with respect to a wide
class of proper loss functions, we demonstrate an exact compactness result: a
class is learnable with a given sample complexity precisely when the same is
true of all its finite projections. For realizable learning with improper loss
functions, we show that exact compactness of sample complexity can fail, and
provide matching upper and lower bounds of a factor of 2 on the extent to which
such sample complexities can differ. We conjecture that larger gaps are
possible for the agnostic case.
At the heart of our technical work is a compactness result concerning
assignments of variables that maintain a class of functions below a target
value, which generalizes Hall's classic matching theorem and may be of
independent interest.
- Abstract(参考訳): 様々な問題の学習性は決定不可能であり、あるいは集合論の標準的なzfc公理とは無関係である。
さらに、そのような問題の学習性は有限文字の性質に失敗する可能性があり、非公式に、問題の有限射影を調べることでは検出できない。
一方、学習理論は、学習を特徴づける次元の概念が豊富にあり、問題の有限制限のみ、すなわち有限文字の性質であると考える。
これらの結果はどのように和解できるのか?
より正確には、どの学習問題が論理的不決定性に弱いのか、どのクラスが有限な特徴の把握範囲内なのか?
計量損失を伴う教師付き学習の難しさは,有限要素の厳密なキャラクタリゼーションを許すことを実証する。
特に、仮説クラスを学習するサンプル複雑性は、その有限射影を調べることによって検出できることを証明する。
適切な損失関数の幅広いクラスに関して実現可能かつ不可知的な学習を行うため、クラスはその有限射影の全てについて同じことが真であるときに与えられたサンプルの複雑さで正確に学習可能であることを示す。
不適切な損失関数を持つ実現可能な学習では、サンプル複雑性の厳密なコンパクト性が失敗しうることを示し、そのようなサンプル複雑度の違いの程度で2の係数の上限を一致させる。
この場合、より大きなギャップが可能であると推測する。
私たちの技術的研究の中心は、ホールの古典的なマッチング定理を一般化し、独立興味を持つかもしれない対象値以下の関数のクラスを保持する変数の割り当てに関するコンパクト性の結果です。
関連論文リスト
- Understanding and Mitigating Classification Errors Through Interpretable
Token Patterns [58.91023283103762]
容易に解釈可能な用語でエラーを特徴付けることは、分類器が体系的なエラーを起こす傾向にあるかどうかを洞察する。
正しい予測と誤予測を区別するトークンのパターンを発見することを提案する。
提案手法であるPremiseが実際によく動作することを示す。
論文 参考訳(メタデータ) (2023-11-18T00:24:26Z) - On Learning Latent Models with Multi-Instance Weak Supervision [63.07650883781489]
本稿では,複数の入力インスタンスに関連付けられた遷移関数$sigma$ラベルによって,教師信号が生成される弱い教師付き学習シナリオについて考察する。
我々の問題は、潜在的な構造学習やニューロシンボリックな統合など、さまざまな分野で満たされている。
論文 参考訳(メタデータ) (2023-06-23T22:05:08Z) - The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。
この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。
我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
論文 参考訳(メタデータ) (2023-05-16T15:01:22Z) - Impossibility of Characterizing Distribution Learning -- a simple
solution to a long-standing problem [11.39656079889941]
分散クラス学習の複雑さを特徴付ける次元の概念は存在しないことを示す。
特に,どのタスクにも次元(あるいは学習可能性の特性)を特徴づける概念は存在しないことを示す。
論文 参考訳(メタデータ) (2023-04-18T03:23:39Z) - Adversarially Robust PAC Learnability of Real-Valued Functions [19.54399554114989]
脂肪散乱次元のクラスは $ell_p$ 摂動条件で学習可能であることを示す。
そこで本研究では,実関数に対する非依存的な新しいサンプルスキームを提案する。
論文 参考訳(メタデータ) (2022-06-26T21:27:23Z) - On Finite-Sample Identifiability of Contrastive Learning-Based Nonlinear
Independent Component Analysis [11.012445089716016]
この研究は GCL ベースの nICA の有限サンプル識別可能性解析を行う。
本フレームワークは, GCL損失関数の特性, 統計解析, 数値微分を加味したものである。
論文 参考訳(メタデータ) (2022-06-14T04:59:08Z) - A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。
最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
論文 参考訳(メタデータ) (2022-02-11T03:01:45Z) - Realizable Learning is All You Need [21.34668631009594]
実現可能かつ不可知的な学習可能性の同値性は、学習理論における基本的な現象である。
実現可能かつ不可知な学習可能性の同値性を説明する最初のモデルに依存しないフレームワークを提示する。
論文 参考訳(メタデータ) (2021-11-08T19:00:00Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳(メタデータ) (2021-10-21T07:28:11Z) - Pairwise Supervision Can Provably Elicit a Decision Boundary [84.58020117487898]
類似性学習は、パターンのペア間の関係を予測することによって有用な表現を引き出す問題である。
類似性学習は、決定境界を直接引き出すことによって二項分類を解くことができることを示す。
論文 参考訳(メタデータ) (2020-06-11T05:35:16Z) - Provably Efficient Exploration for Reinforcement Learning Using
Unsupervised Learning [96.78504087416654]
強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。
本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
論文 参考訳(メタデータ) (2020-03-15T19:23:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。