《数学的美》读书笔记

坏早前看了几乎首博文,只留模糊印象
。这次是于习人工智能的基础知识后又拘留,其中研究自然语言的方从基于规则变更也因统计,对本身启发很怪。
在给一个繁杂的题目时常,一定要是错过想着拿其转化成数学问题,而无是本惯性思维去分析,只有转化成简单优雅的数学模型,才证实你的钻方向对了。电脑连无暧昧,它实际仅仅是白痴
全书内容多,本文特介绍三久主线:自然语言的统计模型、拼音输入法、搜索引擎。PS:简书不支持latex公式,让这首文章写的杀辛苦。

目录

1.言和言语 vs 数字和信息
2.自然语言处理 – 从规则及统计
3.统计语言模型
4.国语分词
5.隐含马尔可夫模型
6.信息熵
7.牛人介绍:
贾里尼克(Jelinek,现代自然语言处理奠基者,将语音识别作为通信问题)
8.布尔代数,搜索引擎的目
9.图论、网络爬虫
10.Page Rank,网页排名技术
11.TF-IDF,网页和查询相关性
12.少状态机和动态规划-地图和本土搜索
13.牛人介绍:阿米特·辛格,
14.余弦定理和讯分类
15.矩阵计算、文本处理中少单分类问题
16.音讯指纹:哈希
17.密码学中的数学、信息论
18.搜索引擎反作弊
19.数套模型重要性
20.极度老熵模型
21.拼音输入法之数学原理
22.牛丁介绍:马库斯(Marcus),建立语料库。
23.布隆过滤器
24.贝叶斯网络
25.标准仍机场和句法分析
26.牛人口介绍:维特于,高通创办者,制定CDMA协议。
27.盼最大化算法
28.逻辑回归和摸索广告
29.Map Reduce

1. 自然语言处理,语音识别,机器翻译

1.1 基于规则的语言处理

初学术界认为,要让机器就翻译和话音识别这种人类才会做的政工,就亟须先给电脑理解自然语言,而成功就点就算如给机器出相近人类的智能。这个方法论被号称“鸟飞派”(通过观察鸟的航空方法,采用仿生的笔触去出飞机)。

这就是说怎么为机器理解自然语言呢?受传统语言学的熏陶,他们觉得假如叫机器做好两起事:分析句子语法和沾语义。分析句子语法就是以语法把词拆分,分清它的主语、谓语、宾语是呀,每个有的词性是什么,用啊标点符号。而语义分析,就是弄清句子要发挥的切实意思。语法规则不行易用电脑算法描述,这吃众人觉得基于规则之办法是指向之。但是这种艺术迅速即陷入困境,因为根据语法的分析器处理不了复杂句子,同时,词的多义性无法用规则表述,例如下面的例子:

The pen is in the box. 和 The box is in the pen.
次句话给不英语母语的口深为难了解,盒子怎么当钢笔里啊?其实当此处,pen是围栏的意。这里pen是钢笔还是围栏,通过上下文已经不能够解决,而需常识,即钢笔可以置身盒子里,但是盒子比钢笔大,所以不能够放在盒子里,于是pen在此处是围栏的意思,盒子可放在围栏里。

1.2 基于统计的语言处理

贾里尼克(Jelinek)把语音识别问题看作通信问题,并因而单薄独带有马尔可夫模型(声学和言语模型)概括了语音识别,推动了基于统计的言语处理办法。

在语音识别中,计算机需要明白一个亲笔序列是否会结成一个豪门了解而且有意义的句子。早期的做法是判定为出底词是否适合语法,由前文可知这漫漫总长走不通。贾里尼克从另外角度看是题目:透过测算一个句出现的概率大小来判定其的合理,于是语音识别问题易成计算概率问题,根据这个思路,贾里尼克建立了统计语言模型

假定S表示有一个生义之语句,由一系列特定顺序排列的词w1,w2,w3…组成。我们纪念知道S在文书中冒出的可能性,计算S的几率P(S),根据条件概率公式:

766net必赢亚洲手机版 1

中P(w1)为w1出现的概率,P(w2|w1)为曾解第一单词出现的尺度下,第二只词起的票房价值,以此类推。前面几独票房价值容易计算,但是后面的几率就变量增多,变得不可计算。在此间需要用马尔可夫假而来简化计算。马尔可夫假设假使当前状态就跟前面一个态有关,即Wi出现的票房价值就和其前面的词有关Wi-1,于是点的公式可以简化为:

766net必赢亚洲手机版 2

连接下的问题是估计条件概率P(Wi|Wi-1),由标准概率公式得:

766net必赢亚洲手机版 3

而估计联合概率P(Wi-1, Wi)和P(Wi-1)可以统计语料库得到,通过计算(Wi-1,
Wi)这对准词在语料库中左右相邻出现的次数C,以及Wi-1单独出现的次数,就只是取得这些歌词要二元组的相对频度。根据大数定理,只要统计量足够,相对频度就相当于概率,于是

766net必赢亚洲手机版 4

乃复杂的语序合理性问题,变成了简要的次数统计问题。

上式对应的统计语言模型是二元模型,实际应用中,google翻译用到四元型。

1.3 中文分词

对此西方拼音语言来说,词中出醒目的分界符(空格),但是遭到、日、韩、泰等语言没有。因此,首先使对准词进行分词,才会举行更加自然语言处理。对一个句正确的分词结果如下:

分词前:中国航天官员应邀到美国以及太空总署负责人开会。
分词后:中国/航天/官员/应邀/到/美国/与/太空/总署/官员/开会/。

最容易想到的分词方法是“查字典”,即拿一个句从左到右扫描一满,遇到字典里片词就标明出,遇到复合词就寻找最丰富匹配,遇到不识的字串就分割成单字。这个法能够解决七八成为的题材,但是遇到有二义性的撤并就无法了,例如“发展中国家”,正确的划分是“发展-中-国家”,但是本查字典法就会见分成“发展-中国-家”。另外,并无是最好丰富匹配都定科学,例如“上海大学城书店”,正确的剪切是“上海-大学城-书店”,而休是“上海大学-城-书店”。

以前文的打响思路,依靠语法规则无法缓解分词的二义性问题,还是得凭借统计语言模型。

设一个句子S有n种分词方法,利用前文的统计语言模型,各自计算起各种分词方法的票房价值,概率最充分之哪怕为无限好的分词方法。因为穷举所有的分词方法计算量太好,所以可以将她看做是一个动态规划问题,并利用维特比算法迅猛找到最佳分词。具体使用时还要考虑分词的颗粒度。

2. 拼音输入法

2.1 拼音输入法中的数学

中文输入法涉了盖当音节编码输入,到偏旁笔画拆字输入,再回归自然音节输入的历程。输入法输入汉字的进度取决于对汉字编码的平均长,也即是击键次数就以搜寻这键需要之日。单纯地减少编码长度未必能够增强输入速度,因为找一个键之辰会加强。

拿汉字输入到电脑中,是将人会看懂的消息编码变成计算机约定的编码(Unicode或UTF-8)的进程。对汉字的编码分为两片段:对拼音的编码和排(一口气多配)歧义。键盘上只是应用的是26只假名和10独数字键,最直接的艺术是为26个假名对诺拼音,用10单数字消除歧义性。只有当半只编码还缩水时,汉字的输入才能够转移快。早期的输入法常常独自重第一部分如忽视第二有些,例如双合输入法和五笔输入法。

诸一个拼音对承诺多独汉字,把一个拼音串对应之汉字由左向右连起来,就是一致布置有于图,如下图所展示,y1,y2,y3…凡是输入的拼音串,W11,W12,W13凡率先个音的候选汉字(后面的文字描述用W1代替),以此类推。从第一只字到最终一个配可以做很多句,每个词对应图备受的相同长达路线。

766net必赢亚洲手机版 5

拼音输入法虽是只要基于上下文在给定的拼音条件下找到最好妙的句子,即求

766net必赢亚洲手机版 6

(Arg是argument的缩写,Arg Max为获最好酷价值的音信错)
化简这个概率需要采取寓马尔可夫模型(见2.2介绍),我们拿拼音串看成能体察到的“显状态”,候选汉字作“隐状态”,然后要于这“显状态”下的“隐状态”概率。带入下文中之涵盖马尔可夫模型公式(2.3),式(2.1)化简为:

766net必赢亚洲手机版 7

化简连乘, 需要用等式两止取对屡次得

766net必赢亚洲手机版 8

乘法变成了加法。我们定义两单词中的离开

766net必赢亚洲手机版 9

这样,寻找最充分概率问题成了搜寻最好差路径问题。

2.2 隐含马尔可夫模型

上文介绍过马尔可夫假设(研究随机过程被之一个如果),即在随心所欲状态序列中,假而中的一个状态就给前一个状态有关。如天气预报,假设今天之天只有和昨天关于,这样即使能够得近似解:

766net必赢亚洲手机版 10

766net必赢亚洲手机版 11

马尔可夫链

顺应这只要的肆意过程叫马尔可夫过程,也给马尔可夫链。隐含马尔可夫模型是马尔可夫链的一个扩大:任意时刻t的状态St是不可见的,但当每个时刻会输出Ot,
Ot仅与St相关,这吃独立输出使,数学公式如下:

766net必赢亚洲手机版 12

P(Ot|St)我们可以通过观察得到。

766net必赢亚洲手机版 13

隐马尔可夫模型

缓解问题便是经既知求未知,我们设通过观察到$o_t$求出$s_t$的概率,即求

766net必赢亚洲手机版 14

出于标准概率公式可得:

766net必赢亚洲手机版 15

盖观察到的状态O一旦产生就非会见变换了,所以她是一个不过忽略的常数,上式可以化简为

766net必赢亚洲手机版 16

因为

766net必赢亚洲手机版 17

766net必赢亚洲手机版 18

仪式(2.2)可以化简为

766net必赢亚洲手机版 19

3.信息论:信息的心路和作用

3.1 信息熵

香农以外的论文“通信的数学原理”[想到牛顿的“自然哲学与数学原理”],提出了信息熵(shang),把信息及数字联系起来,解决了音之量,并量化起消息的打算。

同等条消息的信息量和其的不确定性正相关,信息熵约等于不醒目的粗。香农给有之信熵公式为

766net必赢亚洲手机版 20

P(x)为x的概率分布。

信息熵的公式为什么获得负数?因为概率小于1,小数求得的对数是负数,给通公式加上负号,最终的结果为刚。

脚举例说明信息熵公式为什么会因此到log和几率。

中世界杯冠军需要多少次?
足球世界杯共32只球队,给他俩编号1-32声泪俱下,第一破猜冠军是不是当1-16如泣如诉中,如果对了即会接着猜是否以1-8号,如果错了就知晓冠军在9-16声泪俱下,第三不好猜是否当9-12如泣如诉,这样只是待5不良就可知打中,log32
= 5。这里运用的是赔本半找寻,所以取对数。

而是实则状况不欲猜5不成,因为球队有强弱,可以优先拿夺冠热门分一组,剩下的划分一组,问冠军是不是在热组中,再累这进程,按照夺冠概率对剩下的球队分组。引入概率就见面被寻找数还不见,也便是免引人注目更粗,信息熵更小。可以测算,当各国开球队夺冠概率相等时(1/32),信息熵的结果吗5。

3.2 条件墒:

假定X和Y是有限独随机变量,X是我们如果打听之,已知X的随意分布P(X),于是X的熵为:

766net必赢亚洲手机版 21

如果我们还知道Y的片气象,包括其跟X一起出现的票房价值,即联合概率分布,以及在Y取不同值前提下X的概率分布,即准概率分布,于是当Y条件下X的尺度熵为:

766net必赢亚洲手机版 22

而是证明H(X|Y) <H(X), 即引入相关消息后,不确定性下降了。

3.3 互信息

信息里的相关性如果量呢?
香农提出了所以互信息度量两只随机事件之相关性。例如,“好闷热”和“要下雨了”的并行信息大高。
X与Y的互相信息公式如下:

766net必赢亚洲手机版 23

由此演算,可获得

766net必赢亚洲手机版 24

设出足的语料库,P(x,y), P(x) 和P(y)凡是殊容易计算的。

机翻译受尽难以的一定量个问题之一是二义性,如Bush
既可以是总统布什,也得以是灌木丛,Kerry既好是国务卿克里,也足以是有点母牛。如何科学的翻?一种植思路是由此语法辨别,但意义不好;
另一样栽思路是用互信息,从大量文件中找来同管布什同出现的辞藻,如总统、美国、国会等,再就此平等的计寻找有同灌木一起出现的歌词,如土壤、植物等,有了就有限组词,在翻译Bush时,看看上下文中哪类词又多便可了。

3.4 相对熵/交叉熵

相对熵(KL Divergence),衡量两单取值为刚之函数的相似性:

766net必赢亚洲手机版 25

结论:

  1. 鲜独了相等的函数,相对熵为零星;
  2. 相对熵越大,两单函数差异越充分。
  3. 于概率分布函数,或者概率密度函数,相对熵可以度量两个随机分布之差异性。

当自然语言处理中,常用相对熵计算两单常因此词在不同文本中之概率分布,看他俩是否同样;或者根据两首文章被不同词之布,衡量其的内容是否等。利用相对熵,可以博信息搜索中不过重大之定义:词频率-逆向文档频率(TF-IDF),在末端的物色章节会对它们详细介绍。

4. 搜索

4.1 获取网页:网络766net必赢亚洲手机版爬虫

拿整个互联网作为一布置大图,每个网页就是祈求备受之一个节点,超链接是接二连三节点的弧。通过网爬虫,用图的遍历算法,就可知自行地访问到每个网页并拿她存起来。

网爬虫是这么工作:假定从一家门户网站的首页出发,先下充斥者网页,再通过是网页分析产生其中富含的保有超链接,接下去访问并下载这些超链接指向的网页。让电脑不同地开下去,就会下载整个互联网。
还用用一个记事本(哈希表)记录下载了争网页避免重新下载。

工实现问题:

  1. 遍历算法采用广度优先或深度优先?
    搜索引擎要做到以少的日子内,最多地爬下最为要之网页。显然各个网站极度要的凡它们的首页,那么即便活该先行下充斥具网站的首页。如果将爬虫再扩充一点,就要连续下载首页直接链接的网页,因为这些网页是网站设计者自己觉得相当关键的网页。在此前提下,似乎应当使广度优先。

而是还要考虑网络通信的“握手”问题。网络爬虫每次访网站服务器时,都要经过“握手”建立连接(TCP协议),如果运用广度优先,每个网站先轮流下载所有首页,再回过头来下载第二级网页,这样即便如频繁的拜会网站,增加“握手”耗时。

事实上的大网爬虫是出于多雅服务器组成的分布式系统,由调度体系控制网页下载的顺序,对于有网站,一般是出于特定的一样令抑几乎令服务器专门下载,这些服务器先下充斥了一个网站还上下一个网站,这样可以减少握手次数(深度优先)。具体到每个网站,采用广度优先,先下充斥首页,再下充斥首页直接链接的网页。

  1. 页面分析和超链接(URL)提取
    初的网页都是直用HTML书写,URL以文件的形式在网页中,前后起醒目标识,很易提取出来。但现在广大网页都是为此脚本语言(如JavaScript)生成,URL不是直可见的文件,所以网络爬虫要学浏览器运行网页后才能够博取隐含的URL,但为数不少网页的本子写的不正规,很麻烦解析,这就是招致这样的网页无法为搜引擎收录。

  2. 保安超链接哈希表
    在同玉服务器上树立和掩护一摆哈希表并无是难事,但如同时发出诸多令服务器一起下载网页,维护一布置联合的哈希表就会赶上许多问题:

先是,这张哈希表会死至存不下;其次,每令服务器下载前跟下载后还使顾哈希表,于是哈希表服务器的通信就成为了全部爬虫系统的瓶颈。解决办法是:明确分工,将某区间的URL分给一定的几宝服务器,避免有服务器对同一个URL做判定;批量打探哈希表,减少通信次数,每次换代一深批判哈希表的始末。

4.2 网页搜索:布尔代数

最简易的目录结构是故一个格外丰富之亚向前制数表示一个关键字是否在每个网页遭到,有微只网页就生小位数,每一样各项对应一个网页,1象征相应的网页有这要字,0代表没有。比如重大字“原子能”对应之次向前制数是0100
1000 1100
0001…表示(从左到右)第二、第五、第九、第十、第十六个网页包含这个重要字。假定关键字“应用”对应之次前进制数是0010
1001 1000
0001…,那么只要找到并且涵盖“原子能”和“应用”的网页经常,只需要以即刻简单只伯仲迈入制数进行布尔AND运算,结果是0000
1000 0000 0001…表示第五以及第十六个网页满足要求。
这个次前进制数非常丰富,但是电脑做布尔运算非常快,现在极有益的微处理器,在一个命周期进行32位布尔运算,一秒钟十亿不行以上。

为保对其它搜索还能提供相关网页,主要的索引擎都是本着所有词进行索引,假如互联网上闹100亿个发含义之网页,词汇表大小是30万,那么这个目录至少是100亿x30万=3000万亿。考虑到多数底歌词只有出现于一些文件中,压缩比是100:1,也是30万亿底量级。为了网页排名方便,索引中还要抱其他附加信,如每个词起的职位,次数等等。因此总体索引就换得大特别,需要经过分布式存储到不同服务器上(根据网页编号划分也多小块,根据网页根本建立重要索引和非重要索引)。

4.3 度量网页和询问的相关性:TF-IDF

咱为寻找包含“原子能的采取”网页举例,“原子能的使用”可以分为三个基本点词:原子能、的、应用。凭直觉,我们以为包含这三只主要词比多的网页,比包含它们于少之网页相关。但随即并无长,因为这样的话,内容丰富之网页比内容短的网页占好,所以只要因网页长度对根本词的次数进行归一化,用要词之次数,除以网页的毕竟字数,这个商叫做“关键词之效率”或“单文本频率”(TF:Term
Frequency)。比如,某个网页上发出1000歌词,其中“原子能”“的”“应用”分别出现了2不好、35不好、5不良,那么它的词频就是0.002、0.035、0.005,将即刻三独数相加就是对应网页和询问“原子能的用”的单文本频率。所以,度量网页和询问的相关性,一个简短的办法就是是直接运用各个显要词在网页中冒出的总频率。

可及时为有不规范的地方,例如地方的例证中,“的”占了究竟词频的80%之上,但是她对规定网页的主题几乎没什么用,我们给这么的乐章为平息词(stop
word),类似之还有“是”“和”等。
另外“应用”是坏常见的乐章,而“原子能”是专业词,后者以相关性排名受比较前者主要。因此用为每个词让一个权重,权重的设定满足个别单原则:

  1. 一个乐章预测主题的力尤为强,权重就更充分;
  2. 停止词权重呢零星。

每当信搜索中,使用最多的是“逆文本频率指数”(IDF:Inverse Document
Frequency),公式为

766net必赢亚洲手机版 26

(D是全部网页数,Dw为重中之重词w出现的网页个数)。最终确定询问相关性,是运用TF和IDF的加权求和。
(IDF其实是当特定条件下要词概率分布的交叉熵)

4.4 搜索结果页排序:Page Rank算法

眼看是拉里·佩奇及谢尔盖·布林发明的计算网页自身质量的数学模型,google凭借该算法,使搜索的相关性有了抵押的迅猛,圆满解决了往摸索页中排序不好的题材。该算法的核心思想为:假如一个网页为不少任何网页所链接,说明它接受普遍的肯定与相信,那么其的排行就高。当然,在切实可行行使被还要长权重,给排名高之网页链接更胜之权重。这里发出一个格外圈,计算找结果网页排名过程被待用到网页本身的排名,这不是“先有鸡还是预先有蛋的题目”吗?
谢尔盖·布林解决了是问题,他把这个题材变成了一个二维矩阵题目,先要所有网页排名一样(1/N),在冲是新开始值持续迭代排名,最后能消退到实在排名。

4.5 新闻分类:余弦定理

google有新闻频道,里面的始末是由电脑聚合、整理并分类各网站内容。以前门户网站的情节是由编辑在念懂之后,再冲主题分类。但是电脑从读不亮新闻,它仅仅会计算,所以若让电脑分类新闻,首先将拿文字变成可计算的数字,再规划一个算法来计量任意两首新闻的相似性。

算算同一首新闻被负有实词的TF-IDF值,再将这些价值按照相应的实词在词汇表的职务依次排,就赢得一个向量。例如词汇表中产生64000单词,其编号与歌词要左下表所示,在某某平等篇新闻中,这64000单词的TF-IDF值如右下表所示,这64000只数就整合了一个64000维的向阳量,我们虽因故这个向量代表立即首新闻,成为当时篇新闻之特征向量。每篇新闻还发出一个特征向量,向量中之每个数代表对应的乐章对就首新闻主题的贡献。

766net必赢亚洲手机版 27

一律类的情报,一定某些主题词用的于多,两首相似的资讯,它们的特征向量一定当某个几乎单纬度的价值比较深。如果个别只向量的倾向平,就印证新闻之用词比例基本一致,我们以余弦定理计算两单为量间的夹角:

766net必赢亚洲手机版 28

快讯分类算法分为有目标及无对象:第一种植是既知道一些新闻类别的特征向量,拿其分别与所有待分类的资讯计算余弦相似性,并分割到相应的门类吃,这些既掌握之情报类特征向量既可以手工建立,也可以活动建立;
第二种是没分开好类的特征向量做参考,它应用自底向上的聚类方法,计算有所新闻两零星次的余弦相似性,把相似性大于一个阈值的资讯分作一个小类,再于各小类之间的余弦相似性,就如此持续用在联谊,一直顶有平近似为太非常如致中的资讯相似性很小时停。

发表评论

电子邮件地址不会被公开。 必填项已用*标注