文本上的算法

学术界大牛总结的NLP中的机器学习算法、深度学习算法的总结Hadoop100第五章、你要知道的一些术语●。·b●●●。。。鲁。●b●。。鲁。●。。。●·。b·。自e。●106tf/df/idf106PageRank..................107相似度计算.■·■108第六章、搜索引擎是什么玩意儿s··asa·ss··a·a·s····117搜索引擎原理...17搜索引擎架构.…120搜索引擎核心模块122搜索广告137推荐系统…...……………………143第七章、理解语言有多难●·●D●●●。。·。●●··。●●。·。垂●。e。。。。·。b·。●●。。。。●。。。·b●●149自然语言处理..129对话系统161最后●●●●。●自●●●。·●b●●●●。●●●●。自。·b●●。。·。b●。●●e。●自●b自●●·。b●·●。●be●。自●ee●自。D●●172重大版本变化完成理论篇完成应用篇增加并优化深度学习章节,优化其他章节内容-增加自然语言处理和对话系统部分,优化其他章节内容序:《文木上的算法》主要分两大部分:第一部分是理论篇,主要介绍机器学的基础和一些具体算法;第二部分应用篇,主要是一些的应用,比如:搜索引擊原理是什么?它为什么要建索引?有什么理论基础吗?之所以抽时间写这个文档,是由于以下方面的考虑:、这些都是我个人的一些总结和思考(有些内容在论文和书籍中都不会看到),零零散散的,所以想整理成一个稍微正式一点的文档,方便查阅;、这些知识在平常的工作中都会经常用到,整理成这个较正式文档也可以当作读者的一种参考。、除∫必不可少的公式外,尽量以更口语化的方式表达出来,抛弃掉繁琐的证明,提取岀算法的核心,尽可能达到深入浅出。由于本人水平有限,难免会有一些错误,希望大家不吝指出。理论篇第一章、你必须知道的一些基础知识要想明白机器学习,一些概率论和信息论的基本知识一定要知道,本章就简单的回顾下这些知识(本章可跳过阅读)。概率论概率就是描述一个事件发生的可能性。我们生活中绝大多数事件都是不确定的,每一件事情的发生都有一定的概率(确定的事件就是的概率而已),天气预报说明天有雨,那么它也只是说明天下雨文本上的算法路彦雄1的概率很大。再比如:掷骰子,我把一个骰子掷出去,问某一个面朝上的概率是多少?在骰子没有做任何手脚的情况下,直觉告诉你任何个面朝上的概率都是,如果你只掷几次很难得出这个结论,但是如果你掷上万次或更多,那么必然可以得出任何一个面朝上的概率邵是的结论,这就是大数定理:当试验次数(样本)足够多的时候,事件出现的频率无限接近于该事件真实发生的概率。假如我们用概率函数p(x)来表示随机变量x∈X的概率,那么就要满足如下两个特性:0≤p(x)≤1p(x)=1X∈X联合概率p(x,y)表示两个事件共同发生的概率。假如这两个事件相互独立,那么就有联合概率p(x,y)=p(x)p(y)条件概率p(ylx)是指在已知事件ⅹ发生的情况下,事件y发生的概率,且有:p(yx)=p(x,y)/p(x)。如果这两个事件相互独立,那么p(y|x)与p(y)相等。联合概率和条件概率分別对应两个模型:生成模型和判別模型,这两个模型将在下一章中解释。概率分布的均值称为期望,定乂如下:EXIxp(x)X∈文本上的算法路彦雄2期望就是对每个可能的取值x,与其对应的概率值p(x),进行相乘求和。假如一个随机变量的概率分布是均匀分布,那么它的期望就等于均值,因为它的概率分布p(x)=1/N。概率分布的方差定义如下:Var[X]=>(x-E[x])2p(x)=EICX-E[XI)X∈X可以看出,方差是表示随机变量偏离期望的大小,所以它是衡量数据的波动性,方差越小表示数据越稳定,反之方差越大表示数据的波动性越大。另外,你还需要知道的几个常用的概率分布:均匀分布、正态分布、二项分布、泊松分布、指数分布等等,你还可以了解下矩阵的东西,因为所有公式都可以表示成矩阵形式。信息论假如一个朋友告诉你外面下雨了,你也许觉得不怎么新奇,因为下雨是很平常的一件事情,但是如果他告诉你他见到外星人了,那么你就会觉得很好奇:真的吗?外星人长什么样?同样两条信息,一条信息量很少,一条信息量很大,很有价值,那么这个价值怎么量化呢?就需要信息熵,一个随机变量X的信息熵定义如下H(X)=->p(x)logp(x)X∈X信息越少,事件(变量)的不确定性越大,它的信息熵也就越大,需要搞明白该事件所需要的额外信息就越大,也就是说搞清楚小概率事文本上的算法路彦雄3件所需要额外的信息就越大,比如说,为什么大多数人愿意相信专家的话,因为专家在他专注的领域了解的知识(信息量)多,所以他对某事件的看法越透彻,不确定性就越小,那么他所传达岀来的信息量就越大,听众搞明白该事件所需要的额外信息就越少。不过,在这个利益至上的社会,有时对专家说的话也只能呵呵了。总之,记住一句话:信息熵表示的是不确定性的度量。信息熵越大,不确定性越大。联合熵的定义为:HOX,Y)p(x, y) logp(x,y)∈Xy∈Y联合熵描述的是一对随机变量X和Y的不确定性。条件熵的定义为H(YIX)=2p(x, y )logp(ylx)x∈X,y∈Y条件熵衡量的是在一个随机变量X已知的情况下,另一个随机变量Y的不确定性。两个随机变量X和Y,它们的互信息定义为I X; Y)p(x, y)logp(xp(y)x∈Xy∈Y互信息是衡量两个随机变量(事件)的相关程度,当X和Y完全相关时,它们的互信息就是;反之,当X和Y完全无关时,它们的互信息就是互信息和熵有如下关系:文本上的算法路彦雄4I (X; Y=H(X)-H(XY=H(Y)(YX相对熵(又叫距离)的定义如下D(P|Q)=〉p(x)logX∈X相对熵是衡量相同事件空间里两个概率分布(函数)的差异程度(不同于前面的熵和互信息,它们衡量的是随机变量的关系),当两个概峯分布完全相同时,他们的相对熵就为,当他们的差异增加时,相对熵就会增加。相对熵又叫距离,但是它不满足距离定义的三个条件中的两个:、非负性(满足);、对称性(不满足);、三角不等式(不满足)。它的物理意义就是如果用分布来编码分布(般就是真实分布)的话,平均每个基木事件编码长度增加了多少比特交叉熵的定义如下:H(P, Q)=H(P)+D(PIlQ)=-∑xp(x)logq(x)(离散分布)交叉熵可以理解为就是的信息熵D(P|Q好了,介绍了这么多概念公式,那么我们来个实际的例子,在文本处理中,有个很重要的数据就是词的互信息,上面说了,互信息是衡量两个随机变量(事件)的相关程度,那么词的互信息,就是衡量两个词的相关程度,比如,“计算机”和“硬件”的互信息就比“计算机”和“杯子”的互信息要大,因为它们更相关。那么如何在大量的语料下统计出词与词的互信息呢?公式中可以看到需要计算三个值:文本上的算法路彦雄5p(x)、p(y)和p(x,y),它们分别表示x独立出现的概率,y独立出现的概率,x和y同时出现的概率。前两个很容易计算,直接统计下词频然后除以总词数就知道了,最后一个也很容易,统计一下x和y同时出现(通常会限定一个窗口)的频率除以所有无序对的个数就可以了。这样,词的互信息就计算出来了,这种统计最适合使用来计算。贝叶斯法则贝叶斯法则是概率论的一部分,之所以单独拿出来写,是因为它真的很重要。它是托马斯·贝叶斯生前在《机遇理论中一个问题的解》中提出的一个当时叫“逆概率”问题,贝叶斯逝世后,由他的一个朋友替他发表了该论文,后来在这一理论基础上,逐渐形成了贝叶斯学派贝叶斯法则的定义如下:p(y x)p(xp(y)p(x|y)称为后验概率,p(yx)称为似然概率,p(x)称为先验概率,p(y)一般称为标准化常量。也就是说,后验概率可以用似然概率和先验概率来表示。就这个公式,非常非常有用,很多模型的基础就是它,比如:贝叶斯模型估计、机器翻译纠错、搜索引擎等等,在以后的章节中,大家经常会看到这个公式好了,这个公式看着这么简单,到底能有多大作用呢?那我们先拿中文分词来说说这个公式如何应用的。文本上的算法路彦雄6中文分词在中文自然语言处理中可以算是最底层,最基木的一个技术了,因为几乎所有的文本处理任务都要首先经过分词这步操作,那么到底要怎么对一句话分词呢?最简单的方法就是查字典,如果这个词在词典中出现了,那么就是一个词,当然,查字典要有一些策略最常用的就是最大匹配法,最大匹配法是怎么回事呢?举个例子来说,比如要对“中国地图”来分词,先拿“中”去查字典,发现“中”在字典里(单个词肯定在字典里),这时肯定不能返回,要接着查,“中国”也在字典里,然后再査“中国地”,发现没在字典里,那么“中国”就是一个词了;然后同样的处理剩下的句子。所以,最大匹配法就是匹配最长在字典中出现的词。查字典法有两种:正向最大匹配法和反向最大匹配法,一个是从前向后匹配,一个是从后向前匹配。但是查字典法会遇到一个自然语言处理中很棘手的问题:歧义问题,如何解决歧义问题呢?我们就以“学历史知识”为例来说明,使用正向最大匹配法,我们把“学历史知识”从头到尾扫描匹配一遍,就被分成了“学历史知识”,很显然,这种分词不是我们想要的;但是如果我们使用反向最大匹配法从尾到头扫描匹配一遍,那就会分成“学历史知识”,这才是我们想要的分词结果。可以看出查字典法可以用来分词,就会存在二义性,一种解决办法就是分别从头到尾和从尾到头匹配,在这个例子中,我们分别从头到尾和从尾到头匹配后将得到“学历史知识”和“学历史知识”,很显然,这两个分词都有“知识”,那么说明“知识”是止确的分词,然后就看“学历史”和“学历史”哪个是正确的,从我们人的角度看,很自然想到“学历史”是正确的,为什么呢?因文本上的算法路彦雄7