EM算法：期望最大

作者： 心有宝宝人自圆

声明：欢迎转载本文中的图片或文字，请说明出处

1 初探

设 $\boldsymbol X=(X^{(1)},X^{(2)}...,X^{(n)})$ 是取自总体的样本容量为n的 $d$ 维样本，易得样本间相互独立,则

$(X^{(1)},X^{(2)}...,X^{(n)})$ 的联合分布为 $P(\boldsymbol X|\theta)=P(X^{(1)},X^{(2)}...,X^{(n)}|\theta)=\prod_{i=1}^nP(X^{(i)})$

当然 $X^{(i)}$ 可以是d维的向量 $X_i=(X_1^{(i)},X_2^{(i)},...,X_d^{(i)})$

设 $(x_1,x_2,...,x_n)$ 是一组观测值（样本）

1.1 极大似然估计MLE

$\boldsymbol X$ 看作随机变量

$\hat\theta={\underset{\theta}{arg\ max}}\ log\ P(\boldsymbol X|\theta)$

其中 $L(\theta)=log\ P(\boldsymbol X|\theta)=\log\prod_{i=1}^nP(x_i)=\sum_{i=1}^nlog\ P(x_i)$ 称作对数似然函数

总体是一个具有确定分布的随机变量，总体中每个样本都是独立同分布的

MLE目标是通过观测结果对总体的分布参数作出统计推断

然而当我们建模的概率模型包含隐变量的时候，MLE就会出现问题，而这就是EM算法应用的场景

考虑包含隐变量 $\boldsymbol Z$ 的联合概率模型 $P(\boldsymbol X,\boldsymbol Z|\theta)$ ，此时 $\boldsymbol X,\boldsymbol Z$ 构成了完全数据

$\boldsymbol Z=(Z^{(1)},Z^{(2)},..,Z^{(n)})$ 是生成 $\boldsymbol X$ 的 $d'$ 维隐变量

对于不完全数据的联合概率分布

$P(\boldsymbol X|\theta)=\begin{cases}\int_ZP(\boldsymbol X,\boldsymbol Z|\theta)dz=\int_{z\in Z^{(1)}}\int_{z\in Z^{(2)}}...\int_{z\in Z^{(n)}}P(x,z|\theta)dz\\\sum_ZP(\boldsymbol X,\boldsymbol Z|\theta)=\sum_{z\in Z^{(1)}}\sum_{z\in Z^{(2)}}...\sum_{z\in Z^{(n)}}P(x,z|\theta)\end{cases}$

通常我们已知的就是 $P(\boldsymbol X|\theta)$ ，然而隐变量的存在使得MLE的直接求法难以计算（例如高斯混合模型）

这就是引入EM算法的原因

1.2 隐变量

隐变不是随便强行加入的，而是应该使计算变的更加简单，而且

必须保证 $P(\boldsymbol X|\theta)=\int_ZP(\boldsymbol X,\boldsymbol Z|\theta)dz=\int_ZP(\boldsymbol X|\boldsymbol Z,\theta)\cdot P(\boldsymbol Z|\theta)dz$ 成立，即隐变量不影响边缘概率分布

例如对高斯混合模型，

$P(x)=\sum_{i=1}^k\alpha_iN(x_i|\mu_i,\sigma_i),\ s.t.\ \sum_{i=1}^k\alpha_i=1$

对数似然函数 ${\cal L}(\theta)={\cal L}(\mu_1,...,\mu_k,\sigma_1,...,\sigma_k,\alpha_1,...,\alpha_{k-1})\\\qquad=\sum_{n=1}^Nlog\sum_{i=1}^k\alpha_iN(x_i|\mu_i,\sigma_i)$

log里的加号使直接计算偏导非常困难

高斯混合模型中引入的隐变量是：隐变量 $z$ 可以生成 $x$ 属于特定的高斯分布，即

$z_i\overset{生成} \rightarrow x_i,且(z_i,x_i)样本相互独立$ ，有

$P(x_i|z_i,\theta)=N(x_i|\mu_{z_i},\sigma_{z_i}),\quad P(z_i|\theta)=\alpha_{z_i},其中z_i\in\{1,2,...,k\}$

故引入隐变量 $z_i\in\{1,2,...,k\}$ （一维离散隐变量，表示 $x$ 来自第几个高斯分布）后，边缘概率 $P(x|\theta)=\int_zN(\mu_{z_i},\sigma_{z_i})\cdot\alpha_{z_i}dz_i$ ，与高斯混合模型的边缘概率一致

总结一下关于隐变量的相关概率分布的定义

设 $(z_1,z_2,...,z_n)$ 是一组生成观测数据的隐变量 $(x_1,x_2,...,x_n)$ ，满足独立同分布

$(x_i,z_i),i=1,...,n$ 同样满足独立同分布

$P(\boldsymbol Z|\boldsymbol X,\theta)=\prod_{i=1}^nP(z_i|x_i,\theta)$

$P(\boldsymbol X,\boldsymbol Z|\theta)=\prod_{i=1}^nP(x_i,z_i|\theta)=\prod_{i=1}^nP(x_i|z_i,\theta)\cdot P(z_i|\theta)$

而积分是对每个 $Z_i\in \boldsymbol Z$ 进行分别积分，所以下面采用更明确的形式

$P(Z_i|\theta)=[p_{Z_i=1},p_{Z_i=2},...,p_{Z_i=k}]_{1\times k}$ 或关于z的概率密度函数

$P(X_i|Z_i,\theta)=某种简单分布$

1.3 EM算法

EM算法： $\theta^{(t+1)}=f(\theta^{(t)}):$

$\theta^{(t+1)}=\underset{\theta}{arg\ max}\int_Zlog\ P(\boldsymbol X,\boldsymbol Z|\theta)\cdot P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz$

其中 $\int_Zlog\ P(\boldsymbol X,\boldsymbol Z|\theta)\cdot P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz$ 可以看作 $\boldsymbol Z|\boldsymbol X,\theta^{(t)}$ 分布对于 $log\ P(\boldsymbol X,\boldsymbol Z|\theta)$ 的期望

$E_{\boldsymbol Z|\boldsymbol X,\theta^{(t)}}[log\ P(\boldsymbol X,\boldsymbol Z|\theta)]=\int_Zlog\ P(\boldsymbol X,\boldsymbol Z|\theta)\cdot P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz$

显然EM算法是一种迭代算法，通过迭代的方式求取 $L(\theta)=log\ P(\boldsymbol X|\theta)$ 的极大值

然而上式所给出的迭代函目标数并非我们期望的 $log\ P(\boldsymbol X|\theta)$ 形式

因此我们简单地证明一下EM算法的收敛性，即

证明： $\theta^{(t)}\rightarrow\theta^{(t+1)},log\ P(\boldsymbol X|\theta^{(t)})\le log\ P(\boldsymbol X|\theta^{(t+1)})$
$log\ P(\boldsymbol X|\theta)=log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{P(\boldsymbol Z|\boldsymbol X,\theta)}=log\ P(\boldsymbol X,\boldsymbol Z|\theta)-\log P(\boldsymbol Z|\boldsymbol X,\theta)$
两边同时求关于 $P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})$ 分布的期望
$\begin{equation}\begin{split}左边&=\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\ P(\boldsymbol X|\theta)dz\\&=log\ P(\boldsymbol X|\theta)\cdot\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz\\&=log\ P(\boldsymbol X|\theta)\end{split}\end{equation}$

$\begin{equation}\begin{split}右边&=\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\ P(\boldsymbol X,\boldsymbol Z|\theta)dz-\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot \log P(\boldsymbol Z|\boldsymbol X,\theta)dz\\&=Q(\theta,\theta^{(t)})-H(\theta,\theta^{(t)})\end{split}\end{equation}$

即 $log\ P(\boldsymbol X|\theta)=Q(\theta,\theta^{(t)})-H(\theta,\theta^{(t)})$

故证明目标可以改写为 $Q(\theta^{(t+1)},\theta^{(t)})-H(\theta^{(t+1)})\ge Q(\theta^{(t)},\theta^{(t)})-H(\theta^{(t)},\theta^{(t)})$

不难发现 $Q(\theta,\theta^{(t)})$ 和EM算法的迭代函目标数

由于迭代的目标是 $\theta^{(t+1)}$ 在所有 $\theta$ 中使 $Q(\theta,\theta^{(t)})$ 最大，因此有
$Q(\theta^{(t+1)},\theta^{(t)})\ge Q (\theta,\theta^{(t)})\Leftrightarrow Q(\theta^{(t+1)},\theta^{(t)})\ge Q(\theta^{(t)},\theta^{(t)})$
现只需证明 $H(\theta^{(t+1)},\theta^{(t)})\le H(\theta^{(t)},\theta^{(t)})$
$\begin{equation}\begin{split}&H(\theta^{(t+1)},\theta^{(t)})- H(\theta^{(t)},\theta^{(t)})\\&=\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot \log P(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)})dz-\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot \log\ P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz\\&=\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot \log \frac{P(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)})}{P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})}\\&=-KL(P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})||P(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)}))\le0\end{split}\end{equation}$
若不使用KL散度进行证明，则还能使用Jensen不等式证明

（其实KL散度 $\ge0$ 也是用Jensen不等式证明的）

由于log(x)是凸函数，所以有 $E(log\ x)\le log\ E(x)$

而 $\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot \log \frac{P(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)})}{P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})}$ 就是 $P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})$ 分布对于 $\log \frac{P(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)})}{P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})}$ 的期望

故有 $上式\le log\int_Z\frac{P(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)})}{P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})}\cdot P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz=log\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t+1)})dz=log\ 1=0$

2. 再探EM算法

EM公式：

$\theta^{(t+1)}=\underset{\theta}{arg\ max}\int_Zlog\ P(\boldsymbol X,\boldsymbol Z|\theta)\cdot P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz$

E-step：求期望

$P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\rightarrow E_{\boldsymbol Z|\boldsymbol X,\theta^{(t)}}[log\ P(\boldsymbol X,\boldsymbol Z|\theta)]$

M-step：求极大值

$\theta^{(t+1)}=\underset{\theta}{arg\ max}\ E_{\boldsymbol Z|\boldsymbol X,\theta^{(t)}}[log\ P(\boldsymbol X,\boldsymbol Z|\theta)]$

2.1公式导出：第一种思想

注： $q(\boldsymbol Z)$ 是 $q(\boldsymbol Z|\boldsymbol X)$ 的简写
$\begin{equation}\begin{split}log\ P(\boldsymbol X|\theta)&=log\ P(\boldsymbol X,\boldsymbol Z|\theta)-\log P(\boldsymbol Z|\boldsymbol X,\theta)\\&=log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}-log\frac{P(\boldsymbol Z|\boldsymbol X,\theta)}{q(\boldsymbol Z)},其中q(\boldsymbol Z)\ne0\end{split}\end{equation}$

两边同时求关于 $q(\boldsymbol Z)$ 分布的期望
$\begin{equation}\begin{split}左边&=\int_Zq(\boldsymbol Z)\cdot log\ P(\boldsymbol X|\theta)dz\\&=log\ P(\boldsymbol X|\theta)\cdot\int_Zq(\boldsymbol Z)dz\\&=log\ P(\boldsymbol X|\theta)\end{split}\end{equation}$

$\begin{equation}\begin{split}右边&=\int_Zq(\boldsymbol Z)\cdot log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}dz-\int_Zq(\boldsymbol Z)\cdot log\frac{P(\boldsymbol Z|\boldsymbol X,\theta)}{q(\boldsymbol Z)}dz\\&=ELBO(evidence\ lower\ bound)+KL[q(\boldsymbol Z)||P(\boldsymbol Z|\boldsymbol X,\theta)]\end{split}\end{equation}$

由于 $KL(q||p)\ge0$ ，故 $log\ P(\boldsymbol X|\theta)\ge ELBO$

这里的 $ELBO$ 是关于 $\theta$ 的函数，同样可以视为关于后验分布 $q(\boldsymbol Z)$ 的期望 $E_{q(\boldsymbol Z)}[log\frac{P(\boldsymbol Z|\boldsymbol X,\theta)}{q(\boldsymbol Z)}]$

所以EM算法的想法是让 $ELBO$ 逐步达到最大，进而使 $log\ P(\boldsymbol X|\theta)$ 也达到最大

故E-step的目标是在给定 $\theta^{(t)}$ 求出 $ELBO$ 曲线，M-step是滑动 $\theta$ 是 $ELBO$ 曲线达到最大值来更新 $\theta^{(t+1)}$

1.PNG

故优化目标改写为
$\begin{equation}\begin{split}\hat\theta&=\underset{\theta}{arg\ max}\ ELBO=\underset{\theta}{arg\ max}\int_Zq(\boldsymbol Z)\cdot log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}dz\\&令q(\boldsymbol Z)=P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\\&=\underset{\theta}{arg\ max}\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})}dz\\&=\underset{\theta}{arg\ max}\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\ P(\boldsymbol X,\boldsymbol Z|\theta)-log\ P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\ P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz\end{split}\end{equation}$
然而 $P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\ P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})$ 项与 $\theta$ 无关，故优化目标可进一步改写为
$\underset{\theta}{arg\ max}\int_ZP(\boldsymbol Z|\boldsymbol X,\theta^{(t)})\cdot log\ P(\boldsymbol X,\boldsymbol Z|\theta)$

2.1公式导出：第二种思想

$\begin{equation}\begin{split}log\ P(\boldsymbol X|\theta)&=log\int_ZP(\boldsymbol X,\boldsymbol Z|\theta)dz\\&=log\int_Z\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}\cdot \boldsymbol q(\boldsymbol Z)dz\\&关于概率密度的积分一般都可以看作对于某一变量求期望\\&=log\ E_{q(\boldsymbol Z)}[\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}]\end{split}\end{equation}$

根据Jensen不等式，当 $f(x)$ 为凸函数， $f(\sum\lambda_jx_j)\ge\sum\lambda_jf(x_j),\lambda_j\ge0,\sum\lambda_j=1$

对于 $log(x)$ 的有 $log\ E_{p(x)}(x)\ge E_{p(x)}log(x)$

$log\ E_{q(\boldsymbol Z)}[\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}]\ge E_{q(\boldsymbol Z)}[log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}],当且仅当\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}=const时等号成立$
此时 $E_{q(\boldsymbol Z)}[log\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{q(\boldsymbol Z)}]$ 为 $log\ P(\boldsymbol X|\theta)$ 的下界，即 $ELBO$

当等号成立时，有
$q(\boldsymbol Z)=\frac 1 CP(\boldsymbol X,\boldsymbol Z|\theta)\\1=\int_Z q(\boldsymbol Z)dz=\int_Z\frac 1 CP(\boldsymbol X,\boldsymbol Z|\theta)dz=\frac 1 C\int_Z\frac 1 CP(\boldsymbol X,\boldsymbol Z|\theta)dz=\frac 1 CP(\boldsymbol X|\theta)\\C=P(\boldsymbol X|\theta)\Rightarrow q(\boldsymbol Z)=\frac{P(\boldsymbol X,\boldsymbol Z|\theta)}{P(\boldsymbol X|\theta)}\\\Rightarrow q(\boldsymbol Z)=P(\boldsymbol Z|\boldsymbol X,\theta)$
换句话说，为了保证等号成立， $q(\boldsymbol Z)$ 必须使用后验概率的形式，即 $q(\boldsymbol Z)=P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})$

3.广义EM

在前面的算法中我们假设 $q(\boldsymbol Z)=P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})$

但实际情况可能（大部分情况下）后验 $P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})$ 是难以求出的（一般和生成模型的复杂度有关）

令 ℒ $(q,\theta)=ELBO$ ，则 $log\ P(\boldsymbol X|\theta)=$ ℒ $(q,\theta)+KL(q||P)$

当 $\theta$ 固定时， $log\ P(\boldsymbol X|\theta)$ 也是固定的，此时若 $KL(q||P)$ 越小 $\ \Leftrightarrow ELBO$ 越大

此时 $q(\boldsymbol Z)$ 就可以变成优化问题： $\hat q=\underset{q}{arg\ max}\ KL(q||P)=\underset{q}{arg\ min}\$ ℒ $(q,\theta)$

再固定 $\hat q$ ， $\hat \theta=\underset{\theta}{arg\ max}\$ ℒ $(\hat q,\theta)$

3.1 广义EM算法

E-step：固定 $\theta$ ， $\hat q=\underset{q}{arg\ max}\ KL(q||P)=\underset{q}{arg\ min}\$ ℒ $(q,\theta)$

$q^{(t+1)}=\underset{q}{arg\ max}ℒ(q,\theta^{(t)})$

M-step：固定 $\hat q$ ， $\hat \theta=\underset{q}{arg\ max}\$ ℒ $(\hat q,\theta)$

$\theta^{(t+1)}=\underset{\theta}{arg\ max}ℒ(q^{(t+1)},\theta)$

所以EM是采用了坐标上升法（固定一个维度优化另一个维度）双优化问题

3.2 ELBO

ℒ $(q,\theta)$$=E_q[log\ P(\boldsymbol X,\boldsymbol Z|\theta)-log\ q(\boldsymbol Z)]=E_q[log\ P(\boldsymbol X,\boldsymbol Z|\theta)]-E_q[log\ q(\boldsymbol Z)]$

不难发现 $-E_q[log\ q(\boldsymbol Z)]$ 为熵的定义， $H[q(\boldsymbol Z)]$

ℒ $(q,\theta)$$=E_q[log\ P(\boldsymbol X,\boldsymbol Z|\theta)]+H[q(\boldsymbol Z)]$

在E-step已经将 $q$ 固定下来了，熵 $H[q(\boldsymbol Z)]$ 是确定值，这意味着M-step的优化目标与熵无关

这是广义EM与狭义（原始）EM与的M-step的优化目标可以化成一致的形式：
$\theta^{(t+1)}=\underset{\theta}{arg\ max}\ E_{q^{(t+1)}}[log\ P(\boldsymbol X,\boldsymbol Z|\theta)]$
这意味着狭义（原始）EM就是广义EM的一个特例

4. EM算法实例—GMM模型的参数估计

E-step：

$\quad\int_Zlog\ P(\boldsymbol X,\boldsymbol Z|\theta)\cdot P(\boldsymbol Z|\boldsymbol X,\theta^{(t)})dz\\=\sum_{z_1\in Z^{(1)}}\sum_{z_2\in Z^{(2)}}...\sum_{z_n\in Z^{(n)}}\ [\sum_{i=1}^nlog\ (P(x_i|z_i,\theta)\cdot P(z_i|\theta))\cdot \prod_{i=1}^nP(z_i|x_i,\theta)$

[图片上传失败...(image-399ee1-1595132374108)]

对于高斯混合模型：

$P(x_i|z_i,\theta)=N(\mu_{z_i},\sigma_{z_i}),\quad P(z_i|\theta)=\alpha_{z_i},其中z_i\in\{1,2,...,k\}$

$上式=\sum_{z_1\in Z^{(1)}}\sum_{z_2\in Z^{(2)}}...\sum_{z_n\in Z^{(n)}}[\sum_{i=1}^n(log\ N(x_i|\mu_{z_i},\sigma_{z_i})+log\ \alpha_{z_i})\cdot \prod_{i=1}^nP(z_i|x_i,\theta^{(t)})]$

令 $log\ N(\mu_{z_i},\sigma_{z_i})+log\ \alpha_{z_i}=f(z_i),\prod_{i=1}^nP(z_i|x_i,\theta^{(t)})=p(z_1,z_2,...,z_n)$

$\begin{equation}\begin{split} 上式&=\sum_{z_1\in Z^{(1)}}\sum_{z_2\in Z^{(2)}}...\sum_{z_n\in Z^{(n)}}[\sum_{i=1}^nf(z_i)\cdot p(z_1,z_2,...,z_n)]\\ &=\sum_{z_1\in Z^{(1)}}\sum_{z_2\in Z^{(2)}}...\sum_{z_n\in Z^{(n)}}[f(z_1)\cdot p(z_1,z_2,...,z_n)+f(z_1)\cdot p(z_1,z_2,...,z_n)+......]\\ &=\sum_{z_1\in Z^{(1)}}\sum_{z_2\in Z^{(2)}}...\sum_{z_n\in Z^{(n)}}f(z_1)\cdot p(z_1,z_2,...,z_n)+......\\ &=\sum_{z_1\in Z^{(1)}}f(z_1)\cdot\underbrace{\sum_{z_2\in Z^{(2)}}...\sum_{z_n\in Z^{(n)}}p(z_1,z_2,...,z_n)}_{边缘概率p(z_1)}+......\\ &=\sum_{z_1\in Z^{(1)}}f(z_1)\cdot p(z_1)+\sum_{z_2\in Z^{(2)}}f(z_2)\cdot p(z_2)+...+\sum_{z_n\in Z^{(n)}}f(z_n)\cdot p(z_n)\\ &=\sum_{i=1}^n\sum_{z_i=1}^k(log\ \alpha_{z_i}+log\ N(x_i|\mu_{z_i},\sigma_{z_i}))\cdot P(z_i|x_i,\theta^{(t)}) \end{split}\end{equation}$

M-step：
- 最大化 $\alpha$
  
  $\frac{\part \sum_{i=1}^n\sum_{z_i=1}^k(log\ \alpha_{z_i}+log\ N(x_i|\mu_{z_i},\sigma_{z_i}))\cdot P(z_i|x_i,\theta^{(t)})}{\part[\alpha_1,\alpha_2,...,\alpha_n]}=[\begin{matrix}0&0&...&0\end{matrix}],\ s.t.\sum_{i=1}^n\alpha_i=1$
  
  使用拉格朗日乘数法，解得
  
  $\alpha_k^{(t+1)}=\frac{1}{n}\sum_{i=1}^nP(z_i=k|x_i,\theta^{(t)})$
- 最大化 $\mu$
  
  $\mu_k^{(t+1)}=\frac{\sum_{i=1}^nx_i\cdot P(z_i=k|x_i,\theta^{(t)})}{\sum_{i=1}^nP(z_i=k|x_i,\theta^{(t)})}$
- 最大化 $\sigma$
  
  $\sigma_k^{(t+1)}=\frac{\sum_{i=1}^n(x_i-\mu_i^{(t+1)})(x_i-\mu_i^{(t+1)})^TP(z_i=k|x_i,\theta^{(t)})}{\sum_{i=1}^nP(z_i=k|x_i,\theta^{(t)})}$

Reference

[1] 【机器学习】【白板推导系列】

[2] NLP —— 图模型（零）：EM算法简述及简单示例

[3] EM算法及其应用（一）

[4] 徐亦达机器学习：Expectation Maximization EM算法

转载请说明出处。