論文の概要: Universal Rates for Multiclass Learning

• arxiv url: http://arxiv.org/abs/2307.02066v1
• Date: Wed, 5 Jul 2023 07:12:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-06 14:42:27.959090
• Title: Universal Rates for Multiclass Learning
• Title（参考訳）: 多クラス学習のためのユニバーサルレート
• Authors: Steve Hanneke, Shay Moran, Qian Zhang
• Abstract要約: マルチクラス分類のための普遍的レートについて検討し、全ての仮説クラスに対して最適なレート(ログファクタまで)を確立する。 また、無限のグラフ・リトルストーン(GL)木と無限のナタラジャン・リトルストーン(NL)木との同値性についても、未解決の問題も解決する。
• 参考スコア（独自算出の注目度）: 28.18556410009232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study universal rates for multiclass classification, establishing the optimal rates (up to log factors) for all hypothesis classes. This generalizes previous results on binary classification (Bousquet, Hanneke, Moran, van Handel, and Yehudayoff, 2021), and resolves an open question studied by Kalavasis, Velegkas, and Karbasi (2022) who handled the multiclass setting with a bounded number of class labels. In contrast, our result applies for any countable label space. Even for finite label space, our proofs provide a more precise bounds on the learning curves, as they do not depend on the number of labels. Specifically, we show that any class admits exponential rates if and only if it has no infinite Littlestone tree, and admits (near-)linear rates if and only if it has no infinite Daniely-Shalev-Shwartz-Littleston (DSL) tree, and otherwise requires arbitrarily slow rates. DSL trees are a new structure we define in this work, in which each node of the tree is given by a pseudo-cube of possible classifications of a given set of points. Pseudo-cubes are a structure, rooted in the work of Daniely and Shalev-Shwartz (2014), and recently shown by Brukhim, Carmon, Dinur, Moran, and Yehudayoff (2022) to characterize PAC learnability (i.e., uniform rates) for multiclass classification. We also resolve an open question of Kalavasis, Velegkas, and Karbasi (2022) regarding the equivalence of classes having infinite Graph-Littlestone (GL) trees versus infinite Natarajan-Littlestone (NL) trees, showing that they are indeed equivalent.
• Abstract（参考訳）: 我々は,マルチクラス分類のための普遍的レートを研究し,すべての仮説クラスに対する最適レート(ログ係数まで)を確立した。 これは二分分類(bousquet, hanneke, moran, van handel, yehudayoff, 2021)の以前の結果を一般化し、クラスラベルを限定したマルチクラス設定を扱うkalavasis, velegkas, karbasi (2022) によって研究されたオープン質問を解決する。 対照的に、この結果は任意の可算ラベル空間に適用できる。 有限ラベル空間においても、この証明はラベルの数に依存しないため、学習曲線のより正確な境界を与える。 具体的には、任意のクラスが指数率を許容し、無限のリトルストーン木が存在しないことと、無限のダニエル=シャレフ=シュワルツ=リトルストン(DSL)木が存在しないこと、そしてそれ以外は任意に遅い速度を必要とすることが示される。 DSLツリーは、この作業で定義した新しい構造であり、ツリーの各ノードは、与えられた点の集合の可能な分類の擬似キューブによって与えられる。 Pseudo-cubes は Daniely と Shalev-Shwartz (2014) の業績に根ざした構造であり、最近 Brukhim, Carmon, Dinur, Moran, and Yehudayoff (2022) によって示され、多クラス分類におけるPAC学習可能性(すなわち一様率)を特徴づけている。 また、無限のグラフ・リトルストーン(GL)木と無限のナタラジャン・リトルストーン(NL)木との同値性について、カラバシス、ヴェレグカス、カルバシ(2022年)の開問題も解決し、それらが真に同値であることを示す。

関連論文リスト

• Harnessing Superclasses for Learning from Hierarchical Databases [1.835004446596942]
  多くの大規模分類問題において、クラスは既知の階層に整理され、通常木として表される。 この種の教師付き階層分類の損失について紹介する。 提案手法では,クロスエントロピーの損失に比較して,計算コストの大幅な増大は伴わない。
  論文  参考訳（メタデータ） (2024-11-25T14:39:52Z)
• Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
  この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。 一般分類タスクにおいては,DP学習性はオンライン学習性を意味することを示す。
  論文  参考訳（メタデータ） (2024-07-10T15:43:30Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Contrastive Meta-Learning for Few-shot Node Classification [54.36506013228169]
  少ないショットノード分類は、限定されたラベル付きノードのみを参照としてグラフ上のノードのラベルを予測することを目的としている。 グラフ上にCOSMICという新しい対照的なメタラーニングフレームワークを2つの重要な設計で作成する。
  論文  参考訳（メタデータ） (2023-06-27T02:22:45Z)
• GraphSHA: Synthesizing Harder Samples for Class-Imbalanced Node Classification [64.85392028383164]
  クラス不均衡は、いくつかのクラスが他のクラスよりもはるかに少ないインスタンスを持つ現象である。 近年の研究では、既成のグラフニューラルネットワーク(GNN)が、マイナーなクラスサンプルを以下に表現することが確認されている。 HArderマイナーサンプルの合成によるGraphSHAの汎用化を提案する。
  論文  参考訳（メタデータ） (2023-06-16T04:05:58Z)
• Multiclass Online Learning and Uniform Convergence [34.21248304961989]
  対戦型オンライン学習環境におけるマルチクラス分類について検討する。 任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
  論文  参考訳（メタデータ） (2023-03-30T21:35:48Z)
• Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes [31.2676304636432]
  本研究では,有界なラベル数$k$の多クラス分類の問題について,実現可能な設定で検討する。 従来のPACモデルを(a)分布依存学習率、(b)データ依存仮定下での学習率に拡張する。
  論文  参考訳（メタデータ） (2022-10-05T14:36:27Z)
• A Characterization of Multiclass Learnability [18.38631912121182]
  DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。 リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。 2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
  論文  参考訳（メタデータ） (2022-03-03T07:41:54Z)
• Monotone Learning [86.77705135626186]
  各学習アルゴリズムAは、同様の性能で単調なクラスに変換可能であることを示す。 これは、パフォーマンスを損なうことなく、確実に非単調な振る舞いを回避できることを示している。
  論文  参考訳（メタデータ） (2022-02-10T18:51:57Z)
• 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)
• Forest R-CNN: Large-Vocabulary Long-Tailed Object Detection and Instance Segmentation [75.93960390191262]
  我々は、オブジェクトカテゴリ間の関係に関する事前知識を利用して、きめ細かいクラスを粗い親クラスにクラスタリングする。 そこで本研究では,NMS再サンプリング法を提案する。 提案手法はフォレストR-CNNと呼ばれ,ほとんどのオブジェクト認識モデルに適用可能なプラグイン・アンド・プレイモジュールとして機能する。
  論文  参考訳（メタデータ） (2020-08-13T03:52:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。