論文の概要: Multiclass Transductive Online Learning
- arxiv url: http://arxiv.org/abs/2411.01634v1
- Date: Sun, 03 Nov 2024 16:57:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:44:03.105617
- Title: Multiclass Transductive Online Learning
- Title（参考訳）: マルチクラストランスダクティブオンライン学習
- Authors: Steve Hanneke, Vinod Raman, Amirreza Shaeiri, Unique Subedi,
- Abstract要約: 本稿では,ラベルの数が無制限である場合のオンライン学習の帰納的課題について考察する。
レベル制約されたリトルストーン次元と呼ばれる新しい次元は、この設定におけるオンライン学習可能性の特徴である。
ラベル空間が非有界である場合でも、期待されるミス回数の最小値の3分法が保たれることを示す。
- 参考スコア（独自算出の注目度）: 14.093228102168872
- License:
- Abstract: We consider the problem of multiclass transductive online learning when the number of labels can be unbounded. Previous works by Ben-David et al. [1997] and Hanneke et al. [2023b] only consider the case of binary and finite label spaces, respectively. The latter work determined that their techniques fail to extend to the case of unbounded label spaces, and they pose the question of characterizing the optimal mistake bound for unbounded label spaces. We answer this question by showing that a new dimension, termed the Level-constrained Littlestone dimension, characterizes online learnability in this setting. Along the way, we show that the trichotomy of possible minimax rates of the expected number of mistakes established by Hanneke et al. [2023b] for finite label spaces in the realizable setting continues to hold even when the label space is unbounded. In particular, if the learner plays for $T \in \mathbb{N}$ rounds, its minimax expected number of mistakes can only grow like $\Theta(T)$, $\Theta(\log T)$, or $\Theta(1)$. To prove this result, we give another combinatorial dimension, termed the Level-constrained Branching dimension, and show that its finiteness characterizes constant minimax expected mistake-bounds. The trichotomy is then determined by a combination of the Level-constrained Littlestone and Branching dimensions. Quantitatively, our upper bounds improve upon existing multiclass upper bounds in Hanneke et al. [2023b] by removing the dependence on the label set size. In doing so, we explicitly construct learning algorithms that can handle extremely large or unbounded label spaces. A key and novel component of our algorithm is a new notion of shattering that exploits the sequential nature of transductive online learning. Finally, we complete our results by proving expected regret bounds in the agnostic setting, extending the result of Hanneke et al. [2023b].
- Abstract（参考訳）: ラベルの数が無制限である場合,多段階のオンライン学習の問題を考える。
Ben-David et al [1997] と Hanneke et al [2023b] による以前の研究は、それぞれ二進ラベル空間と有限ラベル空間の場合にのみ考慮する。
後者の研究は、それらの手法が非有界ラベル空間の場合には拡張できないと判断し、非有界ラベル空間の最適誤りを特徴づけるという問題を提起した。
レベル制約のLittlestone次元と呼ばれる新しい次元が、この設定におけるオンライン学習可能性の特徴であることを示すことで、この問題に答える。
その過程で、有限ラベル空間に対するHanneke et al[2023b] による期待される誤り数のミニマックス率の3分法が、ラベル空間が非有界である場合でも保たれることを示す。
特に、学習者が$T \in \mathbb{N}$ラウンドでプレイすると、その最小限のミス数は$\Theta(T)$, $\Theta(\log T)$, $\Theta(1)$のようにしか成長しない。
この結果を証明するために、レベル制約分岐次元と呼ばれる別の組合せ次元を与え、その有限性が期待される最小値の誤差境界を特徴付けることを示す。
次に、三分法はレベル制約のリトルストーンと分岐次元の組み合わせによって決定される。
定量的に,Henneke et al[2023b] の既存のマルチクラス上限よりも,ラベルセットサイズへの依存を取り除くことにより,上界が向上する。
そこで我々は,極大あるいは非有界なラベル空間を扱える学習アルゴリズムを明示的に構築する。
我々のアルゴリズムの重要かつ新しい構成要素は、トランスダクティブオンライン学習のシーケンシャルな性質を利用する、シャッタリングという新しい概念である。
最後に、予測された無知な条件における後悔の限界を証明し、Hanneke et al [2023b] の結果を拡張して結果を完成させる。
関連論文リスト
- The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。
我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-16T12:11:09Z) - A Trichotomy for Transductive Online Learning [32.03948071550447]
我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
論文 参考訳（メタデータ） (2023-11-10T23:27:23Z) - Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
そこで我々はShrinkMatchと呼ばれる新しい手法を提案し、不確実なサンプルを学習する。
それぞれの不確実なサンプルに対して、元の Top-1 クラスを単に含むスランク類空間を適応的に求める。
次に、スランク空間における強と弱に強化された2つのサンプル間の整合正則化を課し、識別的表現を試みます。
論文 参考訳（メタデータ） (2023-08-13T14:05:24Z) - Towards Imbalanced Large Scale Multi-label Classification with Partially
Annotated Labels [8.977819892091]
マルチラベル分類は、複数のクラスにインスタンスを関連付けることができる日常生活において、広く発生する問題である。
本研究では,ラベルの不均衡の問題に対処し,部分ラベルを用いたニューラルネットワークのトレーニング方法について検討する。
論文 参考訳（メタデータ） (2023-07-31T21:50:48Z) - Online Learning with Set-Valued Feedback [18.054632903107546]
学習者は1つのラベルを予測するが、フィードバックとしてラベルのテキストセットを受け取る。
単一ラベルフィードバックによるオンラインマルチクラス学習とは異なり、決定論的かつランダムなオンライン学習は、実現可能な設定においてもテキストと同等であることを示す。
論文 参考訳（メタデータ） (2023-06-09T20:43:19Z) - Prediction, Learning, Uniform Convergence, and Scale-sensitive
Dimensions [39.97534972432276]
本稿では,$[0,1]$-valued関数のクラスを学習するための新しい汎用アルゴリズムを提案する。
このアルゴリズムの絶対誤差の一般上界を証明した。
本研究は, 学習の複雑さに関する一般化された一般境界を得るために, 両方のパッキングバウンドをどう適用するかを示す。
論文 参考訳（メタデータ） (2023-04-21T15:51:35Z) - Multiclass Online Learning and Uniform Convergence [34.21248304961989]
対戦型オンライン学習環境におけるマルチクラス分類について検討する。
任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
論文 参考訳（メタデータ） (2023-03-30T21:35:48Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z) - High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文 参考訳（メタデータ） (2020-11-08T16:48:11Z) - Online Sparse Reinforcement Learning [60.44832065993122]
固定地平線, スパース線形決定過程(MDP)におけるオンライン強化学習の難しさについて検討する。
この場合、よく条件付きデータを収集するポリシーが存在するとしても、線形後悔は一般的に避けられないことを示す。
このことは、大規模な行動において、学習の難しさは、優れた探索政策を見つけるのが困難であることに起因していることを示している。
論文 参考訳（メタデータ） (2020-11-08T16:47:42Z) - Near-tight closure bounds for Littlestone and threshold dimensions [59.245101116396555]
二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。
我々の上界は、アロンらによって示される類似境界に対して指数的($k$で)改善を与える。
論文 参考訳（メタデータ） (2020-07-07T17:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。