論文の概要: Outlier-Robust Clustering of Non-Spherical Mixtures
- arxiv url: http://arxiv.org/abs/2005.02970v3
- Date: Mon, 14 Dec 2020 18:00:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 06:10:00.290106
- Title: Outlier-Robust Clustering of Non-Spherical Mixtures
- Title（参考訳）: 非球面混合系の外乱クラスター化
- Authors: Ainesh Bakshi and Pravesh Kothari
- Abstract要約: 統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。
この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
- 参考スコア（独自算出の注目度）: 5.863264019032882
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first outlier-robust efficient algorithm for clustering a mixture
of $k$ statistically separated d-dimensional Gaussians (k-GMMs). Concretely,
our algorithm takes input an $\epsilon$-corrupted sample from a $k$-GMM and whp
in $d^{\text{poly}(k/\eta)}$ time, outputs an approximate clustering that
misclassifies at most $k^{O(k)}(\epsilon+\eta)$ fraction of the points whenever
every pair of mixture components are separated by
$1-\exp(-\text{poly}(k/\eta)^k)$ in total variation (TV) distance. Such a
result was not previously known even for $k=2$. TV separation is the
statistically weakest possible notion of separation and captures important
special cases such as mixed linear regression and subspace clustering.
Our main conceptual contribution is to distill simple analytic properties -
(certifiable) hypercontractivity and bounded variance of degree 2 polynomials
and anti-concentration of linear projections - that are necessary and
sufficient for mixture models to be (efficiently) clusterable. As a
consequence, our results extend to clustering mixtures of arbitrary affine
transforms of the uniform distribution on the $d$-dimensional unit sphere. Even
the information-theoretic clusterability of separated distributions satisfying
these two analytic assumptions was not known prior to our work and is likely to
be of independent interest.
Our algorithms build on the recent sequence of works relying on certifiable
anti-concentration first introduced in the works of Karmarkar, Klivans, and
Kothari and Raghavendra, and Yau in 2019. Our techniques expand the
sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian
clusters in data. This involves giving a low-degree sum-of-squares proof of
statements that relate parameter (i.e. mean and covariances) distance to total
variation distance by relying only on hypercontractivity and
anti-concentration.
- Abstract（参考訳）: 統計的に分離されたd-次元ガウスアン(k-GMMs)の混合物をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。
特に、このアルゴリズムは、$k$-gmmから$\epsilon$-corruptedサンプルを入力し、$d^{\text{poly}(k/\eta)}$ timeでwcpを入力し、全ての混合成分が1-\exp(-\text{poly}(k/\eta)^k)$ in total variation (tv)距離で分離されるたびに、最大$k^{o(k)}(\epsilon+\eta)$のポイントを割った近似クラスタリングを出力する。
このような結果は以前、$k=2$でも知られていなかった。
tv分離は、統計的に最も弱い分離の概念であり、混合線形回帰や部分空間クラスタリングのような重要な特別なケースを捉えている。
我々の主要な概念的貢献は、(効率的に)クラスタリング可能な混合モデルに必要な、単純な解析的性質(認識可能)と次数2多項式の有界分散と線形射影の反集中を蒸留することである。
その結果、この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
これら2つの解析的仮定を満たす分離分布の情報理論的クラスタビリティでさえ、我々の研究以前には知られておらず、独立した関心を持つ可能性が高い。
我々のアルゴリズムは、2019年にKarmarkar、Klivans、Kothari、Raghavendra、Yauの3作品に初めて導入された、認証済みのアンチ・集中による最近の一連の研究に基づいている。
提案手法は,データ中のテレビ分離ガウスクラスタのロバストな認証性を示すために,2乗和ツールキットを拡張した。
これは、パラメータ(平均と共分散)距離を超収縮率と反集束のみに頼って全変距離に関連づける低次二乗の証明を与える。
関連論文リスト
- Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。
我々は、下層の混合成分について分離を前提としない。
我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-29T17:30:36Z) - Clustering Mixtures of Bounded Covariance Distributions Under Optimal
Separation [44.25945344950543]
境界共分散分布の混合に対するクラスタリング問題について検討する。
このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。
我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
論文 参考訳（メタデータ） (2023-12-19T01:01:53Z) - A Robust and Flexible EM Algorithm for Mixtures of Elliptical
Distributions with Missing Data [71.9573352891936]
本稿では、ノイズや非ガウス的なデータに対するデータ計算の欠如に対処する。
楕円分布と潜在的な欠落データを扱う特性を混合した新しいEMアルゴリズムについて検討した。
合成データの実験的結果は,提案アルゴリズムが外れ値に対して頑健であり,非ガウスデータで使用可能であることを示す。
論文 参考訳（メタデータ） (2022-01-28T10:01:37Z) - Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for
Non-Spherical Gaussian Mixtures [9.670578317106182]
kgeq 2$ Gaussian 成分と未知の手段と未知の共分散(すべての成分について同一視される)の混合を考える。
混合重量が指数関数的に小さい場合にのみこのような硬さが現れることを示す。
我々は,最小混合重量の時間準多項式を用いた2乗法に基づくアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-10T10:51:44Z) - Clustering Mixtures with Almost Optimal Separation in Polynomial Time [21.509452343745252]
高次元における平均分離ガウス多様体のクラスタリング混合問題について考察する。
Delta = Theta (sqrtlog k)$ の分離は必要であり、良いクラスタリングを回復するのに十分である。
我々は多くのサンプルと時間を要し、優れたクラスタリングをうまく回復できるアルゴリズムを提示する。
論文 参考訳（メタデータ） (2021-12-01T18:34:09Z) - Learning Gaussian Mixtures with Generalised Linear Models: Precise
Asymptotics in High-dimensions [79.35722941720734]
多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。
実験的リスク最小化による高次元推定器の精度を実証する。
合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
論文 参考訳（メタデータ） (2021-06-07T16:53:56Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Algebraic and Analytic Approaches for Parameter Learning in Mixture
Models [66.96778152993858]
1次元の混合モデルにおけるパラメータ学習のための2つの異なるアプローチを提案する。
これらの分布のいくつかについては、パラメータ推定の最初の保証を示す。
論文 参考訳（メタデータ） (2020-01-19T05:10:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。