隐马尔可夫模型求解中⽂分词实例（转）
什么问题⽤HMM解决
现实⽣活中有这样⼀类随机现象，在已知现在情况的条件下，未来时刻的情况只与现在有关，⽽与遥远的过去并⽆直接关系。
⽐如天⽓预测，如果我们知道“晴天，多云，⾬天”之间的转换概率，那么如果今天是晴天，我们就可以推断出明天是各种天⽓的概率，接着后天的天⽓可以由明天的进⾏计算。这类问题可以⽤ Markov 模型来描述：
进⼀步，如果我们并不知道今天的天⽓属于什么状况，我们只知道今明后三天的⽔藻的⼲燥湿润状态，因为⽔藻的状态和天⽓有关，我们想要通过⽔藻来推测这三天的真正的天⽓会是什么，这个时候就⽤ Hidden Markov 模型来描述：
HMM 模型的本质是从观察的参数中获取隐含的参数信息，并且前后之间的特征会存在部分的依赖影响。
我们从如何进⾏中⽂分词的⾓度来理解HMM
根据可观察状态的序列找到⼀个最可能的隐藏状态序列
中⽂分词，就是给⼀个汉语句⼦作为输⼊，以“BEMS”组成的序列串作为输出，然后再进⾏切词，进⽽得到输⼊句⼦的划分。其中，B代表该字是词语中的起始字，M代表是词语中的中间字，E代表是词语中的结束字，S则代表是单字成词。
饥不择食什么意思
例如：给个句⼦
⼩明硕⼠毕业于中国科学院计算所
得到BEMS组成的序列为
BEBEBMEBEBMEBES
因为句尾只可能是E或者S，所以得到切词⽅式为
BE/BE/BME/BE/BME/BE/S
进⽽得到中⽂句⼦的切词⽅式为
⼩明/硕⼠/毕业于/中国/科学院/计算/所
这是个HMM问题，因为你想要得到的是每个字的位置，但是看到的只是这些汉字，需要通过汉字来推出每个字在词语中的位置，并且每个字属于什么状态还和它之前的字有关。此时，我们需要根据可观察状态的序列找到⼀个最可能的隐藏状态序列。
如果你在就好了五元组，三类问题，两个假设
五元组
通过上⾯的例⼦，我们可以知道 HMM 有以下5个要素。
观测序列－O：⼩明硕⼠毕业于中国科学院计算所
状态序列－S：BEBEBMEBEBMEBES
初始状态概率向量－π：句⼦的第⼀个字属于{B,E,M,S}这四种状态的概率
状态转移概率矩阵－A：如果前⼀个字位置是B，那么后⼀个字位置为BEMS的概率各是多少
观测概率矩阵－B：在状态B的条件下，观察值为耀的概率，取对数后是-10.460
备注：⽰例数值是对概率值取对数之后的结果，为了将概率相乘的计算变成对数相加，其中-3.14e+100作为负⽆穷，也就是对应的概率值是0
三类问题
三国演义有感
当通过五元组中某些已知条件来求未知时，就得到HMM的三类问题：
似然度问题：参数(O，π，A，B)已知的情况下，求(π，A，B)下观测序列O出现的概率。(Forward-backward算法)
解码问题：参数(O，π，A，B)已知的情况下，求解状态值序列S。(viterbi算法)
学习问题：参数(O)已知的情况下，求解(π，A，B)。(Baum-Welch算法)
中⽂分词这个例⼦属于第⼆个问题，即解码问题。
我们希望找到 s_1,s_2,s_3,… 使 P (s_1,s_2,s_3,…|o_1,o_2,o_3…) 达到最⼤。
意思是，当我们观测到语⾳信号 o_1,o_2,o_3,… 时，我们要根据这组信号推测出发送的句⼦ s_1,s_2,s_3,…，显然，我们应该在所有可能的句⼦中找最有可能性的⼀个。
两个假设
紫薯粥怎么煮才能紫色
有限历史性假设: si 只由 si-1 决定
独⽴输出假设：第 i 时刻的接收信号 oi 只由发送信号 si 决定
有了上⾯的假设，就可以利⽤算法 Viterbi 找出⽬标概率的最⼤值。
Viterbi算法
根据动态规划原理，最优路径具有这样的特性：如果最优路径从结点 i_{t} 到终点 i_{T}，那么这两点之间的所有可能的部分路径必须是最优的。
依据这⼀原理，我们只需从时刻 t=1 开始，递推地计算在时刻 t 状态为 i 的各条部分路径的最⼤概率，直⾄得到时刻 t=T 状态为 i 的各条路径的最⼤概率 P，最优路径的终结点 i_{T} 也同时得到。之后，为了找出最优路径的各个结点，从终结点 i_{T} 开始，由后向前逐步求得结点 i_{T-1}…，i_{1}，进⽽得到最优路径 I＝i_{1}…，i_{T}，这就是维特⽐算法.
举个例⼦：
观测序列 O＝(红，⽩，红)，想要求状态序列S。
需要定义两个变量:
weight[3][3]，⾏3是状态数(1，2，3)，列3是观察值个数(红，⽩，红)。意思是，在时刻 t 状态为 i 的所有单个路径中的概率最⼤值。path[3][3]，意思是，在时刻 t 状态为 i 的所有单个路径中概率最⼤的那条路径，它的第 t-1 个结点是什么。⽐如 path[0][2]=1, 则代表weight[0][2] 取到最⼤时，前⼀个时刻的状态是 1.
1.初始化
t＝1 时的红，分别是在状态 1，2，3 的条件下观察得来的概率计算如下：
此时 path 的第⼀列全是 0.团结一致
2.递归
t＝2 时的⽩，如果此时是在 1 的条件下观察得来的话，先计算此时状态最可能是由前⼀时刻的哪个状态转换⽽来的，取这个最⼤值，再乘以 1 条件下观测到 ⽩ 的概率，同时记录 path矩阵：如下图 weight[0][1]=0.028，此值来源于前⼀时刻状态是3，所以，
3.终⽌
在 t＝3 时的最⼤概率 P＝0.0147，相应的最优路径的终点是 i_3=3.
4.回溯
伶俐的意思是什么
由最优路径的终点 3 开始，向前找到之前时刻的最优点：
在 t＝2 时，因 i_3=3，状态 3 的最⼤概率 P＝0.0147，来源于状态 3，所以 i_2=3.
在 t＝1 时，因 i_2=3，状态 3 的最⼤概率 P＝0.042，来源于状态 3，所以 i_1=3.
最后得到最优路径为 I*＝(i_{1}，i_{2}，i_{3})＝(3,3,3)
⽤Viterbi算法求解中⽂分词问题
根据上⾯讲的 HMM 和 Viterbi，接下来对中⽂分词这个问题，构造五元组并⽤算法进⾏求解。
InitStatus：π
TransProbMatrix：A
EmitProbMatrix：B
Viterbi求解
鼎最初的用途>菠萝炒鸡经过这个算法后，会得到两个矩阵 weight 和 path：
⼆维数组 weight[4][15]，4是状态数(0:B,1:E,2:M,3:S)，15是输⼊句⼦的字数。⽐如 weight[0][2] 代表 状态B的条件下，出现’硕’这个字的可能性。
⼆维数组 path[4][15]，4是状态数(0:B,1:E,2:M,3:S)，15是输⼊句⼦的字数。⽐如 path[0][2] 代表 weight[0][2]取到最⼤时，前⼀个字的状态，⽐如 path[0][2] = 1, 则代表 weight[0][2]取到最⼤时，前⼀个字(也就是明)的状态是E。记录前⼀个字的状态是为了使⽤viterbi算法计算完整个 weight[4][15] 之后，能对输⼊句⼦从右向左地回溯回来，找出对应的状态序列。
