数学之美
2022-06-06 18:44:38 2 举报AI智能生成
吴军博士《数学之美》读书笔记，
作者其他创作
大纲/内容
十八：闪光的不一定是金子
搜索引擎中排名靠前的网页未必是有用的网页
搜索引擎中排名靠前的网页未必是有用的网页
搜索引擎的反作弊
采用不正当的手段提高自己网页的排名：重复关键字、买卖链接(针对PangRank)
反作弊的"术"：分析作弊的例子并清除 反作弊的道"：找到作弊的动机和本质
搜索引擎作弊的本质：对搜索排序的信息加入噪声。 反作弊第一条是增强排序算法的抗噪能力
搜索引擎作弊的动机：获利。 通过计算网页出链向量的余弦距离可以发现卖链接的网站
作弊的网站一般互相链接，在互联网这张大图形成Clique,图论有专门发现Clique的方法可以用于反作弊
搜索结果的权威性
PangRank和其他关于网页质量的度量方式都很难衡量搜索结果的权威性
“提及”，讨论“吸烟危害”的网页“提及”了“WHO”、“xxx研究所”，这些网页相对权威
十九：数学模型的重要性
托勒密发明了球坐标、定义了经纬线、提出了黄道、发明了弧度制
张衡的浑天说也是地心说，但张衡是中国人的骄傲，在历史书上当作正面宣传
托勒密的地心说模型被作为错误理论在历史书上加以批判
托勒密用40-60个在大圆套小圆的方法精确计算了所以行星运动的轨迹，即使现在的PC也很难解出40个套在一起的圆的方程
一个正确的数学模型形式上应该是简单的
哥白尼的日心说只用8-10个圆就能计算出一个行星的运动轨迹，但准确率不如地心说
一个正确的模型一开始可能还不如一个精雕细琢的错误模型
开普勒继承老师第谷的大量数据，凑巧用一个椭圆就能将星体运动规律描述清楚，但开普勒无法解释为什么行星的轨迹是椭圆
大量正确的数据很重要
牛顿的万有引力定律解释了为什么行星的运动轨迹是椭圆
1821年布瓦尔发现天王星轨迹和椭圆模型计算的不同，1861-1862，亚当斯和威内尔独立发现吸引天王星偏离轨道的海王星
正确的模型也可能收到噪声干扰，不要用凑合的修正方法，而要找到噪声的根源
二十：不要把鸡蛋放到一个篮子里
最大熵模型
最大熵模型
在信息处理中，有各种各样又不完全确定的信息，需要用一个统一的模型将这些信息综合起来
遇到不确定性时，就要保留各种可能性
最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不做任何主观假设。
在这种情况下，概率分布最均匀，预测风险最小，因为这时的概率分布的信息熵最大，这种模型叫最大熵模型
在这种情况下，概率分布最均匀，预测风险最小，因为这时的概率分布的信息熵最大，这种模型叫最大熵模型
对一组不自相矛盾的信息，最大熵模型存在且唯一
最大熵模型的训练：迭代算法GIS、改进迭代算法IIS
最大熵模型形式简单，实现复杂
二十一：拼音输入法的数学原理
中文输入法经历了一自然音节编码输入到偏旁字画拆字输入再回归自然音节输入的过程
输入法输入汉字的快慢取决于汉字编码的平均长度，即用击键次数乘以寻找这个键所需的时间
输入法与编码
对汉字的编码分为两部分：对拼音的编码和消除歧义性的编码
双拼输入法增加了编码上的歧义性：键盘只有26个字母键，汉语的声母和韵母有50多个，很多韵母不得不共享一个字母键
双拼比全拼增加了将读音拆成声母和韵母编码的过程，拆字的过程使思维变慢，增加击键时间
双拼对读音的容错性不好，大部分人对前鼻音和后鼻音，卷舌音和平舌音分不清
中文输入法总数一度达到上千种，从信息论上看这些方法水平相当不分优劣，看谁市场吹嘘做的好
这一代输入法的问题在于减少了击键次数，忽视了寻键时间
最后用户还是选择了每个汉字编码较长的全拼输入法
它不需要专门学习
输入自然，不会中断思维
编码长有信心冗余，容错性好
输入一个汉字要敲多少个键
香农第一定理指出：对于一个信息，任何编码长度都不小于它的信息熵
GB2312有6700个常用字，对各个字进行统计，不考虑上下文相关性，信息熵大约在10比特，26个字母键，
每个字母代表log26=4.7比特，因此每个汉字平均需要敲10/4.7=2.1次键
每个字母代表log26=4.7比特，因此每个汉字平均需要敲10/4.7=2.1次键
以词为单位统计信息熵不考虑词的上下文相关性，输入一个汉字平均需要敲8/4.7=1.7次键
考虑上下文相关性，建立基于词的统计语言模型，输入一个汉字需要敲6/4.7=1.3次键
拼音转汉字的算法
拼音转汉字的算法和导航中最找最短路径的算法相同，都是动态规划，
不同的是，导航中，节点(城市)之间是真实地距离，拼音串转汉字的网络图中，节点(词)之间的距离是转移概率
不同的是，导航中，节点(城市)之间是真实地距离，拼音串转汉字的网络图中，节点(词)之间的距离是转移概率
二十二：自然语言处理的教父马库斯和他的弟子
自然语言处理从基于规则的研究转到基于统计的研究
贾里尼克
米奇-马库斯
LDC语料库
子主题
二十三：布隆过滤器
布隆过滤器的原理
储存一亿个地址
哈希表：将每个地址对应为一个8字节的信息指纹，然后将信息指纹存入哈希表，哈希表的存储效率只有50%，因此一个地址需要16字节，一亿个地址需要16亿字节，16.GB
布隆过滤器：先建立一个16亿个比特位，即2亿字节，见这些比特位全置零，对每个地址用8个不同的随机数产生器产生8个信息指纹，再用一个随机数产生器将8个信息指纹映射为1-16亿的8个自然数，将这8个位置的比特位置1
二十四：马尔科夫链的扩展
贝叶斯网络
每个圈表示一个状态，状态之间的连线表示它们的因果关系
假定这个图中马尔可夫假设成立，即每个状态只跟其直接相连的状态有关，而与它间接相连的状态没有直接关系，那么它就是贝叶斯网络
两个状态A和B之间没有直接的有向弧连接只说明它们没有直接的因果关系，不表明A不会通过其他状态影响状态B，即AB之间可能有间接关系
所以这些因果关系，都可以有一个量化的可信度，用概率描述，即贝叶斯网络的弧可以有附加的权重
每个弧都有一个可信度，贝叶斯网络也被称作信念网络
贝叶斯网络的训练过程：拓扑结构训练和状态间概率参数训练
应用：文本分类、概念抽取、决策支持、博弈论、生物统计、图像处理
二十五：文法分析、条件随机场
在HMM中，观察值序列在某时刻的结果xi只与该时刻产生它的隐状态yi有关，和前后隐状态yi-1,yi+1无关，
如果把xi和yi-1、yi、yi+1都考虑进来就构成条件随机场模型
如果把xi和yi-1、yi、yi+1都考虑进来就构成条件随机场模型
二十六：维特比和维特比算法
维特比算法是现在数字通信中最常用的算法，也是很多自然语言处理采用的解码算法
基于CDMA的3G移动通信标准就是维特比和雅各布创办的高通公司制定的
维特比算法是动态规划算法，运用动态规划算法可以解决图的最短路径问题
维特比算法是为特殊的图——篱笆网络的有向图最短路径问题提出的，凡是使用HMM描述的问题都可以用维特比算法解码
数字通信、语音识别、机器翻译、拼音转汉字、分词等
二十七：上帝的算法 期望最大化算法
文本的自收敛分类
随机挑选K个点，作为起始中心
计算所有点到这些聚类中心的距离，将这些点归到最近的一类中
重新计算每一类的中心
重复上述过程，知道新的中心和旧的中心之间的偏移非常小，即过程收敛
期望最大化
首先，根据现有模型(初始模型)计算各个观察数据输入到模型中的计算结果，这个过程称为期望值计算过程，E过程
接下来，重新计算模型参数，以最大化期望值，这个过程称为最大化过程，M过程
EM算法：HMM的训练方法鲍姆-维奇算法，最大熵模型的训练算法GIS
EM算法不能保证全局最优，若目标函数是凸函数，那么一定能保证得到全局最优解
二十八：逻辑回归和搜索广告
搜索广告的发展
第一阶段：按广告主出价高低来排名的竞价排名广告 Overture 百度
第二阶段：综合竞价和点击率预估CTR等因素来决定广告的投放 Google
第三阶段：全局优化
逻辑回归模型
逻辑回归模型是指将一个事件出现的概率逐渐适应到一天逻辑曲线上
逻辑回归的变量范围为-∞到+∞,而值域在0-1之间
[0,1]之间的函数可以是一个概率函数，这样逻辑回归函数就和概率分布联系起来
，x是特征向量，元素代表影响点击率预测的各种信息
二十九：各个击破算法和Google云计算的基础
分治算法的原理
将一个复杂的问题，分成若干简单的子问题进行解决，然后对子问题的结果进行合并，得到原问题的解
从分治算法到MapReduce
将一个大任务拆分成小的子任务，并且完成子任务的计算，这个过程叫Map，将中间结果合并为最终结果，这个过程叫Reduce
三十：Google大脑和人工神经网络
2011年底，Google发布一项新技术，基于深度学习的Google Brain
人工神经网路
结构：输入层、隐藏层、输出层；非线性激活函数
训练：损失函数、误差反向传播算法、梯度下降算法
三十一：区块链的数学原理
椭圆曲线加密
椭圆曲线加密
不对称、不透明之美
BlockChain：Block即模块、数据块，像一个存储信息的保险箱；Chain表示信息内容和交易的历史纪录
当一个比特币被创造出来时，记录其原始信息的区块链也就产生了，这个区块链里的信息无法篡改，可以添加流通和交易信息，无法覆盖原信息
区块链里的某些信息，外界可以确认其真伪，却无法知道其内容
区块链可以成为一种按照约定自动执行的智能合约，这种合约一旦达成就不能更改
椭圆曲线加密
椭圆曲线和椭圆没什么关系，它是具有如下性质的一组曲线：
这种曲线是上下对称的，从曲线上一点画直线，它最多和曲线有三个交点(包括该点本身)
从基点A出发，画一条线过B点，和曲线交于C点，记A.B=C，用C的镜像点D与A连线与曲线交于E点，重复K次到Z点，记KxA=Z
告诉你一开始从A经过B到C，一共K步，可以推出最后到Z，如果告诉你起点A终点Z，几乎不可能推算出K。 基点A 私钥K 公钥Z
三十二：大数据的威力
数据的重要性
人类的文明与进步，从某意义上讲是通过对数据进行收集、处理和总结而达成的
数据的统计与信息技术
科学的使用数据：统计学
统计首先要求数据量充足，统计样本数量不充分，统计数字毫无意义。切比雪夫不等式
统计要求样本具有代表性
数据带来的性能提升逐渐超过算法带来的性能提升
为什么需要大数据
如果说过去几十年里，主导全球IT产业发展的是摩尔定律，那么在今后的几十年里，主导IT产业发展的动力则来自数据
三十三：随机性带来的好处
量子密钥分发
量子密钥分发
量子通信并不是靠量子纠缠实现通信，而是靠光量子的偏振特性承载信息，靠数学和信息论保证他得保密性
三十四：数学的极限
图灵划定计算机可计算问题的边界
1.世界上是否所有的数学问题都有明确的答案
2.如果一个问题有答案，能否通过有限步的计算得到答案，反过来，如果一个问题没有答案，能否通过有限步的推演证实这件事
3.对于在有限步可计算的数学问题，能否有种机器解决这个问题
哥德尔不完全定理：数学不可能既是完备的又是一致的，即一些命题即使是对的，也无法用数学证明它们
希尔伯特划定有解数学问题的边界
希尔伯特第十问题：任意一个不定方程，能否通过有限步的运算，判定它是否存在整数解
马蒂亚塞维奇定理：除了极少数特例，在一般情况下，无法通过有限步的运算，判断一个不定方程是否存在整数解
第十问题的解决向世人宣告很多问题无从得知是否有解，如果连是否有解都不知道，就更不可能通过计算解决它们了
无法判定是否有解的问题，远比有答案的问题多得多
任何可以通过有限步逻辑运算和数学运算解决的问题，理论上都可以遵循一个设定，在图灵机上完成
能够用图灵机计算的问题称为可计算的问题
可计算的问题是有答案问题的一个子集，但是这一子集是否等同于"有答案问题"这一全集仍有争议
在理论上可计算的问题，在今天的工程上未必能够实现。一个问题虽然能够用图灵机在有限步解决，就认为是可计算的，但是这个有限步可以是很多步骤，计算时间可以特别长，长到宇宙灭亡都可以，即一个问题可计算，却永远算不完
所有问题->数学问题->可判定问题->有答案问题->可计算问题->工程可解问题->人工智能问题
今天，我们要担心的不是人工智能或计算机有多强大，更不应觉得它们无所不能，因为它们的边界已经清清楚楚地由数学的边界划定了
我们今天所遇到的问题是不知道怎样将一些应用场景转化为计算机能够解决的数学问题，整本《数学之美》其实讲的都是这件事
一：文字和语言vs数字和信息
信息
数字、文字和语言都是信息的载体，它们都是为了记录和传播信息
信息论之父香农提出信息论，人们才开始把数字和信息系统联系起来
原始人通信的方式和现在通信模型没什么不同：
信息源——编码——信道——解码——接收者
信息源——编码——信道——解码——接收者
文字和数字
文字
文字起源：语言和词汇多到一定程度，仅靠大脑无法记全，高效记录的需求产生了
文字的数量和记录一个文明所需的信息量相关
文明进步，信息量增加，文字不再增加，因为无法记住所有文字
开始对文字进行概括和归类（即一词多义），类似NLP聚类
聚类带来歧义性，依靠上下文去除歧义
罗塞塔石碑的翻译
(相同内容三种语言)
(相同内容三种语言)
不同文字系统在记录信息上的能力是等价的，即文字只是信息的载体而非信息本身
信息的冗余是信息安全的保障
语言的数据即语料对翻译至关重要
数字
数字是人类的财产多到需要数一数才搞清楚有多少的时候出现
数字是计数系统的基础，35000年前就有了计数系统：乐邦博骨
进位制的出现是人类文明的飞跃
几乎所有文明都采用十进制
玛雅文明采用二十进制，一个太阳纪400年，2012是这个太阳纪最后一年
阿拉伯数字，印度人发明
文字和语言背后的数学
楔形文字是最早的拼音文字，从象形文字到拼音文字体现了最短编码原理：常用字短生僻字长，或是笔画数不同
白话和文言文：信道宽信息不必压缩，信道窄信息尽可能压缩，古代文字书写不便，文字尽可能少写
二：NLP-从规则到统计
机器智能
字母、笔画、文字、数字都是信息编码的不同单位，任何语言都是一种编码方式，语言的语法规则是编解码的算法
计算机科学之父阿兰图灵：机器智能
达特茅斯夏季人工智能研究会议：1956，麦卡锡、明斯基、罗切斯特、香农、西蒙、纽维尔
机器翻译和语音识别不是靠计算机理解了自然语言才实现的，而是全靠数学
早期对自然语言的了解：句法分析和语义分析
复杂度太高
从规则到统计
20世纪70年代，基于规则的句法分析走到尽头
1970年统计语言学使nlp重获新生：弗里德里克-贾里尼克，现在自然语言处理的奠基者
三：统计语言模型
针对自然语言上下文相关性的数学模型
针对自然语言上下文相关性的数学模型
用数学的方法描述语言规律
一个句子合理与否看他是否合乎语法，词义是否清晰，早期的nlp沿这条技术路线研究
贾里尼克：一个句子是否合理，看它的可能性如何
马尔可夫假设：任意一个词的出现只和它前面的词有关 二元模型
只和前面N-1个词有关，称为N-1阶马尔可夫假设，对应的模型为N元模型，N<=4
只和前面N-1个词有关，称为N-1阶马尔可夫假设，对应的模型为N元模型，N<=4
四：分词
中文分词方法的演变
查字典法：扫描句子，遇到字典中的词就标识出来，遇到复合词就找最长的匹配，遇到不认识的字串分割为单字词
统计语言模型分词法：比较不同分词结果的概率，用维特比算法动态找出最佳分词
五：隐马尔科夫模型
连接自然语言处理与通信的桥梁
连接自然语言处理与通信的桥梁
通信模型
通信的本质就是一个编解码和传输的过程
雅各布森通信六要素：发送者（信息源）、信道、接收者、信息、上下文、编码
source = argmaxP(source|received)=argmaxP(received|source)*P(source)
隐马尔科夫模型
符合马尔可夫假设的随机过程称为马尔可夫过程，也称为马尔可夫链
HMM：任一时刻t的状态不可见，但会输出一个符号，只和有关，是一个马尔可夫链
HMM的训练
给定一个模型，如何计算某个特定的输出序列的概率：Forword-Backward算法
给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列：维特比算法
给定足够多的观察数据，如何计算HMM的参数（转移概率、生成概率）：鲍姆-维奇算法
六：信息的度量和作用
1948年香农在《通信的数学原理》提出信息熵
1948年香农在《通信的数学原理》提出信息熵
信息熵
一条信息的信息量与其不确定性有关，信息量等于不确定性的多少
信息熵的物理含义是对信息不确定性的度量
对任意一个随机变量X，其熵
变量的不确定性越大，熵越大，要搞清楚它所需的信息量越大
信息的作用
信息是消除系统不确定性的唯一办法
条件熵
H(X)>=H(X|Y)即增加Y的信息后，X的不确定性下降，若Y与X毫无关系，等式成立
互信息
量化两个随机事件的“相关性”
I(X,Y)=H(X)-H(X|Y)
交叉熵\相对熵\KL散度
相对熵也用来衡量相关性，但和变量的互信息不同，它用来衡量两个取值为正数的函数的相似性
相对熵越大，两个随机分布的差异越大
相对熵不对称
JS散度是对称，JS(f||g)=1/2[KL(f||g)+KL(g||f)]
七：贾里尼克和现代语言处理
八：布尔代数与搜索引擎
布尔元素：真和假 布尔运算：与或非
搜索引擎
自动下载尽可能多的网页
网络爬虫
建立快速有效的索引
很长的二进制数表示一个关键字是否出现在某篇文献中
根据相关性对网页进行公平正确的排序
PageRank
九：图论与网络爬虫
图由一些节点和连接节点的弧组成
广度优先搜索BFS
深度优先搜索DFS
若一个图能从一个顶点出发，不重复的遍历每条边回到该顶点，那么每一顶点的度必须为偶数
网络爬虫
网页看作节点，网页间的超链接看着连接网页的弧
用哈希表记录网页是否已经下载
十：PangRank
对于一个特定查询，搜索结果排名取决于两组信息
网页质量
PangRank核心思想：一个网页被很多其他网页所链接，说明它受到信赖，那么它的排名就高
网页排名向量B，网页链接数目矩阵A，
Google创始人拉里-佩奇因此算法在30岁当选美国工程院院士
该查询与每个网页的相关性
十一：网页与查询相关性
搜索关键词权重的科学度量TF-IDF
TF：关键词的次数/网页总字数
IDF：log(总网页数/出现关键词的网页数)
十二：有限状态机和动态规划
地图和本地搜索的核心技术
地图和本地搜索的核心技术
地址识别和有限状态机
有限状态机是一个特殊的有向图，包括一些状态(节点)和连接状态的有向弧
每个状态机都有一个开始和终止状态
如果一条地址能从开始状态经过若干中间状态走到终止状态，则这条地址有效
基于概率的有限状态机可以进行地址的模糊匹配，用于处理不标准的地址或错别字
全球导航和动态规划
寻找全程最短路线的问题分解成一个个寻找局部最短路线的小问题
十三：Google AK-47的设计者
阿米特-辛格
阿米特-辛格
十四：余弦定理和新闻分类
新闻的特征向量
对单词进行OneHot编码 或计算TF-IDF
向量距离的度量
计算两个向量的夹角， cosθ=<x1,x2>/|x1||x2|
十五：矩阵运算与文本处理中的两个分类问题
奇异值分解X=UEV
近义词的分类U
文章的分类V
每个主题与每个词之间的相关性E
十六：信息指纹及其作用
如果对一段信息进行无损压缩编码，理论上编码后的最短长度是它的信息熵
任何一段信息都可以对应一个不太长的随机数，作为区别这段信息和其他信息的指纹
只要产生随机数的算法设计的好，任意两段信息的指纹都很难重复
将不定长的信息映射为定成的128位或160位二进制随机数
伪随机数产生器算法PRNG、梅森旋转算法、MD5、SHA-1
采用128位二进制的MD5算法，每1800亿亿次随机数才重复一次
信息指纹是不可逆的，无法通过信息指纹推出原有信息
计算A和B的信息指纹 应用：爬虫判断网页是否已下载、集合相同的判定、抄袭判定、反盗版
十七：密码学的数学原理
密码学的自发时代
密码学的根本是信息论和数学，没有信息论指导的密码很容易破解
恺撒密码
加密过程看作一个函数的运算F，解密的过程是反函数的运算，
明码是自变量，密码是函数值，好的加密函数不应该通过几个自变量和函数值就能推出函数
明码是自变量，密码是函数值，好的加密函数不应该通过几个自变量和函数值就能推出函数
信息论时代的密码学
香农在为军方研究加密和解密(图灵)的过程中，提出了信息论
密码的最高境界是敌方截获密码后，对我方的所知没有任何增加，即信息量没有增加
一般地，当密码之间分布均匀且统计独立时，提供的信息最少
1976，Diffie和Hellman提出公钥和电子签名，成为互联网安全协议的基础
RSA算法、Rabin算法、ElGamal算法、椭圆曲线算法的共同点
它们都有两个完全不同的密钥，一个用于加密，一个用于解密
这两个看上去无关的密钥，在数学上是关联的
公开密钥在原理上是可靠的，但在工程实现上有漏洞，攻击者从攻击算法转而攻击实现方法
要破解公开密钥的加密方式，最彻底的方法还是对大数N进行因素分解，分解只有一个笨方法，就是“试”
世界上没有永远无法破解的密码，一种加密方法只要保证50年内计算机破解不了，就算满意的
0 条评论
下一页
