本文接上篇继续讨论隐马尔科夫模型，上篇详见：

http://blog.sciencenet.cn/blog-2970729-1188964.html

在讨论之前，欢迎我们的主角——隐马尔科夫模型(HMM)出场！

本篇主要探讨隐马尔科夫模型三个基本问题中的第一个问题，后续还会接着讨论另外的两个，敬请关注

3. 隐马尔科夫模型的三个基本问题

Problem 1. 评估问题 (Evaluation Problem)

给定模型λ= (A, B, π)，以及观测链O，求解此模型出现观测链O的概率P(O|λ)? （注：用上篇中年轮与气温的例子来说，已知状态转移矩阵A，观测矩阵B，以及初始状态分布π，求特定的观测链，例如S-M-S-L这种年轮排列，出现的概率）

方案1. 枚举法

为了解决这个问题，我们最开始可能想到的是简单粗暴的枚举法(概率法)：列举出所有可能的状态链(例如H-H-H-H、H-H-H-C、H-H-C-H …等)，对应出现S-M-S-L这种年轮排列的概率，再把所有的概率相加，自然就可以得到在P(O|λ)。

如果按照数学公式来计算，思路如下：

先定义状态链X = (X₀, X₁, X₂, …, X_T-1)。

(1)只看HMM图中虚线上半部分，相当于给定模型λ，求状态链X的概率，很显然

(2)只看HMM图中虚线下半部分，相当于在给定了状态链X和模型λ，求观测链O的概率。很显然

(3) 按联合概率的定义有

当然，这个公式也可以推导出来，具体如下：

(4)再按概率公式展开P(O|λ)，即

也即，

这种算法虽然直观，但是计算量非常大，是O(TN^T)阶。在概念上可行，但是计算不上可行。

方案2. 前向算法(Forward Algorithm)

既然叫做隐马尔科夫链，作为一条链我们就可以用链的方式来算。链的特征是当前的状态仅与上一个状态有关。

Q1：还是用年轮与气温的例子来说，如何计算第四年观测到大年轮(L)的概率？

A1：它是以下两部分之和：其一是第四年气温为高温(H)，观测为大年轮(L)的概率，其二是第四年气温为低温(C)，观测为大年轮(L)的概率。

Q2：这时有人要问了，第四年气温为低温(C)的概率是多少？

A2：它是以下两部分之和：其一是第三年气温为H的概率乘以气温由高温(H)转低温(C)的概率，其二是第三年气温为低温(C)的概率乘以气温由低温(C)转低温(C)的概率。

Q3：紧接着问，第三年气温为高温(H)的概率是多少？

A3：这是第三年观测为小年轮(S)，气温为H的概率！

Q4：那么第三年观测为小年轮(S)的概率又是多少？

A4：很好，回头看看第一问Q1，这个问题又回来了！相当于整个计算递归(轮回)了一遍。

用图来说明如下：

如果用数学公式表示，如下：

先定义前向概率α_t(i)，它表示到时刻t时，观测序列为o₁, o₂, o₃, …,o_t，且状态为q_i的概率，记作：

思路采用的是递归(从最后一个状态到第一个状态)，但是计算的时候反过(从最一个状态到最后一个状态)：

1. 计算初始的前向概率α₀(i)

2. 联系t-1时刻的前向概率α_t-1(j)与t时刻的前向概率α_t(i)

注：它由两部分组成，红色框中的部分表明t-1时刻各个状态对应的前向概率与其状态转移概率之积再求和，前面t-1的事就搞定了；蓝色框内的是当前时刻(t时刻) O_t这种观测值的第i个状态的概率

3. 当运行到最后一个前向概率时，所有的计算都完成了，即获取到P(O|λ)，具体的式子如下：

直接概率法的复杂度是O(TN^T)，而前向算法的复杂度是O(N²T)，当T较大时可以大大节省计算开销。

参考材料：

Guy Leonard Kouemou. History and Theoretical Basics of Hidden Markov Models

Mark Stamp. A Revealing Introduction to Hidden Markov Models

李航. 统计学习方法