自然语言处理npl 最大概率分词算法

《自然语言处理npl 最大概率分词算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、NLP基于最大概率的汉语切分Ytinrete要求：基于最大概率的汉语切分目标：采用最大概率法进行汉语切分。其中：n-gram用bigram，平滑方法至少用Laplace平滑。输入：接收一个文本，文本名称为：corpus_for_test.txt输出：切分结果文本，其中：切分表示：用一个字节的空格“”分隔，如：我们在学习。每个标点符号都单算一个切分单元。输出文件名为：学号.txtBigram参数训练语料：corpus_for_train.txt注：请严格按此格式输出，以便得到正确评测结果切分性能评价：分切分结果评测F*100,F=2P*R/(P+

2、R)特别注意:代码雷同问题本次作业最后得分会综合考虑：切分性能、代码、文档等几个方面。第三次作业上交的截止时间：2014年1月7日24:001.关于最大概率分词基本思想是：一个待切分的汉字串可能包含多种分词结果，将其中概率最大的作为该字串的分词结果。根据：由于语言的规律性，句子中前面出现的词对后面可能出现的词有很强的预示作用。公式1：其中w表示词，s表示待切分字符串。公式2：例如：S：有意见分歧 W1:有/意见/分歧/ W2:有意/见/分歧/P(W1)=P(有)×P(意见)×P(分歧)＝1.8*10-9P(W2)=P(有意)×P(见)×P(分歧

3、)＝1*10-11P(W1)>P(W2)所以选择W1历史信息过长，计算存在困难p(wi

4、w1w2…wi-1)为了便于计算，通常考虑的历史不能太长，一般只考虑前面n-1个词构成的历史。即：p(wi

5、wi-n+1…wi-1)n-gramn较大时：?提供了更多的语境信息，语境更具区别性。但是，参数个数多、计算代价大、训练语料需要多、参数估计不可靠。n较小时：?语境信息少，不具区别性。但是，参数个数少、计算代价小、训练语料，无需太多、参数估计可靠。题目要求使用bigram，即考虑前一个词，即考虑左邻词。左邻词假设对字串从左到右进行扫描，可以得到w1,w

6、2,…,wi-1wi,…等若干候选词，如果wi-1的尾字跟wi的首字邻接，就称wi-1为wi的左邻词。比如上面例中，候选词“有”就是候选词“意见”的左邻词，“意见”和“见”都是“分歧”的左邻词。字串最左边的词没有左邻词。最佳左邻词如果某个候选词wi有若干个左邻词wj，wk,…等等，其中累计概率最大的候选词称为wi的最佳左邻词。比如候选词“意见”只有一个左邻词“有”，因此，“有”同时也就是“意见”的最佳左邻词；候选词“分歧”有两个左邻词“意见”和“见”，其中“意见”的累计概率大于“见”累计概率，因此“意见”是“分歧”的最佳左邻词。数据稀疏问若某n

7、-gram在训练语料中没有出现,则该n-gram的概率必定是0。解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。由于训练样本不足而导致所估计的分布不可靠的问题，称为数据稀疏问题。在NLP领域中，数据稀疏问题永远存在，不太可能有一个足够大的训练语料，因为语言中的大部分词都属于低频词。解决办法:平滑技术?把在训练样本中出现过的事件的概率适当减小。?把减小得到的概率密度分配给训练语料中没有出现过的事件。?这个过程有时也称为discounting(减值)。目前已经提出了很多数据平滑技术，如：?Add-o

8、ne平滑?Add-delta平滑?Witten-Bell平滑?Good-Turing平滑?Church-Gale平滑?Jelinek-Mercer平滑?Katz平滑这里我使用laplace平滑Add-one平滑(Laplace’slaw)规定任何一个n-gram在训练语料至少出现一次（即规定没有出现过的n-gram在训练语料中出现了一次）。没有出现过的n-gram的概率不再是0。2.算法描述1)对一个待分词的字串S，按照从左到右的顺序取出全部候选词w1,w2,…,wi-1wi,…wn；2)到词典中查出每个候选词的概率值P(wi)，当候选词没有出

9、现时，由laplace平滑设其概率为1/(字典数+1)，记录每个候选词的全部左邻词；3)按照公式1计算每个候选词的累计概率，同时比较得到每个候选词的最佳左邻词；4)如果当前wn是字串S的尾词，且累计概率P’(wn)最大，wn就是S的终点词。5)从wn开始，按照从右到左的顺序，依次将每个词的最佳左邻词输出，即为S的分词结果。3.程序设计整个程序我分为两个阶段，字典生成阶段和分词阶段。(make_dic.cpp)字典生成：目标：输入为训练语料(corpus_for_train.txt)，输出为字典(dic.txt)，字典内容为单词和单词出现在字典中

10、的频率，首行为词典总词数。实现步骤：首先读入训练，通过空格和换行符作为判定，分出单个单词。若单词没有在字典中出现，则将其加入字典，单词自身频数加一，单