自然语言处理——7.5 自动分词基本算法

2018-10-08 本文已影响47人 SpareNoEfforts

􀂋 有词典切分/ 无词典切分
􀂋 基于规则的方法/ 基于统计的方法

1. 最大匹配法(Maximum Matching, MM)

－有词典切分，机械切分

正向最大匹配算法 (Forward MM, FMM)
逆向最大匹配算法 (Backward MM, BMM)
双向最大匹配算法 (Bi-directional MM)

假设句子： $S = c_1c_2...c_n$ ，某一词： $w_i =c_1c_2...c_m，m$ 为词典中最长词的字数。

1.1 FMM算法描述
1.2 例子：
1.3 优缺点
优点
• 程序简单易行，开发周期短；
• 仅需要很少的语言资源（词表），不需要任何词法、句法、语义资源；
缺点
• 歧义消解的能力差；
• 切分正确率不高，一般在95%左右。

2. 最少分词法(最短路径法)

2.1 基本思想

设待切分字串 $S=c_1 c_2…c_n$ ，其中 $c_i (i =1, 2, …, n)$ 为单个的字， $n$ 为串的长度， $n \ge 1$ 。建立一个节点数为 $n+1$ 的切分有向无环图 $G$ ，各节点编号依次为 $V_0，V_1，V_2，…，V_n$ 。

求最短路径：贪心法或简单扩展法。

2.2 算法描述
2.3 例子

2.4 存在的问题
例(2) 输入字串: 他说的确实在理。
输出候选:
他/ 说/ 的/ 确实/ 在理/ 。(词个数：6)
他/ 说/ 的确/ 实在/ 理/ 。(词个数：6)
系统无法做正确性判断。
2.5 优缺点
优点：
• 切分原则符合汉语自身规律；
• 需要的语言资源（词表）也不多。
弱点：
• 对许多歧义字段难以区分，最短路径有多条时，选择最终的输出结果缺乏应有的标准；
• 字串长度较大和选取的最短路径数增大时，长度相同的路径数急剧增加，选择最终正确的结果困难越来越越大。

3. 基于语言模型的分词方法

3.1 方法描述
设对于待切分的句子 $S$ ， $W = w_1w_2……w_k(1\le k \le n)$ 是一种可能的切分。
3.2 优缺点
优点：
• 在训练语料规模足够大和覆盖领域足够多时，可以获得较高的切分正确率。
弱点：
• 模型性能较多地依赖于训练语料的规模和质量，训练语料的规模和覆盖领域不好把握；
• 计算量较大。

4. 基于HMM的分词方法

4.1 基本思想

把输入字串(句子) $S$ 作为 $HMM$ $\mu$ 的输入；切分后的单词串 $S_w$ 为状态的输出，即观察序列 $S_w = w_1w_2 …w_n ,n \ge 1$ 。词性序列 $S_c$ 为状态序列，每个词性标记 $c_i$ 对应 $HMM$ 中的一个状态 $q_i$ ， $S_c= c_1c_2…c_n$ 。

${{\hat S}_\omega } = \mathop {\arg \max }\limits_{{S_\omega }} p({S_\omega }|\mu )$

4.2 优缺点
优点：
在训练语料规模足够大和覆盖领域足够多时，可
以获得较高的切分正确率。
弱点：
• 模型性能较多地依赖于训练语料的规模和质量，训练语料的规模和覆盖领域不好把握；
• 模型实现复杂、计算量较大。

5. 由字构词(基于字标注)的分词方法(Character-based tagging )

5.1 基本思想

将分词过程看作是字的分类问题。该方法认为，每个字在构造一个特定的词语时都占据着一个确定的构词位置(即词位)。假定每个字只有4个词位：词首(B)、词中(M)、词尾(E)和单独成词(S)，那么，每个字归属一特定的词位。

5.2 评价

该方法的重要优势在于，它能够平衡地看待词表词和未登录词的识别问题，文本中的词表词和未登录词都是用统一的字标注过程来实现的。在学习构架上，既可以不必专门强调词表词信息，也不用专门设计特定的未登录词识别模块，因此，大大地简化了分词系统的设计

6. 生成式方法与区分式方法的结合

6.1 基本思想
大部分基于词的分词方法采用的是生成式模型(Generative model)

$WSe{q^*} = \mathop {\arg \max }\limits_{WSeq} p(WSeq|c_1^n) = \mathop {\arg \max }\limits_{WSeq} p(WSeq)$

使用3-gram:

$p(\omega _1^m) = \mathop \Pi \limits_{i = 1}^m p({\omega _i}|\omega _1^{i - 1}) \approx \mathop \Pi \limits_{i = 1}^m p({\omega _i}|\omega _{i - 2}^{i - 1})$

而基于字的分词方法采用区分式模型(Discriminative model)

6.2 生成式模型与判别式模型的比较
6.2.1 生成(产生)式模型(Generative Model)

假设 $o$ 是观察值， $q$ 是模型。如果对 $p(o|q)$ 进行建模, 就是生成式模型。其基本思想是：首先建立样本的概率密度模型，再利用模型进行推理预测。要求已知样本无穷多或者尽可能地多。该方法一般建立在统计学和 Bayes 理论的基础之上。

• 主要特点：从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。
• 主要优点：实际上所带的信息要比判别式模型丰富，研究单类问题比判别式模型灵活性强，模型可以通过增量学习得到，且能用于数据不完整(missing data) 情况。
• 主要缺点：学习和计算过程比较复杂。

6.2.2 判别(区分)式模型(Discriminative Model)

如果对条件概率(后验概率) $p(q|o)$ 进行建模，就是判别式模型。基本思想是：有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。表性理论为统计学习理论。
• 主要特点：寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。
• 主要优点：判别式模型比生成式模型较容易学习。
• 主要缺点：黑盒操作，变量间的关系不清楚，不可视。