論文の概要: Robust Model Selection and Nearly-Proper Learning for GMMs
- arxiv url: http://arxiv.org/abs/2106.02774v2
- Date: Sun, 23 Apr 2023 02:07:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 01:13:10.768744
- Title: Robust Model Selection and Nearly-Proper Learning for GMMs
- Title（参考訳）: GMMにおけるロバストモデル選択と近接学習
- Authors: Jerry Li, Allen Liu, Ankur Moitra
- Abstract要約: 学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。
対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
- 参考スコア（独自算出の注目度）: 26.388358539260473
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In learning theory, a standard assumption is that the data is generated from
a finite mixture model. But what happens when the number of components is not
known in advance? The problem of estimating the number of components, also
called model selection, is important in its own right but there are essentially
no known efficient algorithms with provable guarantees let alone ones that can
tolerate adversarial corruptions. In this work, we study the problem of robust
model selection for univariate Gaussian mixture models (GMMs). Given
$\textsf{poly}(k/\epsilon)$ samples from a distribution that is
$\epsilon$-close in TV distance to a GMM with $k$ components, we can construct
a GMM with $\widetilde{O}(k)$ components that approximates the distribution to
within $\widetilde{O}(\epsilon)$ in $\textsf{poly}(k/\epsilon)$ time. Thus we
are able to approximately determine the minimum number of components needed to
fit the distribution within a logarithmic factor. Prior to our work, the only
known algorithms for learning arbitrary univariate GMMs either output
significantly more than $k$ components (e.g. $k/\epsilon^2$ components for
kernel density estimates) or run in time exponential in $k$. Moreover, by
adapting our techniques we obtain similar results for reconstructing
Fourier-sparse signals.
- Abstract（参考訳）: 学習理論における標準的な仮定は、データは有限混合モデルから生成されるというものである。
しかし、事前にコンポーネントの数が分かっていない場合はどうなりますか?
モデル選択と呼ばれるコンポーネント数を推定する問題は、それ自体が重要であるが、本質的には、証明可能な保証を備えた効率的なアルゴリズムは存在しない。
本研究では,一変量ガウス混合モデル(GMM)におけるロバストモデル選択の問題について検討する。
例えば、$\textsf{poly}(k/\epsilon)$の分布から$\epsilon$-closeの分布から$k$のコンポーネントを持つGMMまでの分布のサンプルを与えられると、$\widetilde{O}(k)$のコンポーネントでGMMを構築して、$\widetilde{O}(\epsilon)$の分布を$\textsf{poly}(k/\epsilon)$の時間内に近似することができる。
したがって、対数係数内の分布に適合するために必要な最小成分数を概ね決定することができる。
我々の研究に先立ち、任意の単変数のGMMを学習するための唯一の既知のアルゴリズムは、$k$コンポーネント(例えば、カーネル密度推定のための$k/\epsilon^2$コンポーネント)よりもはるかに多く出力するか、または$k$で時間指数的に実行される。
さらに, この手法を応用して, フーリエスパース信号の再構成に類似した結果を得る。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Sparse Gaussian Graphical Models with Discrete Optimization:
Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。
擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。
実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文 参考訳（メタデータ） (2023-07-18T15:49:02Z) - A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm [41.03423042792559]
我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。
結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。
提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-01T17:54:35Z) - A Fourier Approach to Mixture Learning [46.995354373649675]
d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。
我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
論文 参考訳（メタデータ） (2022-10-05T17:35:46Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。