論文の概要: Multiclass Learnability Beyond the PAC Framework: Universal Rates and
Partial Concept Classes
- arxiv url: http://arxiv.org/abs/2210.02297v2
- Date: Fri, 7 Oct 2022 14:01:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-10 10:21:31.096729
- Title: Multiclass Learnability Beyond the PAC Framework: Universal Rates and
Partial Concept Classes
- Title（参考訳）: pacフレームワークを越えたマルチクラス学習能力:ユニバーサルレートと部分概念クラス
- Authors: Alkis Kalavasis, Grigoris Velegkas, Amin Karbasi
- Abstract要約: 本研究では,有界なラベル数$k$の多クラス分類の問題について,実現可能な設定で検討する。
従来のPACモデルを(a)分布依存学習率、(b)データ依存仮定下での学習率に拡張する。
- 参考スコア（独自算出の注目度）: 31.2676304636432
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we study the problem of multiclass classification with a
bounded number of different labels $k$, in the realizable setting. We extend
the traditional PAC model to a) distribution-dependent learning rates, and b)
learning rates under data-dependent assumptions. First, we consider the
universal learning setting (Bousquet, Hanneke, Moran, van Handel and
Yehudayoff, STOC '21), for which we provide a complete characterization of the
achievable learning rates that holds for every fixed distribution. In
particular, we show the following trichotomy: for any concept class, the
optimal learning rate is either exponential, linear or arbitrarily slow.
Additionally, we provide complexity measures of the underlying hypothesis class
that characterize when these rates occur. Second, we consider the problem of
multiclass classification with structured data (such as data lying on a low
dimensional manifold or satisfying margin conditions), a setting which is
captured by partial concept classes (Alon, Hanneke, Holzman and Moran, FOCS
'21). Partial concepts are functions that can be undefined in certain parts of
the input space. We extend the traditional PAC learnability of total concept
classes to partial concept classes in the multiclass setting and investigate
differences between partial and total concepts.
- Abstract（参考訳）: 本稿では,有界なラベル数$k$のマルチクラス分類の問題について,実現可能な設定で検討する。
従来のPACモデルを拡張します。
a) 分布依存学習率,及び
b) データ依存的前提に基づく学習率
まず,固定分布毎に保持される達成可能な学習率の完全な評価を行う普遍的な学習環境(Bousquet, Hanneke, Moran, van Handel and Yehudayoff, STOC '21)を考える。
特に, 任意の概念クラスに対して, 最適学習速度は指数的, 線形, 任意に遅いかを示す。
さらに,これらの確率が発生することを特徴付ける仮説クラスの複雑性尺度を提供する。
第2に、構造化データ(低次元多様体上やマージン条件を満たすデータなど)を用いたマルチクラス分類の問題について、部分概念クラス(Alon, Hanneke, Holzman and Moran, FOCS '21)で捉えた設定について考察する。
部分概念は入力空間の特定の部分で定義できない関数である。
我々は,多クラス構成において,全概念クラスの従来のpac学習能力を部分概念クラスに拡張し,部分概念と全体概念の差異を検討する。
関連論文リスト
- Composing Novel Classes: A Concept-Driven Approach to Generalized Category Discovery [13.68907640197364]
我々は、ラベルなしデータセットにおける新しいクラスを発見することを目的として、一般化されたカテゴリ発見問題に取り組む。
本稿では,GCDのための新しい概念学習フレームワークであるConceptGCDを紹介し,概念を2つのタイプに分類する。
我々のフレームワークはまず、既知のクラス事前学習モデルにより既知のクラス概念を抽出し、そこから導出可能な概念を生成する。
論文 参考訳（メタデータ） (2024-10-17T07:30:20Z) - Neural Collapse Terminus: A Unified Solution for Class Incremental
Learning and Its Variants [166.916517335816]
本稿では,3つの課題における不整合ジレンマに対する統一解を提案する。
ラベル空間全体の最大等角的クラス間分離を有する固定構造である神経崩壊終端を提案する。
本手法は,データ不均衡やデータ不足にかかわらず,神経崩壊最適度を漸進的に保持する。
論文 参考訳（メタデータ） (2023-08-03T13:09:59Z) - A Characterization of List Learnability [15.368858716555888]
我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。
最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
論文 参考訳（メタデータ） (2022-11-07T21:28:05Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - Learning What Not to Segment: A New Perspective on Few-Shot Segmentation [63.910211095033596]
近年では、FSS ( few-shot segmentation) が広く開発されている。
本稿では,問題を緩和するための新鮮で直接的な知見を提案する。
提案されたアプローチのユニークな性質を踏まえて、より現実的で挑戦的な設定にまで拡張する。
論文 参考訳（メタデータ） (2022-03-15T03:08:27Z) - A Characterization of Multiclass Learnability [18.38631912121182]
DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。
リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。
2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
論文 参考訳（メタデータ） (2022-03-03T07:41:54Z) - Few-Shot Object Detection via Association and DIscrimination [83.8472428718097]
AssociationとDIscriminationによるオブジェクト検出は、新しいクラスごとに2つのステップで識別可能な特徴空間を構築している。
Pascal VOCとMS-COCOデータセットの実験では、FADIは新しいSOTAパフォーマンスを実現し、ショット/スプリットのベースラインを+18.7で大幅に改善した。
論文 参考訳（メタデータ） (2021-11-23T05:04:06Z) - A Theory of PAC Learnability of Partial Concept Classes [30.772106555607458]
我々は、多種多様な学習タスクをモデル化できるように、PAC学習理論を拡張した。
部分概念クラスのPAC学習性を特徴付け,古典的クラスと根本的に異なるアルゴリズム的ランドスケープを明らかにする。
論文 参考訳（メタデータ） (2021-07-18T13:29:26Z) - Partial Is Better Than All: Revisiting Fine-tuning Strategy for Few-shot
Learning [76.98364915566292]
一般的なプラクティスは、まずベースセット上でモデルをトレーニングし、その後、微調整によって新しいクラスに移行することである。
本稿では,基本モデル内の特定の層を凍結あるいは微調整することにより,部分的知識の伝達を提案する。
提案手法の有効性を実証するために, CUB と mini-ImageNet の広範な実験を行った。
論文 参考訳（メタデータ） (2021-02-08T03:27:05Z) - CURI: A Benchmark for Productive Concept Learning Under Uncertainty [33.83721664338612]
我々は、新しい数ショットメタラーニングベンチマーク、コンポジション推論を不確実性の下で導入する(CURI)。
CURIは、疎結合、生産的一般化、学習操作、変数バインディングなどの抽象的な理解を含む、生産的および体系的な一般化の異なる側面を評価します。
また、モデルに依存しない「構成性ギャップ」を定義し、それぞれの軸に沿って分布外分布を一般化することの難しさを評価する。
論文 参考訳（メタデータ） (2020-10-06T16:23:17Z) - Federated Learning with Only Positive Labels [71.63836379169315]
FedAwS(Federated Averaging with Spreadout)という,正のラベルのみを用いたトレーニングのための汎用フレームワークを提案する。
理論的にも経験的にも、FedAwSは、ユーザが負のラベルにアクセス可能な従来の学習のパフォーマンスとほぼ一致していることを示す。
論文 参考訳（メタデータ） (2020-04-21T23:35:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。