論文の概要: Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures

• arxiv url: http://arxiv.org/abs/2112.05445v1
• Date: Fri, 10 Dec 2021 10:51:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-13 20:46:24.034250
• Title: Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures
• Title（参考訳）: 平行パンケーキを超えて:非球面ガウス混合に対する準多項時間保証
• Authors: Rares-Darius Buhai, David Steurer
• Abstract要約: 我々は、(純粋な)ガウス多様体と混合物を区別しても指数関数的に困難であることを示した($k$)。 我々は,最小混合重量の時間準多項式を用いた2乗法に基づくアルゴリズムを開発した。 本研究の課題は,少数の対向性外れ値に本質的に敏感であると考えられる点である。
• 参考スコア（独自算出の注目度）: 8.782204980889079
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider mixtures of $k\geq 2$ Gaussian components with unknown means and unknown covariance (identical for all components) that are well-separated, i.e., distinct components have statistical overlap at most $k^{-C}$ for a large enough constant $C\ge 1$. Previous statistical-query lower bounds [DKS17] give formal evidence that even distinguishing such mixtures from (pure) Gaussians may be exponentially hard (in $k$). We show that this kind of hardness can only appear if mixing weights are allowed to be exponentially small, and that for polynomially lower bounded mixing weights non-trivial algorithmic guarantees are possible in quasi-polynomial time. Concretely, we develop an algorithm based on the sum-of-squares method with running time quasi-polynomial in the minimum mixing weight. The algorithm can reliably distinguish between a mixture of $k\ge 2$ well-separated Gaussian components and a (pure) Gaussian distribution. As a certificate, the algorithm computes a bipartition of the input sample that separates a pair of mixture components, i.e., both sides of the bipartition contain most of the sample points of at least one component. For the special case of colinear means, our algorithm outputs a $k$ clustering of the input sample that is approximately consistent with the components of the mixture. A significant challenge for our results is that they appear to be inherently sensitive to small fractions of adversarial outliers unlike most previous results for Gaussian mixtures. The reason is that such outliers can simulate exponentially small mixing weights even for mixtures with polynomially lower bounded mixing weights. A key technical ingredient is a characterization of separating directions for well-separated Gaussian components in terms of ratios of polynomials that correspond to moments of two carefully chosen orders logarithmic in the minimum mixing weight.
• Abstract（参考訳）: k\geq 2$ Gaussian 成分と未知の手段と未知の共分散(すべての成分について同一視される)の混合を考える、すなわち、異なる成分は、十分大きな定数 $C\ge 1$ に対して、最大$k^{-C}$ で統計的重複を持つ。 従来の統計的クエリの下限 [DKS17] は、そのような混合を(純粋な)ガウスと区別しても指数関数的に難しい($k$)という公式な証拠を与える。 このような硬さは, 混合重量が指数関数的に小さい場合にのみ出現し, 多項式的に低い有界混合重量の場合, 非自明なアルゴリズム保証は準多項式時間で可能であることを示す。 具体的には,最小混合重量の時間準多項式を用いた2乗法に基づくアルゴリズムを開発した。 このアルゴリズムは、$k\ge 2$ well-separated Gaussian componentと(純粋な)ガウス分布の混合を確実に区別することができる。 証明として、アルゴリズムは、2つの混合成分を分離する入力サンプルの2分割、すなわち、2分割の両側は少なくとも1つのコンポーネントのサンプルポイントのほとんどを含む。 共線形平均の特別な場合、このアルゴリズムは、混合の成分とほぼ一致する入力サンプルの$k$クラスタリングを出力する。 本研究の課題は, ガウス混合物の従来の結果と異なり, 正反対の外れ値に本質的に敏感であると考えられる点である。 この理由は、多項式的に低い有界混合重みを持つ混合の場合であっても、指数関数的に小さな混合重みをシミュレートできるからである。 重要な技術的要素は、最小混合重みで慎重に選択された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)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。 実験的リスク最小化による高次元推定器の精度を実証する。 合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
  論文  参考訳（メタデータ） (2021-06-07T16:53:56Z)
• Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
  任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。 本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-03T17:54:03Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。 この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
  論文  参考訳（メタデータ） (2020-05-06T17:24:27Z)
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians [21.780375994511324]
  我々は、期待最大化(EM)に対する新しい結果を証明する: EMは、分離された$Omega(sqrtlog k)$の下で局所的に収束することを示す。 我々の結果は、(潜在的に異なる)ガウス成分の事前の知識を前提としない。
  論文  参考訳（メタデータ） (2020-02-02T05:09:26Z)
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models [66.96778152993858]
  1次元の混合モデルにおけるパラメータ学習のための2つの異なるアプローチを提案する。 これらの分布のいくつかについては、パラメータ推定の最初の保証を示す。
  論文  参考訳（メタデータ） (2020-01-19T05:10:56Z)
• Distributed, partially collapsed MCMC for Bayesian Nonparametrics [68.5279360794418]
  ディリクレ法やベータ・ベルヌーリ法のようなモデルでよく用いられる完全無作為測度は独立な部分測度に分解可能であるという事実を利用する。 この分解を用いて、潜在測度を、インスタンス化された成分のみを含む有限測度と、他のすべての成分を含む無限測度に分割する。 得られたハイブリッドアルゴリズムは、収束保証を犠牲にすることなくスケーラブルな推論を可能にすることができる。
  論文  参考訳（メタデータ） (2020-01-15T23:10:13Z)

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

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