Fugu-MT 論文翻訳(概要): Sketching semidefinite programs for faster clustering

論文の概要: Sketching semidefinite programs for faster clustering

arxiv url: http://arxiv.org/abs/2008.04270v1
Date: Mon, 10 Aug 2020 17:10:29 GMT
ステータス: 処理完了
システム内更新日: 2022-10-31 23:43:59.845737
Title: Sketching semidefinite programs for faster clustering
Title（参考訳）: 高速クラスタリングのための半定値プログラムのスケッチ
Authors: Dustin G. Mixon, Kaiying Xie
Abstract要約: グラフクラスタリング問題(最小二分法)の半定緩和法(半定緩和法)をスケッチする方法を示す。我々の分析は、より多くの信号がある場合、クラスタリングタスクは計算的に負担が少ないというメタステートをサポートします。
参考スコア（独自算出の注目度）: 9.645196221785694
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Many clustering problems enjoy solutions by semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program exactly recovers the planted clustering when the signal strength is sufficiently large. In practice, semidefinite programs are notoriously slow, and so speedups are welcome. In this paper, we show how to sketch a popular semidefinite relaxation of a graph clustering problem known as minimum bisection, and our analysis supports a meta-claim that the clustering task is less computationally burdensome when there is more signal.
Abstract（参考訳）: 多くのクラスタリング問題は半定プログラミングによる解を楽しむ。この静脈内における理論的結果は、信号強度が十分に大きいときに、半定値プログラムが正確にプラントクラスタリングを回復するという信号強度の概念と、しばしば考慮される。実際には半確定プログラムは遅く、スピードアップも歓迎されています。本稿では,最小二分法と呼ばれるグラフクラスタリング問題の半無限緩和法をスケッチする方法を述べるとともに,より多くの信号が存在する場合,クラスタリングタスクは計算的に負担が少ないというメタ宣言を支持する。

関連論文リスト

Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
グラフクラスタリングフレームワーク textitPCon を開発した。既存のソリューションの多くをフレームワークに還元できることを示します。本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
論文参考訳（メタデータ） (2022-11-22T12:45:27Z)
Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。本稿では,分枝切断法に基づく大域的最適化手法を提案する。上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
論文参考訳（メタデータ） (2022-09-19T10:19:06Z)
Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。最近の研究は、低次手法のクラスに対する低い境界を確立している。意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文参考訳（メタデータ） (2021-12-07T18:50:17Z)
An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文参考訳（メタデータ） (2021-11-30T17:08:53Z)
Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。 MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
論文参考訳（メタデータ） (2021-11-19T04:10:18Z)
Correlation Clustering in Constant Many Parallel Rounds [42.10280805559555]
相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
論文参考訳（メタデータ） (2021-06-15T21:45:45Z)
Community Detection with a Subsampled Semidefinite Program [4.077919509379151]
半定的なプログラムは実行が遅い場合が多いため、スケッチなどのテクニックの高速化も考慮されることが多い。 Mixon と Xie は先日,ネットワークのサブサンプル部分グラフ上でのみ半定値プログラムを解き,計算コストを大幅に削減するスケッチフレームワークを提案している。
論文参考訳（メタデータ） (2021-02-02T10:31:57Z)
Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文参考訳（メタデータ） (2020-12-04T15:46:30Z)
(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
論文参考訳（メタデータ） (2020-12-01T13:17:27Z)
Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文参考訳（メタデータ） (2020-05-21T17:51:30Z)
Local Graph Clustering with Network Lasso [90.66817876491052]
局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。 nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
論文参考訳（メタデータ） (2020-04-25T17:52:05Z)

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