論文の概要: Learning general Gaussian mixtures with efficient score matching

• arxiv url: http://arxiv.org/abs/2404.18893v2
• Date: Tue, 19 Nov 2024 07:08:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:34:20.172329
• Title: Learning general Gaussian mixtures with efficient score matching
• Title（参考訳）: 効率的なスコアマッチングを用いた一般ガウス混合の学習
• Authors: Sitan Chen, Vasilis Kontonis, Kulin Shah,
• Abstract要約: 我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 16.06356123715737
• License:
• Abstract: We study the problem of learning mixtures of $k$ Gaussians in $d$ dimensions. We make no separation assumptions on the underlying mixture components: we only require that the covariance matrices have bounded condition number and that the means and covariances lie in a ball of bounded radius. We give an algorithm that draws $d^{\mathrm{poly}(k/\varepsilon)}$ samples from the target mixture, runs in sample-polynomial time, and constructs a sampler whose output distribution is $\varepsilon$-far from the unknown mixture in total variation. Prior works for this problem either (i) required exponential runtime in the dimension $d$, (ii) placed strong assumptions on the instance (e.g., spherical covariances or clusterability), or (iii) had doubly exponential dependence on the number of components $k$. Our approach departs from commonly used techniques for this problem like the method of moments. Instead, we leverage a recently developed reduction, based on diffusion models, from distribution learning to a supervised learning task called score matching. We give an algorithm for the latter by proving a structural result showing that the score function of a Gaussian mixture can be approximated by a piecewise-polynomial function, and there is an efficient algorithm for finding it. To our knowledge, this is the first example of diffusion models achieving a state-of-the-art theoretical guarantee for an unsupervised learning task.
• Abstract（参考訳）: 我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 共分散行列は有界な条件数を持ち、その手段と共分散は有界な半径の球の中に置かれることしか要求しない。 対象混合物から$d^{\mathrm{poly}(k/\varepsilon")$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、総変量で未知混合物から出力分布が$\varepsilon$-farのサンプルを合成するアルゴリズムを提案する。 この問題の事前処理も行う。 (i)次元$d$の指数的実行を必要とする。 (ii)インスタンス(例えば球面共分散やクラスタビリティ)に強い仮定を置く、又は (iii) 成分数に2倍の指数依存が認められた。 私たちのアプローチは、モーメントの方法のような、この問題によく使われるテクニックから離れています。 代わりに、分布学習から、スコアマッチングと呼ばれる教師付き学習タスクまで、拡散モデルに基づく最近開発された還元を利用する。 本稿では,ガウス混合のスコア関数が一括多項式関数で近似可能であることを示す構造的結果の証明により,後者のアルゴリズムを提案する。 我々の知る限り、これは、教師なし学習タスクに対する最先端の理論的保証を達成するための拡散モデルの最初の例である。

関連論文リスト

• Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures [5.668124846154999]
  我々は,非球面(すなわち任意の成分共分散)ガウス混合モデルをサブルーチンでクラスタリングするための新しいアプローチを開発した。 本手法は特異値分解に基づく古典的次元減少の非球面アナログを与える。 我々のアルゴリズムは自然に任意の外れ値の次元非依存の分数に許容するように拡張する。
  論文  参考訳（メタデータ） (2024-11-19T11:58:51Z)
• Learning Mixtures of Gaussians Using Diffusion Models [9.118706387430883]
  テレビエラーに対して$k$ Gaussiansの混合を学習するための新しいアルゴリズムを提案する。 我々のアプローチは解析的であり、拡散モデルの枠組みに依存している。
  論文  参考訳（メタデータ） (2024-04-29T17:00:20Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  本稿では、ノイズや非ガウス的なデータに対するデータ計算の欠如に対処する。 楕円分布と潜在的な欠落データを扱う特性を混合した新しいEMアルゴリズムについて検討した。 合成データの実験的結果は,提案アルゴリズムが外れ値に対して頑健であり,非ガウスデータで使用可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-28T10:01:37Z)
• 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)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• 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)
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models [66.96778152993858]
  1次元の混合モデルにおけるパラメータ学習のための2つの異なるアプローチを提案する。 これらの分布のいくつかについては、パラメータ推定の最初の保証を示す。
  論文  参考訳（メタデータ） (2020-01-19T05:10:56Z)

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

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