上一小节中，我们看到了使用极大似然估计的方法，我们根本就求不出最优参数$\theta$的解析解。所以，我们使用迭代的方法来求近似解。
EM算法的表达式，可以被我们写为：
\[\begin{equation} \theta^{(t+1)} = \arg\max_\theta \underbrace{\mathbb{E}_{P(Z|X,\theta^{(t)})} \left[ \log P(X,Z|\theta) \right]}_{Q(\theta,\theta^{(t)})} \end{equation}\]经过一系列的迭代，我们可以得到$\theta^{0},\theta^{1},\cdots,\theta^{(t)}$，迭代到一定次数以后我们得到的$\theta^{(N)}$就是我们想要得到的结果。EM算法大体上可以分成两个部分，E-step和M-step，
E-Step}
\[\begin{equation} \begin{split} Q(\theta,\theta^{(t)}) = & \int_Z \log P(X,Z|\theta)\cdot P(Z|X,\theta^{(t)}) dZ \\ = & \sum_Z \log \prod_{i=1}^N P(x_i,z_i|\theta)\cdot \prod_{i=1}^N P(z_i|x_i,\theta^{(t)}) dZ \\ = & \sum_{z_1,\cdots,z_N} \sum_{i=1}^N \log P(x_i,z_i|\theta)\cdot \prod_{i=1}^N P(z_i|x_i,\theta^{(t)}) dZ \\ = & \sum_{z_1,\cdots,z_N} \left[ \log P(x_1,z_1|\theta) + \log P(x_2,z_2|\theta) + \cdots \log P(x_N,z_N|\theta) \right] \cdot \prod_{i=1}^N P(z_i|x_i,\theta^{(t)}) dZ \\ \end{split} \end{equation}\]为了简化推导，我们首先只取第一项来化简一下，
\[\begin{equation} \begin{split} & \sum_{z_1,\cdots,z_N} \log P(x_1,z_1|\theta) \cdot \prod_{i=1}^N P(z_i|x_i,\theta^{(t)}) dZ \\ = & \sum_{z_1,\cdots,z_N} \log P(x_1,z_1|\theta) \cdot P(z_1|x_1,\theta^{(t)}) \cdot \prod_{i=2}^N P(z_i|x_i,\theta^{(t)}) dZ \\ = & \sum_{z_1} \log P(x_1,z_1|\theta) \cdot P(z_1|x_1,\theta^{(t)}) \cdot \sum_{z_2,\cdots,z_N} \prod_{i=2}^N P(z_i|x_i,\theta^{(t)}) dZ \\ \end{split} \end{equation}\]而：
\[\begin{equation} \begin{split} \sum_{z_2,\cdots,z_N} \prod_{i=2}^N P(z_i|x_i,\theta^{(t)}) = & \sum_{z_2,\cdots,z_N} P(z_2|x_2,\theta^{(t)})\cdot P(z_3|x_3,\theta^{(t)})\cdots P(z_N|x_N,\theta^{(t)}) \\ = & \sum_{z_2} P(z_2|x_2,\theta^{(t)})\cdot \sum_{z_3} P(z_3|x_3,\theta^{(t)})\cdots \sum_{z_N} P(z_N|x_N,\theta^{(t)}) \\ = & 1 \cdot 1 \cdots 1 \\ = & 1 \end{split} \end{equation}\]所以，式(3)也就等于：
\[\begin{equation} \begin{split} \sum_{z_1,\cdots,z_N} \log P(x_1,z_1|\theta) \cdot \prod_{i=1}^N P(z_i|x_i,\theta^{(t)}) dZ = \sum_{z_1} \log P(x_1,z_1|\theta) \cdot P(z_1|x_1,\theta^{(t)}) \end{split} \end{equation}\]将式(5)中得到的结果，代入到式(2)中，我们就可以得到：
\[\begin{equation} \begin{split} Q(\theta,\theta^{(t)}) = & \sum_{z_1} \log P(x_1,z_1|\theta) \cdot P(z_1|x_1,\theta^{(t)}) + \cdots + \sum_{z_N} \log P(x_N,z_N|\theta) \cdot P(z_N|x_N,\theta^{(t)}) \\ = & \sum_{i=1}^N \sum_{Z_i} \log P(x_i,z_i|\theta) \cdot P(z_i|x_i,\theta^{(t)}) \end{split} \end{equation}\]| 那么，下一步我们就是要找到，$P(x_i,z_i | \theta)$和$P(z_i | x_i,\theta^{(t)})$的表达方式了。其中： |
所以，我们将式(8)代入到式(6)中，就可以得到：
\[\begin{equation} Q(\theta,\theta^{(t)}) = \sum_{i=1}^N \sum_{Z_i} \log P_{Z_i}\cdot \mathcal{N}(X|\mu_{Z_i},\Sigma_{Z_i}) \cdot \frac{P_{Z_i}^{\theta(t)}\cdot \mathcal{N}(x_i|\mu_{Z_i}^{\theta(t)},\Sigma_{Z_i}^{\theta(t)})}{\sum_{k=1}^K P_k^{\theta(t)}\cdot \mathcal{N}(x_i|\mu_k^{\theta(t)},\Sigma_k^{\theta(t)})} \end{equation}\]M-Step}
根据我们在E-Step中的推导，我们可以得到：
\[\begin{equation} \begin{split} Q(\theta,\theta^{(t)}) = & \sum_{i=1}^N \sum_{Z_i} \log P_{Z_i}\cdot \mathcal{N}(X|\mu_{Z_i},\Sigma_{Z_i}) \cdot \underbrace{\frac{P_{Z_i}^{\theta(t)}\cdot \mathcal{N}(x_i|\mu_{Z_i}^{\theta(t)},\Sigma_{Z_i}^{\theta(t)})}{\sum_{k=1}^K P_k^{\theta(t)}\cdot \mathcal{N}(x_i|\mu_k^{\theta(t)},\Sigma_k^{\theta(t)})}}_{P(Z_i|X_i,,\theta^{(t)})} \\ = & \sum_{Z_i} \sum_{i=1}^N \log \left( P_{Z_i}\cdot \mathcal{N}(X|\mu_{Z_i},\Sigma_{Z_i}) \right) \cdot P(Z_i|X_i,,\theta^{(t)}) \\ = & \sum_{k=1}^K \sum_{i=1}^N \log \left( P_{k}\cdot \mathcal{N}(X|\mu_{k},\Sigma_{k}) \right) \cdot P(Z_i = C_k|X_i,,\theta^{(t)}) \quad (Z_i = C_k) \\ = & \sum_{k=1}^K \sum_{i=1}^N \left( \log P_{k} + \log \mathcal{N}(X_i|\mu_{k},\Sigma_{k}) \right) \cdot P(Z_i = C_k|X_i,\theta^{(t)}) \\ \end{split} \end{equation}\]我们的目的也就是进行不断迭代，从而得出最终的解，用公式表达也就是：
\[\begin{equation} \theta^{(t+1)} = \arg\max_{\theta} Q(\theta,\theta^{(t)}) \end{equation}\]我们需要求解的参数也就是，$\theta^{(t+1)}={ P_1^{(t+1)}, \cdots, P_k^{(t+1)}, \mu_1^{(t+1)}, \cdots, \mu_k^{(t+1)},\Sigma_1^{(t+1)},\cdots,\Sigma_k^{(t+1)} }$。
首先，我们来展示一下怎么求解$P_K^{(t+1)}$：
| 由于在等式(10)，$\sum_{k=1}^K \sum_{i=1}^N \left( \log P_{k} + \log \mathcal{N}(X | \mu_{k},\Sigma_{k}) \right) \cdot P(Z_i = C_k | X_i,,\theta^{(t)})$中的$\log \mathcal{N}(X | \mu_{k},\Sigma_{k})$部分和$P_k$并没有什么关系。所以，可以被我们直接忽略掉。所以，求解问题，可以被我们描述为： |
使用拉格朗日算子法，我们可以写成：
\[\begin{equation} \mathcal{L}(P,\lambda) = \sum_{k=1}^K \sum_{i=1}^N \log P_{k} \cdot P(Z_i = C_k|X_i,\theta^{(t)}) + \lambda(\sum_{k=1}^K P_k - 1) \end{equation}\] \[\begin{equation} \begin{split} \frac{\partial \mathcal{L}(P,\lambda)}{\partial P_k} = & \sum_{i=1}^N \frac{1}{P_k} \cdot P(Z_i = C_k|X_i,\theta^{(t)}) + \lambda = 0 \\ \Rightarrow & \sum_{i=1}^N P(Z_i = C_k|X_i,\theta^{(t)}) + P_k \lambda = 0 \\ \stackrel{k = 1,\cdots,K}{\Longrightarrow} & \sum_{i=1}^N\underbrace{\sum_{k=1}^K P(Z_i = C_k|X_i,\theta^{(t)})}_{1} + \underbrace{\sum_{k=1}^K P_k}_{1} \lambda = 0 \\ \Rightarrow & N+\lambda = 0 \end{split} \end{equation}\]所以，我们可以轻易的得到$\lambda = -N$，所以有
\[\begin{equation} P_K^{(t+1)} = \frac{1}{N} \sum_{i=1}^N P(Z_i = C_k | X_i,\theta^{(t)}) \end{equation}\]那么，我们所有想要求的参数也就是$P^{(t+1)} = (P_1^{(t+1)},P_2^{(t+1)},\cdots,P_k^{(t+1)})$。
求解$P_k^{(t+1)}$是一个有约束的求最大值问题，由于带约束所以我们要使用拉格朗日乘子法。而且这里使用到了一个track，也就是将从1到k，所有的数据集做一个整合，非常的精彩，这样就直接消掉了$P_k$无法计算的问题。而至于$\theta$的其他部分，也就是关于${ \mu_1^{(t+1)}, \cdots, \mu_k^{(t+1)},\Sigma_1^{(t+1)},\cdots,\Sigma_k^{(t+1)} }$的计算，使用的方法也是一样的，这个问题就留给各位了。
为什么极大似然估计搞不定的问题，放在EM算法里面我们就可以搞定了呢？我们来对比一下两个方法中，需要计算极值的公式。
\[\begin{equation} \sum_{k=1}^K \sum_{i=1}^N \left( \log P_{k} + \log \mathcal{N}(X_i|\mu_{k},\Sigma_{k}) \right) \cdot P(Z_i = C_k|X_i,\theta^{(t)}) \end{equation}\] \[\begin{equation} \arg\max_{\theta} \sum_{i=1}^N \log \sum_{k=1}^K P_k \cdot \mathcal{N}(x_i|\mu_k,\Sigma_k) \end{equation}\]极大似然估计一开始计算的就是$P(X)$，而EM算法中并没有出现有关$P(X)$的计算，而是全程计算都是$P(X,Z)$。而$P(X)$实际上就是$P(X,Z)$的求和形式。所以，每次单独的考虑$P(X,Z)$就避免了在log函数中出现求和操作。
-
Previous
Gaussian_Mixture_Model_02_Maximum_Likelihood_Estimation -
Next
Markov_Chain_Monte_Carlo_01_Sampling_Method
