[白话解析]以水浒传为例学习隐马尔可夫模型
罗西的思考 人气:0
# [白话解析]以水浒传为例学习隐马尔可夫模型
## 0x00 摘要
本文将尽量使用易懂的方式，尽可能不涉及数学公式，而是从整体的思路上来看，运用感性直觉的思考来解释隐马尔可夫模型。并且从名著中找了个具体应用场景来帮助大家深入这个概念。
## 0x01 说明
在机器学习过程中，会遇到很多晦涩的概念，相关数学公式很多，大家理解起来很有困难。遇到类似情况，我们应该多从直觉角度入手思考，用类别或者举例来**附会**，这样往往会有更好的效果。
我在讲解论述过程中给自己的要求是：在生活中或者名著中找一个例子，然后用自己的话语阐述出来。
## 0x02 概率图
概率图模型是用图来表示变量概率依赖关系的理论，结合概率论与图论的知识，利用图来表示与模型有关的变量的联合概率分布。由图灵奖获得者Pearl开发出来。
如果用一个词来形容概率图模型（Probabilistic Graphical Model）的话，那就是“优雅”。对于一个实际问题，我们希望能够挖掘隐含在数据中的知识。概率图模型构建了这样一幅图，用观测结点表示观测到的数据，用隐含结点表示潜在的知识，用边来描述知识与数据的相互关系，**最后基于这样的关系图获得一个概率分布**，非常“优雅”地解决了问题。
概率图中的节点分为隐含节点和观测节点，边分为有向边和无向边。从概率论的角度，节点对应于随机变量，边对应于随机变量的依赖或相关关系，其中**有向边表示单向的依赖，无向边表示相互依赖关系**。
概率图模型分为**贝叶斯网络（Bayesian Network）和马尔可夫网络（Markov Network）**两大类。贝叶斯网络可以用一个有向图结构表示，马尔可夫网络可以表 示成一个无向图的网络结构。更详细地说，概率图模型包括了朴素贝叶斯模型、最大熵模型、隐马尔可夫模型、条件随机场、主题模型等，在机器学习的诸多场景中都有着广泛的应用。
## 0x03 生成式模型和判别式模型的区别
现在我们知道，概率图可以分成有向图模型和无向图模型，顾名思义，就是图里面的边是否有方向。那么什么样的模型的边有方向，而什么样的没方向呢？这个很好想到，有方向的表达的是一种推演关系，也就是在A的前提下出现了B，这种模型又叫做生成式模型。而没有方向表达的是一种“这样就对了”的关系，也就是A和B同时存在就对了，这种模型又叫做判别式模型。
根据建模的究竟是联合概率分布 P(x,y) 还是条件概率分布 P(y|x)。派生出生成式模型与判别式模型。
### 1. 生成式模型
生成式模型一般用联合概率计算(因为我们知道A的前提了，可以算联合概率)，即通过对观测值和标注数据计算联合概率分布P(x,y)来达到判定估算y的目的。
生成式模型是模拟数据的生成过程，两类随机变量存在因果先后关系，先有因素 x，后有结果 y，这种因果关系由联合分布模拟：
$$
P(x,y) = P(x)P(y|x)
$$
通过联合分布 P(x,y)，生成式模型其实间接建模了 P(x)：
$$
P(x) = \sum_y P(x,y)
$$
需要注意的是，在模型训练中，我学习到的是X与Y的联合模型 P(X,Y) ，也就是说，**我在训练阶段是只对** P(X,Y)**建模**，我需要确定维护这个联合概率分布的所有的信息参数，要对每个label (y) 都需要建模。所以没有什么判别边界。
完了之后在inference再对新的sample计算P(Y|X)，导出 Y，最终选择最优概率的label为结果，但这已经不属于建模阶段了。
这里有两个缺陷:
- P(x) 很难准确估计，因为特征之间并非相互独立，而是存在错综复杂的依赖关系。
- P(x) 在分类中也没有直接作用。
为了克服这两个问题，判别式模型出现。
### 2. 判别式模型
判别式模型一般用条件概率计算(因为我们不知道前提，所以只能"假设"A条件下B的概率)。即通过求解条件概率分布P(y|x)或者直接计算y的值来预测y。
判别式模型直接跳过了 P(x)，直接对条件概率 P(y|x) 建模，就是说，直接根据X特征来对Y建模训练。不管 x 内部存在多复杂的关系，也不影响判别式模型对 y 的判断，于是就能够**放心大胆的利用各种各样丰富的、有关联的特征**。
具体地，我的训练过程是确定构件 P(Y|X) 模型里面“复杂映射关系”中的参数，对所有的样本只构建一个模型，确认总体判别边界。完了再去inference一批新的sample。观测到输入什么特征，就预测最可能的label。
### 3. 代表
生成式模型的代表是：n元语法模型、隐马尔可夫模型、朴素贝叶斯模型等。
判别式模型的代表是：最大熵模型、支持向量机、条件随机场、感知机模型等
他们之间的区别是这样的：
> 判别式模型是这么工作的，他们直接将数据的Y（或者label），根据所提供的features，学习，最后画出了一个明显或者比较明显的边界（具体怎么做到的？通过复杂的函数映射，或者决策叠加等等mechanism），这一点线性LR、线性SVM应该很明显吧。
>
>
>
> 生成式模型是这么工作的，他们先从训练样本数据中，将所有的数据的分布情况摸透，然后最终确定一个分布，来作为我的所有的输入数据的分布，并且他是一个联合分布 P(X,Y) (注意X包含所有的特征x_i ，Y包含所有的label)。然后我来了新的样本数据（inference），好，通过学习来的模型的联合分布P(X,Y) ，再结合新样本给的X，通过条件概率就能出来Y
> $$
> P(类别|特征) = \frac {P(特征|类别)P(类别)}{P(特征)}
> $$
****
## 0x04 马尔可夫系列概念
提到马尔可夫就是一个值跟前面n个值有关，所以也就是条件概率，也就是生成式模型，也就是有向图模型。
**马尔可夫假设**：每个事件的发生概率只取决于前一个事件。
**马尔可夫链**：将满足马尔可夫假设的连续多个事件串联起来，就构成了马尔可夫链。马尔科夫链的节点是状态，边是转移概率，是template CPD的一种有向状态转移表达。
马尔可夫链的两个假设
- 齐次马尔可夫假设：即t时刻的状态只受t-1时刻状态的影响；
- 观测独立性假设：即任意时刻的观测只受该时刻所处状态的影响；
**马尔科夫模型 ** 是一种无向概率图模型，其与马尔科夫链并不是很一样。马尔科夫模型是与贝叶斯模型并列的一种概率图模型。其作用是描述互相影响，互相作用，不存在因果关系的两个随机变量之间的关系。因为作用是相互的，所有马尔科夫模型的边是无向的，或者可以说是双向的。
马尔科夫模型的强大之处在于它解除了贝叶斯模型中的因果关系，这也就使得它可以对很多平等的东西建立相互关系。比如一幅图片的各个像素就是平等的，但是各个像素之间可以相互影响（天在上，地在下）。所有马尔科夫模型被广泛的应用于图像处理/图像理解。
如果把事件具象为单词，那么马尔可夫模型就具象为二元语法模型。马尔可夫模型还可以看成是一个关于时间t的状态转换过程，也就是随机的有限状态机，那么状态序列的概率可以通过计算形成该序列所有状态之间转移弧上的概率乘积得出。
## 0x05 隐马尔可夫模型
隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。即描述一个系统隐性状态的转移和隐性状态的表现概率。系统的隐性状态指的就是一些外界不便观察(或观察不到)的状态。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析。
HMM是一种生成式模型，它的理论基础是朴素贝叶斯，本质上就类似于我们将朴素贝叶斯在单样本分类问题上的应用推广到序列样本分类问题上。
比如，HMM是描述两个时序序列联合分布 p(x,y) 的概率模型。
- x 序列外界可见(外界指的是观测者)，称为**观测序列**(obsevation sequence);
- y 序列外界不可见，称为**状态序列**(state sequence)。
比如观测 x 为单词，状态 y 为词性，我们需要根据单词序列去猜测它们的词性。
一个马尔科夫过程是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为n阶马尔科夫模型，其中n是影响下一个状态选择的（前）n个状态。最简单的马尔科夫过程是一阶模型，它的状态选择仅与前一个状态有关。这里要注意它与确定性系统并不相同，因为下一个状态的选择由相应的概率决定，并不是确定性的。
隐马尔可夫模型之所以称为“隐”，是因为从外界来看，状 态序列(例如词性)隐藏不可见，是待求的因变量。从这个角度来讲，人们也称 y 状态为隐状态(hidden state),而称观测 x 为显状态( visible state)。
“隐”指的是其中某一阶的信息我们不知道，就像是我们知道人的祖先是三叶虫，但是由三叶虫经历了怎样的演变过程才演变到人的样子我们是不知道的，我们只能通过化石资料了解分布信息，如果这类资料很多，那么就可以利用隐马尔可夫模型来建模，因为缺少的信息较多，所以这一模型的算法比较复杂。
状态与观测之间的依赖关系确定之后，隐马尔可夫模型利用三个要素来模拟时序序列的发生过程----即**初始状态概率向量、状态转移概率矩阵和发射概率矩阵**。
### 1. 隐马尔可夫三大问题
- **概率计算问题**：给定模型，如何有效计算产生观测序列的概率？换言之，如何评估模型与观测序列之间的匹配程度？
- **预测问题**：给定模型和观测序列，如何找到与此观测序列最匹配的状态序列？换言之，如何根据观测序列推断出隐藏的模型状态？
- **学习问题**：给定观测序列，如何调整模型参数使得该序列出现的概率最大？换言之，如何训练模型使其能最好地描述观测数据？
前两个问题是模式识别的问题：1) 根据隐马尔科夫模型得到一个可观察状态序列的概率(**评价**)，被用来测量一个模型的相对适用性；2) 找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大(**解码**)，即用来推测模型隐藏的部分在做什么（“到底发生了”什么）。第三个问题就是根据一个可以观察到的状态序列集产生一个隐马尔科夫模型（**学习**）。
第二个问题是隐马尔可夫模型的核心，很多领域对隐马尔可夫模型的应用大部分会是问题(2)，比如在机器翻译做中文对英文的翻译时，单词的翻译总是有很多个意思，而词性往往起到很重要的作用，乍一看词性这一序列怎么跟我们说到的隐含的状态序列=()很像呢！类似这样的还有很多.......
对应的三大问题解法：
1. 向前算法(Forward Algorithm)、向后算法(Backward Algorithm)
2. 维特比算法(Viterbi Algorithm)
3. 鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法)
网上经典例子
> 小明现在有三天的假期，他为了打发时间，可以在每一天中选择三件事情来做，这三件事情分别是散步、购物、打扫卫生(**对应着可观测序列**)，可是在生活中我们所做的决定一般都受到天气的影响，可能晴天的时候想要去购物或者散步，可能下雨天的时候不想出门，留在家里打扫卫生。而天气(晴天、下雨天)就属于隐藏状态，
>
> 那么，我们提出三个问题，分别对应马尔可夫的三大问题：
>
> 1. 已知整个模型，我观测到连续三天做的事情是：散步，购物，收拾。那么，根据模型，计算产生这些行为的概率是多少。
> 2. 同样知晓这个模型，同样是这三件事，我想猜，这三天的天气是怎么样的。
> 3. 最复杂的，我只知道这三天做了这三件事儿，而其他什么信息都没有。我得建立一个模型，晴雨转换概率，第一天天气情况的概率分布，根据天气情况选择做某事的概率分布。
### 2. 隐马尔可夫的难点/建模
其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，如何应用算法去估计这些缺失的信息，就成了一个很重要的问题。这些东西就是HMM要解决的问题。
观察到的状态序列与隐藏过程有一定的概率关系。我们使用隐马尔科夫模型对这样的过程建模，这个模型包含了一个底层隐藏的随时间改变的马尔科夫过程，以及一个与隐藏状态某种程度相关的可观察到的状态集合。
我们使用一个隐马尔科夫模型（HMM）对这些例子建模。这个模型包含两组状态集合和三组概率集合：
- 隐藏状态：一个系统的（真实）状态，可以由一个马尔科夫过程进行描述。
- 观察状态：在这个过程中‘可视’的状态。
- pi向量：包含了（隐）模型在时间t=1时一个特殊的隐藏状态的概率（初始概率）。
- 状态转移矩阵：包含了一个隐藏状态到另一个隐藏状态的概率
- 混淆矩阵：包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，观察到的某个观察状态的概率。
因此一个隐马尔科夫模型是在一个标准的马尔科夫过程中引入一组观察状态，以及其与隐藏状态间的一些概率关系。
## 0x06 水浒传中的隐马尔可夫应用
水浒传中，梁中书突围大名府就是个 **可以被改造以便于说明的** 隐马尔可夫（HMM）案例。
> 却说梁中书正在衙前醉了闲坐，初听报说，尚自不甚慌；次后没半个更次，流星探马，接连报来，吓得魂不附体，慌忙快叫备马。说言未了，只见翠云楼上，烈焰冲天，火光夺月，十分浩大。梁中书见了，急上得马，却待要去看时，只见两条大汉，推两辆车子，放在当路，便去取碗挂的灯来，望车子上点着，随即火起。梁中书要出东门时，两条大汉口称：“李应、史进在此！”手拈朴刀，大踏步杀来。把门官军，吓得走了，手边的伤了十数个。杜迁、宋万却好接着出来，四个合做一处，把住东门。梁中书见不是头势，带领随行伴当，飞奔南门。南门传说道：“一个胖大和尚，抡动铁禅杖；一个虎面行者，掣出双戒刀，发喊杀入城来。”梁中书回马，再到留守司前，只见解珍、解宝手拈钢叉，在那里东撞西撞；急待回州衙，不敢近前。王太守却好过来，刘唐、杨雄两条水火棍齐下，打得脑浆迸流，眼珠突出，死于街前。虞候押番，各逃残生去了。梁中书急急回马奔西门，只听得城隍庙里，火炮齐响，轰天震地。邹渊、邹润手拿竹竿，只顾就房檐下放起火来。南瓦子前，王矮虎、一丈青杀将来。孙新、顾大嫂身边掣出暗器，就那里协助。铜寺前，张青、孙二娘入去，爬上鳌山，放起火来。此时北京城内百姓黎民，一个个鼠撺狼奔，一家家神号鬼哭，四下里十数处火光亘天，四方不辨。
> 却说梁中书奔到西门，接着李成军马，急到南门城上，勒住马，在鼓楼上看时，只见城下兵马摆满，旗号上写道：“大将呼延灼。”火焰光中，抖擞精神，施逞骁勇；左有韩滔，右有彭玘，黄信在后，催动人马，雁翅一般横杀将来，随到门下。梁中书出不得城去，和李成躲在北门城下，望见火光明亮，军马不知其数，却是豹子头林冲，跃马横枪，左有马麟，右有邓飞，花荣在后，催动人马，飞奔将来。再转东门，一连火把丛中，只见没遮拦穆弘，左有杜兴，右有郑天寿，三筹步军好汉当先，手拈朴刀，引领一千余人，杀入城来。梁中书径奔南门，舍命夺路而走。吊桥边火把齐明，只见黑旋风李逵，左有李立，右有曹正。李逵浑身脱剥，咬定牙根，手双斧，从城濠里飞杀过来。李立、曹正，一齐俱到。李成当先，杀开条血路，奔出城来，护着梁中书便走。只见左手下杀声震响，火把丛中，军马无数，却是大刀关胜，拍动赤兔马，手舞青龙刀，径抢梁中书。李成手举双刀，前来迎敌。那
> 李成无心恋战，拨马便走。左有宣赞，右有郝思文，两肋里撞来。孙立在后，催动人马，并力杀来。正斗间，背后赶上小李广花荣，拈弓搭箭，射中李成副将，翻身落马。李成见了，飞马奔走，未及半箭之地，只见右手下锣鼓乱鸣，火光夺目，却是霹雳火秦明跃马舞棍，引着燕顺、欧鹏，背后杨志，又杀将来。李成且战且走，折军大半，护着梁中书，冲路走脱。
突围有四个选择：东南西北四门。每个门都有不同的梁山好汉。现在梁中书面对的梁山好汉就构成了一条人名链。
比如去南门，遇见武松，再去东门，遇见史进，再去北门，遇见林冲，再去西门，遇见宋江。 那么能得到如下一串好汉名字：武松，史进，林冲，宋江。
这串好汉名字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是梁中书选择门的序列: 南门，东门，北门，西门。
后续我们就围绕 ***梁中书*** 遇见以下各位好汉来说明： **武松，史进，林冲，宋江**
### 1. 状态转移矩阵
状态转移矩阵包含了一个隐藏状态到另一个隐藏状态的概率。一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（城门）之间存在转换概率（transition probability）。
比如，梁中书在西门突围失败之后，下一个状态是南门，东门，北门，西门的概率都是1/4。这样设定是为了容易说清楚。但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义规则如下：
```java
* 顺时针如下：东门 ----> 南门 ----> 西门 ----> 北门 ---> 东门 ---> ...
* 已经到达某门，再次选择此门的概率是1/8，比如 东门 ---> 东门 （不大可能再次原地突围）
* 已经到达某门，如果顺时针或者逆时针选择下一个门的概率是3/8, 比如 东门 ----> 南门 或者 东门 ----> 北门
* 已经到达某门，选择 正对门 的概率是1/8, 比如 东门 ----> 西门 （不大可能选择穿过大名府去对面城门突围）
```
状态转移矩阵如下：
$$
A=
\left\{
\begin{matrix}
\frac18 & \frac38 & \frac18 & \frac38\\
\frac38 & \frac18 & \frac38 & \frac18\\
\frac18 & \frac38 & \frac18 & \frac38\\
\frac38 & \frac18 & \frac38 & \frac18\\
\end{matrix}
\right\}
$$
### 2. 混淆矩阵
混淆矩阵：包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，观察到的某个观察状态的概率。即尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。
水浒传真实总结出的四个门对应的梁山好汉是：
```java
* 水浒传真实总结
* 南门: 武松，鲁智深，呼延灼，韩滔，彭杞，黄信，李逵，李立，曹正，关胜，宣赞，郝思文，孙立，秦明，燕顺、欧鹏，杨志。
* 东门：李应，史进，穆弘，杜兴，郑天寿
* 北门：林冲，马麟，邓飞，花荣
* 西门：梁山好汉大部军马。
* 真实中，北门遇见林冲的概率是1/4， 南门遇见武松的概率是1/17。
```
但这些是确定的概率，没法说明我们的HMM模型。
所以我们需要从梁中书/吴学究的角度改造。假设吴学究派兵部署时候，给每个好汉分配到每个门是有一定概率的，也就是说，梁中书在去了某门之后，遇到某一好汉是有一定概率的。
我们这里是简化版本，只给定几位好汉：**武松，史进，林冲，宋江**。
```java
* 以下为吴学究派兵时候，每个好汉分配到每个门的概率
* 南门：武松 1/2，史进 1/4，林冲 1/8，宋江 1/8
* 东门：武松 1/4，史进 1/2，林冲 1/8，宋江 1/8
* 北门：武松 1/8，史进 1/8，林冲 1/2，宋江 1/4
* 西门：武松 1/8，史进 1/8，林冲 1/4，宋江 1/2
* 就我们的例子来说，梁中书在北门 遇到武松的概率是1/8,遇见史进的概率是1/8，遇见林冲的概率是1/2，......
```
混淆矩阵如下：
$$
B =
\left\{
\begin{matrix}
\frac12 & \frac14 & \frac18 & \frac18\\
\frac14 & \frac12 & \frac18 & \frac18\\
\frac18 & \frac18 & \frac12 & \frac14\\
\frac18 & \frac18 & \frac14 & \frac12\\
\end{matrix}
\right\}
$$
在状态转移矩阵及混淆矩阵中的每一个概率都是时间无关的——也就是说，当系统演化时这些矩阵并不随时间改变。实际上，这是马尔科夫模型关于真实世界最不现实的一个假设。
### 3. pi向量（初始概率）
梁山大部军马在西门偷袭李成，梁中书去西门可能性甚小，去东门可能性最大
```java
* 南门: 1/4
* 东门：7/16
* 北门：1/4
* 西门：1/16
```
pi向量如下：
$$
pi=
\left\{
\begin{matrix}
\frac14 \\
\frac7{16} \\
\frac14 \\
\frac1{16} \\
\end{matrix}
\right\}
$$
## 0x07 水浒传HMM对应的三类问题
### 1. 序列概率过程 --- 估计(Evaluation)
**概率计算问题**：给定模型，如何有效计算产生观测序列的概率。即根据隐马尔科夫模型得到一个可观察状态序列的概率(**评价**)。
```java
结合我们水浒传的例子，就是已经知道门有几种（隐含状态数量），每种门是什么（转换概率），根据"选门之后看到哪位好汉"的结果（可见状态链），我想知道看到这个结果的概率。
比如连续三次，看到的人分别是：武松，史进，林冲。那么根据模型，计算产生这些行为的概率是多少。
```
#### 1.1 直接计算法(穷举搜索)
列举所有可能的状态序列，然后**计算每种状态序列情况下的观测序列概率，最后求和**。时间复杂度非常高，对于每一个t，都有N种隐藏状态，那整个序列T的所有可能就是N的T次方，然后求和又是T的所有复杂度。
#### 1.2 前向算法(基本动态规划思想)
我们使用前向算法（forward algorithm）来计算给定隐马尔科夫模型（HMM）后的一个观察序列的概率，并因此选择最合适的隐马尔科夫模型(HMM)。
这个算法采用了DP思想，减少计算量，即每一次直接引用前一个时刻的计算结果以避免重复计算，跟Viterbi一样的技巧相应地，其时间复杂度与T成线性关系。
给定一个隐马尔科夫模型（HMM），我们将考虑递归地计算一个观察序列的概率。我们首先定义局部概率（partial probability）,它是到达网格中的某个中间状态时的概率。对于最后的观察状态，其局部概率包括了通过所有可能的路径到达这些状态的概率。由此可见，对于这些最终局部概率求和等价于对于网格中所有可能的路径概率求和，也就求出了给定隐马尔科夫模型(HMM)后的观察序列概率。
**注：穷举搜索的时间复杂度是2TN^T，前向算法的时间复杂度是N^2T，其中T指的是观察序列长度，N指的是隐藏状态数目。**
### 2. 序列标注过程 --- 解码(Decoding)
**预测问题**：给定模型和观测序列，如何找到与此观测序列最匹配的状态序列？换言之，如何根据观测序列推断出隐藏的模型状态？对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列，我们常常希望能找到生成此序列最可能的隐藏状态序列。
```java
结合我们水浒传的例子就是，知道门有几种（隐含状态数量），每种门是什么（转换概率），根据"选门之后看到哪位好汉"的结果（可见状态链），我想知道每次选中的是哪个门（隐含状态链）。
比如连续三次，看到的人分别是：武松，史进，林冲。那么这三次每次选的是哪个门？
```
我现在要在给定的观测序列下找出一条隐状态序列，条件是这个隐状态序列的概率是最大的那个。
#### 2.1 Viterbi 算法
可以使用Viterbi 算法（Viterbi algorithm）确定（搜索）已知观察序列及HMM下最可能的隐藏状态序列。
维特比算法致力于寻找一条最佳路径，以便能最好地解释观测到的序列。我们可以通过列出所有可能的隐藏状态序列并且计算对于每个组合相应的观察序列的概率来找到最可能的隐藏状态序列。最可能的隐藏状态序列是使下面这个概率最大的组合：
Pr（观察序列|隐藏状态的组合）
这个思想的基础是这样的，如果从p1到pN存在一条最好的路是k，如果这条路k经过了p‘，则p’到pN一定是最优的，如果不是最优的，就存在另外一条路k‘，他的p’到pN更好，那这条路就不是k了，矛盾。所以我们只要找到最大概率的最后一个结点，然后一步一步向前就能求出来最优路径。
具体在应用中，维特比算法对于网格中的每一个单元(cell)都计算一个局部概率，同时包括一个反向指针用来指示最可能的到达该单元的路径。我们首先定义局部概率，它是到达网格中的某个特殊的中间状态时的概率。这些局部概率与前向算法中所计算的局部概率是不同的，因为它们表示的是时刻t时到达某个状态最可能的路径的概率，而不是所有路径概率的总和。当完成整个计算过程后，首先在终止时刻找到最可能的状态，然后通过反向指针（这个指针指向最优的引发当前状态的前一时刻的某个状态）回溯到t=1时刻，这样回溯路径上的状态序列就是最可能的隐藏状态序列了。
### 3. 学习问题(Learning)
**学习问题**：给定观测序列，如何调整模型参数使得该序列出现的概率最大？换言之，如何训练模型使其能最好地描述观测数据？即根据一个可以观察到的状态序列集产生一个隐马尔科夫模型（**学习**）。
```java
结合我们水浒传的例子就是，知道门有几种（隐含状态数量），不知道每种门是什么（转换概率），观测到很多次"选门之后看到哪位好汉"的结果（可见状态链），我想反推出每种门是什么（转换概率）。
比如连续三次，梁中书看到的人分别是：武松，史进，林冲。而其他什么信息都没有。要建立一个模型，找出各种门之间转换概率，当然也有这些门外他遇到好汉的概率分布。
```
很多时候我们只有可见结果，不知道HMM模型里的参数，我们需要从可见结果估计出这些参数，这是建模的一个必要步骤。
这个问题，也是与HMM相关的问题中最难的，根据一个观察序列（来自于已知的集合），以及与其有关的一个隐藏状态集，估计一个最合适的隐马尔科夫模型（HMM），也就是确定对已知序列描述的最合适的（pi,A,B）三元组。
#### 3.1 监督学习算法——频数/总数就是概率
首先监督学习算法，就是数据足够，然后人工标注好，其实你只需要统计出来各种频数就可以了。
比如分词的时候：
统计B到E的频数，B到M的频数什么的都能求出来，转移矩阵A有了。每个字分别为BEMS的频数，观测矩阵B有了
样本中第一个字为B和S分别的概率。初始概率PI有了。然后就解决问题了，其实分词就是这样的，在人工标注好的数据集上统计就好了。
#### 3.2 非监督学习算法——鲍姆-韦尔奇算法
没有标注的情况下，你只有一堆句子(假设句子长短一致，都是T个字)，这时候矩阵A和B不能够直接被（估计）测量，学习这些参数，就要用EM算法对于HMM参数学习问题的适配版——Baum-Welch算法。
**参数学习算法又叫前向后向算法**。要是计算整个序列的概率，前向就解决了。要是计算整个序列某个子序列出现的概率，那就必须要两者一起来算了。
## 0x08 参考代码
### UMDHMM（Hidden Markov Model Toolkit）：
Hidden Markov Model (HMM) Software: Implementation of Forward-Backward, Viterbi, and Baum-Welch algorithms.
这款属于轻量级的HMM版本。UMDHMM主页：http://www.kanungo.com/software/software.html
#### **前向算法程序（forward.c）**
```c
/* 函数参数说明：
*phmm：已知的HMM模型；T：观察符号序列长度；
*O：观察序列；**alpha：局部概率；*pprob：最终的观察概率
*/
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob) {
int i, j; /* 状态索引 */
int t; /* 时间索引 */
double sum; /*求局部概率时的中间值 */
/* 1. 初始化：计算t=1时刻所有状态的局部概率alpha： */
for (i = 1; i <= phmm->N; i++)
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
/* 2. 归纳：递归计算每个时间点，t=2，... ，T时的局部概率 */
for (t = 1; t < T; t++) {
for (j = 1; j <= phmm->N; j++) {
sum = 0.0;
for (i = 1; i <= phmm->N; i++)
sum += alpha[t][i]* (phmm->A[i][j]);
alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
}
}
/* 3. 终止：观察序列的概率等于T时刻所有局部概率之和*/
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += alpha[T][i];
}
```
#### **维特比算法程序（viterbi.c)**
```c
void Viterbi(HMM *phmm, int T, int *O, double **delta, int **psi,int *q, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
int maxvalind;
double maxval, val;
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++){
delta[1][i] = phmm->pi[i] * (phmm->B[i][O[1]]);
psi[1][i] = 0;
}
/* 2. Recursion */
for (t = 2; t <= T; t++) {
for (j = 1; j <= phmm->N; j++){
maxval = 0.0;
maxvalind = 1;
for (i = 1; i <= phmm->N; i++) {
val = delta[t-1][i]*(phmm->A[i][j]);
if (val > maxval){
maxval = val;
maxvalind = i;
}
}
delta[t][j] = maxval*(phmm->B[j][O[t]]);
psi[t][j] = maxvalind;
}
}
/* 3. Termination */
*pprob = 0.0;
q[T] = 1;
for (i = 1; i <= phmm->N; i++){
if (delta[T][i] > *pprob){
*pprob = delta[T][i];
q[T] = i;
}
}
/* 4. Path (state sequence) backtracking */
for (t = T - 1; t >= 1; t--)
q[t] = psi[t+1][q[t+1]];
}
```
## 0x09 参考
[[2] 如何用简单易懂的例子解释隐马尔可夫模型?[Online]](https://www.zhihu.com/question/20962240/answer/33438846)
[[3] ”相亲记“之从EM算法到Baum-Welch算法[Online]](https://blog.csdn.net/firparks/articlehttps://img.qb5200.com/download-x/details/54934112)
[Itenyh版-用HMM做中文分词一：序]([http://www.52nlp.cn/itenyh%E7%89%88-%E7%94%A8hmm%E5%81%9A%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D%E4%B8%80%EF%BC%9A%E5%BA%8F](http://www.52nlp.cn/itenyh版-用hmm做中文分词一：序))
[HMM学习最佳范例一：介绍](http://www.52nlp.cn/hmm-learn-best-practices-one-introduction)
[条件随机场的简单理解](https://blog.csdn.net/weixin_41911765/articlehttps://img.qb5200.com/download-x/details/82465697)
[HMM隐马尔可夫模型详解](https://blog.csdn.net/weixin_41911765/articlehttps://img.qb5200.com/download-x/details/81979773)
[**3.二元语法与中文分词.md**](https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/3.二元语法与中文分词.md)
[”相亲记“之从EM算法到Baum-Welch算法](https://blog.csdn.net/firparks/articlehttps://img.qb5200.com/download-x/details/54934112)
([https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/3.%E4%BA%8C%E5%85%83%E8%AF%AD%E6%B3%95%E4%B8%8E%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D.md](https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/3.二元语法与中文分词.md))
[https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/3.%E4%BA%8C%E5%85%83%E8%AF%AD%E6%B3%95%E4%B8%8E%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D.md](https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/3.二元语法与中文分词.md)
[如何轻松愉快地理解条件随机场（CRF）？](https://www.jianshu.com/p/55755fc649b1)
[一文读懂机器学习概率图模型](https://blog.csdn.net/weixin_40674835/articlehttps://img.qb5200.com/download-x/details/78782610)
[十五、一篇文章读懂拿了图灵奖和诺贝尔奖的概率图模型](https://blog.csdn.net/jiangjingxuan/articlehttps://img.qb5200.com/download-x/details/54729133)
[机器学习 —— 概率图模型（贝叶斯网络）](https://www.cnblogs.com/ironstark/p/5087081.html)
[贝叶斯网络，看完这篇我终于理解了(附代码)！](https://zhuanlan.zhihu.com/p/73415944)
[概率图模型理解](https://blog.csdn.net/isMarvellous/articlehttps://img.qb5200.com/download-x/details/78828566)
[概率图模型体系：HMM、MEMM、CRF](https://zhuanlan.zhihu.com/p/33397147)
[HMM算法学习——自己动手实现一个简单的HMM分词（java）](https://www.unclewang.info/learn/machine-learning/745/)
[HMM学习最佳范例六：维特比算法1](http://www.52nlp.cn/hmm-learn-best-practices-six-viterbi-algorithm-1)
[wiki上一个比较好的HMM例子](http://www.52nlp.cn/hmm-concrete-example-on-wiki)
[https://hunch.net/](https://hunch.net/)
[https://eps.leeds.ac.uk/computing](https://eps.leeds.ac.uk/computing)
加载全部内容