論文の概要: On the Global Solution of Soft k-Means
- arxiv url: http://arxiv.org/abs/2212.03589v1
- Date: Wed, 7 Dec 2022 12:06:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 16:42:35.928147
- Title: On the Global Solution of Soft k-Means
- Title（参考訳）: ソフトk-meansの全球解について
- Authors: Feiping Nie, Hong Chen, Rong Wang, Xuelong Li
- Abstract要約: 本稿では,ソフトk-平均問題の解法を全世界で提案する。
ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
- 参考スコア（独自算出の注目度）: 159.23423824953412
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents an algorithm to solve the Soft k-Means problem globally.
Unlike Fuzzy c-Means, Soft k-Means (SkM) has a matrix factorization-type
objective and has been shown to have a close relation with the popular
probability decomposition-type clustering methods, e.g., Left Stochastic
Clustering (LSC). Though some work has been done for solving the Soft k-Means
problem, they usually use an alternating minimization scheme or the projected
gradient descent method, which cannot guarantee global optimality since the
non-convexity of SkM. In this paper, we present a sufficient condition for a
feasible solution of Soft k-Means problem to be globally optimal and show the
output of the proposed algorithm satisfies it. Moreover, for the Soft k-Means
problem, we provide interesting discussions on stability, solutions
non-uniqueness, and connection with LSC. Then, a new model, named Minimal
Volume Soft k-Means (MVSkM), is proposed to address the solutions
non-uniqueness issue. Finally, experimental results support our theoretical
results.
- Abstract（参考訳）: 本稿では,ソフトk平均問題をグローバルに解くアルゴリズムを提案する。
ファジィ c-平均とは異なり、ソフト k-平均 (skm) は行列分解型目的を持ち、一般的な確率分解型クラスタリング法、例えば左確率クラスタリング (lsc) と密接な関係を持つことが示されている。
ソフトk平均問題の解法としていくつかの研究がなされているが、通常はSkMの非凸性から大域的最適性を保証することのできない交互最小化スキームや投射勾配降下法を用いる。
本稿では,Soft k-Means問題の実現可能な解がグローバルに最適であるような条件を提示し,提案アルゴリズムの出力が満足できることを示す。
さらに,ソフトk-平均問題に対して,安定性,非特異性,lscとの関連について興味深い議論を行う。
そこで, 最小体積k平均 (MVSkM) と呼ばれる新しいモデルを提案し, 非特異性問題に対処する。
最後に、実験結果が理論的結果を支持する。
関連論文リスト
- Reweighted Solutions for Weighted Low Rank Approximation [47.790126028106734]
重み付き低階近似(WLRA)は、統計解析から信号処理に至るまで、重要かつ困難なプリミティブである。
そこで本研究では,WLRAに対して,必ずしも低ランクではないが極めて少ないパラメータで保存可能な行列を出力する緩和解を提案する。
我々の中心となる考え方は、重み行列自体を低階解の重み付けに利用することであり、これは非常に単純なアルゴリズムであり、顕著な経験的性能を与える。
論文 参考訳（メタデータ） (2024-06-04T15:50:35Z) - Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳（メタデータ） (2023-10-10T01:39:04Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm [20.341309224377866]
マルチプロトタイプの凸マージに基づくK-Meansクラスタリングアルゴリズム(MCKM)を提案する。
MCKM は K-Means 問題の望ましくない局所最小値から k を優先せずに逃れるための効率的で説明可能なクラスタリングアルゴリズムである。
論文 参考訳（メタデータ） (2023-02-14T13:57:33Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Stability and Generalization for Markov Chain Stochastic Gradient
Methods [49.981789906200035]
本稿では,最小化問題と最小化問題の両方に対して,MC-SGMの包括的一般化解析を行う。
我々はスムーズかつ非スムーズなケースに対して最適な過剰人口リスク境界を確立する。
コンベックス・コンケーブ問題に対する最初期のほぼ最適な収束率を期待と高い確率で開発する。
論文 参考訳（メタデータ） (2022-09-16T15:42:51Z) - Factorization Approach for Low-complexity Matrix Completion Problems:
Exponential Number of Spurious Solutions and Failure of Gradient Methods [18.16094563534453]
Burer-Monteiro (B-M) 因数分解法は, RIP条件下での低ランク行列最適化問題を効率的に解けることが知られている。
情報理論の複雑さが低い低ランク行列最適化問題に対して、B-M分解に基づく手法が成功するかどうかを問うのは当然である。
論文 参考訳（メタデータ） (2021-10-19T21:52:14Z) - Saddle Point Optimization with Approximate Minimization Oracle and its
Application to Robust Berthing Control [7.347989843033034]
本稿では,最小化問題を大まかに解決するオラクルのみに依存するサドル点最適化手法を提案する。
我々は、その収束特性を強い凸-凹問題で解析し、その線形収束性を大域的なmin-maxサドル点へ示す。
1+1)-CMA-ES を最小化オラクル、すなわち Adversarial-CMA-ES として開発した手法の実装は、テスト問題に対する既存のアプローチよりも優れている。
論文 参考訳（メタデータ） (2021-05-25T00:08:47Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳（メタデータ） (2020-10-23T05:24:05Z) - Probabilistic K-means Clustering via Nonlinear Programming [13.026121785720395]
確率的K平均 (probabilistic K-Means, PKM) は線形等式と線形不等式に制約された非線形プログラミングモデルである。
理論上は、能動的勾配射影により非効率にモデルを解くことができる。
実験により,PKMの性能と提案手法の解法を5つの側面で検討した。
論文 参考訳（メタデータ） (2020-01-10T02:40:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。