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

作者: SpareNoEfforts | 来源:发表于2018-10-08 22:59 被阅读47次

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

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

基于字的区分模型有利于处理集外词，而基于词的生成模型更多地考虑了词汇之间以及词汇内部字与字之间的依存关系。因此，可以将两者的优势结合起来。

6.2.3 结合方法1

结合方法1：将待切分字串的每个汉字用 $[c, t]_i$ 替代，以 $[c, t]_I$ 作为基元，利用语言模型选取全局最优(生成式模型)。

6.2.4 结合方法2:插值法把两种方法结合起来

7. 其他分词方法

全切分方法
串频统计和词形匹配相结合的分词方法
规则方法与统计方法相结合
多重扫描法

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

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

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

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

4. 基于HMM的分词方法

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

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

7. 其他分词方法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

NLP

NLP