隐马尔科夫模型（1）基本概念和概率计算

---

本文我们介绍一个机器学习中常用的模型————隐马尔科夫模型（Hidden Markov Model，HMM），后文我们简称为HMM。HMM是一种概率图模型，常用于对有序数据进行处理。下面我们通过一个简单的例子来理解下什么是HMM。
##引子
假设你的邻居家有个正在上小学的儿子，我们称之为小明吧，小明每天都在早上背上小书包去上学，然后到晚上的时候回家。假设我们现在对小明在学习里的表现很感兴趣，认为小明在学校里的状态有三种，分别是被老师批评了，被老师表扬了，和既没被表扬也没被批评，我们分别记为$q_{0}$q0​,$q_{1}$q1​,$q_{2}$q2​。

那么怎么能确定他在学校的状态呢？最好的办法就是去小明的学校盯着他。但是谁吃饱了撑的有那个时间去盯他呢？于是我们左思右想，想到一个好主意，小明如果被表扬，他应该心情不错吧，如果被批评了，他不开心的概率可能更大一点。所以我们可以在他放学回家时的心情来估计下他今天的表现。但是凡事也有例外，比如他今天虽然被批评了，但是喜欢的小红成为了他的邻桌，那么他可能会忘掉老师带来的不愉快，而因为小红开心的不得了。所以啊，我们只能说被表扬的情况下，他开心的可能性比较大，但也不会是1，而同样，被批评的时候，不开心概率比较大，但也不会是1，而我们要是看到他今天平平淡淡地回家，那么他比较有可能是既没被批评也没被表扬。这里我们记我们观测到他的心情好、坏、一般分别为$v_{0}$v0​,$v_{1}$v1​,$v_{2}$v2​。那么假设我们观察了一星期，观测到他的心情序列为$v_{0}$v0​，$v_{0}$v0​，$v_{1}$v1​，$v_{1}$v1​，$v_{2}$v2​，$v_{0}$v0​，$v_{1}$v1​，请问小明同学这一星期在学习的状态序列应该是什么呢？

是不是感觉无从下手？是不是感觉这种又有看得见的变量（观测值），又有看不见的变量（状态），还有变量序列的问题很变态很棘手？没关系，在马尔科夫大神和各位数据分析前辈的努力下，我们已经有了解决这种问题的数学工具啦！这就是我们今天要讲的隐马尔科夫模型。

隐马尔科夫模型的基本定义

在《统计学习方法》一书中，隐马尔科夫模型用于描述这样一个过程：

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。

隐藏的马尔科夫链随机生成的不可观测的状态随机序列，就称为是状态序列，而由状态序列生成的观测随机序列为观测序列。读到这里，读者可能已经意识到了，如果要利用隐马尔可夫模型，模型的状态集合和观测集合应该事先给出。隐马尔科夫模型的形式定义如下：

• 状态集合$Q=\{q_{0},q_{1},q_{2}......q_{N-1}\}$Q={q0​,q1​,q2​......qN−1​}，$N$N为状态数量。在上面的例子中，$Q=\{q_{0},q_{1},q_{2}\}$Q={q0​,q1​,q2​}
• 可能的观测集合$V=\{ v_{0},v_{1},v_{2},......v_{M-1} \}$V={v0​,v1​,v2​,......vM−1​}，$M$M为可能的观测数量。在上面的例子中，$V=\{v_{0},v_{1},v_{2}\}$V={v0​,v1​,v2​}
• 长度为$T$T的状态序列$S=[s_{0},s_{1},s_{2},......s_{T-1}]$S=[s0​,s1​,s2​,......sT−1​]，对应得观测序列为$O=[o_{0},o_{1},o_{2},......o_{T-1}]$O=[o0​,o1​,o2​,......oT−1​]。在上面的例子中，$O=[v_{0},v_{0},v_{1},v_{1},v_{2},v_{0},v_{1}]$O=[v0​,v0​,v1​,v1​,v2​,v0​,v1​]
• 状态转移矩阵$A=[a_{ij}]_{N\times N}$A=[aij​]N×N​，其中$a_{ij}$aij​表示状态$q_{i}$qi​转变为状态$q_{j}$qj​的概率$a_{ij}=P(i_{t+1}=q_{j}|i_{t}=q_{i})$aij​=P(it+1​=qj​∣it​=qi​)。在上面的例子中，就是前一天小明的状态对第二天小明的状态的影响，或者说前一天老师对小明的态度，对后一天老师对小明的态度的影响。
• 观测概率矩阵$B=[b_{j}(k)]_{N\times M}$B=[bj​(k)]N×M​，$b_{j}(k)=P(v_{k}|q_{j})$bj​(k)=P(vk​∣qj​)，表示状态$q_{j}$qj​产生$v_{k}$vk​观测的概率。在上面的例子中，就是已知小明$j$j天的状态，小明当天的某种表现情绪的概率。
• 初始状态概率分布$\pi=[\pi_{0},\pi_{1}......\pi_{N-1}]$π=[π0​,π1​......πN−1​]，其中$\pi_{i}=P(i_{1}=q_{i})$πi​=P(i1​=qi​)。在上面的例子中，我们第一天观察的时候，他的每个状态的可能性。

由定义可知，在给定状态集合$Q$Q和可能的观测集合$V$V后，一个HMM模型可以由状态转移矩阵$A$A、观测概率矩阵$B$B以及初始状态概率分布$\pi$π确定，因此一个HMM模型可以表示为$\lambda(A,B,\pi)$λ(A,B,π)。

隐马尔可夫模型的三个基本问题

利用隐马尔可夫模型时，通常涉及三个问题，分别是：

• 概率计算：已知HMM的所有参数，给定长度为T的观测序列$O=[o_{0},o_{1},o_{2},......o_{T-1}]$O=[o0​,o1​,o2​,......oT−1​]，求解$P(O)$P(O)。
• 状态解码：已知HMM的所有参数，给定长度为T的观测序列$O=[o_{0},o_{1},o_{2},......o_{T-1}]$O=[o0​,o1​,o2​,......oT−1​]，求解$O$O出现的条件下，概率最大的状态序列$argmax_{I} P(I|O)$argmaxI​P(I∣O)。
• 参数学习：HMM参数未知，通过观测序列$O$O学习HMM的参数，$argmax_{\lambda}P(\lambda|O)$argmaxλ​P(λ∣O)。

本小节首先对概率计算问题进行阐述。

概率计算

计算$P(O)$P(O)，一个很自然的想法是计算$\Sigma_{I\in I^{*}}P(O,I)$ΣI∈I∗​P(O,I)。其中$I^{*}$I∗为从1时刻到$T$T时刻所有可能的状态序列，应该有$N^{T}$NT个不同的状态序列，计算的复杂度过高，很难利用该方法。
现有的方法是使用一种动态规划的方案，称之为前向算法。首先定义前向概率的概念：

给定HMM模型$\lambda$λ，时刻t时已有观测序列为$o_{0},o_{1}......o_{t-1}$o0​,o1​......ot−1​，且t时刻状态为$q_{i}$qi​的概率前向概率$\alpha_{t}(i)=P(o_{0},o_{1}......o_{t},s_{t}=q_{i}), 0\leq t \leq T-1$αt​(i)=P(o0​,o1​......ot​,st​=qi​),0≤t≤T−1。

需要注意的是，当引入一个特定的前向概率时，需要说明具体的观测序列、时刻t，以及时刻t时的状态。

可以看出，前向概率$\alpha_{t}(i)$αt​(i)涵盖了从0时刻到t-1时刻为止，$N^{t-1}$Nt−1条状态路径的所有可能性。这使得我们在计算t+1时的情况时，不必再考虑从时刻1到时刻t这段时间内的状态路径，只用考虑时间t到时间t+1间的状态路径即可。这无疑大大减少了工作量。具体的算法如下：

1.时刻1的初值：
计算$\alpha_{0}(i)=\pi_{i}b_{i}(o_{1})$α0​(i)=πi​bi​(o1​)
2.递推出时刻２,３．．．Ｔ时刻的前向概率：
$\alpha_{t}(i)=[\Sigma_{0\leq j\leq N-1}\alpha_{t-1}(j)a_{ji}]b_{i}(o_{t})$αt​(i)=[Σ0≤j≤N−1​αt−1​(j)aji​]bi​(ot​)
3.求得$P(O)$P(O):
$P(O)=\Sigma_{0\leq i\leq N-1}\alpha_{T-1}(i)$P(O)=Σ0≤i≤N−1​αT−1​(i)

下面是一个动态演示图，图中的例子有4中状态。

除了前向算法外，还有一种后向算法，同样是利用了动态规划的方案，这里我们同样首先定义后向概率的概念：

给定HMM模型$\lambda$λ，定义t时刻状态为$q_{i}$qi​的条件下，t+1至T时刻观测序列为$o_{t},o_{t+1}......o_{T-1}$ot​,ot+1​......oT−1​，后向概率$\beta_{t}(i)=P(o_{t},o_{t+1}......o_{T-1}|s_{t-1}=q_{i})$βt​(i)=P(ot​,ot+1​......oT−1​∣st−1​=qi​)。

可以看出，前向算法是从前向后推演整个状态路径，而后向算法是从后往前推演整个状态路径。但本质原理是一样的，后向算法的具体如下：

1.时刻T的初值：
计算$\beta_{T-1}(i)=1$βT−1​(i)=1。这里是直接定义为1，从上面的后向概率概念可以看出没有对$\beta_{T-1}(i)$βT−1​(i)的定义。因为不存在T+1时刻。
2.递推出当t=T-2,T-3．．．0时刻的后向概率：
$\beta_{t}(i)=\Sigma_{0\leq j\leq N-1}\beta_{t+1}(j)a_{ij}b_{j}(o_{t+1})$βt​(i)=Σ0≤j≤N−1​βt+1​(j)aij​bj​(ot+1​)
3.求得$P(O)$P(O):
$P(O)=\Sigma_{0\leq j\leq N-1}\beta_{1}(i)\pi_{i}b_i (o_0)$P(O)=Σ0≤j≤N−1​β1​(i)πi​bi​(o0​)
大家可以思考一下，为什么前向概率是联合概率模式，而后向概率是条件概率模式呢？这是因为前向概率开始于一个已知量$\pi$π，因为在描述路径的时候有一个已知的开头，可以用联合概率。而后向概率开始于未知量，在向前推演的时候，没有一个已知的开头，因此需要假设一个开头，因此得使用条件概率。

我在学习HMM的时候，一开始不是很理解后向算法，首先是直观上没有前向算法那么好理解，其次公式推导上也有点费脑。后来我推导出了后向算法，它的思路也在脑海中渐渐清晰。如果后期有时间，我会把后向算法推导更新上。
后期还会继续更新HMM的内容，包括状态解码和参数学习，欢迎一起探讨。