論文の概要: Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes

• arxiv url: http://arxiv.org/abs/2210.05455v1
• Date: Tue, 11 Oct 2022 13:54:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 17:39:54.327204
• Title: Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
• Title（参考訳）: 交叉閉クラスと極値クラスに対するラベルなしサンプル圧縮スキーム
• Authors: J. Hyam Rubinstein and Benjamin I. P. Rubinstein
• Abstract要約: 私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
• 参考スコア（独自算出の注目度）: 16.684376456880642
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The sample compressibility of concept classes plays an important role in learning theory, as a sufficient condition for PAC learnability, and more recently as an avenue for robust generalisation in adaptive data analysis. Whether compression schemes of size $O(d)$ must necessarily exist for all classes of VC dimension $d$ is unknown, but conjectured to be true by Warmuth. Recently Chalopin, Chepoi, Moran, and Warmuth (2018) gave a beautiful unlabelled sample compression scheme of size VC dimension for all maximum classes: classes that meet the Sauer-Shelah-Perles Lemma with equality. They also offered a counterexample to compression schemes based on a promising approach known as corner peeling. In this paper we simplify and extend their proof technique to deal with so-called extremal classes of VC dimension $d$ which contain maximum classes of VC dimension $d-1$. A criterion is given which would imply that all extremal classes admit unlabelled compression schemes of size $d$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.
• Abstract（参考訳）: 概念クラスのサンプル圧縮性は、PAC学習可能性の十分な条件として、そして最近では適応データ解析における堅牢な一般化の道として、学習理論において重要な役割を果たす。 サイズ$O(d)$の圧縮スキームが、VC次元$d$のすべてのクラスに必ず存在するかどうかは不明だが、Warmuthによって推測される。 最近、chalopin, chepoi, moran, and warmuth (2018) は、全ての最大クラスのvc次元の大きさのラベルなしのサンプル圧縮スキームを美しいものにした: sauer-shelah-perles lemma に等しく一致するクラス。 彼らはまた、コーナー剥離と呼ばれる有望なアプローチに基づく圧縮スキームに対する反例を提供した。 本稿では,VC次元が$d-1$の最大クラスを含むいわゆるVC次元が$d$の極限クラスを扱うために,それらの証明手法を簡素化し拡張する。 条件は、すべての極端クラスが$d$の非ラベリング圧縮スキームを許容することを意味する。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容する。

関連論文リスト

• Sample Compression Scheme Reductions [17.389446817000945]
  本稿では,多クラス分類,回帰,対向的頑健な学習環境におけるサンプル圧縮方式の新たな削減について述べる。 我々は、逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが、境界サイズの圧縮スキームを持たない概念クラスの例を示す。
  論文  参考訳（メタデータ） (2024-10-16T20:14:02Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。 任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。 解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
  論文  参考訳（メタデータ） (2024-06-15T06:43:45Z)
• Dual VC Dimension Obstructs Sample Compression by Embeddings [25.63430474763066]
  本研究は、特に極端クラスに焦点を当てた、良好なVCクラスに任意のVCクラスを組み込むことについて研究する。 すべての$d$に対して、$d$の指数よりも小さい任意の極端なVC次元のクラスに組み込むことができないVC次元の$d$を持つクラスが存在することを証明している。 この結果は学習理論において重要な意味を持ち、長期にわたるサンプル圧縮予想に対処するための最も広範囲に研究されたアプローチの1つの基本的限界を明らかにする。
  論文  参考訳（メタデータ） (2024-05-27T12:38:25Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Multiclass Learnability Does Not Imply Sample Compression [5.257719744958368]
  仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、小さなサブサンプルのみを保持することができる。 サンプル圧縮に関する類似文は、多クラス仮説クラスには当てはまらないことを示す。
  論文  参考訳（メタデータ） (2023-08-12T00:26:08Z)
• Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension [86.3584476711976]
  一般関数クラスと有界エリューダを用いた非線形帯域幅とモデルベースエピソードRLのアルゴリズムを提案する。 達成された一様PACサンプルの複雑性は、最先端の後悔境界や、線形ケースに還元された場合のサンプルの複雑さを保証するという意味で厳密である。
  論文  参考訳（メタデータ） (2023-05-15T05:07:45Z)
• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension [6.522952386973185]
  本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
  論文  参考訳（メタデータ） (2022-12-24T01:56:02Z)
• Optimally compressing VC classes [0.0]
  Littlestone と Warmuth の予想を解くと、VC-dimension $d$ の任意の概念クラスは、サンプル圧縮スキームが$d$ であることを示す。
  論文  参考訳（メタデータ） (2022-01-11T18:56:08Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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