論文の概要: 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（参考訳）: 精度とリコールフィードバックからのオンラインセット学習
- 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)の単純な原則によって制御される。
我々は,フィードバックによって引き起こされる依存関係に対処するアルゴリズムを開発し,実現可能な設定と不可知な設定の両方において,後悔の保証を得る。
本研究は,本モデルにおける学習可能性の質的評価を提供し,その最も基本的な問題に対処すると同時に,最適後悔率の判定を含む,自然で興味をそそるオープンな問題に言及する。
関連論文リスト
- Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
本研究では,マッサートノイズの存在下での漂流概念の学習問題について検討する。
このフレームワークでは、オンライン学習者は独立したサンプルの履歴にアクセスすることができる。
目標は、各ラウンドで小さな予測誤差の仮説を出力することである。
論文 参考訳（メタデータ） (2026-06-09T17:35:18Z) - 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) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。
各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。
目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - Controlling Federated Learning for Covertness [15.878313629774269]
学習者は、ノイズの多い勾配評価を提供する分散オラクルを何度もクエリすることで、関数の$f$を最小化することを目指している。
同時に、学習者は、学習者のクエリを監視する悪意のある盗聴者から$argmin f$を隠そうとする。
本稿では,学習者が学習と難読化のどちらを動的に選択するかという,textitcovert や textitlearner-private 最適化の問題について考察する。
論文 参考訳（メタデータ） (2023-08-17T07:16:41Z) - Improved Sample Complexity Bounds for Distributionally Robust
Reinforcement Learning [3.222802562733787]
トレーニング環境とテスト環境のパラメータミスマッチに対して頑健な制御ポリシーを学習することの問題点を考察する。
本研究では,4つの異なる発散によって特定される不確実性集合に対して,ロバスト位相値学習(RPVL)アルゴリズムを提案する。
提案アルゴリズムは,既存の結果より一様によいサンプル複雑性を$tildemathcalO(|mathcalSmathcalA| H5)$とする。
論文 参考訳（メタデータ） (2023-03-05T21:47:08Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳（メタデータ） (2022-10-12T11:04:22Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。