数学之美

读书笔记

---

【吴军. 数学之美[M]. 人民邮电出版社, 2012.】
对《数学之美》这本书早有耳闻，最近终于把他读完了。读完的感受是，受益匪浅。
1、统计语言模型
自然语言的处理经历了一个从规则到统计的过程。对于第一批研究自然语言处理的科学家们来说，想到通过制定规则去处理自然语言是很自然的事情，毕竟如果我们能够将语言中的所有规则全部讲给机器，自然机器就能够理解并运用相应的语言。然而实际上这却是不可能的事情，不说各种语句的理解需要结合语气语境的问题，所有规则根本就不可能存在。到了上世纪下半叶，基于规则的句法分析走到了尽头，此时IBM实验室基于统计将语音的识别率从当时的70%提高到了90%让世界震动，而后续的发展也逐渐奠定了基于统计的自然语言处理的主流地位。
先来明确一个简单的前提：一个句子是否合理，就看看它出现的可能性大小。现在来看看书中给出的模型。假定$S$表示一个有意义的句子，由一连串特定顺序排列的词$w_1,w_2,...,w_n$组成，这里n是句子的长度。现在，我们想知道$S$在文本中出现的可能性也就是$S$的概率$P（S）$。

$$P(S) = P(w_1,w_2,...,w_n)$$
而
$$P(w_1,w_2,...,w_n) = P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)...P(w_n|w_1...w_{n-1})$$
当然，实际上$P(w_n|w_1...w_{n-1})$已经非常难算了，因为它的变量非常多，怎么办呢？利用马尔科夫假设，上面的式子而已得到很好的简化，
$$P（S） = P(w_1)P(w_2|w_1)P(w_3|w_2)...P(w_n|w_{n-1})$$
上式就是统计语言中的二元模型。得出了这个模型后，接下来的问题就只剩下如何估算条件概率$P(w_i|w_{i-1})$了，这个根据定义
$$P(w_i|w_{i-1}) = P(w_{i-1},w_i)/P(w_{i-1})$$
来估算就可以了。
2、网页排序算法PageRank
对于每一个网页的搜索而言，搜索结果的排名都至关重要。而这个排名主要取决于两组信息，关于网页的质量信息（Quality），和这个查询与每个网页的相关性信息（Relevance）。具体来说是什么意思呢，打个比方，假如我们要找李开复博士，有100个人举手说自己是李开复。那么谁是真的呢？也许有好几个真的，但即使如此谁又是大家真正想找的呢？如果大家都说在创新工场的那个是真的，那么他就是真的。相应的，在互联网上，如果一个网页被很多其他网页所链接，说明它收到普遍的承认和信赖，那么它的排名就高。这就是PangRank的核心思想。
来实际的看一个例子，假设现在对于网页$Y$，有$X_1,$$X_2,$$X_3,$$X_4$链接到$Y$上，而且他们各自的权重分别是$k_1,$$k_2,$$k_3,$$k_4$，那么$Y$的网页排名$pagerank = k_1 + k_2 + k_3 + k_4$。现在问题变成了$k_1,k_2,k_3,k_4$怎么来。Google的创始人之一拉里-佩奇认为，这个权重应该是这些网页本身的网页排名。可是，计算网页排名的过程需要用到网页本身的排名，这个问题怎么处理。Google的另一位创始人谢尔盖-布林把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。他们两个人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到排名的真实值。再结合稀疏矩阵计算的技巧，佩奇和布林两人实现了这个网页排名算法。
3、贝叶斯网络
贝叶斯网络又称信度网络，是Bayes方法的扩展，是目前不确定知识表达和推理领域最有效的理论模型之一。从1988年由Pearl提出后，已经成为近几年来研究的热点.。一个贝叶斯网络是一个有向无环图(Directed Acyclic Graph,DAG),由代表变量节点及连接这些节点有向边构成。节点代表随机变量，节点间的有向边代表了节点间的互相关系(由父节点指向其子节点)，用条件概率进行表达关系强度，没有父节点的用先验概率进行信息表达。节点变量可以是任何问题的抽象，如：测试值，观测现象，意见征询等。（贝叶斯网络）
贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络可以找出近义词和相关的词。