Beauty of Mathematics 数学之美

1. 文字和语言vs数字和信息
2. 自然语言处理——从规则到统计
3. 统计语言模型
4. 谈谈中文分词
5. 隐含马尔可夫模型
6. 信息的度量和作用
7. 贾里尼克和现代语言处理
8. 简单之美——布尔代数和搜索引擎的索引
9. 图论和网络爬虫
10. PageRank——Google的民主表决式网页排名技术
11. 如何确定网页和查询的相关性
12. 地图和本地搜索的最基本技术——有限状态机和动态规划
13. Google AK-47的设计者——阿米特 辛格博士
14. 余弦定理和新闻的分类
15. 矩阵运算和文本处理中的两个分类问题
16. 信息指纹及其应用
17. 由电视剧《暗算》所想到的——谈谈密码学的数学原理
18. 闪光的不一定是金子——谈谈搜索引擎反作弊问题
19. 谈谈数学模型的重要性
20. 不要把鸡蛋放到一个篮子里——谈谈最大熵模型
21. 拼音输入法的数学原理
22. 自然语言处理的教父马库斯和他的优秀弟子们
23. 布隆过滤器
24. 马尔可夫链的扩展——贝叶斯网路
25. 条件随机场和句法分析
26. 维特比和他的维特比算法
27. 再谈文本自动分类问题——期望最大化算法
28. 逻辑回归和搜索广告
29. 各个击破算法和Google云计算的基础

文字和语言vs数字和信息

1. 信息

   • 数字、文字和自然语言一样，都是信息的载体
   • 信息源->编码->信道->解码->信息接收者

2. 文字和数字

   • 文字起源于高效记录信息的需求
   • 不同文明下的人们需要交流（通信），翻译的需求便产生了
   • 翻译之所以能达成，仅仅是因为不同的文字系统记录信息的能力是等价的，i.e.，文字只是信息的载体，而非信息本身
   • 信息的冗余是信息安全的保障
   • 语言的数据（语料），尤其是双语/多语的对照语料对翻译至关重要，它是机器翻译的基础

3. 文字和语言背后的数学

   • 通信，如果信道较宽，信息不必压缩就可以直接传递，如果信道较窄，信息在传递前需要尽可能的压缩，然后在接收端进行解压缩
   • 字母到词的构词法是词的编码规则，语法是语言的编码和解码规则
   • 词可以被认为是有限且封闭的集合，语言则是无限和开放的集合。从数学上讲，前者可以有完备的编解码规则，后者不具备这个特性。

4. 小结

   • 通信的原理和信息传播的模型
   • （信源）编码和最短编码
   • 解码的规则，语法
   • 聚类
   • 校验位
   • 双语对照文本，语料库和机器翻译
   • 多义性和利用上下文消除歧义性

自然语言处理——从规则到统计

1. 机器智能

   • NLP 基于数学模型和统计的方法
   • 语法规则、词性、构词法等
   • 句法分析、语义分析

2. 从规则到统计

3. 小结

统计语言模型

Statistical Language Model，它是今天所有NLP的基础，并广泛应用于机器翻译、语音识别、印刷体/手写体识别、拼写纠错、汉字输入和文献查询。

1. 用数学的方法描述语言规律

   • 贾里尼克的出发点：一个句子是否合理，就看它出现的概率大小如何。
   • 假定S表示某一个有意义的句子，由一串特定顺序排列的词w_1,w2,…,wn 组成，n是句子的长度。现在我们想知道S在文本中出现的概率P(S)。
   • 当然不能统计人类有史以来讲过的所有话来求P(S)，建个模型，既然S=w_1,w2,…,wn, 那么不妨把P(S)展开表示：P(S) = P(w_1,w2,…,wn)
   • 利用条件概率的公式，S这个序列出现的概率等于每一个词出现的条件概率相乘，于是
     P(w_1,w2,…,wn) = P(w₁) ⋅ P(w₂ |w₁) ⋅ P(w₃ |w_1,w2) ⋯ P(w_n |w_{1,w2,…,wn-1})
     其中P(w₁)表示第一个词w₁ 出现的概率，P(w₂ |w₁)表示在已知第一个词的前提下，第二个词出现的概率，以此类推。
   • 计算上来看，P(w₁)很容易算，P(w₂ |w₁)也不太麻烦，从第三项就比较麻烦了，越往后越难算。
   • 俄罗斯数学家马尔可夫，给出了一个偷懒但颇为有效的方法，马尔可夫假设：每当遇到这种情况，就假设任一个词w_i 出现的概率只和它前面的词w_i-1有关。于是：
     P(S) = P(w₁) ⋅ P(w₂ |w₁) ⋅ P(w₃ |w₂) ⋯ P(w_i |w_i-1) ⋯ P(w_n |w_n-1)
     这个公式对应的统计语言模型是二元模型(Bigram Model)。当然也可以假设一个词由前面N-1个词决定，称N元模型。
   • 条件概率P(w_i |w_i-1) = P(w_i-1,w_i) / P(w_i-1)
     估计联合概率P(w_i-1,w_i)和边缘概率P(w_i-1)现在很简单，因为有了大量机读文本（语料库Corpus），只要数一数#(w_i-1,w_i)在统计文本中相邻出现次数和同文本中w_i-1单独出现次数，然后除以语料库的大小#，即可得到相对频度
     f(w_i-1,w_i) = #(w_i-1,w_i) / #
     f(w_i-1) = #(w_i-1) / #
     根据大数定理，只要统计量足够，相对频度就等于概率，即
     P(w_i-1,w_i) ≈ #(w_i-1,w_i) / #
     P(w_i-1) ≈ #(w_i-1) / #
     所以P(w_i |w_i-1) ≈ #(w_i-1,w_i) / #(w_i-1)

2. 延伸阅读：统计语言模型的工程诀窍

   1. 高阶语言模型

      • N元模型，N-1阶马尔可夫假设：每个词和前面N-1个有关
        P(w_i |w_{1,w2,…,wi-1}) = P(w_i |w_i-N+1,w_i-N+2,…,w_i-1)
        实际应用中最多的是N=3的三元模型，更高阶的模型很少使用。
      • N元模型的空间复杂度是O(| V |^N)，| V \vert是语言词典的词汇量，时间复杂度是O(| V |^N-1)，因此N不能很大，N从1到2，从2到3，模型效果提升显著，3到4就不显著了。
      • 是否三元、四元或更高阶的模型能覆盖所有语言现象？不能！因为上下文之间的相关性可能跨度非常大，比如从一个段落跨到另一个段落，这是马尔可夫假设的局限性，这时需要采用其他一些长程的依赖性（Long Distance Dependency）来解决这个问题。

   2. 模型的训练、零概率问题和平滑方法

      • 如果#(w_i-1,w_i) = 0或者#(w_i-1,w_i)和#(w_i-1)都只出现了一次呢？统计的可靠性。
      • 大数定理要求足够的观测值
      • 如何正确的训练一个语言模型？直接的办法是增加数据量，但还是会有很多零概率，“不平滑”。
      • 解决统计样本不足时的概率估计问题！古德和图灵提出了在统计中相信可靠的统计数据，而对不可信的统计数据打折扣的一种概率估计方法，同时将折扣出来的那一小部分概率给予未看见的事件。
      • 古德-图灵的原理：对于没有看见的事件，分配一个很小的比例，看见的事件概率总和则小于1,小多少根据“越是不可信的统计折扣越多”。
      • 假定在语料库中出现r次的词有N_r 个，未出现的词数量为N₀ ，语料库大小为N。那么
        N = ∑_r=1 rN_r
        出现r次的词相对频度是r/N。假定r比较小时，统计可能不可靠，因此出现r次的词在计算它们的概率时要使用一个更小一点的次数d_r = (r+1) ⋅ N_r+1/N_r
        显然 ∑_r d_r ⋅ N_r = N
        一般r越大，N_r 越小，即N_r+1<N_r 。因此，一般d_r < r, d₀ > 0

   3. 语料的选取问题

谈谈中文分词

1. 中文分词方法的演变

   • 词是表达语义的最小单位，因此首先要对句子进行分词
   • 最简单的方法是查字典，这个方法可以解决七八成以上的分词问题，但是太简单了，复杂问题无能为力
   • 最少词数分词理论，但无法解决二义性问题，比如“发展中国家”，正确的是“发展-中-国家”，但从左到右查字典会分成“发展-中国-家”。并且不是所有最长匹配都是正确的，比如“上海大学城书店”，正解“上海-大学城-书店”，而不是“上海大学-城-书店”。
   • 统计语言模型分词，假定一个句子S可以有几种分法，比如3种：
     A1,A2,A3,…,Ak
     B1,B2,B3,…,Bm
     C1,C2,C3,…,Cn
     那么最好的一种分词方法应该保证分词后这个句子出现的概率最大，加入A最好，那么
     P(A1,A2,A3,…,Ak) > P(B1,B2,B3,…,Bm)
     P(A1,A2,A3,…,Ak) > P(C1,C2,C3,…,Cn)
     实现的技巧：穷举所有可能的分词方法并计算概率，计算量相当大，因此看成一个动态规划问题，利用维特比算法快速找到最佳分词。

2. 延伸阅读：工程上的细节问题

   1. 分词的一致性

      • 分词的不一致性可以分为2种：错误，颗粒度不一致
      • 错误分2类：一类是越界型错误，比如把“北京大学生”分成“北京大学-生”，另一类是覆盖型错误，比如把“贾里尼克”拆成4个字，这是改进分词器要尽可能消除的。

   2. 词的颗粒度和层次

      • 人工分词的不一致性大多属于颗粒度不一致性

隐含马尔可夫模型

1. 通信模型

   • 通信的本质是一个编解码和传输的过程
   • 雅格布森通信6要素：发送者（信息源），信道，接收者，信息，上下文，编码
   • 几乎所有的NLP问题都可以等价成通信的解码问题
   • 假设s1,s2,s3,…表示信息源发出的信号，o1,o2,o3,…是接收到的信号，通信中的解码就是根据o1,o2,o3,…还原出s1,s2,s3,…
   • 通信中，从所有源信息中找到最可能产生出观测信号的那一个信息，即已知o1,o2,o3,…，求得令条件概率P(s1,s2,s3,…|o1,o2,o3,…)达到最大值的那个信息串s1,s2,s3,…，即
     s1,s2,s3,… = Arg_{all s1,s2,s3,…} Max P(s1,s2,s3,…|o1,o2,o3,…)
     利用贝叶斯公式，上式等价变换成
     P(s1,s2,s3,…|o1,o2,o3,…) ⋅ P(s1,s2,s3,…) / P(o1,o2,o3,…)
     其中P(s1,s2,s3,…|o1,o2,o3,…)表示信息s1,s2,s3,…在传输后变成接收信号o1,o2,o3,…的可能性，P(s1,s2,s3,…)表示s1,s2,s3,…本身是一个在接收端合乎情理的信号的可能性，P(o1,o2,o3,…)表示在发送端产生信息o1,o2,o3,…的可能性。
     一旦o1,o2,o3,…产生了，它就不会变了，P(o1,o2,o3,…)就是一个可以忽略的常数，上面的公式等价成
     P(s1,s2,s3,…|o1,o2,o3,…) ⋅ P(s1,s2,s3,…)
     这个公式可以用隐含马尔可夫模型来估计。

2. 隐含马尔可夫模型

   • 随机过程：随机变量的时间序列s1,s2,s3,…,s_t ,…,任何一个时刻t，s_t 都是随机的，并且s_t 的取值可能和周围其他状态相关，这样随机过程有2个维度的不确定性
   • 马尔可夫提出一种简化的假设，即随机过程中各个状态s_t 的概率分布，只与它的前一个状态s_t-1有关，即
     P(s_t |s1,s2,s3,…,s_t-1) = P(s_t |s_t-1)
     这个假设被命名为马尔可夫假设，符合这个假设的随机过程称为马尔可夫过程，也称马尔可夫链。
   • 独立输出假设：隐含马尔可夫模型是上述马尔可夫链的一个扩展，任一时刻t的状态s_t 是不可见的，但每个时刻t会输出一个符号o_t ，而且o_t 和s_t 相关且仅和s_t 相关。
   • 基于马尔可夫假设和独立输出假设，可以计算出某个特定状态序列s1,s2,s3,…产生输出符号o1,o2,o3,…的概率

3. 延伸阅读：隐含马尔可夫模型的训练

   • 围绕隐含马尔可夫模型有3个基本问题：1、给定一个模型，如何计算某个特定的输出序列的概率；2、给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列；3、给定足够量的观测数据，如何估计隐含马尔可夫模型的参数。
   • 问题1：Forward-Backward算法
   • 问题2：维特比算法
   • 问题3：模型训练，需要事先知道从前一个状态s_t-1 进入当前状态s_t 的概率P(s_t |s_t-1)，也称转移概率，和每个状态s_t 产生相应输出符号o_t 的概率P(o_t |s_t)，也称生成概率，这些被成为隐含马尔可夫模型的参数，而计算或者估计这些参数的过程称为模型的训练。\ P(o_t |s_t) = P(o_t ,s_t) / P(s_t)
     P(s_t |s_t-1) = P(s_t-1,s_t) /P(s_t-1)
     对于第一个式子，状态输出概率，如果有足够多人工标记的数据，P(o_t |s_t) ≈ #(o_t ,s_t) / #(s_t)
     因为数据是人工标注的，因此这种方法称为有监督的训练方法。第二个式子类似。
     训练隐含马尔可夫模型更实用的方法是仅仅通过大量观测到的信号o1,o2,o3,…就能推算模型参数的方法，这类方法称为无监督的训练算法，主要使用的是鲍姆-韦尔奇算法。
   • 期望最大化（EM），EM过程保证算法一定能收敛到一个局部最优点，一般不能保证找到全局最优点

信息的度量和作用

香农提出信息熵，解决了信息的度量问题，并且量化出信息的作用。

1. 信息熵

   • 一条信息的信息量和它的不确定性有直接的关系。比如要搞清楚一件非常不确定/一无所知的事情，就需要了解大量的信息，相反，如果对某事已经有较多的了解，那么不需要太多的信息就能搞清楚。从这个角度来看，信息量就等于不确定性的多少。
   • 比特（bit）来度量信息量，信息的比特数和所有可能情况的对数函数log有关（log₂ ）。
   • 准确信息量是
     H = -(p1**log p1 + p2**log p2 + … + pn**log pn)
     p_i是概率，H称为信息熵（Entropy），单位是比特。
     对于任意一个随机变量X，它的熵定义如下：
     H(X) = -∑_{x \belong X} P(x)logP(x)
     变量的不确定性越大，熵就越大，所需要的信息量就越大。
   • 冗余度：重复的内容很多，信息量就小，冗余度就大。

2. 信息的作用

   • 信息是消除不确定性的唯一办法
   • 一个事物不确定性为U，引入信息I，如果I<U，这些信息可以消除一部分不确定性，新的不确定性U'=U-I
   • 相关的信息也可以消除不确定性——条件熵
     假定X和Y是两个随机变量，X是我们需要了解的，假定知道了X的随机分布P(X)，也就知道了X的熵：
     H(X) = -∑_{x \belong X} P(x)logP(x)
     假定还知道Y的一些情况，包括它和X一起出现的概率（联合概率分布），以及在Y取不同值的前提下X的概率分布（条件概率分布），定义在Y条件下X的条件熵为：
     H(X|Y) = -∑_{x \belong X, y \belong Y} P(x,y)logP(x|y)
     后续证明H(X) ≥ H(X|Y)，也就是说多了Y的信息，X的不确定性下降了。同样的道理可以定义有两个条件的条件熵：
     H(X|Y,Z) = -∑_{x \belong X, y \belong Y, z \belong Z} P(x,y,z)logP(x|y,z)
     也可以证明H(X|Y) ≥ H(X|Y,Z)

3. 延伸阅读：信息论在信息处理中的应用

   1. 互信息

      • 对两个随机事件相关性的量化度量
      • 假定有两个随机事件X,Y，互信息定义如下：
        I(X;Y) = ∑_{x \belong X, y \belong Y} P(x,y)log (P(x,y)/P(x)P(y))
        I(X;Y)就是H(X)和知道随机事件Y条件下的不确定性（熵H(X|Y)）之间的差异：
        I(X;Y) = H(X) - H(X|Y)
        互信息是一个取值在0到min(H(X),H(Y))之间的函数，X和Y完全相关时为1,完全无关时为0。

   2. 相对熵

      • 也称交叉熵，也用来衡量相关性，衡量两个取值为正数的函数的相似性，定义如下：
        KL(f(x)||g(x)) = ∑_{x \belong X} f(x)log f(x)/g(x)
      • 三条结论：1、对于两个完全相同的函数，相对熵等于0。2、相对熵越大，两个函数差异越大，反之亦然。3、对于概率分布或者概率密度函数，如果取值均大于0,相对熵可以度量两个随机分布的差异性。

贾里尼克和现代语言处理

1. 早年生活

2. 从水门事件到莫妮卡 莱温斯基

3. 一位老人的奇迹

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

技术分为术和道两种，具体的做事方法是术，做事的原理和原则是道。
搜索的“道”——建立一个搜索引擎大致需要做3件事：1、下载（自动下载尽可能多的网页） 2、索引（建立快速有效的索引） 3、排序（根据相关性对网页进行公平准确的排序）

1. 布尔代数

   • 二进制除了计数，还可以表示逻辑的是与非，这个特性在索引中非常有用
   • 运算元素2个：1(true)、0(false)
   • 基本运算：与(and)、或(or)、非(not)，后来发现这3种运算都可以转换成与非(and-not)一种运算
   • 举例：用户搜索文献，输入关键词“原子能应用”，如果文献含有某个关键词，赋予一个逻辑值1,否则赋予0,查询语句“原子能and应用and not原子弹”
   • 布尔代数将我们对世界的认识从连续状态扩展到离散状态

2. 索引

   • 信息检索，基于数据库，SQL语句支持各种复杂的逻辑组合
   • 搜索引擎的索引是一张大表，每行对应一个关键词，每个关键词后跟着一组数字，是包含该关键词的网页序号
   • 整个索引巨大，需要通过分布式的方式存储到不同的服务器上，普遍的做法是根据网页的序号将索引分成很多份（Shards），分别存储在不同的服务器中，每当接受一个查询时，这个查询就被分发到许多服务器中，这些服务器并行处理用户请求并把结果送到主服务器进行合并处理，将结果返回给用户

3. 小结

   • 发觉真理在形式上从来是简单的，而不是复杂和含混的。——牛顿
   • Truth is ever to be found in simplicity, and not in the multiplicity and confusion of things.

图论和网络爬虫

离散数学包括数理逻辑、集合论、图论、近世代数四个分支。数理逻辑基于布尔运算。
如何自动下载互联网所有的网页呢？图论中的遍历（Traverse）算法。

1. 图论

   • BFS, DFS

2. 网络爬虫

3. 延伸阅读：图论的两点补充说明

   1. 欧拉七桥问题的证明

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

   2. 构建网络爬虫的工程要点

      • BFS or DFS? BFS要更多一些。
      • 页面分析和URL提取
      • 记录哪些网页已经下载过的URL表，哈希表

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

对于一个特定的查询，搜索结果的排名取决于两组信息，关于网页的质量信息（Quality），和这个查询与每个网页的相关性信息（Relevance）。本章介绍衡量网页质量的方法，下一章介绍度量搜索关键词和网页相关性的方法。

1. PageRank算法的原理

   • 核心思想：如果一个网页被很多其他网页所链接，它的排名就高。网页排名高的网站贡献的链接权重大。
   • 一个网页Y的排名来自于所有指向这个网页的其他网页X1,X2,…,Xk的权重之和，那么Xi的权重如何度量？先有鸡还是先有蛋？
   • 把这个问题变成一个二维矩阵相乘的问题，再用迭代的方法。先假定所有网页的排名相同，再多次迭代，无论初始值如何选取，算法都保证了网页排名的估计值能收敛到排名的真实值。
   • 稀疏矩阵简化计算
   • 2003 MapReduce并行计算完全自动化，大大缩短计算时间，网页排名更新周期短了许多

2. 延伸阅读：PageRank的计算方法

   • 假定向量B = (b1,b2,…,b_N)^T 为N个网页的排名。矩阵A=[a₁₁…a_MM] M**M为网页之间链接的数目，a_mn代表第m个网页指向第n个网页的链接数。A已知，B未知。
   • 假定B_i 是第i次迭代的结果，那么B_i = A ⋅ B_i-1
   • 初始假设所有网页排名都是1/N，即B₀ = (1/N,1/N,…,1/N)
   • B_i 最终会收敛，无限趋近于B，此时B = B×A，因此当两次迭代结果B_i 和B_i-1之间的差异非常小，接近0时，停止迭代，算法结束。一般10次左右的迭代就基本收敛了。
   • 网页之间的链接数量相比互联网的规模非常稀疏，因此计算网页的网页排名也需要对零概率或者小概率事件进行平滑处理。网页的排名是一个一维向量，对它的平滑处理只能用一个小的常数α ，即
     B_i = [α /N ⋅ I + (1-α)A] ⋅ B_i-1
     其中N是互联网网页的数量，\alpha是一个较小的常数，I是单位矩阵。

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

1. 搜索关键词权重的科学度量TF-IDF

   • 比如搜索“原子能的应用”，分成3个关键词：原子能、的、应用。
   • 直觉：包含这3个词较多的网页应该比包含较少的网页相关，但这样内容长的网页就更占便宜，因此需要根据网页长度对关键词的次数进行归一化，即用关键词的次数除以网页总字数，这个商称为“关键词的频率”，或Term Frequency(TF)。
   • 一个查询包含N个关键词w_{1,w2,w3,…,wN} ，它们在一个特定网页中的词频率分别是TF_{1,TF2,…,TFN} 。那么这个查询和该网页的相关性（相似度）就是：
     TF₁ + TF₂ + … + TF_N
   • 上面的例子中，“的”这个词占了总词频的80%，并且它对确定网页主题几乎没用，称这种词为“停止词”，度量相关性时不做考虑。
   • “应用”是个通用的词，“原子能”是个专业的词，因此需要赋予不同的权重
   • 权重的设定必须满足2个条件：1、一个词预测主题的能力越强，权重越大，反之权重越小。2、停止词的权重为0.
   • 上面的条件概括的讲，假定一个关键词w在D_w 个网页中出现过，那么D_w 越大，w的权重越小，反之亦然。在信息检索中，使用最多的权重是“逆文本频率指数”(Inverse Document Frequency，缩写为IDF)
     IDF = log ( D/D_w )
     其中D是全部网页数
   • 利用IDF，相关性计算的公式就变成加权求和，即
     TF₁ ⋅ IDF₁ + TF₂ ⋅ IDF₂ + ⋯ + TF_N ⋅ IDF_N

2. 延伸阅读：TF-IDF的信息论依据

   • 一个查询（Query）中的每一个关键词（Key Word）w的权重应该反映这个词对查询来讲提供了多少信息。一个简单的办法就是用每个词的信息量作为它的权重，即
     I(w) = -P(w)logP(w) = -TF(w)/N log(TF(w)/N) = TF(w)/N log(N/TF(w))
     其中N是整个语料库的大小，是个可以省略的常数，上式简化成
     I(w) = TF(w)log(N/TF(w))
     但是这样有个缺陷，两个词的TF相同，一个是某篇特定文章中的常见词，另一个是分散在多篇文章中，那么显然第一个词有更高的分辨率，它的权重应该更大。
   • 假设：1、每个文献大小基本相同，均为M个词，即M = N/D = ∑_w TF(w) / D
     2、一个关键词在文献一旦出现，不论次数多少，贡献都等同，这样一个词要么在一个文献中出现c(w) = TF(w)/D(w)次，要么是零。注意，c(w) < M，那么
     TF-IDF(w) = I(w) - TF(w)log M/c(w)
     一个词的信息量I(w)越多，TF-IDF越大，同时w命中文献中w平均出现的次数越多，TF-IDF也越大。

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

智能手机的定位和导航，关键技术有3个：1、利用卫星定位（传统的导航仪都能做到）；2、地址的识别（采用有限状态机）；3、根据用户输入的起点和终点，在地图上规划最短路线或者最快路线（动态规划）。

1. 地址分析和有限状态机

   • 地址的描述是比较复杂的上下文有关的文法，而不是上下文无关。所幸的是，地址的文法是上下文有关文法中相对简单的一种，最有效的地址识别和分析的是有限状态机。
   • 一个有限状态机是一个特殊的有向图，它包括一些状态（节点）和连接这些状态的有向弧。每一个有限状态机都有一个开始状态和一个终止状态，以及若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。
   • 如果一条地址能从状态机的开始状态经过若干中间状态，走到终止状态，那么这条地址就有效，否则无效。
   • 解决2个问题：1、通过一些有效的地址建立状态机；2、给定一个有限状态机后，地址字串的匹配算法。
   • 上述基于有限状态机的地址识别方法，只能进行严格匹配，在实用中会有一些问题：当用户输入的地址不太标准或者有错别字时。但我们希望看到可以进行模糊匹配，并给出一个字串为正确地址的可能性。科学家们提出了基于概率的有限状态机，和离散的马尔可夫链基本上等效。

2. 全球导航和动态规划

   • 全球导航的关键算法是图论中的动态规划
   • 最短路径（Shortest Path）

3. 延伸阅读：有限状态传感器

   • 定义：有限状态机是一个五元组（Σ,S,s₀,δ,f），其中：
     Σ 是输入符号的集合
     S 是一个非空的有限状态集合
     s₀ 是S中的一个特殊状态，起始状态
     δ 是一个从空间S × \Sigma到S的映射函数，即Σ:S × Σ → S
     f 是S中另外一个特殊状态，终止状态。
   • 有限状态传感器（Finite State Transducer, FST），特殊性在于，有限状态机中的每个状态由输入和输出符号定义。
   • 加权的有限状态传感器（Weighted Finite State Transducer, WFST），语音识别、自然语言理解等等

Google AK-47的设计者——阿米特 辛格博士

余弦定理和新闻的分类

新闻的自动分类很大程度上依靠余弦定理。

1. 新闻的特征向量

   • 新闻/任何文本的分类，就是要把相似的放到同一类中
   • 新闻是传递信息的，词是信息的载体，新闻的信息和词的语义是联系在一起的
   • 计算一篇新闻中所有实词的TF-IDF，用这个向量来代表新闻，称为新闻的特征向量

2. 向量距离的度量

   • 金融类的新闻，“股票、利息、债券、基金、银行、物价、上涨”等词出现的频率就高，“二氧化碳、宇宙、诗歌、木匠、诺贝尔、包子”等词出现的频率就低
   • 向量的夹角是衡量两个向量相近程度的度量
   • 余弦定理：三角形ABC，cos(A) = ( b² + c² -a² ) / 2bc
     如果将边AC,AB看成以A起点的向量， cos(A) = / |b||c|
     分子为向量b,c的内积，分母为向量b,c的长度
   • 新闻类别的自动分类，自底向上不断合并的办法：
     1、计算所有新闻之间两两余弦相似性，把相似性大于一个阈值的新闻合并成一个小类（Subclass），这样N篇新闻就被合并成N₁ 个小类，当然N₁ < N
     2、把每个小类中所有的新闻作为一个整体，计算小类的特征向量，再计算小类之间两两余弦相似性，然后合并成大一点的小类，加入有N₂ 个，当然N₂ < N₁
     这样不断做下去，类别越来越少，而每个类越来越大。当某一类太大时，这一类里的一些新闻之间的相似性就很小了，这时就要停止迭代。至此，自动分类完成。

3. 延伸阅读：计算向量余弦的技巧

   数值分析

   1. 大数据量时的余弦计算

      • 计算两个向量夹角时，复杂度为O(|a|+|b|)，如果假定其中一个向量更长，不失一般性|a|>|b|，复杂度为O(|a|)。如果比较一篇新闻和所有其他N篇新闻的相关性，那么计算复杂度为O(N ⋅ |a|)，比较所有N篇新闻两两之间的相关性，复杂度为O(N² ⋅ |a|)。
      • 简化一：简化分母，计算向量a,b余弦时，它们的长度可以存起来，计算a,c时可以直接调用a的长度。
      • 简化二：简化分子，计算两个向量内积的时候，只考虑向量中的非0元素即可。
      • 简化三：删除虚词，包括非必留词“的、是、和”，以及一些连词、副词、介词，如“因为、所以、非常”等等。

   2. 位置的加权

      • 出现在文本不同位置的词，在分类时的重要性也不同，比如标题中的词对主题的贡献远比正文的重要，正文中文章开头和结尾的词比出现在中间的重要

矩阵运算和文本处理中的两个分类问题

1. 文本和词汇的矩阵

   • NLP中最常见的2个分类问题：1、将文本按主题归类（比如将所有介绍奥运会的新闻归到体育类）；2、将词汇表中的字词按意思归类（比如将各种运动的项目名称都归成体育一类）。都可以通过矩阵运算来圆满地、一次性地解决。
   • 新闻分类乃至各种分类其实是一个聚类问题，关键是计算两两新闻的相似度。但因为要两两计算，而且迭代很多次，因此耗时特别长，我们希望用一个办法一次就能把所有新闻相关性计算出来——矩阵运算中的奇异值分解（Singular Value Decomposition, SVD）。
   • 矩阵A来描述成千上万篇文章和几十上百万词的关联性，M×N，N个词，M篇文章，每一行对应一篇文章，每一列对应一个词，元素a_ij是字典中第j个词在第i篇文章中出现的加权词频（比如TF-IDF）。
   • 这个矩阵A会非常非常大，SVD就是把这个大矩阵，分解成三个小矩阵相乘。比如M = 10⁶ , N = 5 * 10⁵ , A = X ⋅ B ⋅ Y
     X = 10⁶ * 100, B = 100 * 100, Y = 100 * 5**10⁵
     三个矩阵元素总数加起来不过1.5亿，不到原来的1/3000,对应的存储量和计算量都会小三个数量级以上。
     三个矩阵都有非常清晰的物理含义。
     X是对词进行分类的一个结果，它的每一行表示一个词，每一列表示一个语义相近的词类，或者简称语义类。这一行的每个非零元素表示这个词在每个语义类中的重要性（相关性），数值越大越相关。
     Y是对文本的分类结果。它的每一列对应一个文本，每一行对应一个主题。这一列中每个元素表示这篇文本在不同主题中的相关性。
     中间的矩阵B表示词的类和文章的类之间的相关性。

2. 延伸阅读：奇异值分解的方法和应用场景

   • SVD: A_MN = X_MM × B_MN × Y_NN
     其中X是一个酉矩阵(Unitary Matrix)，Y是一个酉矩阵的共轭矩阵。酉矩阵的定义是它和它的共轭矩阵转置相乘等于单位阵，因此，它们都是方形的矩阵。B是一个对角阵，只有对角线上是非0值。
   • SVD一般分2步进行：
     1、将矩阵A变换成一个双对角矩阵（除两行对角线元素非0,其余全是0），假设M>N，复杂度为O(MN²)，否则就是O(NM²)。可以利用矩阵A的稀疏性大大缩短计算时间。
     2、将双对角矩阵变成SVD的三个矩阵。复杂度只是第一步的零头，忽略不计。
   • 在文本分类中，M对应文本的数量，N对应词典的大小。如果比较SVD的计算复杂度和利用余弦定理计算文本相似度（一次迭代）的时间，它们处于同一数量级，但是前者不需要多次迭代，因此计算时间短不少。SVD的另一个问题是存储量较大，因为整个矩阵都需要存在内存里，而利用余弦定理的聚类则不需要。

3. 小结

   SVD的优点是能较快的得到结果（在实际应用中），因为它不需要一次次迭代。但是分类结果略显粗糙，因此它适合处理超大规模文本的粗分类。实际工作中，可以先SVD，得到粗分类结果，再利用计算向量余弦的方法，进行几次迭代，得到比较精确的结果。

信息指纹及其应用

1. 信息指纹

   • 任何一段信息（文字、语音、视频、图片等等），都可以对应一个不太长的随机数，作为区别它和其他信息的指纹（Fingerprint）。
   • 只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。
   • 伪随机数产生器算法（Pseudo-Random Number Generator, PRNG），通过它将任意很长的整数转换成特定长度的伪随机数。
   • 梅森旋转算法（Mersenne Twister）
   • 信息指纹的一个特征是其不可逆性，无法根据信息指纹推出原有信息，它的孪生兄弟是密码。
   • 互联网上加密使用基于加密的伪随机数产生器，常用的有MD5, SHA-1等，它们将不定长的信息变成定长的128位或者160位二进制随机数。

2. 信息指纹的用途

   举几个例子

   1. 判定集合相同

      • 网页搜索，有时需要判断两个查询用词是否完全相同（但次序可能不同），比如“北京 中关村 星巴克”和“星巴克 北京 中关村”。更普遍的讲是判断两个集合是否相同。
      • 最笨的方法是对集合中的元素一一做比较，O(N²)
      • 稍微好一点的是对两个集合的元素分别排序，然后顺序比较，复杂度O(NlogN)
      • 将第一个集合放在一张哈希表中，然后把第二个集合的元素一一和哈希表中的元素作对比，时间复杂度O(N)，达到最佳，但是额外使用了O(N)的空间
      • 完美的方法是计算两个集合的指纹，然后直接比较。定义一个集合S={e₁,e₂,…,e_n}的指纹FP(S)=FP(e₁)+FP(e₂)+…+FP(e_n)，FP(e_i)是元素e_i对应的指纹。由于加法的交换率，集合的指纹不因元素出现的次序而改变，如果两个集合元素相同，它们的指纹一定相同。

   2. 判定集合基本相同

      • 随机挑选部分集合元素，计算信息指纹
      • 相似哈希（Simhash）

   3. YouTube的反盗版

      • 视频匹配有两个核心技术：1、关键帧的提取；2、特征的提取。
      • MPEG视频每一帧之间的差异不大，只有极少数的帧是完整的图像，这些称为关键帧。其余帧存储的只是和关键帧相比的差异值。信息指纹表示关键帧。
      • 有了信息指纹，查盗版就类似于比较两个集合元素是否相同了。

3. 延伸阅读：信息指纹的重复性和相似哈希

   1. 信息指纹重复的可能性

      • 信息指纹是通过伪随机数产生的，因此有很小概率会相同。那么有多小呢？
      • 假定伪随机数产生范围是0~N-1，共N个。如果是128位的二进制，则N = 2¹²⁸
        随意挑选两个指纹，重复的可能性是1/N，不重复的可能性是1-1/N。随意挑选三个，不重复的概率为(N-1)(N-2)/N²
        k个指纹不重复的概率是P_k = (N-1)(N-2)…(N-k+1)/N^k-1
        P_k 随着k增加而减小，即产生的指纹多到一定程度，就可能有重复的了。如果P_k < 0.5，那么k个指纹重复一次的数学期望超过1.现在来估计一下这时候k的最大值。
        P_k+1 = (N-1)(N-2)…(N-k)/N^k < 0.5
        N趋于无穷时，P_k+1 ≈ e^1/ne^2/n…e^k/n = exp(-k(k+1)/2N) < 0.5，即
        k² + k + 2Nln0.5 > 0.5
        k > (-1 + \sqrt{1+8Nlog2}) / 2
        对于一个很大的N，k是一个很大的数字。

   2. 相似哈希（Simhash）

      以google在下载网页时排查重复网页的例子来说明

      • 假定一个网页中有若干的词t₁,t₂,…,t_k，权重分布为w₁,w₂,…,w_k。先计算出这些词的信息指纹，为便于说明，假定只用8位二进制的信息指纹。计算哈希分为2步。
      • Step 1：扩展。将8位二进制的指纹扩展成8个实数，用r₁,r₂,…,r₈表示，它们的值如下确定：
        首先，将它们都初始化为0,然后看t₁的指纹（8位），如果t₁的第i位为1,在r_i上加上w₁；如果为0,在r_i上减去w₁。接下来处理t₂，以此类推得到全部r的值,r然后把正数变成1,负数变成0.
      • Step 2：收缩。把8个实数变回一个8位的二进制。如果r_i>0，就把相应的二进制的第i位设置成1,否则设置成0。这样就得到了这篇文章的8位相似哈希指纹。
      • 相似哈希的特点是，如果两个网页的相似哈希相差越小，那么相似性越高。

4. 小结

   信息指纹可以理解成将一段信息随机的映射到一个多维二进制空间中的一个点（一个二进制数字）。只要随机函数做的好，那么不同信息对应的这些点不会重合。

由电视剧《暗算》所想到的——谈谈密码学的数学原理

1. 密码学的自发时代

   • 一个好的编码方法会使得解密者无法从密码中统计出明码的统计信息
   • 把常用的词对应成多个密码

2. 信息论时代的密码学

   • 根据信息论，密码的最高境界是密码被截获后，信息量没有增加
   • 一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀分布使得无从统计，而统计独立能保证即使看到一段密码和明码也不能破译另一段密码。
   • 公开密钥，以加密解密单词Caesar举例，先把它变成一组数，比如它的ASCII码X=067097101115097114（每3位代表一个字母）做明码。现在设计一个密码系统对这个明码加密。
     1、找两个很大的质数P和Q，越大越好，比如100位长的，然后计算它们的乘积
     N = P × Q
     M = (P-1) × (Q-1)
     2、找一个和M互素的整数E，也就是说M和E除了1以外没有公约数。
     3、找一个整数D，使得E × D除以M余1,即E × D mod M = 1。
     现在，世界上先进的、最常用的密码系统就设计好了，其中E是公钥，谁都可以用来加密，D是私钥用于解密，一定要自己保存好。乘积N是公开的，即使别人知道也没关系。
     用下面的公式对X加密，得到密码Y。
     X^E mod N = Y
     没有密钥D，无法从Y恢复X，如果知道D，根据费马小定理，按Y^D mod N = X就可以从Y得到X。
   • 公开密钥的好处有：
     1、简单。就是一些乘除。
     2、可靠。保证产生的密文是统计独立而分布均匀的。
     3、灵活。可以产生很多的公开密钥E和私钥D的组合给不同的加密者。
   • 破解密码的难度，最好的办法是对大数N进行因数分解，得到P和Q。

3. 小结

闪光的不一定是金子——谈谈搜索引擎反作弊问题

• 针对搜索引擎网页排名的作弊（SPAM）
• 早期最常见的作弊方法是重复关键词，用很小的字体和与背景相同的颜色来掩盖这些关键词
• 有了PageRank之后，一个网页被引用的链接越多，排名就可能越靠前，于是有了专门买卖链接的生意
• 通信模型对于搜索反作弊依然适用，在通信中解决噪音干扰问题的基本思路有2条：
  1、从信息源出发，加强通信（编码）自身的抗干扰能力。
  2、从传输来看，过滤掉噪音，还原信息。
• 搜索引擎作弊从本质上看就是对（搜索）排序的信息加入噪音，因此反作弊的第一条是要增强排序算法的抗噪声能力。其次是像在信号处理中去噪音那样，还原原来真实的排名。
• 原始信号混入噪音，数学上相当于给两个信号做卷积。噪音消除的过程是一个解卷积的过程。
• 广义上讲，只要噪音不是完全随机并且前后有相关性，就可以检测到并且消除。（事实上，完全随机不相关的高斯白噪音是很难消除的）
• SEO(Search Engine Optimizer)
• 卖链接的网站都有大量的出链（Out Links），这些出链的特点和不作弊的网站的出链特点大不相同。每一个网站到其他网站的出链数目可以作为一个向量，它是这个网站固有的特征。既然是向量，我们就可以计算余弦距离。有些网站的出链向量之间的余弦距离几乎为1,一般这些网站通常是一个人建的，目的只有一个：卖链接。
• 反作弊另一个工具：图论。图中，如果有几个节点两两互相都连接在一起，它们称为一个Clique。作弊的网站一般需要互相链接，以提高自己的排名，这样就在互联网这张大图中形成了一些Clique。
• 作弊的本质是在网页排名信号中加入了噪音，反作弊的关键是去噪音。

谈谈数学模型的重要性

结论：

1. 一个正确的数学模型应当在形式上是简单的。
2. 一个正确的模型一开始可能还不如一个精雕细琢过的错误模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。
3. 大量准确的数据对研发很重要。
4. 正确的模型也可能受噪音干扰，而显得不准确；这时不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源，这也许能通往重大的发现。

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

1. 最大熵原理和最大熵模型

   • 保留全部的不确定性，将风险降到最小
   • 最大熵原理指出，需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设（不做主观假设这点很重要）。在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以称这种模型叫“最大熵模型”。
   • 举例：拼音转汉字，“Wang-Xiao-Bo”可以被转换成王小波（作家）和王晓波（台湾研究两岸关系的学者）。
   • 对任何一组不自相矛盾的信息，最大熵模型不仅存在，而且是唯一的。此外，它们都有同一个非常简单的形式——指数函数。
   • 下面的公式是根据上下文（前两个词）和主题预测下一个词的最大熵模型，其中w₃是要预测的词（王小波or王晓波），w₁和w₂是它的前两个字（比如说它们分别是“出版”和“小说家”），也就是其上下文的一个大致估计，s表示主题。
     P(w3|w1,w2,s) = 1/Z(w1,w2,s) ** e^{λ₁ (w1,w2,w3)+λ₂ (s,w3)}
     其中Z是归一化因子，保证概率加起来等于1。
     参数 λ 和Z需要通过观测数据训练出来。

2. 最大熵模型的训练

   • 假定我们搜索的排序需要考虑20种特征{x1,x2,…,x20}，需要排序的网页是d，那么即使这些特征互相独立，对应的最大熵模型也“很长”
     P(d|x1,x2,…,x20) = 1/Z(x1,x2,…,x20) ** e^{λ₁ (x1,d)+λ₂ (x2,d)+…+λ₂₀ (x20,d)}
     归一化因子Z(x1,x2,…,x20) = ∑_d e^{λ₁ (x1,d)+λ₂ (x2,d)+…+λ₂₀ (x20,d)}
     这个模型里有很多参数λ 需要通过模型的训练来获得。
   • 最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(Generalized Iterative Scaling)的迭代算法。GIS是一个典型的期望值最大化算法（Expectation Maximization, EM），大致概括为以下几个步骤：
     1、假定第0次迭代的初始模型为等概率均匀分布。
     2、用第N次迭代的模型来估算每种信息特征在训练数据中的分布。如果超过了实际的，就把相应的模型参数变小。否则，将它们变大。
     3、重复步骤2直到收敛。
   • 改进迭代算法IIS(Improved Iterative Scaling)
   • 最大熵模型快速算法的实现很复杂，形式简单，实现复杂。

3. 小结

   最大熵模型可以将各种信息整合到一个统一的模型中。它有很多良好的特性：从形式上看，它非常简单、优美；从效果上看，它是唯一一种既可以满足各个信息源的限制条件，同时又能保证平滑性的模型。

拼音输入法的数学原理

输入法输入汉字的快慢取决于对汉字编码的平均长度，就是击键次数乘以寻找这个键所需要的时间。提高输入法的效率在于同时优化这两点。

1. 输入法与编码

   • 将汉字输入到计算机中，本质上是一个将我们人为约定的信息记录编码——汉字，转换成计算机约定的编码（国标码或者UTF-8码）的信息转换过程。
   • 汉字的编码分为2部分：1、对拼音的编码（参照汉语拼音标准即可）；2、消除歧义性的编码。对一个汉字编码的长度取决于这两方面，只有当这两个编码都缩短时，汉字的输入才能够变快。

2. 输入一个汉字需要敲多少个键——谈谈香农第一定理

   • 从理论上分析，输入汉字到底能有多快？需要用到信息论中的香农第一定律。
   • 假定国标GB2312中一共有6700多个常用汉字，如果不考虑汉字频率的分布，用键盘上26个字母对汉字进行编码，2个字母的组合只能对26² =676个汉字编码，对6700多个汉字需要3个字母，即编码长度为3。当然，我们可以对更常见的字用较短的编码，对不太常见的字用较长的编码。假定每个汉字出现的相对频率是
     p1,p2,…,p6700
     它们的编码长度是
     L1,L2,…,L6700
     那么平均编码长度是
     p1L1 + p2L2 + … + p6700L6700
     香农第一定理指出：对于一个信息，任何编码的长度都不小于它的信息熵。
     因此，平均编码长度的最小值就是汉字的信息熵，任何输入法不可能突破信息熵给定的极限。如果将输入法的字库从国标GB2312扩展到更大的GBK，由于后者非常常见字的频率非常小，平均编码长度比针对国标的大不了多少。
     汉字的信息熵：
     H = -p1logp1 - p2logp2 - … -p6700logp6700
     如果对每个字进行统计，而且不考虑上下文相关性，大致可以估算出它的值在10 bits以内，当然这取决于用什么语料库来做估计。如果假定输入法只能用26个字母输入，那么每个字母可以代表log26 ≈ 4.7 bits的信息，也就是说，输入一个汉字平均需要敲10/4.7 ≈ 2.1次键。
     如果把汉字组成词，再以词为单位统计信息熵，那么每个汉字的平均信息熵会减少，这样平均输入一个字可以少敲零点几次键盘。

3. 拼音转汉字的算法

   • 拼音转汉字的算法和导航寻找最短路径算法相同，都是动态规划。
   • 把一个拼音串对应的汉字从左到右连起来，就是一张有向图，它被称为网格图或者篱笆图（Lattice）。
   • 输入的拼音串：y₁,y₂,…,y_N
     w_i1,w_i2,…是y_i的候选汉字，用w_i表示
     从第一个字到最后一个字可以组成很多句子，每个句子和图中一条路径一一对应，拼音输入法就是根据上下文在给定拼音条件下找到一个最优的句子，即
     w₁,w₂,…,w_N = ArgMax_{w \belong W} P(w₁,w₂,…,w_N | y₁,y₂,…,y_N)
     即从起点到终点的一条最短路径。

4. 延伸阅读：个性化的语言模型

   • 每个人有各自的语言模型，候选词次序的排列
   • 2个问题：1、如何训练一个个性化的语言模型；2、处理好它和通用语言模型的关系。
   • 训练用户特定的语言模型步骤如下：
     1、可以将训练语言模型的文本按照主题分成很多不同的类别，比如1000个，C1,C2,…,C1000。
     2、对于每个类，找到它们的特征向量(TF-IDF) X1,X2,…,X1000。
     3、统计某个人输入的文本，得到他输入的词的特征向量Y。
     4、计算Y和X1,X2,…,X1000的余弦（距离）。
     5、选择前K个和Y距离最近的类对应的文本，作为这个特定用户语言模型的训练数据。
     6、训练一个用户特定的语言模型M1。
     大部分情况下，M1对这个特定用户的输入比通用模型M0好。但对于相对偏僻的内容，M1远不如M0。因此一个更好的办法就是综合两个模型——最大熵模型，但成本较高。因此采用一个简化的模型：线性插值的模型。

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

1. 教父马库斯

2. 从宾夕法尼亚大学走出的精英们

   1. 柯林斯：追求完美

   2. 布莱尔：简单才美

布隆过滤器

1. 布隆过滤器的原理

   • 判断一个元素是否在一个集合中，最直接的方法就是将集合中全部元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合用哈希表（Hash Table）来存储，它的好处是快速准确，缺点是耗费存储空间。
   • 哈希表实现的具体办法是将每一个元素对应成一个8字节的信息指纹，然后将这些信息指纹存入哈希表，但哈希表的存储效率一般只有50%。
   • 布隆过滤器，只需要哈希表1/8到1/4的大小就能解决同样的问题，它实际上是一个很长的二进制向量和一系列随机映射函数。
   • 假定存储1亿个电子邮件地址，先建立一个16亿二进制（bit），即2亿字节的向量，然后所有二进制位全部初始化为0。对于每一个电子邮件地址X，用8个不同的随机数产生器（F1,F2,…,F8）产生8个信息指纹（f1,f2,…,f8）。再用一个随机数产生器G把这8个信息指纹映射到1-16亿中的8个自然数g1,g2,…,g8。现在把这8个位置的二进制全部设置为1.对全部1亿个电子邮件地址都这样处理后，一个布隆过滤器就建成了。
   • 现在用布隆过滤器来检测一个电子邮件地址Y是否在集合中。用相同的8个随机数产生器（F1,F2,…,F8）对Y产生8个信息指纹（s1,s2,…,s8），然后将8个指纹对应到布隆过滤器的8个二进制位，分别是t1,t2,…,t8。如果Y在集合中，显然t1,t2,…,t8对应的8个二进制位一定都是1。
   • 布隆过滤器有极小的误识别率，常见的补救办法是再建立一个小的白名单，存储那些可能被误判的元素。

2. 延伸阅读：布隆过滤器的误识别问题

   • 误判，在检验上被称为“假阳性”，下面估算其概率。
   • 假定布隆过滤器有m比特，里面有n个元素，每个元素对应k个信息指纹的哈希函数。m比特里有些是1,有些是0。
     先看看某个比特为0的概率，比如在这个布隆过滤器中插入一个元素，它的第一个哈希函数会把布隆过滤器中某个比特置1，因此，任何一个比特被置1的概率是1/m，它依然是0的概率则是1-1/m。
     对于布隆过滤器中一个特定的位置，如果这个元素的k个哈希函数都没有把它置1，其概率是(1-1/m)^k。如果布隆过滤器中插入第二个元素，某个特定的位置依然没有被置1的概率为(1-1/m)^2k。插入n个元素还没有置1的概率是(1-1/m)^kn。反过来，一个比特在插入了n个元素后被置1的概率是1-(1-1/m)^kn。
   • 假定n个元素都被插入到布隆过滤器中了，新来一个不在集合中的元素，由于它的信息指纹的哈希函数都是随机的，因此它的第一个哈希函数正好命中某个值为1的比特的概率，就是1-(1-1/m)^kn。一个不在集合中的元素被误判在集合中，需要所有哈希函数对应的比特都为1,其概率为
     (1-(1-1/m)^kn)^k ≈ (1-e^kn/m)^k
     化简后为
     p = (1-e^{(m/n ln2)n/m})^{(m/n ln2)}
     如果n比较大，可近似为
     (1-e^{-k(n+0.5)/(m-1)})^k ≈ (1-e^-kn/m)^k
     假定一个元素用16比特，k=8，那么误判的概率是万分之五。

3. 小结

   布隆过滤器背后的数学远离在于两个完全随机的数字冲突的概率很小。

马尔可夫链的扩展——贝叶斯网路

1. 贝叶斯网络

   • 马尔可夫链描述了一种状态序列，其每个状态值取决于前面有限个状态。现实生活中很多事物相互的关系并不能用一条链来串起来。
   • 把有向图看成一个网络，其中每个圆圈表示一个状态。状态之间的连线表示它们的因果关系。假定在图中马尔可夫假设成立，即每一个状态只和与它直接相连的状态有关，而和它间接相连的状态没有直接关系，那么它就是贝叶斯网络。
   • 两个状态A和B之间没有直接的有向弧链接，只说明它们之间没有直接的因果关系，但并不表明状态A不会通过其他状态间接地影响状态B，只要在图中有一条从A到B的路径，这两个状态就有间接的相关性。所有这些关系，都可以有一个量化的可信度（Belief），用一个概率描述。也就是说，贝叶斯网络的弧上可以有附加的权重。马尔可夫假设保证了贝叶斯网络便于计算。
   • 网络中每个节点概率的计算，都可以用贝叶斯公式来进行，贝叶斯网络因此而得名。由于网络的每个弧都有一个可信度，贝叶斯网络也被称作信念网络（Belief Networks）。

   • 假定只有3个状态，A：“心血管疾病”，B：“高血脂”，C：“家族病史”，假定每个状态取值只有“有”、“无”两种。

     A/B,C	有	无
     有，有	0.9	0.1
     有，无	0.4	0.6
     有，有	0.4	0.6
     有，无	0.1	0.9

     B/C	有	无
     有	0.4	0.6
     无	0.1	0.9

     如果有家族病史，高血脂的可能性是0.4，如果无家族病史，可能性是0.1。 图：A->B, A->C, B->C - 如果要计算A、B和C三者的联合概率分布，可以利用贝叶斯公式：
     P(C,B,A) = P(A|C,B) * P(B|C) * P(C)
     只要代入表中的数值就能计算出来。
     如果问心血管疾病有多大的可能是由家族病史引起的，也可以通过这个贝叶斯网络计算出来。
     P(C|A) = P(C,A) / P(A)
     其中，P(C,A) = P(C,A,!B) + P(C,A,B)
     P(A) = P(C,A,!B) + P(C,A,B) + P(!C,A,!B) + P(!C,A,B) - 贝叶斯网络的拓扑结构比马尔可夫链灵活，不受链状结构的约束，可以更准确的描述事件之间的相关性。 - 使用贝叶斯网络必须先确定网络的拓扑结构，然后还要知道各个状态之间相关的概率。得到拓扑结构和这些参数的过程分别叫做结构训练的参数训练，统称训练。训练贝叶斯网络比较复杂，理论上讲是一个NP-Complete问题，不可计算。但实际应用可以简化。

2. 贝叶斯网络在词分类中的应用

   • 用基于统计的模型分析文本，从重抽取概念，分析主题。不妨称这样的模型为主题模型（Topic Model）。
   • 文本分类，如果把文本和关键词的关联矩阵转90度，进行奇异值分解，或者对每个词以文本作为维度，建立一个向量，再进行向量的聚类，那么得到的是对词的一个分类而不是对文本的分类。分出来的每一类我们称为一个概念。显然，一个概念可以包含多个词，一个词也可以属于多个概念。类似地，一篇文章可以对应多个概念，一个概念也对应多篇文章。用贝叶斯网络建立一个文章、概念、关键词之间的联系。

3. 延伸阅读：贝叶斯网络的训练

   • 使用贝叶斯网络必须先确定网络的拓扑结构，稍微复杂一点的问题就无法人工给出结构了，需要通过机器学习得到。
   • 优化的贝叶斯网络结构要保证它产生的序列从头走到尾的可能性最大，如果是使用概率做度量，那就是后验概率最大。当然，产生一个序列可以有多条路径，从理论上讲，需要完备的搜索（Exhaustive Search），即考虑每一条路径，才能得到全局最优。但计算复杂度是NP-Hard，因此一般采用贪婪算法（Greedy Algorithm），也就是在每一步时，沿着箭头的方向寻找有限步。这样会导致陷入局部最优，并且最终远离全局最优解。一个防止显然局部最优的方法，就是采用蒙特卡罗（Monte Carlo）的方法，用许多随机数在贝叶斯网络中试一试，看看是否显然局部最优，计算量比较大。最近的新方法是利用信息论，计算节点之间两两的互信息，然后只保留互信息较大的节点直接的连接然后再对简化了的网络进行完备的搜索，找到全局优化的结构。
   • 确定网络结构后，就要确定节点之间弧的权重了，假定权重用条件概率来度量。需要一些训练数据，我们需要做的就是优化贝叶斯网络的参数，使得观察到的这些数据的概率（后验概率）达到最大，这个过程就是EM过程（Expectation Maximization Process）。
   • 结构的训练和参数的训练通常是交替进行的

4. 小结

   • 贝叶斯网络是一个加权的有向图

条件随机场和句法分析

条件随机场是计算联合概率分布的有效模型

1. 句法分析计算机算法的演变

   • 句法分析就是为每个句子建立一棵语法树
   • 形式语言采用基于规则的方法，建这棵树的过程就是不断地使用规则将树的末端节点逐级向上合并，直到合并出根节点，即一个整句。这种方法是自底向上的，也可以自顶向下。不论哪一种，都无法避免选择规则时不可能一次选对。如果某一步一旦走岔路了，需要回溯很多步。因此计算复杂度非常大，不可能分析复杂的句子。
   • 80年代 统计文法规则的概率，选择文法规则时，坚持一个原则——让被分析的句子的语法树对概率达到最大。
   • 把句法分析看成是一个括括号的过程
   • 浅层分析（Shallow Parsing），比如找出句子中主要的词组以及它们之间的关系即可——条件随机场

2. 条件随机场

   • 一个隐含马尔可夫模型中，以x1,x2,…,xn表示观测值序列，以y1,y2,…,yn表示隐含的g状态序列，那么x_i只取决于产生它们的状态y_i，和前后的状态y_i-1,y_i+1都无关。如果把x_i和y_i-1,y_i,y_i+1都考虑进来，对应的模型就是条件随机场。
   • 条件随机场是一种特殊的概率图模型（Probabilistic Graph Model），图中顶点代表一个个随机变量，比如x1,y1，顶点之间的弧代表它们相互的依赖关系，通常采用一种概率分布，比如P(x1,y2)来描述。它的特殊性在于，变量之间要遵守马尔可夫假设，即每个状态的转移概率只取决于相邻的状态，这一点，它和另一种概率图模型——贝叶斯网络相同。它们的不同之处在于，条件随机场是无向图，贝叶斯网络是有向图。
   • 条件随机场的节点分为状态节点的集合Y和观察变量节点的集合X。整个条件随机场的量化模型就是这两个集合的联合概率分布模型P(X,Y)
     P(X,Y) = p(x1,x2,…,xn,y1,y2,…,ym)
     由于这个模型的变量特别多，不可能获得足够多的数据来用大数定理直接估计，因此只能通过它的一些边缘分布（Marginal Distribution），比如P(x1), P(y2),P(x1,y3)等等来找出一个符合所有这些条件的概率分布函数。当然，这样的函数通常可能不止一个。根据最大熵原则，我们希望找到一个符合所有边缘分布，同时使得熵达到最大的模型。这个模型是指数函数。每一个边缘分布，对应指数模型中的一个特征f_i，比如针对x1的边缘分布特征就是：
     f_i(x1,x2,…,xn,y1,y2,…,ym) = f_i(x1)
     这个特征表明它和除x1以外的变量无关。如果某个特征函数对应一些变量的取值是0,说明这些特征函数对这些变量不起作用。把这些特征都应用到模型中，得到如下公式：
     P(x1,x2,…,xn,y1,y2,…,ym) = e^{f₁+f₂+…+f_k} / Z
   • 以浅层句法分析为例，说明这个条件随机场模型是如何工作、如何训练的。假定X代表看到的东西，在浅层分析中，它是句子中的词、每个词的词性等；Y代表要推导的东西，它是语法成分，比如名词短语、动词短语、时间短语等。
   • 每一层分析中，模型P(X,Y)，X是句子中的词w1,w2,…,wn、词性pos1,pos2,…,posn、每一层语法成分的名称h1,h2,…,hm等等，Y是操作（左括号，继续留在括号中，右括号）以及新的一层语法成分的名称。如果展开写，就是
     P(w1,w2,…,wn,pos1,pos2,…,posn,h1,h2,…,hm,Y)
     模型的计算量太大，工程上需要做一个近似，把限制条件的组合w1,w2,…,wn,pos1,pos2,…,posn,h1,h2,…,hm拆成很多子集，比如最后的两个词w_n-1,w_n，最后两个句子成分h_m-1,h_m等等，在每一个子集和要预测的操作（以及更高层次的语法成分名称）之间可以找到可靠的统计关系。
     其次，在训练数据中把每一个统计量足够的统计关系作为一个限制条件，我们的目标是寻找符合所有这些限制条件的最大熵模型。

维特比和他的维特比算法

维特比算法是现在数字通信中使用最频繁的算法，同时也是很多NLP的解码算法。

1. 维比特算法

   • 维特比算法是一个特殊但应用最广的动态规划算法
   • 动态规划可以解决任何一个图中的最短路径问题，维特比算法针对一个特殊的图——篱笆网络的有向图（Lattice）的最短路径问题
   • 凡是使用隐含马尔可夫模型描述的问题都可以用维特比算法来解码
   • 假定用户输入的拼音是y1,y2,…yN,对应的汉字是x1,x2,…,xN，那么
     x1,x2,…,xN = ArgMax_{x \belong X} P(x1,x2,…,xN|y1,y2,…,yN)
     = ArgMax_{x \belong X} ∏_{i=1 → N} P(y_i|x_i) ⋅ P(x_i|x_i-1)
     输入的（可见）序列为y1,y2,…,yN，而产生它们的隐含序列是x1,x2,…,xN。
     P(x_i|x_i-1)是状态之间的转移概率，P(y_i|x_i)是每个状态的产生概率。现在，这个马尔可夫链的每个状态的输出是固定的，但是每个状态的值可以变化。比如输出读音“zhong”的字可以是“中”、“重”等多个字。用x_ij表示状态x_i的第j个可能的值，把每个状态按照不同的值展开，就得到篱笆网络（Lattice）。
     从第一个状态到最后一个状态的任何一条路径（path）都可能产生我们观察到的输出序列Y。我们要寻找最可能的这条路径，但状态的组合太多，计算量太大，因此需要一个最好能和状态数目成正比的算法——维特比算法。
   • 维特比算法的基础概括为以下3点：
     1、如果概率最大的路径P（最短路径）经过某个点，比如x₂₂，那么这条路径上从起始点S到x₂₂的一段路径Q，一定是S到x₂₂之间的最短路径。
     2、从S到E的路径必定经过第i时刻的某个状态，假定第i时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中的一条。这样，在任何时刻，只要考虑非常有限条最短路径即可。
     3、结合上述2点，假定从状态i进入状态i+1时，从S到状态i上各个节点的最短路径已经找到，并且记录在这些节点上，那么在计算从S到第i+1状态的某个节点x_i+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这k个节点到x_i+1,j的距离即可。
   • 基于以上3点基础，维特比算法如下：
     1、从S出发，对第一个状态x₁的n₁个节点，计算距离d(S,x_1i)，其中x_1i表示任意状态1的节点。
     2、对于第二个状态x₂的所有节点，计算S到它们的最短距离。d(S,x_2i) = d(S,x_1j) + d(x_1j,x_2i)，一一计算找到最小值，共计算O(n₁n₂)次。
     3、类似step 2继续算下去直到最后一个状态，相邻两个状态S_i,S_i+1的计算复杂度是O(n_i,n_i+1)。假定节点最多的状态有D个节点（即整个网格的宽度为D），那么任何一步的复杂度都不超过O(D²)，网格长度为N，所以整个维特比算法的复杂度是O(ND²)。

2. CDMA技术——3G移动通信的基础

再谈文本自动分类问题——期望最大化算法

可用于各种分类（用户、词、商品分类等），机器学习中最重要的一个算法——期望最大化算法（Expectation Maximization Algorithm）。上帝的算法。

1. 文本的自收敛分类

   • 既不需要事先设定好类别，也不需要对文本两两比较进行合并聚类。而是随机挑选一些类的中心（Centroids），然后来优化这些中心，使它们和真实的聚类中心尽可能一致。
   • 自收敛分类，假设有N篇文本，对应N个向量V1,V2,…,VN，希望分到K类中，这K类的中心是c1,c2,…,cK。无论是向量，还是中心，都是空间中的点。K可以是固定的数，也可以不固定。分类步骤如下：
     1、随机选K个点，作为起始的中心c1(0),c2(0),…,cK(0)。
     2、计算所有点到这些聚类中心的距离，将这些点归到最近的一类中。
     3、重新计算每一类的中心。假定某一类中的v，有m个点，每一个点都多个维度，即
     v_i = v_i1,v_i2,…,v_id
     最简单的方法是用这些类的中心w = w1,w2,…,wm作为其中心，其中第i维的值计算如下：
     w_i = (v_1i+v_2i+…+v_mi) / m
     新的聚类中心和原先的相比会有一个位移。
     4、重复上述过程，直到每次新的中心和旧的中心之间的偏移非常非常小，即过程收敛。

2. 延伸阅读：期望最大化和收敛的必然性

   • 只要距离函数足够好，就能保证同一类相对距离较近，而不同类的相对距离较远。同一类各个点到中心的平均距离d较近，不同类中心之间的平均距离D较远。迭代过程每一次迭代后d比以前变小，D变大。
   • 假设第1类到第K类中分别有n₁,n₂,…,n_k个点，每一类中，点到中心的平均距离是d₁,d₂,…,d_k，因此d = (n₁d₁+n₂d₂+…+n_kd_k)/k。假定第i类和第j类中心之间的距离是D_ij，那么D = ∑_i,j D_ij/k(k-1)。考虑到不同类的大小，即点的数量，那么D加权平均的公式应该是
     D = ∑_i,j D_ijn_in_j/n(n-1)
   • 上述算法包含2个过程和1组目标函数，2个过程是：
     1、根据现有的聚类结果，对所有数据（点）重新进行划分。
     2、根据重新划分的结果，得到新的聚类。
     目标函数就是上面的点到聚类的距离d和聚类之间的距离D，整个过程就是要最大化目标函数。
   • 首先，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；
     接下来，重新计算模型参数，以最大化期望值，即最大化D和-d，这个过程称为最大化过程（Maximization），或M过程。
     这一类算法都称为EM算法。
   • 如果优化的目标函数是一个凸函数，那么EM算法一定能保证得到全局最优解。
     如果不是凸函数，EM算法给出的是局部最优解。

3. 小结

   EM算法只需要一些训练数据，定义一个最大化函数，其余交给计算机。经过若干次迭代，需要的模型就训练好了。

逻辑回归和搜索广告

1. 搜索广告的发展

   • 搜索广告，竞价排名，单位搜索量带来的收入（一般以千次搜索量带来的收入衡量，称为RPM）。Google不是将价格高的广告放前面，而是预测哪个广告可能被点击，结合出价和点击率（Click Through Rate, CTR）来决定广告的投放。
   • 点击率预估，最好的办法是根据以前的经验值来预测，比如广告A展示了n次，被点击了m次，点击率就是m/n。
   • 但实际问题没这么简单：
     1、新广告没有被点击的历史数据。
     2、旧广告绝大多数时候一个查询对应的特定广告不过两三次的点击，统计数据严重不足。
     3、广告的点击量显然和它们摆放的位置有关，做点击率预估时必须消除这个噪音。并且影响点击率的因素很多，都要考虑。
   • 逻辑回归模型（Logistic Regression/Logistic Model）

2. 逻辑回归模型

   • 逻辑回归模型是将一个事件出现的概率适应到一条逻辑曲线（Logistic Curve，其值域在(0,1)之间）上。逻辑曲线是一条S型的曲线，其特点是开始变化快，逐渐减慢，最后饱和。比如一个简单的逻辑回归函数有如下形式：
     f(z) = e^z / (e^z+1) = 1 / (1+e^-z)
   • 逻辑自回归的好处是它的变量范围从负无穷到正无穷，值域范围在0-1之间。对应于[0,1]之间的函数可以是一个概率函数，这样逻辑回归函数就可以和一个概率联系起来了。自变量z的值在负无穷到正无穷的好处是，它可以把这种信号组合起来，不论组合成多大或者多小的值，最后依然能得到一个概率分布。
   • 假设有k个影响点击率的变量,x1,x2,…,xk,线性组合
     z = β₀ + β₁x1 + β₂x2 + … + β_kxk
     每个x_i被称为变量，它们代表了影响概率预测的各种信息，比如广告的位置、广告和搜索词的相关性、广告展现的时间（比如晚上会略高于下午）。对应的 β_i被称为其自回归参数，表示相应变量的重要性，β₀是一个特殊的参数，和任何变量无关，可以保证在没有任何信息时，有一个稳定的概率分布。
   • 上述逻辑回归函数其实是一个一层的人工神经网络，如果需要训练的参数数量不多，所有训练人工神经网络的方法都适用。

3. 小结

   逻辑回归模型是一种将影响概率的不同因素结合在一起的指数模型。

各个击破算法和Google云计算的基础

云计算技术涉及的面很广，从存储、计算、资源调度到权限管理等。云计算的一个关键问题是，如何把一个非常大的计算问题，自动分解到许多计算能力不是很强大的计算机上，共同完成。Google针对这个问题给出了MapReduce，根本原理就是分治算法（Divide-and-Conquer）。

1. 分治算法的原理

   • 分治算法的基本原理是：将一个复杂的问题，分成若干个简单的子问题进行解决。然后，对子问题的结果进行合并，得到原有问题的解。

2. 从分治算法到MapReduce

   • 归并排序（Merge Sort），O(nlogn)
   • 矩阵A × B，A,B都是N × N的矩阵，把矩阵分割成更小的矩阵
   • MapReduce：将一个大任务拆分成小的子任务，并且完成子任务的计算，这个过程叫Map，将中间结果合并成最终结果，这个过程叫Reduce。