文档章节

搜索引擎之N元分词方法

潘少online
 潘少online
发布于 2015/05/24 23:42
字数 2009
阅读 78
收藏 1

香农游戏(Shannon Game)

根据前面的(n-1)个词预测下一个单词可能是什么?


“NBA______”

        比赛?  球星? 篮球?秀选?

“直播NBA______”

       决赛?季后赛?


转移概率P(比赛|NBA)


选择n值

词汇量(V) = 20,000

可靠性(Reliability)和可区别性(Discrimination)成反比,需要折中

n越大,区别力越大;n越小,可靠性越高

N取多大?

理论上讲,越大越好

经验值:二元或三元(trigram)

二元模型

如果简化成一个词的出现仅依赖于它前面出现的一个词,那么就称为二元模型(bigram)。

即:

P(S) = P(w1,w2,...,wn)= P(w1) P(w2|w1) P(w3|w1,w2)…P(wn|w1w2,...,wn-1)

          ≈P(w1) P(w2|w1)P(w3|w2)…P(wn|wn-1) 

基本的计算方法:

P(wi|wi-1) ≈ freq(wi-1,wi) /freq(wi-1)

二元搭配词典

Freq(有,意见)=4

P(意见|有) ≈ freq(wi-1,wi) /freq(有)=4/4000=0.001

因为数据稀疏导致 “意见,分歧” 等其他的搭配都没找到。

P(S1)和P(S2)都将是0,无法通过比较计算结果找到更好的切分方案。

这就是零概率问题。

查找二元词典

  • 可以采用Trie树的形式来存放N元模型的参数。与词典Trie树的区别在于:词典Trie树上每个结点对应一个汉字,而N元模型Trie树的一个结点对应一个词。

  • 或者可以把搭配信息存放在词典Trie树的叶子节点上。每个词有一个编号wId。

public class BigramMap {
    public int[] keys;//词编号
    public int[] vals;//频率
}

以存储“大学生,生活”为例,“生活”的词编号是8,大学生的词编号是5。假设“大学生,生活”频率是3


避免零概率:数据平滑(smoothing)

  • p’(w) ≈p(w), 但p’(w)≠0

  • 对一些p(w)>0,生成p’(w)<p(w)

  • 分配概率D给所有概率为0的项目w: p’(w)>p(w)=0

  •     可能对于概率值较低的词也作调整

  • 可能有些w: p’(w)=p(w)

  • 需要确保

  • 有许多数据平滑的方法

  •         加1平滑

  •         加Lambda平滑

  •         Witten-Bell平滑

  •         Good-Turing平滑

加一平滑

26个字母,每个都加1

300个观测事件,而不是3个,有了更好的数据后,平滑更少了

假设有20000个单词类型,而不是26个字母

“新事件” = 零次事件(不会在训练集中出现)。

这里: 19998个新事件,全部估计概率是19998/20003.  

因此加一平滑认为特别可能看到新事件,而不是在训练集已经看到的单词。

仅仅因为有一个大词典就如此认为:引入了20000个可能的事件。

“想的太多,违背直觉而出错了”?


加Lambda平滑

大的词典使得新事件变得太有可能了。

解决方法:不是加1到所有的频率上,而是加  = 0.01?

这样又可能给太小的可能性到新事件


如何选择最好的l?  

也就是说,要平滑多少?

例如,分出多少概率给新事件?

依赖于新事件有多大可能出现

可能依赖于文本的类型,训练语料集的大小…

从数据中判断要平滑多少。

术语: 类型 与 表征

词 类型(type) = 不同的词汇项

词 表征(token) = 该类型在语料库中的出现

词典是一个类型的列表 (词典中的每一项就是一个类型)

语料库是一个表征的列表(每个类型有许多表征)

有任何理论上的好方法来选择λ?新事件有多大可能? 


新事件有多常见?

Witten-Bell 平滑思想

Good-Turing平滑思想

证明Good-Turing

实验次数

通过留一个训练证明! 蓝色部分是训练集。黄色部分是留出来的一个表征。蓝色部分加黄色部分做测试集。

轮流拿出N个表征中的一个,训练集大小是N-1,拿出来的集合大小是1

不是仅仅调整l,可以调整多个值

p(novel)=0.02=N1/N                     [=黄色部分拿出来的一个开发词在蓝色训练集里是新事件]

p(singleton)=0.015=N2*2/N        [=黄色部分拿出来的一个开发词在蓝色训练集里是singleton]

p(doubleton)=0.012=N3*3/N      [=黄色部分拿出来的一个开发词在蓝色训练集里是doubleton]

也就是

p(novel) = 在全部训练集里的singleton部分

p(singleton) =在全部训练集里的doubleton部分,依次类推


Witten-Bell平滑

Witten-Bell构想:如果已经看到许多不同的事件 ,则新事件也是有可能的。  (考虑 类型/表征 比率)

Good-Turing构想:如果已经看到许多singleton,则新事件也是有可能的。

Good-Turing平滑    

构想:可以通过singleton的比率判断新事件的比率


假设 Nr = 出现r次的词类型数量

例如,N0 = 没看到的单词数

例如,N1 = 只出现1次的单词数

假设N = N = S r Nr  = 总的词数


朴素的估计:如果x有r个表征,则 p(x) = ?

答案: r/N

全部的朴素概率全部的有r个表征的词类型?

答案: : Nr r / N   

这个全部概率的Good-Turing 估计:

定义成: Nr+1 (r+1) / N

主要思想:利用高频n-gram的频率调整低频n-gram的频率。估计次数r*:

问题:有1个n-gram出现了r=1000次,有0个n-gram出现了1001次,那么, 

解决方法:可以把概率最大的词保持原概率不变,但仍然参与归一化处理                 


Good Turing平滑的例子

想象正在钓鱼

已经钓到了10条鲤鱼,3条鳕鱼,2条金枪鱼,1条鳟鱼,1条三文鱼,1条鳗鱼。

多大可能下一条是新的一种鱼? 

3/18

多大可能下一条是金枪鱼? 

小于 2/18











简单线性插值(Simple Linear Interpolation)

    这里 λ1 +λ2 +λ3 =1,而且对所有的i来说,λi≥0

线性插值

这个估计定义了分布:


估计条件概率

使用Good Turing估计条件概率

例如,估计三元连接条件概率: 


根据平滑公式计算举例

P(S1) = P(有) * P’(意见|有) * P’(分歧|意见) 

= P(有) * (0.3P(意见)+0.7P(意见|有)) * (0.3P(分歧)+0.7P(分歧|意见) )

= 0.0180*(0.3*0.001+0.7*0.001)*(0.3*0.0001)

= 5.4*10-9

P(S2) = P(有意) * P’(见) * P’(分歧) 

= P(有意) * (0.3P(见)+0.7P(见|有意)) * (0.3P(分歧)+0.7P(分歧|见) )

= 0.0005*(0.3*0.0002) *(0.3*0.0001)

= 9*10-13

P(S1)> P(S2) 

动态规划求解二元模型

到Nodei为止的最大概率称为Nodei的概率。 

如果Wj的结束节点是Nodei,就称Wj为Nodei的前驱词

这里的prev2(Nodei)就是节点i的二级前驱词序列,记做Wj,Wk 。

比如上面的例子中,“意见”和“见”都是节点3的1级前驱词,候选词“有”就是节点3的2级前驱词。

StartNode(wj)是wj 的开始节点,也是节点i的2级前驱节点。

因此切分的最大概率max(P(S))就是P(Nodem)也就是

P(节点m的最佳2级前驱节点)*P(节点m的2级最佳前驱词序列)


求解二元模型的实现

//计算节点i的最佳前驱节点
void getBestPrev(AdjList g,int i){
  Iterator<CnToken> it1 = g.getPrev(i);//得到一级前驱词集合
  double maxProb = Double.NEGATIVE_INFINITY;
  int maxPrev1 = -1;
  int maxPrev2 = -1;
  
  while(it1.hasNext()) {
      CnToken t1 = it1.next();
      Iterator<CnToken> it2 = g.getPrev(t1.start);//得到一级前驱词对应的二级前驱词集合
        while(it2.hasNext()){
      CnToken t2 = it1.next();
      
      int bigramFreq=getBigramFreq(t2,t1);//从二元词典找二元频率
        double biProb = lambda1*t1.freq + lambda2*(bigramFreq/t2.freq);//平滑后的二元概率
          double nodeProb = prob[t2.start]+(Math.log(biProb));
        
          if (nodeProb > maxProb)//概率最大的算作最佳前趋
             {
          maxPrev1 = t1.start;
          maxPrev2 = t2.start;
          maxProb = nodeProb;
          }
      }
   }
  prob[i] = maxProb;
  prev1Node[i] = maxPrev1;
  prev2Node[i] = maxPrev2;
}


N元模型扩展

可以用于汉字(字符)的搭配关系:

“张志___”

         强? 刚?杰?

“汪___”

         洋? 涵?溪?




© 著作权归作者所有

潘少online
粉丝 12
博文 58
码字总数 107019
作品 2
深圳
程序员
私信 提问
干货 | 自然语言处理(1)之聊一聊分词原理

前言 在做文本挖掘时,首先要做的预处理就是分词。英文单词天然有空格隔开容易按照空格分词,但有时也需要把多个单词做为一个分词,比如一些名词如“New York”,需要做为一个词看待。而中文...

sfm06sqvw55dft1
2017/12/08
0
0
随思:关于中文分词方法

疑问:为什么会涉及到分词方法学呢? 为什么需要确定哪些是词语,哪些不是词语呢? 为什么需要进行分词,如果不分词会是什么情况呢? 分词的根本目的是为了搜索服务的,更确切的是为快速搜索而...

wangtaotao
2014/04/06
0
0
触类旁通Elasticsearch:分析数据

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wzy0623/article/details/86693408 目录 一、什么是分析 二、分析文档 三、分析API 四、分析器、分词器、分词...

wzy0623
01/29
0
0
浅谈SEO的关键:中文分词

在搜索引擎技术中,中文分词对于影响搜索引擎结果排序有着至关重要的作用。我们在实际的搜索引擎优化中,为了避免很多主关键词的大量竞争,也会使用到中文分词技术来做SEO优化。举个简单的例...

红薯
2009/03/11
1K
2
ES0.2 Analysis和Analyzer

Analysis 和Analyzer analysis: 1,对文本分词,分成适合做倒排索引的词语。 2,对词语做标准化(normalizing),比如统一大小写、缩写转换等。这样做的目的是为了提升可搜索的能力。 Analyz...

gangzz
2015/01/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

对集合的理解

开端 同事小G提了一点,Set都是无序的,但是我之前有看到过treeSet是有序的,就和他讨论了起来,还百度了一下,有序。然而他只是淡淡的说自己敲代码验证一下。 TreeSet 循环int类型 1~20,毫...

无极之岚
30分钟前
0
0
Kernel字符设备驱动框架

Linux设备分为三大类:字符设备,块设备和网络设备,这三种设备基于不同的设备框架。相较于块设备和网络设备,字符设备在kernel中是最简单的,也是唯一没有基于设备基础框架(device结构)的...

yepanl
34分钟前
0
0
Ajax

定义 Ajax是一种在无需重新加载整个网页的情况下,能够更新部分网页的技术,用于创建动态网页 Ajax=Asynchronous Javascript And XML(异步的JavaScript和XML) 原理 XMLHttpRequest对象(异...

星闪海洋
昨天
2
0
Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
昨天
3
0
Spring中如何使用设计模式

关于设计模式,如果使用得当,将会使我们的代码更加简洁,并且更具扩展性。本文主要讲解Spring中如何使用策略模式,工厂方法模式以及Builder模式。 1. 策略模式 关于策略模式的使用方式,在S...

爱宝贝丶
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部