数学之美读书笔记-图缺失

第一章

数字的发展:从原始人呜呜丫丫的语言,到中国和罗马的数字,到古印度发明的阿拉伯数字。

文字的发展:从象形文字,到楔形文字(古巴比伦,每个形状不同的楔子其实是一个不同的字母),到地中海腓尼基人简化为22个字母成为拼音文字。

信息的冗余是信息安全的保障。

语言的数据,称之为语料。

校验码:古犹太人抄写旧约《圣经》的时候要在每行和每列加一个校验码。

总结:语言和数字是信道编码的不同单位。语言是一种编码的方式,语言的语法规则是编解码的算法。

第二章

自然语言处理从基于语法语义分析到基于统计的演变。

第三章

马尔可夫:一个词Wi出现的概率只同它前面的Wi-1词有关

N-1阶马尔可夫假设:每个词和前面N-1个词有关

统计语言模型对于训练数据中没看见的模型(二元模型、三元模型等)的处理:降低低于某个出现阈值的组合的概率,把这些概率加到没有出现的组合上。

第四章:谈谈中文分词

以统计语言模型为基础,已经完善。

1518837227597-300x105

第五章:隐马尔可夫模型

生成概率:

标注的训练数据:

1518837320154-300x195

期望值最大化:鲍姆-韦尔奇算法的每一次迭代都是不断估计新的模型参数,使得输出的概率达到最大化。

隐马尔可夫:
1518838082267-300x103

1518838093204-300x131

第六章:信息的度量和作用

信息熵:

变量的不确定性越大,信息熵就越大。对不确定性的衡量。

条件熵:

???why?

X和Y的互信息:

所谓两个事件量化度量,是在了解其中一个Y的前提下,对消除另一个X不确定性所提供的信息量。

相对熵:衡量两个取值为正数的函数的相关性

词频率-逆向文档频率:TF-IDF

第七章:贾里尼克和现代语言处理

第八章:简单之美——布尔代数和搜索引擎的索引

第九章:图论和网络爬虫

定理:如果一个图能够从一个顶点出发,每条边不重复的遍历一遍回到这个顶点,那么每一顶点的度必然为偶数。

BFS or DFS?

第十章:PageRank——Google的民主表决式网页排名技术

然后需要用一种合适的数据结构表示页面间的连接关系。其实,PageRank算法是基于这样一种背景思想:被用户访问越多的网页更可能质量越高,而用户在浏览网页时主要通过超链接进行页面跳转,因此我们需要通过分析超链接组成的拓扑结构来推算每个网页被访问频率的高低。最简单的,我们可以假设当一个用户停留在某页面时,跳转到页面上每个被链页面的概率是相同的。例如,上图中A页面链向B、C、D,所以一个用户从A跳转到B、C、D的概率各为1/3。设一共有N个网页,则可以组织这样一个N维矩阵:其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵(Transition Matrix)。下面的转移矩阵M对应上图:

然后,设初始时每个页面的rank值为1/N,这里就是1/4。按A-D顺序将页面rank为向量v:

注意,M第一行分别是A、B、C和D转移到页面A的概率,而v的第一列分别是A、B、C和D当前的rank,因此用M的第一行乘以v的第一列,所得结果就是页面A最新rank的合理估计,同理,Mv的结果就分别代表A、B、C、D新rank:

然后用M再乘以这个新的rank向量,又会产生一个更新的rank向量。迭代这个过程,可以证明v最终会收敛,即v约等于Mv,此时计算停止。最终的v就是各个页面的pagerank值。例如上面的向量经过几步迭代后,大约收敛在(1/4, 1/4, 1/5, 1/4),这就是A、B、C、D最后的pagerank。

第十一章:如何确定网页和查询的相关性

单文本词频:关键词的次数除以网页的总字数。

相关性:词频*权重

D(w):这个词在多少个文献中出现

TF(w):词频,这个词在这篇文献中出现的次数

权重IDF应该是log(D/Dw)

第十二章:地图和本地搜索的最基本技术——有限状态机和动态规划

导航的关键算法是图论中的动态规划

有限状态机:

1518861262259
WFST:加权的有限状态传感器。

第十三章:Google AK-47的设计者——阿米特·辛格博士

第十四章:余弦定理和新闻的分类

把文章中的词用向量表示,两篇文章的相似度可以用两个向量的余弦值表示。

第十五章:矩阵运算和文本处理中的两个分类问题

两个分类问题:将文本按主题归类,将词汇表中的字词按意思归类。

文本间相似度用两个向量的夹角:a·b/|a|*|b|

我们希望有一个方法一次就能把所有的新闻相关性计算出来。

但是矩阵太大的时候需要做奇异值分解:

1519010998699

X是对词进行分类的一个结果,每一行表示一个词,每一列表示一个语义相近的词类,或者简称语义类,这一行的每个非零元素表示这个词在这个语义类中的重要性。???

Y是对文本的分类结果,每一列对应一个文本,每一行对应一个主题。

B表示词的类和文章的类的相关性。

(摘抄:三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一列表示一类主题,其中的每个非零元素表示一个主题与一篇文章的相关性,数值越大越相关。最后一个矩阵Y中的每一列表示100个关键词,每个key word与500,000个词的相关性。中间的矩阵则表示文章主题和keyword之间的相关性。因此,我们只要对关联矩阵A进行一次奇异值分解, 我们就可以同时完成了近义词分类和文章的分类。(同时得到每类文章和每类词的相关性))

矩阵分解的步骤:将矩阵A换成一个双对角矩阵,将双对角矩阵变成奇异值分解的三个矩阵。

小结:实际工作中可以先进行奇异值分解得到粗分类结果,再利用计算向量余弦的方法,在粗分类结果的基础上进行几次迭代,得到比较精确的结果。

第十六章:信息指纹及其应用

信息指纹重复的可能性很小

相似哈希

第十七章:由电视剧《暗算》所想到的——谈谈密码学的数学原理

对Y进行加密:

1.找到两个很大的素数P和Q,计算乘积:

N=P*Q

M=(P-1)*Q-1

2.找一个和M互素的整数E

3.找一个整数D使得E*D mod M = 1

E是公钥,D是私钥。密码Y是

解密:根据费尔玛小定理有

评论:https://www.douban.com/note/232094256/

作者在这里用的是欧拉定理?

欧拉定理摘抄:http://blog.csdn.net/update7/article/details/70943545

欧拉函数φ

欧拉定理是用来阐述素数模下,指数同余的性质。

欧拉定理:对于正整数N,代表小于等于N的与N互质的数的个数,记作φ(N)

例如φ(8)=4,因为与8互质且小于等于8的正整数有4个,它们是:1,3,5,7

欧拉定理还有几个引理,具体如下:

①:如果n为某一个素数p,则φ(p)=p-1;

①很好证明:因为素数p的质因数只有1和它本身,p和p不为互质,所以φ(p)=p-1;

②:如果n为某一个素数p的幂次,那么φ(p^a)=(p-1)*p^(a-1);

②因为比p^a小的数有p^a-1个,那么有p^(a-1)-1个数能被p所整除(因为把1~p^a-1的p的倍数都筛去了)

所以φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)

③:如果n为任意两个数a和b的积,那么φ(a*b)=φ(a)*φ(b)

③因为比ab小的数有ab-1个,条件是a与b互质

那么可以知道,只有那些既满足a与其互质且既满足b与其互质的数满足条件。

根据乘法原理,这样的数可以互相组合,那么就有φ(a)*φ(b)个

所以可以得知φ(a*b)=φ(a)*φ(b) (注意条件必须满足a和b互质)

④:设n=(p1^a1)(p2^a2)……*(pk^ak) (为N的分解式)

那么φ(n)=n*(1-1/p1)(1-1/p2)……*(1-1/pk)

④因为各个分解完的p1、p2、……pk均为素数,所以它们均为互质的

每次再刨去它们本身,乘起来

剩下的运用容斥原理,再根据引理②和引理③就可以得出

欧拉定理:a^(φ(m))同余1(mod m) (a与m互质)

欧拉函数的线性筛法—————————————-

大家都知道素数的线性筛法吧,欧拉函数也有线性筛法,可以在线性时间内求出1~N的所有φ

有以下三条性质:

①:φ(p)=p-1

②:φ(pi)=pφ(i) (当p%i==0时)

③:φ(p*i)=(p-1)*φ(i) (当p%i!=0时)

那么筛法基本与素数筛相同。

欧拉定理:

在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则:

???不太严谨

第十八章:闪光的不一定是金子——谈谈搜索引擎反作弊问题

第十九章:谈谈数学模型的重要性

第二十章:不要把鸡蛋放到一个篮子里——谈谈最大熵模型

最大熵:保留全部的不确定性,将风险降到最低。

GIS、IIS

假定搜索需要的排序需要考虑20种特征,{x1,x2,…,x20},需要排序的网页是d,假设特征互相独立,对应的最大熵模型是:

1519025010789

第二十一章:拼音输入法的数学原理

线性插值

第二十二章:自然语言处理的教父马库斯和他的优秀弟子们

第二十三章:布隆过滤器

1519027979386

第24章:马尔可夫链的扩展——贝叶斯网络

贝叶斯网络,又称有向无环图模型(DAG),是一种概率图模型,根据概率图的拓扑结构,考察一组随机变量{X1,X2…Xn}及其n组条件概率分布(CPD)的性质。

一般而言,贝叶斯网络的有向无环图中的节点表示随机变量,它们可以是可观察到的变量,或隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有因果关系(或非条件独立)。若两个节点间以一个单箭头连接在一起,表示其中一个节点是“因(parents)”,另一个是“果(children)”,两节点就会产生一个条件概率值。

每个结点在给定其直接前驱时,条件独立于其非后继。

652224-20160505093551701-2134454968

扩展阅读:https://www.jianshu.com/p/55755fc649b1

第26章:维特比和他的维特比算法

参考知乎:

作者:李大雷
链接:https://www.zhihu.com/question/20136144/answer/37291465
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

尝试用高中概率知识去理解一下 Veterbi 算法。内容绝对粗浅,100% 抄袭,欢迎指正。用一个别人家的栗子来说一下。

1.题目背景:

从前有个村儿,村里的人的身体情况只有两种可能:健康或者发烧。
假设这个村儿的人没有体温计或者百度这种神奇东西,他唯一判断他身体情况的途径就是到村头我的偶像金正月的小诊所询问。
月儿通过询问村民的感觉,判断她的病情,再假设村民只会回答正常、头晕或冷。
有一天村里奥巴驴就去月儿那去询问了。
第一天她告诉月儿她感觉正常。
第二天她告诉月儿感觉有点冷。
第三天她告诉月儿感觉有点头晕。
那么问题来了,月儿如何根据阿驴的描述的情况,推断出这三天中阿驴的一个身体状态呢?
为此月儿上百度搜 google ,一番狂搜,发现维特比算法正好能解决这个问题。月儿乐了。

2.已知情况:

隐含的身体状态 = { 健康 , 发烧 }

可观察的感觉状态 = { 正常 , 冷 , 头晕 }

月儿预判的阿驴身体状态的概率分布 = { 健康:0.6 , 发烧: 0.4 }

月儿认为的阿驴身体健康状态的转换概率分布 = {
健康->健康: 0.7 ,
健康->发烧: 0.3 ,
发烧->健康:0.4 ,
发烧->发烧: 0.6
}

月儿认为的在相应健康状况条件下,阿驴的感觉的概率分布 = {
健康,正常:0.5 ,冷 :0.4 ,头晕: 0.1 ;
发烧,正常:0.1 ,冷 :0.3 ,头晕: 0.6
}
阿驴连续三天的身体感觉依次是: 正常、冷、头晕 。

3.题目:

已知如上,求:阿驴这三天的身体健康状态变化的过程是怎么样的?

4.过程:

根据 Viterbi 理论,后一天的状态会依赖前一天的状态和当前的可观察的状态。那么只要根据第一天的正常状态依次推算找出到达第三天头晕状态的最大的概率,就可以知道这三天的身体变化情况。
传不了图片,悲剧了。。。
1.初始情况:

  • P(健康) = 0.6,P(发烧)=0.4。

2.求第一天的身体情况:
计算在阿驴感觉正常的情况下最可能的身体状态。

  • P(今天健康) = P(正常|健康)*P(健康|初始情况) = 0.5 * 0.6 = 0.3
  • P(今天发烧) = P(正常|发烧)*P(发烧|初始情况) = 0.1 * 0.4 = 0.04

那么就可以认为第一天最可能的身体状态是:健康。
3.求第二天的身体状况:
计算在阿驴感觉冷的情况下最可能的身体状态。
那么第二天有四种情况,由于第一天的发烧或者健康转换到第二天的发烧或者健康。

  • P(前一天发烧,今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(冷|发烧) = 0.04 * 0.6 * 0.3 = 0.0072
  • P(前一天发烧,今天健康) = P(前一天发烧)*P(发烧->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
  • P(前一天健康,今天健康) = P(前一天健康)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 = 0.084
  • P(前一天健康,今天发烧) = P(前一天健康)*P(健康->发烧)*P(冷|发烧) = 0.3 * 0.3 *.03 = 0.027

那么可以认为,第二天最可能的状态是:健康。
4.求第三天的身体状态:
计算在阿驴感觉头晕的情况下最可能的身体状态。

  • P(前一天发烧,今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(头晕|发烧) = 0.027 * 0.6 * 0.6 = 0.00972
  • P(前一天发烧,今天健康) = P(前一天发烧)*P(发烧->健康)*P(头晕|健康) = 0.027 * 0.4 * 0.1 = 0.00108
  • P(前一天健康,今天健康) = P(前一天健康)*P(健康->健康)*P(头晕|健康) = 0.084 * 0.7 * 0.1 = 0.00588
  • P(前一天健康,今天发烧) = P(前一天健康)*P(健康->发烧)*P(头晕|发烧) = 0.084 * 0.3 *0.6 = 0.01512

那么可以认为:第三天最可能的状态是发烧。

5.结论

根据如上计算。这样月儿断定,阿驴这三天身体变化的序列是:健康->健康->发烧。

https://en.wikipedia.org/wiki/File:Viterbi_animated_demo.gif

第27章:再谈文本分类问题——期望最大化算法EM算法:最大化期望:有一些训练数据,然后定义一个最大化函数。

第28章:逻辑回归和搜索广告

逻辑回归:一种将影响概率的不同因素结合在一起的指数模型,可以采用通用迭代算法GIS和改进的迭代算法IIS实现。

一个简单的逻辑回归模型如下:

第29章:各个击破算法和google云计算的基础

MapReduce和分治算法。
MapReduce:将一个大任务拆分成小的子任务。

comments powered by Disqus