jieba 分词源代码研读(4)

在上一节中我们考察了结巴分词对于未登录词的分词方法,它使用了HMM模型和用来解码HMM的维特比算法。较之基于语料库打分的初步分词结果,例句:

'乔治马丁写冰与火之歌拖了好久'

分词情况变成了这样:

'乔治/马丁/写冰/与/火之歌/拖/了/好久'

比原来有改进,但改进幅度可以忽略不计。。。

下一步我们就要调试代码了,目前可以知道程序会把连续的单个的字收集起来组成字符串交由 finalseg 中的 cut 函数处理。而该函数把这个字符串 写冰与火之歌拖了 标注成了 BESBMESS, 而相对比较正确的标注方式应该是 SBMMMESS,那么在程序内部这两种标注方式计算得到的概率值相差多少呢?

这就要用到前向算法来计算了。前向概率就是用来计算在已知HMM模型的全部参数的前提下,判断某一个输出序列产生的概率,其本质仍是动态规划,层层递进。那么在某一时刻,HMM呈现某种输出状态的概率值是多少呢?

 

这个公式表示 λ 时刻输出为O的概率等于 λ 时 状态为Q输出为O的概率对状态Q的遍历求和,P(O,Q|λ )是一个联合概率,表示λ 时状态为Q且输出为O的概率,它等于

P(O,Q|λ)=P(λ)*E(O | Q)

E(O | Q)即发射概率已知,P(Q|λ)等于前一时刻所有状态概率对于转移概率的加权和,又因为前一时刻的输出已知(即概率为1),所以有P(Q | λ-1)=P(O,Q | λ-1)

所以有递推公式 P(O | λ)=( ΣP(O,Q|λ-1)*T(q->Q) ) * E(O | Q)

T(q->Q)表示从前一个状态q转移到Q的转移概率,其中(ΣP(O,Q|λ-1)*T(q->Q))即所谓前一时刻所有状态概率对于转移概率的加权和。

推荐一篇解释地更好的文章:http://www.cnblogs.com/tornadomeet/archive/2012/03/24/2415583.html

下面一段代码是我实现的前向算法,把它添加到 jieba 分词的 finalseg/__init__.py 文件中运行就能得到在jieba分词的HMM模型下产生“写冰与火之歌拖了”这句输出的概率值了。

def forward(obs, states):
    import math
    sos={}
    for i,sw in enumerate(obs):
        if i==0:
            for s in states:
                sos[s]=start_P[s]+emit_P[s].get(obs[i],MIN_FLOAT)
        else:
            buf=dict(sos)
            for s in states:
                em_p = emit_P[s].get(sw,MIN_FLOAT)
                sos[s]=math.log(sum([math.e**(buf[s0]+trans_P[s0].get(s,MIN_FLOAT)+em_p) for s0 in PrevStatus[s] ]))
        #print sos
    return math.log(sum([math.e**(sos[s]) for s in sos.keys()  if s not in ('B','M') ]))

print finalseg.forward(u'写冰与火之歌拖了',('B','M','E','S')) #结果是-60.7515239889

前向算法得到的是一个概率总和,如果我们想要得到具体某一条链路的概率应该怎么做呢?循着前向算法的思路,可以推导出:

P(O,Q|λ)=P(Q | λ)*P(O | Q,λ)=P(O,Q|λ-1)*E(O | Q)*T(q->Q )

下面这段代码就实现了这个公式计算出了特定的路径的概率值:

def pathprobability(obs, test_path):
    rs=0.0
    for i,sw in enumerate(obs):
        if i==0:
            rs += start_P[test_path[0]]+emit_P[test_path[0]].get(sw,MIN_FLOAT)
        else:
            s0 = test_path[i-1]
            s = test_path[i]
            em_p = emit_P[s].get(sw,MIN_FLOAT)
            tr_p = trans_P[s0][s]
            rs += tr_p+em_p
    return rs

total_val=finalseg.forward(u'写冰与火之歌拖了',('B','M','E','S'))
print total_val #-60.7515239889
viterbi_val=finalseg.pathprobability(u'写冰与火之歌拖了','BESBMESS')
print viterbi_val #-62.0665839518
right_val=finalseg.pathprobability(u'写冰与火之歌拖了','SBMMMESS')
print right_val #-66.1378460505


可以看到正确的分词路径的概率值比维特比算法解码得到的最优解差了4个指数级别,这个误差很大,那么应该怎么修正呢?当然最直接的方法就是在语料库里加上“冰与火之歌”这个词语,但是从HMM的角度有没有什么好办法呢?

原文地址:https://www.cnblogs.com/rav009/p/5131116.html