論文の概要: On the Power of SVD in the Stochastic Block Model
- arxiv url: http://arxiv.org/abs/2309.15322v1
- Date: Wed, 27 Sep 2023 00:04:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 17:20:37.778112
- Title: On the Power of SVD in the Stochastic Block Model
- Title（参考訳）: 確率ブロックモデルにおけるSVDのパワーについて
- Authors: Xinyu Mao and Jiapeng Zhang
- Abstract要約: PCAやSVDのようなスペクトルベースの次元削減ツールは、多くのアプリケーションにおけるクラスタリングアルゴリズムの性能を改善する。
対称的な設定では、バニラ-SVDアルゴリズムは全てのクラスタを正しく復元する。
- 参考スコア（独自算出の注目度）: 6.661713888517129
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A popular heuristic method for improving clustering results is to apply
dimensionality reduction before running clustering algorithms. It has been
observed that spectral-based dimensionality reduction tools, such as PCA or
SVD, improve the performance of clustering algorithms in many applications.
This phenomenon indicates that spectral method not only serves as a
dimensionality reduction tool, but also contributes to the clustering procedure
in some sense. It is an interesting question to understand the behavior of
spectral steps in clustering problems.
As an initial step in this direction, this paper studies the power of
vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the
symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This
result answers an open question posed by Van Vu (Combinatorics Probability and
Computing, 2018) in the symmetric setting.
- Abstract（参考訳）: クラスタリング結果を改善するための一般的なヒューリスティックな方法は、クラスタリングアルゴリズムを実行する前に次元削減を適用することである。
多くのアプリケーションにおいて,PCAやSVDなどのスペクトルベース次元減少ツールによってクラスタリングアルゴリズムの性能が向上することが観察されている。
この現象は、スペクトル法が次元減少ツールとして機能するだけでなく、ある意味でのクラスタリング手順にも寄与していることを示している。
クラスタリング問題におけるスペクトルステップの挙動を理解することは興味深い問題である。
この方向の最初のステップとして,確率ブロックモデル(SBM)におけるバニラ-SVDアルゴリズムのパワーについて検討する。
対称的な設定では、バニラ-SVDアルゴリズムは全てのクラスタを正しく復元する。
この結果は、Van Vu(Combinatorics Probability and Computing, 2018)が対称的な設定で提起したオープンな質問に答える。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - A Restarted Large-Scale Spectral Clustering with Self-Guiding and Block
Diagonal Representation [1.115905690697198]
自己誘導とブロック対角表現を備えた再起動クラスタリングフレームワークを提案する。
この戦略の利点は、以前のサイクルから得られた有用なクラスタリング情報を保存できることである。
スペクトルクラスタリングにおける不正確な計算の合理性を示す理論的結果が確立された。
論文 参考訳（メタデータ） (2023-06-27T01:38:52Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral
Clustering [7.632758664232665]
スペクトルクラスタリングにおけるスペクトル解析のための大規模先行固有値問題の解法として,分散Block Chebyshev-Davidsonアルゴリズムを開発した。
チェビシェフ・ダビッドソンアルゴリズムの効率は、推定にコストがかかる固有値スペクトルの事前の知識に依存している。
分散バージョンと並列バージョンは、魅力的なスケーラビリティで開発されている。
論文 参考訳（メタデータ） (2022-12-08T18:06:13Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Kernel learning approaches for summarising and combining posterior
similarity matrices [68.8204255655161]
我々は,ベイズクラスタリングモデルに対するMCMCアルゴリズムの出力を要約するための新しいアプローチを提案するために,後部類似性行列(PSM)の概念を構築した。
我々の研究の重要な貢献は、PSMが正の半定値であり、したがって確率的に動機付けられたカーネル行列を定義するのに使用できることである。
論文 参考訳（メタデータ） (2020-09-27T14:16:14Z) - Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling [19.675277307158435]
本稿では,新しいサンプリング手法であるCentroid Minimum Sum of Squared similarities (CMS3)と,それをいつ使用するかを示す,スケーラブルなNystromベースのクラスタリングアルゴリズムを提案する。
我々のデータセットはデータセットの固有スペクトル形状に依存しており、他の最先端手法と比較して、テストにおいて競合する低ランク近似が得られる。
論文 参考訳（メタデータ） (2020-07-21T17:49:03Z) - An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。
最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。
本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
論文 参考訳（メタデータ） (2020-06-22T20:02:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。