論文の概要: Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2306.12968v1
• Date: Sun, 18 Jun 2023 08:46:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-23 14:07:00.701984
• Title: Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Title（参考訳）: ラベル付き確率ブロックモデルにおけるインスタンス最適クラスタリカバリ
• Authors: Kaito Ariu, Alexandre Proutiere, Se-Young Yun
• Abstract要約: 観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
• 参考スコア（独自算出の注目度）: 79.46465138631592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of recovering hidden communities in the Labeled Stochastic Block Model (LSBM) with a finite number of clusters, where cluster sizes grow linearly with the total number $n$ of items. In the LSBM, a label is (independently) observed for each pair of items. Our objective is to devise an efficient algorithm that recovers clusters using the observed labels. To this end, we revisit instance-specific lower bounds on the expected number of misclassified items satisfied by any clustering algorithm. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability. IAC consists of a one-time spectral clustering algorithm followed by an iterative likelihood-based cluster assignment improvement. This approach is based on the instance-specific lower bound and does not require any model parameters, including the number of clusters. By performing the spectral clustering only once, IAC maintains an overall computational complexity of $\mathcal{O}(n \text{polylog}(n))$. We illustrate the effectiveness of our approach through numerical experiments.
• Abstract（参考訳）: 我々は,有限個のクラスタを持つラベル付き確率ブロックモデル (lsbm) において隠れたコミュニティを回復する問題を考える。 LSBMでは、ラベルは(独立して)各アイテムに対して観測される。 我々の目的は、観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案することである。 この目的のために、任意のクラスタリングアルゴリズムで満たされる誤分類項目の期待数について、インスタンス固有の下限を再検討する。 本稿では,これらの下位境界を期待値と高い確率で一致させる最初のアルゴリズムであるIACを提案する。 iacは1回のスペクトルクラスタリングアルゴリズムと反復的確率に基づくクラスタ割り当て改善からなる。 このアプローチはインスタンス固有の低境界に基づいており、クラスタ数を含むモデルパラメータは一切必要としない。 スペクトルクラスタリングを一度だけ実行することで、IACは$\mathcal{O}(n \text{polylog}(n))$の全体的な計算複雑性を維持する。 本手法の有効性を数値実験により示す。

関連論文リスト

• Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
  ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。 以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。 本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-29T21:27:21Z)
• Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle [9.578056676899203]
  オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。 我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-17T08:51:19Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  本稿では,局所凸型ユーザコストを用いた個人化フェデレーション学習のためのアルゴリズム群を提案する。 提案するフレームワークは,異なるユーザのモデルの違いをペナル化する凸クラスタリングの一般化に基づいている。
  論文  参考訳（メタデータ） (2022-02-01T19:25:31Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• On Margin-Based Cluster Recovery with Oracle Queries [22.672233769934845]
  1組の$n$ポイントのオラクルと"これらの2つのポイントは同じクラスタ内にあるのか? 本稿では,任意の凸クラスタを正確な時間で復元するアルゴリズムを提案する。 一般の擬計量空間では、クラスターが凸でない場合や、形状の概念が存在しない場合、$O(log n)$クエリ境界を達成し、確実に最適に近いアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-06-09T08:48:23Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Exact Recovery of Mangled Clusters with Same-Cluster Queries [20.03712152278538]
  半教師付きアクティブクラスタリングフレームワークにおけるクラスタリカバリ問題について検討する。 我々は、$n$ポイントを$k$クラスタに分割するアルゴリズムを設計し、$O(k3 ln k ln n)$oracleクエリと$tildeO(kn + k3)$でクラスタを非分類エラーで復元する。
  論文  参考訳（メタデータ） (2020-06-08T15:27:58Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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