数学之美
分类：Math
第二次看吴军老师的《数学之美》，还记得上一次看是两年以前，当时觉得很好看，但是由于基础知识不够，不能完全领会吴老师的精髓（虽然讲的通俗易懂，但是要深入理解其中的数学知识、数学模型还是差得远），看了一半多就束之高阁了。最近在复习高等数学，瞬间回忆起来以前学习数学的快乐时光，数学的简洁之美引人入胜，重新燃起了对数学的渴求；同时，突然看到了池建强老师的一篇推送《方向不对，十五年白费》（其实一看标题就像是《数学之美》hhhh），立马重拾了这本书，准备以一个计算机工作者的视角品味吴老师的数学思维和哲学理念。
一切多依赖于我们把眼睛紧盯在自然界的事实之上 –培根
第一章 文字和语言 vs 数字和信息
数学的力量
只有数学能把语言学也归结到科学的领域，纵观现代社会发展几十年，很多学科发展到最后都成为了科学，但是唯独只有语言学，这门人类文明发展的起源学科不能被归结进来，甚至没有人这么想过（包括我自己），一直把语言学当作是文科的东西来定义。
文字的起源
人类为了记录更多的事物，从语言发展到了文字，这是必然趋势。最初期自然是象形文字，因为那时候的人类还不具备抽象的能力，见到什么东西只是如实的记录下来而已，不过就仅仅是这种机械的记录，已经使文明的发展突飞猛进。在文字以前，人类的经验都只能靠部落之间的口口相传，也即是信息传递的载体仅为声音，但是有了文字以后，信息的载体能够突破声音的限制（那时候的声音不能存储），通过固体广泛的传播。哪个文明先发明了文字，也就先人一步，正式进入人类文明。
抽象概念
在早期，象形文字的数量和记录一个文明需要的信息量显然是相关的。 然而随着文明的进步，信息量的增加，埃及的象形文字数量便不再随着文明的发展而增加了，因为没有人能够学会和记住这么多的文字。于是，概念的第一次概括和归类就开始了。
这时，人类便具备了抽象和概括的能力。人们发现，光靠增加编码量的方式不能解决本质的问题，在人类能够理解的范畴内，信息的编码量有上限，也就是说，有的概念必须归类合并。
学科交叉
这种概念的聚类，在原理上与今天的自然语言处理或者机器学习的聚类有很大的相似性，只是在远古，完成这个过程可能需要上千年；而今天，可能只需几天甚至几小时，视计算机的速度和数量而定。
谁说研究历史没有用，这就是最好的证明，要想解决自然问题，最好的办法就是回到自然中去，看看这个东西最开始是怎么产生的，为什么这么多年研究自然语言处理的专家连这一点都没有想到呢？只是照着前人的基础，最开始发明的SPT语法分类树是能够解决少量的语言处理的问题，但是这只是实验模型，真正到了应用的范畴，其计算复杂度根本不是一个量级的，只想着依靠提高计算性能来解决，还是没有抓住本质的问题。要是哪个历史学家或者语言学家懂一点香农信息论，开创性的跨领域解决了这个看似“人工智能”的问题，那就更具教育意义了。
有了文字，前人的生活经验和发生的事件便一代代传了下来。只要一个文明不中断，或者这种文字还有人认识，这些信息就会永远流传下去，比如中国的文明便是如此。当然，当一种文字不再有人认识时，破解相应的信息就有点困难了，虽然办法还是有的。
看到这里，我以为吴老师是像费马一样，俏皮地写个结论在书上，并不给予证明，就猜想，怎样才能破解无人知晓的文字。
- 爆破方法 受到信息安全领域用字典破解口令的启发，但是感觉难度太大，而且不一定能有效的得出结果，也不能验证结果的正确性。当然，这里的爆破也是有方向的，根据当时文明可能发展的程度，来判断当时可能记录什么内容。
- 等价替换 想着，这不就等同于不同文明之间的碰撞的时候，第一个翻译官是怎么知晓另一个文明的语言或者文字的。这时候就应当像一个婴儿一样，学习对方的语言或者文字，从而习得另一个文明。加上对自己文明的认知，总会有交叉的部分，比如生活事物，那相应的翻译也就建立起来了。 看到后来，吴老师就给予了方法，跟我想的大同小异：不同的文明，因为地狱的原因，历史上相互隔绝，便会有不同的文字。随着文明的融合与冲突，不同文明下的人们需要进行交流，或者说通信，那么翻译的需求便产生了。翻译这件事之所以能达成，仅仅是因为不同的文字系统在记录信息上的能力是等价的。（这个结论很重要。但是我不是很明白为什么是等价的，又或者怎样衡量记录信息的能力。）进一步讲，文字只是信息的载体，而非信息本身。那么不用文字，而用其他的载体（比如数字）是否可以存储同样意义的信息呢？这个答案是肯定的，也就是现代通信的基础。当然，不同的文明进行交流时，或许会用不同的文字记载同一件事。这就有可能为我们破解无人能懂的语言提供一把钥匙。
信息的冗余是信息安全的保障。罗塞塔石碑上的内容是同一信息重复三次，因此只要有一份内容完好保留下来，原有的信息就不会丢失，这对信道编码有指导意义。
这样看来，2000多年前的祖先比现在的我聪明，也有可能是那时候信息非常珍贵而且容易损坏，需要同时备份三份，这点成本比信息损失的成本小多了。我以前总是觉得，精简才是最好，任何冗余都是浪费，看来，适当的“浪费”，能很大程度的提高风险抵御能力。
数字编码
渐渐地，我们的祖先发现是个指头不够用了。虽然最简单的办法就是把十个脚趾头也算上，但是这不能解决根本问题。事实上，我们的祖先没有这样做，当然也许在欧洲大陆上出现过这么做的部落，但早就被灭绝了。我们的祖先很聪敏，发明了位进制，也就是我们今天说的逢十进一。这是人类的一大飞跃，因为我们的祖先开始懂得对数量进行编码了，
不能解决根本问题。
相比十进制，二十进制有很多不便之处。我们中国人过去即使是不识几个字的人，也能背诵九九表。但是，换成二十进制，要背的可就是19✖19的围棋盘了。即使到了人类文明的中期，即公元前后，除非是学者，几乎没有人能够做到这一点。我想这可能是玛雅文明发展非常缓慢的原因之一，当然更重要的原因是它的文字极为复杂，以至于每个部落没有几个人能认识。
决策者对一个文明的影响是得有多大啊，那个时候，能够决定部落的文字和数字这种高级别的事务的，肯定只有部落领袖或者酋长之类的人物，如果没有设计或者选取一个好的文字或者数字，不光使部落的发展滞后，更有可能直接带来毁灭。这就是历史版的“落后就要挨打”。
对于不同位数数字的表示，中国人和罗马人都用明确的单位来表示数字的不同量级，中国人是用个十百千万亿兆；罗马人用字符l代表1，V代表5，X代表10，L代表50，C代表100，D代表500，M代表1000，再往上就没有了。这两种表示法都不自觉地引入了朴素的编码的概念。但是，从编码的有效性来讲，中国人的做法比罗马人高明。
这里同样证明了决策者对种族的影响，而且还间接说明了中华民族为什么能够兴盛这么多年。
高度抽象
描述数字最有效的是古印度人，他们发明了包括0在内的10个阿拉伯数字，就是今天全世界通用的数字。这种表示方法比中国和罗马的都抽象，但是使用方便。因此，它们由阿拉伯人传入欧洲后，马上得到普及。阿拉伯数字或者说印度数字的革命性不仅在于它的简洁有效，而且标志着数字和文字的分离。这在客观上让自然语言的研究和数学在几千年里没有重合的轨迹，而且越走越远。
原来是这样，数字和文字以前是一家人，只是在阿拉伯数字之后才开始分离。阿拉伯数字的高度抽象使得对于纯数的研究比文字快了很多，才能使人类的科学飞速发展（机器）。但是到了现在的人工智能时代，机器需要和人类更自然的交互，就不得不使用到语言，通过历史看到数字（计算机语言）和文字（人类语言）的内在一致性，从而找到终极解决办法。
如果把中文的笔画作为字母，它其实也是一种拼音文字，不过它是二维的而已。（然而，为了和罗马体系的拼音文字相区别，在这本书中我们会把汉字称为意型文字。）
中国的拼音系统其实是从日本舶来的，目的是为了让人们更易学习文字。但是既然都是作为一种信息编码，如果说罗马体系的拼音文字是一维的话，那汉字是不是有点类似二维码？西文字母的机器识别比中文汉字的机器识别发展的快，就像是最开始出现条形码（一维），近年来才出现二维码一样。因为高维度的东西总是比低维度难处理。
不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。大家可能都有这个经验，一本英文书，翻译成汉语，如果字体大小相同，那么中译本一般都会薄很多。这和人们普遍的认识–汉语是最简洁的语言–是一致的。同样的大小，二维码的信息量要比条形码多很多。这些，在哲学上都是相统一的。
拼音文字由腓尼基人美索不达米亚带到地中海东岸的叙利亚。腓尼基人是天生的商人，不愿意花大量时间雕刻这些漂亮的楔型字母，而将他们简化成22个字母。
“偷懒”才是推进物种进步的源动力，人都有懒惰性，如果当前的环境能够非常舒适的生活，一定不会有人去给自己“找不痛快的”，历史上从不缺这样的例子：为了简化图形，发明了文字；为了简化重复劳动，发明了机器；为了简化计算，发明了计算机，数不胜数。所以，我们应该学会“偷懒”，也就是尽力去弄清问题的本质，从而找到解决方案，而不是为了安逸、不动脑筋，一直做重复劳动。
后文概要
- 通信的原理和信息传播的模型
- （信源）编码和最短编码
- 解码的规则，语法
- 聚类
- 校验位
- 双语对照文本、语料库和机器翻译
- 多义性和利用上下文消除歧义性
这些今天自然语言处理学者们研究的问题，我们的祖先在设计语言之初其实已经遇到了，并且用类似今天的方法解决了，虽然他们的认识大多是自发的，而不是自觉的。他们过去遵循的法则和我们今天探求的研究方法背后有着共同的东西，这就是数学规律。
不得不感叹吴老师精妙的写作，像极了一部精彩的纪录片，从古至今，讲述了人类文明的发展，还给予读者足够的想象和感叹的空间。
第二章 自然语言处理–从规则到统计
虽然早期自然语言处理的工作对今天没有任何指导意义，但是回顾几代科学家的认识过程，对我们了解自然语言处理的方法很有好处，同时避免重走前人的弯路。
吴老师的高度还是高，这种话，至少我是讲不出来的，不仅站在历史的高度向先辈致敬，也教育了后人的研究方向。
信息熵
一条信息的信息量与其不确定性有直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果对某件事了解较多，则不需要太多的信息就能把它搞清楚。所以，从这个角度来看，可以认为，信息量就等于不确定性的多少。
这其实是很直观的结论，为什么前人都没有想到呢，可能是对“事情”这个事物没有更抽象的理解（没有抽象为一般事件），还有可能是因为概率学没有发展到一定地步，对概率模型的理解还不够深入。
在从20世纪80年代末至今的25年里，随着计算能力的提高和数据量的不断增加，过去看似不可能通过统计模型完成的任务，渐渐都变得可能了，包括很复杂的句法分析。到了20世纪90年代末期，大家发现通过统计得到的句法规则甚至比语言学家总结的更有说服力。2005年以后，随着Google给予统计方法的翻译系统全面超过给予规则方法的SysTran翻译系统，给予规则方法学派固守的最后一个堡垒被拔掉了。这才使得我们在这本书里，可以且只需用数学的方法给出现今所有自然语言处理相关问题的全部答案。 第二点，也很有意思，用给予统计的方法代替传统的方法，需要等待原有的一批语言学家退休。这在科学史上也是经常发生的事。钱钟书在《围城》中讲，老科学家可以理解成“老的科学家”或者“老科学的家”两种。如果是后者，他们年纪不算老，但是已经落伍，大家必须耐心等他们退休让出位子。毕竟，不是所有人都乐意改变自己的观点，无论对错。当然，等这批人退休之后，科学就会以更快的速度发展。因此，我常想，我自己一定要在还不太糊涂和固执时就退休。
这点很值得玩味，有些话就不用说的太明白。总得有人来打破旧规则制定新规则。
第三章 统计语言模型
统计语言模型
判断一个句子的意思在贾里尼克看来很简单–它的可能性大小如何。用严格的语言表述就是：假定S表示一个有意义的句子，由一连串特定顺序排列的词 $w_1, w_2, \ldots, w_n$ 组成（n为句子的长度），要想知道S在文本中中出现的可能性（概率）P(S)，需要用一点条件概率的知识。
S序列出现的概率等于每一个词出现的条件概率相乘，即：
\[P(w_1, w_2, \ldots, w_n) = P(w_1)·P(w_2\|w_1)·P(w_3\|w_1, w_2) \cdots P(w_n\|w_1, w_2, \ldots, w_{n-1})\]其中 $P(w_1)$ 表示第一个词 $w_1$ 出现的概率； $P(w_2|w_1)$ 表示在已知第一个词出现的前提下第二个词出现的概率。
马尔可夫假设
但，有一个麻烦事，计算 $P(w_n|w_1, w_2, …, w_{n-1})$ 的可能性太多了，无法估算。别着急，俄国的马尔可夫来帮忙，他假设后面的状态只有前一种状态有关，这样就简单多了（暂且不讨论这样是否合理，从结果上看是合理的，为什么，因为很多事就是这样，后面的状态只与前一种状态最相关，虽然与之前所有的都相关，但是相关性没那么大，而且那些小的相关性可以通过前一种状态逐渐传递到现在的状态，所以我们可以说这种假设是合理的，误差可以忽略），于是P（S)可以展开成：
\[P(w_1, w_2, \ldots, w_n) = P(w_1)·P(w_2|w_1)·P(w_3|w_2) \cdots P(w_n|w_{n-1})\]至此，就得到了著名的统计语言二元模型（Bigram Model）。当然，也可以假设一个词跟前面的N-1个词相关，对应的模型就叫做N元模型，用什么模型取决于你的数据和需要的精度。（实际中最常用的就是3元模型，也即是假设一个词和前面的两个词相关，想想看你平时说的话，嗯，差不多了）
零概率问题的平滑处理
剩下的就交给计算机统计训练集中的词（组）频了。如果语料中恰好没有一些词（组）出现怎么办，是否意味着 $P(w_i|w_{i-1}) = 0$ ？肯定不是。
古德-图灵估计（Good-Turning Estimate）来帮忙，总体思想就是：分配一个很小的比例给看不见的事件，同时将所有看得见的事件概率调小一点，这样就能保证所有事件的总和仍然为1了。古德-图灵估计按照下面的公式计算：
\[d_r = \frac{ (r+1)·N_{r+1} }{ N_r }\]在前人的基础上，前IBM科学家卡茨提出了卡茨退避法（Katz backoff）：
\[p(w_i\|w_{i-1}) = \begin{cases} f(w_i\|w_{i-1}), \quad if #(w_{i-1}, w_i) \beq T \\ f_{gt}(w_i\|w_{i-1}), \quad if 0 < #(w_{i-1}, w_i) < T \\ Q(w_{i-1})·f(w_i), \quad otherwise \end{cases}\]其中T为阈值，通常在8-10左右，当词频超过这个阈值时，按照常规的方式统计，当词频低于这个阈值时，按照古德-图灵估计后的相对频度统计；而：
\[Q(w_{i-1}) = \frac{ 1 - \sum_{w_i seen}{P(w_i\|w_{i-1})} }{ \sum_{w_i unseen}{f(w_i)} }\]可以保证所有事件的概率和为1。
语料的选取
不要迷信权威，腾讯的搜索部门最早的语言模型就是使用《人民日报》的预料训练的，但事实证明效果很差，经常出现搜索串和网页不匹配的例子。后来改用网页数据，尽管用很多噪音，但是因为训练数据和应用的一致性，质量反而很好。
所以做预测通常将合理的数据集抽样，大部分用于训练模型，小部分用于测试模型，这样的结果通常令人满意。
第四章 谈谈分词
运用上面的语言模型又可以有效地将语料进行分词，计算那种分词正确的概率大即可。
在不少人看来，分词技术只是针对亚洲语言的，而罗马体系的拼音语言没有这个问题，其实不然。很难想象，中文分词的方法居然用到了英语处理中，主要是用于手写识别，因为很多人在手写英文的过程中是没有那么严格地空格停顿的。
这样看来，英文确实天生具有“可计算”的优点。
第五章 隐含马尔可夫模型
隐含马尔可夫模型最初应用于通信领域，继而推广到语音和语言处理中，成为连接自然语言处理和通信的桥梁。同时，隐含马尔可夫模型也是机器学习的主要工具之一。和几乎所有的机器学习的模型工具一样，它需要一个训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特比算法），掌握了这两类算法，就基本上可以使用隐含马尔可夫模型这个工具了。
一下就讲清楚了问题的本质。先使用鲍姆-韦尔奇算法对机器学习的模型进行训练（迭代优化参数），再使用维特比算法
如果没有任何信息，任何公式或者数字的游戏都无法排除不确定性。这个朴素的结论非常重要，但是在研究工作中经常被一些半瓶子醋的专家忽视，希望做这方面工作的读者谨记。几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。 如果这些信息还是不够消除不确定性，不妨再问问用户。这就是相关搜索的理论基础。不正确的做法是在这个关键词上玩数字和公式的游戏，由于没有额外的信息引入，这种做法没有效果，这就是很多做搜索质量的人非常辛苦却很少有收获的原因。最糟糕的做法是引入人为的假设，这和“蒙”没什么差别。其结果似乎满足了个别用户的口味，但是对大部分用户来讲，搜索结果反而变得更糟。合理利用信息，而非玩弄什么公式和机器学习算法，是做好搜索的关键。
