首页 / 算法 / 最大期望算法-EM算法

最大期望算法-EM算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最大期望算法-EM算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4010字，纯文字阅读大概需要6分钟。

内容图文

EM

Jensen不等式：

如果函数f为凸函数，那么存在下列公式：

  • \(f(\theta x+(1-\theta)y)\leq\theta f(x)+(1-\theta)f(y)\)

若\(\theta_1,\cdots,\theta_k\geq0,\theta_1+\cdots+\theta_k=1\)；则：

  • \(f(\theta_1 x_1 +\cdots+\theta_k x_k)\leq\theta_1f(x_1)+\cdots+\theta_kf(x_k)\)
  • \(f(E(x))\leq E(f(x))\)
  • 当且仅当 \(p(x=E(X))=1\),即\(X\)是常量时，等号成立

Jensen不等式应用于凹函数时，不等号方向反向。

EM 算法

EM思想与最大似然参数估计问题密切相关。单纯的同参数(同一类别)同分布的参数估计使用最大似然估计或矩估计解决。若是混合参数(多个类别)同分布的参数估计使用的就是EM思想。EM算法就是这样，假设我们想估计知道A和B两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

EM 推导过程（离散值）

  1. 给定的 m 个训练样本\(\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}\)，样本间独立，找出样本模型参数\(\theta\)，极大化参数模型分布的对数似然函数如下：
  • 对数似然函数：\(l(\theta)=\sum^m_{i=1}log(P(x^{i};\theta))\)

\(\theta=arg_\theta max \sum^m_{i=1}log(P(x^{i};\theta))\)

  1. 假定样本数据中存在隐含数据\(z=\{z^{(1)},z^{(2)},\cdots,z^{(k)}\}\)，此时极大化模型分布的对数似然函数如下：

    \(\theta=arg_\theta max \sum^m_{i=1}log(P(x^{i};\theta))\)

    \(=arg_\theta max \sum^m_{i=1}log(\sum_{z^{(i)}}P(z^{(i)})P(x^{(i)}|z^{(i)};\theta))\)

    \(=arg_\theta max \sum^m_{i=1}log(\sum_{z^{(i)}}P(x^{(i)},z^{(i)};\theta)\)

  2. 假设z的分布为\(Q(z;\theta)\)，且\(\sum_zQ(z;\theta)=1\)，\(Q(z;\theta)\geq0\)（如果z为连续性，那么Q是概率密度函数，需要将求和符号换成积分符号）；那么有如下公式：
  • \(l(\theta)=\sum^m_{i=1}log(\sum_{z^{(i)}}P(x^{(i)},z^{(i)};\theta)\)
  • \(=\sum^m_{i=1}log(\sum_{z^{(i)}} Q(z^{(i)};\theta)\frac{P(x^{(i)},z^{(i)};\theta)}{Q(z^{(i)};\theta)}\)
  1. 根据凹函数的Jensen不等式
    • \(l(\theta)\geq\sum^m_{i=1}\sum_{z^{(i)}} Q(z^{(i)};\theta)log( \frac{P(x^{(i)},z^{(i)};\theta)}{Q(z^{(i)};\theta)}\)
  2. 根据Jensen不等式性质,且\(\sum_zQ(z;\theta)=1\)：
    • \(\frac{p(x,z;\theta)}{Q(z,\theta)}=c\)
    • \(\Rightarrow Q(z;\theta)=\frac{p(x,z;\theta)}{c}=\frac{p(x,z;\theta)}{c\sum_zQ(z;\theta)}\)
    • \(\quad=\frac{p(x,z;\theta)}{\sum_zp(x,z;\theta)}\)
    • \(\quad=\frac{p(x,z;\theta)}{p(x;\theta)}\)
    • \(\quad=p(z|x;\theta)\)
      • 从概率的角度而言，\(p(z|x;\theta)\)表示为在θ参数的模型中，在xi的条件下，取到zi的概率。
  3. 将上式结果带入\(l(\theta)\)
    • \(l(\theta)=\sum^m_{i=1}log(\sum_{z^{(i)}} p(z|x;\theta)\frac{P(x^{(i)},z^{(i)};\theta)}{p(z|x;\theta)}\)
    • \(\theta=arg_\theta max l(\theta)\)

EM算法流程：

  1. 初始化分布参数：
  2. 第j次迭代：
    1. E步骤：估计隐藏变量的概率分布期望函数\(p(z|x;\theta^j)\)；
    2. M步骤：根据期望函数重新估计分布参数。\(\theta^{j+1}=arg_\theta max l(\theta)\)
    3. \(\theta^{j+1}\)是否收敛

EM 算法收敛证明

证明对数似然函数的值在迭代过程中增加即可

  • \(\sum^m_{i=1}log(p(x^i;\theta^{j+1}))\geq\sum^m_{i=1}log(p(x^i;\theta^{j}))\)

由：

  • \(P(x|\theta)=\frac{P(x,z|\theta)}{P(z|x,\theta)}\)

上式取对数化简得：

  • \(logP(X|\theta)=logP(X,Z|\theta) -logP(Z|X,\theta)\)

因\(\sum_zQ(Z;\theta)=\sum_zp(Z|X;\theta)=1\),记：

  • \(L(\theta,\theta^j)=\sum_{i=1}^m\sum_zp(z|x^i;\theta^j)logp(x^i,z;\theta)\)
  • \(H(\theta,\theta^j)=\sum_{i=1}^m\sum_zp(z|x^i;\theta^j)logp(z|x^i,\theta)\)

对数似然函数可以写成

  • \(\sum_{i=1}^mlogp(x^i|\theta)=L(\theta,\theta^j)-H(\theta,\theta^j)\)

故有下式

  • \(\sum_{i=1}^mlogp(x^i|\theta^{j+1}) -\sum_{i=1}^mlogp(x^i|\theta^j)\)
  • \(\quad = L(\theta^{j+1},\theta^j)-L(\theta^{j},\theta^j) - (H(\theta^{j+1},\theta^j)-H(\theta^{j},\theta^j))\)

因为：

  • \(L(\theta^{j+1},\theta^j)-L(\theta^{j},\theta^j)>0\)
  • \(H(\theta^{j+1},\theta^j)-H(\theta^{j},\theta^j)=\sum_{i=1}^m\sum_zp(z|x^i;\theta^j)log\frac{p(z|x^i,\theta^{j+1})}{p(z|x^i,\theta^j)}\)
  • \(\quad\leq\sum_{i=1}^mlog(\sum_zp(z|x^i;\theta^j)\frac{p(z|x^i,\theta^{j+1})}{p(z|x^i,\theta^j)})=0\)

所以：
\(\sum^m_{i=1}log(p(x^i;\theta^{j+1}))-\sum^m_{i=1}log(p(x^i;\theta^{j}))\geq0\)

GMM-EM

  • GMM：（Gaussian Mixture Model,高斯混合模型）是指该算法由多个高斯模型线性叠加混合而成。每个高斯模型称为 component。GMM 算法描述的是数据的本身存在的一种分布
  • 应用场景：GMM 算法常用于聚类应用中，component 的个数就可以认为是类别的数量。

内容总结

以上是互联网集市为您收集整理的最大期望算法-EM算法全部内容，希望文章能够帮你解决最大期望算法-EM算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/742289.html

来源：【匿名】