《计算语言学讲义04)词法分析二)》由会员分享,可在线阅读,更多相关《计算语言学讲义04)词法分析二)(78页珍藏版)》请在金锄头文库上搜索。
1、计算语言学 第 4 讲 词法分析(二) 刘群 中国科学院计算技术研究所 liuqun 中国科学院研究生院 2010 年春季课程讲义 计算语言学讲义 (04) 词法分析 ( 二 )2 内容提要 计算语言学讲义 (04) 词法分析 ( 二 )3 内容提要 计算语言学讲义 (04) 词法分析 ( 二 )4 内容提要 计算语言学讲义 (04) 词法分析 ( 二 )5 内容提要 计算语言学讲义 (04) 词法分析 ( 二 )6 什么是统计语言模型 语言模型给出任何一个句子的出现概率: Pr(Sentence=w1w2wn) 归一化条件:SentencePr(Sentence)=1 统计语言模型实际上就是
2、一个概率分布,它给 出了一种语言中所有可能的句子的出现概率 在统计语言模型看来,对于一种语言,任何一 个句子都是可以接受的,只是接受的可能性 (概率)不同 统计语言模型问题是一个典型的序列评估问题 计算语言学讲义 (04) 词法分析 ( 二 )7 语言模型的类型 理论上,单词串的任何一种概率分布,都是一个语言模型。 实际上, N 元语法模型是最简单也是最常见的语言模型。 N 元语法模型由于没有考虑任何语言内部的结构信息,显然 不是理想的语言模型。 其他语言模型: 隐马尔科夫模型( HMM )(加入词性标记信息) 概率上下文无关语法( PCFG )(加入短语结构信息) 概率链语法( Probab
3、ilistic Link Grammar )(加入链语法的结构信 息) 目前为止,其他形式的语言模型效果都不如 N 元语法模型 统计机器翻译研究中开始有人尝试基于句法的语言模型 计算语言学讲义 (04) 词法分析 ( 二 )8 N 元语法模型概念辨析 N 元语法模型: N-Gram Model 。 所谓 N-Gram ,指的是由 N 个词组成的串,可 以称为“ N 元组”,或“ N 元词串”。 基于 N-Gram 建立的语言模型,称为“ N 元语 法模型 (N-Gram Model)” 。 Gram 不是 Grammar 的简写。在英文中,并 没有 N-Grammar 的说法。 在在汉语中,单
4、独说“ N 元语法”的时候,有 时指“ N 元组 (N-Gram)” ,有时指“ N 元语 法模型 (N-Gram Model)” ,请注意根据上下文 加以辨别。 计算语言学讲义 (04) 词法分析 ( 二 )9 N 元语法模型定义 N 元语法模型( N-gram Model ) 假设:单词 wi出现的概率只与其前面的 N-1 个单词有关 Pw= i=1 n pwiw1w2.wi1 i=1 n pwiwiN1wiN2.wi1 计算语言学讲义 (04) 词法分析 ( 二 )10 N 元语法模型举例 N=1 时:一元语法模型 相当于词频表,给出所有词出现的频率 N=2 时:二元语法模型 相当于一个
5、转移矩阵,给出每一个词后面出现另一 个词的概率 N=3 时:三元语法模型 相当于一个三维转移矩阵,给出每一个词对儿后面 出现另一个词的概率 在自然语言处理中, N 元语法模型可以在汉字 层面,也可以在单词层面,还可以在概念层面 计算语言学讲义 (04) 词法分析 ( 二 )11 二元语法模型图示 P(t-i-p) = p(X1 = t)p(X2 = i|X1 = t)p(X3 = p|X2 = i) = 1.00.30.6= 0.18 计算语言学讲义 (04) 词法分析 ( 二 )12 袋子模型 Bag Model (1) 将一个英语句子中所有的单词放入一个 袋子中 用 N 元语法模型试图将其
6、还原 对于这些单词的任何一种排列顺序根据 N 元 语法模型计算其出现概率 取概率最大的排列方式 计算语言学讲义 (04) 词法分析 ( 二 )13 袋子模型 Bag Model (2) 实验:取 38 个长度小于 11 个单词的英语句子,实验 结果如下: 计算语言学讲义 (04) 词法分析 ( 二 )14 代码识别问题 (1) 给出一段汉语文本,需要识别出其是 GB 码还是 BIG5 码 假设 GB 码的文本和 BIG 码的文本出现概率相同 code=argmax code Pcodetext =argmax code PtextcodePcode Ptext =argmax code Pte
7、xtcodePcode argmax code Ptextcode 计算语言学讲义 (04) 词法分析 ( 二 )15 代码识别问题 (2) 为 GB 码和 BIG5 码分别建立一元统计语 言模型,也就是为两种代码分别建立字 频表 将代码 text 按照 GB 码和 BIG5 码分别识 别成不同的汉字串,计算其中所有汉字 频率的乘积 算法的优点:简单、高效,通过很短的 一段文本就可以识别出其代码类型 计算语言学讲义 (04) 词法分析 ( 二 )16 音字转换 (1) 给出一段拼音,要求转换成汉字 pinyin woaini 汉字我爱你、窝爱霓、我挨你 不考虑同音字,即认为 P(pinyin|
8、text) 为常量 text=argmax text Ptextpinyin =argmax text P pinyintextPtext Ppinyin =argmax text P pinyintextPtext argmax text Ptext 计算语言学讲义 (04) 词法分析 ( 二 )17 音字转换 (2) 一元语法模型: 空间: n (汉字总数) 同音字中总是会选择最高频的汉字,不合适 二元语法模型: 空间: n2 效果比一元语法模型有较大提高 估计对于汉语而言四元语法模型效果较好 实用系统:智能狂拼,微软拼音 计算语言学讲义 (04) 词法分析 ( 二 )18 N 元语法模型
9、的参数估计 最大似然估计: 选择参数,使得训练语料出现的概率最大 用实际样本中事件出现的频率来估计该 事件的概率 pwnw1w2.wn1= f w1.wn f w1.wn1 计算语言学讲义 (04) 词法分析 ( 二 )19 数据平滑 数据稀疏问题 如果 f(w1wn) 0 ,那么出现零概率,导 致整个文本的出现概率为零 解决办法:劫富济贫 约束:概率的归一性 wn pwnw1w2.wn1=1 计算语言学讲义 (04) 词法分析 ( 二 )20 平滑算法加 1 法 给每个事件出现的词数加 1 m 为单词( word type )的个数 会导致未出现的事件概率过高 可以将 1 改成一个更小的常数
10、 pwnw1w2.wn1= f w1.wn1 f w1.wn1m 计算语言学讲义 (04) 词法分析 ( 二 )21 平滑算法 Good-Turing 法 (1) 样本数据的大小为 N 样本中出现 r 次的样本数为 nr, 且 r 最大值为 R ,于是有: 估计: r=1 R rN r=N Pr= r1 N nr1 nr 计算语言学讲义 (04) 词法分析 ( 二 )22 平滑算法 Good-Turing 法 (2) 修正: nr=0 时, Pr=0 nr+1=0 时,用下一个不为 0 的 nr+k 取代 nr+1 直观理解: 用出现 r+1 次的事件出现的总概率平均分 配到出现 r 次的事件
11、上面 Pr= r1 N nr1 nr 计算语言学讲义 (04) 词法分析 ( 二 )23 平滑算法 Good-Turing 法 (3) 优点: 有很好的理论基础:理论上,可以采用留一方法(交 叉检验的一种),通过最大似然估计推导出这种方法 其它平滑技术的基础 缺点: 无法保证概率估计的“有序性”,即出现次数多的事 件的概率大于出现次数少的事件的概率。 pr与 r/N 不能很好地近似,好的估计应当保证 pr p(n) then p(n)=p(n), previous_edge(n)=e Let best_segmentationis a empty array of edges Let node
12、 nis the destination node Repeat until nis the source node Push previous_edge(n) to the head of best_segmentation Letnbe the node where e start from Return best_segmentation 计算语言学讲义 (04) 词法分析 ( 二 )49 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成
13、分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p(分|合成) p(成|结合) 计算语言学讲义 (04) 词法分析 ( 二 )50 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p(分|合成) p(成|结合) 计算语言学讲义 (04) 词法分析 ( 二 )51 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S
14、)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p(分|合成) p(成|结合) 计算语言学讲义 (04) 词法分析 ( 二 )52 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p(分|合成) p(
15、成|结合) 计算语言学讲义 (04) 词法分析 ( 二 )53 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p(分|合成) p(成|结合) 计算语言学讲义 (04) 词法分析 ( 二 )54 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p(分|合成) p(成|结合) 计算语言学讲义 (04) 词法分析 ( 二 )55 在词图上搜索最优路径: Viterbi 算法 S结合分子 p(结|S)p(合|结)p(成|合)p(分|成)p(子|分) p(结合|S) p(合成|结) p(成分|合) p(分子|合成) 结合 合成 成分 分子 p(成分|结合) p(子|成分) D p(D|子) 成 p(分子|成) p