1. EM 算法推论和相关数学知识

1.1. Describe

EM(Expectation-Maxmization)算法是一个迭代算法
主要应用的理论是极大似然估计
对于贝叶斯算法来说，训练的样本必须是完整的，属性值如果缺失会对结果有较大的影响。EM算法对于缺失属性的数据集有较好的表现。

期望最大化(EM)算法是一种被广泛用于极大似然(ML)估计的迭代性型计算方法。处理大量数据不完整问题非常有用。

Advantages：

-　数值计算的稳定
-　实现简单
-　可靠全局收敛

1.2. Theory

1.2.1. 先验概率&后验概率

接下来把c记成$\Theta_c,\Theta_c$Θc​,Θc​是c的一组条件。

1. 结果还没有发生，我们通过一些经验等猜测某个结果可能发生的概率。先验（通过历史原因求）

是$\Theta_c$Θc​类别的概率。

$P（\Theta_c）$P（Θc​）

2. 结果已经发生，根据结果估计发生的原因的概率。后验(通过结果求原因)

$P(\Theta_c | x)$P(Θc​∣x)

$\Theta_c代表原因，x代表结果。在已知结果求各种原因的概率$Θc​代表原因，x代表结果。在已知结果求各种原因的概率
对于机器学习，$\Theta$Θ代表

1.2.2. 极大似然估计/条件概率 （通过原因求结果）

Maximum Likelihood Estimation ，简称MLE，是一种根据采用来估计概率分布参数的方法。

先定下来原因，然后根据原因求结果。
如果是$\Theta$Θ类别里的(结果)，求x的概率。

$P(x|\Theta )$P(x∣Θ)

1.2.3. Jensen不等式

优化理论中的函数凹凸性和高数中是相反的，

如果$f''(x) \geq0$f′′(x)≥0是，是凸函数
如果$f''(x) \leq0$f′′(x)≤0是，是凹函数

$凸函数：E[f(X)] \geq f(EX)$凸函数：E[f(X)]≥f(EX)

$凹函数：E[f(X)] \leq f(EX)$凹函数：E[f(X)]≤f(EX)

图片来源

以凹函数为例，开口向上。如果概率为0.5的二项分布，E[f(x)]相当于是对纵轴两个值加和除以2，一定大于对应的f(x)取值。简单理解：[f(a)+f(b)]/2 >= f((a+b)/2)

1.2.4. 联合概率密度&边缘概率密度

联合概率分布
二维离散随机变量(X,Y)可能取值为(Xi,Yj)（i,j=1,2,…）

$P\{ X=x_i,Y=y_j\}=p_{i,j}, \quad i,j=1,2....$P{X=xi​,Y=yj​}=pi,j​,i,j=1,2....
成为随机变量(X,Y)的概率分布(联合概率分布)

连续型：
$F(x,y)=\int_{-\infty}^{x}\int_{-\infty}^{y}f(u,v)dudv\quad -\infty < x,y <+\infty$F(x,y)=∫−∞x​∫−∞y​f(u,v)dudv−∞<x,y<+∞

边缘概率分布
$p_{i \ ·}=P\{X=x_i\} ,i=1,2....$pi ⋅​=P{X=xi​},i=1,2....称为(X,Y)关于X的边缘概率分布。

显然$p_{i \ ·}=P\{X=x_i\}=\sum_{j=1}^{+\infty}P\{X=x_i,Y=y_j\}=\sum_{j=1}^{+\infty}p_{ij} ,\quad i=1,2...$pi ⋅​=P{X=xi​}=∑j=1+∞​P{X=xi​,Y=yj​}=∑j=1+∞​pij​,i=1,2...

连续型：
对一个进行积分。

1.2.5. 数学期望相关

数学期望：
$E(X)=\sum_{k=1}^{+\infty}x_k p_k$E(X)=∑k=1+∞​xk​pk​
$E(X)=\int_{-\infty}^{+\infty}xf(x)dx$E(X)=∫−∞+∞​xf(x)dx

随机变量X的函数Y=g(X)的数学期望

• 离散型
  $E(Y)=E[g(x)]=\sum_i g(x_i)p(x_i)$E(Y)=E[g(x)]=∑i​g(xi​)p(xi​)

• 连续型
  $E(Y)=E[g(x)]=\int_{-\infty}^{+\infty}g(x)p(x)$E(Y)=E[g(x)]=∫−∞+∞​g(x)p(x)

1.2.6. 推导过程

参考来源

Begin
$X=\{x_i\}$X={xi​}完整数据， $Z=(z_i)$Z=(zi​)隐数据 $Y=(X,Z)，Y=\{(x_1,z_1)....\}$Y=(X,Z)，Y={(x1​,z1​)....}，

1. 根据边缘概率分布，
   $logL(\theta)=\sum_iln(x_i;\theta)=\sum_i ln \sum_{z}p(x_i,z_i;\theta) \quad (1)$logL(θ)=∑i​ln(xi​;θ)=∑i​ln∑z​p(xi​,zi​;θ)(1)

离散型边缘概率密度等于另一个维度累加。
上文提到的 $p_{i \ ·}=P\{X=x_i\}=\sum_{j=1}^{+\infty}P\{X=x_i,Y=y_j\}=\sum_{j=1}^{+\infty}p_{ij} ,\quad i=1,2...$pi ⋅​=P{X=xi​}=∑j=1+∞​P{X=xi​,Y=yj​}=∑j=1+∞​pij​,i=1,2...

2. 假定Z服从分布Qi

$Q_i$Qi​是Z的某种分布，满足$\sum_ZQ_i(z_i)=1 \quad Q_i(z)\geq0$∑Z​Qi​(zi​)=1Qi​(z)≥0
（1）经过变换得到(2)
$=\sum_iln\sum_zQ_i(z_i)\frac{p(x_i,z_i;\theta)}{Q_i(z_i)} \quad (2)$=∑i​ln∑z​Qi​(zi​)Qi​(zi​)p(xi​,zi​;θ)​(2)

3. 根据jensen不等式和数学期望
   $E(Y)=E[g(x)]=\sum_i g(x_i)p(x_i)$E(Y)=E[g(x)]=∑i​g(xi​)p(xi​)
   令:$g(x_i)=\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}$g(xi​)=Qi​(zi​)p(xi​,zi​;θ)​
   $p(x_i)=Q_i(z_i)$p(xi​)=Qi​(zi​) 注意这里是z的概率，也就是对z的函数求期望。

则(2)式中$\sum_zQ_i(z_i)\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}$∑z​Qi​(zi​)Qi​(zi​)p(xi​,zi​;θ)​代表是$\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}$Qi​(zi​)p(xi​,zi​;θ)​的数学期望。也就是

$(2)=\sum_iln(E[\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}]) \quad (3) \quad$(2)=i∑​ln(E[Qi​(zi​)p(xi​,zi​;θ)​])(3)

4. 根据Jensen不等式，ln函数为凹函数(优化理论中的凹函数，和高数中相反。这里的凹凸性概念有混淆。)
   $凹函数：E[f(X)] \leq f(EX)$凹函数：E[f(X)]≤f(EX)
   可得：
   $\sum_iln(E[\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}]) \geq \sum_i E[ln\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}]$∑i​ln(E[Qi​(zi​)p(xi​,zi​;θ)​])≥∑i​E[lnQi​(zi​)p(xi​,zi​;θ)​]

把E提出来了。确定了下界线

5. 把E展开。是对z的函数求期望。

由公式$E(Y)=E[g(x)]=\sum_i g(x_i)p(x_i)$E(Y)=E[g(x)]=∑i​g(xi​)p(xi​)
$\sum_i E[ln\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}]=\sum_i\sum_zQ_i(z)ln\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}] \quad (4)$∑i​E[lnQi​(zi​)p(xi​,zi​;θ)​]=∑i​∑z​Qi​(z)lnQi​(zi​)p(xi​,zi​;θ)​](4)

6. 可得$logL(\theta) \geq (4)$logL(θ)≥(4)：

$logL(\theta) \geq\sum_i\sum_zQ_i(z)ln\frac{p(x_i,z_i;\theta)}{Q_i(z_i)} \quad (5)$logL(θ)≥i∑​z∑​Qi​(z)lnQi​(zi​)p(xi​,zi​;θ)​(5)

7. (5)式等号成立的条件：
   固定$\theta$θ，选择Q的可能分布，等号成立时达到了$L(\theta)$L(θ)的下界。Jensen不等式等号成立的条件是X为常亮。也就是$\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}=C \quad (6)$Qi​(zi​)p(xi​,zi​;θ)​=C(6)
   $\Rightarrow p(x_i,z_i;\theta)=C(Q_i(z_i))$⇒p(xi​,zi​;θ)=C(Qi​(zi​))
   $\Rightarrow \sum_z p(x_i,z_i;\theta)=C(\sum_z Q_i(z_i))$⇒∑z​p(xi​,zi​;θ)=C(∑z​Qi​(zi​))
   由于Qi是z的分布率，故累加和为1，可得：
   $\sum_z p(x_i,z_i;\theta)=C \quad (7)$∑z​p(xi​,zi​;θ)=C(7)
   (6)=(7)可得：
   $\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}=\sum_z p(x_i,z_i;\theta)=C$Qi​(zi​)p(xi​,zi​;θ)​=∑z​p(xi​,zi​;θ)=C
   解得

$Q_i(z_i)=\frac{p(x_i,z_i;\theta)}{\sum_z p(x_i,z_i;\theta)} \\ =\frac{p(x_i,z_i;\theta)}{p(x_i;\theta)} \\ =p(z_i|x_i;\theta)$Qi​(zi​)=∑z​p(xi​,zi​;θ)p(xi​,zi​;θ)​=p(xi​;θ)p(xi​,zi​;θ)​=p(zi​∣xi​;θ)
意义：在$\theta$θ参数下，ｘi条件下，取到ｚi的概率。
总结
E－step
固定$\theta$θ，求zi的Ｑi的概率密度公式。建立$Ｌ(\theta)$Ｌ(θ)的下界。
$Q_i(z_i):=p(z_i|x_i;\theta)$Qi​(zi​):=p(zi​∣xi​;θ)

M－step:
给定Qi，极大似然估计$\theta$θ。极大化$L(\theta)$L(θ)的下界（因为L最大化，下界也就随之提升）。得到新的$\theta$θ