論文の概要: A Characterization of List Learnability

• arxiv url: http://arxiv.org/abs/2211.04956v2
• Date: Sun, 26 Mar 2023 08:17:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-29 01:59:23.218420
• Title: A Characterization of List Learnability
• Title（参考訳）: リスト学習能力の特徴付け
• Authors: Moses Charikar, Chirag Pabbaraju
• Abstract要約: 我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。 最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
• 参考スコア（独自算出の注目度）: 15.368858716555888
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of $k$ predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to $k$-list learn a hypothesis class? We completely characterize $k$-list learnability in terms of a generalization of DS dimension that we call the $k$-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.
• Abstract（参考訳）: 学習理論における古典的な結果は、二項仮説クラスのPAC学習可能性の等価性とVC次元の有限性を示している。 これをマルチクラスに拡張することはオープンな問題であり、Daniely と Shalev-Shwartz が以前に導入したDS次元による多クラスPAC学習性を特徴付ける最近のブレークスルーで解決された。 この作業では、$k$の予測リストを出力することを目標とするPAC学習について検討する。 リスト学習アルゴリズムは,これまでいくつかの設定で開発されてきたが,近年のマルチクラス学習性評価において,リスト学習が重要な役割を担っている。 k$-listで仮説クラスを学ぶことはいつ可能でしょうか? 我々は、$k$-DS次元と呼ぶDS次元の一般化の観点から、$k$-listの学習可能性を完全に特徴づける。 最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。

関連論文リスト

• A Characterization of List Regression [5.371337604556312]
  リスト回帰の完全な特徴付けを提供する。 我々は、$k$-OIG次元と$k$-fat-shattering次元という2つの次元を提案し、それぞれに実現可能な回帰と$k$-list回帰を最適に特徴付けることを示す。
  論文  参考訳（メタデータ） (2024-09-28T03:19:37Z)
• Beyond Prototypes: Semantic Anchor Regularization for Better Representation Learning [82.29761875805369]
  表現学習の最終的な目標の1つは、クラス内のコンパクトさとクラス間の十分な分離性を達成することである。 本稿では,機能セントロイドとして機能する事前定義されたクラスアンカーを用いて,特徴学習を一方向ガイドする新しい視点を提案する。 提案したSemantic Anchor Regularization (SAR) は,既存モデルのプラグアンドプレイ方式で使用することができる。
  論文  参考訳（メタデータ） (2023-12-19T05:52:38Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。 本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
  論文  参考訳（メタデータ） (2023-07-02T19:26:58Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  そこで我々は,学習のためのチケット付きモデルを提案する。 広義のコンセプトクラスに対して,空間効率のよいチケット付き学習スキームを提供する。
  論文  参考訳（メタデータ） (2023-06-27T18:54:40Z)
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes [5.194264506657145]
  比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。 たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。 比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
  論文  参考訳（メタデータ） (2022-11-16T18:38:24Z)
• 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)
• 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)
• The Information Bottleneck Problem and Its Applications in Machine Learning [53.57797720793437]
  近年,機械学習システムの推論能力が急上昇し,社会の様々な側面において重要な役割を担っている。 情報ボトルネック(IB)理論は、ディープラーニング(DL)システムを分析するための大胆な情報理論パラダイムとして登場した。 本チュートリアルでは,この抽象原理の情報理論的起源と最近のDLへの影響について考察する。
  論文  参考訳（メタデータ） (2020-04-30T16:48:51Z)

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

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