基于语言模型的无监督分词

语言模型

如果只需要大规模语料来训练的无监督分词模型, 怎么切分, 应该是由语料来决定的. 只要足够多语料, 就可以告诉我们怎么分词. 这种不依赖词典以及之前已有的分词工具的新的分词方法, 在得到新的分词后, 与之前的词典进行对比, 就能够找到新词了.

语言模型是计算条件概率$p(w_n|w_1,w_2,\dots,w_{n-1})$的模型, 其中$w_1,w_2,\dots,w_{n-1}$是句子中前$n-1$个词/字, $w_n$是第$n$个词/字. 使用神经网络训练语言模型, 思路是: $p(w_n|w_1,w_2,\dots,w_{n-1})$是关于$w_1,w_2,\dots,w_{n-1}$的一个函数, 使用神经网络去拟合这个函数. 为了更好地拟合, 并且减少模型参数, 要将词/字嵌入到实数空间中, 用短向量来表示词语, 跟语言模型一起训练.

从这个角度看, 词向量只是语言模型的副产品.

无监督分词

分词问题转标注问题

从最大概率法出发, 如果一个长度为$l$的字符串表示为$s_1, s_2, \cdots, s_l$, 其最优的分词结果为$w_1, w_2, \cdots, w_m$, 那么它应该是所有切分中, 概率乘积$p(w_1)p(w_2) \cdots p(w_m)$最大的一个.

用贝叶斯公式, 将词的概率转化为字的组合概率:

$$p(w)=p(c_1)p(c_2|c_1)p(c_3|c_1 c_2) \cdots p(c_k|c_1 c_2 \dots c_{k-1})$$

其中$w$是一个词, $c_1,c_2,\cdots,c_k$是词$w$的第$1,2,\cdots,k$个字. $p(c_k|c_1 c_2 \cdots c_{k-1})$就是字的语言模型.

如果$k$很大, 即词很长, $p(c_k|c_1 c_2 \cdots c_{k-1})$还是不容易估算的. 但词的平均长度不大, 因此我们只需要使用n-gram语言模型就够了, 去$n$为4时效果就挺不错. 如果得到n-gram语言模型呢.

对于原字符串$s_1, s_2, \cdots, s_l$, 假设切分后的文本片段之间没有联系, 在概率上是独立的, 如果对每个位置进行切分, 它的路径概率为:

$$p(s_1)p(s_2)p(s_3) \cdots p(s_l)$$

如果$s_1, s_2$应该合并为一个词, 则路径概率为:

$$p(s_1 s_2)p(s_3) \cdots p(s_l)=p(s_1)p(s_2|s_1)p(s_3) \cdots p(s_l)$$

如果$s_1, s_2, s_3$应该合并为一个词, 则路径概率为:

$$p(s_1 s_2 s_3) \cdots p(s_l)=p(s_1)p(s_2|s_1)p(s_3|s_1 s_2) \cdots p(s_l)$$

可以看到, 每一种切分方式, 都对应着$l$个条件概率的相乘. 现在的目标变为从这些条件概率的相乘模式中, 找出结果最大的那个, 如果我们知道了最优的相乘模式, 就可以对应地写出分词结果来.

其实就是将分词转化为了标注问题. 如果基于字的语言模型取到4-gram, 那么它相当于做了如下的字标注:

• b: 单字词或者多字词的首字

• c: 多字词的第二字

• d: 多字词的第三字

• e: 多字词的其余部分

对于句子中的一个字$s_k$来说, 就有:

$$\begin{aligned}&p(b)=p(s_k)\\ &p(c)=p(s_k|s_{k-1})\\ &p(d)=p(s_k|s_{k-2} s_{k-1})\\ &p(e)=p(s_k|s_{k-3} s_{k-2} s_{k-1}) \end{aligned}$$

这就是将分词问题变成了一种字标注问题, 而每个标签的概率由语言模型给出. 而且, 显然b后面只能接b或者c, 类似地, 就得到非零的转移概率只有:

$$p(b|b),\,p(c|b),\,p(b|c),\,p(d|c),\,p(b|d),\,p(e|d),\,p(b|e),\,p(e|e)$$

这些转移概率的值, 决定了划分出来的是长词还是短词, 最后找最优路径, 依旧由Viterbi算法完成.

最优路径Viterbi算法

分词问题转化为序列标注问题, 问题也变成了寻找概率最大的标注路径, 即最优路径, 如对于北京欢迎你这句话, 最优路径为bcbcb, 对应的分词结果为[北京, 欢迎, 你].

进一步地, 最优路径的概率可以拆分为:

• 每个字对应的每个标签的概率, 这个概率的计算方法在上面提到, 可以看到就是由语言模型得到的

• 标签状态之间的转移概率, 这个转移概率是一组超参数, 可通过经验反复调参设定

将所有位置的标注概率与位置之间的状态转移概率乘在一起, 使用Viterbi算法优化路径搜索范围, 减小计算量. 选取计算得到的最大概率的路径, 再根据标签反推得到分词结果.

如何得到语言模型

上面提到的两个概率, 标签之间的转移概率是超参数, 是已知的. 至此, 问题就变成了语言模型的无监督训练了. 简单地可以只用传统的统计+平滑模型, 也可以用神经语言模型. 分词的效果, 取决于语言模型的质量.

实现

首先关注语言模型如何表达标签概率.

以传统的统计+平滑方法训练语言模型, 使用kenlm这个工具进行训练. 训练得到的模型, 输出是字符串的联合分布概率. 如输入算, 输出是单字概率P(算); 输入算 法, 输出的是P(算法), 而不是条件概率P(法|算). 因此, 为了获得条件概率值, 需要计算两次联合概率, 然后相除得到: P(法|算) = P(算法) / P(算).

对于神经网络类的语言模型, 单字的概率就是将这个字整理成正常的输入格式, 经过模型这个字输出的在字典空间中的概率分布. 对于多字情况, 神经网络输出的概率就是条件概率, 将多字输入, 每个字输出的概率都是基于它之前所有字的条件概率. 因此我们拿一个文本片段中最后一个字的输出的条件概率, 直接使用.

下面以kenlm工具得到的语言模型为例, 详解怎么使用语言模型和Viterbi算法分词.

首先, kenlm模型输出值是$log_{10}(p)$这种形式, 即取概率以10位底的对数, 这样将概率的乘除计算转换为了加减运算, 也解决了概率相乘导致的溢出问题.

接下来定义转移概率矩阵. 这部分根据经验, 以及当前语料的情况制定. 上面提到非零的转移概率只有$p(b|b),\,p(c|b),\,p(b|c),\,p(d|c),\,p(b|d),\,p(e|d),\,p(b|e),\,p(e|e)$, 因此定义:

trans = {'bb':1, 'bc':0.15, 'cb':1, 'cd':0.01, 'db':1, 'de':0.01, 'eb':1, 'ee':0.001}
trans = {i:log10(j) for i,j in trans.iteritems()}

这里注意以下几点:

• 定义完概率后, 需要取对数, 跟kenlm语言模型的输出形式保持一致

• 字典中没有涉及到的转移对, 对应的转移概率为0, 这一点可以在转移概率声明时不显式声明, 而是在计算整体概率时, 减去一个很大的值(对0取对数趋近于负无穷)

• 如果预期语料中的词平均长度较短, 可以降低两字转三字, 三字接更多字的概率

然后对于句子中的每个字, 计算b, c, d, e这四个标签的概率, 例如对于句子新词发现, 对于现这个字, 它为b, c, d, e这四个标签的概率分别为:

prob_b = model.score('现', bos=False, eos=False)
prob_c = model.score('发 现', bos=False, eos=False) - model.score('发', bos=False, eos=False)
prob_d = model.score('词 发 现', bos=False, eos=False) - model.score('词 发', bos=False, eos=False)
prob_e = model.score('新 词 发 现', bos=False, eos=False) - model.score('新 词 发', bos=False, eos=False)

遍历整个句子, 得到每个字标签概率的代码如下:

def cp(s):
    return (model.score(' '.join(s), bos=False, eos=False) - model.score(' '.join(s[:-1]), bos=False, eos=False)) or -100.0

nodes = [{
    'b':cp(s[i]),
    'c':cp(s[i-1:i+1]),
    'd':cp(s[i-2:i+1]),
    'e':cp(s[i-3:i+1])
} for i in range(len(s))]

注意函数cp中输出-100.0的情况, 对于句子中最前面的几个字, 由于字数不够, 是无法输出c, d, e标签的, 因此输出一个很大的负值.

解决了通过语言模型计算标签概率之后, 现在考虑Viterbi算法, 依次计算每个字作为结尾时, 4个标签对应的最大标注序列概率.

初始值为一个字典, 其中有4个key, value对, 代表句子中第一个字4个标签的概率:

{
  "b": -1.0,
  "c": -100.0,
  "d": -100.0,
  "e": -100.0
}

接下来要计算句子第二个字分别为4个标签的概率, 即?b, ?c, ?d, ?e的概率. 以?b为例, 分别计算第一个字分别为b, c, d, e这个标签时, 第二个字标签为b的概率. 这个概率包含3部分:

• 前面子序列, 最后一个字标记分别为b, c, d, e时的序列概率. 由Viterbi算法得到的到达中间某个状态(标签)的概率, 为到达中间某个状态最可能的一条路径的概率.

• 状态转移概率, 由前一个字的标签转移到当前字某标签的概率, 使用状态转移概率矩阵中的值

• 当前字对应标签的概率, 由语言模型得到

代码如下:

def viterbi(nodes):
    # 输入`nodes`是一个list, 其中的每个元素都是字典, 代表一个字, 且key都为b, c, d, e
    # 对应的value是字为这个标签的概率

    # 拿第一个字的标签概率进行初始化
    paths = nodes[0]

    # 从左向右按字迭代
    for l in range(1, len(nodes)):
        # 存储上一轮Viterbi得到的路径概率
        paths_ = paths

        # 存储加上这一个字后的新路径概率
        paths = {}

        # 遍历当前字对应的4个标签的概率, 计算以每个标签结尾的路径最大概率
        for i in nodes[l]:
            nows = {}
            # `paths_`中有4个pair, 每个`j`是一个路径, 4个pair代表4个路径, 对应的结尾
            # 标签分别为b, c, d, e, 代表到达中间某个状态最可能的一条路径的概率
            for j in paths_:
                # 取路径中最后一个标签, 以及当前字符的一个标签, 组合成一个长度为2的标签序列
                # 在状态转移矩阵`trans`寻找这个标签序列的转移概率
                # 如果状态转移概率矩阵后没有这个转移对, 说明这种转移不可行, 因此直接忽略
                if j[-1]+i in trans:
                    # 新路径的概率由三部分相乘得到, 由于对概率进行了对数转换, 因此将它们相加
                    # `paths_[j]`: 之前的路径概率
                    # `trans[j[-1]+i]`: 状态转移概率
                    # `nodes[l][i]`: 当前节点指定标签的概率
                    nows[j+i] = paths_[j] + nodes[l][i] + trans[j[-1]+i]
            # `nows`中存储的是字的标签为`i`时, 与之前的4个局部最优路径组成的新路径的概率
            # 从中选取最大的概率, 最为新的局部最优路径
            k = nows.values().index(max(nows.values()))
            # 将这个局部最优路径更新到状态字典中
            paths[nows.keys()[k]] = nows.values()[k]

    # 遍历完所有字后, 此时的状态字典为完整的4个路径, 选取概率值最大的路径返回
    return paths.keys()[paths.values().index(max(paths.values()))]

最后根据标签路径, 得到分词结果:

def mycut(s):
    nodes = [{'b':cp(s[i]), 'c':cp(s[i-1:i+1]), 'd':cp(s[i-2:i+1]), 'e':cp(s[i-3:i+1])} for i in range(len(s))]
    tags = viterbi(nodes)
    words = [s[0]]
    for i in range(1, len(s)):
        if tags[i] == 'b':
            words.append(s[i])
        else:
            words[-1] += s[i]
    return words

参考资料

• 【中文分词系列】 5. 基于语言模型的无监督分词