搜索引擎（二）

承接上文，我们谈到分词是搜索引擎的第一个环节，直接影响着后续的搜索改写、意图识别、实体识别以及搜索召回等的质量。

为此，本文从分词的意义出发，概述一下主流分词技术及目前较为成熟的分词算法包。

在对分词技术展开具体的描述之前，先让我们简单的聊一下分词的必要性和挑战。

以中文场景为例，不同的字在不同的上下文中所表达的意义截然不同，比如参考资料【1】中提到的：

“哈哈哈”和“哈士奇”中的【“哈”】含义截然不同，如果模型在训练过程中没有见过“哈士奇”，且按最小单元字的量级去处理时，可能就会把“哈士奇”错误的识别成一种欢快的气氛词，而非一种动物实体。

从特征的角度来理解，词序列会包含的部分实体、意图等信息，特征的信息量往往大于字序列。因此，好的分词可以给NLP模型提供质量更好的特征，从而使得搜索引擎对文本的理解可以从“字序列”升级为“词序列”。

与大部分印欧语言、日耳曼语 不同，中文词与词之间没有天然的语法空格和边界，在分词中更容易遇到挑战。

中文场景容易遇到的典型问题如下：

一词多义、和切词歧义是问题是中文下的常见的一个问题，如经典的 【武汉市长江大桥】 和 【无线电法国别研究】 案例。

前者可以毫无违和地切为 [武汉市 / 长江大桥] 和 [武汉市长 / 江大桥]，后者则可以切分为 [无线电/ 法国 / 别 / 研究] 和 [无线电法/ 国别/ 研究] 截然不同的词块。

未登录词，即out-of-vocabulary word 问题，指得是一些不在词库中的词，分词器没有见过在切分时就非常容易给出不合理的结果。

中文场景下的日新月异的网络词就是这个问题中的典型，比如“老六”、“卷王”、“栓Q”、“摆烂”等词。

规范问题某种层度上歧义类似，本质上由于中文语法的特殊性，词与词之间没有明确的边界，在切词时容易出现公说公有理婆说婆有理的情况，尽管在 1992 年国家颁布了《信息处理用现代词汉语分词规范》。

上文指明了分词的必要性和挑战，本章节就来聊聊业界有主流的分词技术都有哪些。

分词技术总的说了可以分为三大类，飞别对应着人工智能技术的三大脉络，即：

规则分词是最早、也是最为经典的一系列分词算法，其核心思想是基于词典 + greedy匹配 的方式切分出文本中的最长词块，主要包括 正向最长匹配FMM、逆向最长匹配RMM和双向最长匹配BMM三种。

正向最长匹配FMM，顾名思义，是从句子的开头 开始查找字典，每次找到以当前字开头的最长单词时，便得到一个对应切分词。

以经典示例 ”无线电法国别研究 “ 为例，基于FMM的切词可得：【无线电法 / 国别 / 研究】，得到了一个合理的分词结果。

了解完FMM，我们从RMM的命名上就容易知道，RMM切分的方向与FMM相反，是从句子的结尾反过来寻找每个字往前找的最大词块。

以示例 “在北京大学研究生命科学” 为例，基于RMM的切词方法可得到如下结果：【在 / 北京大学 / 研究 / 生命科学】

值得一提的是，在中文场景下，由于中国人说话一般比较含蓄，重要的内容一般会后置，因此RMM的切词准确率往往要高于FMM。

聊到这里，细心的同学或许已经发现了，如果 ”无线电法国别研究“按RMM的切分方法会得到 【无线电 / 法国 / 别 / 研究】 这一奇葩的结果；

同样的，“在北京大学研究生命科学” 按FMM切分 也会得到 【在 / 北京大学 / 研究生 / 命 / 科学】这一不符合语义理解的切分；

因此就有聪明的小伙伴就想着，能不能按FMM和RMM各切一遍，看看谁的更合理。

而这种思想便是BMM。

简单来说，BMM就是结合FMM和RMM两家之所长，来降低歧义词的分词错误率。一种比较常见的融合规则如下：

（1）同时执行正向和逆向最长匹配，若两者的词数不同，返回词数更少的那一个。

（2）如果相同，返回两者中单字（单个字成词）更少的结果 。

（3）当单字数也相同时，则优先返回逆向最长匹配的结果 。

小结：

了解完以FMM/RMM/BMM为代表的规则切词后，我们容易发现这类分词算法有着原理简单、效率高等优点，但同样也有这几个很致命的弱点：

在这样的背景下，基于统计机器学习的切词方法应运而生。

统计机器学习范式下有两类分词方法，分别是语言模型 和序列标注模型，这里我们先讲原理比较简单的语言模型N-gram。

语言模型的核心思想是：在各种切词集合中找出最合理的组合，即计算出分词概率最大路径。

公式化的来说，假设一个句子由若干词w组成：W=[w_0, w_1, w_2, ..., w_n, w_{n+1}]，此时该 W 的概率如下：

p(W) = p(w_0, w_1, w_2, ..., w_n, w_{n+1}) = p(w_1|w_0) * p(w_2|w_0w_1)*...*p(w_{n+1}|w_0w_1...w_n)=\prod_{t}^{n+1}p(w_t|w_0w_1...w_{t-1}) \\

不过，稍微了解概率统计的同学一眼就会发现，上述概率的求解成本极高，特别是在n较大的情况下，而且对于后几项联合概率的求解需要极为庞大的语料，才能计算出一个相对置信的结果。

因此，在实际计算中往往会引入马尔可夫假设来简化语言模型，即假设分词的当前状态只与前一项相关，从而退化成容易求出的2-gram。

此时有：

p(w_{t}|w_0w_1...w_{t-1})=p(w_{t}|w_{t-1}) \\

p(W) 的求解则可简化为：

p(W) = p(w_1|w_0) * p(w_2|w_1)*...*p(w_{n+1}|w_n)=\prod_{t}^{n+1}p(w_t|w_{t-1}) \\

最后，值得一提的是2-gram的计算，通常会采用非常经典的维特比算法进行计算优化。其中，维特比算法的原理可参考如下：

基于序列标注模型切词的思想 与语言模型截然不同，经典的做法是采样隐马尔科夫模型HMM和条件随机场CRF模型，将分词问题转为为序列标注（分类）问题。

HMM（hidden markov model）作为一个非常经典和常用的生成式模型，在前深度学习期间，被广泛的应用于语音识别、NLP和模型识别等领域。

不过HMM的定义和求解相对复杂，因此要梳理清楚HMM的算法原理其实并不简单，这里我们仅以分词为列，概述一下HMM的算法思想，细节部分后面再写文章剖析。

先引用下《统计学习方法》中HMM的定义：

emm，说实在的，HMM模型学了很多次，但每次看这个定义都觉得好绕，不像是在说人话。

看看再补充点context会如何。

好的，似乎更绕了 ，我们上个图来简化理解。

引用宝宝一天的状态简图。

假设一个刚出生的小宝宝 一天有两个状态【吃，睡】需要观察，她在每个状态下我们都可以观测到它的三个潜在行为【哭，没精神，找妈妈】。

作为一个合格的宝妈和奶爸，每天的任务就是：基于宝宝可观测的状态【哭，没精神，找妈妈】，来预测是让宝宝未知的状态 --> 吃奶还是哄她睡觉 。

套用到HMM当中就是，宝宝的状态序列为【吃，睡】，随机观测序列为【哭，没精神，找妈妈】，每个状态下都有着对应的转态转移概率和观测概率。

ok，到这里我们好像清晰了不少，我们来把上述流程公式化。

一个隐马尔科夫模型由三大要素组成，即 初始状态概率向量 \pi 、状态转移概率矩阵 A 和观测概率矩阵 B ，其中 \pi 和 A 决定状态序列， B 决定观测序列。

\lambda = （A, \ B,\ \pi） \\

可作为补充的公式定义有：

设 Q 为所有可能得状态集合， V 是所有可能得观测集合：

Q = \{q_1,q_2,...q_N\}, \ \ \ \ \ \ V=\{v_1,v_2,...,v_M\} \\ I 定义为长度为 T 的状态序列， O 定义为对应的观察序列：

I=\{i_1,i_2,...,i_T \} \ \ \ \ \ O=\{o_1, o_2, ..., o_T \} \\ 据此，我们以宝宝一天状态的例子描述清楚了HMM的算法原理，接下来我们就回到HMM分词的任务理解上。

在分词中，状态序列就是词块对应的标签，即B/M/E/S {B:begin, M:middle, E:end, S:single}，是基于HMM分词的终究预测目标，它的状态是不可见，是未知而需要求解的；

在分词场景中，观测序列就是字的序列集合，它是可见、可统计的。

此时，分词问题就转化为HMM的三大求解问题之一，即：

给定模型输入 \lambda = （A, \ B,\ \pi） 和观测序列 O=\{o_1, o_2, ..., o_T \} ，计算在模型 \lambda 下观察序列 O 出现的概率 P(O|\lambda) 。

已知观测序列 O=\{o_1, o_2, ..., o_T \} ，估计模型 \lambda = （A, \ B,\ \pi） 的参数，使得在该模型下观测序列概率 P(O|\lambda) 最大。（一般采用极大似然估计的方法预估参数）

也称解码问题。已知模型 \lambda = （A, \ B,\ \pi） 和观测序列 O=\{o_1, o_2, ..., o_T \} ，求给定观测序列条件概率 P(O|\lambda) 最大的状态序列 I=\{i_1,i_2,...,i_T \} 。即给定观测序列，求解最有可能的状态序列。

容易知道的是，当HMM分词器训练完后，切词问题就转变为HMM的预测问题，即解码问题。

举个 如下：

通过HMM分词器预测后，得到各个字位对应的状态标签：

依据此状态标签序列可切词如下：

对应的切词结果为：

讲到这里，HMM的算法原理和切词方法描述清楚了✌️！

条件随机是另一个经典的序列标注模型，与HMM不同的是，CRF是一种判别模型，相同的是，同作为统计机器学习派系的扛把子，CRF的算法原理同样容易让新手同学望而止步 。

不信的话，我们先上一个《统计学习方法》里CRF的定义：

同时，书中提到，在序列标注即分词场景下，主要采用的线性(linear chain)条件随机场，此时：

看完之后，不知道大家有没有一种，同君一席话，如听一席的话感觉。

不过，有句老话说的好，上帝的归上帝，凯撒的归凯撒，晦涩归晦涩，该理解的还是得理解。

CRF 公式化概述:

1.线性链条件随机场用于标注问题（分词）；

2.在条件概率模型 P(Y|X) 中， Y 是输出变量，表示的是标记序列，也即状态序列（参考HMM部分描述）， X 是输入变量，是需要标注的观测序列；

3.学习时（训练时），利用训练数据集通过极大似然估计或者正则化极大似然估计得到条件概率模型P(Y|X)；预测时，对于给定的输入序列 x ，求出条件概率 \hat{P}(y|x) 的最大输出序列 \hat{y} 。

上述概述进一步的阐述了CRF的核心思想是：训练 基于观测序列与状态序列的条件概率模型，在预测（分词时），预测词块的状态标签；

而关于条件随机场的训练问题，则转变为了条件概率模型 P(Y|X) 求解问题，参考文献资料【7】、【8】、【9】（强烈推荐阅读）可知，CRT的求解问题关键在于特征函数求解，即：

score(l|s)=\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_j f_j(s,i,l_i,l_{i-1}) \\ 其中：

可以看到上式中有两个求和，外层求和是求每一个特征函数 f_j 评分值的和，里层的求和是求句子中每个位置的单词的的特征值和。

而对上述分值计算做指数化和标准化，就可以得到序列 l 对应的概率值 p(l|s) ，也即上文定义中的条件概率模型 P(Y|X) :

p(Y|X)=p(l|s)=\frac{exp(score(l|s))} {\sum_{l'} exp[score(l'|s)]} = \frac{exp[\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_j f_j(s,i,l_i,l_{i-1})]} {\sum_{l'}exp[\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_j f_j(s,i,l{_i}^{'},l_{i-1}^{'})]} \\

看到这里大家可能已经发现，p(l|s)的定义与逻辑回归是异曲同工的。

事实上，条件随机场是逻辑回归的序列化版本。只不过逻辑回归是用于分类的对数线性模型，而条件随机场是用于序列化标注的对数线性模型。也正是因为这样，上文公式化概述提到的：条件概率模型P(Y|X)用极大似然估计求解变的更容易理解。

据此，我们简要的描述了CRF用于分词的原理。可以看到的是，在预测形式上CRF和HMM是类似的，都是基于观测序列计算状态序列（B/M/E/S {B:begin, M:middle, E:end, S:single}）。

当把时间线推移到2014和2017年左右，以LSTM（Long Short-Term Memory）和《Attention Is All You Need》中推出的Transformer为代表的神经网络 开始引爆整个NLP领域。时至今日LSTM与Transformer变种的深度学习网络框架，如GRU/BiLSTM/BERT，已然成为NLP的基础操作和显学。

好风凭借力，送我上晴天，基于LSTM和BERT的分词也是同样的道理。

BiLSTM + CRF是进入深度学习时代最常用的分词算法之一，从命名上我们就可以知道其是基于BiLSTM和CRF两种算法策略的结合体。

其中的CRF上文已经介绍过，不必多说。BiLSTM（Bidirectional LSTM）则是LSTM的知名变种之一，双向LSTM，不过在介绍BiLSTM之前，我们先简单概述一下LSTM的网络结构。

LSTM结构图如下：

了解LSTM原理的同学都知道，LSTM由记忆元、输入门、遗忘门和输出门组成。其中，

对应的公式如下：

\begin{split}\begin{aligned} \mathbf{I}_t &= \sigma(\mathbf{X}_t \mathbf{W}_{xi} + \mathbf{H}_{t-1} \mathbf{W}_{hi} + \mathbf{b}_i),\\ \mathbf{F}_t &= \sigma(\mathbf{X}_t \mathbf{W}_{xf} + \mathbf{H}_{t-1} \mathbf{W}_{hf} + \mathbf{b}_f),\\ \mathbf{O}_t &= \sigma(\mathbf{X}_t \mathbf{W}_{xo} + \mathbf{H}_{t-1} \mathbf{W}_{ho} + \mathbf{b}_o),\\ \tilde{\mathbf{C}}_t &= \text{tanh}(\mathbf{X}_t \mathbf{W}_{xc} + \mathbf{H}_{t-1} \mathbf{W}_{hc} + \mathbf{b}_c) \\ \mathbf{C}_t & = \mathbf{F}_t \odot \mathbf{C}_{t-1} + \mathbf{I}_t \odot \tilde{\mathbf{C}}_t \\ \mathbf{H}_t &= \mathbf{O}_t \odot \tanh(\mathbf{C}_t) \end{aligned}\end{split} \\

具体的公式不做描述和展开，需要的可以移步参考资料【11】，李师傅（李沐）那里有很容易理解的文档和课程；

而BiLSTM，Bidirectional LSTM，从命名我们就可以看出，其是一个双向的LSTM模型，如下图所示：

在模型结构上，BiLSTM同时使用了前向和后向的序列信息，即同时使用来自过去和未来的观测信息来预测当前的观测，使得BiLSTM在LSTM的基础上 同时具备了隐马尔可夫模型类似的前瞻能力。

OK，讲完BiLSTM的模型结果后，BiLSTM-CRF的模型结构就可以千呼万唤始出来了，如下：

简单的来说，使用BiLSTM+CRF模型架构实现分词任务（当然，NER任务也是一样的原理），大致分为两个阶段：首先是使用BiLSTM生成发射分数（标签向量），其次是基于发射分数使用CRF解码最优的标签路径。

具体的来说，BiLSTM层负责计算各个位置（各个词块）的标签向量，然后将这些标签向量当做发射分数传入CRF中。而CRF则会据此解码出一串标签序列，并且从所有的可能路径中，找到概率最大，效果最优的一条路径，也即分词的结果；

例如：

据此，BiLSTM-CRF的分词原因描述完毕。如果你对其中的发射概率，以及CRF的转移概率计算细节感兴趣的可移步参考资料【12】，百度paddle的资料，文档中描述的非常仔细和清晰。

当时间跨入2018年，以ELMo、BERT、XLNet、GPT为代表的大规模预训练模型 席卷了NLP的绝大部分领域。分词作为NLP任务中的序列标注问题，使用这类大规模模型自然有着同样的显著优越性。

但强归强，大规模预测模型的计算成本可不是每个场景都可以承受的住的。目前业界一种减少计算成本的方案是：将预训练模型中的分词知识，通过知识蒸馏（Knowledge Distillation）来迁移到小模型（比如LSTM、GRU）上。

不过关于ELMo、BERT、XLNet以及知识蒸馏的方法这里就不展开讲了，一方面这类模型的初衷都是在文本翻译、MLM(Masked Language Model)，NSP(Next Sentence Prediction)任务，另一方面要讲清楚这些模型也需要篇幅不小的文章，如果需要补充这方面的知识，推荐先快速阅读一下百度飞桨关于预训练系列模型的短文，然后同步搭配李沐的论文精读视频。

好的，聊完原理，可以名正言顺的进入愉快地调包环节了。对于一名资深调包侠而言，很多时候其实不怎么关心模型的算法原理，更多的是在关心算的准不准以及算的快不快。

目前市面上比较知名的算法包大概有以下几个：

Jieba

主页链接：GitHub - fxsjy/jieba: 结巴中文分词

jieba分词，笔者接触的第一个分词包，算法核心是基于字典 + 基于统计的最短路径切分，对与未登录词采用HMM算法，同时最近一期的更新内置了基于 百度飞桨的预训练模型+大规模蒸馏的前沿分词模型。

jieba分词有一个值得称道的优点是快。

HanLP

主页链接：https://github.com/hankcs/HanLP/tree/doc-zh

HanLP前几年非常火的《自然语言处理入门》作者开源的一系列算法库，除了分词之外，HanLP还可以处理词性标注、命名实体识别、句法分析等任务。其早期版本主打的是基于CRF切词，2.0版本后也基于深度学习算法开发升级版本。

Stanford CoreNLP

主页链接：GitHub - Lynten/stanford-corenlp: Python wrapper for Stanford CoreNLP.

Stanford CoreNLP 是斯坦福推出的一系列NLP算法包，分词任务下的核心算法是CRF，对比Jieba/HanLP 的优点是 可以支持多种语言，不足之处是分词速度较慢。

除此之外，THULAC（THU Lexical Analyzer for Chinese），PKUSeg和LTP 都是国内比较知名的公开分词工具，感兴趣的可以关注一下它们的主页。

THULAC 主页：https://github.com/thunlp/THULAC

PKUSeg主页：GitHub - lancopku/pkuseg-python: pkuseg多领域中文分词工具; The pkuseg toolkit for multi-domain Chinese word segmentation

LTP主页：GitHub - HIT-SCIR/ltp: Language Technology Platform

本文从切词的意义和挑战出发，概要式地描述了切词10余年发展期间的核心技术，即：基于规则切词、基于统计机器学习切词和基于深度学习模型切词。

可以看到的是，随着机器学习或者说NLP技术的发展，分词采用的算法在不断地改变。而理解这些原理是十分必要的，比如HMM/CRF/LSTM/BERT算法，后续的其它搜索任务会经常用到这些算法。

你可能感兴趣的文章推荐：