《数学之美》阅读笔记22-23-24

《数学之美》22-23-24章阅读笔记

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

1教父马库斯

米奇·马库斯：基于统计的自然语言处理

宾夕法尼亚大学LDC语料库

              弟子：迈克尔·柯林斯、艾里克·布莱尔、大卫·雅让斯基、拉纳帕提……

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

·柯林斯：追求完美

迈克尔·柯林斯：自然语言文法分析器

·布莱尔：简单才美

艾里克·布莱尔：基于变换规则的机器学习方法                

第23章 布隆过滤器

1原理

提出：伯顿·布隆  

实质：一个很长的二进制向量和一系列随机映射函数

计算机中的集合：一般是用散列表（哈希表）来存储的

                优点：快速准确

                缺点：耗费存储空间

例子：过滤垃圾邮件

采用散列表，存储一个亿Email地址，需要1.6GB内存（一个Email地址对应一个8字节的信息指纹，散列表的存储效率为50%，即一个Email地址需要占用16个字节）

布隆过滤器：存储一亿个电子邮件地址，建立一个16亿个比特位全部清零（2亿字节）的向量；对于每一个电子邮件地址X，用8个不同的随机数产生器产生8个信息指纹；再用一个随机数产生器把这8个信息指纹映射到1-16亿中的8个自然数；把这个8个位置的比特位全部置1。对于可疑电子邮件地址Y，用相同的8个随机数产生器对Y产生8个信息指纹；将这8个指纹对应到布隆过滤器的8个比特位，分别是；如果对应的比特值为1，则Y在黑名单中。

优点：快速、省空间

缺点：有一定的误识别率

2布隆过滤器的误识别问题

布隆过滤器的“假阳性”：把不在集合中的元素错判成集合中的元素

假定布隆过滤器有m比特，里面有n个元素，每个元素对应k个信息指纹的散列函数。m个比特中有些为1，有些为0。

在布隆过滤器中插入一个元素，它的第一个散列函数会把过滤器中的某个比特置成1，任何一个比特被置成1的概率：，依然为0的概率：。

对于过滤器中一个特定的位置，如果这个元素的k个散列函数都没有把它置为1的概率：。

如果过滤器中插入第二个元素，某个特定的位置仍然为0的概率：。

如果插入n个元素，某个特定的位置仍然为0的概率：。

一个比特在插入n个元素后，被置为1的概率：。

假定布隆过滤器中已经插入n个元素，新插入一个不在集合中的元素，由于它的信息指纹的散列函数是随机的，因此它的第一个散列函数正好命中某个值为1的比特的概率：。不在集合中的元素被误识别为在集合中，需要所有的散列函数对应的比特值均为1，概率为：。

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

1贝叶斯网络

马尔可夫链：描述了一种状态序列，每个状态值取决于前面有限个状态。

贝叶斯网络：每个圆圈表示一个状态，状态之间的连线表示因果关系。假定马尔可夫假设成立，即每个状态只跟与其直接相连的状态有关，跟与其间接相连的状态没有直接关系。

贝叶斯网络中的直接和间接关系，都可以有一个量化的可信度，即用一个概率描述，也就是贝叶斯网络的连线有附加的权重。在网络中，每个节点的概率可以用贝叶斯公式来计算。

马尔可夫链是贝叶斯网络的特例，贝叶斯网络是马尔可夫链的推广。

应用：图像处理、文字处理、支持决策

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

主题模型：基于统计的模型分析文本，从中抽取概念，分析主题。

把文本和关键词的关联矩阵转90度，进行奇异值分解，或者对每个词以文本作为维度，建立一个向量，再进行向量的聚类，得到对词的分类，分出的每一类称为一个概念。

一个概念可以包含多个词，一个词可以属于多个概念。一篇文章可以对应多个概念，一个概念也对应多篇文章。

Phil Cluster：文章、概念和关键词的联系，只考虑关键词与文本关系

Rephil：增加考虑关键词上下文关系

3贝叶斯网络的训练

确定贝叶斯网络的结构：

保证产生的序列——需要完备的搜索——采用贪心算法——会导致陷入局部最优——解决：蒙特卡罗方法；计算互信息

确定节点间的权重：

用条件概率度量——只需优化贝叶斯网络的参数，使得后验概率最大（EM过程）——最大熵模型

结构的训练和参数的训练通常是交替进行的。