背景知识

相似三角形

1. 定理：两角分别对应相等的两个三角形相似。
2. 定理：相似三角形任意对应线段的比等于相似比。

梯形中位线推论

已知：在梯形$\text{ABCD}$$\text{ABCD}$中，$\text{AB}//\text{DC}，\text{AB}=a,\text{DC}=b，\text{E}$$\text{AB} // \text{DC}，\text{AB}=a, \text{DC}=b，\text{E}$为边$\text{AB}$$\text{AB}$上的任意一点，$\text{EF}//\text{DC}$$\text{EF} // \text{DC}$，且$\text{EF}$$\text{EF}$与$\text{BC}$$\text{BC}$相交与点$\text{F}$$\text{F}$。

结论：$\text{EF}=\frac{\text{n*a + m*b}}{\text{m + n}}$$\text{EF} = \frac{\text{n*a + m*b}}{\text{m + n}}$

证明：过$\text{E}$$\text{E}$做直线$\text{HI}$$\text{HI}$平行于$\text{BC}$$\text{BC}$，由相似三角形定理可知，$\mathrm{△}AEH\sim \mathrm{△}EDI$$\triangle A E H \sim \triangle E D I$。

所以，$\frac{\text{AE}}{\text{ED}}=\frac{\text{HA}}{\text{DI}}=\frac{\text{EF - a}}{\text{b - EF}}=\frac{\text{m}}{\text{n}}$$\frac{\text{AE}}{\text{ED}} = \frac{\text{HA}}{\text{DI}} = \frac{\text{EF - a}}{\text{b - EF}} = \frac{\text{m}}{\text{n}}$

化简可得：$\text{EF}=\frac{\text{n*a + m*b}}{\text{m + n}}$$\text{EF} = \frac{\text{n*a + m*b}}{\text{m + n}}$

特别地，当$m+n=1$$m + n = 1$时，$\text{EF}=\text{n*a + (1-n)*b}$$\text{EF} = \text{n*a + (1-n)*b}$

Jensen(琴生)不等式

若$f$$f$是凸函数，则：

证明1：令$x=\lambda x_1+(1-\lambda )x_2$$x = \lambda x_{1}+(1-\lambda) x_{2}$，直线与曲线相交的两点分别为$(x_1,f(x_1))，(x_2,f(x_2))$$(x_1,f(x_1))，(x_2,f(x_2))$。

根据直线两点式，可得直线方程为 $\frac{f(x_2)-f(x_1)}{x_2-x_1}=\frac{f(x)-f(x_1)}{x-x_1}$$\frac{f(x_2)-f(x_1)}{x_2-x_1} = \frac{f(x)-f(x_1)}{x-x_1}$

当$x=\lambda x_1+(1-\lambda )x_2$$x = \lambda x_{1}+(1-\lambda) x_{2}$时，$y=\lambda f\left(x_1\right)+(1-\lambda )f\left(x_2\right)$$y = \lambda f\left(x_{1}\right)+(1-\lambda) f\left(x_{2}\right)$

证明2：令$x=\lambda x_1+(1-\lambda )x_2$$x = \lambda x_{1}+(1-\lambda) x_{2}$

因为$\lambda \in [0,1]$$\lambda \in [0,1]$，所以$x\in [x_1,x_2]$$x\in [x_1,x_2]$。

因为$\frac{x-x_1}{x_2-x}=\frac{\lambda x_1+(1-\lambda )x_2-x_1}{x_2-\lambda x_1-(1-\lambda )x_2}=\frac{(1-\lambda )(x_2-x_1)}{\lambda (x_2-x_1)}=\frac{1-\lambda }{\lambda }$$\frac{x - x_1}{x_2 - x} = \frac{\lambda x_{1}+(1-\lambda) x_{2} - x_1}{x_2 - \lambda x_{1} - (1-\lambda) x_{2}} = \frac{(1 - \lambda)(x_2 - x_1)}{\lambda (x_2 - x_1)} = \frac{1 - \lambda}{\lambda}$

根据梯形推导公式可得：

$y=\text{AB}=\lambda f\left(x_1\right)+(1-\lambda )f\left(x_2\right)$$y = \text{AB} = \lambda f\left(x_{1}\right)+(1-\lambda) f\left(x_{2}\right)$

将上式中的$\lambda$$\lambda$推广到$n$$n$个同样成立，即：

如果将$t$$t$看做概率分布，则在概率论中：

期望

对随机变量$x_i$$x_i$，对应的概率为$p_i$$p_i$，则随机变量$x$$x$的期望为：

三硬币模型引入

问题：假设有3枚硬币，分别记作A，B，C。这些硬币正面出现的概率分别是 $\pi ,p$$\pi,p$和$q$$q$。进行如下掷硬币试验： 先掷硬币A，根据其结果选出硬币B或硬币C，正面选硬币B，反面选硬币C；然后掷选出的硬币，掷硬币的结果，出现正面记作1，出现反面记作0；独立地重复n次试验（这里，n=10），观测结果如下： ​ $1，1，0，1，0，0，1，0，1，1$$1，1，0，1，0，0，1，0，1，1$ ​ 假设只能观测到掷硬币的结果，不能观测掷硬币的过程。问如何估计三硬币正面出现的概率，即三硬币模型的参数。

解：对每一次试验可如下建模

则观测数据的似然函数为：

考虑求模型参数$\theta =(\pi ,p,q)$$\theta=(\pi,p,q)$的极大似然估计，即使用对数似然函数来进行参数估计，可得：

上式没有解析解，也就是没有办法直接通过求导方式解出$(\pi ,p,q)$$(\pi,p,q)$的值，只能使用迭代法进行求解。

EM算法

为什么需要EM算法

概率模型有时候既含有观测变量又含有隐变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接使用极大似然法估计或贝叶斯估计进行求解。但是，当模型含有隐变量时，就不能简单地使用这些估计方法。 ​ EM算法就是解决含有隐变量的概率模型参数的极大似然估计。

EM算法推导

当面对含有隐变量的模型时，目标是极大化观测数据$\text{Y}$$\text{Y}$关于参数$\theta$$\mathbf{\theta}$的对数似然函数，即极大化：

注意到这一极大化的主要困难是上式中有未观测数据$\text{Z}$$\text{Z}$并有包含和（$\text{Z}$$\text{Z}$为离散型时）或 者积分（$\text{Z}$$\text{Z}$为连续型时）的对数。EM算法采用的是通过迭代逐步近似极大化 $L(\theta )$$L(\theta)$ 。 ​ 假设在第$i$$i$次迭代后 $\theta$$\theta$ 的估计值是 ${\theta }^{(i)}$$\theta^{(i)}$, 我们希望新的估计值 $\theta$$\theta$ 能使 $L(\theta )$$L(\theta)$ 增加，即 $L(\theta )>L\left({\theta }^{(i)}\right)$$L(\theta)>L\left(\theta^{(i)}\right)$ 并逐步达到极大值。为此，我们考虑两者的差：

将$L\left({\theta }^{(i)}\right)$$L\left(\theta^{(i)}\right)$移项，令：

则：

即函数$B(\theta ,{\theta }^{(i)})$$B\left(\theta, \theta^{(i)}\right)$是$L(\theta )$$L(\theta)$的一个下界函数。

此时，若设${\theta }^{i+1}$$\theta ^{i+1}$使得$B(\theta ,{\theta }^{(i)})$$B\left(\theta, \theta^{(i)}\right)$达到极大，也就意味着：

由于：

进一步可推得：

即：

因此，任何能使得$B(\theta ,{\theta }^{(i)})$$B\left(\theta, \theta^{(i)}\right)$增大的$\theta$$\theta$，也可以使$L(\theta )$$L(\theta)$增大。于是，问题就转化为求解能使得$B(\theta ,{\theta }^{(i)})$$B\left(\theta, \theta^{(i)}\right)$到达极大的${\theta }^{i+1}$$\theta ^{i+1}$，即：

至此，完成了EM算法的一次迭代，求出的${\theta }^{(i+1)}$$\theta^{(i+1)}$作为下一次迭代的初始${\theta }^{(i)}$$\theta^{(i)}$。

综上所述，可以总结出EM算法的“E步”和“M步”分别为：

1. $\text{ E步：导出Q函数 }$$\text { E步：导出Q函数 }$

   计算完全数据的对数似然函数$\ln P(Y,Z\mid \theta )$$\ln P(Y, Z \mid \theta)$关于给定观测数据$\text{Y}$$\text{Y}$和当前参数$\theta$$\mathbf{\theta}$下对未观测数据$\text{Z}$$\text{Z}$的条件概率分布$P(Z\mid Y,{\theta }^{(i)})$$\ P\left(Z \mid Y, \theta^{(i)}\right )$的期望，也即$\text{Q}$$\text{Q}$函数：

   $$\begin{array}{}\text{(17)}& Q(\theta ,{\theta }^{(i)})=E_Z[\ln P(Y,Z\mid \theta )\mid Y,{\theta }^{(i)}]=\sum _{Z}P(Z\mid Y,{\theta }^{(i)})\ln P(Y,Z\mid \theta )\end{array}$$

2. $\text{ M步：Q函数极大 }$$\text { M步：Q函数极大 }$

   求使得$\text{Q}$$\text{Q}$函数达到极大的${\theta }^{(i+1)}$$\theta^{(i+1)}$。

使用EM求解三硬币模型

求解思路：

1. $\text{ E步：导出Q函数 }$$\text { E步：导出Q函数 }$
2. $\text{ M步：求使得Q函数达到极大的 }{\theta }^{(i+1)}=({\pi }^{(i+1)},p^{(i+1)},q^{(i+1)})$$\text { M步：求使得Q函数达到极大的 } \theta^{(i+1)}=\left(\pi^{(i+1)}, p^{(i+1)}, q^{(i+1)}\right)$

E步：导出Q函数

单独考察 $\sum _{z_1,z_2,\dots ,z_N}\{\prod _{j=1}^{N}P(z_j\mid y_j,{\theta }^{(i)})\cdot \ln P(y_1,z_1\mid \theta )\}$$\sum_{z_{1}, z_{2}, \ldots, z_{N}}\left\{\prod_{j=1}^{N} P\left(z_{j} \mid y_{j}, \theta^{(i)}\right) \cdot \ln P\left(y_{1}, z_{1} \mid \theta\right)\right\}$

所以，

将其带回$\text{Q}$$\text{Q}$函数可得：

由于：

所以，$\text{Q}$$\text{Q}$函数的最终形式为：

求Q函数达到极大的参数

该步骤求使得$\text{Q}$$\text{Q}$函数达到极大的${\theta }^{(i+1)}=({\pi }^{(i+1)},p^{(i+1)},q^{(i+1)})$$\theta^{(i+1)}=\left(\pi^{(i+1)}, p^{(i+1)}, q^{(i+1)}\right)$。

对$\pi$$\pi$求偏导

对$\text{Q}$$\text{Q}$函数关于$\pi$$\mathbf{\pi}$求一阶偏导数，并令一阶偏导数为0：