数学之美读书日记
判断句子是否合乎语法
判断一个句子是否符合人们的习惯（合乎人们的说话习惯）只需要计算出该句子出现的概率就行
假设有一句话为 $ S=w_1w_2w_3…w_n(n=len(s))$
则 P ( S ) = P ( w 1 ) ∗ P ( w 2 ∣ w 1 ) ∗ P ( w 3 ∣ w 1 , w 2 ) ∗ . . . ∗ P ( w n ∣ w 1 , . . . , w n − 1 ) P(S)=P(w_1)*P(w_2|w_1)*P(w_3|w_1,w_2)*...*P(w_n|w_1,...,w_{n-1)} P(S)=P(w1)∗P(w2∣w1)∗P(w3∣w1,w2)∗...∗P(wn∣w1,...,wn−1)
马尔可夫提出了一个假设“假设任意一个单词出现的频率只和他前面一个单词有关”(十分任性的假设…)，（三阶的马尔可夫假说则是只和他前面两个单词有关，一般用三阶的）
那么 P ( S ) = P ( w 1 ) ∗ P ( w 2 ∣ w 1 ) ∗ P ( w 3 ∣ w 2 ) ∗ . . . ∗ P ( w n ∣ 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(S)=P(w1)∗P(w2∣w1)∗P(w3∣w2)∗...∗P(wn∣wn−1)
限定在某一个语料库(样本库) P ( w i ∣ w i − 1 ) P(w_{i}|w_{i-1}) P(wi∣wi−1)可以化简为 # ( w i ∣ w i − 1 ) # ( w i − 1 ) \frac{\#(w_{i}|w{i-1})}{\#(w_{i-1})} #(wi−1)#(wi∣wi−1)
换言之就是统计处 w i − 1 w_{i-1} wi−1和 w i w_i wi相邻的总情况数和 w ( i − 1 ) w(i-1) w(i−1)出现的次数即可，十分的易于处理。
当然真正的算法没有这么丝滑，因为我们可能会遇见因为不满足大数定律而导致的种种问题，要查的两个词同时出现的次数为0，要查的两个词总共就出现了很少的次数，这些都会造成很大的误差，而我们没有那种满足大数定律的语料库（就算有，查找也不是一个很轻松的活）所以我们不可避免的要处理这种情况，方法就是卡兹退避法，关于卡兹退避法遇到了在细谈吧，还是有点小复杂的…
分词
这是一个已经被近乎完美解决的问题，我们只需要知道一些注意点就行，首先是人工分词会随着人的主观意志而产生些许分歧，对于有歧义的句子，我们可以通过上面的方法来进行选择，但是枚举全部的分词可能太低效，我们可以通过DP+维特比算法来进行优化，另外就是要注意词的颗粒度，不同的应用对于颗粒度的需求不同，比如“联想公司”对于机器翻译来讲，当作一个整体会更好，可以直接找到对应的logo，但是对于搜索引擎来讲颗粒度小一点可能会更加符合用户的需求。
什么是机器翻译呢？ 其实很简单我们知道一个原语言的字符串，我们要想可能是哪个字符串可能会翻译出来这样的一系列字符串呢，因为单词往往具有多义性，所以我们得到的答案往往是有很多个的，这个时候我们就要找其中可能性最高的，这正是隐马尔可夫模型能解决的，因为上面的问题明显有两个性质，我们要求的字符串可以看作是满足马尔可夫性质（每一个状态只和前面有限个状态相关）的不可观测的状态链，这个状态链与一个可观测的状态链（译文）相关
隐马尔可夫模型
信息的度量和作用
信息熵
信息熵代表信息量的大小，单位比特，这里照办《数学之美》上的解释，假设现在有32只球队来争夺冠军，你问另一个人谁是冠军，他不愿意直接告诉你，而是让你猜，每猜一次就要交1块钱，那么根据二分，我们最快5次就猜到了，那么这个信息就值5块钱，“5块钱”就是这个信息的信息熵。但是这是建立在所有球队实力完全一致的情况下的，假设你知道有几个球队明显强于另外的球队，那么可能不需要5次就能猜出来，所以完整的信息熵计算公式为： H = − ( p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p n log 2 p n ) 其 中 p n 为 概 率 H=-(p_1\log_2^{p_1}+p_2\log_2^{p_2}+...+p_n\log_2^{p_n}) 其中p_n 为概率 H=−(p1log2p1+p2log2p2+...+pnlog2pn)其中pn为概率
我们可以看出来，不确定性越大，熵就越大（这也是为什么叫做信息熵，而不是信息量）,这里举一个小例子，常用汉语是7000字左右，所以大概13b就可以存储一个汉字，而其中最常用的只有前10%，所以一个汉子大概8-9b就能存储完，再结合上下文语境，一本50w的中文书，我们只需要320K就能存储完，如果直接用国标码，那么这本书就是1M左右，是压缩文件的3倍左右，这两个数量的差距就是“冗余度“
信息的作用
作用就是消除不确定性，几乎所用的自然语言处理，信号，以及信号处理的应用都是在消除不确定性。
互信息
用来描述，两个随机事件之间的相关性的大小
I ( X ; Y ) = ∑ x ∈ x , y ∈ Y P ( x , y ) log P ( x , y ) p ( x ) P ( y ) = H ( X ) − H ( X ∣ Y ) I(X;Y)=\sum_{x\in{x},y\in{Y}}{P(x,y)\log\frac{P(x,y)}{p(x)P(y)}}=H(X)-H(X|Y) I(X;Y)=∑x∈x,y∈YP(x,y)logp(x)P(y)P(x,y)=H(X)−H(X∣Y)
我们可以通过互信息来确定一个可能产生歧义的词的含义
相对熵
K L ( f ( x ) ∣ ∣ g ( x ) ) = ∑ x ∈ X f ( x ) ∗ log f ( x ) g ( x ) KL(f(x)||g(x))=\sum_{x\in{X}}{f(x)*\log\frac{f(x)}{g(x)}} KL(f(x)∣∣g(x))=∑x∈Xf(x)∗logg(x)f(x)
相对熵的性质：
- 对于两个完全相同的函数，相对熵等于0
- 相对熵越大，两个函数的差异越大，反之，相对熵越小，两个函数的差异越小
- 对于概率分布函数或者概率密度函数，如果取值均大于零，相对熵可以度量两个随机分布的差异
相对熵不是对称的
K L ( f ( x ) ∣ ∣ g ( x ) ) ≠ K L ( g ( x ) ∣ ∣ f ( x ) ) KL(f(x)||g(x))\neq KL(g(x)||f(x)) KL(f(x)∣∣g(x))=KL(g(x)∣∣f(x))
这样有时候用起来不方便，所以有了
J S ( f ( x ) ∣ ∣ g ( x ) ) = 1 2 ( K L ( f ( x ) ∣ ∣ g ( x ) ) + K L ( g ( x ) ∣ ∣ f ( x ) ) ) JS(f(x)||g(x))=\frac{1}{2}(KL(f(x)||g(x))+ KL(g(x)||f(x))) JS(f(x)∣∣g(x))=21(KL(f(x)∣∣g(x))+KL(g(x)∣∣f(x)))
相对熵在自然语言上的应用很多：用来衡量两个常用词（在语法和语义上）在不同文本中的概率分布，看他们是否同义等
利用相对熵我们可以得到信息检索中最重要的一个概念：词频率-逆向文档频率（TF-IDF） 这和后面的网页搜索相关性和新闻分类有关
搜索引擎
PageRank
– google的*表决式网页排名技术
分布式集群形式的网络爬虫经过图的遍历可以得到大部分的网页信息，对于用户的查询，通常会返回大量的结果，我们如何才能吧用户最想看到的东西放在前面呢？对于一个特定的查询，搜索结果的排名取决于两组信息：关于网页的质量信息，以及查询与这个网页的相关性信息
PageRank算法是用来衡量一个网页的质量的，原理简单的令人无语，它被引用的越多，他的质量就越高，我们假设最开所有网页的排名都是 1 N ( N 是 网 页 个 数 ) \frac{1}{N}\ (N是网页个数) N1 (N是网页个数) 那么就有了一个向量 B 1 = ( 1 N 1 N ⋯ 1 N ) B_1=\begin{pmatrix} \frac{1}{N}&\frac{1}{N} & \cdots & \frac{1}{N} \end{pmatrix} B1=(N1N1⋯N1) 然后我们构建网页之间的可达矩阵
A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] A=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}\\ \end{bmatrix} A=⎣⎢⎢⎢⎡a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann⎦⎥⎥⎥⎤
其中 a n m a_{nm} anm表示从网页n到网页m有 a n m a_{nm} anm个链接
B i = A B i − 1 B_i=AB_{i-1} Bi=ABi−1
当 B i B_i Bi和 B i − 1 B_{i-1} Bi−1所差无几的时候，我们就认为 B i B_i Bi就是最终的网页排名
当然想想很美好，网页的个数是以百亿为单位的，还想做矩阵乘法？有点痴人说梦，所以真正的PageRank算法要比描述的复杂的多，大致上是利用了稀疏矩阵
网页和查询的相关性分析
现在的商业搜索引擎一般以用户的点击量作为相关性分析的权重最大的指标，但是在互联网用户没有那么多的时候查询和网页的相关性一般是通过算法来实现的
搜索关键词权重的科学度量 TF-IDF
短语“原子能的应用”可以分为三个关键词“原子能”，“的”，“应用”，某篇文章中一共有1000个词，这三个词一共出现了2，35，7次，那么将他们的词频相加，就是相应网页对于查询“原子能的应用”的单文本词频（TF），这么做当然是十分不合理的，因为我们注意到“的”这个词其实对于主题没有任何意义，实际上“的”这种词被称为“停止词”，还有一个漏洞就是，“原子能”比“应用”更能体现主题，按理说“原子能”这个词对于搜索的权重应该更大一些，那么这个权重应该怎么判断呢？其实很简单，就是所谓的“逆文本频率指数”， I D F = log ( D D w ) IDF=\log(\frac{D}{D_w}) IDF=log(DwD) D是文章（网页）总数， D w D_w Dw是出现单词w的文章数，至于为什么是取对数而不是取根号呢， 因为这个东西实际上是一种相对熵，大致上可以理解为，这个词和这篇文章的主题是否同意
所以“原子能的应用”在文章T中的相关性就是 I D F ( 原 子 ) T K ( T , 原 子 ) + I D F ( 的 ) T K ( T , 的 ) + I D F ( 应 用 ) T K ( T , 应 用 ) IDF(原子)TK(T,原子)+IDF(的)TK(T,的)+IDF(应用)TK(T,应用) IDF(原子)TK(T,原子)+IDF(的)TK(T,的)+IDF(应用)TK(T,应用)
文章相关性和文章质量的乘积就是用来衡量综合排名的数据了
余弦定理和新闻分类
正如书本上的第一句话所说“世界上的有些事情常常超乎人们的想象”，在这里的应用便是，新闻分类很大程度上利用的便是余弦定理。
计算机是读不懂文字的，但是计算机可以“算”新闻，只要我们能吧新闻变成一组数据，然后在设计一个算法来算出任意两个新闻之间的相似度，中文常用词有6w左右，我们通过上一节的方法（TF-IDF）计算出每一个词对于这篇文章的相关性，我们就得到了一个向量，对于另一个文章，我们得到了另一个向量，两个向量如果指向一个方向我们就说他们属于一类文章，那么如何判断两个向量之间的夹角呢？余弦定理
那么最后一个问题是，如何将新闻归类呢？
一个很直观的想法是，利用并查集将余弦值大于一定阈值的向量归为一个小类。然后我们再统计每个小类的特征向量，继续归并，当一个小类的大小足够大时我们就不再在这个小类中添加元素了。
所以我们可以看到，尽管思路很简单，但是对于 T ∗ N 2 ∗ l e n ( A ) T*N^2*len(A) T∗N2∗len(A)的复杂度我们还是不能接受的
矩阵运算和文本处理的两个分类问题
在自然语言处理中最常见的两个问题是：讲文本按主题分类和讲词汇按照意思归类，这两个问题都可以通过矩阵来一次行的解决
比如在新闻分类中，我们需要求出每一个新闻的向量，并两两比较，最后还要迭代很多次
解决方法是奇异值分解
首先我们构造一个矩阵
A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] A=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m1}}&{a_{m2}}&{\cdots}&{a_{mn}}\\ \end{bmatrix} A=⎣⎢⎢⎢⎡a11a21⋮am1a12a22⋮am2⋯⋯⋱⋯a1na2n⋮amn⎦⎥⎥⎥⎤
其中 a i j a_{ij} aij 表示字典中第j个词在第i篇文章中的加权词频（TF-IDF）这个矩阵会非常大 m=1000000，n=500000
奇异值分解就是将这么个大矩阵表示成三个矩阵相乘的形式，这三个矩阵的大小是 1000000 ∗ 100 ， 100 ∗ 100 ， 100 ∗ 500000 1000000*100，100*100，100*500000 1000000∗100，100∗100，100∗500000
$A=XBY $
他们三个的元素数量之和也不到大矩阵的 1 3000 \frac{1}{3000} 30001 并且每个矩阵都有自己确切的物理意义
第一个矩阵是对词意的分类结果
X
=
[
a
11
a
12
⋯
a
1
t
a
21
a
22
⋯
a
2
t
⋮
⋮
⋱
⋮
a
m
1
a
m
2
⋯
a
m
t
]
X=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1t}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2t}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m1}}&{a_{m2}}&{\cdots}&{a_{mt}}\\ \end{bmatrix}
X=⎣⎢⎢⎢⎡a11a21⋮am1a12a22⋮am2⋯⋯⋱⋯a1ta2t⋮amt⎦⎥⎥⎥⎤
其中
a
i
j
a_{ij}
aij 表示字典中第i个词对于语义j的相关度
最后一个矩阵Y是对文本的分类结果
Y
=
[
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
t
1
a
t
2
⋯
a
t
n
]
Y=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{t1}}&{a_{t2}}&{\cdots}&{a_{tn}}\\ \end{bmatrix}
Y=⎣⎢⎢⎢⎡a11a21⋮at1a12a22⋮at2⋯⋯⋱⋯a1na2n⋮atn⎦⎥⎥⎥⎤
其中 a i j a_{ij} aij 表示第j个文本在第i个主题下的相关度。
中间的矩阵则是词意和文本主题的相关度
B
=
[
a
11
a
12
⋯
a
1
t
a
21
a
22
⋯
a
2
t
⋮
⋮
⋱
⋮
a
t
1
a
t
2
⋯
a
t
t
]
B=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1t}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2t}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{t1}}&{a_{t2}}&{\cdots}&{a_{tt}}\\ \end{bmatrix}
B=⎣⎢⎢⎢⎡a11a21⋮at1a12a22⋮at2⋯⋯⋱⋯a1ta2t⋮att⎦⎥⎥⎥⎤
其中
a
i
j
a_{ij}
aij 表示第i个词对于主题j的相关度
因此只需要对原来的矩阵完成一次奇异值分解，我们就可以同时完成近义词分类和文章分类，还能得到每个主题和每个词之间的相关性，非常漂亮
小结
因为这本书面向大众，所以对于稍微懂得一些数学知识的人来说都可以读懂，这本书的重心放在解释一些看起来很麻烦但实际上出乎意料的简单的实现原理，这也是书中反复提到的也是书的名字“数学之美”