論文の概要: A Characterization of Multiclass Learnability
- arxiv url: http://arxiv.org/abs/2203.01550v1
- Date: Thu, 3 Mar 2022 07:41:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-05 06:24:07.195640
- Title: A Characterization of Multiclass Learnability
- Title（参考訳）: 多クラス学習能力のキャラクタリゼーション
- Authors: Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran and Amir
Yehudayoff
- Abstract要約: DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。
リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。
2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
- 参考スコア（独自算出の注目度）: 18.38631912121182
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A seminal result in learning theory characterizes the PAC learnability of
binary classes through the Vapnik-Chervonenkis dimension. Extending this
characterization to the general multiclass setting has been open since the
pioneering works on multiclass PAC learning in the late 1980s. This work
resolves this problem: we characterize multiclass PAC learnability through the
DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz
(2014).
The classical characterization of the binary case boils down to empirical
risk minimization. In contrast, our characterization of the multiclass case
involves a variety of algorithmic ideas; these include a natural setting we
call list PAC learning. In the list learning setting, instead of predicting a
single outcome for a given unseen input, the goal is to provide a short menu of
predictions.
Our second main result concerns the Natarajan dimension, which has been a
central candidate for characterizing multiclass learnability. This dimension
was introduced by Natarajan (1988) as a barrier for PAC learning. Whether the
Natarajan dimension characterizes PAC learnability in general has been posed as
an open question in several papers since. This work provides a negative answer:
we construct a non-learnable class with Natarajan dimension one.
For the construction, we identify a fundamental connection between concept
classes and topology (i.e., colorful simplicial complexes). We crucially rely
on a deep and involved construction of hyperbolic pseudo-manifolds by
Januszkiewicz and Swiatkowski. It is interesting that hyperbolicity is directly
related to learning problems that are difficult to solve although no obvious
barriers exist. This is another demonstration of the fruitful links machine
learning has with different areas in mathematics.
- Abstract（参考訳）: 学習理論におけるセミナルな結果は、Vapnik-Chervonenkis次元を通してバイナリクラスのPAC学習可能性を特徴づける。
この特徴を一般的なマルチクラス設定に拡張することは、1980年代後半のマルチクラスpac学習の先駆的研究から始まった。
DS次元(Daniely and Shalev-Shwartz (2014) によって定義される組合せ次元)を通して多クラスPAC学習可能性を特徴づける。
二項の場合の古典的特徴は、経験的リスク最小化に沸騰する。
対照的に、我々のマルチクラスケースの特徴付けには、様々なアルゴリズム的アイデアが含まれています。
リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。
第2の主な成果は,多クラス学習可能性の特徴付けの中心的候補であるナタラジャン次元に関するものです。
この次元はNatarajan (1988)によってPAC学習の障壁として導入された。
ナタラジャン次元が一般のPAC学習可能性を特徴づけるかどうかについては、いくつかの論文でオープンな疑問として提起されている。
この研究は否定的な答えを与える: ナタラジャン次元 1 の非学習可能なクラスを構築する。
構成に関して、概念クラスとトポロジー(つまり、カラフルな単体複体)の基本的な関係を同定する。
我々はJanuszkiewicz と Swiatkowski による双曲的擬多様体の深くて関連する構成に決定的に依存する。
双曲性は、明らかな障壁がないにもかかわらず解決が難しい学習問題に直接関係していることは興味深い。
これは、機械学習が数学の様々な分野に持つ実りあるリンクのもうひとつの実演である。
関連論文リスト
- Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。
一般分類タスクにおいては,DP学習性はオンライン学習性を意味することを示す。
論文 参考訳（メタデータ） (2024-07-10T15:43:30Z) - Beyond Prototypes: Semantic Anchor Regularization for Better
Representation Learning [82.29761875805369]
表現学習の最終的な目標の1つは、クラス内のコンパクトさとクラス間の十分な分離性を達成することである。
本稿では,機能セントロイドとして機能する事前定義されたクラスアンカーを用いて,特徴学習を一方向ガイドする新しい視点を提案する。
提案したSemantic Anchor Regularization (SAR) は,既存モデルのプラグアンドプレイ方式で使用することができる。
論文 参考訳（メタデータ） (2023-12-19T05:52:38Z) - Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。
まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。
オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
論文 参考訳（メタデータ） (2023-07-07T21:39:25Z) - Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。
本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
論文 参考訳（メタデータ） (2023-07-02T19:26:58Z) - Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。
まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。
第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
論文 参考訳（メタデータ） (2023-02-06T02:52:36Z) - A Characterization of List Learnability [15.368858716555888]
我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。
最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
論文 参考訳（メタデータ） (2022-11-07T21:28:05Z) - Multiclass Learnability Beyond the PAC Framework: Universal Rates and
Partial Concept Classes [31.2676304636432]
本研究では,有界なラベル数$k$の多クラス分類の問題について,実現可能な設定で検討する。
従来のPACモデルを(a)分布依存学習率、(b)データ依存仮定下での学習率に拡張する。
論文 参考訳（メタデータ） (2022-10-05T14:36:27Z) - 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) - Multiclass versus Binary Differentially Private PAC Learning [32.22526322514124]
多クラス差分プライベートPAC学習からバイナリプライベートPAC学習への一般化について述べる。
我々の証明は、Ben-Davidらによる[JCSS '95]で定義された$Psi$-dimensionの概念をオンライン設定に拡張し、その一般的な性質を探求する。
論文 参考訳（メタデータ） (2021-07-22T18:06:39Z) - A Theory of PAC Learnability of Partial Concept Classes [30.772106555607458]
我々は、多種多様な学習タスクをモデル化できるように、PAC学習理論を拡張した。
部分概念クラスのPAC学習性を特徴付け,古典的クラスと根本的に異なるアルゴリズム的ランドスケープを明らかにする。
論文 参考訳（メタデータ） (2021-07-18T13:29:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。