論文の概要: Online Set Learning from Precision and Recall Feedback
- arxiv url: http://arxiv.org/abs/2605.09565v1
- Date: Sun, 10 May 2026 14:28:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:50.312694
- Title: Online Set Learning from Precision and Recall Feedback
- Title（参考訳）: 精度とリコールフィードバックからのオンラインセット学習
- Authors: Lee Cohen, Yishay Mansour, Shay Moran, Han Shao,
- Abstract要約: オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。
この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。
この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
- 参考スコア（独自算出の注目度）: 60.00180898830079
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of learning an unknown subset $N_\text{target}$ of a domain in an online setting. In each round $t$, the learner predicts a set of items ${N}_t$ and receives one of two types of feedback, each with equal probability: precision feedback, in which a randomly chosen item from the predicted set $N_t$ is revealed and the learner is told whether it belongs to $N_\text{target}$ (incurring a reward if it does), or recall feedback, in which a randomly chosen item from the target set $N_\text{target}$ is revealed and the learner is told whether it belongs to $N_t$ (incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning -- where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM) -- our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.
- Abstract（参考訳）: 我々は、未知のサブセットである$N_\text{target}$をオンライン設定で学習する問題を考える。
各ラウンド$t$において、学習者は、${N}_t$のセットを予測し、それぞれ同じ確率で2種類のフィードバックの1つを受け取る: 精度フィードバック、予測セット$N_t$からランダムに選択されたアイテムが露呈され、学習者は、そのアイテムが$N_\text{target}$に属するかどうかを知らせる(その場合、報酬が発生する)、あるいは、ターゲットセット$N_\text{target}$からランダムに選択されたアイテムが露呈され、学習者は、$N_t$に属するかどうかを知らせる(その場合、報酬を受ける)。
目標は、累積的な報酬を時間とともに最大化することです。
この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。
この設定において、仮説クラス(領域の部分集合の族)が学習可能であることは、それが有限なVapnik-Chervonenkis (VC)次元を持ち、古典的なPAC特徴づけを反映している場合に限る。
しかし、アルゴリズム構造は明らかに複雑で、標準的な確率的精度(PAC)学習とは対照的に、アルゴリズムのランドスケープは経験的リスク最小化(Empirical Risk Minimization、ERM)の単純な原則によって制御される。
我々は,フィードバックによって引き起こされる依存関係に対処するアルゴリズムを開発し,実現可能な設定と不可知な設定の両方において,後悔の保証を得る。
本研究は,本モデルにおける学習可能性の質的評価を提供し,その最も基本的な問題に対処すると同時に,最適後悔率の判定を含む,自然で興味をそそるオープンな問題に言及する。
関連論文リスト
- Partial Feedback Online Learning [88.27143767009376]
我々は、偏見フィードバックオンライン学習と呼ばれる新しい学習プロトコルについて研究する。
各インスタンスは許容できるラベルのセットを許可するが、学習者は1ラウンドごとに許容できるラベルを1つだけ観察する。
論文 参考訳（メタデータ） (2026-01-29T09:39:11Z) - Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond [37.92189925462977]
本稿では,一括線形報酬に対する後悔の最小化に取り組むための一般的なオンライン学習フレームワークを提案する。
我々のアルゴリズムは$widetildeO(sqrtnT)$を後悔しており、$n$は報酬関数のピース数、$T$はラウンド数である。
第2に,提案アルゴリズムは,ポストプライスオークションにおける価格設定の学習において,適切な(かつ望ましい)インスタンス非依存の後悔境界を達成できることを実証する。
論文 参考訳（メタデータ） (2025-03-03T16:13:45Z) - Probably Approximately Precision and Recall Learning [60.00180898830079]
機械学習における重要な課題は、一方的なフィードバックの頻度である。
本稿では,確率的近似(PAC)フレームワークを導入し,各入力をラベルの集合にマッピングする仮説を定めている。
我々は、正のデータのみから学習する新しいアルゴリズムを開発し、実現可能な場合において最適なサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2024-11-20T04:21:07Z) - Controlling Federated Learning for Covertness [15.878313629774269]
学習者は、ノイズの多い勾配評価を提供する分散オラクルを何度もクエリすることで、関数の$f$を最小化することを目指している。
同時に、学習者は、学習者のクエリを監視する悪意のある盗聴者から$argmin f$を隠そうとする。
本稿では,学習者が学習と難読化のどちらを動的に選択するかという,textitcovert や textitlearner-private 最適化の問題について考察する。
論文 参考訳（メタデータ） (2023-08-17T07:16:41Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。