第1章 文字和语言vs数字和信息

这章讲了文字、语言与数字、信息的关系。文字是信息的载体，它记录了众多的信息。古人们对文字的考究，用文字记录信息的方式与当前自然语言处理有异曲同工之妙。古人们记录文字为了节省时间，将通俗易懂的白话文压缩成了文言文，只为节省开支，这与当前的通信技术一样。

通信技术，信道较宽，就不必压缩，可直接传递。若信道较窄，则需要对信息进行压缩，压缩后再传递，接收到数据后再进行解压。与古人讲话用白话文，节省财力物力书写用文言文有异曲同工之妙。

关于信息的观点： 信息的冗余是信息安全的保障。信息内容有重复，丢失了其中一份，原有的信息也可以修复。这对信道编码具有指导意义。

语言的数据称之为语料。

总结：

语言的出现是为了解决人类之间的通信问题。文字和数字实际上是信息编码的不同单位，它们都可以承载信息。任何一种语言都是编码方式，而语言的语法就是解码方式。一个人只要懂得它的语法规则便可以理解其中的意思，即对其进行解码操作。这就是语言的数学本质。

第2章 自然语言处理

计算机能否处理自然语言? 可以！

1.自然语言处理经历的两个过程

20世纪50年代到70年代 – 走弯路阶段

人们对自然语言处理的认识局限在人类学习语言的方式上，让电脑模拟人，像人一样理解语言，成果几乎为0.

当前的机器翻译和语言识别依靠的不是让计算机像人一样理解了语言，而是依靠数学，准确说是依靠统计.

当时的人们，认为让机器理解自然语言，要进行的工作室分析语句和获取语义.对于语义的研究和分析,相比较而言要不系统的多，也更难在计算机中表达。

分析句子采用文法规则，句子稍微复杂一点，其文法分析树都异常庞大，难以计算。而且想通过文法规则覆盖哪怕20%的真实语句，文法规则的数量也至少是几万条，语言学家几乎来不及书写。有些语法规则还会出现矛盾，出现矛盾又需要特定的规则去解决这些矛盾，极其复杂。

20世纪70年代 – 基于数学模型和统计学方法

文法规则很难描述自然语言中的多义词，而是严重依赖于上下文，甚至可能是常识，如下面的句子。

The pen is in the box. 笔在盒子中

The box is in the pen. 盒子在栅栏中

这两个句子，是常识性问题，单纯通过文法规则进行判断是很难得出正确结果的。

而基于统计学方法的自然语言处理，随着数据量的不断增大，其准确性越来越高，超出了基于文法规则的自然语言处理。经过15年的较量，文法规则败下阵来。

证明

P(AB)<= P(B) 

P(A|B) = P(AB)/P(B)

P(B)P(A|B) = P(AB)

P(A|B)<=1

所以P(B)>=P(AB)

第3章统计语言模型

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) = \frac{P(w_i-_1,w_i)}{P(w_i-_1)}\]

估计联合概率密度和边缘概率密度比较简单，有了大量的语料库只要数一数 \(w_i-_1,w_i和w_i-_1在文本中出现的频率即可。\) 在除以语料库的大小，即可得到相对频度。根据大数定理，只要统计量足够，相对频率就等于概率。 相对频度如下： $$ f(w_i-_1,w_i) = \frac{(w_i-_1,w_i)}{语料库大小}

f(w_i-_1) = \frac{(w_i-_1)}{语料库大小} \(根据大数定律，统计量足够，频度就等于概率。因此\) P(w_i|w_i-_1) = \frac{(w_i-_1,w_i)}{w_i-_1} $$

2.语料库的选择

如果训练语料和模型应用的领域相脱节，那么模型的效果往往会大打折扣。

第4章谈谈分词

1.最开始的分词技术

最开始的分词技术有匹配字典，将句子分割为最少词组。但这种方式对复杂句式或者存在二义性的词表现结果不尽人意。

改进的分词技术

1990年，郭靖博士用统计语言模型成功解决了分词二义性的问题，将汉语分词的错误率降低了一个数量级。

利用统计语言模型分词的方法，可用几个数学公式进行简单概括。例：假定一个句子S可以有几种分词方式，分词方式如下： $$ A_1 ,A_2 ,A_3 … ,A_k

B_1 ,B_2 ,B_3 … ,B_m

C_1 ,C_2 ,C_3 … ,C_n \(上述分词产生的词数可能不尽相同。最好的一种分词方式应该保证这个句子出现的概率是最大的即：\) P(A_1 ,A_2 ,A_3 … ,A_k)>P(B_1 ,B_2 ,B_3 … ,B_m)

并且

P(A_1 ,A_2 ,A_3 … ,A_k)>P(C_1 ,C_2 ,C_3 … ,C_n) $$

分词技术也可被应用到英语的手写识别。手写时，单词之间的空隙可能没有那么明显，也需要进行分词。中文分词方法可以帮助判别英语单词的边界。 其实自然语言处理的许多数学方法是通用的，与具体语言无关。吴军博士在Google内部设置语言处理的算法时，都会考虑其是否可以很容易的适用于其他语言，这样才能有效地支持上百种语言的搜索。

2.扩展延申

分词的一致性

不同人对句子分词的观点不一样。对同一个句子，大家对北京大学的分词就可能不一样。这是个人习惯问题，差异性很大。最初分词是否准确是通过将机器的分词和人工分词进行对比的。这种对比由于人看法的不同，其结果也难以定论。但随着统计语言模型的广泛应用，不同的分词器产生的结果差异越来越小。

词的颗粒度和层次

人工分词差异的主要原因在于人们对词的颗粒度的认识问题。随着颗粒度的细化，词的意思可能也在发生着改变，甚至是截然不同。在不同的应用中，对词的颗粒度有着不同的要求。==在机器翻译中==，较大的颗粒度有助于提高翻译的结果；==在信息检索时==，细化的颗粒度带来的效果可能更好。

针对不同的应用，我们可以构造不同的分词器，但却非常浪费。我们可以让一个分词器支持不同层次的词的切分。

准备一个基本词表和复合词表。根据这两个词表各建立一个语言模型，在用对应的词表和对应的模型进行分词。

第5章隐含马尔可夫模型

通信模型

自然语言处理的本质与通信很像。都是编码传递，接收解码的过程。如语音识别： 人经过大脑从口中说出语音，这是一个编码传递的过程，计算机接收语音，将其转化为文字的过程是一个接收解码的过程。很多自然语言处理的应用也可以理解为这样的一个过程。
==那么如何通过接收端的观测信号o1,o2,o3,…来推测信号源发送的信息s1,s2,s3…呢?== 还是通过概率的方式来进行估算。在o的情况下，他为s的概率，用数学语言描述如下： $$ P(s_1,s_2,…,s_3|o_1,o_2…,o_3) 求满足条件的s_x的最大值。该公式不好计算出结果，考虑换成贝叶斯公式

\frac{P(o_1,o_2…,o_3 s_1,s_2,…,s_3)*P(s_1,s_2,…,s_3)}{P(o_1,o_2…,o_3)}

由于P(o_1,o_2…,o_3)是确定的，所以分母可以不管，找分子的最大值就行。 $$

第6章信息的度量和作用

1.信息熵

一条信息的信息量与其不确定性有直接的关系。对一件不确定的事，我们需要更多的信息。从这个角度看，信息量就等于不确定性的多少。那么如何度量?

足球比赛，32支球队参加，谁是冠军的信息量。 $$ H = -(p_1logp_1+p_2logp_2+p_3logp_3+…+p_{32}logp_{32}) P是每支球队获胜的概率 变量的不确定越大，熵就越大。

熵的定义 H(X) = -\sum_{x\epsilon X}P(x)logP(x) $$

2.信息的作用

网页搜索的本质是从数十亿条数据中筛选出你想要的。本质上就类似于消除信息的不确定性。根据用户的简短条件，搜寻出他想要知道的信息。当用户输入的信息越多，不确定性就越小(假设是这样的)，得到的信息就越准确。请看下面的公式

假定X和Y是两个随机变量，X是我们需要了解的。假定我们现在知道了X的随机分布P(x)，那也就知道了X的熵 \(H(X) = -\sum_{x\epsilon X}P(x)logP(x)\) 假设我们现在还知道Y的一些情况，包括他和X一次出现的概率，即联合概率分布，以及在Y取不同值得前提下X的概率分布，即条件概率分布。定义在Y条件下的条件熵。 \(H(X|Y) = -\sum_{x\epsilon X y\epsilon Y}P(x,y)logP(x|y)\) 可证明 \(H(x) \geq H(x|y) \\) 在引入Y后，不确定性变小了(熵变小了)。在统计语言模型中，如果把Y看成是前一个字，那么在数学上就证明了二元模型的不确定性小于一元模型。

同理，可定义有两个条件的条件熵 \(\) H(X|Y,Z) = -\sum_{x\epsilon X y\epsilon Y z\epsilon Z}P(x,y,z)logP(x|y,z)

H(X|Y) \geq H(X|Y,Z) $$

三元模型好于二元模型 \(还可证明 H(X|Y,Z) = -\sum_{x\epsilon X y\epsilon Y z\epsilon Z}P(x,y,z)logP(x|y,z)\)

上述的等号在引入的条件熵与信息无关时成立。 不怕噪音吗?

3.互信息!important

两个随机事件相关性的量化单位。当两者完全无关时，互信息为0 假定有两个随机事件X和Y,它们的互信息定义如下： $$ I(X;Y) = -\sum_{x\epsilon X y\epsilon Y}P(x,y)log\frac{P(x,y)}{P(x)P(y)}

H(X) = -\sum_{x\epsilon X}P(x)logP(x)

H(X Y) = -\sum_{x\epsilon X y\epsilon Y}P(x,y)logP(x y)

I(X;Y) = H(X)-H(X|Y) $$ 公式推导

机器翻译中最难的两个问题之一是词义的二义性。解决他的比较好的一个办法是看词与词之间的互信息。互信息越大，相关性越大，越可能是这个翻译的结果。

4.相对熵

背景知识，概率论。不记了。

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

https://baike.baidu.com/item/%E8%B4%BE%E9%87%8C%E5%B0%BC%E5%85%8B/7851117?fr=aladdin百度百科有，就是数学之美上的话。

第8章简单之美-布尔代数和搜索引擎

0.引言

建立一个搜索引擎大致需要做以下几件事

第9章图论和网络爬虫

如何自动下载互联网所有的网页呢?图论遍历算法。

1.图论

2.网络爬虫

BFS

DFS

3.总结

网络爬虫并非简单的BFS或DFS，而是相对复杂的下载优先级排序。 下载过的URL用散列表进行维护 如何维护散列表呢?(上千台服务器一起下载) 明确分工 - xx服务器下x的URL 批处理 - 节省通信时间

第10章PageRank

0.引言

假如我们要找 A 博士，有100个人举手说自己是 A，那么谁是真的？也许有好几个真的，但谁又是我们真正想找的？

1.PageRank

一个网页的可信赖度可以通过它在链接中被引用的次数进行度量。如果有很多网站引用了它，那它的可信赖的就比较高。对于那些信赖度高的网站，它们对网页的引用比普通网站引用更值得信赖。可以用权值来刻画这一重要性。

网页排名应该来自于所有只想和、这个网页的其他网页 X1,X2…Xn 的权重之和，但是这又依赖于其他网页的排名（佩奇提出）。

布林：假设每个网页的初始权重都为 1，对排名进行多次迭代，可解决最终的排名问题。

早期的排名迭代是通过半手工半自动化的方式进行更新，周期长。后来发明了并行计算工具 MapReduce。

2.PageRank的计算方法

书上的公式错了
假定向量 \(B = (b_1,b_2,...,b_N)^T\) 为第一、第二、…第N个网页的网页排名。矩阵 \(A=\left[ \begin{matrix} a_{11} & ... & a_{1n} & ... & a_{1m}\\ ... & &... & & ... \\ a_{m1} & ... & a_{mn} & ... & a_{mM} \\ ... & & ... & & ...\\ a_{M1} & ... & a_{Mn} & ... & a_{MM} \end{matrix} \right]\)

amn代表第m个网页指向第n个网页的link数。A是已知，B是未知，要进行计算，算出B 假定Bi是第i词迭代的结果，那么 Bi = A*Bi-1
初始假设：所有网页的排名都是1/N
B0=(1/N,1/N,1/N,1/N,…,1/N)

然后一直算B0，B1，..，Bk直到Bm与Bm-1之间的差距很小，几乎为0.（收敛） 一般，迭代10次就差不多了。

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

假设某个网页一共有1000个词，其中‘原子能’出现了2次，那它的词频就是0.002

如果一个查询包含N个关键词w1,w2,…,wn,它在一个特定网页的词频分别是：TF1,TF2…TFn,那么这个查询和该网页的相关性就是： \(TF_1 + TF_2 + ... + TF_N\) 逆文本频率指数 假设D是网页数有10亿 Dw是关键词w在D中出现的网页数目，假设它在10亿的网页中出现了200w次，那么逆文本频率指数就是： \(log(\frac{D}{D_w})\)

网页的搜索是通过关键词进行的。关键词要求可以辨别搜索的主题。对于那些毫无意义的停止词(是，和，的等)要进行过滤。我们可以对关键字进行词频统计，词频高的往往不能预测主题，词频低的往往是主题词。我们对每个关键字计算他的权重，将他的词频和逆文本频率指数的乘积累加。 \(TF_1 * IDF_1 + TF_2 * IDF_2 + ... + TF_N * IDF_N\) 延申阅读全是信息论，概论论背景+公式推导，就不记笔记了。

第12章有限状态机和动态规划

地图与本地搜索的核心技术

智能手机的定位和导航功能

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

地址分析是一个复杂的过程。同一个地址有许多不同的描述，还都是正确的描述。如：

地址的文法是上下文有关文法的一种。

其最有效的解决方法还是有限状态机。

有限状态机是一个特殊的有向图，包含一些状态和连接这些状态的简单例子，它要求较为严格，要求完全匹配。

有向图，从起点到终点的路径都是合法路径。

非严格有限状态机（非严格的字符串匹配）

2.全球导航和动态规划

全球导航的关键算法是计算机科学图论中的动态规划(自行百度)

正确的数学模型可以将一个计算量看似很大的问题计算复杂度大大降低。

第13章Google AK-47的设计者阿米特·辛格博士

又到了人物外传的时候了，自个百度吧。

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

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

人识别新闻的类型可以通过阅读判断，计算机呢?计算机只能通过计算来进行判断。

前面讲过的逆文本词频的作用又体现出来了。

新闻的主题和它内容中的关键字是相关联的。我们将新闻单词的TF-IDF值计算出来，然后将新闻变成一组可计算的数字(新闻的特征向量),设计算法，算出相似度即可。

而文章的相似度高不高取决于其特征向量像不像。两个向量越像，其余弦值越–>1.

已知一些新闻类别的特指向量x1,x2,…,xk, \(对\forall一个要被分类的y，算出其余x_1,x_2,...,x_k的余弦，选最大即可\)

若事先没有新闻类别可供参考，则采用如下方法：

这样不断做下去，类别越来越少，每个类越来越大。当某一类太大时，这个类别中的新闻间的相似性就很小了，要停止迭代了。

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

计算新闻分类时，两两来算，太麻烦了。如何简便计算？ 用矩阵!

我们用一个大矩阵描述成千上万篇文章和几十上百万个词的关联性。在这个矩阵中，每一行对应一篇文章，每一列对应一个词，如果有N个词，M篇文章则得到一个MxN的矩阵 \(A=\left[ \begin{matrix} a_{11} & ... & a_{1n} & ... & a_{1m}\\ ... & &... & & ... \\ a_{m1} & ... & a_{mn} & ... & a_{mM} \\ ... & & ... & & ...\\ a_{M1} & ... & a_{Mn} & ... & a_{MM} \end{matrix} \right]\)

这个矩阵好像会非常大。。。。

那么分解吧

奇异值分解。把一个大矩阵分解成小矩阵相乘。存储量和计算量会小非常多。

第16章信息指纹及其应用

“所谓信息指纹，可以简单的理解为将一段信息，随机的映射到一个多维二进制空间中的一个点（一个二进制数字）。只要这个随机函数做得好，那么不同信息对应的这些点就不会重合，因此，这些二进制数字就成了原来的信息所具有的独一无二的指纹。”

本章中大略介绍了信息之为在如下领域内的应用：

1.压缩数据

对于搜索引擎查询的条件，我们可以将其用信息指纹进行表示。如64位的二进制（可能不够）代替上百字符的查询条件，可以减少数据的传输量和存储空间等。

2.检测数据

以视频防止盗为例子。每秒的视频由几十帧组成，连续的帧数之间的差距下，所以一秒中可以用来进行对比的其实就几个。视频帧的对比麻烦(图像识别??)。我们可以将每帧的视频换算成信息指纹 ,对比所要检测视频的信息指纹，相似度达到了一定程度就判断其为抄袭。Goggle的YouToBe的视频防盗就采用过这种方式。

信息指纹的重复率极低，可忽略不计。

第17章密码学的数学原理

这个。它里面讲的是，密码的一些设计原则，和如何破解那些不符合设计原则的代码。还吐槽了下暗战。

第18章闪光的不一定是金子

谈谈搜索引擎反作弊问题和搜索结果的权威性问题

1.搜索引擎的反作弊

根据前面讲的PageRank算法，我们大概知道了谷歌搜索引擎对网页进行排名的算法的要点：关键字，被link的数目，link它的网站的权威性（影响权重）。

作弊者通过重复关键字以此达到增加排名的目的。在角落里，用及其微小的文字重复关键词。如买手机的网站，重复罗列各种手机品牌手机名称。这种做法很容易被搜索引擎发现并纠正（为什么…你倒是说下）。

另一种方式就是增加link次数。有人手中握有几百个网站，通过在这几百个网站上link那些需要提升排名的网站，增加它们的名次。这种做法比较高端。但是由于大量的卖连接也容易被发现。搜索引擎发现源头后可对它进行一些处理。

后来作弊的手段越来越多，也越来越难排查。

解决问题有道和术两种。通过具体的作弊例子，找到作弊的动机和本质进而从本质上解决问题，这是道。

通信模型对于搜索反作弊依然适用。

那些卖链接的网站都有大量的出链，而这些出链的特点与不作弊的网站的出链相比，==特点大不相同==。每一个网站到其他网站的出链数目可以作为一个向量，是这些网站的特征。可采用余弦定理计算余弦值。==有些网站的出链向量之间的余弦距离几乎为1==，一般来讲，这些网站就是一个人建的，目的就是为了买链接。发现该规律后，对PageRank算法进行改进即可。

2.搜索结果的权威性

对同一个问题进行搜索时，可能会得到截然不同的结果，那到底哪个结果才是对的？权威性如何度量呢?

引入一个概念：提及

提及不像网页直接的链接那样清晰，需要用自然语言处理的方式分析出来，即便有了好的算法，计算量也非常大。

以吸烟有害健康为例。通过搜索引擎检索，查询到的结果说吸烟会导致癌症，还指明是引用自一个权威网站，结果去权威网站一看，他给的是不确定，有些实验结果表明会，有些实验结果表明不会。很明显，搜索引擎检索的结果是不权威的。更改了原话的意思。那么如何保证搜索结果的权威性?

计算权威度的步骤如下：

第19章谈谈数学模型的重要性

这章也是讲故事的P171

结论

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

保留最大的不确定性，让熵保持最大。不添加任何主观假设。数学之美P180掷骰子案例。

最大熵原理指出：对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，==对未知条件不要做任何主观假设==。

最大熵模型是否存在?

存在!匈牙利数学家、信息论香农奖得住希萨证明存在且唯一。

它有一个非常简单的形式，指数函数！

下面的公式是更具上下文（前两个词）和主题预测下一个词的最大熵模型。其中w3是要预测的词。w1,w2是它前面的两个词。s表示主题。

\(P(w_3|w_1,w_2,s) = \frac {1}{Z(w_1,w_2,s)}e^{\lambda_1(w_1,w_2,w_3)+\lambda_2(s,w_3)}\) Z 是归一化因子，其概率加起来要为 1

公式中的几个参数 $\lambda$ 和 $Z$ 需要通过观测数据训练出来。

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

输入法输入汉字速度的快慢取决于汉字编码的平均长度。但是单纯的减少编码长度从而减少键盘敲击次数的策略不一定可以提高输入速度。因为，减少编码长度可能会增加寻找一个键的时间和查找对应单词的时间(单词多了，需要多翻页)

1.输入法与编码

对汉字的编码分为2部分：对拼音的编码和消除歧义性的编码。只有这这两个编码都缩短时，汉字的输入才能够变快。

早期的输入法只重视第一部分二忽略第二部分。

以微软的双拼输入法为例：虽然击键次数少了，减少了编码长度，但是输入一点也不快。==因为它只优化了局部，而伤害了整体==。它减少了编码长度，但是增加的单词的歧义性，用户可能需要翻找很多页才能找到自己想要的单词。

一个成功的例子：拼音输入法

拼音输入法虽然编码较长，每个汉字需要多敲几下键盘，但是其有三个有点让它的输入速度并不慢。

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

GB2312简体中文字符集一共有6700多个常用汉字。不考虑汉字的频率分布，用键盘上26个字母对汉字进行编码，两个字母的组合只能对676个汉字进行编码。对6700多个进行编码则需要三个字母的组合。

优化策略：对不常见的字用长编码，对常见的字用短编码。这样平均下来可以缩短每个汉字的编码长度。

假定每一个汉字出现的相对频率是 \(p_1, p_2, p_3 ... p_{6700}\)

他们的编码长度是 \(L_1, L_2, L_3, ... L_{6700}\) 那么平均编码长度是 \(p_1*L_1 + p_2*L_2 + p_3*L_3 + ... + p_{6700}*L_{6700}\)

香农第一定理指出：对于一个信息，任何编码的长度都不小它的信息熵。 \(H = -(p_1*logp_1+p_2*logp_2+...+p_{6700}*logp_{6700})\) 熵的定义 \(H(X) = -\sum_{x\epsilon X}P(x)logP(x)\) 如果对每一个字进行统计，且不考虑上下文相关性，大致可以估算出它的值在10比特以内。[取决于用什么语料库进行估计]

假定输入法只能用 26 个字母进行输入，那么 26 个字母可以代表 $log26≈4.7$ 比特。就是说，输入一个汉字平均需要敲击$10/4.7≈2.1$ 次键

如何进一步优化?

利用上下文，当句子中的一个汉字的拼音敲击完一部分的时候，这个汉字就被提示出来了，这样又可以有效的较少敲击次数，而且根据上下文进行的提示，其为所需要的字的可能性也极大。

如何利用上下文?

最开始是建立庞大的词库，记录长词，从里面进行筛选。但是一字词和二字词占文本的大多数，而它们恰恰又是多音字最严重的。单纯的增加词库大小并不能有效解决问题。==要能够利用上下文去确定到底选那个词==。

利用上下文最好的办法就是借助语言模型。

3.拼音转汉字的算法

拼音转汉字的算法和导航中寻找最短路径的算法相同，都是动态规划。我们可以将汉语输入看成一个通信问题。输入法则是一个将拼音串变到汉字的转换器。每一个拼音可以对应多个汉字，把一个拼音串对应的汉字从左到右连起来，形成有向图。寻找从起点到重点的最短路径。

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

故事 略

第23章布隆过滤器

推荐阅读此博客

编写软件的过程中，要经常性的判断某个元素是否在已知列表中。如单词拼写是否正确[==是否在已知词库中==]，IP是否被加入黑名单，是否是垃圾邮寄等。

如何进行判断呢？

常见方法是采用散列表对数据进行维护。散列表的查找性能十分优异，但是空间利用不足，一般只能用到一半的空间。

引出布隆过滤器：一个根除的二进制向量和一系列随机映射函数。

假定存储一亿个电子邮件地址[散列表实现：将每个电子邮件地址对应成一个8字节的信息指纹]，先建立一个16亿个比特位即2亿字节的向量，然后将16亿个比特全部清零。

对于每一个电子邮件地址X，用8个不同的随机数产生器（F1,F2,…,F8）产生8个信息指纹（f1,f2,…,f8）。

在用一个随机数生成器G把这八个指纹信息映射到一个1-16亿中的8个自然数g1,g2,…,g8。把这八个位置的比特位全部置为1.

一个针对电子邮件地址的布隆过滤器仅建成了。

如何用布隆过滤器检测可疑的电子邮件地址Y是否在黑名单中?

用相同的8个随机数产生器（F1,F2,…,F8）对这个地址产生8个信息指纹s1,s2,…,s8,然后将这8个指纹对应到布隆过滤器的8个比特位，分别是t1,t1,…,t8。如果Y在黑名单中，显然t1,t2,…t8,对应的8个比特值一定是1.

注：然后将这8个指纹对应到布隆过滤器的8个比特位意思是还需要一个将指纹信息对应到布隆过滤器的随机函数，和建立布隆过滤器所用的应该是同一个。

可能遇到不是黑名单却被误判。建立白名单!

误差的推导公式需要简单的求极限基础，可参看此篇博客

第24章马尔可夫链的扩展 - 贝叶斯网络

1.贝叶斯网络

马尔可夫链回忆

马尔可夫链描述了一种状态序列，其中每个状态值取决于前面有限个状态。但对于错综复杂的关系无法用一个链来表示。

什么叫贝叶斯网络?

在网络中，每个节点的概率，都可以用贝叶斯公式来计算，贝叶斯网络因此得名。可以说：马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。

使用贝叶斯网络的前提

使用贝叶斯网络必须先确定这个网络的拓扑结构，然后还有直到各个状态之间相关的概率。得到拓扑结构和这些参数的过程分别交结构训练和参数训练，统称训练。[NP完备问题]

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

可以用基于统计的模型分析文本，从中抽取概念，分析主题。一个概念可以包含多个词，一个词也可以属于多个概念。可以用贝叶斯网络建立一个文章，从而判别概念和关键词之间的联系。