論文の概要: Universal Multiclass Transductive Online Learning
- arxiv url: http://arxiv.org/abs/2605.30479v1
- Date: Thu, 28 May 2026 18:51:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-01 20:56:50.184782
- Title: Universal Multiclass Transductive Online Learning
- Title（参考訳）: ユニバーサル多クラストランスダクティブオンライン学習
- Authors: Steve Hanneke, Hongao Wang,
- Abstract要約: ラベル空間を有するユニバーサルトランスダクティブオンライン分類の問題を考える。
この設定はオンライン学習を考慮し、学習者が事前に知っている一連の事例を列挙する。
- 参考スコア（独自算出の注目度）: 32.4543379850765
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{A}$ grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.
- Abstract（参考訳）: 我々は,潜在的に有界なラベル空間を持つユニバーサルトランスダクティブオンライン分類の問題を考える。
この設定はオンライン学習を考慮し、学習者が事前に知っている(ラベルなしで)一連のインスタンスを列挙する。
概念クラス $\mathcal{H}$ が学習可能であるとは、学習アルゴリズム $\mathcal{A}$ が存在するときに言う。
この設定の学習可能性を特徴付け、学習可能なクラスには2つの最適率(有界か対数的に増加するどちらか)しか存在しないことを示す。
そこで我々は'Level-Constrained-Littlestone-Littlestone (LCLL) tree''と呼ばれる新しい組み合わせ構造を導入する。
また、学習可能性の結果を非依存のケースに拡張し、インスタンスシーケンスを生成する確率過程のみを既知のケースに拡張する。
関連論文リスト
- On Improving Neurosymbolic Learning by Exploiting the Representation Space [54.16389421332958]
本稿では,入力インスタンスの隠されたゴールドラベルが論理式を満たすニューロシンボリック・セッティングにおけるニューラル分類器の学習問題について検討する。
ひとつの課題は、ラベルの組み合わせの空間が指数関数的に成長し、学習を困難にすることです。
類似の潜在表現を持つインスタンスが同じラベルを共有できるという直感を利用して,この空間を刺激する手法を提案する。
論文 参考訳（メタデータ） (2026-02-08T13:56:47Z) - Partial Feedback Online Learning [88.27143767009376]
我々は、偏見フィードバックオンライン学習と呼ばれる新しい学習プロトコルについて研究する。
各インスタンスは許容できるラベルのセットを許可するが、学習者は1ラウンドごとに許容できるラベルを1つだけ観察する。
論文 参考訳（メタデータ） (2026-01-29T09:39:11Z) - Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。
バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。
ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
論文 参考訳（メタデータ） (2025-11-16T15:47:47Z) - 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) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Multiclass Online Learning and Uniform Convergence [34.21248304961989]
対戦型オンライン学習環境におけるマルチクラス分類について検討する。
任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
論文 参考訳（メタデータ） (2023-03-30T21:35:48Z) - List Online Classification [13.358536176734999]
学習者が複数のラベルのリストを用いて予測できるマルチクラスオンライン予測について検討する。
我々は、このモデルにおける学習可能性について、$b$-ary Littlestone 次元を用いて特徴づける。
私たちの研究の一環として、ラベルのリストを使って予測するために、LittlestoneのSOAやRosenblattのPerceptronのような古典的なアルゴリズムを適用しました。
論文 参考訳（メタデータ） (2023-03-27T16:56:57Z) - Backward Feature Correction: How Deep Learning Performs Deep
(Hierarchical) Learning [66.05472746340142]
本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。
我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
論文 参考訳（メタデータ） (2020-01-13T17:28:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。