[人工智能]【EM算法】【1/6，迭代收敛性】

本系列为哔哩哔哩网站shuhuai008的【机器学习白板推导】的注解。

1. EM算法背景

   EM算法应用于以下这类问题^[1]：
   有三枚硬币A、B、C，单独投掷正面朝上概率为a、b、c。下图为一个自动投掷机的逻辑，重复进行多次 (例：5次实验结果为[正，正，反，反，正])，估计a、b、c。

   隐变量

   正面

   反面

   投掷A

   投掷B

   投掷C

   记录正反结果

   上述问题是一个有隐变量的问题，硬币A的投掷结果是一个黑箱，我们观测不到。
   把要估计参数的称为$\mathbf{\theta }=(a,b,c)$，把实验得到的一组正反称为样本$\mathbf{x}$，最终目标就是求：

   $$\begin{array}{rl}\underset{\mathbf{\theta }}{\mathrm{argmax}}P(\mathbf{x}|\mathbf{\theta })& =\underset{\mathbf{\theta }}{\mathrm{argmax}}\log P(\mathbf{x}|\mathbf{\theta })\\ & =\log \prod _{j=0}^n(a{b}^{x_j}(1?b{)}^{1?x_j}+(1?a)c^{x_j}(1?c{)}^{1?x_j})\end{array}\text{\hspace{1em}(1)}$$

   如何求$(1)$式？
   使用极大似然估计法对$\mathbf{\theta }$各个参数进行求偏导令其等于0是没有解析解的[李航，统计学习方法，2012]，因为对隐变量a求偏导得到的方程是复杂的。
   PRML书^[1]section9.2.1结尾给出了两种方法，一种是梯度下降方法，一种是EM算法。PRML介绍了用EM算法解决上述含有隐变量问题，其将EM算法描述为"elegant and powerful"。在胡浩基的机器学习课程的EM算法部分中指出EM算法相对于梯度下降法的优点是[1.不需要调节参数；2.编程简单]。
   EM算法的思想是多次迭代，使每次迭代满足$$\log P(\mathbf{x}|{\mathbf{\theta }}^{[i+1]})\ge \log P(\mathbf{x}|{\mathbf{\theta }}^{[i]})\text{\hspace{1em}(2)}$$，$i$表示第$i$轮迭代，这样迭代多次后，似然越来越大，就能收敛，就能得到$(1)$式的局部近似解（EM算法无法得到全局最优解）。

2. EM算法收敛证明

   本系列根据B站【白板推导】顺序注解，所以先直接给出EM算法公式，证明是迭代收敛的，以后的章节再给出公式推导。
   设隐变量为$\mathbf{z}$，样本为$\mathbf{x}$，要估计的参数为$\mathbf{\theta }$，EM算法迭代公式为：
   $${\mathbf{\theta }}^{[i+1]}=\underset{\mathbf{\theta }}{\mathrm{argmax}}{\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?\log P(\mathbf{x},\mathbf{z}|\mathbf{\theta })d\mathbf{z}\text{\hspace{1em}(3)}$$
   蓝色的是期望E(Expectation)，红色的是取最大M(Maximization)，所以叫做EM算法。注意：$\mathbf{\theta }$为变量，${\mathbf{\theta }}^{[i]}$为数值，${\mathbf{\theta }}^{[0]}$是人为给定的。
   要证明EM算法迭代收敛，只要证明$(2)$式成立即可。
   根据条件概率公式，将$(2)$式基本形式变形引出隐变量：
   $$\log P(\mathbf{x}|\mathbf{\theta })=\log \frac{P(\mathbf{x},\mathbf{z}|\mathbf{\theta })}{P(\mathbf{z}|\mathbf{x},\mathbf{\theta })}=\log P(\mathbf{x},\mathbf{z}|\mathbf{\theta })?\log P(\mathbf{z}|\mathbf{x},\mathbf{\theta })$$
   对上式乘$P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})$，再对$\mathbf{z}$积分，这步操作动机是为了利用$(3)$式，得：
   $$\begin{array}{rl}左边& ={\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?\log P(\mathbf{x}|\mathbf{\theta })d\mathbf{z}=\log P(\mathbf{x}|\mathbf{\theta })\\ 右边& ={\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?\log P(\mathbf{x},\mathbf{z}|\mathbf{\theta })d\mathbf{z}?{\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?\log P(\mathbf{z}|\mathbf{x},\mathbf{\theta })d\mathbf{z}\end{array}$$
   左边没有变化，记作$L(\mathbf{\theta })$。绿色部分记作$Q(\mathbf{\theta })$，橙色部分记作$H(\mathbf{\theta })$。
   $(2)$式其实就是：$$L({\mathbf{\theta }}^{[i+1]})?L({\mathbf{\theta }}^{[i]})=(Q({\mathbf{\theta }}^{[i+1]})?Q({\mathbf{\theta }}^{[i]}))?(H({\mathbf{\theta }}^{[i+1]})?H({\mathbf{\theta }}^{[i]}))\ge 0$$
   收敛性问题进一步转化为证明：
   $$\begin{gathered} Q({\mathbf{\theta }}^{[i+1]})\ge Q({\mathbf{\theta }}^{[i]}) \\ H({\mathbf{\theta }}^{[i+1]})\le H({\mathbf{\theta }}^{[i]}) \end{gathered}$$
   $Q(\mathbf{\theta })$就是故意凑出来的$(3)$式蓝色部分，所以$Q({\mathbf{\theta }}^{[i+1]})\ge Q({\mathbf{\theta }}^{[i]})$直接得证。
   接下来证明$H(\mathbf{\theta })$不等式：
   $$H({\mathbf{\theta }}^{[i+1]})?H({\mathbf{\theta }}^{[i]})={\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?\log \frac{P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i+1]})}{P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})}d\mathbf{z}$$
   根据$E(\log 猫)\le \log E(猫)$（参考$\frac{\log a+\log b}{2}\le \log \frac{a+b}{2}$，E就是相加除以2），
   将紫色部分中$\frac{P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i+1]})}{P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})}$看作猫，紫色部分为：
   $$\begin{array}{rl}& {\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?\log 猫d\mathbf{z}\\ & \le \log {\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i]})?猫d\mathbf{z}\stackrel{消去分母}{}\log {\int }_{\mathbf{z}}P(\mathbf{z}|\mathbf{x},{\mathbf{\theta }}^{[i+1]})d\mathbf{z}\\ & =\log 1\\ & =0\end{array}$$
   所以$H({\mathbf{\theta }}^{[i+1]})\le H({\mathbf{\theta }}^{[i]})$得证。
   $Q(\mathbf{\theta })$和$H(\mathbf{\theta })$不等式都证明完毕后，得到$L({\mathbf{\theta }}^{[i+1]})\ge L({\mathbf{\theta }}^{[i]})$，得到$(2)$式得证，得到EM算法收敛得证。

参考文献：
[1]李航. 统计学习方法[M]. 清华大学出版社, 2012.
[2]Christopher M. Bishop. Pattern Recognition and Machine Learning[M]. Springer, 2006.