論文の概要: Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?

• arxiv url: http://arxiv.org/abs/2406.11667v2
• Date: Tue, 18 Jun 2024 04:18:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 11:41:25.382810
• Title: Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?
• Title（参考訳）: 効果的なPAC学習は'Yes'や'No'に応答するOracleで可能か?
• Authors: Constantinos Daskalakis, Noah Golowich,
• Abstract要約: 本研究では,与えられたデータセットに対する経験的リスクを最小化する仮説を計算したERMの実行能力が,効率的な学習に必要かどうかを検討する。 バイナリ分類のためのPACの実際の設定において、概念クラスは1ビットしか返さないオラクルを用いて学習可能であることを示す。 また,本研究の結果は,オラクルを少し強化した学習環境や,部分的な概念,マルチクラス,実価値の学習環境にまで及んでいる。
• 参考スコア（独自算出の注目度）: 26.334900941196082
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The empirical risk minimization (ERM) principle has been highly impactful in machine learning, leading both to near-optimal theoretical guarantees for ERM-based learning algorithms as well as driving many of the recent empirical successes in deep learning. In this paper, we investigate the question of whether the ability to perform ERM, which computes a hypothesis minimizing empirical risk on a given dataset, is necessary for efficient learning: in particular, is there a weaker oracle than ERM which can nevertheless enable learnability? We answer this question affirmatively, showing that in the realizable setting of PAC learning for binary classification, a concept class can be learned using an oracle which only returns a single bit indicating whether a given dataset is realizable by some concept in the class. The sample complexity and oracle complexity of our algorithm depend polynomially on the VC dimension of the hypothesis class, thus showing that there is only a polynomial price to pay for use of our weaker oracle. Our results extend to the agnostic learning setting with a slight strengthening of the oracle, as well as to the partial concept, multiclass and real-valued learning settings. In the setting of partial concept classes, prior to our work no oracle-efficient algorithms were known, even with a standard ERM oracle. Thus, our results address a question of Alon et al. (2021) who asked whether there are algorithmic principles which enable efficient learnability in this setting.
• Abstract（参考訳）: 経験的リスク最小化(ERM)の原則は、機械学習において非常に影響を受けており、EMMベースの学習アルゴリズムのほぼ最適理論的保証と、近年のディープラーニングにおける経験的成功を推進している。 本稿では,与えられたデータセットに対する経験的リスクを最小化する仮説を計算したERMを実行する能力が,効率的な学習に必要であるかどうかを考察する。 本稿では,2進分類のためのPAC学習の実現可能な設定において,与えられたデータセットがクラス内の何らかの概念によって実現可能かどうかを示す単一ビットのみを返却するオラクルを用いて概念クラスを学習可能であることを示す。 アルゴリズムのサンプルの複雑さとオラクルの複雑さは、仮説クラスのVC次元に多項式的に依存しているため、より弱いオラクルを使用するために支払う多項式価格のみが示される。 また,本研究の結果は,オラクルをわずかに強化した無知学習設定や,部分的概念,マルチクラス,実価値学習設定にまで及んでいる。 部分的概念クラスの設定では, 標準的なERMオラクルであっても, オラクル効率のよいアルゴリズムは知られていない。 そこで,本研究では,アルゴリズムの原理を問うAlon et al (2021) の質問に答えた。

関連論文リスト

• Probably Approximately Precision and Recall Learning [62.912015491907994]
  精度とリコールは機械学習の基本的な指標である。 一方的なフィードバック – トレーニング中にのみ肯定的な例が観察される – は,多くの実践的な問題に固有のものだ。 PAC学習フレームワークでは,各仮説をグラフで表現し,エッジは肯定的な相互作用を示す。
  論文  参考訳（メタデータ） (2024-11-20T04:21:07Z)
• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learningはニューラルネットワークを"時間とともに"学習するための新しい統合フレームワーク i)外部ソフトウェアソルバを必要とせずに統合できる、(ii)フィードフォワードおよびリカレントネットワークにおける勾配に基づく学習の概念を一般化する、(iii)新しい視点で開放する、という微分方程式に基づいている。
  論文  参考訳（メタデータ） (2024-09-18T14:57:13Z)
• LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning [11.037017229299607]
  大規模言語モデル(LLM)におけるインテリジェンス(インテリジェンス)の出現は、オートマチックラーニングへの統合に関する調査にインスピレーションを与えている。 本稿では,pMAT (probabilistic Minimally Adequate Teacher) の定式化について紹介する。 我々は,解答精度を向上し,学習したオートマタの正確性を確保する技術を開発した。
  論文  参考訳（メタデータ） (2024-08-06T07:12:09Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。 本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
  論文  参考訳（メタデータ） (2023-07-02T19:26:58Z)
• Impossibility of Collective Intelligence [10.107996426462604]
  異種環境をまたいで学習できる有理学習アルゴリズムを設計することは理論的には不可能であることを示す。 全ての公理と互換性のある唯一の実現可能なアルゴリズムは、標準的な経験的リスク最小化である。 その結果、研究者にとって最も大きな障害の一つとして、環境間の情報的非互換性が明らかとなった。
  論文  参考訳（メタデータ） (2022-06-05T07:58:39Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• On the Statistical Benefits of Curriculum Learning [33.94130046391917]
  本研究では,マルチタスク線形回帰問題におけるカリキュラム学習(CL)の利点について,構造化と非構造化の両方の条件下で検討する。 その結果,適応学習は,非構造化環境でのオラクル学習よりも根本的に困難であることが判明した。
  論文  参考訳（メタデータ） (2021-11-13T14:51:07Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  強化学習アルゴリズムは、いくつかのルールの1つに従ってエージェントのパラメータを更新する。 本稿では,更新ルール全体を検出するメタラーニング手法を提案する。 これには、一連の環境と対話することで、"何を予測するか"(例えば、値関数)と"どのように学習するか"の両方が含まれている。
  論文  参考訳（メタデータ） (2020-07-17T07:38:39Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

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