读《数学之美》

读了吴军的《数学通识讲义》，这两天也读一下他的《数学之美》，这本书写的特别好的是，它用讲故事的方式先阐述数学理论发起的原因，让读者知道某个数学分支有什么用，然后再去学数学就很有画面感，也容易学得进去。

现在年纪大了，今天看懂的知识明天不一定用得上，后天就忘记了，所以需要对书中的精华记录一下：

统计模型

在统计语言模型中，贾里尼克的方法很简单，一个句子是否合理，就看看它的可能性大小如何就好了，至于可能性就用统计学概率来衡量。其中条件概率公式 P(S) = P(W1) • P(W2|W1) • P(W3|W2) ... P(Wi|Wi-1) ... P(Wn|Wn-1) 是基于俄罗斯数学家马尔可夫提出的一个偷懒但还颇为有效的方法，就是每当遇到要求一句话的统计学概率，就假设任意一个词 Wi 出现的概率只同它前面的词 Wi-1 有关，于是问题就变得简单了。

其中条件概率 P(Wi|wi-1) 的定义是 P(Wi|wi-1) 等于联合概率 P(Wi-1, Wi) 除以边缘概率 P(Wi-1). 联合概率就是两个单词 Wi 和 Wi-1 统计次数除以语料库所有单词的次数，边缘概率 P(Wi-1) 就是单词 Wi-1 统计次数除以语料库单词的次数。根据大数定理，只要统计量足够，相对频率就等于概率。

通过马尔克夫的模型，一个复杂的统计模型的解决方法如此简单，用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题，而用很复杂的文法规则和人工智能却做不到。数学的精彩之处就在于简单的模型可以干大事。

上面是理论上的模型，主要让读者可以清楚的理解其原理，软件工程中，一般会把联合概率做到再前面的单词进行关联统计，而不仅仅只是相邻的单词做联合概率统计，其中 N=2 的二元模式就是上面的公式， N=1 的一元模型实际上是一个上下文无关的模型。考虑到语言模型统计的计算复杂度是指数复杂度，一般来说 N=3 的效果就非常好，也就是统计当前单词和前后两个单词的联合统计概率效果就很好了， N 太大计算量太大，性价比不高。以 Google 为例， Google 参与翻译比赛的罗塞塔翻译系统使用四元模型需要存储在 500 台以上的 Google 服务器中。

对于语料库没有出现的词，我们不能简单的认为概率是 0，而要用古德-图灵估计的原理，对于没有看见的事件一个比较小的概率值，根据次数的多寡来折扣计算，这样就可以解决概率统计不平滑的问题。

模型训练中另一个重要的问题就是训练数据，或者语料库的选取。如果训练语料和模型应用的领域相脱节，那么模型的效果通常要大达折扣。比如网页搜索，它的训练数据就应该是杂乱无章的网页输入和用户输入的关键字，而不是传统的、规范的新闻稿，用新闻稿训练的数据模型做搜索引擎就会出现关键字和网页不匹配的情况，效果很差。

中文分词

中文分词可以用语言统计模型的来计算出不同分词情况的概率，并找出概率最大的，就能够找到最好的分词方法。

同时为了避免穷举所有分词情况概率的资源浪费，可以把最佳概率搜索转换成一个动态规划(Dynamic Programming)的问题，并利用 Viterbi 算法快速找到最佳分词。

隐含马尔可夫模型

19 世纪，概率论的发展从对随机变量的研究发展到随机变量的时间序列（即随机过程）的研究，比如我们把 S1, S2, S3, … St, … 看成北京每天的最高气温，这里的每个状态 St 都是随机的。马尔可夫为了简化问题，提出了一种简化的假设，即随机过程中各个状态 St 的概率分布，只与它的前一个状态 St-1 有关，即 P(St|S1,S2,S3,...,St-1) = P(St|St-1)。当然这种假设未必适合所有的应用，但是至少对以前很多不好解决问题给出了近似解。

在实践马尔可夫的模型时，需要对数据进行大量标注进行监督训练，但是有些场景下，是无法进行人工数据标记的，比如声学模型训练人是无法确定某个语音的状态序列的，比如中英机器翻译，基于大量中英对照的语料对中英词组一一对应标注的成本太高了。

所以，隐含马尔可夫模型的方式是仅仅通过观测到的信号 O1,O2,O3,… 就能推算模型参数 P(St|St-1) 和 P(Ot|St)，这就是鲍姆-韦尔奇算法的思想：根据一个初始化的模型，不断找概率空间更优的解，上次模型的结果相当于下次模型训练的 ‘标注数据’，直到找到一个最优解。这种就是无监督训练。

无监督训练很难找到全局最优解（除非目标函数是凸函数，只有一个最优解）。

所有的机器学习都需要一个训练算法（鲍姆-韦尔奇算法）和解码算法（维特比算法），只要掌握这两类算法，就基本可以使用隐含马尔可夫模型这个工具了。

可以把深度学习的思考逻辑和通信原理中的编解码思想是类似的。

信息的度量和作用

一条消息的信息量和它的不确定性有着直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，那么不需要太多的信息就能把它搞清楚。所以，从这个角度来看，可以认为，信息量就等于不确定性的多少。

机器翻译中，最难的两个问题之一是词义的二义性（又称歧义性）问题。比如 Bush 一词可以是美国总统布什的名字，也可以是灌木丛。消除歧义性最好的办法是由雅让斯基提出来的：首先从大量文本中找出和总统布什一起出现的互信息量最大的一些词，比如总统、美国、国会、华盛顿等，当然，再用同样的方法找出和灌木丛一起出现的互信息量大的词，比如土壤、植物、野生等等。有了这两组词，再翻译 Bush 时，看看上下文中哪类相关的词多就可以了。这种看上去简单的方法效果好得让同行们大吃一惊。

贾里尼克和现代语言处理

每当弗莱德和我谈起我们各自少年时的教育 ,我们都同意这样几个观点。首先。小学生和中学生其实投有必要花那么多时间读书。而他们的社会经验、生活能力以及在那时树立起的志向将帮助他们的一生。第二，中学阶段花很多时间比同伴多读的课程,在大学以后用非常短的时间就可以读完。困为在大学阶段。人的理解力要强得多。举个例子。在中学需要花 500 小时才能学会的内容,在大学可能花 100 小时就够了。因此,一个学生在中小学阶段建立的那一点点优势在大学很快就会丧失殆尽。第三，学习 (和教育)是一个人一辈子的过程,很多中学成绩好的亚裔学生进入名校后表现明显不如那些因为兴趣而读书的美国同伴。因为前者不断读书的动力不足。第四,书本的内容可以早学，也可以晚学，但是错过了成长阶段却是无法补回来的。(因此。少年班做祛不足取。 )现在中国的好学校里。恐怕百分之九十九的孩子在读书上花的时间比我当时要多,更比贾里尼克要多得多,但是这些孩子今天可能有百分之九十九在学术上的建树不如我，更不如贾里尼克。这实在是教育的误区。

贾里尼克教授在学术上给我最大的帮助就是提高了我在学术上的境界。他告诉我最多的是: 什么方法不好。在这一点上他与股神巴菲特给和他吃饭的投资人的建议有异曲同工之处。巴菲特和那些投资人讲 ,你们都非常聪明 ,不需要我告诉你们做什么,我只需要告诉你们不要去做什么(这样可以少犯很多错误 ) ,这些不要做的事情,是巴菲特从一生的经验教训中得到的。

简单之美-布尔代数和搜索引擎的索引

技术分为术和道两种,具体的做事方法是术,做事的原理和原则是道。这本书的目的是讲道而不是术。很多具体的搜索技术很快会从独门绝技到普及,再到落伍 ,追求术的人一辈子工作很辛苦。只有掌握了搜索的本质和精髓才能永远游刃有余。很多希望我介绍 “术” 的人是希望走捷径。但是真正儆好一件事设有捷径。需要一万小时的专业训练和努力。

做好搜索,最基本的要求是每天分析 10-20 个不好的搜索结果,累积一段时间才有感觉。我在 Google 做搜索质量的时候每天分析的搜索数量远不止这个, Google 的搜索质量笫一技术负贲人阿米特 .辛格 ( Amit Singhal ) 今天依然经常分析这些不好的结果。但是,很多儆搜索的工程师 (美国的中国的都有 ) 做不到这一点,总是希望一个箅法,一个模型就能毕其功于一役,这是不现实的。

图论和网络爬虫

对于图中的每一个顶点。它相连的边的数量定义为它的度 ( Degree )。

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

证明: 假如能够遍历图的每一条边各一次,那么对于每个顶点。需要从某条边进入顶点。同时从另一条边脔开这个顶点。进人和离开顶点的次数是相同的,因此每个顶点有多少条进入的边，就有多少条出去的边。也就是说，每个顶点相连的边的数量是成对出现的, 即每个顶点的度都是偶数。

搜索引擎的网络爬虫问题更应该定义成 “如何在有限时间里最多地爬下最重要的网页“。显然各个网站最重要的网页应该是它的首页。在最极端的情况下,如果爬虫非常小,只能下载非常有限的网页,那么应该下载的是所有网站的首页。如果把爬虫再扩大些。应该爬下从首页直接链接的网页 (就如同和北京直接相连的城市) ,因为这些网页是网站设计者自己认为相当重要的网页。在这个前提下,显然 BES 明显优于 DES。

爬虫的分布式结构以及网络通信的握手成本有关。所谓 “握手” 就是指下载服务器和网站的服务器建立通信的过程。这个过程需要额外的时间 ( OverheadTime ) , 如果握手的次数太多。下载的效率就降低了。实际的网络爬虫都是一个由成百上千甚至成千上万台服务器组成的分布式系统。对于某个网站,一般是由特定的一台或者几台服务器专门下载。这些服务器下载完一个网站。然后再进入下一个网站,而不是每个网站先轮流下载 5%,然后再回过头来下载笫二批。这样可以避免握手的次数太多。

现在很多网页如今是用一些脚本语言比如 Javascript 生成的。打开网页的源代码,URL 不是直接可见的文本。而是运行这一段脚本后才能得到的结果。因此,网络爬虫的页面分析就娈得复架很多,它要模拟浏览器运行一个网页,才能得到里面隐含的 URL。因此，若你发现一些网页明明存在,但搜索引擎就是没有收录, 一个可能的原因是网络肥虫中的解析程序没能成功解析网页中不规范的脚本程序。

在一台下戴服务器上建立和维护一张哈希表并不是难事。但是如果同时有上千台服务器一起下载网页,维护一张统一的哈希表就不是一件容易的事情了。首先,这张哈希表会大到一台服务器存储不下。其次。由于每个下载服务器在开始下载前和完成下戴后都要访问和维护这张表,以免不同的服务器做重复的工作。这个存储哈希表的服务器的通信就成了蹩个爬虫系统的瓶颈。

首先明确每台下载服务器的分工。也就是说在调度时一看到某个 URL 就知道要交给哪台服务器去下载。这样就避免了很多服务器对一个 URL 做出是否需要下戴的判断。然后,在明确分工的基础上 ,判断 URL 是否下载就可以批处理了,比如每次向哈希表(一组独立的服务器 )发送一大批询问,或者每次更新一大批哈希表的内容。这样通信的次数就大大减少了。

PageRank Google 的民主表决式网页排名技术

虽然佩奇和布林不强调这个算祛中谁都贡献了什么思想, 但是据我了解上述想法应该来自于佩奇。接下来的问题是 X1,X2. X3,84 的权重分别是多少 ,如何度量。佩奇认为 ,应该是这些网页本身的网页排名。现在麻烦来了,计算搜索结果的网页排名过程中需要用到网页本身的排名,这不成了 “先有鸡还是先有蛋” 的问题了吗?

破解这个怪圈的应该是布林。他把这个问题变成了一个二维矩阵相乘的问题,并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的,并且根据这个初始值,箅出各个网页的第一次迭代排名,然后再根据笫一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取。这种箅法都保证了网页排名的估计值能收敛到排名的真实值。值得一提的事, 这种算祛是完全没有任何人工干预的。

如何确定网页和查询的相关性

在信息检索中，单文本词频 (Term Frequency) TF 是指某个单词的次数除以网页中所有单词的数量。

逆文本频率指数 IDF (Inverse Document Frequency), 它的公式为 log(D/Dw), 其中 D 是全部网页数， Dw 是包含关键字的网页数。

利用 IDF，上述相关性的公式就有词频的简单求和变成了加权求和，即 TF1 • IDF1 + TF2 • IDF2 + ... + TFn • IDFn

TF-IDF 是对搜索关键词的重要性的度量。从理论上讲,它有很强的理论根据。因此,如果对搜索不是很精通的人,直接采用 TF-IDE 效果也不会太差。现在各家搜索引擎对关键词重要性的度量,都压 TF-IDE 的基础上有些改迸和微调。但是,在原理上与 TF-IDF 相差不远。

自己备注：

首先分词，提取出重要的关键字
计算某个网页中各关键字的 TF 值
计算出整个网络中关键字的 IDF 值
最后加权求和就可以知道关键字和网页的关联性

地图和本地搜索的最基本技术 – 有限状态机和动态规划

在地图应用中，对用户输入的地址，可以用有限状态机来解决。每一个有限状态机都有一个开始状态和一个终止状态,以及若干中间状态。每一条弧上带有从一个状态进入下_个状态的条件。比如当前的状态是 “省”, 如果遇到一个词组和(区)县名有关, 就进入状态 “区县” ; 如果遇到的下一个词组和城市有关。那么就进人 “市”的状态 ,如此等等。如果一条地址能从状态机的开始状态经过状态机的若干中间状态,走到终止状态,那么这条地址就有效,否则无效。比如,”北京市双清路 &3 号” 对亍上面的有限状态来讲有效。而 “上海市辽宁省马家庄” 则无效 (因为无法从 “市” 走回到 “省” )。使用有限状态机识别地址，关键要解央两个问题,即通过一些有效的地址建立状态机,以及给定一个有限状态机后 ,地址字串的匹配箅法。

上述基于有限状态机的地址识别方法在实用中会有-些问题: 当用户输入的地址不太标准或者有错别字时,有限状态机会束手无策。因为它只能进行严格匹配。(其实,有限状态机在计算机科学中早期的成功应用是在程序语言编译器的设计中。一个能运行的程序在语法上必须是没有错的,所以不需要模糊匹配。而自然语言则很随意。无法用简单的语法描述。 )为了解决这个问题。我们希望看到可以进行模糊匹配。并给出一个字串为正确地址的可能性。为了实现这一目的,科学家们提出了基于概率的有限状态机。这种基于概率的有限状态机和离散的马尔可夫链 (详见前面关于马尔可夫模型的章节 )基本上等效。

计算从广州到北京的最短路径的方法是，在中间横向切一下，最短路径必领经过这一条横切线上的某个城市 (鸟督木齐，西宁，兰州，西安，郑州，济南 ) 。我们可以先找到从北京出发到这条线上所有城市的最短路径,最后得到的全程最短路线一定包括这些局部最短路线中的一条。这样,就可以将一个 “寻找全程最短路线” 的问题。分解成-个个寻找局部最短路线的小问题。只要将这条横切线从北京向广州推移。直到广州为止,我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。在上面的例子中,每加入一条横切线,线上平均有 I0 个城市,从广州到北京最多经过 15 个城市,那么采用动态规划的计算量是 10x10x15,而采用穷举路径的笨办法是 10 的 15 饮方,前后差了厅亿倍。正确的数学模型可以将一个计算量看似很大的问题的计算复杂度大大降低。这便是数学的妙用。

有限状态机和动态规划的应用非常广泛。远远不止识别地址导航等地图服务相关颔域。它们在语音识别。拼写和语法纠错。拼音输入祛。工业控制和生物的序列分析等领域都有着极其重要的应用。

Google 的 AK-47

辛格这种儆事情的哲学, 即先帮助用户解决 80% 的问题，再慢慢解央剩下的 20% 问题,是在工业界成功的秘诀之一。许多失败并不是因为人不优秀 ,而是做事情的方法不对,一开始追求大而全的解决方案,之后长时间不能完成,最后不了了之。

在 Google 里,辛格一直坚持寻找简单有效的解央方案,因为他奉行简单的哲学。但是这种做法在 Google 这个人才济济的公司里常常招人反对 ,因为很多资深的工程师倾向于低估简单方法的有效性。2003-2004 年,Google 从世界上很多知名实验室和大学。比如 MITRE, AT&T 实验室和 IBM 实验室。招揽了不少自然语言处理的科学家。不少人试图用精确复杂的办法对辛格设计的各种 “AK-47” 进行改进,后来发现几乎所有时倏 ,辛格的简单方法都接近最优的解决方案,而且还快得多。

辛格坚持选择简单方案的另一个原因是容易解释每一个步骤和方法背后的逍理。这样不仅便于出了问题时耷错 ( Debug) , 而且容易找到今后改进的目标。今夭,整个业界的搜索质量比十多年前佩奇和布林开始研究搜索时已经有了很大的提高,大的改进之处己经不存在了。现在几乎所有的改迸都非常细徵: 通常对一类搜索有改迸的方祛,会对另外某一类搜索产生稍稍负面的影响。这时候。需要很清楚 “所以然” ,才能找出这个方祛产生负面影响的原因和场景,并且避免它的发生。对于非常复杂的方祛,尤其是像黑盒子似的基于机器学习的方法, 这一点是做不到的。而如果每一项改进都是有得有失,甚至得失相差无几,那么长期下来搜索的质量不会有什么明显提升。辛格要求对于搜索质量的改进方祛都要能说清楚理由,说不清楚理由的改进即使看上去有效也不会采用,因为这样将来可能是个隐患。

余弦定理和新闻的分类

由于向量中的每一个娈量都是正数。因此余弦的取值在 0 和 1 之间,也就是说夹角在 0 度到 90 度之间。当两条新阐向量夹角的余弦等于 1 时,这两个向量的夹角为零,两条新闻完全相同; 当夹角的余弦接近于 1 时,两条新闸相似,从而可以归成一类; 夹角的余弦趑小,夹角趑大。两条新阐趑不相关。当两个向量正交肘 (90 度) ,夹角的余弦为零。说明两篇新闻根本没有相同的主题词。它们亳不相关。

美国人总是倾向于用机器 (计算机 )代替人工来完成任务。虽然在短期需要儆一些额外的工作。但是从长远看可以节省很多时间和成本。

信息指纹及其用途

我们知道 IDF 大的词鉴别能力强,因此只需找出每个网页中 IDE 最大的几个词 ,并且算出它们的信息措纹即可。如果两个网页这么计算出来的信息指纹相同。它们基本上是相同的网页。为了允许有一定的容错能力, 在 Google 里采用了一种特定的信息指纹 – 相似哈希 ( Simhash ) 。相似哈希的原理会茌延伸阅读中介绍。上面的算法稍作改进还可以判断一篇文章是否抄袭另一篇文章。具体的做祛是。将每一篇文章切成小的片段。然后对这些片段用上述方法选择特征词的集合，并且计箅它们的指纹。只要比较这些措纹。就能找出大段相同的文字。最后根据时间先后，找到原创的和抄袭的。 Google 实验室利用这个原理做了一个名为 CopyCat 的项目,能够很准确地找出原文和转载的文章。

有了这些信息措纹后,接下来查盗版的事情就类似于比较两个集合元素是否相同了。 Google 收购 YouTube 后,由 Google 研究院研究图像处理的科学家们开发出的反盗版系统,效果非常好。由于可以找出相同的视频的原创和拷贝, Google 制定了一个很有意思的广告分成策略: 虽然所有的视频都可以插人广告,但是广告的收益全部提供给原创的视频,即使广告是插入在拷贝的视频中。这样一来。所有拷贝和上传别人的视频的网站就不可能获得收人。设有了经济利益。也就少了很多盗版种拷贝。

密码学

吴军这章讲的比较模糊，故事偏多，关于密码学的详尽了解，推荐读日本作家结城浩的《图解密码技术》, 讲的通俗易懂，而且全面。

搜索引擎反作弊的问题

吴军将的这一章还是比较有意思的，说了一些搜索引擎反作弊的方法：

探测作弊网站的模式，通过对作弊网站的特征学习后，对作弊网站的噪音进行解卷积的过程，然后自动化清除
作弊网站有大量出链，这个和作弊网站最终链接到商家的网站的内容的特征向量角度差别太大，容易被识别出来

数学模型的重要性

一个正确的数学模型应当在形式上是简单的(托勒密的模型显然太复杂)
一个正确的模型一开始可能还不如一个精雕细琢过的错误模型来的准确 ,但是,如果我们认定大方向是对的,就应该坚持下去(日心说开始并没有地心说准确)
大量准确的数据对研发很重要。
正确的模型也可能受噪音干扰而显得不准确，这时不应该用一种凑合的修正方祛来弥补它，而是要找到噪音的根源,这也许能通往重大的发现

不要把鸡蛋放到一个篮子里 – 谈谈最大的熵模型

最大熵原理指出，要对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件 ,而对未知的情况不要做任何主观假设。(不做主观假设这点很重要)在这种情况下。概率分布最均匀。预测的风险最小。团为这时概率分布的信息熵最大。所以人们称这种模型叫 “最大熵模型”我们常说,不要把所有的鸡蛋放在一个篮子里,其实就是最大熵原理的一个朴素的说法。

自然语言处理的教父马库斯和他的优秀弟子们

布莱尔的成名作是基于变换规则的机器学习方法 ( Trahsformation Rule Based Machine Learning) 。这个方法名称虽然很复杂,其实非常简单。以拼音转汉字为例来说明它:

把每个拼音对应的汊字申最常见的找出来作为笫一遍变换的结果, 当然结果有不少错误。比如,”常识” 可能被转换成 “长识”
可以说是 “去伪存真”，用计算机根据上下文，列举所有的同音字替换的规则,比如如果 chang 被标识成 “长” ,但是后面的汊字是”识” ,则将”长” 改成 “常” ;
应该就是”去粗取精” ,将所有的规则应用到事先标识好的语料中,挑出有用的,掉无用的。然后重复二三步。直到找不出有用的为止。

布莱尔就靠这么简单的方法,在很多自然语言研究领域。取得了几乎最好的结果。

布隆过滤器

布隆过滤器是由佾顿 .布隆 Burton Bloom ) 于 1970 年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明其工作原理。假定存储一亿个电子邮件地址。先建立一个 16 亿二进制 (比特) ,即两亿字节的向量,然后将这 16 亿个二进制位全部清零。对于每一个电子邮件地址 8,用 8 个不同的随机数产生器产生 8 个信息指纹。再用一个随机数产生器 G 把这 &个信息指纹映射到 1-16 亿中的 8 个自然数，再把这 8 个位置的二进制全部设置为 1。对这一亿个电子邮件地址都进行这样的处理后,一个针对这些电子邮件地址的布隆过滤器就建成了。

布隆过滤器决不会漏掉黑名单中的任何一个可疑地址。但是,它有一个不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址也判定为在黑名单中,因为有可能某个好的邮件地址在布隆过滤器中对应的 8 个位置”恰巧” 被 (其他地址 )设置成 1。好在这种可能性很小。我们把它称为误识别率。在上面的例子中,误识别率在万分之-以下。

布隆过滤器的好处在于快速。省空间,但是有一定的误识别率。常见的补救办法是再建立一个小的白名单。存储那些可能被误判的邮件地址。

马尔可夫链的扩展 – 贝尔斯网络

贝叶斯网络在图像处理，文字处理，支持决策等方面有很多应用。在文字处理方面 ,语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络,可以找出近义词和相关的词,因而在 Google 搜索和 Google 广告中都有直接的应用。

维特比和他的维特比算法

维特比算法的基础可以概括成下面三点:

如果概率最大的路径 P (或者说最短路径 ) 经过某个点，比如图中的 X22, 那么这条路径上从起始点 S 到 X22 的这一段子路径 Q,一定是 S 到 X22 之间的最短路径。否则,用 S 到 X22 的最短路径 R 替代 Q, 便构成了一条比更短的路径, 这显然是矛盾的。
从 S 到区的路径必定经过第 i 时刻的某个状态(这显然是大白话,但是很关键 ), 假定第 i 时刻有 k 个状态, 那么如果记录了从 S 到第 i 个状态的所有 k 个节点的最短路径, 最终的最短路径必经过其中的一条。这样, 在任何时刻，只要考虑非常有限条最短路径即可。
结合上述两点, 假定当我们从状态 i 进入状态 i+1 时, 从 S 到状态 i 上各个节点的最短略径巳经找到,并且记录在这些节点上, 那么在计算从起点 S 到第 i+1 状态的某个节点 Xi+1 的最短路径时, 只要考虑从 S 到前一个状态 i 所有的 k 个节点的最短路径, 以及从这 k 个节点到 Xi+1， j 的距离即可。

基于上述三点基础,维特比总结了如下的算法:

笫一步, 从点 S 出发，对于第一个状态 X1 的各个节点，不妨假定有 N1 个, 计算出 S 到它们的距离 d(S,X1i) , 其中 X1i 代表任意状态 1 的节点。因为只有 1 步, 所以这些距离都是 S 到它们各自的最短距离。

笫二步, 这是理解整个箅法的关键。对于第二个状态 X2 的所有节点，要计算出从 S 到它们的最短距离。我们知逍, 对于特定的节点 X2i, 从 S 到它的路径可以经过状态 1 的 N1 中任何一个节点 X1i, 当然, 对应的路径长度就是 d(S, X2i)= d(S,X1j) + d(X1j, X2i)。由于 j 有 N1 种可能性。我们要一一计算, 然后找到最小值，即

d(S, X2i) = MINi=1,N1 d(S, X1j) + d(X1i, X2i)

这样对于第二个状态的每个节点。需要 N1 次乘法计算。假定这个状态有 N2 个节点, 把 S 这些节点的距离都算一遍，就有 O（N1 . N2) 次计算。

接下来，类似地按照上述方法从笫二个状态走到第三个状态,一直走到最后一个状态,就得到了整个网格从头到尾的最短路径。每一步计算的复杂度都和相邻两个状态 Si 和 Si+1 各自的节点数目 Ni， Ni+1 的乘积成正比。即 0(Ni . Ni+1)。如果假定在这个隐含马尔可夫链中节点最多的状态有 D 个节点,也就是说整个网格的宽度为 D。那么任何一步的复杂度不超过 0(D^2) ,由于网格长度是 N , 所以整个维特比算法的复杂度是 0(N . D^2)。

回到上面那个输入法的问题。计算量基本上是 13 X 13 X10 = 1690 = 10^3，这和原来的 10^16 有天壤之别。更重要的是, 维特比算法是和长度成正比的。无论是在通信中。还是在语音识别。打字中,输入都是按照流 ( Stream )的方式进行的。只要在处理每个状态的肘间比讲话或者打字速度快 (这点很容易做到 ) , 那么不论输入有多长，解码过程永远是实时的。这便是数学漂亮的地方!虽然数字通信和自然语言处理的基础算法的原理其实就是这么简单。每个通信或者计算机专业的学生两个小时就能学会,但是在上个世纪 60 年代能够想出这个快速算法是非常了不起的。

CDMA

在 CDMA 以前, 移动通信使用过两种技术: 频分多址 ( EDMA) 和时分多址 ( TDMA ) 技术。

频分多址顾名思义 ,是对频率迸行切分,每一路通信使用一个不同的频率,对讲机采用的就是这个原理。由于相邻频率会互相干扰。因此每个信逍要有足够的带宽。如果用户数量增加,总带宽就必须增加。我们知逍空中的频带资源是有限的,因此要么必领限制逋信人数,要么降低话音质量。

时分多址是将同一频带按时间分成很多份。每个人的(语音 )通信数据在压缩后只占用这个频带传输的 1/N 时间。这样同一个频带可以被多个人局时使用。第二代移动通信的标准都是基于 TDMA 的。

前面讲了,扩频传输对频带的利用率比固定频率传输更高,因此。如果把很多细分的频带合在一起。很多路信息同时传输。那么应该可以提高带宽的利用率。这样就可以增加用户的数量,或者当用户数量不娈时,提商每个用户的传输速度。

美囤的两个主要无线运菅商 AT&T 和 Verizon, 前者的基站密度不比后者低,信号强度也不比后者差。但是通话质量和数据传输速度却明显不如后者。原因就是 AT&T 网络总的来讲是继承过去 TDMA 的。而 Verizon 则完全是基于 CDMA 的。

当然, 读者可能会有个问题: 如果一个发送者占用了很多频带。那么有多个发送者同时发射岂不打架了? 没关系,每个发送者有自己不同的密码。接收者在接到不同信号时。通过密码过滤掉自己无法解码的信号,留下和自己密码对应的信号即可。由于这种方法是根据不同的密码区分发送的,因此称为码分多址。

世界上绝大多数科学家最大的满足就是自己的研究成果得到同行的认可,如果能有应用就更是喜出望外了。而能够亲自将这些成就应用到实际中的入少之又少,因为做到这一点对科学家来讲很不容易。这样的科学家色括 RISC 的发明人亨利西和 DSL 之父查菲等人。这些人已经非常了不起了,但是也只做了一个行业中他们擅长的部分。而不是从头到尾完成一次革命。而维特比所做的远远超出了这一点。他不仅提供了关键性的发明 ,而且为了保障这项关键性的发明的效益在全社会得到最大化,他解央了所有配套的技术。所有试图另辟蹊径的公司都发现。高通公司的标难几乎无祛绕过去,困为他们已经把能想到的事情都想到了。

最后

吴军深入浅出的功底真的非常强，《数学通识讲义》更像是告诉数学入门者数学历史来龙去脉和高等数学有啥用，强调的是思维方式。《数学之美》这本书更适合像我这样的工程师，想知道很多高大上技术背后朴素的数学原理，这本书中的马尔可夫模型和维特比算法讲的非常透彻，虽然这本书是十多年前的书，但是我依然认为它是研究人工智能领域最好的数学科普书。

系统性的学习任何知识的关键不是去互联网上看很多高手的结论，也不是看像我这样博客记录的读书笔记，只知道结论本身并不能提高我们自己的认知，因为今天学得知识在这个变化的世界中明天就可能没用了，关键要学习每个知识后面的思维方式，学会了思维方式才能真正融会贯通。

而学会思维方式的方法就是要系统性的读书，系统性读书的好处是你知道事情的背景、起因、过程和想法这些细节后，你才能在大脑中完整性的构建思维体系，才能在作者在娓娓道来的过程中进行思考，最终启发自己。

希望本博客记录的这些精彩内容能够吸引大家去好好的读这本难得的《数学之美》。

PS：本书大部分的文字稿都是我结合 EAF PDF-Viewer 的 OCR 功能自动识别的，难免有遗漏的字识别不好，欢迎发送 PR 来修正它们。