論文の概要: Sample compression schemes for balls in graphs
- arxiv url: http://arxiv.org/abs/2206.13254v1
- Date: Mon, 27 Jun 2022 12:39:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-28 16:42:52.986111
- Title: Sample compression schemes for balls in graphs
- Title(参考訳): グラフ内の球に対するサンプル圧縮スキーム
- Authors: J\'er\'emie Chalopin, Victor Chepoi, Fionn Mc Inerney, S\'ebastien
Ratel, Yann Vax\`es
- Abstract要約: 我々は、VC次元$d$の任意の集合族が、サイズ$O(d)$のサンプル圧縮スキームを許容するかどうかを研究する。
任意の半径$r$の球に対して、木に2ドル、サイクルに3ドル、インターバルグラフに4ドル、サイクルに6ドル、キューブのない中央値グラフに22ドルという適切なサンプル圧縮スキームを設計する。
- 参考スコア(独自算出の注目度): 0.03499870393443267
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the open problems in machine learning is whether any set-family of
VC-dimension $d$ admits a sample compression scheme of size~$O(d)$. In this
paper, we study this problem for balls in graphs. For balls of arbitrary radius
$r$, we design proper sample compression schemes of size $2$ for trees, of size
$3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of
cycles, and of size $22$ for cube-free median graphs. For balls of a given
radius, we design proper labeled sample compression schemes of size $2$ for
trees and of size $4$ for interval graphs. We also design approximate sample
compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.
- Abstract(参考訳): 機械学習におけるオープンな問題の1つは、VC次元$d$のセットファミリーが、サイズ~$O(d)$のサンプル圧縮スキームを認めるかどうかである。
本稿では,球体グラフのこの問題について考察する。
任意半径$r$のボールについては、木のサイズが$$、サイクルサイズが$$、インターバルグラフが$$$、サイクルツリーが$$$、キューブフリーの中央値グラフが$$$2$という適切なサンプル圧縮スキームを設計します。
与えられた半径の球に対して、木に対して2ドル、インターバルグラフに対して4ドルという適切なラベル付きサンプル圧縮スキームを設計する。
また、$$\delta$-hyperbolic graph の球に対して、サイズ2の近似的なサンプル圧縮スキームを設計する。
関連論文リスト
- Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳(メタデータ) (2024-02-01T03:39:01Z) - Graph Generation with $K^2$-trees [14.926940390573385]
K2$-tree表現を利用した新しいグラフ生成手法を提案する。
また、プルーニング、フラットニング、トークン化プロセスを組み込んだシーケンシャルな$K2$-treerepresentationを提示する。
グラフ生成の優位性を確認するため,本アルゴリズムを4つの一般および2つの分子グラフデータセット上で広範囲に評価した。
論文 参考訳(メタデータ) (2023-05-30T15:36:37Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳(メタデータ) (2023-02-13T22:51:07Z) - A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension [6.522952386973185]
本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
論文 参考訳(メタデータ) (2022-12-24T01:56:02Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳(メタデータ) (2022-08-18T09:19:01Z) - Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using
Graph-based Machine Learning [1.52292571922932]
本稿では,グラフニューラルネットワークに基づくアルゴリズムであるPYGONについて述べる。
我々はPYGONが$Thetaleft(sqrtnright)$を復元できることを示し、$n$は背景グラフのサイズである。
また、同じアルゴリズムで、$Thetaleft(sqrtnright)$の複数の植字されたサブグラフを、有向および無向の両方で復元できることを示す。
論文 参考訳(メタデータ) (2022-01-05T21:11:23Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Partition and Code: learning how to compress graphs [50.29024357495154]
まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。
提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
論文 参考訳(メタデータ) (2021-07-05T11:41:16Z) - WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement [75.12782480740822]
We design novel composable sketches for WOR $ell_p$ sample。
私たちのスケッチは、サンプルサイズと直線的にしか成長しないサイズです。
我々の方法は、最初に$p>1$の重要なレギュレーションでWORサンプリングを提供し、最初に$p>0$で署名された更新を処理する。
論文 参考訳(メタデータ) (2020-07-14T00:19:27Z) - Agnostic Sample Compression Schemes for Regression [30.539063844697772]
他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。
$ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
論文 参考訳(メタデータ) (2018-10-03T11:46:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。