論文の概要: 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の係数の上限を一致させる。 この場合、より大きなギャップが可能であると推測する。 私たちの技術的研究の中心は、ホールの古典的なマッチング定理を一般化し、独立興味を持つかもしれない対象値以下の関数のクラスを保持する変数の割り当てに関するコンパクト性の結果です。

関連論文リスト

• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
  論文  参考訳（メタデータ） (2024-05-08T16:26:49Z)
• On Representation Complexity of Model-based and Model-free Reinforcement Learning [11.843778337443824]
  回路複雑性の文脈におけるモデルベースおよびモデルフリー強化学習(RL)の表現複雑性について検討した。 理論的には、その基底となる遷移関数と報酬関数が、大きさの一定深さの回路で表現できるような、幅広い種類のMDPが存在することを証明している。 近似誤差に注意を向け、複雑性理論への接続を構築することによって、モデルベースのアルゴリズムが、新しい表現複雑性の観点からモデルフリーアルゴリズムよりも、なぜサンプルの複雑さを楽しむのかというユニークな洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-03T00:01:58Z)
• On Learning Latent Models with Multi-Instance Weak Supervision [57.18649648182171]
  本稿では,複数の入力インスタンスに関連付けられた遷移関数$sigma$ラベルによって,教師信号が生成される弱い教師付き学習シナリオについて考察する。 我々の問題は、潜在的な構造学習やニューロシンボリックな統合など、さまざまな分野で満たされている。
  論文  参考訳（メタデータ） (2023-06-23T22:05:08Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency [105.17746223041954]
  部分的に観察されたマルコフ決定過程(POMDP)における強化学習は2つの課題に直面している。 しばしば、未来を予測するのに完全な歴史を要し、地平線と指数関数的にスケールするサンプルの複雑さを誘導する。 本稿では,2段階の表現を最適化しながら学習するETC(Embed to Control)という強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-26T16:34:46Z)
• Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability [7.727052811126007]
  結果の不一致性において、目標は、ターゲット予測子と区別できない予測子を出力することである。 結果の不一致性のサンプル複雑性は、$P$ w.r.tの計量エントロピーによって特徴づけられる。 この同値性は凸幾何学における長年の計量エントロピー双対性予想と興味深い関係を持つ。
  論文  参考訳（メタデータ） (2022-03-09T06:02:31Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model [11.821892196198457]
  我々は$d$-bitパリティ関数の学習のサンプル複雑さが$Omega (2d/2)$であることを示した。 また、単純なシャッフルモデルプロトコルをスケッチし、その結果が$poly(d)$ factorにきついことを示す。
  論文  参考訳（メタデータ） (2021-03-29T15:26:02Z)
• Enhanced Principal Component Analysis under A Collaborative-Robust Framework [89.28334359066258]
  重み学習とロバストな損失を非自明な方法で組み合わせる,一般的な協調ロバスト重み学習フレームワークを提案する。 提案されたフレームワークでは、トレーニング中の重要度を示す適切なサンプルの一部のみがアクティブになり、エラーが大きい他のサンプルは無視されません。 特に、不活性化試料の負の効果はロバスト損失関数によって軽減される。
  論文  参考訳（メタデータ） (2021-03-22T15:17:37Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)

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

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