EM算法与高斯混合模型

EM算法（The Expectation-Maximization Algorithm）可以解决HMM的参数估计问题，在MT中的词对齐中也会用到。

Jensen不等式

Jensen不等式表述如下：
如果f是凸函数，X是随机变量，那么E[f(X)]≥f(E[X])$E[f(X)]\ge f(E[X])$特别地，如果f是严格凸函数，那么E[f(X)]=f(E[X])$E[f(X)]=f(E[X])$;当且仅当p(x=E[x])=1$p(x=E[x])=1$,也就说X$X$是常量。用图表示就是：

Jensen不等式应用于凹函数时，不等号方向反向，也就是E[f(X)]≤f(E[X])$E[f(X)]\le f(E[X])$

Jensen’s Inequality
当f$f$为凸函数且 ∑iλi=1, λi≥0$\sum _i{\lambda }_i=1,{\lambda }_i\ge 0$ 时，有f(∑iλixi)≤∑iλif(xi)$f(\sum _i{\lambda }_i{x}_i)\le \sum _i{\lambda }_{i}f(x_i)$

极大似然估计

极大似然估计(Maximum Likelihood Estimation)提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。但其前提是，假设所有的采样都是独立同分布的。
假设x1,x2,…,xn dii$x_1,x_2,\dots ,x_{n}dii$,参数为θ的模型f产生上述采样可表示为:

此时x1,x2,…,xn$x_1,x_2,\dots ,x_n$为已知，θ$\theta$为未知，则定义为

在实际应用中常用的是两边取对数（Ln 或者 log不影响），得到公式如下：

其中lnL(θ|x1,x2,…,xn)$\ln L(\theta |x_1,x_2,\dots ,x_n)$称为对数似然，而ι^$\hat{\iota }$称为平均对数似然。而我们平时所称的最大似然为最大的对数平均似然，即：

显然对L(θ|X)$L(\theta |X)$求导，令导数得0 ，求得的解即为最优的θ∗${\theta }^{\ast }$了,而且对MLE来说数据量越多，所得到的模型会越能反映数据的真实分布。

EM算法

期望最大化算法（Expectation Maximization Algorithm，EM）用于含有隐变量概率模型的MLE，隐变量就是每个可见随机变量的值都对应着一个隐藏的随机变量。参见三硬币模型实例

问题描述

给定一个训练集X=x1,…,xm$X=x^1,\dots ,x^m$，我们希望拟合包含隐含变量z的模型P(x,z;θ)$P(x,z;\theta )$中的参数 θ。根据模型的假设，每个我们观察到的xi$x^i$还对应着一个我们观察不到的隐含变量zi$z^i$，我们记Z=z1,…,zm$Z=z^1,\dots ,z^m$。做极大对数似然就是要求θ的“最优值”：

其中

直接使用log 套∑的形式直接求解θ往往非常困难。EM 通过迭代逐步极大化L(θ)$L(\theta )$，假设第i次迭代后θ的估计值是θi,θi${\theta }^i,{\theta }^i$已知后，下一次迭代需要使得L(θ)$L(\theta )$更大.

EM算法基本步骤

输入:观测数据X，隐变量数据 Z，联合分布P(X,Z|θ)$P(X,Z|\theta )$
输出：极大似然参数θ
1. 选择初始参数θ0${\theta }^0$；
2. E Step：计算隐变量Z$Z$在参数θi${\theta }^i$下的后验分布P(Z|X,θi)$P(Z|X,{\theta }^i)$以得到：

EZ|X;θiL(θ|X,Z):=EZ|X;θilogP(X,Z|θ)=∑ZP(Z|X,θi)logP(X,Z|θ)$$\begin{array}{rl}{E}_{Z|X;{\theta }^i}L(\theta |X,Z)& :=E_{Z|X;{\theta }^i}\log P(X,Z|\theta )\\ & =\sum _{Z}P(Z|X,{\theta }^i)\log P(X,Z|\theta )\end{array}$$

3. M Step：估计θ(i+1)${\theta }^{(i+1)}$的值：

θ(i+1)=argmaxθEZ|X,θiL(X,Z|θ)$${\theta }^{(i+1)}=arg\underset{\theta }{max}{E}_{Z|X,{\theta }_i}L(X,Z|\theta )$$

4. 重复（2）至（3），直到收敛.

EM 算法每次迭代都建立在上轮迭代对θ的最优值的估计θi${\theta }^i$上,利用它可以求出Z的后验概率P(Z|X,θi)$P(Z|X,{\theta }^i)$ ，进而求出L(θ|X,Z)$L(\theta |X,Z)$ 在分布Z∼P(Z|X,θ)$Z\sim P(Z|X,\theta )$上的期望 EZ|X;θiL(θ|X,Z)$E_{Z|X;{\theta }^i}L(\theta |X,Z)$。

因为argmaxθL(θ|X,Z)$\arg \underset{\theta }{max}L(\theta |X,Z)$在未知Z的情况下难以直接计算,EM算法就转而通过最大化它的期望EZ|X;θiL(θ|X,Z)$E_{Z|X;{\theta }^i}L(\theta |X,Z)$来逼近θ的最优值，得到θ(t+1)${\theta }^{(t+1)}$。注意由于L(θ|X,Z)$L(\theta |X,Z)$的这个期望是在Z的一个分布上求的，这样得到的表达式就只剩下θ一个未知量，因而绕过了z未知的问题。而θ(i+1)${\theta }^{(i+1)}$又可以作为下轮迭代的基础，继续向最优逼近。

算法中E-step就是在利用θi${\theta }^i$ 求期望EZ|X;θiL(θ|X,Z)$E_{Z|X;{\theta }^i}L(\theta |X,Z)$，这就是所谓“Expectation”；
M-step就是通过寻找 θ(i+1)${\theta }^{(i+1)}$ 最大化这个期望来逼近θ的最优值，这就“Maximization”。

EM算法推导

引入一个概率分布Q(θ,θi)=EZ|X,θilogL(θ|X,Z)=P(Z|X,θi)$Q(\theta ,{\theta }^i)=E_{Z|X,{\theta }^i}\log L(\theta |X,Z)=P(Z|X,{\theta }^i)$,利用分子分母同乘Q(θ,θi)$Q(\theta ,{\theta }^i)$的trick(期望可以写成概率和样本的乘积形式)，得到：

根据 Jensen 不等式,对于任意分布Q$Q$都有：

且上面的不等式在P(X|Z,θ)Q(θ,θi)$\frac{P(X|Z,\theta )}{Q(\theta ,{\theta }^i)}$为常数时取等号。之后Q（θ,θi）$Q（\theta ,{\theta }^i）$用贝叶斯公式展开：

带入回上式：

第二行P(X|Z),P(X|Z,θi)$P(X|Z),P(X|Z,{\theta }^i)$这两个其实相同所以约去；最后一行在已知θi${\theta }^i$时，仅
Q(θ,θi)$Q(\theta ,{\theta }^i)$不固定,所以需要不断调整下一时刻θ$\theta$使之最大。即可得到：

除以上方法推导，还可以用前项减后项方法推导L(θ)−L(θ(i))$L(\theta )-L({\theta }^{(i)})$
具体见The Expectation Maximization Algorithm A short tutorial

高斯混合模型

高斯分布

假设数据x∈Rn$x\in R^n$服从参数为μ,Σ$\mu ,\Sigma$的高斯分布:

这里μ$\mu$为均值，Σ$\Sigma$为协方差矩阵，对于单个高斯分布，当给定数据集之后，直接进行 MLE 即可估计高斯分布的参数；但是有些数据集是多个高斯分布叠加在一起形成的，也就数据集是由多个高斯分布产生的，如下图所示三个高斯分布叠加在一起：

多个高斯分布叠加在一起便是混合高斯模型 GMM,其的定义如下：

这里K$K$表示高斯分布的个数,πk${\pi }_k$代表混合系数,且满足0≤πk≤1,∑kπk=1$0\le {\pi }_k\le 1,\sum _k{\pi }_k=1$,可以把πk${\pi }_k$看做每个模型的权重。如果把 GMM 用在聚类中，则样本x的类别即为argmaxkπk$\arg \underset{k}{max}{\pi }_k$

在 GMM 中，需要估计的参数为πk，μk，Σk${\pi }_k，{\mu }_k，{\mathbf{\Sigma }}_k$模型里每个观测数据x都对应着一个隐变量z∈RK$\mathbf{z}\in {\mathbb{R}}^K$，代表的即为类别变量， 且zk∈{0,1}${\mathbf{z}}_k\in \left\{0,1\right\}$,一个样本可以属于多个类别，叠加起来概率为 1，这里显而易见有：

对于GMM的参数采用EM算法来求解，其完全数据的联合分布为：

写成对数似然函数的形式：

EM算法求解GMM的步骤

E步： 使用参数θold=(πold,μold,Σold)${\theta }^{old}=({\pi }^{old},{\mu }^{old},{\mathbf{\Sigma }}^{old})$，计算每个样本xn$x_n$对应隐变量zn$z_n$的后验分布：

γ(znk)=p(zn=k|xn;μold,Σold)=p(znk=1)p(xnk|znk=1)∑Kj=1p(znj=1)p(xn|znj=1)=πoldkN(xn|μoldk,Σoldk)ΣKj=1πoldjN(xn|μoldj,Σoldj)$$\begin{array}{rl}\gamma (z_{nk})=p(z_n=k|{\mathbf{x}}_n;{\mu }^{old},{\mathbf{\Sigma }}^{old})& =\frac{p(z_{nk}=1)p({\mathbf{x}}_{\mathbf{n}\mathbf{k}}|z_{nk}=1)}{\sum _{j=1}^{K}p(z_{nj}=1)p({\mathbf{x}}_{\mathbf{n}}|z_{nj}=1)}\\ & =\frac{{\pi }_k^{old}\mathcal{N}({\mathbf{\text{x}}}_n|{\mu }_k^{old},{\mathbf{\Sigma }}_k^{old})}{{\mathrm{\Sigma }}_{j=1}^K{\pi }_j^{old}\mathcal{N}({\mathbf{\text{x}}}_n|{\mu }_j^{old},{\mathbf{\Sigma }}_j^{old})}\end{array}$$

M步： 极大化Q函数的计算

Q(θ,θold)=∑Zp(Z|X,θold)lnp(X,Z|θ)=∑Zp(Z|X,θold)lnp(X|Z,θ)P(Z|θ)=∑n=1N∑k=1Kγ(znk){lnπk+lnN(xn|μk,Σk)}$$\begin{array}{rl}\mathcal{Q}(\theta ,{\theta }^{\text{old}})& =\sum _{Z}p(Z|X,{\theta }^{old})\ln p(X,Z|\theta )\\ & =\sum _{Z}p(Z|X,{\theta }^{old})\ln p(X|Z,\theta )P(Z|\theta )\\ & =\sum _{n=1}^N\sum _{k=1}^K\gamma (z_{nk})\left\{\ln {\pi }_k+\ln \mathcal{N}({\mathbf{x}}_n|{\mu }_k,{\mathbf{\Sigma }}_k)\right\}\end{array}$$

得到下一步迭代的参数：

θnew=argmaxθQ(θ,θold)$${\theta }^{new}=\arg \underset{\theta }{max}\mathcal{Q}(\theta ,{\theta }^{\text{old}})$$

对Q函数求导，令倒数得0，即可求得下一次迭代的参数值

μnewkΣnewkπnewk=1Nk∑n=1Nγ(znk)xn=1Nk∑n=1Nγ(znk)(xn−μnewk)(xn−μnewk)T=NkN$$\begin{array}{rl}{\mu }_k^{new}& =\frac{1}{N_k}\sum _{n=1}^N\gamma (z_{nk}){\mathbf{x}}_n\\ {\mathbf{\Sigma }}_k^{new}& =\frac{1}{N_k}\sum _{n=1}^N\gamma (z_{nk})({\mathbf{x}}_n-{\mu }_k^{new})({\mathbf{x}}_n-{\mu }_k^{new}{)}^T\\ {\pi }_k^{new}& =\frac{N_k}{N}\end{array}$$

其中：

Nk=∑n=1Nγ(znk)$$N_k=\sum _{n=1}^N\gamma (z_{nk})$$