論文の概要: Uniform Concentration Bounds toward a Unified Framework for Robust
Clustering
- arxiv url: http://arxiv.org/abs/2110.14148v1
- Date: Wed, 27 Oct 2021 03:43:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 13:54:34.556452
- Title: Uniform Concentration Bounds toward a Unified Framework for Robust
Clustering
- Title（参考訳）: ロバストクラスタリングのための統一フレームワークに向けた一様濃度境界
- Authors: Debolina Paul, Saptarshi Chakraborty, Swagatam Das and Jason Xu
- Abstract要約: センターベースのクラスタリングの最近の進歩は、ロイドの有名な$k$-meansアルゴリズムの欠点によって改善され続けている。
様々な手法は、ローカル・ミニマ(英語版)の貧弱さ、異常値に対する感度、ユークリッドの対応に適さないデータに対処しようとする。
本稿では,一般的な相似性尺度に基づく中心クラスタリングのための密結合型ロバストフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 21.789311405437573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent advances in center-based clustering continue to improve upon the
drawbacks of Lloyd's celebrated $k$-means algorithm over $60$ years after its
introduction. Various methods seek to address poor local minima, sensitivity to
outliers, and data that are not well-suited to Euclidean measures of fit, but
many are supported largely empirically. Moreover, combining such approaches in
a piecemeal manner can result in ad hoc methods, and the limited theoretical
results supporting each individual contribution may no longer hold. Toward
addressing these issues in a principled way, this paper proposes a cohesive
robust framework for center-based clustering under a general class of
dissimilarity measures. In particular, we present a rigorous theoretical
treatment within a Median-of-Means (MoM) estimation framework, showing that it
subsumes several popular $k$-means variants. In addition to unifying existing
methods, we derive uniform concentration bounds that complete their analyses,
and bridge these results to the MoM framework via Dudley's chaining arguments.
Importantly, we neither require any assumptions on the distribution of the
outlying observations nor on the relative number of observations $n$ to
features $p$. We establish strong consistency and an error rate of
$O(n^{-1/2})$ under mild conditions, surpassing the best-known results in the
literature. The methods are empirically validated thoroughly on real and
synthetic datasets.
- Abstract（参考訳）: センターベースのクラスタリングの最近の進歩は、導入後60ドル以上でロイドの有名な$k$-meansアルゴリズムの欠点を改善し続けている。
様々な手法は、ローカルな最小値の貧弱さ、異常値に対する感度、ユークリッドの測度に適さないデータに対処しようとするが、その多くが経験的に支持されている。
さらに、このようなアプローチを断片的な方法で組み合わせることで、アドホックな手法がもたらされ、個々の貢献を支持する限られた理論的結果はもはや成り立たない。
本稿では、これらの課題を原則的に解決する上で、一般的な相似性尺度に基づく中心クラスタリングのための強固な枠組みを提案する。
特に、Median-of-Means (MoM) 推定フレームワーク内で厳密な理論的処理を行い、いくつかの一般的な$k$-means 変種を仮定することを示す。
既存手法の統一に加えて、解析を完了した一様濃度境界を導出し、ダドリーの連鎖論を通してこれらの結果をMoMフレームワークにブリッジする。
重要なことは、外向きの観測の分布や相対的な観測数に$n$から$p$という仮定は必要としない。
弱条件下では強い一貫性と誤り率を$O(n^{-1/2})$と定め、文献でよく知られた結果を上回る。
これらの手法は実データと合成データで実証的に検証される。
関連論文リスト
- Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transport [84.51977664336056]
我々は,テクストロバスト連続バリセンタを推定するための,新しいスケーラブルなアプローチを提案する。
提案手法は$min$-$max$最適化問題であり,テキスト一般コスト関数に適応可能である。
論文 参考訳（メタデータ） (2024-10-04T23:27:33Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
本稿では,Wasserstein Barycenter問題を解くための新しいスケーラブルなアプローチを提案する。
我々の手法は最近のNeural OTソルバをベースとしている。
また,提案手法の理論的誤差境界も確立する。
論文 参考訳（メタデータ） (2024-02-06T09:17:07Z) - Can Evolutionary Clustering Have Theoretical Guarantees? [21.343803954998915]
進化的クラスタリングは多くの成功例を見出したが、すべての結果は実証的であり、理論的な支持が欠如している。
本稿では,GSEMOの近似性能を理論的に保証できることを証明して,このギャップを埋める。
論文 参考訳（メタデータ） (2022-12-04T09:00:35Z) - Rethinking Clustering-Based Pseudo-Labeling for Unsupervised
Meta-Learning [146.11600461034746]
教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。
このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。
このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
論文 参考訳（メタデータ） (2022-09-27T19:04:36Z) - A One-shot Framework for Distributed Clustered Learning in Heterogeneous
Environments [54.172993875654015]
異種環境における分散学習のためのコミュニケーション効率化手法のファミリーを提案する。
ユーザによるローカル計算に基づくワンショットアプローチと、サーバにおけるクラスタリングベースのアグリゲーションステップは、強力な学習保証を提供する。
厳密な凸問題に対しては,ユーザ毎のデータ点数がしきい値を超える限り,提案手法はサンプルサイズの観点から順序最適平均二乗誤差率を達成する。
論文 参考訳（メタデータ） (2022-09-22T09:04:10Z) - Bregman Power k-Means for Clustering Exponential Family Data [11.434503492579477]
我々は、ブレグマン発散の下でのハードクラスタリングに関する古典的な研究のアルゴリズム的進歩を橋渡しする。
ブレグマン発散のエレガントな性質は、単純で透明なアルゴリズムで閉形式更新を維持できる。
シミュレーション実験の徹底的な実証分析と降雨データに関するケーススタディを考察し,提案手法はガウス以外の様々なデータ設定において,既存のピア手法よりも優れていることを示した。
論文 参考訳（メタデータ） (2022-06-22T06:09:54Z) - A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
バイナリ密度比推定(DRE)は多くの最先端の機械学習アルゴリズムの基礎を提供する。
ブレグマン最小化の発散の観点から一般的な枠組みを開発する。
我々のフレームワークはバイナリDREでそれらのフレームワークを厳格に一般化する手法に導かれることを示す。
論文 参考訳（メタデータ） (2021-12-07T01:23:20Z) - Improved Estimation of Concentration Under $\ell_p$-Norm Distance
Metrics Using Half Spaces [14.947511752748005]
測定の集中は、敵の脆弱性の根本的な原因であると議論されている。
本稿では,実験データセットの濃度を$ell_p$-norm距離で推定する手法を提案する。
提案アルゴリズムはMahloujifar et alよりも効率的です。
合成データセットと画像ベンチマークに関する我々の実験は、より厳密な内在的堅牢性境界を見つけることができることを示した。
論文 参考訳（メタデータ） (2021-03-24T01:16:28Z) - Generalization Bounds in the Presence of Outliers: a Median-of-Means
Study [8.905677748354364]
Median-of-Means (MoM) は平方可積分 r.v.$Z$ の平均$theta$ の推定量である。
ヘビーテールのデータに対する高い信頼性のおかげで、MoMは機械学習に様々な応用を見出した。
新たな作業ラインは、MoMが破損したデータに対処する能力を特徴付け、活用しようとしている。
論文 参考訳（メタデータ） (2020-06-09T13:21:39Z) - Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
経験値関数の新しい正規化器を導入し、ワッサーシュタイン分布のロバストな値関数を下限とすることを示す。
強化学習における$textitexternalな不確実性に対処するための実用的なツールとして正規化を使用することを提案する。
論文 参考訳（メタデータ） (2020-03-05T19:56:23Z) - Entropy Regularized Power k-Means Clustering [21.013169939337583]
本稿では、クローズドフォーム更新と収束保証を享受できるスケーラブルな大規模化最小化アルゴリズムを提案する。
我々の手法は、$k$-meansと$k$-meansと同じ計算量を維持しているが、どちらも大幅に改善されている。
論文 参考訳（メタデータ） (2020-01-10T14:05:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。