机器算法验证 - 为什么直接优化高斯混合在计算上很困难？ - 吾爱随笔录

机器算法验证机器学习高斯混合分布期望最大化

2022-01-31 16:24:28

考虑混合高斯的对数似然：

l (S_{n}; θ) = \sum_{t = 1}^{n} \log f (x^{(t)} | θ) = \sum_{t = 1}^{n} \log {\sum_{i = 1}^{k} p_{i} f (x^{(t)} | μ^{(i)}, σ_{i}^{2})}

$l(S_n; \theta) = \sum^n_{t=1}\log f(x^{(t)}|\theta) = \sum^n_{t=1}\log\left\{\sum^k_{i=1}p_i f(x^{(t)}|\mu^{(i)}, \sigma^2_i)\right\}$

我想知道为什么直接最大化该方程在计算上是困难的？我一直在寻找一个清晰可靠的直觉，为什么它应该是显而易见的，或者可能是一个更严格的解释，为什么它很难。这个问题是 NP 完全的还是我们只是不知道如何解决它？这就是我们使用 EM（期望最大化）算法的原因吗？

符号：

$S_n$ = 训练数据。

$x^{(t)}$ = 数据点。

$\theta$ = 指定高斯的参数集、它们的均值、标准差和从每个聚类/类/高斯生成点的概率。

$p_i$ = 从簇/类/高斯 i 生成点的概率。

2个回答

首先，GMM 是一种特殊的聚类算法，您可以在其中尝试找到观察值的最佳标记。有个可能的类别，这意味着您的训练数据和的中等值，这已经变得很大。 $n$ $k$ $k^n$ $k$ $n$

其次，你试图最小化的函数不是凸的，再加上你的问题的大小，使它变得非常困难。我只知道 k-means（GMM 可以看作是 kmeans 的软版本）是 NP-hard。但我不知道它是否也被 GMM 证明了。

看问题不是凸的，考虑一维情况：并检查您不能保证。

L = \log (e^{- (x / σ_{1})^{2}} + e^{- (x / σ_{2})^{2}})

$L = \log \left(e^{-({x}/{\sigma_{1}})^2} + e^{-({x}/{\sigma_{2}})^2}\right)$

\frac{d^{2} L}{d x^{2}} > 0

$\frac{d^2L}{dx^2} > 0$

遇到非凸问题意味着您可能会陷入局部最小值。一般而言，您在凸优化中没有强有力的保证，而且寻找解决方案也更加困难。

除了 juampa 的观点，让我指出这些困难：

函数是无界的，所以真正的最大值是并且对应于（例如）和。因此，真正的最大化器应该以这种解决方案结束，这对于估计目的没有用。 $l(\theta|S_n)$ $+\infty$ $\hat\mu^{(i)}=x_1$ $\hat\sigma_i=0$
即使不考虑将和的乘积分解为中要最大化的函数也是高度多模态的（除了非凸）因此对数值方法是一个挑战。EM 通过收敛到本地模式或鞍点并需要多次运行来承认困难。如图所示 $k^n$ $l(\theta|S_n)$ $\theta$

附加说明：不调用 EM 算法，可以使用标准优化算法（如 Newton-Raphson）一次一个参数，即迭代

如果有个参数并且每一步都应该增加目标函数的值，但这个方案最多只能以与 EM 算法相同的模式结束。 $v$ $l(\theta|S_n)$

其它你可能感兴趣的问题