論文の概要: Correlation Clustering with Asymmetric Classification Errors

• arxiv url: http://arxiv.org/abs/2108.05696v1
• Date: Wed, 11 Aug 2021 12:30:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-14 05:24:07.366842
• Title: Correlation Clustering with Asymmetric Classification Errors
• Title（参考訳）: 非対称分類誤差による相関クラスタリング
• Authors: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev and Yury Makarychev
• Abstract要約: すべての"類似"エッジ$e$は重みを持つ $mathbfw_ein[alpha mathbfw]$と、すべての"類似"エッジ$e$は重みを持つ $mathbfw_egeq alpha mathbfw。
• 参考スコア（独自算出の注目度）: 12.277755088736864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the Correlation Clustering problem, we are given a weighted graph $G$ with its edges labeled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar" edge $e$ has weight $\mathbf{w}_e\in[\alpha \mathbf{w}, \mathbf{w}]$ and every "dissimilar" edge $e$ has weight $\mathbf{w}_e\geq \alpha \mathbf{w}$ (where $\alpha\leq 1$ and $\mathbf{w}>0$ is a scaling parameter). We give a $(3 + 2 \log_e (1/\alpha))$ approximation algorithm for this problem. This assumption captures well the scenario when classification errors are asymmetric. Additionally, we show an asymptotically matching Linear Programming integrality gap of $\Omega(\log 1/\alpha)$.
• Abstract（参考訳）: 相関クラスタリング問題では、二項分類器によって「類似」あるいは「類似」とラベルされたエッジを持つ重み付きグラフ$G$が与えられる。 目的は、クラスタ間の「類似」エッジの重みとクラスタ内の「類似」エッジの重みの和である「異」エッジの重みを最小化するクラスタリングを作ることである。 すべての "similar" edge $e$ has weight $\mathbf{w}_e\in[\alpha \mathbf{w}, \mathbf{w}]$ およびすべての "dissimilar" edge $e$ has weight $\mathbf{w}_e\geq \alpha \mathbf{w}$ (ここで $\alpha\leq 1$ と $\mathbf{w}>0$ はスケーリングパラメータである)。 この問題に対して$(3 + 2 \log_e (1/\alpha))$近似アルゴリズムを与える。 この仮定は、分類誤差が非対称である場合のシナリオをうまく捉えている。 さらに、漸近的に一致する線形計画積分性ギャップ $\omega(\log 1/\alpha)$ を示す。

関連論文リスト

• Multilayer Correlation Clustering [12.492037397168579]
  相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。 本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。 目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
  論文  参考訳（メタデータ） (2024-04-25T15:25:30Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
  学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。 本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。 我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
  論文  参考訳（メタデータ） (2022-10-31T03:00:11Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Local Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
  相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。 クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。 我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
  論文  参考訳（メタデータ） (2021-08-11T12:31:48Z)

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

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