如果我们观测到一个数据集$X = \{x1,...,x_N\}$，那么我们可以使用最大似然法确定HMM的参数。似然函数通过对联合概率分布(13.10)中的潜在变量进行求和的方式得到，即

$$p(X|\theta) = \sum\limits_Zp(X,Z|\theta) \tag{13.11}$$

由于联合概率分布$p(X,Z|\theta)$无法在$n$上进行分解（与第9章关于混合概率分布的讨论不同），因此我们不能独立地在每个zn上进行求和。我们也不能显示地完成这个求和，因为有$N$个变量需要求和，每个都有$K$个状态，从而总计有$K^N$个求和项。因此求和式中的项的数量随着链的长度指数增长。事实上，式（13.11）中的求和对应于在图13.7的晶格图中通过指数多条路径进行的求和。

我们之前在讨论图8.32所示的简单变量链的推断问题时，已经遇到了一个类似的困难。那里，我们能够使用图的条件独立性质对求和式重新排序，得到一个计算代价与链的长度呈线性 关系而不是指数关系的算法。我们将类似的方法应用到隐马尔可夫模型中。

似然函数表达式(13.11)的另一个问题是，由于它对应于混合概率分布的一个推广，因此它表示潜在变量的不同配置下，对发射概率进行求和。因此直接对这个似然函数进行最大化会导致复杂的表达式，没有解析解。这一点与简单的混合模型一样(回忆一下，独立同分布数据 的混合模型是HMM的一个具体实例)。

于是我们使用期望最大化算法来寻找对隐马尔可夫模型中似然函数进行最大化的有效框架。EM算法的开始阶段是对模型参数的某些初始的选择，我们记作$\theta^{old}$。在E步骤中，我们使用 这些参数找到潜在变量的后验概率分布$p(Z|X,\theta^{old})$。然后，我们使用这个后验概率分布计算完整数据似然函数的对数的期望，得到了一个关于参数$\theta$的函数$Q(\theta, \theta^{old})$，定义为

$$Q(\theta,\theta^{old}) = p(Z|X,\theta^{old})\ln p(X,Z | \theta) \tag{13.12}$$

现在，引入一些记号会比较方便。我们使用$\gamma(z_n)$来表示潜在变量$z_n$的边缘概率分布， 用$\xi(z_{n−1}, z_n)$表示两个连续的潜在变量的联合后验概率分布，即

$$\begin{eqnarray} \gamma(z_N) &=& p(z_n|X,\theta^{old}) \tag{13.13} \\ \xi(z_{n-1},z_n) &=& p(z_{n-1},z_n|X,\theta^{old}) \tag{13.14} \end{eqnarray}$$

对于每个$n$值，我们可以使用$K$个非负数来存储$\gamma(z_n)$，这些数的和等于1。类似的，我们可以使用一个由非负数组成的$K \times K$的矩阵来存储$\xi(z_{n−1}, z_n)$，同样加和等于1。我们也会使用$\gamma(z_{nk})$来表示$z_{nk} = 1$的条件概率，类似地使用$\xi(z_{n−1},j,z_{nk})$来表示后面介绍的另一个概率。 由于二值随机变量的期望就是取值为1的概率，因此得到

$$\begin{eqnarray} \gamma(z_{nk}) &=& \mathbb{E}[z_{nk}] = \sum\limits_{z_n}\gamma(z)z_{nk} \tag{13.15} \\ \xi(z_{n−1,j},z_{nk}) = \mathbb{E}[z_{n−1,j}z_{nk}] &=& \sum\limits_{z_{n-1},z_n}\xi(z_{n-1},z_n)z_{n-1,j}z_{nk} \tag{13.16} \end{eqnarray}$$

如果我们将式（13.10）的联合概率分布$p(X, Z|\theta)$代入式（13.12），使用$\gamma$和$\xi$的定义，我们有

$$\begin{eqnarray} Q(\theta,\theta^{old}) &=& \sum\limits_{k=1}^K\gamma(z_{1k})\ln \pi_k + \sum\limits_{n=2}^N\sum\limits_{j=1}^K\sum\limits_{k=1}^K\xi(z_{n-1,j},z_{nk})\ln A_{jk} \\ & & \sum\limits_{n=1}^N\sum\limits_{k=1}^K\gamma(z_{nk})\ln p(x_n|\phi_k) \tag{13.17} \end{eqnarray}$$

E步骤的目标是高效地计算\gamma(zn)和ξ(zn−1， zn)，我们后面会详细讨论。

在M步骤中，我们关于参数\theta = {\pi， A， \psi}最大化Q(\theta， \theta旧)，其中我们将\gamma(zn)和ξ(zn−1， zn)看 做常数。关于\pi和A的最大化可以使用拉格朗日乘数法很容易求出，结果为

EM算法在初始化时必须选择$\pi$和$A$的初始值，这当然应该遵守概率的加和性质。注意，如果将$\pi$或$A$的任何元素都设为0，那么在接下来的EM更新中也会保持为0。一个典型的初始化步骤是在满足加和限制和非负限制的条件下，为这些参数随机选择初始值。注意，对于从左到右的模型的情形，我们无需对EM的结果进行特别的修改，只需在$A_{jk}$的适当的元素设置为0即可，因为这些元素始终为0。

为了关于$\psi_k$最大化$Q(\theta， \theta^{old})$，我们注意到式（13.17）中，只有最后一项依赖于$\psi_k$，并且这一项的形式与独立同分布数据的标准混合分布的对应的函数中的数据依赖项完全相同，这一点可以通过与高斯混合模型的式（9.40）进行对比的方式看出来。这里，$\gamma(z_{nk})$起着“责任”的作用。如果对于不同的分量，参数$\psi_k$独立，那么这一项可以分解为一组项的和的形式，每一项对应于一个$k$值，每一项都可以独立地最大化。这样，我们可以简单地最大化发射概率密度$p(x | \psi_k)$的加权的对数似然函数，权值为$\gamma(z_{nk})$。这里，我们假设这个最大化过程可以高效地完成。例如，在高斯发射密度的情形下，我们有$p(x|\psi_k) = \mathcal{N}(x|\mu_k, \Sigma_k)$，最大化函数$Q(\theta, \theta^{old})$可得

$$\begin{eqnarray} \mu_k = \frac{\sum\limits_{n=1}^N\gamma(z_{nk})x_n}{\sum\limits_{n=1}^N\gamma(z_{nk})} \tag{13.20} \\ \Sigma_k = \frac{\sum\limits_{n=1}^N\gamma(z_{nk})(x_n - \mu_k)(x_n - \mu_k)^T}{\sum\limits_{n=1}^N\gamma(z_{nk})} \tag{13.21} \end{eqnarray}$$

对于观测变量服从离散多项式分布的情形，观测变量的条件概率分布为

$$p(x|z) = \prod\limits_{i=1}^D\prod\limits_{k=1}^K\mu_{ik}^{x_ix_k} \tag{13.22}$$

对应的M步骤方程为

$$\mu_{ik} = \frac{\sum\limits_{n=1}^N\gamma(z_{nk}x_{ni}}{\sum\limits_{n=1}^N}\gamma(z_{nk}) \tag{13.23}$$

对于服从伯努利分布的观测变量，可以得到类似的结果。

EM算法要求有发射概率分布的参数的初始值。一种设置的方式是首先将数据集看成独立同分布的，然后通过最大似然方法调节发射概率密度，之后使用得到的值来初始化EM的参数。