論文の概要: Local Correlation Clustering with Asymmetric Classification Errors
- arxiv url: http://arxiv.org/abs/2108.05697v1
- Date: Wed, 11 Aug 2021 12:31:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-14 04:57:35.661795
- Title: Local Correlation Clustering with Asymmetric Classification Errors
- Title（参考訳）: 非対称分類誤差による局所相関クラスタリング
- Authors: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev and Yury
Makarychev
- Abstract要約: 相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。
クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。
我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
- 参考スコア（独自算出の注目度）: 12.277755088736864
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the Correlation Clustering problem, we are given a complete weighted graph
$G$ with its edges labeled as "similar" and "dissimilar" by a noisy binary
classifier. For a clustering $\mathcal{C}$ of graph $G$, a similar edge is in
disagreement with $\mathcal{C}$, if its endpoints belong to distinct clusters;
and a dissimilar edge is in disagreement with $\mathcal{C}$ if its endpoints
belong to the same cluster. The disagreements vector, $\text{dis}$, is a vector
indexed by the vertices of $G$ such that the $v$-th coordinate $\text{dis}_v$
equals the weight of all disagreeing edges incident on $v$. The goal is to
produce a clustering that minimizes the $\ell_p$ norm of the disagreements
vector for $p\geq 1$. We study the $\ell_p$ objective in Correlation Clustering
under the following assumption: Every similar edge has weight in the range of
$[\alpha\mathbf{w},\mathbf{w}]$ and every dissimilar edge has weight at least
$\alpha\mathbf{w}$ (where $\alpha \leq 1$ and $\mathbf{w}>0$ is a scaling
parameter). We give an
$O\left((\frac{1}{\alpha})^{\frac{1}{2}-\frac{1}{2p}}\cdot
\log\frac{1}{\alpha}\right)$ approximation algorithm for this problem.
Furthermore, we show an almost matching convex programming integrality gap.
- Abstract（参考訳）: 相関クラスタリング問題では、雑音二項分類器によって「類似」および「類似」とラベルされたエッジを持つ完全重み付きグラフ$G$が与えられる。
グラフ $G$ のクラスタリング $\mathcal{C}$ の場合、類似のエッジは $\mathcal{C}$ と、そのエンドポイントが別のクラスタに属している場合、類似のエッジは $\mathcal{C}$ と、そのエンドポイントが同じクラスタに属している場合は $\mathcal{C}$ と一致しない。
不一致ベクトル $\text{dis}$ は、$g$ の頂点によってインデックス化されたベクトルであり、$v$-th 座標 $\text{dis}_v$ は、$v$ 上の不一致エッジインシデント全体の重みと等しい。
目標は、$p\geq 1$に対する不一致ベクトルの$\ell_p$ノルムを最小化するクラスタリングを作成することである。
すべての類似エッジは$[\alpha\mathbf{w},\mathbf{w}]$の範囲で重みを持ち、すべての類似エッジは少なくとも$\alpha\mathbf{w}$である(ここで$\alpha \leq 1$と$\mathbf{w}>0$はスケーリングパラメータである)。
我々はこの問題に対して$O\left((\frac{1}{\alpha})^{\frac{1}{2}-\frac{1}{2p}}\cdot \log\frac{1}{\alpha}\right)$近似アルゴリズムを与える。
さらに、ほぼ一致する凸プログラミングの積分性ギャップを示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On Generalization Bounds for Projective Clustering [3.4490841399255823]
ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。
中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
論文 参考訳（メタデータ） (2023-10-13T14:15:54Z) - 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) - Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文 参考訳（メタデータ） (2022-02-03T03:45:45Z) - Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。
これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文 参考訳（メタデータ） (2021-11-08T20:18:10Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
すべての"類似"エッジ$e$は重みを持つ $mathbfw_ein[alpha mathbfw]$と、すべての"類似"エッジ$e$は重みを持つ $mathbfw_egeq alpha mathbfw。
論文 参考訳（メタデータ） (2021-08-11T12:30:52Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。