今天茶话会，同事分享了HMM（隐马尔可夫模型）以及其在分词中的应用，觉得还蛮有意思，记下来防止后面忘了。

马尔可夫链

　　首先得了解下什么是马尔可夫链，随机过程中各个状态的S_t的概率分布只与它的前一个状态S_(t-1)有关，即：

1
P(S_t|S_1,S_2,...,S_(t-1)) = P(S_t|S_(t-1))

　　举个例子：

　　举个更具体的例子，假设天气状况就是一种状态，假设总共有:晴天、阴天、下雨三种天气状态，而每天的天气状况只与前一天的天气状况相关，例如，如果昨天晴天，那么今天晴天的概率为0.5，今天阴天的概率为0.3，今天下雨的概率为0.2，而不与前天或更早的时间的天气相关，则天气状况的出现就是一个马尔可夫链。

隐马尔可夫模型

定义: 马尔科夫链的一个扩展，任意时刻t的状态S_t是不可见的，所以观察者没法通过观察到一个状态序列S_1,S_2,…,S_t来推测转移概率等参数。但是，HMM在每个时刻𝑡会输出一个符号O_t，而且O_t跟S_t相关且仅跟S_t相关，即独立输出假设。（当然马尔可夫链的条件，当前状态只与上一个状态相关是前提）

　　这样说其实很抽象，不好理解，所以我们举个例子：

　　假设我们有三种骰子，一个四面骰，一个六面骰，一个八面骰，这就代表三个隐藏的状态，也就是上面说的不可见的状态，为什么叫隐藏的状态，因为我们假设每次掷一个骰子，但是我们并不知道掷的这个骰子是四面骰还是六面骰还是八面骰，因此这个状态是不可见的，但是掷出来的数字，我们是知道的，这个数字也就是所谓的在每个时刻t输出的一个符号，而且数字出现的概率跟你所使用的骰子相关，如果是4面骰，那么只可能掷出来1-4，且几率都是1/4，这就是所谓的O_t跟S_t相关且仅跟S_t相关。

　　那么，在有三种骰子的情况下，我们掷了5次骰子，我们能观察到的是每次掷出的数字，例如：4，2，1，6，7，但是我们并不知道每次掷的是哪个骰子，但是每次掷出骰子是哪个只跟上次掷出的骰子是哪个相关，这就是隐马尔可夫模型的例子。

　　下面，我们用公式来分析隐马尔可夫模型：

　　上面的公式还是挺好理解的吧

HMM五元组定义

　　(S,V,π,A,B)

• 隐藏状态S={S_1,S_2,…,S_n}
• 显示状态V={V_1,V_2,…,V_m}
• 初始状态概率π={π_i}; i∈S
• 状态转移概率A={a_ij}; i,j∈S
• 输出概率B={b_jk}; j∈S,k∈V

　　其中，S是隐藏状态集合（三种骰子），V是显示状态集合（掷出的数字，1-8），π是初始状态概率，即最初出现某个状态的概率（第一次掷骰子，掷出来四面骰、六面骰、八面骰的概率），A是状态转移概率，即上一个状态为S_t-1时，下一个状态为S_t的概率（上次掷了四面骰之后，下次掷四面骰的概率），B是输出概率，即在某一个状态下，出现显示状态k的概率（掷出了四面骰后，掷出的数字为1-8的概率），示例图如下：

HMM三个基本问题

• 给定一个模型和某个特定的输出序列，如何找出最可能产生这个输出的隐藏状态序列;

• 给定一个模型，如何计算某个特定的输出序列的概率；

• 给定足够的观测数据，如何估计隐含马尔科夫模型的参数;

　　第一个问题

　　从掷骰子出发来解释就是：

　　知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率，如果有三种骰子，那么转换概率都为1/3），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。

　　假设，我们现在有一个可见状态链，即掷出的数字序列为1，6，3,那么我想知道，最有可能掷出这种序列的隐藏状态序列，也就是每次掷的骰子是哪种。

　　一种简单的解法是暴利穷举法，我把每种可能的隐藏状态序列都列举出来，然后依次计算他们掷出这种可见状态序列的概率，例如，有一种可能是D6-D8-D8（第一次掷出来的六面骰，后两次掷出来的八面骰），那么这种情况的概率是：

1
P=P(D6)∗P(D6→1)∗P(D6→D8)∗P(D8→6)∗P(D8→D8)∗P(D8→3)

　　P(D6)代表第一次掷出六面骰的概率（初始状态概率，在这里为1/3），P(D6→1)代表六面骰下掷出1的概率(输出概率，这里为1/6)，P(D6→D8)代表上个状态为D6的情况下下一次掷出D8的概率（状态转移概率，这里为1/3）

　　穷举法虽然简单，但是效率太低，因此有一个比较著名的算法叫viterbi算法

　　以掷骰子为例，下面简述viterbi算法的基本过程：

　　首先我们计算第一次掷骰子掷的是D4、D6、D8各自的概率是多少,但其实我们并不是计算P(S1=D4)、P(S1=D6)、P(S1=D8)，因为我们已经观察到第一次掷出来的是1,所以我们其实要计算的是P(S1=D4|O1=1)、p(S1=D6|O1=1)、p(S1=D8|O1=1)，那么根据概率论公式：

1
2
3
4
5
6
7
8
P(S1=D4|O1=1) = P(S1=D4,O1=1)/P(O1=1) = P(S1=D4) * P(O1=1|S1=D4) / P(O1=1)
= (1/3 * 1/4) / 1 = 1/12

P(S1=D6|O1=1) = P(S1=D6,O1=1)/P(O1=1) = P(S1=D6) * P(O1=1|S1=D6) / P(O1=1)
= (1/3 * 1/6) / 1 = 1/18

P(S1=D8|O1=1) = P(S1=D8,O1=1)/P(O1=1) = P(S1=D8) * P(O1=1|S1=D8) / P(O1=1)
= (1/3 * 1/8) / 1 = 1/24

　　其中P(O1=1)我们将其视为1即可，因为这三个概率算出来都与之相关，在比较时，可以忽略，因此可以看成，掷出的是D4的概率为1/12,掷出的是D6的概率是1/16,掷出的是D8的概率是1/24.因此第一天最有可能的隐藏状态是D4

　　接着我们算第二次掷的最有可能的隐藏状态P(S2=D4)、P(S2=D6)、P(S2=D8)。我们知道第二次掷出来的是6，那么我们要计算的是P(S2=D4|O2=6)、P(S2=D6|O2=6)、P(S2=D8|O2=6)，根据概率论公式:

1
2
3
4
5
P(S2=D4|O2=6) = P(S2=D4,O2=6)/P(O2=6) = P(S2=D4) * P(O2=6|S2=D4) / P(O2=6) 
= max{P(S2=D4,S1=D4),P(S2=D4,S1=D6),P(S2=D4,S1=D8)} * P(O2=6|S2=D4) / P(O2=6)
= max{P(S1=D4)*P(S2=D4|S1=D4),P(S1=D6)*P(S2=D4|S1=D6),P(S1=D8)*P(S2=D4|S1=D8)} * P(O2=6|S2=D4) / P(O2=6)
= max{1/12 * 1/3 , 1/18 * 1/3 , 1/24 * 1/3} * 0 / P(O2=6)
= 0

　　同理，P(S2=D6|O2=6)、P(S2=D8|O2=6)也可以计算出来，这就是第二次掷出的是D4、D6、D8的概率。之所以用max{P(S2=D4,S1=D4),P(S2=D4,S1=D6),P(S2=D4,S1=D8)},是因为，只可能走一条路径，即S1只可能有一个状态，那么这里是用max取得最有可能的路径。

　　算出来P(S2=D4)、P(S2=D6)、P(S2=D8)后，再用相同的方法去计算P(S3=D4)、P(S3=D6)、P(S3=D8)，这样就能把最有可能的隐藏状态序列计算出来了。

　　关于viterbi算法，可以参考知乎的这个回答：https://www.zhihu.com/question/20136144

　　第二个问题

　　还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率。

　　要解决这个问题，我们就需要一步步地计算出，第一次掷D4、掷D6、掷D8的概率，然后根据前一次的概率计算出下一次掷出D4，D6，D8的概率，最后求和，求解过程如下图：

　　最后算出的概率就是0.03

　　第三个问题

　　求隐含状态转移概率和输出概率，也就是模型的训练。

　　从条件概率的定义出发：

1
2
P(O_t│S_t)=P(O_t,S_t)/P(S_t)
P(S_t│S_(t−1))=P(S_(t−1),S_t)/P(S_(t−1))

　　那我们如何计算上面的概率呢？如果我们样本足够多，我们可以基于统计的方法来得到：

　　人工标记足够多的话，知道经过状态S_t有多少次，记为#(S_t)，每次经过这个状态时，分别产生的输出O_t是什么，并且记下状态为S_t时产生O_t输出的次数： #(O_t,S_t)，就可以用两者的比值：

1
P(O_t│S_t) ≈ #(O_t,S_t) / #(S_t)

　　同理：

1
P(S_t│S_(t−1)) ≈ #(S_(t−1),S_t) / #(S_(t−1))

基于HMM的分词应用

　　分词五元组

• 隐藏状态集S={S(单字成词),B(词头),M(词中),E(词尾)}
• 观察序列V={V_1,V_2,…,V_k }每个V_i表示一个单字，k为单字总数
• 初始状态概率π={π_i},每个状态S_i于词库中的初始概率分布
• 状态转移概率A为一个n×n维的矩阵，这里n为4
• 输出概率B是一个n×k维观察概率分布矩阵，b_ij 表示当前观察状态为S_i时可观察单字为V_j的概率

　　目标：给每个词打上最有可能的词状态标注，根据词的状态标注切分字串。（单字成词切开，遇到词尾切开），于是问题就变成了对最大概率词状态序列的求解，这正是隐马尔可夫模型要解决的三个问题之一。我们可以利用viterbi算法来求解。

　　那么，可见用HMM来进行分词，最重要的是训练出HMM模型

　　已知条件

• 隐藏状态集合
• 输出状态集合

　　未知条件

• 初始状态概率
• 隐藏状态转移概率
• 隐藏状态到输出状态的输出概率

　　首先我们准备很多的句子，即训练集合，那么初始状态概率，我们需要统计所有句子的第一个字的隐藏状态，来获得初始状态概率。

　　而隐藏状态转移概率，也需要通过统计所有语料，计算前一个状态为S_t-1时，后一个状态为S_t的概率，同理隐藏状态到输出状态的输出概率也是需要通过统计所有语料，获得当状态为S_t时，输出为某个单字的概率是多少。

　　当然，HMM只是最简单的一种模型，通过上面的分词应用我们就可以看出来，这种分词算法完全没有考虑字与字之间的关系，所以肯定还有更多牛逼的模型等着我继续去学习，嗯！