中文分词－HMM模型

关于HMM模型的文章和资料有很多，各种公式推导看起来也是有点复杂。不过还是那句话，多看看～～～

模型介绍

隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。

摘自百科，有点抽象的。一般书上的介绍主要有5个元素。

StatusSet:隐含状态集
ObserveSet:观察状态集
InitProbMatrix:初始状态概率矩阵
TranProbMatrix:隐含状态转移概率矩阵
EmitProbMatrix:发射状态矩阵

HMM模型可以用来解决三种问题：

参数(StatusSet,TransProbMatrix,EmitRobMatrix,InitStatus)已知的情况下，求解观察值序列。(Forward-backward算法)
参数(ObservedSet,TransProbMatrix,EmitRobMatrix,InitStatus)已知的情况下，求解状态值序列。(viterbi算法)
参数(ObservedSet)已知的情况下，求解(TransProbMatrix,EmitRobMatrix,InitStatus)。(Baum-Welch算法)

第3种问题似乎很厉害的样子，知道一个参数可以求出3个。。知乎上有个例子，关于抓赌场老千，很形象。第2个问题，就是本文要介绍的，用来解决中文分词的问题。

关于HMM模型的一般原理介绍，可以看52nlp上的系列文章，很多，可以挑着看，再看后面的在中文分词应用。看不懂可以多看几遍。

5大元素在中文分词中的具体含义。

ObserveSet 首先我们拿到一段文本：

小明硕士毕业于中国科学院计算所

这就是观察值序列，也就是我们看到的。。。好直白P:

StatusSet

在说说隐含状态集，顾名思义就是我们看不出来的；这里的隐含状态指的是每个字的状态。那么每个字都有哪些状态。有词语的开头、词语的中间字、词尾、单个字，当然简单的分有开头、结尾；这里的隐含状态集有4个状态对应的英文字母

{B,M,E,S}

显然这是我们要求解的。输入

小明硕士毕业于中国科学院计算所

输出

BEBEBMEBEBMEBES

根据这个来切分

BE/BE/BME/BE/BME/BE/S

也就是

小明/硕士/毕业于/中国/科学院/计算/所

这里的4个状态之间的关系，不是两两任意组合的，比如B后面只能是M E，M 后面只能是 M E ，BS 这样是不存在的。

这就是输入，输出的过程，很简单，不过具体中间过程是什么样的，这里我们只是讲到了5个元素中的2个。下面再看看另外3个元素是怎么使用的。

InitStatusSet

初始状态概率分布

B -0.57746333344078771

M -inf

E -inf

S -0.82398607534977875

也就是句子中第1个字是{B,M,E,S}的概率，显然句子开头只能是B，词语的开头或者S，单个字。这里概率取了对数,也可以自己直接给个默认值，比如都是0.5，我们认为2种可能性一样；当然也可以自己统计下现有的文本，看看具体的概率是什么样的。

TransProbMatrix

隐含状态转移矩阵，也就是4个状态之间的转移概率，BMES*BMES,4*4的矩阵。

   B        M        E        S
B -inf    -1.8750  -0.1664  -inf
M -inf    -0.7227  -0.6644  -inf
E -0.6378 -inf     -inf     -0.7517
S -0.5051 -inf     -inf     -0.9248

这里的概率取了对数值，有一些负无穷的值是表示不可能的状态，比如M 后面不可能是B。

EmitProbMatrix

发射状态概率矩阵

   你        好        小        明   ...
B -0.6378  -1.8750  -6.2217   -inf
M -0.6378  -0.7227  -5.0638   -inf
E -0.6378 -0.6378   -8.2379   -0.7517
S -0.5051 -0.6378   -6.3409   -0.9248

这里的矩阵的横向是中文字，假如有5000个常用字，那么这个矩阵就是4*5000维。通常这个矩阵很稀疏，而且也不能保证所有的字都在这个矩阵里，所以一般是采用4个map来存储，如果map里不存在，那么给个很小的值，表示概率很低。

具体值的含义是P(Observed[i]|Status[j])==P(你|B)

ok,全部的5个元素介绍完了，那么理论上假如我有了这些参数值(现成的参数模型)，就可以拿来作分词了。分词属于前面提到的HMM用来解决的第2类问题，需要用Viterbi算法来求解。

HMM－Viterbi算法

再次拿出待切分文本

小明硕士毕业于中国科学院计算所

对于这个15个字长度的文本，每个字有{B,M,E,S}4种状态。说白了，我们想要的就是，概率最大的一个BMES...组合，如果枚举一下，那么有4^15次方，显然我们不能让机器太累，毕竟地球变暖，人人有责~~P:.

那么我们可以这样，先确定第一个字

由InitStatusSet

初始状态概率分布

B -0.57746333344078771

M -inf

E -inf

S -0.82398607534977875

和 EmitProbMatrix

Status[B] -> Observed[小]: -6.2217

Status[M] -> Observed[小]: -5.0638

Status[E] -> Observed[小]: -8.2379

Status[S] -> Observed[小]: -6.3409

weight[B,小]=－0.5774+ -6.2217=-6.7991

weight[M,小]=-inf+ -5.0638= -inf

weight[E,小]=-inf+ -8.2379= -inf

weight[S,小]=-0.8239+-6.3409= -7.1648

这里小有4种情况，已经计算好了；

这里明也有4种情况，那么如何计算呢？

明的隐状态概率和前面一个字相关，这也就是HMM的重大假设:当前T=i时刻的状态Status(i)，只和T=i时刻之前的n个状态有关。

这里简单处理就是，每个字符的状态只和前一个状态相关，构建一个2-gram(bigram)语言模型，也就是一个1阶HMM。当然这种假设是不切实际的，也是hmm的缺陷的地方，这里不作讨论。

那么明的状态依赖于小的状态，那么就有4x4种情况，取最大的概率。整个过程计算下来，大概是4x4x15次计算，比起枚举的4^15次，大大减少计算量了。

关于Viterbi算法的具体公式推导可以看52nlp上相关的系列文章。

Viterbi算法代码实现

变量解释

weight[4][15]表示，4种状态下的概率，15个字。

weight[0][1]表示明，在状态B下，出现的概率。

path[4][15]表示，4种状态下前一个字的状态，15个字。对于每个字我们都在求4种状态下的最大概率，那么相对应的就有前一个字的状态； path[0][1]表示：在weight[0][1]取最大概率时，前面一个字的状态，比如path[0][1]=0，表示小的状态是B. 这个path用法好巧妙，通过记录前面一个字的状态，最后计算完整个weight数组，回溯回来，就得到整个结果。

//维特比算法
void Viterbe(std::vector<uint32_t>& words, std::vector<size_t>& ret)
{
    std::vector< vector<double> > weight = std::vector< vector<double> >(4,vector<double>(words.size(),0));
    std::vector< vector<int> > path = std::vector< vector<int> >(4,vector<int>(words.size(),0));
    
    //计算第1个字的概率
    for (int i=0; i<4; i++) {
        weight[i][0] =Init_Status[i]+ GetEmitProb(*(vec_Emit_map[i]),words[0]);
    }
    
    for (int i=1; i<words.size(); i++) {
        for (int j=0; j<4; j++) {
            weight[j][i] = -INT64_MAX;
            path[j][i]=3;
            for (int k=0; k<4; k++) {
                //前面一个字的状态概率＋状态转移概率＋发射矩阵概率
                //因为取对数 所以 ＋
                double tmp = weight[k][i-1]+TransProbMatrix[k][j]+GetEmitProb(*(vec_Emit_map[j]),words[i]);
                if (tmp>weight[j][i]) {
                    weight[j][i]=tmp;
                    path[j][i]=k;
                }
            }
        }
    }
    
    //计算完整个weight 最后一个字要么是 E 要么 S，比较一下 就可以确定。
    double endE,endS;
    endE = weight[2][words.size()-1];
    endS = weight[3][words.size()-1];
    int inx=-1;
    if (endE>endS)
        inx = 2;
    else
        inx = 3;
    ret.resize(words.size());
    
    //利用最后一个字的状态来回溯整个状态路径，很巧妙的运用了path数组
    for (int i=words.size()-1; i>=0; i--) {
        ret[i]=inx;
        inx = path[inx][i];
    }
}