加载中…
个人资料
大蒜开门
大蒜开门
  • 博客等级:
  • 博客积分:0
  • 博客访问:75,938
  • 关注人气:7
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

《数学之美》读书笔记(二)

(2012-06-30 01:34:43)
标签:

机器学习

密码算法

自然语言处理

信息论

互联网

搜索算法

it

分类: 数据分析

Chapter.5 隐马尔可夫模型

1.通信的本质是一个编解码和传输的过程。

2.通信六要素:发送者,信道,接受者,信息,上下文,编码

3.随机过程----随机变量的时间序列;马尔科夫链----马尔科夫假设下的随机过程

4.隐马尔可夫模型:任意时刻t的状态st不可见,,没法通过观察到一个状态序列S1S2....ST来推测转移概率等参数,但每个时刻t会输出一个仅和st相关的符号ot

5.隐马尔可夫模型三个基本问题:

5.1.给定一个模型,如何计算某个特殊输出序列的概率-----Forward--Backward算法

5.2.给定一个模型和某一个特定输出序列,如何找到最可能产生这个输出的状态序列----维特比算法

5.3.给定足够量的观测数据,如何估计隐马尔可夫模型的参数(各个转移概率,生成概率)----模型训练问题

6.无监督训练算法---鲍姆-韦尔奇算法---通过迭代找到期望概率最大化的模型(但结果可能是局部而非全局最优)

7.隐马尔可夫模型作为机器学习的模型工具之一,使用时需要一个训练算法(鲍姆-韦尔奇)和使用时的解码算法(维特比)

Chapter.6 信息的度量和作用

1.一条信息的信息量就等于其不确定性(熵)(越是不确定的事物越是要大量信息去说明),以比特为衡量单位;信息是消除不确定性的唯一方法

2.几乎所有自然语言处理,信息与信号处理的应用都是一个消除不确定性的过程

3.合理利用信息,而不是玩弄什么公式和机器学习算法,是做好搜索的关键。

4.信息熵---用信息比特数的先验概率加权和

5.两个随机事件X,Y的互信息为随机事件X的信息与XY条件信息之差,即衡量了了解Y的条件能为减少X的不确定性所能提供的信息量。互信息可用于解决词义的二义性。

6.相对熵用来衡量两个取值为正数的函数的相似性,其中:

6.1.两个完全相同的函数相对熵等于零

6.2.相对熵的大小好两个函数的差异成正比

6.3.相对熵可以度量两个随机分布的差异性,但需满足其概率分布或概率密度函数取值大于零

7.相对上的应用:

7.1.衡量两个词 在不同文本中的概率分布以判别它们意思是否相近。

7.2.根据两篇文章中不同词的分布判断它们内容的相似性。

7.3.得到词频率---逆向文档频率(TF-IDF)

Chapter.7 贾里尼克和现代语言处理

Chapter.8 布尔代数与搜索引擎的索引

1.搜索引擎所用做的工作:自动下载尽可能多的网页,建立快速有效的索引,根据相关性对网页进行公平准确的排序

2.布尔代数---二进制逻辑运算

3.布尔代数对数学的意义类似量子力学对物理学的意义,它将对世界的认识从连续状态扩展到离散状态

Chapter.9 图论和网络爬虫

1.离散数学:数理逻辑,集合论,图论,近世代数

2.遍历算法包括:(广度优先算法BFS:走完一个节点的所有弧再继续深入;深度优先算法DFS:一条线走到底再回头寻找没去过的节点)

3.网络爬虫:从任何一个网页出发,用图的遍历算法,自动的访问到每一个网页并把它们存起来。

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

5.握手:下载服务器和网站服务器建立通信的过程

Chapter.10 pagerank---网页排名技术(加权的民主投票制,用于度量网页质量)

1.某个查询的搜索结果排名取决于两组信息:关于网页的质量信息;此查询和每个网页的相关信息

2.如果在矩陣中,多數的元素並沒有資料,稱此矩陣為稀疏矩陣(sparse matrix),由於矩陣在程式中常使用二維陣列表示,二維陣列的大小與使用的記憶體空間成正比,如果多數的元素沒有資料,則會造成記憶體空間的浪費,為 此,必須設計稀疏矩陣的陣列儲存方式,利用較少的記憶體空間儲存完整的矩陣資訊。

Chapter.11 如何确定网页和查询内容的相关性

1.TF-IDF法,利用逆文本频率指数(关键词在总文本中的比例的对数)加权的特定网页关键词词频度量关键词在此特定网页中的相关性

Chapter.12 地图和本地搜索(用移动客户观进行的当地搜索)的最基本技术-----有限状态机和动态规划

1.关键技术:卫星定位;地址识别;路径规划

2.有限状态机是一个特殊的有向图,包括一些状态节点和连接这些节点的有向弧(每一条弧上带有状态1到状态2所需的条件),用于地址识别的上下文分析

3.模糊匹配问题的解决总是依靠马尔科夫链

4.动态规划:分段分步求解局部最小路径从而达到全程最小路径

5.加权的有限状态传感器WFST,其每一个状态由输入和输出符号定义,根据输入和输出可能性的不同赋以权重。WFST中的每一条路径就是一个候选的句子,其中概率最大的那条路径就是句子的识别结果。

Chapter.13 阿米特.辛格博士

1.先帮助用户解决80%的问题,再慢慢解决剩下的20%问题,是在工业界成功的秘诀之一。简单方案容易解释每一个步骤和方法背后的道理,这样不仅便于除了问题debug,而且容易找到今后改进的目标。

Chapter.14 新闻搜索和余弦定理

1.新闻分类原理:先把文字的新闻变成可以计算的一组数字(将新闻转化成成每个词的TF-IDF值的向量),然后再设计一个算法算出任意两篇新闻的相似性

2.向量方向越一致则新闻之间的用此比例越相似,因此余弦定理在新闻搜索中起到了巨大的作用

Chapter. 15 矩阵运算和文本处理中的两个分类问题

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

2.酉矩阵:它和它的共轭矩阵转置相乘等于单位阵

3.矩阵的奇异值分解:Amn=Xmm*Bmn*Ynn,其中X,Y为酉矩阵,B为对角阵

4.奇异值分解分类法相对于余弦定理计算次数大幅降低---计算速度大大加快,但需要一个更大的存储量,且分类结果略显粗糙

Chapter.16 信息指纹及其应用

1.信息指纹不可逆,既无法根据它推出原有信息。

2.用信息指纹判断集合是否相同可大大减少运算量(且不占用额外的储存空间)

3.一个视频文件虽然每秒有数帧的图像,但只有极少数帧的图像是完整的,这些被称为关键帧,其余帧存储的只适合关键帧相比的差异值。

Chapter.17 密码学的数学原理

1.密码的最高境界是敌人在截获密码后,对我方的信息量并没有增加。当密码之间分布均匀且独立统计时,提供的信息量最少。均匀分布使敌人无从统计,独立统计保证密文不会被一并破译。

2.密钥原理:

2.1.找两个很大的素数PQ,越大越好,然后计算它们的乘绩:N=P*Q;M=(P-1)*(Q-1)

2.2.找一个和M互素的整数E(EM最小公约数为1

2.3.找一个整数D,使E*D/M1,即E*D mod M=1

2.4.其中E是公钥,谁都可以用来加密,D是私钥用于解密,一定要保存好,乘积N是公开的,被人知道也无所谓

2.5.X加密得到Y----X^(E) mod N=Y

2.6.根据费马小定理,用如下公式解密  Y^(D) mod N=X

3.公开密钥保证产生的密文是统计独立而分布均匀的,更重要的是N,E可以给任何人加密用,但是只有掌握密钥D的人才能够解密;其破解方法是对N进行因式分解(穷举强算)

Chapter.18 搜索引擎反作弊问题

1.常见作弊方法:重复关键词,链接买卖

2.解决噪声干扰基本思路:从信息源出发,加强通信编码自身抗干扰能力;在传输中过滤掉噪音,还原信息

3.某些高端手机能识别接听环境下的噪音频率,并加上一个频率相同振幅相反的信号进行除噪,保证通话质量  

4.原始的信号混入了噪音,在数学上相当于给两个信号做卷积,噪音消除的过程就是一个解卷积的过程。

5.只要噪音不是完全随机且前后有相关性,就可以检测到并消除,而完全随机不相关的高斯白噪声是很难消除的。

6.在图论中定义,如果有几个节点两两都互相连接在一起,它们被称之为一个CLIQUE.     

Chapter. 19 数学模型的重要性

1.一个正确的数学模型应当在形式上是简单的

2.一个正确的模型在一开始可能不如一个精雕细琢过的错误模型来的准确,但认为大方向对时就应该坚持下去

3.大量准确的数据对研发很重要

4.正确的模型有可能受噪音的干扰,这是去寻找噪音的根源也许会通往一个重大的发现。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有