Home

gentlesnow

10 May 2019

【NLP基础任务】 1 中文分词

NLP中文分词方法分为两个类别：

  1. 基于词典分词算法
  2. 基于统计的机器学习方法

目前中文分词难点主要有三个：

  1. 分词标准
  2. 歧义
    • 组合型歧义
    • 交集型歧义
    • 真歧义
  3. 新词

如下部分分词工具，供参考：

  1. 中科院计算所NLPIR http://ictclas.nlpir.org/nlpir/
  2. ansj分词器 https://github.com/NLPchina/ansj_seg
  3. 哈工大的LTP https://github.com/HIT-SCIR/ltp
  4. 清华大学THULAC https://github.com/thunlp/THULAC
  5. 斯坦福分词器 https://nlp.stanford.edu/software/segmenter.shtml
  6. Hanlp分词器 https://github.com/hankcs/HanLP
  7. 结巴分词 https://github.com/yanyiwu/cppjieba
  8. KCWS分词器(字嵌入+Bi-LSTM+CRF) https://github.com/koth/kcws
  9. ZPar https://github.com/frcchang/zpar/releases
  10. IKAnalyzer https://github.com/wks/ik-analyzer

部分分词器的简单说明：

  1. 哈工大的分词器：主页上给过调用接口，每秒请求的次数有限制。
  2. 清华大学THULAC：目前已经有Java、Python和C++版本，并且代码开源。
  3. 斯坦福分词器：作为众多斯坦福自然语言处理中的一个包，目前最新版本3.7.0， Java实现的CRF算法。可以直接使用训练好的模型，也提供训练模型接口。
  4. Hanlp分词：求解的是最短路径。优点：开源、有人维护、可以解答。原始模型用的训练语料是人民日报的语料，当然如果你有足够的语料也可以自己训练。
  5. 结巴分词工具：基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)；采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合；对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法。
  6. 字嵌入+Bi-LSTM+CRF分词器：本质上是序列标注，这个分词器用人民日报的80万语料，据说按照字符正确率评估标准能达到97.5%的准确率，各位感兴趣可以去看看。
  7. ZPar分词器：新加坡科技设计大学开发的中文分词器，包括分词、词性标注和Parser，支持多语言，据说效果是公开的分词器中最好的，C++语言编写。

关于速度：

由于分词是基础组件，其性能也是关键的考量因素。 通常，分词速度跟系统的软硬件环境有相关外，还与词典的结构设计和算法复杂度相关。 比如我们之前跑过字嵌入+Bi-LSTM+CRF分词器，其速度相对较慢。 另外，开源项目 https://github.com/ysc/cws_evaluation 曾对多款分词器速度和效果进行过对比。

公开的分词数据集

测试数据集

  1. SIGHAN Bakeoff 2005 MSR,560KB http://sighan.cs.uchicago.edu/bakeoff2005/
  2. SIGHAN Bakeoff 2005 PKU, 510KB http://sighan.cs.uchicago.edu/bakeoff2005/
  3. 人民日报 2014, 65MB https://pan.baidu.com/s/1hq3KKXe

基于词典分词算法

也称字符串匹配分词算法。该算法是按照一定的策略将待匹配的字符串和一个已建立好的“充分大的”词典中的词进行匹配，若找到某个词条，则说明匹配成功，识别了该词。

常见的基于词典的分词算法分为：

  1. 正向最大匹配法
  2. 逆向最大匹配法
  3. 双向匹配分词法

基于词典的分词算法是应用最广泛、分词速度最快的。 很长一段时间内研究者都在对基于字符串匹配方法进行优化， 比如最大长度设定、字符串存储和查找方式以及对于词表的组织结构， 比如采用TRIE索引树、哈希索引等。 缺点是对歧义和未登录词处理不好。

ikanalyzer,paoding 等就是基于字符串匹配的分词。

最大匹配分词算法

最短路径分词算法首先将一句话中的所有词匹配出来，构成词图（有向无环图DAG）， 之后寻找从起始点到终点的最短路径作为最佳组合方式，引用《统计自然语言处理》中的图：

nlp-task-1-1

我们认为图中每个词的权重都是相等的，因此每条边的权重都为1。 在求解DAG图的最短路径问题时，总是要利用到一种性质： 即两点之间的最短路径也包含了路径上其他顶点间的最短路径。 比如S->A->B->E为S到E到最短路径，那S->A->B一定是S到B到最短路径， 否则会存在一点C使得d(S->C->B)<d(S->A->B)， 那S到E的最短路径也会变为S->C->B->E，这就与假设矛盾了。 利用上述的最优子结构性质，可以利用贪心算法或动态规划两种求解算法：

  1. 最短路径分词算法
  2. N-最短路径分词算法

基于Dijkstra算法求解最短路径。 该算法适用于所有带权有向图，求解源节点到其他所有节点的最短路径， 并可以求得全局最优解。 Dijkstra本质为贪心算法，在每一步走到当前路径最短的节点，递推地更新原节点到其他节点的距离。 针对当前问题，Dijkstra算法的计算结果为：“他／说／的／确实／在理“。 可见最短路径分词算法可以满足部分分词要求。 但当存在多条距离相同的最短路径时，Dijkstra只保存一条，对其他路径不公平，也缺乏理论依据。

N-最短路径分词是对Dijkstra算法的扩展，在每一步保存最短的N条路径， 并记录这些路径上当前节点的前驱，在最后求得最优解时回溯得到最短路径。 该方法的准确率优于Dijkstra算法，但在时间和空间复杂度上都更大。

基于n-gram model的分词算法

在前文的词图中，边的权重都为1。 而现实中却不一样，常用词的出现频率／概率肯定比罕见词要大。 因此可以将求解词图最短路径的问题转化为求解最大概率路径的问题， 即分词结果为“最有可能的词的组合“。计算词出现的概率，仅有词典是不够的，还需要有充足的语料。 因此分词任务已经从单纯的“算法”上升到了“建模”， 即利用统计学方法结合大数据挖掘，对“语言”进行建模。 语言模型的目的是构建一句话出现的概率p(s)， 根据条件概率公式我们知道： \(P(他说的的确有理) = P(他)p(说\|他)...p(理\|他说的的确有)\) 而要真正计算“他说的确实在理”出现的概率， 就必须计算出上述所有形如 $P(w_n|w_1, … w_{n-1}), n=1,…,6$ 的概率，计算量太过庞大， 因此我们使用二元语言模型。 如果只对词频进行统计，则为一元语言模型。 在实际应用中一般用三元语言模型。

MM算法

def mm_cut(self, sentence='', max_len=6):
    """
    使用正向最大匹配法划分词语
    :param sentence: str 待划分句子
    :param max_len: int 最大词长 默认为6
    :return: str-list 已分词的字符串列表
    """
    sentence = sentence.decode('utf-8')
    cur = 0  # 表示分词的位置
    sen_len = sentence.__len__()  # 句子的长度
    word_list = []  # 划分的结果
    while cur < sen_len:
        l = None
        for l in range(max_len, 0, -1):
            if sentence[cur: cur+l] in self.word_set:
                break
        word_list.append(sentence[cur: cur+l])
        cur += l
    return word_list

逆向最大匹配法

主要原理与正向最大匹配算法一致，只是切分方向相反，从文章的尾部开始匹配。

RMM算法

def rmm_cut(self, sentence='', max_len=6):
    """
    使用逆向最大匹配法划分词语
    :param sentence: str 待划分句子
    :param max_len: int 最大词长 默认为6
    :return: str-list 已分词的字符串列表
    """
    sentence = sentence.decode('utf-8')
    sen_len = sentence.__len__()  # 句子的长度
    cur = sen_len  # 表示分词的位置
    word_list = []  # 划分的结果
    while cur > 0:
        l = None
        if max_len > cur:
            max_len = cur
        for l in range(max_len, 0, -1):
            if sentence[cur-l: cur] in self.word_set:
                break
        word_list.insert(0, sentence[cur-l: cur])
        cur -= l
    return word_list

最大匹配算法的缺点：

  1. 无法细分
  2. 只能找到局部最优
  3. 效率低，依赖max_len
  4. 歧义，无法考虑语义

考虑语义的分词： 输入–>生产所有可能的分割–>选择其中最好的(使用一个工具来找最好的，language model语言模型)

Viterbi

维特比算法（英语：Viterbi algorithm）是一种动态规划算法。 它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列， 特别是在马尔可夫信息源上下文和隐马尔可夫模型中。

nlp-task-1-15

基于统计的机器学习方法

这类目前常用的是算法是

  1. 生成式模型分词算法
    • n-gram模型
    • HMM
    • 朴素贝叶斯
  2. 判别式模型分词算法
    • 感知机
    • SVM
    • CRF
    • 最大熵模型
  3. 神经网络分词算法
    • RNN/LSTM
    • BiLSTM+CRF

stanford、Hanlp分词工具是基于CRF算法。 以CRF为例，基本思路是对汉字进行标注训练， 不仅考虑了词语出现的频率，还考虑上下文，具备较好的学习能力， 因此其对歧义词和未登录词的识别都具有良好的效果。

这类分词算法能很好处理歧义和未登录词问题，效果比前一类效果好， 但是需要大量的人工标注数据，以及较慢的分词速度。

与基于词典的分词不同的是，基于字的分词事先不对句子进行词的匹配， 而是将分词看成序列标注问题， 把一个字标记成B(Begin), I(Inside), O(Outside), E(End), S(Single)。 因此也可以看成是每个字的分类问题，输入为每个字及其前后字所构成的特征，输出为分类标记。 对于分类问题，可以用统计机器学习或神经网络的方法求解。

统计机器学习方法通过一系列算法对问题进行抽象，进而得到模型，再用得到的模型去解决相似的问题。 也可以将模型看成一个函数，输入X，得到f(X)=Y。 另外，机器学习中一般将模型分为两类：生成式模型和判别式模型， 两者的本质区别在于X和Y的生成关系。 生成式模型以“输出Y按照一定的规律生成输入X”为假设对P(X,Y)联合概率进行建模； 判别式模型认为Y由X决定，直接对后验概率P(Y|X)进行建模。 两者各有利弊，生成模型对变量的关系描述更加清晰，而判别式模型容易建立和学习。

黄和赵(2007)接受《中文信息学报》委托，针对自20世纪末以来的中文分词的 机器学习方法做了十年回顾，发表了《中文分词十年回顾》一 文。该文的基本结论是中文分词的统计机器学习方法优于传统的规则方法，尤其在未登录词 （out-of-vocabulary words, OOV)即训练集之中未出现的词的识别上，具有无可比拟的优势。[6]

生成式模型分词算法

生成式模型主要有n-gram模型、HMM隐马尔可夫模型、朴素贝叶斯分类等。 在分词中应用比较多的是n-gram模型和HMM模型。 如果将2.1.3中的节点由词改成字，则可基于字的n-gram模型进行分词， 不过这种方法的效果没有基于词的效果要好。

HMM模型认为在解决序列标注问题时存在两种序列，一种是观测序列，即人们显性观察到的句子， 而序列标签是隐状态序列，即观测序列为X，隐状态序列是Y，因果关系为Y->X。 因此要得到标注结果Y，必须对X的概率、Y的概率、P(X|Y)进行计算，即建立P(X,Y)的概率分布模型。 例句的隐马尔科夫序列如下图：

nlp-task-1-2

HMM模型是常用的分词模型，基于Python的jieba分词器和基于Java的HanLP分词器都使用了HMM。要注意的是，该模型创建的概率图与上文中的DAG图并不同，因为节点具有观测概率，所以不能再用上文中的算法求解，而应该使用Viterbi算法求解最大概率的路径。

判别式模型分词算法

判别式模型主要有感知机、SVM支持向量机、CRF条件随机场、最大熵模型等。在分词中常用的有感知机模型和CRF模型：

平均感知机分词算法

感知机是一种简单的二分类线性模型，通过构造超平面， 将特征空间（输入空间）中的样本分为正负两类。 通过组合，感知机也可以处理多分类问题。 但由于每次迭代都会更新模型的所有权重，被误分类的样本会造成很大影响， 因此采用平均的方法，在处理完一部分样本后对更新的权重进行平均。

CRF分词算法

CRF可以看作一个无向图模型，对于给定的标注序列Y和观测序列X， 对条件概率P(Y|X)进行定义，而不是对联合概率建模。 CRF可以说是目前最常用的分词、词性标注和实体识别算法， 它对未登陆词有很好的识别能力，但开销较大。

神经网络分词算法

自从词嵌入（word embedding）表示达到了数值计算的实用化阶段之后，深度学习开始席卷自然语言 处理领域。原则上，嵌入向量承载了一部分字或词的句法和语义信息，应该能带来进一步的性能提升。[6]

中文分词任务中可用的特征仅限于滑动窗口内的n-gram特征。由此，虽然典型的深度学 习模型皆以降低特征工程代价的优势而著称，但是对于分词任务的特征工程压力的缓解却相当有限。因 而，期望神经分词模型带来进一步性能改进的方向在于：一，有效集成字或者词的嵌入式表示，充分利 用其中蕴含的有效句法和语义信息；二，将神经网络的学习能力有效地和已有的传统结构化建模方法结 合，如在经典的字位标注模型中用等价的相应网络结构进行置换。[6]

在NLP中，最常用的神经网络为循环神经网络（RNN，Recurrent Neural Network）， 它在处理变长输入和序列输入问题中有着巨大的优势。 LSTM为RNN变种的一种，在一定程度上解决了RNN在训练过程中梯度消失和梯度爆炸的问题。 双向（Bidirectional）循环神经网络分别从句子的开头和结尾开始对输入进行处理， 将上下文信息进行编码，提升预测效果。 目前对于序列标注任务，公认效果最好的模型是BiLSTM+CRF。 结构如图：

nlp-task-1-3

利用双向循环神经网络BiLSTM，相比于上述其它模型，可以更好的编码当前字等上下文信息， 并在最终增加CRF层，核心是用Viterbi算法进行解码， 以得到全局最优解，避免B,S,E这种标记结果的出现。

本文回顾中文分词在2007-2017十年间的技术进展，尤其是自深度学习渗透到自然语言处理以来的 主要工作。我们的基本结论是，中文分词的监督机器学习方法在从非神经网络方法到神经网络方法的 迁移中尚未展示出明显的技术优势。中文分词的机器学习模型的构建，依然需要平衡考虑已知词和未 登录词的识别问题。尽管迄今为止深度学习应用于中文分词尚未能全面超越传统的机器学习方法，我 们审慎推测，由于人工智能联结主义基础下的神经网络模型有潜力契合自然语言的内在结构分解方式， 从而有效建模，或能在不远将来展示新的技术进步成果。[6]

在序列标注任务（中文分词CWS，词性标注POS，命名实体识别NER等）中， 目前主流的深度学习框架是BiLSTM+CRF。 其中BiLSTM融合两组学习方向相反（一个按句子顺序，一个按句子逆序）的LSTM层， 能够在理论上实现当前词即包含历史信息、又包含未来信息，更有利于对当前词进行标注。 BiLSTM在时间上的展开图如下所示。

nlp-task-1-7

若输入句子由120个词组成，每个词由100维的词向量表示，则模型对应的输入是（120，100）， 经过BiLSTM后隐层向量变为T1（120，128），其中128为模型中BiLSTM的输出维度。 如果不使用CRF层，则可以在模型最后加上一个全连接层用于分类。 设分词任务的目标标签为B（Begin）、M（Middle）、E（End）、S（Single）， 则模型最终输出维度为（120，4）的向量。 对于每个词对应的4个浮点值，分别表示对应BMES的概率，最后取概率大的标签作为预测label。 通过大量的已标注数据和模型不断迭代优化，这种方式能够学习出不错的分词模型。

虽然依赖于神经网络强大的非线性拟合能力，理论上我们已经能够学习出不错的模型。 但是，上述模型只考虑了标签上的上下文信息。 对于序列标注任务来说，当前位置的标签L_t与前一个位置L_t-1、后一个位置L_t+1都有潜在的关系。

例如，“我/S 喜/B 欢/E 你/S”被标注为“我/S 喜/B 欢/B 你/S”， 由分词的标注规则可知，B标签后只能接M和E，因此上述模型利用这种标签之间的上下文信息。 因此，自然语言处理领域的学者们提出了在模型后接一层CRF层，用于在整个序列上学习最优的标签序列。 添加CRF层的模型如下图所示。

nlp-task-1-8

模型通过下述公式计算最优标注序列，A矩阵是标签转移概率，P矩阵是BiLSTM的预测结果。

nlp-task-1-9

模型训练的时候，对于每个序列 y 优化对数损失函数，调整矩阵A的值。

nlp-task-1-10

nlp-task-1-11

当模型训练完成，模型预测的时候，按如下公式寻找最优路径：

nlp-task-1-12

Y_x表示所有可能的序列集合，y*表示集合中使得Score函数最大的序列。

至此，我们已经大致了解BiLSTM-CRF的原理。 对于分词任务，当前词的标签基本上只与前几个和和几个词有关联。 BiLSTM在学习较长句子时，可能因为模型容量问题丢弃一些重要信息， 因此我在模型中加了一个CNN层，用于提取当前词的局部特征。 CNN用于文本分类的模型如下。

nlp-task-1-13

设句子输入维度为（120,100），经过等长卷积后得到T2（120，50），其中50为卷积核个数。 对于当前词对应的50维向量中，包含了其局部上下文信息。 我们将T1与T2拼接，得到T3（120,178），T3通过全连接层得到T4（120，4）, T4输入至CRF层，计算最终最优序列。 最终模型BiLSTM-CNN-CRF如下。

nlp-task-1-14

分词算法中的数据结构

词典

中文有7000多个常用字，56000多个常用词，要将这些数据加载到内存虽然容易， 但进行高并发毫秒级运算是困难的，这就需要设计巧妙的数据结构和存储方式。 前文提到的Trie树只可以在O(n)时间完成单模式匹配，识别出“的确”后到达Trie树对也节点， 句子指针接着指向“实”，再识别“实在”，而无法识别“确实”这个词。 如果要在O(n)时间完成多模式匹配，构建词图， 就需要用到Aho-Corasick算法将模式串预处理为有限状态自动机， 如模式串是he/she/his/hers，文本为“ushers”。 构建的自动机如图：

nlp-task-1-4

这样，在第一次到叶节点5时，下一步的匹配可以直接从节点2开始， 一次遍历就可以识别出所有的模式串。

对于数据结构的存储，一般可以用链表或者数组，两者在查找、插入和删除操作的复杂度上各有千秋。 在基于Java的高性能分词器HanLP中，作者使用双数组完成了Trie树和自动机的存储。

词图

图作为一种常见的数据结构，其存储方式一般有两种：

邻接矩阵

邻接矩阵用数组下标代表节点，值代表边的权重，即d[i][j]=v代表节点i和节点j间的边权重为v。 如下图：

nlp-task-1-5

用矩阵存储图的空间复杂度较高，在存储稀疏图时不建议使用。

邻接表

邻接表对图中的每个节点建立一个单链表，对于稀疏图可以极大地节省存储空间。 第i个单链表中的节点表示依附于顶点i的边，如下图：

nlp-task-1-6

在实际应用中，尤其是用Viterbi算法求解最优路径时， 由于是按照广度优先的策略对图进行遍历，最好是使用邻接表对图进行存储， 便于访问某个节点下的所有节点。

总结

分词作为NLP底层任务之一，既简单又重要，很多时候上层算法的错误都是由分词结果导致的。 因此，对于底层实现的算法工程师，不仅需要深入理解分词算法，更需要懂得如何高效地实现。 而对于上层应用的算法工程师，在实际分词时，需要根据业务场景有选择地应用上述算法， 比如在搜索引擎对大规模网页进行内容解析时，对分词对速度要求大于精度， 而在智能问答中由于句子较短，对分词的精度要求大于速度。

关于中文分词的机器学习方法，长期以来一直存在着“字还是词”的特征表示优越性之争，这恰好 和语言学界对于中文结构分析的“字本位”还是“词本位”的争议相映成趣。这一点早在黄和赵 (2006) 中就给出了经验性观察结果：字、词的特征学习需要在分词系统中均衡表达，才能获得最佳性能。实际 上，所谓字、词争议的核心对应于分词的两个指标，已知词（或词表词，即出现在切分训练语料中的词） 的识别精度和未登录词的识别精度，前者识别精度很高、相对容易但所占百分比高，后者识别精度很低、 难度较大但所占百分比较低。经验性的结果表明，强调基于字的特征及其表示会带来更好的未登录词的 识别性能。原因无他，未登录词从未在训练集出现，只能依赖于模型通过字的创造性组合才能识别。反 过来，强调词特征的系统，包括基于词的切分系统，对于未登录词的识别效果通常略为逊色。最佳的分 词系统总是需要合理考虑字表示和词表示的平衡问题。最近的两个工作的改进点可以辅证这一结论：Cai et al. (2017)对于Cai & Zhao (2016)的一个关键性改进，是词向量不再总是由字向量通过神经网络计算得 到，而是采取了两种策略，即低频或者未知词继续由字向量计算，而训练集中的高频词（可以认为是更 为稳定的已知词）则进行直接计算。当系统由后者偏向字向量表示的模式转向字-词均衡的表示模式以后， 确实带 来了额外的性能提升。[6]

最近5年，基于神经网络模型的分词学习已经取得了一系列成果。就目前的结果来看，我们可以得出 两个基本结论：一，神经分词所取得的性能效果仅与传统分词系统大体相当，如果不是稍逊一筹的话； 二，相当一部分的神经分词系统所报告的性能改进（我们谨慎推测）来自于经由字或词嵌入表示所额外 引入的外部语言资源信息，而非模型本身或字词嵌入表示方式所导致的性能改进。如果说词嵌入表示蕴 含着深层句法和语义信息的话，那么，这个结论似乎暗示一个推论，即分词学习是一个不需要太多句法 和语义信息即可良好完成的任务。[6]

现代深度学习意义下的神经网络归类于人工智能的联结主义思潮，由于其带有先天性的内在拓扑结 构，如果能克服其训练计算低效的弊病，它就应该是本身需要结构化学习的自然语言处理任务的理想建 模方式。这是我们在深度学习时代看到更多样化的结构建模方法用于中文分词任务的主要原因。如果我 们能有效平衡字-词表示的均衡性，不排除将来深度学习基础上的分词系统能有进一步的成长空间。[6]

参考资料：

  1. Python第三方库jieba（中文分词）入门与进阶（官方文档）
  2. Python自然语言处理实战
  3. 中文分词算法简介
  4. 竹间智能 Emotibot-有哪些比较好的中文分词方案？
  5. 知乎：李如
  6. 中文分词十年又回顾: 2007-2017*Chinese Word Segmentation: Another Decade Review (2007-2017)
  7. 使用keras实现的基于Bi-LSTM + CRF的中文分词+词性标注

Til next time,
gentlesnow at 16:10

scribble
‹ ›