論文の概要: On the Computability of Multiclass PAC Learning

• arxiv url: http://arxiv.org/abs/2502.06089v1
• Date: Mon, 10 Feb 2025 01:07:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:35:08.808468
• Title: On the Computability of Multiclass PAC Learning
• Title（参考訳）: マルチクラスPAC学習の計算可能性について
• Authors: Pascale Gourdeau, Tosca Lechner, Ruth Urner,
• Abstract要約: 最近導入された計算可能PAC(CPAC)学習フレームワークでは、学習者と出力する関数の両方が計算可能であることが求められている。 識別器の計算可能次元がCPAC学習を特徴付けることを示す。
• 参考スコア（独自算出の注目度）: 9.507869508188266
• License:
• Abstract: We study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984). In the recently introduced computable PAC (CPAC) learning framework of Agarwal et al. (2020), both learners and the functions they output are required to be computable. We focus on the case of finite label space and start by proposing a computable version of the Natarajan dimension and showing that it characterizes CPAC learnability in this setting. We further generalize this result by establishing a meta-characterization of CPAC learnability for a certain family of dimensions: computable distinguishers. Distinguishers were defined by Ben-David et al. (1992) as a certain family of embeddings of the label space, with each embedding giving rise to a dimension. It was shown that the finiteness of each such dimension characterizes multiclass PAC learnability for finite label space in the non-computable setting. We show that the corresponding computable dimensions for distinguishers characterize CPAC learning. We conclude our analysis by proving that the DS dimension, which characterizes PAC learnability for infinite label space, cannot be expressed as a distinguisher (even in the case of finite label space).
• Abstract（参考訳）: 本稿では,Valiant(1984)のPAC学習フレームワークにおける計算可能な多クラス学習可能性の問題について検討する。 Agarwal et al (2020)の最近導入された計算可能PAC(CPAC)学習フレームワークでは、学習者と出力する関数の両方が計算可能であることが求められている。 本稿では,有限ラベル空間の場合に着目し,まずナタラジャン次元の計算可能なバージョンを提案し,この設定においてCPAC学習性を特徴付けることを示す。 さらに,ある次元の族に対するCPAC学習可能性のメタキャラクタリゼーションを確立することで,この結果を一般化する。 区別器は Ben-David et al (1992) によってラベル空間の埋め込みの特定の族として定義され、それぞれの埋め込みは次元を生じる。 これらの次元の有限性は、計算不可能な設定において有限ラベル空間に対する多クラスPAC学習性を特徴付けることを示した。 識別器の計算可能次元がCPAC学習を特徴付けることを示す。 我々は、無限ラベル空間のPAC学習性を特徴付けるDS次元が(有限ラベル空間の場合でさえ)微分器として表現できないことを証明して、解析を結論付ける。

関連論文リスト

• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings [0.0]
  本稿では,概念クラスやドメインセットに制約を加えることなく,VC次元を近似的に計算する手法を開発した。 提案手法は,経験的リスク最小化(Empirical Risk Minimization,ERM)学習パラダイムが,概念クラスの破砕特性を特徴付ける新しいツールとして利用できることを示すものである。
  論文  参考訳（メタデータ） (2023-08-19T14:57:24Z)
• A Geometric Notion of Causal Probing [91.14470073637236]
  言語モデルの表現空間では、動詞数のような概念に関するすべての情報が線形部分空間に符号化される。 理想線型概念部分空間を特徴づける内在的基準のセットを与える。 LEACEは概念情報の約半分を含む1次元の部分空間を返す。
  論文  参考訳（メタデータ） (2023-07-27T17:57:57Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
  論文  参考訳（メタデータ） (2023-07-07T21:39:25Z)
• 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 Multiclass Learnability [18.38631912121182]
  DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。 リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。 2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
  論文  参考訳（メタデータ） (2022-03-03T07:41:54Z)
• On characterizations of learnability with computable learners [0.0]
  Agarwalらによる計算可能PAC(CPAC)学習について検討した。 我々は,強いCPAC学習という,密接に関連する概念を特徴づける。 我々は(計算可能な)PAC学習可能性の不決定性について考察する。
  論文  参考訳（メタデータ） (2022-02-10T13:57:20Z)
• On computable learning of continuous features [2.278415626131568]
  計算可能距離空間上の二項分類のための計算可能PAC学習の定義を導入する。 また、計算可能なサンプル関数を持つ適切なPAC学習者を認めない仮説クラスを提示する。
  論文  参考訳（メタデータ） (2021-11-24T02:28:21Z)
• EigenGAN: Layer-Wise Eigen-Learning for GANs [84.33920839885619]
  EigenGANは、異なる発電機層から解釈可能で制御可能な寸法を無監督にマイニングすることができます。 特定の固有次元の係数をトラバースすることで、ジェネレータは特定の意味属性に対応する連続的な変化を伴うサンプルを生成することができる。
  論文  参考訳（メタデータ） (2021-04-26T11:14:37Z)
• 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)
• Towards a combinatorial characterization of bounded memory learning [21.031088723668486]
  我々は,境界記憶学習を特徴付ける次元を開発する。 候補解に対して上界と下界の両方を証明します。 我々は、我々の特徴がより広いパラメータの体系で成り立つと推測する。
  論文  参考訳（メタデータ） (2020-02-08T09:04:21Z)

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

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