【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.EM算法简介
我们经常会从样本观察数据中，找出样本的模型参数。最常用的方法就是极大化模型分布的对数似然函数。
但是在一些情况下，我们得到的观察数据有未观察到的隐含数据（学名是“隐变量”（latent variable）），此时我们未知的有隐含数据和模型参数，因而无法直接用极大化对数似然函数得到模型分布的参数。怎么办呢？这就是EM算法可以派上用场的地方了。
EM算法也称期望最大化（Expectation-Maximum，简称EM）算法。
EM算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含数据（EM算法的E步），接着基于观察数据和猜测的隐含数据一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐藏数据是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。不过没关系，我们基于当前得到的模型参数，继续猜测隐含数据（EM算法的E步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。
从上面的描述可以看出，EM算法是迭代求解最大值的算法，同时算法在每一次迭代时分为两步，E步和M步。一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。
对于$m$个样本观察数据$x = (x^{(1)},x^{(2)},…,x^{(m)})$中，找出样本的模型参数$\theta$，极大化模型分布的对数似然函数如下：
\[\theta = \arg \max \limits_{\theta} \sum^m_{i=1} \log P(x^{(i)};\theta)\]如果我们得到的观察数据有未观察到的隐含数据$z=(z^{(1)},z^{(2)},…,z^{(m)})$，此时我们来最大化已观测数据的对数“边际似然”（marginal likelihood）：
\[\theta = \arg \max \limits_{\theta} \sum^m_{i=1} \log P(x^{(i)};\theta) = \arg \max \limits_{\theta} \sum^m_{i=1} \log \sum_{z^{(i)}} P(x^{(i)},z^{(i)} ; \theta)\]公式的具体求解过程本文不再赘述。事实上，隐变量估计问题也可通过梯度下降等优化算法求解，但由于求和的项数将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；而EM算法则可看作一种非梯度优化方法。EM算法可看作用坐标下降法（见本文第2部分）来最大化对数似然下界的过程。
然后通过一个例子来形象化的理解EM算法。假设有两枚硬币A和B，它们随机抛掷的结果见下（H为正面，T为反面）：
可以很容易估计出两枚硬币抛出正面的概率：
\[\theta_A = \frac{24}{24+6}=0.80\] \[\theta_B = \frac{9}{9+11}=0.45\]现在我们加入隐变量$Z=(z_1,z_2,z_3,z_4,z_5)$，代表每一轮所用的硬币，即抹去每轮投掷的硬币标记：
这种情况下，我们该如何估计$\theta_A$和$\theta_B$的值？其解决方法就是先随机初始化$\theta_A$和$\theta_B$，然后用去估计$Z$，然后基于$Z$按照最大似然概率去估计新的$\theta_A$和$\theta_B$，循环至收敛。
假设随机初始化：
\[\theta_A = 0.6\] \[\theta_B = 0.5\]对于第一轮来说，如果使用硬币A，则得到5H5T的概率为$C^5_{10} \cdot 0.6^{0.5} \cdot 0.4^{0.5}$；如果使用硬币B，则得到5H5T的概率为$C^5_{10} \cdot 0.5^{0.5} \cdot 0.5^{0.5}$。据此，我们便可以算出第一轮使用硬币A或硬币B的概率为：
\[P_A = \frac{C^5_{10} \cdot 0.6^{0.5} \cdot 0.4^{0.5}}{C^5_{10} \cdot 0.6^{0.5} \cdot 0.4^{0.5} + C^5_{10} \cdot 0.5^{0.5} \cdot 0.5^{0.5}}=0.45\] \[P_B = \frac{C^5_{10} \cdot 0.5^{0.5} \cdot 0.5^{0.5}}{C^5_{10} \cdot 0.6^{0.5} \cdot 0.4^{0.5} + C^5_{10} \cdot 0.5^{0.5} \cdot 0.5^{0.5}}=0.55\]剩余轮次，以此类推可得到：
以上就是E-Step。
接下来结合硬币A的概率和投掷结果，我们利用期望可以求出硬币A和硬币B的贡献。以第二轮硬币A为例：
\[H : 0.80 * 9 =7.2\] \[T : 0.80 * 1 = 0.8\]于是我们可以得到：
重新计算$\theta_A$和$\theta_B$：
\[\theta_A = \frac{21.3}{21.3+8.6}=0.71\] \[\theta_B = \frac{11.7}{11.7 + 8.4}=0.58\]这就是M-Step。然后如此反复迭代直至参数收敛。
2.坐标下降法
坐标下降法（coordinate descent）是一种非梯度优化方法，它在每步迭代中沿一个坐标方向进行搜索，通过循环使用不同的坐标方向来达到目标函数的局部最小值。
求解极大值问题时亦称“坐标上升法”（coordinate ascent）。
不妨假设目标是求解函数$f(\mathbf x)$的极小值，其中$\mathbf x = (x_1,x_2,…,x_d)^T \in \mathbb R^d$是一个$d$维向量。从初始点$\mathbf x^0$开始，坐标下降法通过迭代地构造序列$\mathbf x^0,\mathbf x^1,\mathbf x^2,…$来求解该问题，$\mathbf x^{t+1}$的第$i$个分量$x^{t+1}_i$构造为：
\[x^{t+1}_i = \arg \min \limits_{y \in \mathbb R} f(x^{t+1}_1,...,x^{t+1}_{i-1},y,x^{t}_{i+1},...,x^t_d)\]即固定其他因变量，只留一个因变量。此时求解$f(x)$的最小值。这样问题就变得容易许多。
通过执行此操作，显然有：
\[f(\mathbf x^0) \geqslant f(\mathbf x^1) \geqslant f(\mathbf x^2) \geqslant ...\]与梯度下降法类似，通过迭代执行该过程，序列$\mathbf x^0,\mathbf x^1,\mathbf x^2,…$能收敛到所期望的局部极小点或驻点（stationary point）。
坐标下降法不需计算目标函数的梯度，在每步迭代中仅需求解一维搜索问题，对于某些复杂问题计算较为简便。但若目标函数不光滑，则坐标下降法有可能陷入非驻点（non-stationary point）。
