Fugu-MT 論文翻訳(概要): Sample compression schemes for balls in graphs

論文の概要: 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の近似的なサンプル圧縮スキームを設計する。

関連論文リスト

Sample Compression Scheme Reductions [17.389446817000945]
本稿では,多クラス分類,回帰,対向的頑健な学習環境におけるサンプル圧縮方式の新たな削減について述べる。我々は、逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが、境界サイズの圧縮スキームを持たない概念クラスの例を示す。
論文参考訳（メタデータ） (2024-10-16T20:14:02Z)
Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文参考訳（メタデータ） (2024-08-03T20:08:02Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文参考訳（メタデータ） (2023-04-17T10:38:08Z)
Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文参考訳（メタデータ） (2022-08-18T09:19:01Z)
Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文参考訳（メタデータ） (2022-02-22T04:14:45Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文参考訳（メタデータ） (2021-10-07T05:49:55Z)
Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文参考訳（メタデータ） (2021-06-25T17:59:16Z)
Deep Learning Meets Projective Clustering [66.726500395069]
NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
論文参考訳（メタデータ） (2020-10-08T22:47:48Z)
Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文参考訳（メタデータ） (2020-06-17T09:21:00Z)
Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文参考訳（メタデータ） (2020-04-13T08:06:29Z)

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