論文の概要: PAC Learning with Multiple Correct Answers

• arxiv url: http://arxiv.org/abs/2611.05133v2
• Date: Wed, 04 Nov 2026 06:37:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:57.788331
• Title: PAC Learning with Multiple Correct Answers
• Title（参考訳）: 複数回答を用いたPAC学習
• Abstract要約: 各サンプルが少なくとも$ll$正しいラベルのセットを持ち、このセットに属している場合、予測が正しい場合、PAC学習について検討する。 トレーニングは、提案されたラベルが正しい(バンドフィードバック)か、またはデモストレーターによって選択された1つの正しいラベル(デモ)のみ、完全なセットを明らかにすることができる。
• 参考スコア（独自算出の注目度）: 26.137708992013813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study PAC learning when each example comes with a set of at most $\ell$ correct labels and a prediction is correct if it belongs to this set. Training may reveal the full set, only whether a proposed label is correct (bandit feedback), or one correct label chosen by a demonstrator (demonstrations). Our main finding is that demonstrations can be much harder than full sets, and even than bandit feedback, both in which classes can be learned and in how many examples are needed. For finite label spaces, a generalized Natarajan dimension characterizes learnability from full sets and from bandit feedback, in both the realizable and the agnostic setting. From demonstrations, however, a class is realizably learnable if and only if the intersections of at most $\ell+1$ of its hypotheses are learnable from full sets. Already with three labels, this condition can fail for a class learnable from a single full-set example or even a single bandit answer. When the condition holds, we show that $\widetilde O(\varepsilon^{-\ell})$ demonstrations suffice, and the exponent $\ell$ cannot be improved in general, even for classes learnable from $\widetilde O(1/\varepsilon)$ full sets or bandit answers. For countable label spaces and $\ell \geq 2$, our packed dimension, which asks for many disjoint groups of at most $\ell+1$ hypotheses with no common label, characterizes full-set learnability, and demonstrations still reduce to intersections. Agnostic learning from demonstrations, already for finite label spaces, is not determined by the dimensions of the intersection class that characterize realizable learning. Finally, we show that the uniform bound $\ell$ on the number of correct labels is essential. Without this bound, it is impossible to characterize learnability by any dimension determined by finite subclasses.
• Abstract（参考訳）: 各サンプルに少なくとも$$\ell$の正しいラベルのセットが付いてくると、PAC学習が研究され、このセットに属すると予測が正しい。 トレーニングは、提案されたラベルが正しい(バンドフィードバック)か、またはデモストレーターによって選択された1つの正しいラベル(デモ)のみ、完全なセットを明らかにすることができる。 私たちの主な発見は、実演はフルセットよりもはるかに難しく、また、学習可能なクラスと必要なサンプルの数の両方において、包括的フィードバックよりもはるかに難しいということです。 有限ラベル空間に対して、一般化されたナタラジャン次元は、完全集合と包帯的フィードバックから、実現可能かつ不可知的な設定の両方において学習可能性を特徴づける。 しかし、実演から、クラスが真に学習可能であることと、その仮説の少なくとも$\ell+1$の交叉が完全集合から学習可能であることは同値である。 既に3つのラベルがあり、この条件は1つのフルセットの例から学べるクラスや、1つのバンディットの答えから学べるクラスで失敗することがある。 条件が成り立つと、$\widetilde O(\varepsilon^{-\ell})$ が十分であり、指数$\ell$は、$\widetilde O(1/\varepsilon)$ から学習可能なクラスであっても、一般には改善できない。 可算ラベル空間と $\ell \geq 2$ に対して、我々の充填次元は、最大で$\ell+1$ という多くの非連結な群に共通ラベルを持たず、完全集合の学習性を特徴付け、デモは依然として交叉に還元される。 有限ラベル空間に対して既に証明から得られる非依存的な学習は、実現可能な学習を特徴づける交叉クラスの次元によって決定されない。 最後に、正しいラベルの数に対する一様有界$\ell$が不可欠であることを示す。 この境界がなければ、有限部分類によって決定される任意の次元によって学習可能性を特徴づけることは不可能である。

関連論文リスト

• Two Dimensions Govern Agnostic Multiclass Transductive Learning [1.14219428942199]
  帰納的分類では、敵はラベル付き人口を固定し、1つのラベルは均一に隠され、学習者は残りの全てのラベルを見る。 バイナリクラスでは、トランスダクティブとPAC学習は同じミニマックスレートを持つ。 我々は、この有限人口分割における実現可能な圧縮、ラベル空間の縮小、および内部メニュー圧縮を組み合わせる。
  論文  参考訳（メタデータ） (2026-08-26T03:15:54Z)
• PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting [46.089126569274676]
  本研究では,マルチクラスPAC学習における帯域幅フィードバックによる課題について検討する。 このフレームワークでは、インスタンススペース$mathcalX$とラベルスペース$mathcalY$に未知のデータ分散があります。 我々は、この問題の最適サンプルの一般的な特徴を与え、すべての概念クラスを複雑さまで鋭くする。
  論文  参考訳（メタデータ） (2026-05-25T10:35:16Z)
• Partial Feedback Online Learning [88.27143767009376]
  我々は、偏見フィードバックオンライン学習と呼ばれる新しい学習プロトコルについて研究する。 各インスタンスは許容できるラベルのセットを許可するが、学習者は1ラウンドごとに許容できるラベルを1つだけ観察する。
  論文  参考訳（メタデータ） (2026-01-29T09:39:11Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• Understanding Aggregations of Proper Learners in Multiclass Classification [4.422219522591412]
  マルチクラスの学習性は、適切な障壁を示すことが知られている。 二項分類の最近の進歩は、適切な学習者の集合を用いて、この要件を満たすことを実証している。 1つのERMが$Omega left(fracd_G ln (1 / delta)epsilonright)$サンプルを必要とすることを示す。
  論文  参考訳（メタデータ） (2024-10-30T07:12:02Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Agnostic Multi-Group Active Learning [24.97598179536084]
  能動的学習の観点から,この問題の変種を考察し,学習者がコレクションの各分布からどの例をラベル付けするかを判断する権限を付与する。 我々の主な課題は、不一致に基づくアクティブラーニングのような標準的なアクティブラーニング技術が、マルチグループラーニングの目的に直接適用されないことである。 既存のアルゴリズムを改良し、多群学習の非依存的な定式化のための一貫した能動的学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-06-02T21:24:13Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)

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

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