論文の概要: Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming

• arxiv url: http://arxiv.org/abs/2305.18436v1
• Date: Mon, 29 May 2023 00:39:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 21:03:40.565589
• Title: Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming
• Title（参考訳）: 非負の低ランク半定計画法による統計的K平均クラスタリング
• Authors: Yubo Zhuang, Xiaohui Chen, Yun Yang, Richard Y. Zhang
• Abstract要約: K$-meansクラスタリングは、大規模なデータセットのパターンを識別する機械学習手法として広く使用されている。 本稿では,非負の低ランク因数分解問題を解くことでNMFライクなアルゴリズムについて述べる。 提案アルゴリズムは,既存の最先端技術と比較して,誤クラスタリング誤差を著しく小さくする。
• 参考スコア（独自算出の注目度）: 23.854834495492543
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: $K$-means clustering is a widely used machine learning method for identifying patterns in large datasets. Semidefinite programming (SDP) relaxations have recently been proposed for solving the $K$-means optimization problem that enjoy strong statistical optimality guarantees, but the prohibitive cost of implementing an SDP solver renders these guarantees inaccessible to practical datasets. By contrast, nonnegative matrix factorization (NMF) is a simple clustering algorithm that is widely used by machine learning practitioners, but without a solid statistical underpinning nor rigorous guarantees. In this paper, we describe an NMF-like algorithm that works by solving a nonnegative low-rank restriction of the SDP relaxed $K$-means formulation using a nonconvex Burer--Monteiro factorization approach. The resulting algorithm is just as simple and scalable as state-of-the-art NMF algorithms, while also enjoying the same strong statistical optimality guarantees as the SDP. In our experiments, we observe that our algorithm achieves substantially smaller mis-clustering errors compared to the existing state-of-the-art.
• Abstract（参考訳）: K$-meansクラスタリングは、大規模なデータセットのパターンを識別する機械学習手法として広く使用されている。 半有限計画法(SDP)緩和法は, 統計的最適性の強い保証を享受する$K$-means最適化問題を解くために最近提案されているが, SDPソルバの実装の禁止コストは, これらの保証を実用的なデータセットに到達できないものにしている。 対照的に、非負行列分解(non negative matrix factorization, nmf)は、機械学習の実践者によって広く使われている単純なクラスタリングアルゴリズムである。 本稿では,sdpの非負低ランク制限を解いたnmfライクなアルゴリズムについて,非凸burer-monteiro因子分解法を用いて,k$-means定式化を緩和した。 結果として得られるアルゴリズムは、最先端のNMFアルゴリズムと同じくらい単純でスケーラブルであり、SDPと同じ強力な統計的最適性を保証する。 実験では,既存の最先端技術と比較して,アルゴリズムの誤クラスタ化誤差が著しく小さいことを観察した。

関連論文リスト

• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  similarity Completion Matrixは多くの機械学習タスクの中核にある基本的なツールとして機能する。 この問題に対処するために、類似行列理論(SMC)法が提案されているが、それらは複雑である。 提案手法は,PSD特性を解析して推定プロセスを導出し,低ランク解を保証するために非低ランク正規化器を組み込む2つの新しい,スケーラブルで効果的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-29T04:27:23Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Adversarially robust clustering with optimality guarantees [7.0830450321883935]
  我々はガウス以下の混合系から得られるデータポイントをクラスタリングする問題を考察する。 ロイドアルゴリズムのような最適ラベル誤りを確実に達成する既存の手法は、通常、外れ値に対して脆弱である。 本稿では, 対数外乱が存在する場合でも, 座標中央値に基づく単純なロバストアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-16T17:17:07Z)
• Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data [16.153709556346417]
  クラスタリングは広くデプロイされた学習ツールである。 iLA-SDPはEMよりも感度が低く、高次元データでは安定である。
  論文  参考訳（メタデータ） (2022-09-29T21:03:13Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Sketch-and-Lift: Scalable Subsampled Semidefinite Program for $K$-means Clustering [16.153709556346417]
  セミデフィニティプログラミング(SDP)はクラスタリングなどの幅広い計算困難問題に対処するための強力なツールである。 本稿では,SDP緩和した$K$-meansクラスタリングを近似する線形時間複雑性アルゴリズムを提案する。 シミュレーション実験により,提案手法の統計的精度は最先端の高速クラスタリングアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2022-01-20T15:31:28Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  シンメトリー非負係数行列(SNMF)は、データクラスタリングの強力な方法であることを示した。 より良いクラスタリング結果を求めるアンサンブルクラスタリングにインスパイアされた,自己監視型SNMF(S$3$NMF)を提案する。 SNMFのコード特性に対する感度を、追加情報に頼らずに活用しています。
  論文  参考訳（メタデータ） (2021-03-02T12:47:40Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
  Kernel $k$クラスタリングは、非線形データの教師なし学習のための強力なツールである。 本稿では,最適化された局所解に対処するための一般的な手法を応用した結果を一般化する。 我々のアルゴリズムは、この非線形分離問題をよりよく解くために、Magricalization-minimization (MM) を利用している。
  論文  参考訳（メタデータ） (2020-11-12T16:07:18Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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