读书笔记：《数学之美》

2019-12-28 本文已影响0人 IT_小马哥

数学之美

不同的文字系统在记录信息上的能力是等价的
图灵测试
通信六要素：发送者（信息源）、信道、接受者、信息、上下文和编码

三语言模型

假定 $S$ 表示某一个有意义的句子，由一连串特定顺序排列的词 $W_1，W_2,...,W_n$ 组成，则 $S$ 出现的概率 $P(S)$ :
$P(S) = P(W_1,W_2,...,W_n)$
$S$ 序列出现的概率等于每一个词出现的条件概率相乘：
$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_2,...,W_{n-1})$

二元模型：

假设任意一个词 $W_i$ 出现的概率只同它前面的词 $W_{ i-1}$ 相关，就变成了马尔科夫假设
$P(W_1,W_2,...,W_n) = 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}) =\tfrac{P(W_i , W_{i-1}) }{P(W_{i-1})}$

根据大数定理：只要统计量足够，相对频度就等于概率
$P(W_{i-1},Wi) = W_{i-1}$ 和 $W_i$ 联合出现的次数 / 样本总数
$P(W_{i-1})= W_{i-1}$ 出现的次数 / 样本总数

极端问题： $(W_{i-1},Wi)$ 没有出现，是否意味着 $P(W_{i-1},Wi) =0$ ？ $(W_{i-1},Wi)$ 出现一次，是否意味着 $P(W_{i-1},Wi) =1$ ？

在语言统计中，零概率问题是无法回避的，我们称之为：不平滑

古德-图灵估计解决了不平滑问题：

对于没有看见的事，我们不能认为发生的概率是零，因此我们从概率的总量中分配一个很小的比例给予这些没有看见的事件，这样一来看见的事件的概率总和就要小于1了，因此需要将所有看见的事的概率调小一点。

假定语料库中出现 $r$ 次的词有 $N_r$ 个，未出现的有 $N_o$ 个，语料库大小为 $N$ ，显然
$N = \sum_{r=1}^{∞} {rN_r}$
当 $r$ 比较小时，出现 $r$ 次的词修正为 $dr$ ，古德-图灵 $dr:$

$d_r= (r+1) * N_{r+1} / N_r$
显然
$N = \sum_{r} {d_r * N_r}$

zifp定律：标识符出现的频率与其在排序列表中的排名或位置成反比。即出现一次的单词的数量多于出现两次的，两次多于三次的，以此类推

一般对出现次数低于某个阈值的词，频率下调，下调的频率总和给未出现的词。，阈值一般设定为8-10

N阶语言模型

假定文本中每个词 $Wi$ 和前面 $N-1$ 词有关，而与更前面的词无关了，实际应用最多的就是 $N=3$ 的三阶模型

语料选取问题
- 如果训练语料和模型应用的领域相脱节，那么模型的效果通常要大打折扣
- 训练语料的噪声高低也会对模型的效果产生一定的影响
四中文分词法
- 在中国古代，断句和说文解字从根本上就是消除歧义性
利用统计模型的分词法
假定一个句子可以有几种分词法，比如三种：
$A_1,A_2,A_3,...A_k\\ B_1,B_2,B_3,...B_m\\ C_1,C_2,C_3,...C_n$
$k,n,m$ 代表不同分词法分出词的数目不同。最好的分词法应该是分完词后这个句子出现的概率最大。
假定第一种方法最好，即：

$P（A_1,A_2,A_3,...A_k）>P（B_1,B_2,B_3,...B_m） and P（A_1,A_2,A_3,...A_k ）>P（C_1,C_2,C_3,...C_n）$
实现技巧：动态规划-维特比

分词的一致性问题

分词的不一致分为：

错误。越界错误：北京大学生，分成“北京大学”“生”；覆盖错误：将人名拆开
颗粒度不一致。 主要在于人们对词颗粒度的认识问题，同一个句子有不同的分词方法。比如：清华大学，可以分为：“清华”、“大学”或者“清华大学”

一般在机器翻译中，颗粒度大好
网页搜索中，颗粒度小好

五隐含马尔可夫模型

通信模型

$p(s_1,s_2,...|o_1,o_2,...) = \frac{P(o_1,o_2,...|s_1,s_2,...) * P(s_1,s_2,...)}{P(o_1,o_2,...)}$

等式左边表示：在接受到信号 $O$ 的情况下，求的源信息 $S$ 的概率
等式右边表示：分子：信息 $S$ 传输后变成 $O$ 的可能性， $P(s)$ 表示 $S$ 本身是一个正常信号的概率；分母：表示发送端产生信号 $O$ 的可能性，由于信息一旦产生，不会改变，，因此 $P(O)$ 为常数
那么等式简化为：
$p(s_1,s_2,...|o_1,o_2,...) = {P(o_1,o_2,...|s_1,s_2,...) * P(s_1,s_2,...)}$

马尔可夫假设

随机过程中各个状态 $S_t$ 的概率分布，只与它前一个状态 $S_{t-1}$ 有关，即
$P(S_t|S_1,S_2,...S_{t-1}) = P(S_t|S_{t-1})$

符合马尔科夫假设的随机过程称为：马尔可夫链

马尔可夫链在经过一段时间T后，就会产生一个状态序列， $S_1,S_2...S_t$ 通过这个序列可以估计出从某个状态 $M_i$ 转换到 $M_j$ 的概率

隐含马尔可夫模型

任一时刻 $t$ 的状态 $S_t$ 是不可见的，在每个时刻 $t$ 会输出一个符号 $O_t$ ,而且 $O_t$ 和 $S_t$ 相关且仅和 $S_t$ 相关。这个输出被称为独立输出假设
基于马尔可夫假设和独立输出假设，我们可以计算出某个特定的状态序列 $S_1，S_2...$ 产生的输出符号 $O_1，O_2$ 的概率
$P(s_1,s_2...,o_1,o_2,...)= \prod_{t} P(S_t|S_{t-1}) . P(o_t | s_t)$

很多自然语言处理问题是和通信的解码问题等价的，因此它们完全可以由隐含马尔可夫模型解决

隐含马尔可夫模型的训练 P57

给定一个模型，如何计算某个特定的输出序列的概率
- Forward-Backward算法
给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列
- 维特比算法
给定足够量的观测数据，如何估计隐含马尔可夫模型的参数
两个参数：
- 转移概率：从一个状态 $S_{t-1}$ 进入到状态 $S_t$ 的概率 $P(S_t|S_{t-1})$
- 生成概率：每个状态 $S_t$ 产生输出符号 $O_t$ 的概率 $P(O_t|S_{t})$
  训练模型的方法：
- Baum-Welch（鲍姆-韦尔奇）算法：首先找到一个能够产生输出序列O的模型参数，然后不断的迭代，直到一个局部最优。

六信息的度量和作用

信息量等于不确定的多少

信息熵

信息熵的定义如下： $P(x)$ 是随机分布
$H(X) = - \sum_{{x∈X}} {P(x) *logP(x)}$
变量的不确定性越大，熵也就越大
一个事物的不确定性假定为 $U$ ，而消除这个不确定性的办法是引入信息I，只有当 $I>U$ 时，才可以消除不确定性
所有的自然语言处理、信息与信号处理的应用都是消除不确定性的过程

条件熵

假设 $X$ 和 $Y$ 具有联合概率分布 $P(x,y)$ ，同时具有条件概率分布 $P(x|y)$ ，则 $Y$ 在 $X$ 下的条件熵为：
$H(X|Y) = - \sum_{{x∈X,y∈Y}} {P(x,y) * logP(x|y)}$

具有结论： $H(X)≥H(X|Y)$ ,即二元模型好于一元模型，以此类推

互信息

假定两个随机事件 $X,Y$ ，互信息的定义如下：

$I(X;Y) = \sum_{x∈X,y∈ Y} \frac{P(x,y)}{P(x) * P(y)}$

其实：在了解其中一个 $Y$ 的前提下，对消除另一个 $X$ 不确定性所提供的信息量。
$I(X;Y) = H(X) - H(X|Y)$

当 $X,Y$ 完全相关，其值为 $1$ ，完全无关，其值为 $0$

相对熵(交叉熵)

定义：衡量两个取值为正数的函数的相似性
$KL(f(x) || g(x)) = \sum_{x∈X}f(x) * log \frac{f(x)}{g(x)}$
三条结论：
1. 对于量完全相同的函数，他们的相对熵等于零
2. 相对熵越大，两个函数的差异越大，反之，相对熵越小，两个函数的额差异越小
3. 对于概率分布或者概率密度函数，如果取值均大于零，相对熵可以度量两个随机分布的差异性

利用相对熵就可以获得TF_IDF

语言模型复杂度用于衡量语言模型的好坏其定义为：在给定上下文的条件下，句子中的每个位置平均可以选择的单词数量。一个模型的复杂度越小，每个位置的词就越确定，模型越好。

七贾里尼克和现代语言

小学生和中学生其实没必要花那么多时间读书，而他们的社会经验、生活能力以及在那时树立起的志向将帮助他们的一生
中学阶段花很多时间比同伴多读的课程，在大学以后用非常短的时间就可以读完
学习（和教育）是一个人一辈子的事情
书本的内容可以早学，也可以晚学，但是错过的成长阶段却无法补回来

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

搜索产品就是：下载（网页）、索引（建立单词和网页索引）、排序（计算分数排序）、
搜索的发展：
1. 首先：用一个很长的二进制数表示一个关键字是否出现在每篇文献中，有多少篇文章，就有多少位，每一位对应一篇文章，1代表文献有关键字，0代表没有，多个关键字查找就是多个二进制的and操作
2. 然后：由于二进制中大部分为0，因此索引变成了一张表，每个表的一行对应一个关键字，每个关键字后跟着一组数字，是包含该关键字的文献的序号
3. 最后：其实就是倒排索引
现在基本采用分布式架构：由于索引的巨大，因此根据网页序号把索引分布在不同服务器，当接收一个查询时，被分发到很多服务器，同时处理结果，然后返回。

九图论和网络爬虫

BFS 和 DFS
每个网页是一个节点，超链接是链接网页的弧，那么整个互联网就是一张图
网络爬虫用BFS还是DFS？BFS优于DFS，因为在有限时间里爬取最重要的网站

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

搜索结果的排名取决与两组信息：网页质量和网页相关性
PageRank的核心思想：如果一个网页被很多其他网页所连所链接，他的排名就应该高，排名高的网页的链接更可靠，权重更大
先假定所有网页的排名是一样的，然后一直迭代，收敛(P103)

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

关键词频率TF，对关键词的次数的归一化，关键词次数除以网页总字数
停止词(无用词)对相关性没帮助，比如:"的"地""是"得"
给每个词一个不同的权重：
1、一个词预测主题的能力越强，权重越大，反之越小
2、停止词权重为零。即IDF逆文本频率指数
$D$ 是全部网页数， $D_w$ 代表关键词 $w$ 在 $D_w$ 个网页中出现
$IDF= log \frac {D }{D_w}$

TF-IDF的信息论依据

P108

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

智能手机的定位和导航功能，关键技术有三点：
1. 利用卫星定位
2. 地址识别有限状态佳
3. 根据用户的起点和终点规划路线动态规划

地址的识别和分析最有效的方法是有限状态机
为了解决模糊地址匹配问题，使用基于概率的有限状态机，基于概率的有限状态机和马尔科夫模型基本等效
语音识别解码器基本上是基于有限状态机的原理
加权的有限状态传感器是天然的自然语言处理的分析工具与解码工具

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

好的算法应该是：简单、有效、可靠性好、易读懂（操作）
先帮助用户解决80%的问题，再慢慢解决剩下的20%

十四余弦定理和新闻分类

如果是同一类新闻，他们的特征向量在某几个维度的值都比较大，而在其他维度的值都比较小
新闻的相似性就是衡量两个向量之间的相似性
因为新闻字数的不同，比较各个维度的大小没有意义，如果两个向量的方向一致，说明相应的新闻用词的比例基本一致
通过计算两个向量之间的夹角来判断对于的新闻主题的接近程度
夹角越大，夹角的余弦越小，两条新闻越不相关；夹角越小，夹角的余弦越大，两条新闻相关度越高
自底向上的新闻分类方法：

计算所有新闻之间的两两余弦相似性，把相似性大于某一个阈值的新闻合并成一个小类，这样 $N$ 篇新闻就被合并成 $N_1$ 个小类， $N_1 < N$
把每个小类中的所有新闻作为一个整体，计算小类的特征向量，在计算小类之间两两的余弦相似性，然后合并成大一点的小类，如有 $N_2，N_2<N_1$
一直这样做下去，当某一个类太大时，停止迭代

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

计算大量新闻的相关性

奇异值分解（SVD）

十六信息指纹及其应用

任何一段信息，都可以对应一个随机数，作为它的信息指纹
哈希表的存储效率一般只有50%
产生信息指纹的算法：伪随机数产生器算法，常用的是 $MD5 和SHA-1$
判定集合的相同：完美的方法是计算两个集合的指纹之和
判断两个网页是否相同：挑选网页主题词作为几个，然后判断集合的信息指纹，一般用IDF的指纹判

相似哈希(simhash)

用于去重

十七密码学的数学原理

公开密钥

找两个很大的素数（质数） $P,Q$ ，然后计算他们的乘积
$N= P * Q\\ M= (P-1) * (Q-1)$
找一个和 $M$ 互素的整数 $E$ ，也就说 $M$ 和 $E$ 除了 $1$ 以外没有公约数
找一个整数 $D$ ，使得 $E * D$ 除以 $M$ 余 $1$ ，即 $E * D mod M =1$
以上： $E$ 是公钥， $D$ 是私钥
用公式对 $X$ 加密，得到密码 $Y$
$X^E mod N = Y$
根据费尔马小定理，可以解密出 $X$
$Y^D mod N =X$

十八搜索反引擎作弊问题

搜索引擎的作弊本质就是对搜索排序的信息加入噪音
反作弊常用做法：
1. 增强排序算法的抗噪音能力
2. 去噪音
针对商业搜索，采用抗干扰强的算法
针对信息类搜索，采用敏感算法

十九谈谈数学模型的重要性

一个正确的数学模型应当在形式上是简单的
一个正确的模型一开始可能还不如一个精雕细琢过的错误模型来的准确，但是如果我们认为大方向是对的，就应该坚持下去
大量准确的数据对研发很重要
正确的模型也可能受到噪音干扰，而显得不准确，这是应该找到噪音的根源

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

保留全部的不确定性，将风险降到最低
需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设
对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的

最大熵

最大熵模型的一个示例：根据前两个词和主题词预测下一个词的最大熵模型

$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$

二十一拼音输入法的数学原理

输入法输入汉字的快慢取决于对汉字编码的平均长度，即击健次数乘以以寻找这个健所需要的时间
根据香农第一定理：对于一个信息，任何编码的长度都不小于它的信息熵

拼音转汉字的算法也是动态规划

拼音输入法就是要根据上下文在给定的拼音条件下找打一个最优解
$w_1,w_2,...,w_n = ArgMaxP(w_1,w_2,...,w_n|y_1,y_2,...,y_n)$
其中 $Y$ 是使用者输入的拼音串， $W$ 是得到的汉字结果。

个性化的语言模型

训练用户特定语言模型步骤：
1. 将训练语言模型的文本按照主题分成很多不同的类别，比如： $C1，C2，。。。Cn$
2. 对于每个类，找到特征向量(TF_IDF) $X_1,X_2,...Xn$
3. 统计某人的输入我文本，得到他输入的词的特征向量Y
4. 计算 $Y和X，X，。。Xn$ 的余弦值
5. 选择前 $K$ 个和 $Y$ 距离最近的类对应的文本，作为这个特点用户语言训练模型的数据
综合通用模型 $M_0$ 和用于特定语言模型 $M_1$ :线性插值模型， $λ(w_{i−1})$ 是一个插值参数

$P(W_i|W_{i-1}) = \lambda(w_{i-1}) * P_0( w_i |w_{i-1})+(1-{\lambda(w_{i-1})}) * P_1(w_i |w_{i-1})$
这种线性插值的模型比最大熵模型效果略差，但是能得到大约80%的收益

二十三布隆过滤器

哈希表的存储效率一般只有50%
原理
1. 新建一个二进制比特的向量，并清零
2. 对于每一个地址（url、邮件地址等） $X$ ，用8个不同的随机数产生器 $F_1,F_2,...F_8$ 产生8个指纹信息 $f_1,f_2,...f_8$
3. 再用一个随机数产生器，把8个指纹信息映射到二进制比特的向量中，并设置为1
4. 以后每个新的地址 $X$ 都经过步骤二和步骤三，如果发现8个二进制都是1，则表示 $X$ 已经存在
有很小的概率误判
数学原理：完全随机的两个数字冲突概率很小

二十四马尔可夫链的扩展--贝叶斯网络

每一个状态只和它直接相连的状态有关，而和它间接相连的状态没有直接关系
使用贝叶斯网络必须知道网络的拓扑结构和状态之间的概率
得到拓扑结构和概率参数的过程称为训练

贝叶斯在词分类中的应用

用基于统计的模型分析文本，从中抽取概念，分析主题。这样的模型为主题模型（Topic Model）
1. 将文本聚类
2. 同一类的文章共享很多关键词。不同文章就通过关键词建立一种关系。
3. 将关键词分类，分出的类称为一个概念
那么，一个概念可以包含很多词，一个词也可以属于很多概念，一篇文章可以对应对各概念，一个概念也可以对应多篇文章

二十五条件随机场和句法分析

在隐含马尔可夫的基础上（ $x_i$ 只与产生它的状态 $y_i$ 有关），将状态 $y_{i-1}和y_{i+1}$ 也考虑进来
和贝叶斯网的区别就是无向图

二十六维特比和他的维特比算法

维特比算法是针对一个特殊的图--篱笆网络的有向图的最短路径问题而提出的。
凡使用隐含马尔科夫模型描述的问题都可以使用它来解码，包括：数字通信、语音识别、机器翻译、拼音转汉字、分词等

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

根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望计算过程（E过程）
然后重新计算模型参数，以最大化期望值，这个过程称为最大化过程（M过程）

二十八逻辑回归与广告搜索

搜索广告的三个阶段
1. 竞价排名
2. 预测哪个广告可能被点击，结合出价和点击率来决定广告的投放
3. 全局优化
逻辑回归模型

将一个事情出现的概率适应到一条逻辑曲线上，定义域 $（-∞，+∞）$ ，值域是（ $0,1$ ）正好可以将其与概率分布联系起来

一个逻辑回归的函数如下：
$f(z) = \frac {1}{1 + e ^{-z}}$
假如有 $k$ 个影响点击率的变量 $x_1,x_2,...,x_k$ ，用线性的办法组合：
$z = β_0 + β_1x_1 + ... + β_kx_k$
其中 $x_i$ 称为变量，代表了影响概率预测的各种信息。 $β_i$ 是回归参数，表示变量的重要性。
逻辑回归函数本质是一个一层的人工神经网络。
训练最大熵模型的IIS方法可以直接用于训练逻辑回归函数的参数。

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

云计算的关键问题是：如何把一个非常强大的计算问题，自动分解到许多计算能力不是很强大的计算机上。
谷歌采用MapReduce完成，即分治算法。
将一个复杂的问题，分成若干个简单的子问题进行解决。然后，对子问题的结果进行合并，得到原有问题的解。

计算复杂度

计算复杂度用变量 $N$ 来衡量，如果一个算法的计算量是 $N$ 的多项式函数，则认为这个算法是多项式函数复杂度。
如果一个问题存在一个多项式函数复杂度的算法，则这个问题成为 $P$ 问题，
如果计算量比 $N$ 的多项式函数还高，理论上可以计算，实际是不可计算的，称为非多项式问题（ $NP$ 问题）比如围棋下步最优落子。
对于一个 $NP$ 问题，可以在多项式函数复杂度的时间里证实这个方法正确与否，那么称为： $NP$ 完全问题
如果一个问题，它的计算复杂度至少是 $NP$ 完全，那么被称为： $NP-Hard$ 问题。

后记

采用错误的模型在特定的场合，或许勉强有效，但是错误的模型终究是远离真理的，其负面影响会渐渐表现出来。
世界顶级的科学家都能把自己领域最深奥的道理用很简单的比喻介绍清楚。

读书笔记：《数学之美》

数学之美

三 语言模型

二元模型：

N阶语言模型

语料选取问题

四 中文分词法

利用统计模型的分词法

分词的一致性问题

五 隐含马尔可夫模型

通信模型

马尔可夫假设

隐含马尔可夫模型

隐含马尔可夫模型的训练 P57

六 信息的度量和作用

信息熵

条件熵

互信息

相对熵(交叉熵)

七 贾里尼克和现代语言

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

九 图论和网络爬虫

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

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

TF-IDF的信息论依据

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

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

十四 余弦定理和新闻分类

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

计算大量新闻的相关性

十六 信息指纹及其应用

相似哈希(simhash)

十七 密码学的数学原理

公开密钥

十八 搜索反引擎作弊问题

十九 谈谈数学模型的重要性

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

最大熵

二十一 拼音输入法的数学原理