序列比对（15）EM算法以及Baum-Welch算法的推导

###EM算法
EM算法就是这样一种迭代算法，该算法在有缺失值存在的情况下估算概率模型的参数（或参数集，下文统称参数）。其大致过程如下：
E步骤：计算Q函数。
M步骤：相较于$\theta$，最大化$Q(\theta|\theta^t)$。

其具体推导过程如下：
最终目的是找到最大对数似然对应的参数。
$$\hat{\theta} = \mathrm{argmax}_\theta \, \mathrm{log} \, P(x|\theta) \tag{1}$$

假设$y$为缺失数据，我们首先可以得到：
$$\mathrm{log} \, P(x|\theta) = \mathrm{log} \, P(x,y|\theta) - \mathrm{log} \, P(y|x,\theta) \tag{2}$$


>公式(2)很容易推导，因为：
$$P(x,y|\theta) = P(x|\theta)P(y|x,\theta) \tag{2.1}$$
所以
$$P(x|\theta) = \frac{P(x,y|\theta)}{P(y|x,\theta)} \tag{2.2}$$
等式两边取 $\mathrm{log} \, $ 可以得到公式(2)。

在求取最大对数似然的迭代过程中，假设步骤$t$中得到了参数$\theta^t$，对应的对数似然是$\mathrm{log} \, P(x|\theta^t)$。那么步骤$t+1$中的对数似然应该不小于$\mathrm{log} \, P(x|\theta^t)$。即
$$\mathrm{log} \, P(x|\theta^{t+1}) - \mathrm{log} \, P(x|\theta^t) \geq 0 \tag{3}$$

为了得到$\theta^{t+1}$，我们首先变换得到：
$$\begin{aligned}
\displaystyle \mathrm{log} \, P(x|\theta)=
& \sum_y P(y|x,\theta^t)\mathrm{log} \, P(x,y|\theta)\\
& -\sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta) \tag{4}
\end{aligned}$$

>公式（4）可以这样推导得到：
将公式（2）等式两边乘上$P(y|x,\theta^t)$，再对所有的$y$求和，得到：
$$\begin{aligned}
\displaystyle \sum_y P(y|x,\theta^t)\mathrm{log} \, P(x|\theta) =
& \sum_y P(y|x,\theta^t)\mathrm{log} \, P(x,y|\theta)\\
& -\sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta) \tag{4.1}
\end{aligned}$$
很容易看出等式左边：
$$\begin{aligned}
\displaystyle \sum_y P(y|x,\theta^t)\mathrm{log} \, P(x|\theta)
& = \mathrm{log} \, P(x|\theta)\sum_y P(y|x,\theta^t) \\
& = \mathrm{log} \, P(x|\theta) \tag{4.2}
\end{aligned}$$
由公式（4.1）和（4.2）可以得到公式（4）。

如果令
$$Q(\theta|\theta^t) = \sum_y P(y|x,\theta^t)\mathrm{log} \, P(x,y|\theta) \tag{5}$$

那么我们可以得到：
$$\begin{aligned}
\displaystyle & \mathrm{log} \, P(x|\theta) - \mathrm{log} \, P(x|\theta^t)\\
&= Q(\theta|\theta^t) - Q(\theta^t|\theta^t) + \sum_y P(y|x,\theta^t)\mathrm{log} \,  \frac{P(y|x,\theta^t)}{P(y|x,\theta)} \tag{6}
\end{aligned}$$

>公式（6）的推导也很容易：
$$\begin{aligned}
&\mathrm{log} \, P(x|\theta) - \mathrm{log} \, P(x|\theta^t)\\
&=\bigg[\sum_y P(y|x,\theta^t)\mathrm{log} \, P(x,y|\theta) - \sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta) \bigg]\\
&\ \ \ \ \ - \bigg[\sum_y P(y|x,\theta^t)\mathrm{log} \, P(x,y|\theta^t) - \sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta^t) \bigg]\\
&=\bigg[Q(\theta|\theta^t) - \sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta)\bigg] \\
&\ \ \ \ \ - \bigg[Q(\theta^t|\theta^t) - \sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta^t)\bigg] \\
&=\bigg[Q(\theta|\theta^t) - Q(\theta^t|\theta^t)\bigg]\\
&\ \ \ \ \ +\bigg[\sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta^t) - \sum_y P(y|x,\theta^t)\mathrm{log} \, P(y|x,\theta)\bigg]\\
&=Q(\theta|\theta^t) - Q(\theta^t|\theta^t) + \sum_y P(y|x,\theta^t)\mathrm{log} \,  \frac{P(y|x,\theta^t)}{P(y|x,\theta)} \tag{6.1}
\end{aligned}$$

其中$\sum_yP(y|x,\theta^t)\mathrm{log} \, \frac{P(y|x,\theta^t)}{P(y|x,\theta)}$一项是$P(y|x,\theta^t)$对$P(y|x,\theta)$的相对熵，所以不小于0。只要$Q(\theta|\theta^t)$不小于$Q(\theta^t|\theta^t)$，那么就可以保证公式（3）成立。那么可以取
$$\theta^{t+1}=\mathrm{argmax}_\theta \, Q(\theta|\theta^t) \tag{7}$$

>我们定义概率分布$P(x)$相对于概率分布$Q(x)$的相对熵为：
$$\displaystyle H(P||Q) = \sum_i\ P(x_i) \mathrm{log} \,  \frac{P(x_i)}{Q(x_i)} \tag{7.1}$$
那么$H(P||Q) \geq 0$，证明如下：
我们知道：
$$\mathrm{log} \, x \leq x - 1, \qquad when \quad x > 0 \tag{7.2}$$
那么：
$$-\mathrm{log} \, x \geq 1 - x, \qquad when \quad x > 0 \tag{7.3}$$
所以：
$$\begin{aligned}
\mathrm{log} \, \frac{P(x_i)}{Q(x_i)} 
&= -\mathrm{log} \, \frac{Q(x_i)}{P(x_i)} \\
&\geq 1 - \frac{Q(x_i)}{P(x_i)} \tag{7.4}
\end{aligned}$$
因而：
$$\begin{aligned}
\displaystyle H(P||Q) 
&= \sum_i\ P(x_i) \mathrm{log} \,  \frac{P(x_i)}{Q(x_i)}\\
&\geq \sum_i\ P(x_i) \bigg(1 - \frac{Q(x_i)}{P(x_i)}\bigg)\\
&=\sum_i\ P(x_i)-\sum_i\ Q(x_i)\\
&=1-1\\
&=0 \tag{7.5}
\end{aligned}$$
等号成立当且仅当对所有的$i$，$P(x_i)=Q(x_i)$都成立。