《数学之美》_吴军

阅于2017年11月

相关性（概率）、权重是核心

理解当前网络机理的同时，也深刻认识到自己在数理知识与编程上的不足。不应该在这个方向深入太久；

语言处理

第1章 ~ 第7章

第1章文字和语言 Vs. 数学和信息

数学、文字和自然语言一样，都是信息的载体。区别只是信息编码的不同单位而已；

数学和语言的产生都是为了同一个目的：记录和传播信息

直到香农博士提出信息论，人们才把数学和信息系统自觉地联系起来。

信息传播的模型： $$ 信息源 \to 编码 \to 信道 \to 解码 \to 接收者$$
翻译这件事之所以能达成，仅仅是因为不同的文字在记录信息上的能力是等价的。
- 文字只是信息的载体，而非信息本身
- 那不用文字，而用其他载体（比如数字）也是可以存储相同意义的信息
古印度人发明了0 - 10 个阿拉伯数字
象形文字到拼音文字是一个飞越；因为人类在描述物体的方式上，从物体的外表进化到了抽象的概念

第2章自然语言处理

任何一种语言度是一种编码的方式；而语言的语法规则是编解码的算法。这是语言的数学本质；

图灵测试（Turning Test）
从规则到统计
- 原先都是通过定义语法的方式去进行自然语言识别
- 之后是基于有向图的统计模型

第3章统计语言模型

从数学的方法描述语言规律：贾里尼克
- 一个句子是否合理，就看它的可能性大小
- 可能性用概率来衡量
假设$S$ 表示一个有意义的句子，有一连串特定顺序排列的词 $w_1, w_2, …, w_n$ 组成，$n$ 是句子的长度；
- 现在想知道 $S$ 在文本中出现的可能性，即概率 $P(S)$
- $S = w_1,w_2,…$ 即 $P(S) = P(w_1,w_2,…)$
- 利用条件概率公式，展开为
  
  $$P(S) = P(w_1) P(w_2|w_1) P(w_3|w_1,w_2) … P(w_n|w_1,w_2,…)$$
  
  $P(w_1)$ 表示第一个词 $w_1$ 出现的概率； $P(w_2|w_1)$ 表示在已知第一个词的前提下出现的概率；以此类推， $w_n$ 的出现概率取决于它前面的所有词
安德烈.马尔科夫 ( Andrey Markov ) 19世纪俄国数学家
- 假设任意一个词 $wi$ 出现的概率只同它前面的词 $w{i-1}$ 有关；即马尔科夫假设
  
  $$P(S) = P(w_1) P(w_2|w_1) P(w_3|w_2) … P(wn|w{n-1})$$
  
  也可以假设一个词由前面 $N-1$ 个词决定；则称为 $N$ 元模型
- 问题转化为如何估计条件概率 $P(wi|w{i-1})$
  
  $$P(wi|w{i-1}) = {P(w_{i-1},wi) \over P(w{i-1})}$$
  
  若有大量机读文本（即语料库），只要做统计即可得出相应的概率
延伸阅读
- 高阶语言模型：实际应用中最多选取 $N=3$ 的三元模型，更高阶的很少使用；
  - 当模型从3到4时，效果的提升不显著，但资源的耗费量却增加地很快
- 模型训练、零概率问题和平滑方法
  - 统计中若 # $(w_{i-1},w_i)$ 的次数等于0，但并不意味着出现的概率为0
  - 古德 - 图灵估计 ( Good - Turning Estimate) ：对于没有看见的事件，我们不能认为它发生的概率为零；因此需要从概率的总量中分配一个很小的比例给这些没有看见的事件。

第4章分词

分词的一致性：统计模型被广泛应用后，不同的分词器产生记过的差异远远小于不同人之间看法的差异
词的颗粒度与层级：不同的应用中要选择不同的颗粒度标准
- “清华大学” 可以看做一个整体，也可以看做由2个词组成的
- 在机器翻译中，一般颗粒度大的翻译效果好；
- 在网页搜索中，小的颗粒度效果比大的好
  - 当用户查询 “清华” 时，若使用较大的颗粒度，是找不到清华大学的

第5章隐含马尔科夫模型

美国数学家鲍姆 ( Leonard E. Baum )等人在20世纪六十七年代提出的

马尔科夫假设与马尔科夫链
- 一个状态到另一个状态是有一定概率的，并且只与前一个状态有关
隐含马尔科夫假设
- 任意时刻 t 的状态 $s_t$ 是不可见的；观察者没办法通过观察到一个状态序列 $s_1, s_2,…$ 来推测转移概率
- 但是，会在每个时刻t 输出一个符号 $o_t$ ，且仅跟 $s_t$ 相关；即独立输出假设
- 因此，通过计算出某个特定的状态序列所产生的输出符号 $o_1, o_2,…$ 的概率来推测 $s_1, s_2,…$ 发生的概率

【精】第6章信息的度量和作用

信息熵不仅是对信息的量化度量，而且是整个信息论的基础；

信息熵的物理含义是对一个信息系统不确定性的度量

信息熵

信息量等于不确定性的多少； 一条信息的信息量与其不确定性有着直接的关系；
- 我们对一件事一无所知，就需要了解大量信息；如果了解很多，不需要太多信息就能把它搞清楚
香农用 “比特” (Bit) 来度量信息量
- 一个比特是一位二进制数
- 信息量的比特数和所有可能情况的对数函数 $log$ 有关（$log_232=5$）
  - 一共32个球队，哪个球队会获胜？这条消息的信息量是5比特 用二分法，先猜在1-16号中，若正确则继续二分；若错误则跳到另一半进行二分；最后需要用5次即可获得正确答案；
  - 当每个球队获胜的概率不等时，“谁是冠军” 的信息量比5比特少
  准确的信息量： $$H = -(p_1 log_2{p_1} + p_2 log_2{p_2} + …)$$
信息熵的概念： $$H(X) = - \sum_x P(x) log_2{P(x)}$$

变量的不确定性越大，熵就越大
有了熵的概念，就可以回答这样一个问题 “一本50万字的中文书平均有多少信息量”
- 常用的汉字大约有7000个；若每个概率相等，则需要约13比特 $2^{13} = 8192$ 表示一个汉字
- 但汉字的使用频率是不相等的；一般前10%的汉字占常用文本的95%以上
- 假设每个汉字的信息熵为 9 比特；在考虑上下文关系，每个汉字的信息熵就只有 5 比特
- 结论：一本50万字的中文书有大约250万比特，大约2M的内容
汉语是最简洁的语言；一本英文书，如果字体大小相同，那么中译本一般都会薄很多

信息的作用

信息的作用在于消除不确定性

自然语言处理的大量问题就是寻找相关的信息

信息是消除系统不确定性的唯一办法；在没有获得任何信息前，一个系统就像一个黑匣子，不确定性为$U$；需要引入的信息量$I$ 取决于这个不确定性的大小
- 当 $I > U$ 可以完全消除
- 当 $I < U$ 可以消除部分不确定性
相关性能够消除不确定性；
- 在自然语言的统计模型中，一元模型就是通过某个词自身的概率分布来消除不确定性；二元即高阶的语言模型还使用了上下文的信息
- 联合概率分布是小于等于单一概率的；即 $P(X|Y) \leq P(X)$
- 可以证明条件熵 $H(X|Y) \leq H(X)$ ；即由于多了 $Y$ 这个信息，关于 $X$ 的不确定性下降了
- 当增加的信息是完全无关的时候，等号成立；

互信息

相关性的度量

$ I(X;Y) = \sum_{x,y} P(x,y) log_2 {P(x,y) \over P(x)P(y)} $

$$I(X;Y) = H(X) - H(X|Y) $$

互信息是的取值在 0 到 min( (H(X), H(Y)) 之间

当X和Y 完全相关时，它的取值为 H(X) ；此时由于Y的出现，使得条件信息熵 H(X|Y) = 0

当两者挖暖无关时，它的取值为 0

相对熵

用来衡量两个取值为正的函数的相似性

对于两个完全相同的函数，它们的相对熵等于零
相对熵越大，两个函数的差异越大；反之则越小
对于概率分布或者概率密度函数，如果取值均大于零，相对熵可以度量两个随机分布的差异性

第7章贾里尼克和现代语言处理

去思索作为一个孩子，他应该有的时间分配；尤其在学习上；为自己的孩子做思考
贾里尼克教授告诉吴军最多的是：什么方法不好；（避免走弯路）
- 巴菲特和那些投资人讲，你们都非常聪明，不需要我告诉你们做什么，我只需要告诉你们不要去做什么；这是巴菲特从一生的经验教训中得出的；

网络搜搜

第8章 ~ 第13章

第8章简单之美：布尔代数与搜索引擎

布尔代数与搜索引擎

牛顿：（人们）发觉真理在形式上从来都是简单的，而不是复杂和含混的； ( Truth is ever to be found in simplicity, and not in the multiplicity and confusion of things)

布尔代数

布尔代数将我们对世界的认识从连续状态扩展到离散状态，它对数学的意义等同于量子力学对物理学的意义；

布尔运算非常简单，但它把数学和逻辑合二为一，而且给了我们一个看待世界全新的视角，开创了数字化的时代；

世界上最简单的计数方法：二进制（0和1）
布尔代数运算的元素：1 （True，真）、0 （False，假）
基本的运算：与（And）、或（or）、非（Not）

And ：必须同为一个属性；一真一假，则为假；

Or ：只要一个属性存在即可；

布尔 ( George Boole ) 19世纪英国人；

1854年《思维规律》 ( An Investigation of the Laws of Thought , on which are founded the Mathematical Theories of Logic Probabilities ) 本书第一次向人们展示了如何运用数学的方法解决逻辑问题

索引

数据库的查询语言（SQL）支持各种复杂的逻辑组合，但它背后的基本原理是基于布尔运算的
计算机做布尔运算是非常快的

第9章图论和网络爬虫

图论

大数学家欧拉 (Leonhard Euler) ；1973年普鲁士的哥尼斯堡的七座桥，每座桥恰好走过一遍并返回原点；欧拉证明了这种走法是不可能的；

广度优先搜索（Breadth-First Search，BFS）：尽可能 “广” 地访问与每个节点直接连接的其他节点
- 先访问与之相邻的所有节点，然后在访问与之间接相连的节点
深度优先搜索（Depth-First Search，DFS）：一路走到底，直到找不到更远的节点；再往回找，看是否还有其他尚未访问的节点
- 先随机选取一个相邻的节点，然后作用为下一个要访问的节点；

网络爬虫

麻省理工的学生马休.格雷（Matthew Gray）在1993年完成第一个网络爬虫；取名为互联网漫游者（www Wanderer）

把互联网作为一张大图；把每一个网页作为一个节点，把那些超链接作为连接网页的弧；有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并它它们存起来；
网络爬虫下载互联网的过程
- 假定从一家门户网站的首页出发，先下载这个网页
- 然后通过分析这个网页，可以找到里面所有的超链接，就等于知道了其所直接链接的全部网页
- 接下来访问、下载分析这些门户网站的邮件等网页，又能找到其他相连的网页
- 同时记录哪个网页下载过了，避免重复；使用一种 “散列表” （Hash Table，哈希表）来记录
构建网络爬虫的工程要点（延伸阅读）
- 考虑的问题是：如何在有限的时间里更多地爬下最重要的网页
- 一般情况下BFS由于DFS

第10章 PageRank：Google的民主表决式网页排名技术

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

PageRank算法的核心思想：在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。 对不同网页的链接区别对待，排名高的网页给予较大的权重（因为那些排名高的网页的链接更可靠）
网页排名算法的高明之处：它把整个互联网当做一个整体来对待。这无意中符合了系统论的观点；以前的信息检索大多把每一个网页当做独立的个体对待，大部分人当初只注意了网页内容和查询语句的相关性，而忽略了网页之间的关系；

第11章确定网页和查询的相关性：TF-IDF

度量网页和查询的相关性的简单方法：直接使用各个关键词在网页中出现的总词频；

例如查询 “原子能的应用”
- 如果一个查询包含 N 个关键词 $w_1, w_2,…$ ，它们在一个特定网页中的词频分别是 $TF_1,TF_2,…$ （TF : Term Frequency ，词频）
- 这个查询和该网页的相关性 = $TF_1 + TF_2 + …$
优化：权重的设定
- 对于不同的词设定不同的权重；一个词预测主题的能力越强，权重越大；（例如 ”原子能“ 应有较大的权重；”应用“ 的权重较小）
- 停止词的权重应为零（例如 ”的“）
若一个词在很少的网页中出现，通过它容易锁定搜索目标，它的权重应该越大；如果一个词在大量网页中出现，看到它仍然不清楚要找什么内容，权重应该更小；
信息检索中常用的权重：逆文本频率指数（Inverse Document Frequency，IDF）

$$IDF = log {D \over D_w}$$

D 所有网页的数量；$D_w$ 该词频出现的网页数量；

若中文网页的数量为D=10亿，而“的“出现的次数 $D_w$ =10亿；则 IDF = log(1) = 0
TF - IDF ：衡量最终的相关性（即加权求和）；被公认为信息检索中最重要的发明

$$TF_1\cdot IDF_1 + TF_2 \cdot IDF_2 + …$$

第12章有限状态机和动态规划：地图与本地搜索

第13章 Google AK-47的设计者：阿米特.辛格

Google内部的排序算法 Ascorer 中A便是他的名字首字母

辛格做事情的哲学：先帮助用户解决80%的问题，再慢慢解决剩下20%的问题，是在工业街成功的秘诀；

很多人失败并不是因为他们不优秀，而是做事情的方法不对。一开始追求大而全的解决方法，之后长时间不能完成，不了了之；

分类

第14、15章

第14章余弦定理和新闻的分类

分类就是把相似的内容归入同一类中

向量：实际上是多维空间中从原点出发的有向线段；
- 如果两个向量的方向一致，则说明响应的新闻的用词比例基本一致
- 可通过计算两个向量的夹角来判断对应新闻主题的接近程度（涉及到余弦定理）
新闻分类的过程
- 已有一些新闻类别的特征向量：进行的是分类；
  - 对于任何一个要被分类的新闻Y，计算它和各类新闻特征向量的余弦相似性，并进行归类
- 缺少新闻类别的特征向量：进行的是聚类
  - 计算所有新闻之间两两的余弦相似性，把相似性大于一个阈值的新闻合成一个小类；N篇新闻被合并成 $N_1$ 个小类
  - 把每个小类作为一个整体，计算小类的特征向量，在计算小类两两之间的余弦相似性，然后合并成大一点的小类，即$N_2$
  $N_2 < N_1 < N$
  - 这样做下去，类别越来也少，每个类越来越大；当某一类太大时，这一类里的新闻之间的相似性就很小了，这时就要停止迭代的过程。至此，自动分类完成；

其他内容

无法进行划分的内容

第16章信息指纹及应用

找到一个函数，将5000一个网址随机映射到128位二进制（即128比特，即16个字节的整数空间）；这16个随机数被称为该网址的信息指纹；可以证明，只要产生随机数的算法够好，就能保证几乎不可能有两个字符串的指纹相同；
伪随机数产生器算法（Pseudo-Random Number Generator，PRNG） ：它将任意很长的整数转化为特定长度的伪随机数
- 最早的PRNG由冯 $\cdot$ 诺依曼提出。他将一个数的平方掐头去尾，取中间的几位数；例如一个四位的二进制数1001（相关于十进制的9），其平方为01010001（十进制的81）；掐头去尾剩下中间的4为0100；当然这种方法产生的不很随机
- 常用的是梅森旋转算法（Mersenne Twister）
从十进制的理解看二进制：333（虽然3个数字都是3，但表达的含义是不同的）
- 最后一个3 ：表示这个数中有3个 $10^0$ ；
- 第二个3 ：表示这个数中有3个 $10^1$
- 第三个3 ：表示这个数中有3个 $10^2$
$333 = 3 \times 10^2 + 3 \times 10^1 + 3 \times 10^0$

$01010001 = 0 \times2^7 + 1\times2^6+ 0 + 1\times2^4 + 0 + 0 + 0 + 1\times2^0 = 64 + 16 + 1 = 81$
信息指纹的特征是不可逆性；即无法根据信息指纹推断出原有的信息；这种性质正是网络加密传输所需要的

第17章谈谈秘密学的原理

当密码之间分布均匀并且统计独立时，提供的信息最少；
- 均匀分布使得无法统计
- 统计独立使得即使知道了加密算法，并且看到一段密码和明码后，也无法破译另一段密码

第18章搜索引擎反作弊和搜索结果权威性问题

在原始信号中混入了噪音，在数学上相当于给两个信号做了卷积。噪音消除的过程就是一个解卷积的过程。
- 如果在发动机很吵的汽车里打电话，对方可能听不清楚。但如果知道了发动机的频率，加上一个与之频率相同、振幅相反的信号，就能够很容易消除发动机的噪音
- 消噪：首发动机的频率是固定的；其次这个频率的噪音重复出现；因此只要采集几秒钟的信号进行处理就能做到
- 广义上讲，只要噪音不是随机并且相关的，就可以检测到并消除；（事实上，完全随机不相关的高斯白噪音是很难消除的）
度量搜索结果的权威性：提及（若一个词作为信息源被多次 “提及”，那么我们有理由相信它是这个主题的权威机构）

第20章最大熵模型

不要把鸡蛋放在一个篮子里，是最大熵原理的一个朴素说法；即当我们遇到不确定时，就要保留各种可能性

最大熵的原理：保留全部的不确定性，将风险降到最低；
最大熵原理指出：对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件；而对未知的情况不要做任何假设。 在这种情况下，概率分布最均匀，预测的风险最小；因为此时概率分布的信息熵最大，成为最大熵模型
- 一个骰子 “每个面朝上的概率分别是多少？” ；等概率的1/6
- 为什么这么回答，因为我们对这个 “一无所知” 的骰子，假定它每个面超上的概率均等是最安全的做法
  - 从信息论上看，这是保留了最大的不确定性，即让熵达到最大
- 继续说，对整个骰子做过处理，“ 已知4点朝上的概率是1/3 ，这种情况下每个面朝上的概率是多少？” ；4点的概率为1/3，其他的为2/15
- 因为已知的条件必须满足（4点的概率为1/3），其余的点仍然未知；所以不过任何假设，因此只好认为它们均等；

第21章拼音输入方法的数学原理

输入法与编码

对于汉字最直接的编码方式：
- 让26个字母对应拼音
- 用10个数字键来消除歧异（汉字一音多意的问题）
对汉字的编码分为如上两部分：对拼音的编码、消除歧异的编码

这决定了一个汉字编码的长度
拼音法早期出现的是双拼，原因是为了缩短对拼音的编码；这些输入法看似节省了一点编码长度，但输入一点也不快，因为它们只是局部优化，而伤害了整体；
- 双拼增加了编码上的歧异性：键盘只有与26个字母，但汉语得到声母和韵母有50多个；结果是很多韵母必须共享一个字母键；增加歧异性的结果就是要从更多候选字中找到想要输入的字
- 增加了每一次击键的时间。因为双拼的方法不自然；研究表明，在脱稿输入时，拆字的思维过程会使思维变慢。（这也是自己之前觉得打字用双拼累的原因）
- 双拼的容错性不好
语言和文字作为通信的编码手段，一个重要的目的是帮助思维和记忆。

一个汉字要敲多少个键盘

香农第一定律指出：对于一个信息，任何编码的长度都大于等于它的信息熵；任何输入法都不可能突破信息熵给定的极限
- 平均编码长度的最小值就是汉字的信息熵

第23章布隆过滤器

布隆过滤器只要散列表 1/8 ~ 1/4的大小就能解决同样的问题

伯顿$\cdot$布隆（Burton Bloom）于1970年提出

实质是一个很长的二进制向量和一系列随机映射函数
工作原理
- 假定存储1亿个邮件地址，先建立一个16亿个比特位（即2亿字节）的向量，然后将其全部清零
- 对每一个邮件地址X，用8个不同的随机数产生器 ($F_1,F_2,…$) 产生8个信息指纹($f_1, f_2,..$)
- 再用一个随机数产生器G把这8个信息指纹映射到1-16亿中的8个自然数 $g_1, g_2,…$
- 现在这8个位置的比特位全部变为1

第24章马尔科夫链的扩展：贝叶斯网络

马尔科夫链（Markov Chain）描述了一种状态序列：每个状态的取值取决于前面有限个状态；

当假定每个状态只与其直接相连的状态有关，而与它间接相连的状态没有直接关系，那么它就是贝叶斯网络。
马尔科夫链是贝叶斯网络的特例，而贝叶斯网络是马尔科夫链的推广
- 相同点：均值考虑了前面一个状态
- 区别：贝叶斯网络的拓扑结构比马尔科夫链灵活，它不受马尔科夫链的链状结构的约束
从数学层面来讲，贝叶斯网络是一个加权的有向图，是马尔科夫链的扩展；从认识论的层面看，贝叶斯网络克服了马尔科夫链的线性约束，它可以把任何有关联的事件统一到它的框架下面；

第25章条件随机法、文法分析

条件随机场是一个特殊的概率图模型；
- 它遵从马尔科夫假设：每个状态的转移概率只取决于相邻的状态
- 与贝叶斯网络的区别在于，它是无向图
先验概率与后验概率
- 先验概率：从原因到结果的论证，是先验的；即根据以往的经验和分析得到的概率；即固定的和已知的；
- 后验概率：从结果到原因的论证，是后验的；即在得到结果的信息之后，重新修正的概率；

第27章期望最大算法：上帝的算法

期望最大化和收敛的必然性
- 如果我们的距离函数足够好，它能保证同一类相对距离较近，而不同类的相对距离较远
- 最终结果：相近的点被聚集到了同一类，同一类中各个点到中心的平均距离$d$ 较近；而不同类中心之间的平均距离$D$ 较远；
EM算法中，若目标函数是凸函数，一定能够得到全局最优解；
- 熵函数一个是凸函数（即向上凸）；如果在N维空间以欧氏距离做度量，聚类中试图优化的两个函数也是凸函数
- 文本分类中的余弦距离不是凸函数，可能得到局部最优解
以最大化(Maximization) 期望值(Expectation) 的算法：EM算法
- 因为它只需要一些训练数据，定义一个最大化函数，剩下的事情交给计算机；经过若干次迭代之后，我们需要的模型就训练好了；这太神奇了，所有称它为上帝的算法

第28章逻辑回归和搜索广告

搜索广告的三个阶段
- 竞价排名
- 根据哪个广告可能被点击，综合出价和点击率（Click Through Rate：CTR）来决定
- 全局最优
逻辑回归模型：将一个事件出现的概率逐渐适应到一条逻辑曲线（Logistic Curve）上，其值域在[0,1]之间
- 逻辑曲线是一条 $S$ 型曲线
- 特点：一开始变化快，逐渐减慢，最后饱和
- 优点：将值域限制在 [0,1] 之间
  
  $$f(z) = {e^z \over e^z+1} = {1 \over 1 + e^{-z}}$$
  
  $ z= \beta_0 + \beta_1x_1 + …$
逻辑回归模型，一种将影响概率的不同因素结合在一起的指数模型；

z 可以是用线性的办法将各个因素组合起来

第29章各个击破算法与云计算

云计算的关键之一：如何把一个非常大的计算问题，自动分解到许多计算能力不是很强的计算机上面来共同完成
分治算法的基本原理：将一个复杂的问题分成若干个简单的子问题进行解决；然后对问题的结果进行合并，得到原有问题的解。

第30章 Google大脑和人工神经网络

人工神经网络

大多数与 “智能” 有点关系的问题，都可以归结为一个多维空间进行模式分类的问题；

人工神经网络所擅长的正是这种分类；

它的模式分类的能力等价于最大熵模型；

如果把不同输出节点上的值看成是一个概率分布，那人工神经网络就等价于一个概率模型

本质是一种有向图，但是一种特殊的有向图；
- 图中的所有节点都是分层的；
  - 每一层节点可以通过有向弧指向上一层节点，但同一层节点之间没有弧相连接，并且每个节点不能约过一层连接到上上一层的节点上
- 每个弧上有一个值（权重），根据这些值可以用一个非常简单的公式算出所指节点的值
通过输入层进行输入，通过中间层，最后到达输出层，输出结果
人工神经网络（总结）：一个分层的有向图；
- 第一层输入节点$X_1, X_2, ..$ 接受输入的信息；
  - 来自这些点的数值 ($x_1,x_2,…$) 按照它们输出弧的权重($w_1,w_2,…$)，根据公式 $G = w_0 + x_1w_1+…+x_nw_n$ 进行线性加权（得到G）
  - 然后再做一次非线性变换 $f(G)$ ，赋值给第二层的节点 $Y$
- 第二层的节点将此数值向后传递，直至第三层节点，直到输出层
- 在模式分类时，最后在输出层哪个节点的数值最大，输入模式就被分在哪一类
需要设计的部分只有两个：
- 它的结构：即网络分几层、每层几个节点、节点之间如何连接（权重）
- 非线性函数$f(G)$的设计：常用的是指数函数 $f(G) = e^G = e ^{w_0+x_1w_1+…}$

训练人工神经网络

确定弧上的权重 w

人工神经网络的训练可以分为监督训练、无监督训练

监督训练：在训练之前需要先取得一个批注好的样本（训练数据），有输入数据和输出数据；训练的目的是找到一组参数w，使得模型给出的输出值的函数（$y(w)$ ）和这组训练数据中的输出值尽可能地一致
- 即得到一个成本函数$C$ ，使得得到的结果与真实的结果的差距最小化；例如可以定义 $C = \sum(y(w)-y)^2$ （即欧几里得距离）
- 现在就变成了一个最优化问题：找最值；
  - 梯度下降法（Gradient Descent）：每一次向 “最陡” 的方向走一步，使得最快达到山顶
无监督学习：没有输出数据；所以要设计一个成本函数
- 成本函数遵从的原则：既然人工神经网络解决的是分类问题，那么希望分类之后，同一类样本（训练数据）之间的距离尽可能的近，不同类的样本应该尽可能的远

人工神经网络与贝叶斯网络

共同点
- 都是有向图，每一个节点的取值只取决于前一级的节点，而且与更前一级的节点无关；即遵从马尔科夫假设
- 训练方法相似
- 对于很多分类问题，两者在效果上也是相似的；但效率可能不同
- 计算量都比较大
不同点
- 人工神经网络在结构上是完全标准化的，而贝叶斯网络更灵活；Google大脑选用人工神经网络就是因为看重它的标准化这一特点
- 人工神经网络虽然神经元函数是非线性的，但各个变量只能先进行线性组合，最后对一个变量（即前面组合出来的结果）进行非线性变换，因此计算机比较容易实现；贝叶斯网络中变量可以组成任意的函数，在获得灵活性的同时也增加了复杂性
- 人工神经网络的输出相对孤立，它可以识别一个个字，但内难以处理一个序列；因此主要用于估计一个概率模型的参数（语音中声学模型参数的训练、机器翻译中语言模型参数的训练）；贝叶斯网络更容易考虑前后的相关性，因此可以解码一个输入的序列（比如将一段语言识别为文字，或将一个英语句子翻译成中文）

Google大脑

Google大脑本质是一种大规模$^1$并行处理$^2$的人工神经网络$^3$。
选用人工神经网络的原因
- 理论上讲可以在多维空间画出各种形状的分类边界，有很好的通用性
- 在过去20多年里，人工神经网络的算法非常稳定，几乎没有改变；google希望自己开发的工具能够设计一次，长时期使用
- 人工神经网络的算法简单，容易实现并行化
Google大脑的实现
- Google大脑中每一块的计算并不是完全独立的，而是要考虑周边的很多块，当切的块数比较多以后，相互的关联总数大致跟块数的平方成正比；而MapReduce中每块的计算是独立的；
  - 这让块与块之间的计算变得复杂，但是能把一个原本无法在一台服务器上完成的大问题分解成大量可在一台服务器上完成的小问题
两点改进
- 降低每一次的迭代量：采用随机梯度下降法（Stochastic Gradient Descent）：在计算成本函数时只需要随机抽取少量的数据来计算，而非像梯度下降法那样对所有的样本都计算一遍，可以大大减少计算量但会牺牲一点准确度
  - 由于训练的数据量非常大，综合考虑时间与准确性之后，采取了相对较快的这种算法
- 减少了训练的迭代次数；采用 L-BFGS（Limited-memory Broyden Fletcher Goldfarb Shanno Method）比一般梯度下降收敛法更快
  - 原理与随机梯度下降相似，但它能根据离最后目标的 “远近” 调整每次迭代的步长；这样经过很少次的迭代就能收敛，但它每次的计算量会增加一点；并且L-BFGS更容易实现并行化

Google大脑中的存储：输入数据存储在本地、模型参数存储在服务器
在生活中，真正能够通用的工具在形式上都是简单的。

第31章数据的重要性

在Google内部，产品经理都遵循：在没有数据之前，不要给出任何结论。
- 对常识/常规现象的理解
- 对未知事件的估计
【共鸣】因为很多基于直觉的并不一定是真实的；
在搜索行业容易形成一种马太效应；即搜索量不足的搜索引擎因为用户点击数据量的不足，搜索质量会越来越差。相反，搜索质量好的会越来越好。一些公司做出了激动的办法：通过搜索条、浏览器、甚至是输入法来搜索用户的点击行为；这些做法的好处在于不仅可以收集到使用该公司搜索引擎本身的点击数据，还能得到用其他搜索引擎的数据。搜索质量的竞争变成了浏览器或者其他客户端软件市场占有率的竞争；
医疗 - 世界性难题：(1) 不同人的细胞&体制是不同的；(2) 疾病的阶段是不同的；(3) 病毒的变异性

语言处理

第1章 文字和语言 Vs. 数学和信息

第2章 自然语言处理

第3章 统计语言模型

第4章 分词

第5章 隐含马尔科夫模型

【精】第6章 信息的度量和作用

信息熵

信息的作用

互信息

相对熵

第7章 贾里尼克和现代语言处理

网络搜搜

第8章 简单之美：布尔代数与搜索引擎

布尔代数

索引

第9章 图论和网络爬虫

图论

网络爬虫

第10章 PageRank：Google的民主表决式网页排名技术

第11章 确定网页和查询的相关性：TF-IDF

第12章 有限状态机和动态规划：地图与本地搜索

第13章 Google AK-47的设计者：阿米特.辛格

分类

第14章 余弦定理和新闻的分类

其他内容

第16章 信息指纹及应用

第17章 谈谈秘密学的原理

第18章 搜索引擎反作弊和搜索结果权威性问题

第20章 最大熵模型

第21章 拼音输入方法的数学原理

输入法与编码

一个汉字要敲多少个键盘

第23章 布隆过滤器

第24章 马尔科夫链的扩展：贝叶斯网络

第25章 条件随机法、文法分析

第27章 期望最大算法：上帝的算法

第28章 逻辑回归和搜索广告

第29章 各个击破算法与云计算

第30章 Google大脑和人工神经网络

人工神经网络

训练人工神经网络

人工神经网络与贝叶斯网络

Google大脑

第31章 数据的重要性

第1章文字和语言 Vs. 数学和信息

第2章自然语言处理

第3章统计语言模型

第4章分词

第5章隐含马尔科夫模型

【精】第6章信息的度量和作用

第7章贾里尼克和现代语言处理

第8章简单之美：布尔代数与搜索引擎

第9章图论和网络爬虫

第11章确定网页和查询的相关性：TF-IDF

第12章有限状态机和动态规划：地图与本地搜索

第14章余弦定理和新闻的分类

第16章信息指纹及应用

第17章谈谈秘密学的原理

第18章搜索引擎反作弊和搜索结果权威性问题

第20章最大熵模型

第21章拼音输入方法的数学原理

第23章布隆过滤器

第24章马尔科夫链的扩展：贝叶斯网络

第25章条件随机法、文法分析

第27章期望最大算法：上帝的算法

第28章逻辑回归和搜索广告

第29章各个击破算法与云计算

第31章数据的重要性