隐马尔可夫模型是相对于马尔可夫模型而言的，其中的马尔可夫源于俄国数学家安德烈·马尔可夫（A.A.Markov）。隐马尔可夫模型被广泛地应用在语音识别、词性自动标注、音字转换、自然语言处理等领域。在介绍隐马尔可夫模型之前，先来看看马尔可夫模型。马尔可夫模型也称为马尔可夫链（Markov chain），以随机过程的视角来看，又称为马尔可夫过程（Markov process）。
一个n阶的马尔可夫过程是指过程中的每个状态的转移只依赖于过去的n个状态。当n=1时，就是最简单的一阶马尔可夫过程，它满足以下假设：
（1）t+1时刻的系统状态的概率分布只与t时刻的状态有关，与t时刻之前的状态无关。
（2）从t时刻到t+1时刻的状态转移与t的值无关。
简单来说，就是状态将来是什么样子只与当前的状态有关，而和过去的状态无关。或者说，某个物体以随机的方式运动，并且它的运动是无记忆的，满足这种性质的随机过程就可以称作一阶马尔可夫过程。现实生活中有很多场景符合这个假设，比如传染病受感染的人数、股票的价格、公园内的游玩人数、液体中微粒的布朗运动等。马尔可夫过程就是指一个状态不断演变的过程。它是随机过程的典型代表，对其建模后就称为马尔可夫模型；如果过程中状态和时间都是离散的，该过程就可以用随机变量序列X1，X2，X3，…表示，此时就称为马尔可夫链。Xi表示在i时刻的状态，Xi所有可能取值的集合就是状态空间。马尔可夫链中状态的变化可以用条件概率模型来描述：
它表示当前状态为Xi时下一个状态变为Xj的转移概率。整个状态空间的转移概率就可以用状态转移概率矩阵A来描述，这便是马尔可夫模型的参数之一。
其中，N表示所有可能隐藏状态的个数。
马尔可夫模型参数还包括一个初始状态概率分布向量，称为π向量：
一个一阶马尔可夫模型由状态空间、初始状态概率分布向量π、状态转移概率矩阵A三个部分组成。下面用一个简单的例子来说明。
例4.11 假设天气的变化服从马尔可夫性质，并假设天气的状态只有2种——晴和雨，那么每天观测一次天气就能得到一组天气状态序列。如果某个地区天气变化情况统计为：当天是晴天，第2天为晴天的概率为0.8，第2天下雨的概率为0.2；当天为下雨状态，第二天为晴天的概率为0.5，第二天还是下雨天的概率为0.5。假设第一天为晴天的概率为0.7，请用马尔可夫模型描述该随机过程。
解 依题意有
用图来表示这个马尔可夫过程如图4.42所示。
图4.42 马尔可夫过程实例
有了这个模型，就可以计算该地区和天气相关的一些问题了，比如出现“雨、晴、晴、晴、雨”的概率是多少？运用条件概率公式即可得
P=πRa21a11a11a12=0.3·0.5·0.8·0.8·0.2=0.0192
再比如，计算某一天为晴天的概率是多少？无论前一天是晴还是雨，第2天都可能为晴天，所以使用全概率公式，前一天是晴天变为第二天还是晴天的概率加上前一天是雨天变为第二天为晴天的概率，即
P=πSa11+πRa21=0.7·0.8+0.3·0.5=0.71
在马尔可夫模型中，状态变量是可以直接观测到的。现实中还有很多情况，状态变量本身并不能直接观测到，能观测到的只是在该状态下的一些随机输出变量。这样就变成了一个双重的随机过程，其中状态的变化是基本的随机过程，它是隐藏着的，无法直接观测，能观测到的是另一组在对应状态下的输出随机过程。比如对于语音信号，可以观测到的是声音信号，具体来说可以是每个音素的频谱或者强度等参数，这些参数又和文字、词语等相关联。显然，在语音对话中，文字等并不能直接观测得到，人们通过听到的声音来感知对应的文字。再比如，小红在北京，她的容易受到天气的影响，下雨的时候，她经常不开心，10天里会有6天不开心、4天开心；而天晴，她心情就不错，10天里有8天是开心的。小明是小红的朋友，他在武汉，他不知道北京的天气情况，但是他每天会和小红通电话，他知道小红的心情容易受到天气的影响，通过电话他能判断出小红的心情是好还是坏，于是他也就大概知道北京的天气情况了。这时，北京的天气情况对于小明而言就是隐马尔可夫模型。小明无法观测到北京的天气，但是他可以观测到由于北京的天气而产生的结果（小红的心情），也就是北京的天气状态变化是观测不到的隐藏随机过程，可以观测到的是小红的心情，而小红心情的变化是另一个随机过程，所以隐马尔可夫模型相当于是一个双重随机过程。隐马尔可夫模型的表示，相对于马尔可夫模型而言多了可以观测到的所有输出对应的观测空间以及在不同状态下产生的观测输出的概率分布参数B矩阵：
其中，M表示所有可能观测到的状态的个数，行X代表隐藏的状态，列y代表可以观测到的状态，比如b2（y3），简写为b2（3），就代表着在X2状态下观测到y3的概率。显然，每一行的概率和为1。例4.11的B参数为
用图表示，如图4.43所示。
图4.43 隐马尔可夫模型实例
一个完整的隐马尔可夫模型λ包括具有N个状态的隐藏状态空间、由隐藏状态产生的M种观测数据的观测空间和A、B、π参数。A为隐藏状态的转移概率矩阵；B为观测矩阵，也称为混淆矩阵；π为初始状态概率分布向量。在这个模型下，可以观测到的数据序列用O=［o1，o2，o3，…］表示，oi的取值为观测空间Y中的某个值。
针对隐马尔可夫模型，有3个基本的问题，分别是：
（1）评估问题。
评估问题也称概率计算问题，是指给定模型参数和观测到的数据序列，如何去有效计算在该模型下产生这个观测序列的概率，也就是评估在该模型下有多大的可能性产生这个观测序列。还以前面的例子说明，如果小明知道了与北京的天气和小红的心情对应的隐马尔可夫模型，当有人告诉小明小红这个星期每天都心情不好时，小明应该相信这个人的话几分？
（2）估计问题。
估计问题也称为解码或预测问题，是指给定模型和观测序列，如何找到和该观测序列匹配性最佳的隐藏状态序列，也就是根据观测到的结果推算模型最有可能的隐藏状态变化情况。比如，小明发现小红一个星期都心情不好时，小明怎样去推算这个星期北京最有可能的天气情况？
（3）训练问题。
训练问题也称为学习问题，是指给定观测序列，如何调整模型参数，使得该观测序列出现的概率最大，也就是如何训练模型，使其能更好地描述观测数据。该问题是3个问题中最难也是最关键的一个。举例来说，小明只是知道了小红每天的心情，他知道小红的心情是和天气有一定关系的，他需要找出第一天北京的天气情况概率分布，北京晴天和下雨天转换的概率是怎样的，晴天、雨天小红的心情又是怎样受到天气的影响的，也就是不同天气情况下她心情好或者不好的概率可能会是什么样。
下面，分别介绍这3个问题的求解方法。
对于第1个问题的求解，已知模型参数求产生某个输出序列的概率，通常采用前向算法（forward algorithm）或后向算法（backward algorithm）。如果不采用前向、后向算法，直接使用暴力算法，则由初始状态开始，计算在所有可能的状态组合下，产生该输出序列的概率，然后加在一起即可。当隐藏状态数为N、状态变化的长度为T时，状态的组合数可以达到NT，每个状态下还要计算观测值出现的概率，算法的时间复杂度将达到O（TNT）。当状态数较多或者观测序列较长时，用暴力算法进行计算，复杂度太高，显然不可行。比如，对于图4.43所示的隐马尔可夫模型，观测到小红三天的心情为“开心、开心、不开心”，这三天的天气状态组合（用S代表晴天，用R代表雨天，用H代表开心，用U代表不开心）就有“S，S，S”，“S，S，R”，“S，R，S”，…，“R，R，R”八种。在“S，S，S”状态下，小红出现对应心情的概率为
πS·bS（H）·aSS·bS（H）·aSS·bS（U）=0.7·0.8·0.8·0.8·0.8·0.2=0.0573 44
……
依次计算完所有概率后加在一起就得到了产生该输出序列的概率。在计算过程中会发现，很多计算被重复进行，而前向、后向算法采用递归的方式，用到了第3章中介绍的动态规划的思想，大大减少了计算量。假设最后一步为在t时刻观测到输出yt，可能出现的每个状态都由t-1时刻观测到的yt-1转移而来，从而可以构建递推表达式。这样从初始t=1时刻开始向前逐级计算并保存结果，可以避免重复计算。
前向算法的具体流程为：
（1）由初始状态概率分布向量π开始，计算初始前向概率：
（2）递推计算：
其中αt（j）是为了写递推表达式而定义的前向概率，表示从开始到t时刻，状态为Xj，观测到指定序列的概率。中括号内为观测到前t-1个输出时每个状态的前向概率与转移到当前状态时的概率是乘积之和，如图4.44（a）所示，然后在当前状态下观测到当前的输出yt。
（3）最后计算：
即在已知模型λ下观测到Y序列中T个状态的概率。
由图4.44（b）可以简单估算算法的复杂度。相邻两级中，第2级N个节点中的每个节点都可以由前1级N个节点转移而来，计算次数为N2，每一级需要进行累加计算，执行时间和T个N2成正比，即算法的时间复杂度为O（TN2），相对于O（TNT），大大降低。
图4.44 前向概率计算递推示意图
例4.12 已知北京天气（sunny、rainy）和小红心情（happy、unhappy）的隐马尔可夫模型参数（A，B，π），用前向算法计算小红3天的心情为“开心、开心、不开心”的概率。
解 计算初始前向概率：
递推计算：
最后计算
Python实现前向算法参考代码如下。
完整前向和后向算法代码请参考\C4\s4_4_3_HMM\forward_backward.py，代码中还包括例4.12的求解。
和前向算法很相似，后向算法也采用了递推的方式，只是它由后往前递推计算，算法中定义了后向概率βt（i）。它表示在时刻t-1，从状态为Xi出发，观测到从t到最后的T时刻的输出状态时的概率，如图4.45所示。显然，对于最终的T时刻，后继再没有状态和可观测的内容了。为了方便计算和作为递推的初始条件，将所有状态的后向概率都定义为1。
图4.45 后向算法递推计算
后向算法具体流程为：
（1）初始化，对最终时刻所有状态Xi的后向概率都定义为1：
βT（i）=1， i=1，2，…，N （4.73）
因为最终时刻后面再没有状态和可观测的内容了，为了方便计算，所以定义为1。
（2）递推计算：
（3）最后计算：
对于第2个问题的求解，已知隐马尔可夫模型和观测序列，求最有可能产生该观测序列的隐藏状态，常用的算法是维特比算法。
维特比算法的发明者安德鲁·维特比是高通公司（Qualcomm）的创始人之一，于1967年首次提出该算法。维特比算法是动态规划的典型应用，即用动态规划求解概率最大的路径，也就是最佳路径。
从最后时刻的T观测状态开始分析，假设可以产生该观测状态的隐藏状态有N个，那么能产生最大概率的路径，一定来自产生前T-1个观测状态并具有最大概率的路径转移到这N个状态，所以只需要计算由到达上一个状态的最大概率的路径转移到当前每个状态并产生当前输出的概率，选择其中最大的概率作为当前时刻的最佳路径的概率即可，如图4.46所示。按照动态规划的思想，从初始时刻t=1开始，递推地计算各个时刻每个状态路径的最大概率，直到最后时刻t=T为止，此时得到的最大概率即为最佳路径的概率。然后由后向前依次选择使当前概率值最大的上一个状态，就可以得到最优的隐藏状态序列。
图4.46 维特比算法示意图
定义δt-1（i）为在t-1时刻，状态为Xi的所有单条路径中的概率最大值，则可以得到递推公式
(www.xing528.com)
定义在时刻t，状态为Xi的所有单条路径中概率最大的路径上一个时刻的隐藏状态为
得到维特比算法的具体流程为：
（1）初始化：
（2）递推计算：
（3）最后计算：
（4）回溯得到最优隐藏状态序列：
可以发现，维特比算法和前向算法很相似，主要区别是多了一个回溯步骤，并且以用式（4.80）对前面状态求最大值代替了前向算法中的式（4.71）求和。维特比算法在Python中的实现可以参考代码\C4\s4_4_3_HMM\viterbi_01.py。
例4.13 假设在高、中、低（H、M、L）三种不同的气压情况下，晴天和下雨的概率分别为：0.75，0.25；0.5，0.5；0.25，0.75。另外，还观察到三种气压的转换概率分布如图4.47所示。设初始状态概率πH=0.2，πM=0.5，πL=0.3，如果观察到连续两天的天气情况都是晴天，请估计这两天的气压状况。
图4.47 气压状态转换图
解 （1）初始化，计算δ1（·）。
由式（4.78）得
δ1（L）=πLbL（S）=0.3×0.25=0.075
δ1（H）=πHbH（S）=0.2×0.75=0.15
定义ψ1（·）=0。
（2）由式（4.80）、式（4.81）计算δ2（·）和ψ2（·）。
δ2（M）=max［δ1（H）aHM，δ1（M）aMM，δ1（L）aLM］·bM（S）
代入数值，有
δ1（H）aHM=0.15·0.2=0.03
δ1（M）aMM=0.25·0.4=0.1
δ1（L）aLM=0.075·0.3=0.0225
最大值为δ1（M）aMM，所以
δ2（M）=δ1（M）aMMbM（S）=0.05， ψ2（M）=M
同理，可得
δ2（L）=δ1（M）aMLbL（S）=0.018 75， ψ2（L）=M
δ2（H）=δ1（H）aHHbH（S）=0.078 75， ψ2（H）=H
（3）根据第（2）步的结果确定最优隐藏状态序列的概率为0.078 75，最优隐藏状态序列的终状态为H。
（4）回溯。
由最终状态ψ2（H）=H回溯，得到最优隐藏状态序列为H H。
隐马尔可夫模型的第3个问题是关于如何确定模型参数的问题，即如何建模的问题。对于这个问题，可以分为两种情况。一种实际上属于监督学习的内容了，也就是说如果训练数据不仅有观测数据序列，还知道其对应的隐藏状态序列，那就属于监督学习，可以直接利用最大似然估计（maximum likelihood estimate）算法来估计模型参数。比如已经知道了一段时间北京的天气变化情况，就可以统计晴天中，有多少个晴天的前一天也是晴天，有多少个晴天的前一天是下雨天，从而用最大似然估计算法估计出隐藏状态转移概率矩阵A；再统计在晴天和下雨各种状态下，心情不错有多少天，心情不好又有多少天，从而估计出观测矩阵B。初始状态概率分布向量π也可以从这些天的天气统计中估算得到。在使用最大似然估计算法时，由于似然函数是连乘的，因此为了方便分析与计算，常常对其取对数，使用对数似然函数，将连乘变成连加。
最大似然函数估计算法的一般步骤为：
（1）写出似然函数，并取对数；
（2）求对数似然函数的导数或偏导数，并令其为0，得到似然方程；
（3）解似然方程，得到的参数即为所求。
然而，在很多情况下，人工标注训练数据可能代价很高或者无法实现，这时就只能利用非监督学习方法，也就是说在只有观测数据序列［o1，o2，o3，…］的情况下，去优化模型的参数（A，B，π）。在这种情况下，由于存在隐藏状态X，最大似然估计算法很难直接使用，这时常用的算法是鲍姆-韦尔奇算法（Baum-Welch algorithm）。
Baum-Welch算法的思想是这样的：首先找到一组可以产生输出观测数据序列O的模型参数，构建初始模型λ0，比如转移概率和输出观测符号概率都是均匀分布时，就可能产生任何输出。接下来，在这个初始模型的基础上找到一个更好的模型。具体来说，前面已经讨论了隐马尔可夫模型第一个问题和第二个问题的求解，所以基于这个初始模型，可以计算出该模型产生这个观测数据序列O的概率以及在该模型下，产生O的所有可能路径和这些路径产生O的概率。然后，把这些数据当作是标注过的数据，采用前面监督学习的方式，用最大似然估计算法，计算出一组新的模型参数，构建新模型λ1。可以证明
将上述作为一次迭代过程。这样，重复这个过程，不断迭代下去，直到P（O|λ）不再有明显提高为止。
Baum-Welch算法每次迭代都是在估计（expectation）新的模型参数，使得在新模型下，观测数据序列的输出概率（可以看作为目标函数）达到最大化（maximization），所以这个过程也称为期望值最大化（EM，expectation maximization）过程。
EM算法的基本步骤为：
（1）确定完全数据的对数似然函数；
（2）初始化参数的值，然后分两步进行循环迭代；
（3）执行EM算法的E步，基于当前参数计算在给定观测样本的条件下，对隐变量x的条件概率，即隐变量的后验概率值；
（4）执行EM算法的M步，由E步得到的概率值构造目标函数（下界函数），它是隐变量的数学期望，求数学期望的极值来更新参数的值；
（5）当相邻两次迭代目标函数值之差小于指定阈值时，终止迭代。
关于EM算法的数学证明，简单分析如下：
首先，对于一个凸函数，在其定义域上的任意两点x1，x2，满足
也就是说凸函数任意两点的割线位于函数图形上方，如图4.48所示。这也是数学上有名的Jensen不等式（Jensen’s inequality）的两个点的表示形式。凸函数也可以定义为；如果对于所有实数x，f（x）的二阶导数都大于或等于0，那么f是凸函数。
图4.48 凸函数及Jensen不等式示意图
Jensen不等式是指对于任意点集｛xi｝，若λi≥0且
，则凸函数f（x）满足
上述结论可用数学归纳法证明，这里不做说明。在概率论中，如果把式（4.87）中的λi看成是取值为xi的离散变量x的概率分布，那么Jensen不等式可以写成f（E［x］）≤E［f（x）］，其中E［］·表示期望。举例来说，假设随机变量x可以取值为x1和x2，取值为x1的概率为t，取值为x2的概率为1-t，那么tx1+（1-t）x2可以看作是x的期望E［x］，tf（x1）+（1-t）f（x2）可以看作是f（x）的期望，即E［f（x）］，如图4.48中所示，满足E［f（x）］≥f（E［x］）。Jensen不等式应用于凹函数时，大于或等于符号反向变成小于或等于符号。
在隐马尔可夫模型参数估计中，相当于在似然函数中多了一个未知变量x，最大似然估计的目标变成了找合适的参数和x，使似然函数最大，即
因为存在和的对数，求导形式会很复杂，所以进一步对其处理，利用Jensen不等式，构造求期望的表达式，
可以看作是
的期望，
看作是式（4.87）中的λi，由于取对数运算函数f（x）=log（x）为凹函数，因此式（4.87）符号反向，于是有
和的对数就变成了对数的和，求导就容易了。由于是不等式，因此式（4.89）的右边可以看作是一个下界函数，求其极大值，构造新的下界函数，不断优化，使对数似然函数的值也增大，直至收敛到局部最优解。
下面介绍Baum-Welch算法获取隐马尔可夫模型参数的具体流程。
首先根据隐马尔可夫模型前向、后向算法，可以得到两个计算公式：
（1）给定隐马尔可夫模型λ和观测数据序列O，在时刻t处于状态Xi的概率，记为
由前向概率αt（i）和后向概率βt（i）的定义可知
于是
（2）给定隐马尔可夫模型λ和观测数据序列O，在时刻t处于状态Xi，在下一时刻t+1处于状态Xj的概率，记为根据前向、后向算法，有
然后采用Baum-Welch算法：
（1）初始化，取n=0，设定一组可以产生观测数据序列的隐马尔可夫模型参数
（2）递推，依次取n=1，2，…，计算
（3）终止，得到模型参数λ（n+1）=（A（n+1），B（n+1），π（n+1））。
Baum-Welch算法的实现代码请参考“\C4\s4_4_3_HMM\baum_welch.py”。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
