nlp推荐算法,nlp新技术研究

NLP下级任务----分词算法概要NLP的下级任务从难到难依次为3358www.Sina.com/、词法分析、句法分析和3358 www.com语义分析(也包括词性标注和命名实体识别)中最基本的任务可以说是简单而复杂的。

说简单是因为分词算法的研究已经成熟，大部分精度可以达到95%以上。 说复杂是因为剩下的5%很难突破。 主要从三个方面来说：

粒度根据APP不同对粒度的要求也不同。 例如，“苹果手机”既是一个词也是两个词的歧义。 比如“雨天留人留天我不留下”的未录入语，比如“skrrr”、“打call”等新词，但在实际APP中，由于这些难点，分词效果较差，会影响后续任务对于追求算法表达的童鞋，不仅要了解分词是词法分析，还要了解这些基础技术，在真正工业水平的应用中具有调整分词器的能力。

它介绍了常用的调分词包(不仅包括机器学习和神经网络，还包括动态规划等)及其中心思想。

分词算法为分词算法其分词算法主要为核心思想

第一，根据词典的分词，先把句子按照词典切成单词，然后寻找单词的最佳组合方式；

二是根据词的分词，即词构词，将句子分成一个词，然后合成词群，寻找最佳切分策略，同时可以转化为序列标注问题。

毕竟，上述两种方法都可以归结为在图表或概率图上寻找最短路径的问题。 其次，以“分为两种”一词为例，分别说明不同分词算法的核心思想。

一、基于词典的分词1 .最大匹配分词算法他说的确实在理寻找最佳组合的方法是组合匹配的最长词。 的主要思想为最大匹配分词，也称为先将词典构造成一棵Trie树，如下图所示。

树由单词的公共前缀组成节点，在减少存储空间的同时提高搜索效率。 最大匹配分词使句子与Trie树匹配，并在与根节点匹配时从下一个单词开始重新开始搜索。 例如，如果将“他说的确实有道理”正向(从左向右)匹配，就会得到“他/说/确实/真实/理”的结果。 如果进行反方向最大匹配，则为“其他/说/的/确实/在理”。

这样，词典分词可以在o(n )时间对句子进行分词，但效果很差，实际上几乎没有使用这种方法。

2 .最短路径分词算法最短路径分词算法首先匹配一句中的所有词，组成词图(有向图DAG )，然后以寻找从起点到终点的最短路径为最优组合方式，引用《统计自然语言处理》图。

因为认为图中各词的权重相等，所以各边的权重为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。 这与假设相矛盾。 利用上述最佳子结构性质，可以利用贪婪算法或动态规划两种求解算法：

基于33558www.Sina.com/Dijkstra算法求解最短路径。 该算法应用于所有加权有向图，可求解从源节点到所有其他节点的最短路径，进而求得全局最优解。 戴克斯特拉本质上是贪婪算法，每一步去当前路径最短的节点，递归更新从原节点到其他节点的距离。 针对目前的问题，Dijkstra算法的计算结果是“其他/说/的/确实/在理”。 可见最短路径分词算法可以满足部分分词的要求。 但是，存在多个距离相同的最短路径时，Dijkstra只保存1条，对其他路径不公平，也缺乏理论依据。

字典树N-最短路径分词是对Dijkstra算法的扩展，每一步保存最短的n条路径，记录这些路径上当前节点的前驱，最后求解最优解时得到最短路径。 该方法的精度优于Dijkstra算法，但在时间和空间上都很复杂。

在基于n-gram model的分词算法前文的单词图中，边的权重都是1。 虽然在现实中是不同的，但常用词的出现频率/概率肯定比罕见词更大。 因此，求单词图最短路径的问题可以转换为求最大概率路径的问题，即分词结果为“最可能的单词组合”。 要计算单词出现的概率，仅有词典是不够的，还需要足够的词汇。 因此分词任务从单纯的“算法”上升到了“建模”，即运用统计学方法结合大数据挖掘对“语言”进行建模的“建模”。

语言模型的目的是构建一句话出现的概率p(s )，从条件概率公式中可以看出以下内容。

另一方面，要真正计算“他说的是肯定的”出现的概率，上述所有形式都必须计算n=1，…，6这样的概率，计算量太庞大，我们来近似考虑一下。

其中wi是字或单词。 我们把上述模型做成二元语言模型(2-g )

我们将基于词的语言模型所统计出的概率分布应用到词图中，可以得到词的概率图：

对该词图用2.中的算法求解最大概率的路径，即可得到分词结果。

与基于词典的分词不同的是，基于字的分词事先不对句子进行词的匹配，而是将分词看成序列标注问题，把一个字标记成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)进行建模。两者各有利弊，生成模型对变量的关系描述更加清晰，而判别式模型容易建立和学习。下面对几种序列标注方法做简要介绍。

生成式模型主要有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)的概率分布模型。例句的隐马尔科夫序列如下图：

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

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

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

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

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

目前对于序列标注任务，公认效果最好的模型是BiLSTM+CRF。结构如图：

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

前文主要讲了分词任务中所用到的算法和模型，但在实际的工业级应用中，仅仅有算法是不够的，还需要高效的数据结构进行辅助。

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

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

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

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

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

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

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

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

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