读完数学之美,收获很多,在这里我对我的收获进行简要的总结,这些总结中不包括对具体算法和模型的详解,详解请参考其他资料,这里只进行简要的总结。
文字、数字、语言和数学是天然的内在的联系。我们的祖先过去在处理问题、设计语言的时候遵循的法则和我们今天探求的研究方法背后有着共同的东西,那就是数学规律。
信息 —— 编码 ——> 信道 —— 解码 ——> 信息
任何一种语言都是一种编码方式,语言的语法规则就是编解码算法。
基于规则的句法分析很快走到了尽头:
只有基于有向图的统计模型才能很好的解决复杂的句法分析。
基于统计方法的核心模型:
通信系统 + 隐马尔科夫模型
如何衡量一个句子s在文本中出现的可能性- s在文本中出现的概率p(s)
s = w1 w2 w3 ... wm
p(s) = p(w1 w2 w3 ... wm)
= p(w1)*p(w2|w1)*p(w3)*p(w3|w1,w2)*...*p(wm|w1,w2,...,wm-1)
p(w1) 表示词w1出现的概率
p(w2|w1) 表示w2出现在w1之后的概率
p(w1)好统计, p(w2|w1) 也还好统计,但是p(wm|w1,w2,...,wm-1)无法统计!
马尔科夫提出了马尔科夫假设:
假设任意一个词wi出现的概率只与他前面的词wi-1有关
则有
s = w1 w2 w3 ... wm
p(s) = p(w1 w2 w3 ... wm)
= p(w1)*p(w2|w1)*p(w3)*p(w3|w2)*...*p(wm|wm--1)
对应的统计模型是二元模型 bi-gram
假设一个词的概率又他前面n-1个词共同决定,则成他为n元模型 n-gram
很多亚洲语言、中日韩泰等,还有手写的英语,需要一些手段将词分开。
后来使用基于统计的方法进行分词
分词准确性很难衡量,不能说这个达到95%准确率的分词器就好于另一个90%准确率的分词器。只能说它与人工分词的吻合度稍微高一些而已。
信息 —— 编码 ——> 信道 —— 解码 ——> 信息
利用贝叶斯条件概率公式,从收到的消息中,还原信源的真实信息。
模型的具体详情,这里不做讲述,需要参考其他资料。
一个系统,内部有很多个状态,这些状态我们不知道,但是我们能看到不同的观察序列。状态之间的转移有概率,每个状态发出哪个观察值也有概率。这样一个模型为隐含马尔科夫模型。
信息和不确定性有直接关系。如果要搞清楚一件非常不确定的事情,需要大量的信息。如果对事情了解比较多,则不需要太多的信息就能把他搞清楚。信息量就等于不确定性的多少。
香浓提出信息熵的概念,用来衡量信息量的多少。
信息熵的具体数学原理在这不多说,还需参考其他资料。
衡量事件的相关性。
在自然语言处理中,用来衡量语义的相关性。
用来衡量两个取值为整数的函数的相似性。
一个传奇科学家的一生的故事。向老师致敬!
三种运算: 与 或 非
就像擦字典一样, 需要先去查到这个字的页码,在去这个页看这个字的解释。
就像图书馆找书一样,需要先查到这本书在哪个货架哪个位置,再去这个位置找到这本书。
类似,关键词、网页之间建立起了索引,这种快速拿关键词去查找网页的技术运用了布尔代数来实现。
广度优先遍历
搜索引擎实际上是一个大图,每个网页都是一个结点,网页之间的超链接就是结点之间的弧。
通过爬虫,在网页的连接之间来回搜索网页,也就是对图进行尽量完全的遍历,来实现了搜索引擎的数据。
在这里,如果快速、不重复又完整的遍历所有网页是技术关键。
搜索引擎把什么搜索结果排在前面?什么排在后面?
一般来说,一个权威专家说, xxx 和xxx 是该领域的专家, 那么绝大多数人都会觉着一定是这样。
如果一个偷鸡摸狗的不良少年说xxx是一个专家,可能大家都会笑笑就过去了,并不会信以为真。
google rank 把所有网页(结点)和网页之间的链接(边)建立起联系。 不同的边有不同的权重,是对结点优先级的贡献程度。 权威一点的网站指向来的路径权重会稍大一些。 通过这样的数学模型,把网页的排序搞定了。
简而言之如上所述,但是实际上要复杂得多。 具体的数学模型这里不做叙述。
作者在这个章节讲了 TF-IDF作为一种度量,来衡量查询的关键词和检索出网页的语义相关性。
是一张图, 有开始状态和结束状态还有中间状态,所有状态都是结点,状态之间能转移,就有通路。这样一个图模型,为有限状态机。总能经过有限次状态转换从起始状态到终点状态。
可以用于文本的地址分析,xx省xx市xx市xx区xx县xx街道xx号,这种状态转移
城市之间的道路可以构建一个图结构,道路的距离可以定义成图的边权。在这种情况下,导航两个地点的最短路径的时候,使用动态规划算法进行最短路径搜索。
向伟大的老师致敬。这是一位前辈科学家的故事。主要讲述他设计和实现的算法又简单又好用。
对于一篇新闻中所有的实词,计算他们的tf-idf,把这些值按照对应的实词词汇表的位置依次排序,得到一个向量。
比如:
词表总有5个词: a b c d e
文章x中所有实词是: a d, 计算a d在文章x中的tf-idf 为 0.1 0.3
则 x的特征向量: [0.1, 0, 0, 0.3, 0]
作者在这里提出余弦相似度,用来衡量两篇文章的中心思想的相似程度
对于两篇文章的向量 a和b
cos<a,b> = <a, b> / |a| * |b|
分子是两个向量的内积,分母是两个向量模长的乘积。
算两个向量的余弦的大小,也就是两个向量夹角的大小。虽然两篇文章使用的关键词的数量不一定一样,但如果用词比例接近,那么向量方向就几乎相同。
如果两个向量同向共线,那么他们语义完全相同
如果两个向量正交,那么语义无关
如果两个向量反向共线,那么语义完全相反
可以使用余弦相似度对文本进行聚类或者分类,把新闻分成不同类别。
当类别太多的时候,分类任务很难,可以使用自动聚类,把文档从多到少最后聚类成一个类别,认为决定哪个中间结果是最好的聚类结果。
用一个大矩阵来表示词和文章的关联性。
假如有N个词,M篇文章,可以得到一个M*N的矩阵:
A = (a_i,_j)_m*_n
其中aij表示第i行第j列元素,也表示第i篇文章在字典中第j个词的加权词频(可以用tf-idf或其他的)
对A 进行奇异值分解,为
Am*n = X_m*_x B_x*_x Y_x*_n
是一种技术手段,在大量文档中,给每个文档一个指纹,所有文档的指纹长度相同,每个文档有唯一的指纹,并且不同文档的指纹相同的概率非常小。
生成指纹的方法:
介绍了一些算法,在信息论的指导下,加密算法在解密上的难度大大增加。
例举了古代先哲研究航天问题的一些故事,道出了数学模型的重要性。
对一个随机事件概率分布进行预测的时候,我们的预测应当满足全部已知条件,而对未知情况不要做任何主观的假设。在这种情况下,概率分布最均匀,预测的风险也最小。因为这时候概率分布的信息熵最大,所以叫做最大熵模型。
模型算法具体内容不叙述,请参考其他资料。
采用通用的迭代算法GIS算法:
后来有科学家提出了改进的gis算法为 IIS 算法,加快了模型的训练。
对汉字的编码氛围两部分:
向伟大的前辈致敬。讲了这位老前辈在管理和教学上的优秀成果。
一个快速从集合中查找是否已经存在某元素的算法。
贝叶斯网络的具体算法不进行介绍,还请参考其他材料
条件随机场是联合概率分布的有效模型。
在隐含马尔科夫模型中,观察值序列中某一个时刻都观察值xi只与同时刻状态有关yi,如果xi与该时刻前后的状态yi-1 yi yi+1 都考虑有关,对应的模型就是条件随机场。
x为看到的东西,在浅层分析中,他是句子的词、每个词的词性等。
y为要推导的东西,语法成分,比如 名词短语、动词短语、时间短语等。
曾用于每个城市犯罪的时间地点预测,去的相当不错的成果。
讲述了科学家维特比的故事。向伟大的科学家致敬。
维特比算法是一种图中最短路径的动态规划搜索算法。
该算法主要用于隐马尔科夫模型中。
在这本书中,我看到的EM算法,我感觉就是k-means聚类算法,没有感觉到他和kmeans的不同。在学校的模式识别课上也学到了EM算法,当时觉着特别难理解,根本理解不上去。在这里我就不胡乱给出见解了。还望大神多多指点。
第一阶段——竞价排名,谁给的钱多谁排在前面
猜想:给得起钱的公司都是卖好东西的大公司。
结果:很多给大钱的公司是卖残次品获得高昂利润的公司。
第三阶段——进一步进行全局优化
广告推荐这里有很多数学问题,不能进行详细说明。还请参阅其他材料。
logistic回归算法不做介绍,请参考其他材料。
后来各个公司纷纷采用logistic模型来做自己的广告点击率预测模型。
分治算法思想,把大问题逐个分解成小问题,小问题的解合并成大问题的解。
google开发出mapreduce之后,实现了把超大问题放在多个不那么强悍的计算机上进行分治求解,从而实现了云计算的基础。
主要讲了google利用神经网络算法构建出了google大脑,神经网络算法不进行详细介绍请参考更多权威资料。
这章中作者讲了很多内容 很有意思,很有作者的个人观点,却也我感到十分认同。
其他内容就不细说了,总之带有了作者主观色彩却又让人折服。
个人读完数学之美的总结。希望对其他人有帮助,也留给自己今后回来参考。
欢迎披露与指正
原文:https://www.cnblogs.com/Lin-Yi/p/11624823.html