极大似然估计在混合高斯分布中遇到的困难

在一般的情况下,对于所得到的样本集,\(X=\left\{x_{1}, \dots, x_{N}\right\}\),我们的目标是最大化似然函数,通过最大化似然函数来获取参数的值。这是似然函数往往取对数表示就是:
\[
\begin{aligned} L(\theta | X) &=\log \left(\prod_{i=1}^{N} p\left(x_{i} | \theta\right)\right) \\ &=\sum_{i=1}^{N} \log p\left(x_{i} | \theta\right) \end{aligned}
\]
这个过程的参数估计可以描述成:
\[
\hat{\theta}=\arg \max _{\theta} L(\theta | X)
\]
这个结果是可以直接计算出来的,那么引入混合高斯分布会是什么样呢?

混合高斯分布:

简单的说就是,非混合的情况下,我们的数据集满足高斯分布,这样用极大似然就直接算出高斯分布中的参数就可以了。那么混合的情况下就是,原数据集是由多个满足高斯分布的数据集线性组合起来,这个时候我们理解为:有 \(k\) 个满足不同参数的高斯分布的数据集,并且 \(\sum_{j=1}^{k} \phi_{j}=1\)。其中 $\phi $ 表示权重那么我们新的数据集就可以表示成 \(\sum_{j=1}^{k} \phi_{j} p_{j}\left({x} | \theta_{j}\right)\) 。那么这时参数就有两个,分别是 $ \phi $ 和 $ \theta$ 。现在我们假设有\(\phi_{j} = p\left(z^{(i)}=j\right)\) 。

这个时候,根据条件概率的计算公式,我们似然函数可以写成下面这样的式子:
\[
\begin{aligned} \ell(\phi, \mu, \Sigma) &=\sum_{i=1}^{m} \log p\left(x^{(i)} ; \phi, \mu, \Sigma\right) \\ &=\sum_{i=1}^{m} \log \sum_{z^{(i)}=1}^{k} p\left(x^{(i)} | z^{(i)} ; \mu, \Sigma\right) p\left(z^{(i)} ; \phi\right) \end{aligned}
\]
上式中的 \(x^{(i)}|z^{(i)}\) 可以理解为 $x^{(i)} $ 来自第 $ j$ 个数据集的概率。显然这个 \(p\left(x^{(i)} | z^{(i)} ; \mu, \Sigma\right)\) 表示的是第 \(z^{(i)}\) 个高斯分布的函数。所以 $z^{(i)} $ 是个隐变量。这个式子我感觉自己说的不够清楚,这个里的 $z^{(i)} $ 的选择我们选择的是 \(\{1, \ldots, k\}\) 中的某一个,其实 $z^{(i)} $ 可以用向量来表示,表示成:
\[
\left[ \begin{matrix}
0& 0& 1& 0& ……& 0& 0& 0\\
\end{matrix} \right]
\]
这样说明这个式子更直观,也更加细节,这里推荐一篇博客 传送门 ,

概率论中的 Jensen 不等式

对于 Jensen 不等式,通常情况下是这样的:对于 \(f^{\prime \prime}(x) \geq 0\) 也就是对于凸函数而言,这个可以用中值定理来证明,同时这个公式还可以用于证明多项式的均值不等式与调和不等式,这里就不给出证明了,在概率的条件下就是:实际上,这就是均值不等式来的啊, E 表示数学期望
\[
\mathrm{E}[f(X)] \geq f(\mathrm{E} X)
\]

EM 算法讲了什么东西

对于一般形式的,引入隐变量 \(z\) 的极大似然函数:
\[
\begin{aligned} \ell(\theta) &=\sum_{i=1}^{N} \log p(x ; \theta) \\ &=\sum_{i=1}^{N} \log \sum_{z} p(x, z ; \theta) \end{aligned}
\]
现在,我们假设对于每一个 $ i $ , \(Q_{i}\) 表示 $ z $ 的分布,那么我们有 \(\sum_{z} Q_{i}(z)=1, Q_{i}(z) \geq0\) 。然后我们使用 Jensen 不等式将上面的式子进行放缩,写成下面的这样形式,
\[
\begin{aligned} \ell(\theta) =\sum_{i} \log p\left(x^{(i)} ; \theta\right) &=\sum_{i} \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right) \\ &=\sum_{i} \log \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \end{aligned}
\]
这里的 \(Q_{i}\) 应该就是 EM 算法不断的迭代的关键。

上面的式子表明 \(\ell(\theta)\) 有一个下界,从极大似然的角度考虑,我们就是要最大化这个下界,得到 $ \theta $ 的取值,但是其中的 \(Q_{i}\) 是一个隐变量的分布,我们并不知道这个分布是什么样子的。

上面使用 Jensen 不等式关键的一步是:
\[
f\left(\mathrm{E}_{z^{(i)} \sim Q_{i}}\left[\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right]\right) \geq \mathrm{E}_{z^{(i)} \sim Q_{i}}\left[f\left(\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right)\right]
\]
这个式子取等式的时候,对于数学期望而言,只有常数可以满足数学期望中的 Jensen 不等式相等。这里不做具体的证明,我们可以考虑从均值不等式来理解这个问题,假设这个常数是 $ c$ :
\[
\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=c
\]
也就是说:
\[
Q_{i}\left(z^{(i)}\right) \propto p\left(x^{(i)}, z^{(i)} ; \theta\right)
\]
我们知道:\(\sum_{z} Q_{i}\left(z^{(i)}\right)=1\) ,那么我可以考虑这样的情况:
\[
1 = \sum{Q_i\left( z^{\left( i \right)} \right)} \propto \sum{p\left( x^{\left( i \right)},z^{\left( i \right)};\theta \right) } = \sum_{z} p\left(x^{(i)}, z ; \theta\right)
\]
这样的话,就有下面的公式:
\[
\begin{aligned} Q_{i}\left(z^{(i)}\right) &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z} p\left(x^{(i)}, z ; \theta\right)} \\ &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \\ &=p\left(z^{(i)} | x^{(i)} ; \theta\right) \end{aligned}
\]
这一步我们称为 E 步骤,可以得到等式成立的条件, \(Q_{i}\left(z^{(i)}\right) :=p\left(z^{(i)} | x^{(i)} ; \theta\right)\) ,这个是最大化下界的条件,我们将这个条件带入 $\ell(\theta) $ 得到,也就是说,这个是最大似然函数的条件之一:那么我们可以用下面的步骤来计算 $ \theta$ ,
\[
\theta :=\arg \max _{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}
\]
那么这个 $ \theta$ 是不是最优的呢?接下来我们来证明 EM 算法中一个很关键的问题,那就是上述的 E 步骤与 M 步骤不断放缩与收敛,最终得到最优的 $ \theta$ 的值。

所以 EM 算法的步骤可以表示成下面这样:

  1. 函数声明 \(\operatorname{EM}\left(p_{Y, C}(y, c ; \theta), p_{C | Y}(c | y ; \theta), \theta^{(0)}\right)\)
  2. for iteration \(t \in 1,2, \ldots\) do
  3. \(Q_{i}^{(t)} \leftarrow P\left(z_i | x_i ; \theta^{(t-1)}\right) \quad(\text { E-step })\)
  4. \(\theta^{(t)} \leftarrow \operatorname{argmax}_{\theta} \mathbb{E}_{Q_{i}^{(t)}}\left[P(y, C ; \theta)\right] \quad\left(\mathrm{M}{-\mathrm{Step}}\right)\)
  5. if \(\theta^{(t)} \approx \theta^{(t-1)}\) then
  6. return $\theta^{(t)} $

EM 算法的收敛问题

这个收敛的思想是这样的:我们的 $ \theta $ 是直接通过极大似然函数算出的来的。那么 EM 算法迭代的步骤就是,我们不断地最大化极大似然估计函数,也就是说 \(\ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right)\) ,这样就会不断地逼近最优解。在 EM 迭代的过程中,我们不断改变是 \(Q_{i}\) ,

为了更好的说明,假设上一步我们已经得到了一个最优解 \(\ell\left(\theta^{(t)}\right)\) 以及 $ \theta^{(t)} $ 那么在这一步,我们满足下面的情况:
\[
Q_{i}^{(t)}\left(z^{(i)}\right) :=p\left(z^{(i)} | x^{(i)} ; \theta^{(t)}\right) \ \ \ Jensen不等式条件\\ 用于计算 \ell\left(\theta^{(t+1)}\right)
\]

\[
\ell\left(\theta^{(t)}\right)=\sum_{i} \sum_{z^{(i)}} Q_{i-1}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i-1}^{(t)}\left(z^{(i)}\right)}
\]

上面是一次最大化似然函数的条件,假设在上一次结束后我们得到满足如上的条件,第一个式子是,我们在上一次结束之后我们得到 \(\ell\left(\theta^{(t)}\right)\) 以及最优解 $ \theta^{(t)} $ ,那么接下来的一次 E 步骤中,就会满足上面第一个等式,

那么我们可以推出下面的不等式:
\[
\begin{aligned} \ell\left(\theta^{(t+1)}\right) & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t+1)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \\ &=\ell\left(\theta^{(t)}\right) \end{aligned}
\]
对于上面的两个不等式做出以下解释:

  1. 这个式子来自 Jensen 不等式,原式是这样的:\(\ell(\theta) \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\) 对任意的 $ Q_i $ 与 \(\theta\) 均成立,所以我们进行放缩得到第一个不等式,这个式子比较显然,

EM 算法用于混合高斯分布

\[
\sum_{i=1}^{m} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \phi, \mu, \Sigma\right)}{Q_{i}\left(z^{(i)}\right)} \\ =\sum_{i=1}^{m} \sum_{j=1}^{k} Q_{i}\left(z^{(i)}=j\right) \log \frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{Q_{i}\left(z^{(i)}=j\right)} \\ =\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_{j}\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}}
\]

然后我们用极大似然函数来将这个函数求最大值,偏导为0,
\[
\nabla_{\mu_{l}} \sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_{j}\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}} \\ =-\nabla_{\mu_{l}} \sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right) \\ =\frac{1}{2} \sum_{i=1}^{m} w_{l}^{(i)} \nabla_{\mu_{l}} 2 \mu_{l}^{T} \Sigma_{l}^{-1} x^{(i)}-\mu_{l}^{T} \Sigma_{l}^{-1} \mu_{l} \\ =\sum_{i=1}^{m} w_{l}^{(i)}\left(\sum_{l}^{-1} x^{(i)}-\Sigma_{l}^{-1} \mu_{l}\right)
\]
然后就可以得出了:
\[
\mu_{l} :=\frac{\sum_{i=1}^{m} w_{l}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{l}^{(i)}}
\]

最新文章

  1. Java分别与MySQL、Oracle、SQL Server数据库建立连接
  2. django表单
  3. angularJS--ngSelect
  4. 使用Python将HTML转成PDF
  5. 那晚征服的一道js经典的面试题
  6. HDU 1247 Hat's Words (map+string)
  7. emWin5.24 VS2008模拟LCD12864 stm32 RTX移植 【worldsing笔记】
  8. h5 web模板
  9. CDN的原理及对SEO的影响
  10. Hadoop 2.4.0完全分布式平台搭建、配置、安装
  11. 使用NSURLSession实现下载的进度
  12. 【温故而知新-万花筒】C# 异步编程 逆变 协变 委托 事件 事件参数 迭代 线程、多线程、线程池、后台线程
  13. 在mac本上折腾android 开发环境
  14. vs2008编译wxWidgets 2.8.12
  15. repeater控件自定义Url分页带参数
  16. CCS学习(三)
  17. 替换Spring Boot 的EnableCaching注解
  18. linkin大话设计模式--模板方法模式
  19. HTTP协议简单认识
  20. django后台管理--添加自定义action

热门文章

  1. 单词CAEMENT水泥CAEMENT英文
  2. Solr基础理论【排名检索、查准率、查全率】
  3. MySQL的JOIN连接
  4. crontab定时任务不执行,单独运行sh生效
  5. 离线环境下自动化部署python环境(含openssl)
  6. Httpd服务入门知识-Httpd服务常见配置案例之修改监听的IP和Port
  7. k8s如何访问pod
  8. HDU2883 kebab(最大流判断满流 + 离散化 + 区间化点)
  9. httprunner学习13-环境变量.env
  10. FTPClient中使用completePendingCommand方法注意事项