EM算法
Tags: 参数估计 场景: 1. 半监督学习分类器 2. 数据预处理：填充特征缺失值 3. 求解隐马尔科夫模型中的发射概率 4. 聚类
原理简介
概率模型中如果全部是观测变量，在给定数据之后，直接可以用最大似然估计或者贝叶斯估计模型参数
概率模型中如果存在隐变量就不能直接估计
EM是迭代求解概率模型中的隐变量，分两步，因为要求解期望【均值】，又称为期望最大极大算法
- E步求解期望
- M步求解极大
为啥用EM算法估计模型参数而不用最大似然估计
- 概率模型中包含隐变量的时候，最大似然依据的是已知样本，而隐变量没有对应样本，无法求解 【目标函数包含了未观测数据的分布的积分和对数】
- 公式推导
观测变量：Y=[{ $$y_1$$ ,$$y_2$$,$$y_3$$.....,$$y_n$$}]
隐变量： Z=[{$$z_1$$,$$z_2$$......,$$z_m$$}]
对数似然函数 $$\quad logP(Y;\theta) \quad \theta:$$模型参数 $$\quad\quad$$分解后发现$$P(Z;\theta)$$求解不出$$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$
分解似然函数：$$logP(Y;\theta)=\sum_ilogP(Y=y_i;\theta)=\sum_ilog\sum_ZP(Y=y_i,Z;\theta) =\sum_ilog\bigg[\sum_ZP(Y=y_i|Z;\theta)P(Z;\theta)]\bigg] \quad\quad$$
EM算法要优化的目标函数是什么
对数似然函数： $$L(\theta) = logP(Y;\theta) $$
优化目标是：极大化对数似然函数值 也就是求解$$L(\theta)$$的极大值解$$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad $$
优化方法是：多次迭代估计$$\theta$$,记$$\theta^i$$为第i次迭代估计值,$$\theta$$为最新估计值,使得$$L(\theta)$$的值在增加,即$$L(\theta)>L(\theta^i)=>logP(Y;\theta)-logP(Y;\theta^i)>0 $$
-
jesen 不等式 如果函数f(x)是凸函数，自变量的均值E(x)对应的函数值 f(E(x)) 大于 函数值的均值 E( f(x) )。见右图。
Jesen不等式 应用到对数似然函数上：$$P(y_i)=\lambda_i \quad $$且$$\sum_iP(y_i)=1,\quad log\sum_i\lambda_iy_i >=\sum_ilog(\lambda_iy_i) $$
$$logP(Y;\theta)-logP(Y;\theta^i)=\sum_jlog\sum_ZP(Y=y_j,Z;\theta)-\sum_jlogP(Y=y_j;\theta^i)$$ 因为：$$\sum_ZP(Z|Y;\theta)=1 $$和Jesen所以：$$>=\sum_jlog\sum_ZP(Z|Y=y_j;\theta^i)\frac{\sum_ZP(Y=y_j,Z;\theta)}{\sum_ZP(Z|Y=y_j;\theta^i)}-log\sum_jP(Y=y_j;\theta^i)$$
$$ = \sum_j \bigg[\sum_ZP(Z|Y=y_j;\theta^i)log\frac{\sum_ZP(Y=y_j,Z;\theta)}{\sum_ZP(Z|Y=y_j;\theta^i)}-log\sum_jP(Y=y_j;\theta^i)*\sum_ZP(Z|Y=y_j;\theta^i)\bigg] $$
$$ =\sum_j\bigg[\sum_ZP(Z|Y=y_j;\theta^i)log\frac{P(Y=y_j,Z;\theta)}{P(Z|Y=y_j;\theta^i)\sum_jP(Y=y_j;\theta^i)}\bigg] $$
$$ =\sum_j\bigg[\sum_ZP(Z|Y=y_j;\theta^i)log\frac{P(Y=y_j|Z;\theta)P(Z;\theta)}{P(Z|Y=y_j;\theta^i)\sum_jP(Y=y_j;\theta^i)}\bigg] $$
求取关于$$\theta$$最大值，将于$$\theta$$无关项省略后$$\quad $$目标函数为$$\quad argmax\quad\sum_j\bigg[\sum_ZP(Z|Y=y_j;\theta^i)logP(Y=y_j,Z;\theta)\bigg] $$
EM算法步骤
- 输入：
观测变量：Y=[{ $$ y_1 $$ ,$$y_2$$,$$y_3$$.....,$$y_n$$}] 。联合分布 $$P(Y,Z|\theta) \quad $$条件分布$$P(Z|Y;\theta) \quad $$联合分布和条件分布的形式已知（比如说高斯分布等），但是参数未知（比如均值、方差）$$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $$
- 输出： 模型估计参数 theta
-
具体步骤：
-
选择参数的初值 $$\theta$$，开始迭代。$$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $$
-
E 步计算过程 $$\theta^i $$为第i次迭代的估计值，第i+1次迭代过程为：$$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad $$
令 $$Q(\theta,\theta^i)=\sum_{j=1}^NE_{P(Z|Y=y_j;\theta^i)}logP(Y=y_j,Z;\theta)=\sum_{j=1}^N\bigg(\sum_ZP(Z|Y=y_j;\theta^i)logP(Y=y_j,Z;\theta)\bigg)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad $$
3.M步计算使得$$Q(\theta,\theta^i)$$最大值的$$\theta$$,确定i+1次迭代估计值$$\theta^{i+1} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$
$$ \theta^{i+1} = argmax_\theta(Q(\theta,\theta^i)) $$
- 重复上面两步，直到收敛
-
EM算法是如何和高斯核结合在一起使用的
1. 什么是高斯分布,它的概率密度函数PDF是怎样的
高斯分布又叫正态分布，
数据均值(期望)： $$\mu \quad$$ 标准方差：$$\sigma^2 \quad$$ 高斯分布：$$X-N(\mu,\sigma^2) \quad $$其中$$\mu=0,\sigma^2=1$$称为标准正态分布 $$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$
概率密度函数：$$\frac{1}{\sqrt{2\pi}\sigma}exp\biggr( - \frac{(x-\mu)^2}{2\sigma^2}\bigg)\quad\quad$$所以标准正态分布PDF：$$\frac{1}{\sqrt{2\pi}}exp\biggr( - \frac{x^2}{2}\biggr)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$
2. 高斯核如何结合EM的【高斯混合模型】
为每一个隐变量创建一个对应的高斯核【K=M】，高斯核的概率密度函数来表示该隐变量出现的概率。【也不一定和隐变量数量一致，高斯混合模型的分量数 K，隐变量个数M 观测变量个数 N】
所以结合高斯核的EM联合概率函数和条件概率函数如下：
第k个分模型：$$\quad\phi(y;\theta_k)=\frac{1}{\sqrt{2\pi}\sigma_k}exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg) \quad\quad$$ 对应的模型参数：$$ \quad \theta_k={\mu_k,\sigma_k^2,\alpha _k} \quad $$其中$$ \alpha_k$$为采用k分模型的概率$$ \quad P(z=k)=\alpha_k \quad $$v表示的是观测数据y来自k模型的概率
联合概率函数：$$P(Y=y_j,Z=k;\theta)=\alpha_k\frac{1}{\sqrt{2\pi}\sigma_k}exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)\quad\quad $$它的对数$$\quad LogP(Y=y_j,Z=k;\theta)=log(\alpha_k)-log(\sqrt{2\pi}\sigma_k)-\frac{(y-\mu_k)^2}{2\sigma_k^2}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$
后验概率【条件概率】：$$P(Z|Y=y_j;\theta^i)=\frac{P(Y=y_j,Z=k;\theta^i)}{\sum_{t=1}^KP(Y=y_j,Z=t;\theta)}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$ Q函数：$$Q(\theta,\theta^i)=\sum_{j=1}^N\bigg(\sum_ZP(Z|Y=y_j;\theta^i)P(Y=y_j,Z;\theta)\bigg)=\sum_{j=1}^N\sum_{k=1}^KP(Z|Y=y_j;\theta^i)\bigg(log(\alpha_k)-log(\sqrt{2\pi}\sigma_k)-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)$$
所以EM高斯混合模型在参数估计的时候主要计算：
根据偏导数为0，$$\sum_{k=1}^K\alpha_k=1$$得到：$$\alpha_k^{i+1}=\frac{n_k}{N}=\frac{\sum_{j=1}^NP(z=k|y=y_j;\theta^i)}{N}\quad\quad\alpha_k$$ 表示采用k分模型的概率，也就是观测数据来自k分模型的概率，n_k也就是观测数据来自k分模型的数量
$$\mu_k^{i+1} = \frac{Sum_k}{n_k}=\frac{\sum_{j=1}^Ny_jP(z=k|y=y_j;\theta^i)}{\sum_{j=1}^NP(z=k|y=y_j;\theta^i)} \quad\quad$$ \mu_k:表示来自k模型观测变量的均值，sum_k:表示来自k模型观测变量总和，n_k:表示来自k模型观测变量的个数
$$ \sigma_k^{2,i+1}=\frac{Var_k}{n_k}=\frac{\sum_{i=1}^N(y_j-\mu_k^i)^2P(z=k|y=y_i;\theta^i)}{n_k}\quad\quad \sigma_k^2:表示来自k模型观测变量的标准差，Var表示来自K模型观测变量偏离均值的平方和 $$