論文の概要: Multiclass Learnability Does Not Imply Sample Compression

• arxiv url: http://arxiv.org/abs/2308.06424v1
• Date: Sat, 12 Aug 2023 00:26:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-15 17:36:28.308576
• Title: Multiclass Learnability Does Not Imply Sample Compression
• Title（参考訳）: 多クラス学習能力はサンプル圧縮を含まない
• Authors: Chirag Pabbaraju
• Abstract要約: 仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、小さなサブサンプルのみを保持することができる。 サンプル圧縮に関する類似文は、多クラス仮説クラスには当てはまらないことを示す。
• 参考スコア（独自算出の注目度）: 5.257719744958368
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the labels on the entire sample can be inferred. The size of the compression scheme is an upper bound on the size of the subsample produced. Every learnable binary hypothesis class (which must necessarily have finite VC dimension) admits a sample compression scheme of size only a finite function of its VC dimension, independent of the sample size. For multiclass hypothesis classes, the analog of VC dimension is the DS dimension. We show that the analogous statement pertaining to sample compression is not true for multiclass hypothesis classes: every learnable multiclass hypothesis class, which must necessarily have finite DS dimension, does not admit a sample compression scheme of size only a finite function of its DS dimension.
• Abstract（参考訳）: 仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、サンプル全体のラベルを推測できる小さなサブサンプルのみを保持することができる。 圧縮スキームのサイズは、生成されたサブサンプルのサイズの上限である。 すべての学習可能な二項仮説クラス(必ずしも有限VC次元を持つ必要がある)は、標本サイズとは独立に、そのVC次元の有限関数のみの大きさのサンプル圧縮スキームを許容する。 多クラス仮説クラスでは、VC次元のアナログはDS次元である。 サンプル圧縮に関する類似のステートメントは、多クラス仮説クラスには当てはまらないことが示されている: すべての学習可能な多クラス仮説クラスは、必ずしも有限のds次元を持つ必要があるが、そのds次元の有限関数のみの大きさのサンプル圧縮スキームを認めない。

関連論文リスト

• Dual VC Dimension Obstructs Sample Compression by Embeddings [25.63430474763066]
  本研究は、特に極端クラスに焦点を当てた、良好なVCクラスに任意のVCクラスを組み込むことについて研究する。 すべての$d$に対して、$d$の指数よりも小さい任意の極端なVC次元のクラスに組み込むことができないVC次元の$d$を持つクラスが存在することを証明している。 この結果は学習理論において重要な意味を持ち、長期にわたるサンプル圧縮予想に対処するための最も広範囲に研究されたアプローチの1つの基本的限界を明らかにする。
  論文  参考訳（メタデータ） (2024-05-27T12:38:25Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension [6.522952386973185]
  本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
  論文  参考訳（メタデータ） (2022-12-24T01:56:02Z)
• Differentially-Private Bayes Consistency [70.92545332158217]
  差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。 ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
  論文  参考訳（メタデータ） (2022-12-08T11:57:30Z)
• 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)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
  論文  参考訳（メタデータ） (2022-10-11T13:54:41Z)
• Intrinsic Dimension Estimation [92.87600241234344]
  内在次元の新しい推定器を導入し, 有限標本, 非漸近保証を提供する。 次に、本手法を適用して、データ固有の次元に依存するGAN(Generative Adversarial Networks)に対する新しいサンプル複雑性境界を求める。
  論文  参考訳（メタデータ） (2021-06-08T00:05:39Z)
• 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)
• Rethinking preventing class-collapsing in metric learning with margin-based losses [81.22825616879936]
  メトリクス学習は、視覚的に類似したインスタンスが近接し、異なるインスタンスが分離した埋め込みを求める。 マージンベースの損失は、クラスの全サンプルを埋め込み空間の単一点に投影する傾向がある。 そこで本研究では,各サンプルが最寄りの同一クラスをバッチで選択するように,埋め込み損失の簡易な修正を提案する。
  論文  参考訳（メタデータ） (2020-06-09T09:59:25Z)
• Compressing Large Sample Data for Discriminant Analysis [78.12073412066698]
  判別分析フレームワーク内での大きなサンプルサイズに起因する計算問題を考察する。 線形および二次判別分析のためのトレーニングサンプル数を削減するための新しい圧縮手法を提案する。
  論文  参考訳（メタデータ） (2020-05-08T05:09:08Z)
• Agnostic Sample Compression Schemes for Regression [30.539063844697772]
  他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。 $ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
  論文  参考訳（メタデータ） (2018-10-03T11:46:59Z)

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

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