3.3.2 HMM关键问题
一个HMM可以用一个三元组Φ来表示。围绕这个三元组和观测值，存在下面三个基本问题。
·评估问题：给定模型参数和观测序列，推断出观测序列的可能概率。当存在多个模型时，比较它们对应的概率，可以确定描述该观测序列最合适的HMM。
·解码问题：给定模型参数和观测序列，推断出最可能经历的隐含状态。
·学习问题：给定观测序列，学习得到最适合的HMM参数。
上述三个问题在统一的概率模型下紧密联系，但侧重点各有不同。解决这些问题都要使用动态规划的基本原则，即将多步决策的过程拆分为多个单步状态的级联，从而将复杂问题转化为每步状态决策问题来解决。在HMM中，观测序列和隐含序列包含了多步的转移，要求取整个序列的优化目标，可以转化成单步优化的子问题逐个解决。
1. 评估问题
给定一个HMM系统Φ，根据观测序列X=（X1，X2，…，XT），估计概率P（X|Φ），这时最基本的方法是将所有可能的状态序列的概率相加：
对于特定的状态序列S=（s1，s2，…，sT），可以根据马尔可夫性质计算该序列的联合概率，再利用输出独立假设，可以计算得到如下概率：
其中为了统一，已将计算公式中应该包含的初始概率πs1改写为as0s1。
仍然以天气为例，图3-5中绘制出了连续5天的隐含状态转移网格图。此时对应的观测序列为“干燥、干燥、舒适、舒适、潮湿”。由于每种隐含状态下都可能出现三种观测状态，因此每个观测状态的概率计算都要包含三种可能性。要计算连续5天观测序列的概率，就需要先遍历35=243种可能的隐含状态转移路径，再将所有可能的隐含状态转移路径对应概率累加。例如，如果隐含状态为“晴、晴、多云、多云、阴雨”，则在此条件下产生该观测序列的概率为（假设第一天为晴天的初始概率为0.6）：
P（X|晴，晴，多云，多云，阴雨）
=P（s0=晴）P（X0=干燥|s0=晴）P（s1=晴|s0=晴）
P（X1=干燥|s1=晴）P（s2=多云|s1=晴）
P（X2=舒适|s2=多云）P（s3=多云|s2=多云）
P（X3=舒适|s3=多云）P（s4=阴雨|s3=多云）
P（X4=潮湿|s4=阴雨）
=0.6×0.5×0.5×0.5×0.2×0.6×0.4×0.6×0.3×0.8
≈5.2×10-4
图3-5 对应观测序列的HMM隐含状态转移网格图
显然，当参数值很大时，这种计算的计算量巨大。需要采用合适的方法减少计算量。
从上面的计算实例中可以观测到，由于所有的转移概率、输出概率都不随时间变化，因此可以利用马尔可夫性质和输出独立假设，将相邻两个时刻的局部输出概率计算出来。可以通过前向迭代快速计算观测序列的概率。前向算法（Forward Algorithm）就是遵循了这样一个思路。可以定义前向概率参数为
它表示HMM在时刻t时，处于状态i下产生观测序列
的概率。对应到实例中，就是今天是阴雨天，而且先前几天的观测序列概率是图3-5中观测序列的概率。
根据HMM的两个假设，前向概率的计算只涉及相邻两天的状态转移概率P（st|st-1，Φ）和当天的输出概率P（Xt|st，Φ），即仅依赖参数st-1，st和Xt，因此时刻t=T的P（X|Φ）可以按算法3-2迭代计算，示意图如图3-6所示。
图3-6 前向概率计算示意图
算法3-2 前向算法
输入：观测变量{xj}，j=1，2，…，T，Φ。
输出：P（X|Φ）。
1）初始化，α1（i）=πibi（X1）（1≤i≤N），令t=1。
2）迭代：
①计算前向概率：
②t=t+1。
③若t≥T，则跳至步骤3；否则返回步骤2中第1步继续迭代。
3）输出
，即为估计结果。
使用前向算法计算前向概率时，只利用了前一个时刻的前向概率值。也就是说，如果知道了昨天各种天气的前向概率，以及今天的湿度观测值，那么在计算今天的前向概率时，只要遍历当前的所有状态就可以了。由于充分利用了局部路径的概率，用前向算法计算最终概率时只需要将当前时刻的所有前向概率相加即可，不需要再遍历所有的可能性，复杂度大幅下降。
在很多应用场合中，可能同时存在多个HMM，这时利用前向算法可以计算在给定每个HMM的条件下一个观测序列的概率，并由此来选择最适合这个序列的HMM。例如，在孤立词语音识别中，每个单词都可以定义一个HMM，因此可以得到数量较多的HMM。当检测到一段语音信号时，根据前向算法计算得到每个HMM下该语音出现的概率，就能通过寻找对应此观测序列最可能的HMM来识别这个单词。
2. 解码问题
给定一个HMM系统Φ，以及由系统产生的观测序列
，估计该系统产生此观测序列时最可能经历的状态序列
。对应上节的天气示例，HMM的解码过程也就是要在所有可能的243种路径中确定一条最佳路径，这条最佳路径对应的就是解码问题的答案——最佳状态序列。
使用得最广的最佳状态序列定义为在给定观测序列X的前提下，概率P（S|X，Φ）最大的状态序列
。显然，遍历所有可能路径，直接穷举对比的方法肯定不实用。与前向算法类似，根据HMM参数中概率不随时间改变的特点以及HMM的马尔可夫性质，可以知道，当前时刻最佳状态的概率只和前一个时刻的各状态的最佳概率以及一步转移概率有关。这个性质和动态规划思想很相似，因此可以使用Viterbi算法来确定HMM中的最佳状态序列。
定义最佳路径概率：
它是所有在时刻t时产生了观测序列
，并且结束状态为i的状态序列中的最大概率，其迭代计算公式为
式中，第三个等号两侧使用了最佳路径概率的定义式和输出独立假设。最佳路径概率和前向算法中的局部概率并不相同，最佳路径概率对应的是最可能的路径概率，而局部概率是所有概率的累加。
为了得到完整的最佳路径，必须对每个i和j进行路径跟踪。定义Bt（j）为t时刻结束状态为j的最佳路径上，前一个时刻的状态序号。Bt（j）可以记录最佳路径下的状态邻接关系，起到了后向指针的作用。例如，在图3-5所示的观测序列条件下，今天是阴雨天对应的最佳隐含状态序列是晴、晴、多云、多云、阴雨，那么Bt（j）对应记录的就是前一天是多云天。
寻找最佳路径的Viterbi算法的计算步骤见算法3-3。
算法3-3 Viterbi算法
输入：观测变量{xt}，t=1，2，…，T，Φ。
输出：隐含状态序列{st}。
1）初始化，V1（i）=πibi（X1）（1≤i≤N），B1（i）=0，令t=1。
2）迭代。
①计算前向概率：
②更新前一时刻对应的状态序号：
③t=t+1；
④若t≥T，则跳至步骤3，否则返回步骤2中第1步继续迭代。
3）计算全局最佳路径概率
，得到最终状态估计：
4）路径回溯：
Viterbi算法采用了回溯方法对观测序列全体进行匹配，“通盘”考虑了观测序列的情况，可以有效降低噪声带来的干扰。
3. 学习问题
对一个未知的HMM系统Φ，根据系统产生的观测序列
，确定使系统联合概率
最大的模型参数。
评估问题是利用已知的模型参数计算给定隐含状态序列的概率，解码问题是利用已知的模型参数找到最佳的隐含状态序列，它们都依赖于已知的HMM参数。但是对于很多问题来说，人们无法预先知道HMM的参数，只能依靠实际观测来推测Φ中的各种参数。这个问题是HMM相关问题中最难的。
HMM学习问题是无监督学习的典型实例，其中只有观测数据，缺少对状态的描述，因此和GMM的参数估计一样，可以使用EM算法解决。虽然使用现有理论还无法给出一个完整的表达式来得到使观测数据概率最大的模型参数，但依然可以选择最大似然作为最优化目标，使用Baum-Welch迭代算法来估计模型参数。Baum-Welch算法是Baum于1972年在EM算法的基础上提出的，又由于它同时使用了前向概率和后向概率，因此通常又称为前向-后向算法。
图3-7 后向概率计算示意图
仿照前向概率，可以定义后向概率为
其中，βt（i）是在t时刻HMM的状态为i的条件下，HMM产生部分观测序列
的概率。此时观测序列都是出现在当前时刻之后，因此后向概率考察的是当前时刻下未来的可能性。
βt（i）的递归计算需要“由后向前”迭代，如图3-7所示，方法如下。
为描述参数重估计过程，定义γt（i，j）表示在模型和观测序列确定的条件下，时刻t时HMM从状态i转移到状态j的概率：
满足γt（i，j）条件的路径如图3-8所示，其中前向概率α从左到右计算，后向概率β从右到左计算。
式（3-17）实际计算的是在当前时刻t时状态i向状态j的转移占所有状态转移概率的比值。这样可以满足概率的归一化条件。
同样地，类似γt（i，j），可以定义在模型和观测序列确定的条件下，时刻t时HMM处于隐含状态i的概率为Vt（i）：
根据式（3-17）和式（3-18）以及两个概率的含义，可以得到
。两个公式中都同时包含了前向和后向因素，前向-后向算法的得名就源于此。
图3-8 前向-后向概率计算示意图
由此可以根据观测序列来计算各参数的期望频度，并作为HMM参数的估计，如表3-3所示。
表3-3 HMM参数估计列表
估计公式为
其中，
表示在观测序列确定的情况下从状态i出发的转移个数的数学期望，
表示在观测序列确定的情况下，从状态i转移到状态j的转移个数的数学期望。
根据EM算法的性质，在得到模型参数的估计后，可以利用参数估计值替换原来的模型参数重新进行估计。Baum等已经证明，利用估计值
重新估计，可得
，因此如果迭代地计算式（3-19）的三个式子，不断循环估计，那么可以得到最大似然意义下的最优模型参数。前向-后向算法得到的最优估计结果只是一个局部最优解，无法保证全局最优。