> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/zi-ran-yu-yan-chu-li/nlp-chang-jian-ren-wu/xin-ci-fa-xian/ji-yu-yu-yan-mo-xing-de-wu-jian-du-fen-ci.md).

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

## 语言模型

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

语言模型是计算条件概率$$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](https://github.com/kpu/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)$$, 因此定义:

```python
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这四个标签的概率分别为:

```python
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)
```

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

```python
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个标签的概率:

```javascript
{
  "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算法得到的到达中间某个状态(标签)的概率, 为到达中间某个状态最可能的一条路径的概率.
* 状态转移概率, 由前一个字的标签转移到当前字某标签的概率, 使用状态转移概率矩阵中的值
* 当前字对应标签的概率, 由语言模型得到

代码如下:

```python
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()))]
```

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

```python
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. 基于语言模型的无监督分词](https://kexue.fm/archives/3956)