論文の概要: On the Role of Channel Capacity in Learning Gaussian Mixture Models
- arxiv url: http://arxiv.org/abs/2202.07707v1
- Date: Tue, 15 Feb 2022 20:15:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-17 14:59:16.288897
- Title: On the Role of Channel Capacity in Learning Gaussian Mixture Models
- Title（参考訳）: ガウス混合モデルの学習におけるチャネル容量の役割について
- Authors: Elad Romanov, Tamir Bendory, Or Ordentlich
- Abstract要約: 平衡ガウス混合モデル(GMM)の未知中心を学習する際のサンプル複雑性について検討する。
本研究の主な成果は,GMM学習問題である,大規模システム制限$d,ktoinfty$の正確なノイズ閾値$sigma2$をラベル付き観測から学習するのと同じくらい容易である,という特徴付けである。
この結果は、中心が球面上に均一に分布しているGMMに対してのみ証明されるが、対応するGMMを学習する統計的困難度を決定するためのチャネル符号として、中心星座に付随する復号誤り確率が示唆される。
- 参考スコア（独自算出の注目度）: 31.841289319809814
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the sample complexity of learning the $k$ unknown centers
of a balanced Gaussian mixture model (GMM) in $\mathbb{R}^d$ with spherical
covariance matrix $\sigma^2\mathbf{I}$. In particular, we are interested in the
following question: what is the maximal noise level $\sigma^2$, for which the
sample complexity is essentially the same as when estimating the centers from
labeled measurements? To that end, we restrict attention to a Bayesian
formulation of the problem, where the centers are uniformly distributed on the
sphere $\sqrt{d}\mathcal{S}^{d-1}$. Our main results characterize the exact
noise threshold $\sigma^2$ below which the GMM learning problem, in the large
system limit $d,k\to\infty$, is as easy as learning from labeled observations,
and above which it is substantially harder. The threshold occurs at $\frac{\log
k}{d} = \frac12\log\left( 1+\frac{1}{\sigma^2} \right)$, which is the capacity
of the additive white Gaussian noise (AWGN) channel. Thinking of the set of $k$
centers as a code, this noise threshold can be interpreted as the largest noise
level for which the error probability of the code over the AWGN channel is
small. Previous works on the GMM learning problem have identified the minimum
distance between the centers as a key parameter in determining the statistical
difficulty of learning the corresponding GMM. While our results are only proved
for GMMs whose centers are uniformly distributed over the sphere, they hint
that perhaps it is the decoding error probability associated with the center
constellation as a channel code that determines the statistical difficulty of
learning the corresponding GMM, rather than just the minimum distance.
- Abstract（参考訳）: 本稿では, 球面共分散行列 $\sigma^2\mathbf{i}$ を持つ$\mathbb{r}^d$ における平衡ガウス混合モデル (gmm) のk$未知中心を学習するサンプル複雑性について検討する。
特に、以下の質問に興味を持っている: ラベル付き測定値から中心を推定する際に、サンプルの複雑さが本質的に同じである最大ノイズレベル$\sigma^2$ とは何でしょうか?
そのために、この問題のベイズ的定式化に注意を向け、そこで中心は球面 $\sqrt{d}\mathcal{S}^{d-1}$ 上で均一に分布する。
我々の主な結果は、gmm学習問題である大きなシステム制限値である$d,k\to\infty$がラベル付き観測から学ぶのと同じくらい簡単であり、それよりもはるかに困難である、正確な雑音閾値$\sigma^2$を特徴付けるものである。
閾値は$\frac{\log k}{d} = \frac12\log\left(1+\frac{1}{\sigma^2} \right)$で、これは付加的な白色ガウスノイズ(AWGN)チャネルの容量である。
コードとしての$k$ Centerのセットを考えると、このノイズ閾値は、AWGNチャネル上のコードのエラー確率が小さい最大のノイズレベルと解釈できる。
GMM学習問題に関するこれまでの研究は、GMM学習の統計的困難度を決定する重要なパラメータとして、中心間の最小距離を特定してきた。
本研究の結果は, 球面上に一様分布するGMMに対してのみ証明されるが, 最小距離ではなく, 対応するGMMを学習することの統計的困難さを判断するチャネル符号として, 中心星座に付随する復号誤差確率が示唆される。
関連論文リスト
- Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - Better Gaussian Mechanism using Correlated Noise [1.450405446885067]
分散を$(sqrtd + 1)/4$にスケールしたガウス変数として分布するランダム変数を追加することで、独立雑音サンプルの分散を$(d + sqrtd)/4$でのみスケールできることを示す。
私たちのメカニズムの中心的な考え方はシンプルで、そのテクニックは柔軟です。
論文 参考訳（メタデータ） (2024-08-13T12:31:03Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。
ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
論文 参考訳（メタデータ） (2022-02-22T01:49:41Z) - Multimeasurement Generative Models [7.502947376736449]
我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
論文 参考訳（メタデータ） (2021-12-18T02:11:36Z) - Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。
対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
論文 参考訳（メタデータ） (2021-06-05T01:58:40Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。