論文の概要: A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension
- arxiv url: http://arxiv.org/abs/2212.12631v1
- Date: Sat, 24 Dec 2022 01:56:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-27 14:51:12.711635
- Title: A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension
- Title（参考訳）: vc次元における最大二次サイズラベル付きサンプル圧縮スキーム
- Authors: Farnam Mansouri and Sandra Zilles
- Abstract要約: 本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
- 参考スコア（独自算出の注目度）: 6.522952386973185
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper presents a construction of a proper and stable labelled sample
compression scheme of size $O(\VCD^2)$ for any finite concept class, where
$\VCD$ denotes the Vapnik-Chervonenkis Dimension. The construction is based on
a well-known model of machine teaching, referred to as recursive teaching
dimension. This substantially improves on the currently best known bound on the
size of sample compression schemes (due to Moran and Yehudayoff), which is
exponential in $\VCD$. The long-standing open question whether the smallest
size of a sample compression scheme is in $O(\VCD)$ remains unresolved, but our
results show that research on machine teaching is a promising avenue for the
study of this open problem.
As further evidence of the strong connections between machine teaching and
sample compression, we prove that the model of no-clash teaching, introduced by
Kirkpatrick et al., can be used to define a non-trivial lower bound on the size
of stable sample compression schemes.
- Abstract（参考訳）: 本稿では,任意の有限概念クラスに対して,サイズ$O(\VCD^2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築し,その場合,$\VCD$はVapnik-Chervonenkis次元を表す。
この構成は、再帰的教育次元(recursive teaching dimension)と呼ばれる有名な機械教育モデルに基づいている。
これにより、サンプル圧縮スキーム(moran と yehudayoff による)のサイズで現在知られている範囲を大幅に改善し、これは$\vcd$ で指数関数的である。
サンプル圧縮スキームの最小サイズが$o(\vcd)$であるかどうかという長年の疑問はまだ解決されていないが、機械教育の研究は、このオープン問題の研究にとって有望な道筋であることを示している。
機械教育とサンプル圧縮の強い結びつきの証拠として,Kirkpatrickらによって導入された非クラッチ学習のモデルは,安定なサンプル圧縮スキームのサイズに基づく非自明な下限を定義するために利用できることを示す。
関連論文リスト
- Sample Compression Scheme Reductions [17.389446817000945]
本稿では,多クラス分類,回帰,対向的頑健な学習環境におけるサンプル圧縮方式の新たな削減について述べる。
我々は、逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが、境界サイズの圧縮スキームを持たない概念クラスの例を示す。
論文 参考訳（メタデータ） (2024-10-16T20:14:02Z) - Activations and Gradients Compression for Model-Parallel Training [85.99744701008802]
モデル並列分散トレーニングセットアップにおけるアクティベーションと勾配の同時圧縮が収束に与える影響について検討する。
グラデーションはアクティベーションよりも軽度な圧縮速度を必要とする。
実験では、TopKでトレーニングされたモデルが、推論中に圧縮も適用された場合にのみ正常に動作することが示されている。
論文 参考訳（メタデータ） (2024-01-15T15:54:54Z) - Multiclass Learnability Does Not Imply Sample Compression [5.257719744958368]
仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、小さなサブサンプルのみを保持することができる。
サンプル圧縮に関する類似文は、多クラス仮説クラスには当てはまらないことを示す。
論文 参考訳（メタデータ） (2023-08-12T00:26:08Z) - Unlabelled Sample Compression Schemes for Intersection-Closed Classes
and Extremal Classes [16.684376456880642]
私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。
また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
論文 参考訳（メタデータ） (2022-10-11T13:54:41Z) - Unrolled Compressed Blind-Deconvolution [77.88847247301682]
sparse multi channel blind deconvolution (S-MBD) はレーダー/ソナー/超音波イメージングなどの多くの工学的応用で頻繁に発生する。
そこで本研究では,受信した全信号に対して,はるかに少ない測定値からブラインドリカバリを可能にする圧縮手法を提案する。
論文 参考訳（メタデータ） (2022-09-28T15:16:58Z) - L$_0$onie: Compressing COINs with L$_0$-constraints [0.4568777157687961]
Inlicit Neural Representations (INR)は、ドメインに依存しない圧縮技術の研究を動機付けている。
我々はCOIN圧縮方式の空間制約付き拡張を提案する。
論文 参考訳（メタデータ） (2022-07-08T22:24:56Z) - Estimating the Resize Parameter in End-to-end Learned Image Compression [50.20567320015102]
本稿では,最近の画像圧縮モデルの速度歪みトレードオフをさらに改善する検索自由化フレームワークについて述べる。
提案手法により,Bjontegaard-Deltaレート(BD-rate)を最大10%向上させることができる。
論文 参考訳（メタデータ） (2022-04-26T01:35:02Z) - Labeled sample compression schemes for complexes of oriented matroids [0.04297070083645048]
本稿では,VC次元$d$の複合配向マトロイド(COM)の上部に,適切なラベル付きサンプル圧縮スキームが$d$であることを示す。
これは、サンプル圧縮予想へのステップであり、計算学習理論における最も古いオープンな問題の1つである。
論文 参考訳（メタデータ） (2021-10-28T14:42:55Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Compressing Large Sample Data for Discriminant Analysis [78.12073412066698]
判別分析フレームワーク内での大きなサンプルサイズに起因する計算問題を考察する。
線形および二次判別分析のためのトレーニングサンプル数を削減するための新しい圧縮手法を提案する。
論文 参考訳（メタデータ） (2020-05-08T05:09:08Z) - On Biased Compression for Distributed Learning [55.89300593805943]
バイアス圧縮機が単一ノードと分散設定の両方において線形収束率をもたらすことを初めて示す。
理論的保証と実用性能を期待できる新しいバイアス圧縮機を提案する。
論文 参考訳（メタデータ） (2020-02-27T19:52:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。