論文の概要: Self-Directed Apple Tasting
- arxiv url: http://arxiv.org/abs/2611.06677v1
- Date: Wed, 04 Nov 2026 15:46:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 03:25:58.190073
- Title: Self-Directed Apple Tasting
- Title(参考訳): セルフダイレクトのアップルテイスティング
- Abstract要約: 学習者が真のラベルを観測する部分的フィードバックモデルである古典的なリンゴ味付け設定について検討する。
自己指向の環境では,学習者が犯したミスの最小限の数の四分法を確立する。
- 参考スコア(独自算出の注目度): 0.764671395172401
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the classical apple-tasting setting, a partial feedback model in which the learner observes the true label only when it predicts $1$. A combinatorial characterization for the rates of this problem in the online adversarial setting has been studied by Raman et al. (2024). We study the self-directed setting, in which the learner can adaptively choose the order of the points it predicts on. In the realizable setting, we establish a tetrachotomy on the expected minimax number of mistakes made by any learner. Depending on the VC dimension, the $\emptyset$-centered star number, and the self-directed dimension, we show that the rates could possibly be $Θ(1)$, $O(\log n) \cap ω(1)$, $\tilde Θ(\sqrt{n})$, or $Θ(n)$. In the agnostic setting, the minimax regret is $\tilde Θ(\sqrt{n})$ or $Θ(n)$, depending on the VC dimension.
- Abstract(参考訳): 学習者が真のラベルを観測する部分的フィードバックモデルである古典的なリンゴ味付け設定について検討する。
オンライン対数設定におけるこの問題の速度の組合せ的特徴は、Raman et al (2024) によって研究されている。
本研究では,学習者が予測する点の順序を適応的に選択できる自己指示設定について検討する。
実現可能な設定では、任意の学習者が犯したミスの最小限の数の四分法を確立する。
VC次元、$\emptyset$-centered star number、および自己指向次元に依存すると、このレートは、$ >(1)$, $O(\log n) \cap ω(1)$, $\tilde >(\sqrt{n})$, $ >(n)$ となる可能性がある。
不可知的な設定では、ミニマックスの後悔はVC次元に応じて$\tilde >(\sqrt{n})$または$(n)$である。
関連論文リスト
- Online Set Learning from Precision and Recall Feedback [60.00180898830079]
オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。
この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。
この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
論文 参考訳(メタデータ) (2026-05-10T14:28:05Z) - Deterministic Apple Tasting [2.4554686192257424]
我々は、初めて広く適用可能な決定論的リンゴテイスティング学習者を提供する。
すべてのクラス $mathcalH$ は簡単、困難、あるいは学習不能でなければならない、という三分法を証明します。
我々の上限は、リンゴの味付けフィードバックに関する専門家のアドバイスから学ぶための決定論的アルゴリズムに基づいている。
論文 参考訳(メタデータ) (2024-10-14T11:54:46Z) - A Trichotomy for Transductive Online Learning [32.03948071550447]
我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
論文 参考訳(メタデータ) (2023-11-10T23:27:23Z) - Apple Tasting: Combinatorial Dimensions and Minimax Rates [16.52706654413988]
エンファップル味覚フィードバックに基づくオンライン二項分類では、学習者は1を予測した場合のみ真のラベルを観察する。
実現可能な設定では、期待されるミスの回数が$Theta$または$Theta(T)$であることを示す。
論文 参考訳(メタデータ) (2023-10-29T16:37:51Z) - Self-Directed Linear Classification [50.659479930171585]
オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。
そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
論文 参考訳(メタデータ) (2023-08-06T15:38:44Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳(メタデータ) (2022-10-06T06:49:48Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳(メタデータ) (2021-04-17T08:22:04Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳(メタデータ) (2020-06-16T13:01:33Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。