思维之海

——在云端,寻找我的星匙。

阅《数学之美》

数学之美》是吴军的作品。
主要包括自然语言处理,信息学和搜索算法等内容。

这是Vel的读书笔记,收获+思考。

自然语言

起源时期

一个信息的原始传播模型

等价地用幻想学语言表述为:

对于$“现实\rightarrow幻想 \rightarrow联想\rightarrow信息
”$部分。

在人类发展以后,逐渐出现了庞大的信息载体:象形文字

然而象形文字太过于唯象(就是说,任何事物都用一个初等联想来表征),导致人类需要的记忆量很大,因此必须通过编码(联想)加以简化。

在联想过程中,又产生了复杂联想,如多方联想(聚类,一词多义),从而产生特征群。

但当我们只研究$“联想\rightarrow信息\rightarrow逆联想”$部分时。可以得出另一个结论:

翻译的可行性,是因为不同的文字系统在记录信息上的能力是等价的

对比幻想学中对翻译的定义:

翻译:根据任意给定的想界,对特定幻想的可想特征联想称为该想界下对该幻想的翻译。

都可以发现,翻译的主要局限在于想界。也就是说,想界决定了文字的复杂度上限,而翻译并不依赖于特定的文字系统(联想群)。

接着书中介绍了罗塞塔石碑。(同名语言学习软件:Rosettastone

  • 信息的冗余提高信息的安全性。
  • 语言的数据(语料)对翻译至关重要。

随着资源的丰富化,人类语言开始出现数字

进一步,出现了进位制。(普遍10进制。玛雅文明使用了20进制)

  • 中国:个十百千万亿兆(大端
  • 罗马:$IVXM$(大端相减,小端相加)
  • 印度:0123456789(隐式进制单位)

自然语言从此与数字分道扬镳。

楔形文字是最早的拼音文字。

若把中文中的拼音当作字母,则它也是一种(二维)拼音文字。
可以认为历史发展中,中文字体从抽象的图逐渐规整化,从而表意$\rightarrow$表音。

从楔形文字中传播简化出的22个字母后来演变成欧亚非大陆语言体系的主体。


词是有限而封闭的集合,语言则是无限而开放的集合。

任何语言都有语法规则覆盖不到的地方。
从而引出了语言和语法之争。

转折时期

  • 计算机能否处理自然语言?Yes。
  • 处理方法是否与人一样?Yes。

早期:

1950-170。用电脑模拟人脑。成果几乎为0。

中期:

1970-21世纪。基于数学模型+统计方法。实质性突破。

核心结论:计算机并不需要拥有类似人类的智能才能完成翻译。(唯象派


早期的研究如下:

  • 应用层:语音识别,机器翻译,自动问答
  • 认知层:自然语言处理
  • 基础层:句法分析,语义分析

但是,由于基础分析的复杂性,研究迟迟没有进展。

可以参考:抽象语法树,以及何为语法树。自然语言的语法树所需要定义的文法规则过多。

实际上,就是因为幻想和幻想之间的联想被一个一个地处理,计算机并没有学会通用联想规则。

其次,由于文本的上下文相关,更加大难度。这类特征联想也没有被掌握。

  • 算法复杂度——上下文无关算法:$O(n^2)$;上下文相关算法:$O(n^6)$。

基于统计的自然语言处理方法,在数学模型上和通信是相通的(甚至相同的)。

统计模型

通用模型

初衷:语音识别,判定一个文字序列是否可被理解并有意义。

比如在上一章的例子中:

  • 美联储主席本·伯南克昨天告诉媒体7 000 亿美元的救助资金将借给上百家银行、保险公司和汽车公司。

这句话就很通顺【语法】,意思【词义】也很明白。

如果改变一些词的顺序,或者替换掉一些词,将这句话变成:

  • 本·伯南克美联储主席昨天7 000 亿美元的救助资金告诉媒体将借给银行、保险公司和汽车公司上百家。

意思就含混了,虽然多少还能猜到一点。【词义】

但是如果再换成:

  • 联主美储席本·伯诉体南将借天的救克告媒昨助资金70 元亿00 美给上百百百家银保行、汽车险公司公司和。

基本上读者就不知所云了。【模糊】

上面的例子体现了一个转变过程:语法——词义——模糊

贾里尼克提出:(拓展:BCJR算法

一个句子是否合理,就看看它出现的可能性大小如何。至于可能性就用概率来衡量。
第一个句子出现的概率大致是10-20,第二个句子出现的概率是10-25 次方,第三个句子出现的概率是10-70。因此,第一个最有可能,它的可能是第二个句子的10 万倍,是第三个句子的一百亿亿亿亿亿亿倍。

(注:为避免值太小,可以使用对数概率)

引入马尔可夫假设:(马尔可夫

  • 假设任意一个词出现的概率只同它前面的词有关。(前驱,联想链表)

条件概率公式为

利用马尔可夫假设:

于是得到

该公式对应着二元模型More)。

当所考虑的前驱不止一个时(一般为有限个),称为n元语法模型

对应的简化公式为:(以三元为例)

这样的模型之所以在自然语言中很成功,是因为大多数自然语言都具有局部性。(人类的联想大多是初等的)

由于现实中,联想总是相对稀少,统计模型的成功也就不难理解了。事实上,越是重复度高,统计模型就越有用武之地。(大数定律)

比如,翻译一个几乎很少被使用的生僻词汇,可能就需要非统计学的手段。(频率将不可靠)

对于跨越上下文的”长程依赖性(Long Distance Dependency)“,n元模型将很难解析。
(n元模型的复杂度为$O(|V|^n)$,$V$是词汇量)

尽管联想稀少,但对于人工处理来说仍然是天文数字级的。(联想视界论)

接下来只需要进行文本统计,确定各个概率就行了。


为了解决统计样本不足时的概率估计问题,诞生了很多平滑性的处理。

比如,古德-图灵估计MoreMore2):从已有事件中统一分配一部分的概率给未知事件。

公式表述了Good-Turing估计的核心。其中,$N_r$指语料库中频率为$r$的词数。

$r$较大时,

  • 统计中频率$\approx$概率。

$r$较小时,我们利用Good-Turing估计,将$r$较小的词的概率进行修正

  • 一般$N_r$和$r$的关系呈现凹性负相关Zipf定律
    因而$r$ 越小,$N_r$上升越快,故我们修正得到的$d_r$会比$r$小得多。(并且,有正定性:$d_0>0$)
    这样,我们实际上只把一些中等频率的词的概率分配给了生僻词。(卡茨退避法

为了更直观的理解,我们还可以用反证法。
假如我们把前面的公式写为

可以得到

对于$\cfrac{r}{r+1}$,在$r\rightarrow0$时,极限趋于1。

而对于$\cfrac{N_{r+1} }{N_r}$,由于$N_r$和$r$凹性负相关,因此在$r\rightarrow0$时,极限趋于$\infty$。(仅负相关则不能推出)

故原假设不成立。并且,$r\rightarrow0$时,$0<d_r≪r$。

接下来只需要进行语料收集,训练模型就行了。

分词

贪心法

查字典,单向遍历字符串,每次贪心地找到最长的(字典里有的)匹配。(梁南元守创)

但是,贪心法对二义分割失效。

例:发展中国家。

字典:发,展,中,国,家,发展,中国,国家。

从左往右:发展-中国-家。
从右往左:发展-中-国家。

动态规划+统计

由底至上地利用统计数据获得最大概率出现的分词方法。(拓展:背包问题背包九讲

例:发展中国家。

频率字典:发(0.05),展(0.01),中(0.02),国(0.04),家(0.03),发展(0.1),中国(0.2),国家(0.15),发展中(0.4)。

状态转移方程可描述为:

其中$dp[i,j]$指分词法在区间$[i,j]$的最大概率。(仅用加法粗糙地表示)

下为初始的频率字典表。

dp[i,j] j0 1 2 3 4
i0 0.05 0.1 0.4
1 0.01
2 0.02 0.2
3 0.04 0.15
4 0.03

经过状态转移方程(5)计算后得到:(仅利用了上三角。技巧:由底向上计算)

dp[i,j] j0 1 2 3 4
i0 0.05 0.1 0.4 0.44 0.55
1 0.01 0.03 0.21 0.24
2 0.02 0.2 0.23
3 0.04 0.15
4 0.03

细节上可能还要实现回溯功能,dp[i,j]不为空时跳过……and so on

更一般地,利用Viterbi算法More)。


介绍了颗粒度概念。

机器翻译中大颗粒度更好;网页搜索中小颗粒度更好。

Viterbi算法

维特比算法是针对篱笆网络(Lattice)的有向图最短路径提出的。(动态规划,传播式算法

凡是使用隐马尔可夫模型描述的问题都可以用它来解码。

维特比算法的核心在于:传播


由于维特比算法的传播特性,维特比算法可以等效为一个BFS

如下图:(相当于一条马尔可夫链的状态伸展【上下伸展】,每一列代表原来的一个时刻)

在两条竖线之间就是维特比算法的篱笆图。
维特比求的是最优值。其实就是求从左到右的最短路。
我们在左右端添加两个头尾节点(红色节点),连上一些0权的边(黄色边),即可以使用从节点$I$到$O$的BFS了。

设共有$N$列,每一列节点的最大数量记为$D$(篱笆高度),可以算出两列间边数的上限为$D^2$(篱笆间隙)。
维特比算法只须遍历所有的边,故算法复杂度为$O(ND^2)$。
(相比穷举的指数级复杂度:$O((D^2)^N)=O(D^N)$优化不少)

总之,形象地说,BFS最短路径问题掐头去尾就得到了Viterbi算法。

由于任何的语音、文字的输入都是以流(Stream)的形式进行,只要处理每个状态的速度快过讲话、打字就行。此时,解码过程将是实时的。


(我的思考)

纯粹幻想学中对幻想空间的纯化,就是一个逆向的BFS。

其次,为了结合BFS、DFS和统计学的优势,我构想了以下的算法。

有限传播算法/有限优先算法(Finite First Search,FFS):

  • BFS只能无偏地传播,搜索进度慢,形成比较均衡的搜索树
  • DFS只能定向传播(又称为传递,因为仿佛有一个虚拟的信物/令牌在节点之间传递),容易陷入过于细分的领域,运气成分高,并且容易形成强烈失衡的搜索树
  • FFS综合了BFS和DFS,充分利用已知信息(通常信息集中于前几层),引入概率模型,在每一次搜索时选择概率最大的多个进行搜索,实现适度均衡的搜索树。(与剪枝策略相反)
  • 类似思想:随机梯度下降(Stochastic gradient descent,SGD)。
    (在有限传播中可能找不到类似梯度这样局部的全面、精准的度量。有限传播算法考虑在有限资源的前提最大可能程度地获得答案)
  • 类似算法:A*算法。(More,启发式搜索算法)

维特比本人还参与将CDMA技术(码分多址)应用于3G移动通信(More,高通公司)。

  • 频分多址(FDMA):将不同的频率(频道)一一对应地分给用户。
  • 时分多址(TDMA):类似时间片轮转,将同一频道切分为细小的时间片给不同用户。当切分得足够小,可近似具有实时性。
  • 码分多址(CDMA):类似量子态叠加(或者Fourier解析),用户通过一个密匙从大量的信息中过滤出自己的信号。

注:可以认为,址就是用户,分多址就是分给多个用户(使用)。

隐马尔可夫

上文已经提到过通信模型:$【发送】信息1 \rightarrow编码\rightarrow信息2(信道)\rightarrow解码\rightarrow信息3【接收】$。

具体的,我们认为信息3和信息1是相似的。为了求取最佳信息3(解码),通过最大概然法。

假设信息1的序列:$S_1,S_2,…S_n$;信息2的序列:$O_1,O_2,…O_n$;信息3的序列:$s_1,s_2,…s_n$。

假定我们已经拥有信息1的所有可能序列(样本)。

利用相似原理和贝叶斯公式有

我们要求左式$P(s_1,s_2,…s_n)$的最大值,而$P(O_1,O_2,…O_n)$是固定的,不影响最值求解。因而我们可以简化为


最后,我们使用隐含马尔可夫模型来对上式进行估计。

马尔可夫链之前已经介绍过了。我们可以将其形成过程形象地称为“概率图灵机”。

图灵机按照一定的规则在纸带上的状态上行走;概率图灵机将每一步固定的路线选择解析成有概率的事件。

记录这些事件发生概率的总表称为“概率转移矩阵”。(实质就是带权、归一邻接矩阵

通过概率图灵机产生一个可观测的马尔可夫链:$S_1,S_2,…S_T$。

显然,我们可以通过统计频率的方法来估计概率转移矩阵。

但是,当观测条件受限时,则要引入隐马尔可夫。(可以想成唯象化的马尔可夫链)

隐马尔可夫马尔可夫链($S_1,S_2,…S_T$,隐序列)不可观测。我们将接收到一个新序列($O_1,O_2,…O_n$,表序列),其中满足$O_i=f(S_i)$。

注意,$O_i=f(S_i)$表示$O_i$是且仅是$S_i$的函数。(独立输出假设

如下图所示:

计算特定S序列产生O序列的概率:

式右边利用了马尔可夫假设【$P(St|S{t-1})$】和独立输出假设【$P(O_t|S_t)$】。

现在我们利用上式和前面的简化式的相似性完成对简化式的估计。

相似性体现如下:

至此,解码问题将能利用隐马尔可夫模型解决。


隐马尔可夫模型(HMM)有三个典型问题:

  • 预测)给定模型,计算特定O序列的概率【Forward-Backward算法
  • 溯源)给定模型+特定O序列,估计最佳似然S序列【Viterbi算法
  • 训练给定观测数据,训练隐马尔可夫模型参数Baum-Welch算法

对于训练,可以使用监督学习获得参数$P(St|S{t-1})和P(O_t|S_t)$,但标注数据的获取成本高。

于是有了无监督的Baum-Welch算法。

同样的O序列可能对应多个HMM模型(记为$M_{i}$)。

Baum-Welch算法将试图找到其中最可能的模型$M_{\theta}$(最佳模型)。

Baum-Welch算法(迭代):

  • 首先找到任意一个满足O序列的HMM模型$M_i$
  • 通过$M_1$可以利用O序列反向生成一个标注数据集
  • 利用标注数据集,根据隐马尔可夫(解码算法)生成新的模型$M_{i+1}$
  • 再次反向生成、生成……
  • ……
  • 直到收敛。找到质量足够好的模型$M_n$(期望最大化
    • 用$Mn近似表示最佳模型M{\theta}$。

注意,Baum-Welch算法证明了$P(O|M_{i+1})>P(O|M_i)$,即,每次迭代都更优。

由于一般得到的是局部最优(极值),Baum-Welch算法生成的模型可能稍逊于监督学习模型。

对于单峰的凸函数(如,信息熵),则将表现正常。

若为了确保得到全局最优,可以考虑结合遗传算法

信息学

信息论

香农创立的信息论的基础内容不再介绍。只记录几个概念。

  • 信息熵:$H(X)=-\sum_{x\in X}P(x)logP(x)$。

  • 条件熵:$H(X|Y)=-\sum_{x\in X,y\in Y}P(x,y)logP(x|y)$。

$H(X)\geq H(X|Y)$。(可以推广。意味着n元模型的精确度高于n-1元模型)

  • 互信息:$I(X;Y)=\sum_{x\in X,y\in Y}P(x,y)log \cfrac{P(x,y)}{P(x)P(y)}$。

$I(X;Y)=H(X)-H(X|Y)$。

  • 交叉熵(相对熵):$KL(f(x)\mid \mid g(x))=\sum_{x\in X}f(x)\cdot log\cfrac{f(x)}{g(x)}$。

交叉熵衡量差异度。差异越大,交叉熵越大。
交叉熵没有对称性。

为了获得对称性,提出了平均交叉熵:$JS(f(x)\mid\mid g(x))=\frac{1}{2}[KL(f(x)\mid \mid g(x))+KL(g(x)\mid \mid f(x))]$

应用:信号处理,同义词判断,语言模型复杂度TF-IDF似乎可以用来查重orz


内容学习参见:学堂在线-《应用信息论基础》

指导读物:通信的数学理论。(香农所著的信息论奠基性论文)

通俗读物:信息简史。(英文版)

教材参考书如下,[2]和[3]可作为延伸阅读材料:

[1] Thomas M. Cover与Joy A. Thomas著的无比经典的教材《Elements of Information Theory》(中文版书名为《信息论基础》,阮吉寿、张华等译);
[2] Abbas El Gamal和Young-Han Kim合著的《Network Information Theory》(中文版书名为《网络信息论》,张林译);
[3] Imre Csiszár和János Körner Csizar所著的学院派经典《Information Theory: Coding Theorems for Discrete Memoryless Systems》。

信息指纹

爬虫应用

爬取过的URL的直接存储,非常占用内存。

但通过一个散列函数,将长长的URL映射到一个128位(16字节)的随机数,将能有效地控制空间。

关键算法:伪随机数产生器算法(Pseudo-Random Number Generator,PRNG)。

现在常用的PRNG算法是梅森旋转算法(Mersenne Twister)。

这个随机数就称为URL的信息指纹。

集合判等

  • 暴力法:两两做比较,$O(N^2)$
  • 排序法:先排序,再从头至尾比较,$O(NlogN)$
  • 散列法:将第一个集合放到散列表中,然后拿第二个集合作对比,$O(N)$。但需要额外的$O(N)$空间。
  • 指纹法:对集合$S$,定义指纹$FP(S)=FP(e_1)+FP(e_2)+…+FP(e_n)$。比较即可。就地算法。

如果集合只是相似。

可以按某些规则(比如,尾号是24的电子邮件地址)随机从集合中抽取几个元素,如果两个集合的抽查指纹相同,那么它们是相似的。

也可以使用相似哈希

反盗版(视频)

视频动辄上M、G的体量,几乎不可能采用普通的比较策略。

视频匹配的两个核心技术:

  • 关键帧提取
    • 尽管视频每秒可能有几十帧,但每一帧的差异不大。一般来说,每数秒才能提取出一个关键帧。
  • 特征提取
    • 利用信息指纹来表示关键帧,退化为集合判等问题

指纹重复

信息指纹客观地存在着极小概率的重复可能性。

假设随机数范围是$0~N-1$,共$N$个。可以推出$k$个指纹不发生重复的概率:


(我的解法)

对上式,当N很大时,分子可以用斯特林公式估计:$n!\approx \sqrt{2\pi n}(\frac{n}{e})^n$。

即:$(N-1)(N-2)…(N-k+1)=\cfrac{(N-1)!}{(N-k)!}\approx \cfrac{ \sqrt{2\pi (N-1)}(\frac{N-1}{e})^{N-1} }{ \sqrt{2\pi (N-k)}(\cfrac{N-k}{e})^{N-k} }$。

若我们有$k\ll N$(这一般是成立的,比如128位的指纹,$N=2^{128}$和$k\approx 10^{6}\approx 2^{20}$【百万级】),则可以进一步化简:($c=e^{-(k-1)}$是一个关于$k$的小常数)

故我们得到原来的概率变为:

即,当给定$N\gg 0$和$k\ll N$时,不冲突的概率$P_k$是与$k$强相关的指数衰减函数。(当然,数值上可能并不准确)


在《数学之美》中采用的估计函数如下:

同时,若要$k$个指纹重复的数学期望超过1,则$P_k<0.5$,此时可以解得$k>\frac {-1+\sqrt{1+8Nlog2} }{2}\approx2^{64}\approx 1.8\times 10^{19}$。可能性几乎为0。

相似哈希

相似哈希是一种特殊的信息指纹。

假设一个网页有若干词$T:t_1,t_2,…t_k$,对应的权重(比如TF-IDF值)为$w_1,w_2,…_k$。计算出$T$向量的信息指纹$FP(T)$。(假设指纹为8位)

  • 扩展【将8位指纹处理为8个实数$r_i$】

    • ```c++
      for(int i=1;i<=k;++i)
      r[i] = 0;  //初始化为0
      
      for(int i=1;i<=k;++i) //这里在变量类型上是扩展的,但在信息上却是压缩的
      for(int j=1;j<=8;++j)
          if(t[i][j]) r[j] += w[i];  //t[i][j]是词t_i的第j位
          else r[j] -= w[i];
      
      1
      2
      3
      4
      5
      6
      7
      8
      9

      经过上面的处理,我们将获得一个实数向量$R=\{r_i\}$。

      - **收缩**【将8个实数$r_i$重新布尔化为8位指纹】

      - ```C++
      bool P[9];
      for(int i=1;i<=8;++i) //进一步压缩信息
      P[i]=(bool)(r[i]); //P向量是文章的信息指纹
  • 我们获得了可以进行相似性比较的信息指纹$P$(相似Hash)。
    若两个网站雷同,则相似哈希接近。

布隆过滤器

需求:判断一个元素是否在一个集合内。(联系之前的信息指纹部分——集合判等)

一般的散列表需要较多的容量才能存下集合中所有的元素。

布隆过滤器(Bloom Filter)仅需要散列表1/8到1/4的大小就能解决同样的问题。
它实际上是一个很长的二进制向量和一系列随机映射函数。

例:假定存储1亿个电子邮件地址,先建立一个16亿bit的向量并清零。

  • 对每一个邮件地址$X$,用8个随机数产生器$F_i$先生成8个信息指纹$f_i$
  • 然后将$f_i$用随机数产生器$G$将$f_i$映射到1~16亿的8个自然数$g_i$
  • 将$g_i$对应的bit位设置为1
  • 对1亿个电子邮件地址做相同处理

这样,一个针对这些电子邮件地址的布隆过滤器就建好了。

检测可疑电子邮件:

  • 用$F_i$转换该地址,生成信息指纹$s_i$
  • 将$s_i$用$G$映射到8个bit位,若对应为1,则命中

布隆过滤器能保证所有的命中,但可能会过度命中(一些不在集合中的元素也有极小的可能被命中)。

补救:维护一个小的白名单。

密码学

密码学的道:

  • 无论获取多少密文,也无法消除己方情报系统的不确定性。
    为了这个目的,不仅要密文之间相互无关,同时密文还是看似完全随机的序列

注:根据信息守恒,当密文的形式越混沌,其可以携带的信息量就越少,则为了保证信息不失真,必然会在密钥(解密方法)上集聚极高的信息量。这值得权衡。

搜索

索引

搜索之道:下载、索引和排序三大步骤。


介绍布尔代数

真值表示法:用一个2进制真值串表示关键字。(由于大量0,属于稀疏,可改用字典【关键字-真值位置】结构)

假设互联网上约$10^{10}$个有意义页面,词汇表大小约$3\times 10^5$,压缩比约$100:1$。则最终索引的大小约$3\times10^{13}$。

为了排名方便,还存有词频、词的位置等。
由于存储量巨大,故一般要采用分布式系统

网络爬虫

根据图论的两种典型遍历方法:BFSDFS

互联网通过超链接(有向边)的形式连成虚拟之海。

注:可以查看我的文章了解更具体的技术:Pyspider操作指南

网络爬虫的构建

  1. BFS或DFS
    1. 小容量爬虫,爬取首页即可,用BFS
    2. 考虑握手(和网站建立连接)成本,在特定的网站适当采用DFS
  2. 页面分析和URL(链接)提取
    1. 通常采用队列,直接提取HTML中的URL标签
    2. 若网站采用了不规范的脚本(如JaveScript),需要通过高级模拟手段,利用浏览器内核解析网页
  3. URL记录表
    1. 用一个散列表记录已经遍历过的网页(分摊复杂度$O(1)$)
    2. 分布式系统散列表的维护和访问是难题

PageRank

质量

对于特定查询,搜索结果的排名取决于两组信息:质量(Quality)信息和相关性(Relevance)信息。

早期搜索引擎的挫折:(按解决时间排序)

  • 收录网页少,只能对常见词索引
  • 查询的结果相关性差

信任法则:指向一个网页的其它网页数量(节点的入度)越高,排名越高。(民主表决)

为了更加合理地刻画高信任高权重的相关性,采用了权重。
即,一些被链接更多的网页,链接其它网页将具有更高的影响力。(可信度)

迭代原理:给定所有网页一个相同的初始排名,利用信任法则进行迭代计算,最终排名将收敛到真实值。

由于互联网的链接是稀疏的,因此可以采用稀疏矩阵计算方法简化算法复杂度。
由于PageeRank更新一次很慢,因此诞生了并行计算方法(MapReduce)。
如果进一步考虑用户的点击数据,则可以进一步优化排名。

PageRank是一种整体化思维

对于PageRank,就是典型的联想图,如果一个幻想所链接的其它幻想越多,说明它更常见、更重要。但PageRank仍然有其局限所在,幻想的唯象程度太高了。

而且,由于是民主表决,PageRank将具有群体惯性,即,有偏向性。

搜索的目的是了解更广阔的世界,如果一个搜索引擎是有偏的,想界的扩张自然也就受限了。此时,用户更容易陷入神经制剂的纷扰当中。

另一方面,由于人类获取信息的能力有限,搜索引擎可能要在无偏和高效之前作出权衡。(联想公平和效率)

PageRank的计算方法

简单示意如下:

其中,$A$为带权邻接矩阵(刻画网页链接),$B$为排名向量。

设初始排名为$B_0=[\frac{1}{N},\frac{1}{N},…,\frac{1}{N}]^T$,迭代方程如下:

一般迭代10次左右就基本收敛。

MapReduce

上述问题已经抽象为了一个矩阵相乘的问题。

若要充分利用分布式系统的优势,可以采用矩阵的分治法

另一种非严格意义上的分治是求结果矩阵的某一个元素。可以分出原两个矩阵中的对应行、列,然后再细分,将计算任务平均分配(此时分配是容易的),就能将计算时间缩短。这就是MapReduce的原理。(Map,分解任务;Reduce,整合结果)

相关性

为了解决之前提到的PageRank可能具有的唯象性,引入了相关性的度量和排序。

影响搜索引擎质量的因素:

  • 用户的点击数据
  • 完备的索引
  • 网页质量的度量(PageRank)
  • 用户偏好
  • 网页与查询的相关性

TF-IDF

TF:Term Frequency,词频。

一般采用相对词频:$\cfrac{关键词次数}{网页总字数}$。查询的所有关键词的词频相加,得到网页的相关性。
为了避免某些无意义的词的干扰(如“的”、“是”等),引入了停止词(这样的词不计入相关性统计)。
为了让一些更专业的词汇有更大的权重,引入了主题词(这样的词具有权重系数)。

由TF得到了相关性的计算公式:

为了进一步确认权重,引入了IDF。

IDF:Inverse Document Frequency,逆文本频率指数。

定义式:$IDF=log\cfrac{D}{D_w}$。(关键词$w$在$D_w$个网页中出现过,$D$是总网页数)

假如中文网页数是$D=10亿$,停止词“的”在所有网页中出现,则它的$IDF=log\frac{10亿}{10亿}=0$。
假如专用词“原子能”在200万个网页中出现,那么它的$IDF=log\frac{10亿}{100万}=8.96$。(以2为底)
假如通用词“应用”在5亿个网页中出现,那么它的$IDF=log\frac{10亿}{5亿}=1$。

于是,得到引入权重后的相关性:


从本质上讲,$IDF$是一个特定条件下关键词的概率分布的交叉熵。

权威性

提及(Mention):在文章段落中,讨论某个主题,提及了某个名称。

当提及越多,则认为某个名称越权威。

提及隐藏在自然句中,需要自然语言处理方法。
即使有了好的算法,提及的计算仍然巨大。

另一个难点是搜索结果的权威性的排序与搜索的主题相关。

假设有$M$个网页,$N$个关键词,则需要计算和存储$O(MN)$的结果。

非常依赖于云计算和大数据技术。


计算权威度的步骤:

  • 对网页标题、正文进行句法分析,获取Mention信息
  • 利用互信息,找到主题短语和信息源的相关性
  • 对主题短语进行聚类(可用矩阵奇异值分解)
  • 对网页进行聚类,权威性的度量只能建立在子域(Subdomain)或子目录(Subdirectory)等粗略的级上。

新闻分类

更广义地讲,文本分类的任务都是基于同一个原理。

假设词汇表有N个词。

我们统计新闻中出现的词,计算它们的TF-IDF值(没有出现过的为0),就可以形成一个关于该新闻的TF-IDF向量(N维)。

利用两个新闻的TF-IDF向量的夹角,可以来反映新闻之间的相似度。

这里利用余弦定理即可。

通过这个的方法,我们可以设定一个相似度阀值,将小于阀值的新闻归到一类。在分好的小类里,又可以继续求类与类之间的相似度,从而获得更大的分类……


大数据时余弦计算的额外处理:

  • 充分利用TF-IDF向量中的非零元素
  • 删除虚词/停止词(消除了噪声)
  • 考虑词的位置加权(比如,在标题、首尾进行额外加权)

奇异值分解

上文中的余弦算法只适合于处理中大规模的文本(百万级),对于超大规模文本(亿级),则需要相对快速、粗糙的算法。

之前的新闻分类本质上是一个聚类问题,但是需要每个向量两两做计算。我们希望有一个办法——一次性地计算出所有的相关性——矩阵奇异值分解(Singular Value Decomposition,SVD)。

我们需要一个超大的矩阵$A_{M\times N}$来描述成千上万的文章和上百万的词的关联性。

奇异值分解:($r≪M,r≪N$)

$X_{M\times r}$:每一行(M)代表一个词,每一列(r)表示一个语义相近的词类。(元素值代表相关度)

$Y_{r\times N}$:每一列(N)代表一篇文本, 每一行(r)对应一个主题。

$B_{r\times r}$:表示词类和文章类(主题)的相关性。

只要对$A_{M\times N}$做一次奇异值分解,就可以同时完成近义词分类和文章分类,还能得到相应的相关性。

地图定位

智能手机的定位、导航:

  • 利用卫星定位
  • 地址的识别
  • 根据起点和终点,规划最短或最快路线

有限状态机

有限状态机用于地址的识别。

简单来说,有限状态机能够在有向无环状态图中不可逆地转换,当转换失败时则地址无效。

为了让识别具有一定的容错性(输错了一点仍然能够查询),提出了基于概率的有限状态机。(与马尔可夫链基本等效)

其它应用:Google Now

动态规划

对于导航系统,一般会采用动态规划的办法。

从A点到B点的路线,一定会经过一个里程数不断增长的过程。也就是说,这是一个传播问题。因此,全局的最优,一定也是局部里程圈的最优。至此,形成了状态转移。

有限状态传感器

加权有限状态传感器:Weighted Finite State Transducer,WFST。有限状态机中的每个状态由输入和输出符号定义。

任何一个词的前后二元组,都可以对应到WFST的一个状态。

若在符号序列中某个时刻前后出现了形如$AB$的有序对。(相当于A是输入,B是输出)
则根据在有限状态机中对应的$…\stackrel{A}{\longrightarrow} STATE_i\stackrel{B}{\longrightarrow} …$结构,进入对应$STATE_i$状态。

可用于语音识别

SEO与作弊

SEO就是搜索引擎优化。

SEO一般要适当,遵循搜索引擎的规则。

一个无所不用其极的SEO优化就称为在搜索引擎中的作弊。


早期作弊手法:

  • 重复关键词
    • 利用TF的相对词频
  • 买卖链接
    • 识别链接的流通
    • 利用出链(Out Links)向量,通过余弦算法聚类,识别卖链接的网站

利用通信模型解决搜索反作弊:

  • 从信息源出发,加强通信(编码)自身的抗干扰能力
    • 利用相反的信号抵消噪音
    • 搜集一段时间的作弊信息后,还原其原有的排名
  • 从传输来看,过滤掉噪音,还原信息

利用图论:

  • 互相链接的节点称为Clique,发现Clique并直接应用到反作弊中

利用浏览内核解析:

  • 对于使用JavaScrpt跳转页面,其落地页(Landing Page)质量非常高,但进入之后会立即通过JS程序被跳转到商业网站

反作弊是自动、无偏的。根本是去噪声
一个网站的内容质量,决定其排名。
越流行的搜索引擎,SEO越风行。

搜索广告

搜索广告的三个阶段:

  • 竞价排名(Overture、百度)
  • 利用经验预估点击率(Click Through Rate,CTR),预测用户的点击概率
  • 逻辑回归模型

逻辑回归模型:将一个事件出现的概率逐渐适应到一条逻辑曲线(Logistic Curve)上。

一个简单的逻辑回归函数:$f(z)=\cfrac{e^Z}{e^Z+1}=\cfrac{1}{1+e^{-Z} }$。(指数模型)

逻辑回归的定义域在$(-\infty ,+\infty)$,值域在$(0,1)$。

对于$(-\infty ,+\infty)$,对于任何信号都可进行回归。
而对于$[0,1]$,可以看作概率函数,于是逻辑回归与概率分布联系起来。

对于预估点击率而言,假设$k$个影响变量$x_1,x_2,…,x_k$。

则可线性组合得到$z=\beta_0+\beta_1x_1+\beta_2x_2+…+\beta_kx_k$。

${\beta_i}$向量就是该模型的参数向量。可以通过神经网络训练得到。比如最大熵模型的$GIS$或者$IIS$算法。

数学模型

  • 一个正确的模型应当在形式上是简单的
  • 一个正确的模型最开始可能并不如复杂的错误模型准确
  • 大量的准确数据对研发很重要
  • 正确的模型可能受到噪声干扰,此时应坚定信心,积极找寻噪声源

最大熵模型

最大熵原理(The Maximum Entropy Principle):在已知信息的基础上,不做任何主观假设,使未知事件的预测信息熵最大。此时的概率分布称为最大熵模型。

这里的熵是信息熵。

保留全部的不确定性,将风险降到最小。

希萨证明:对任何一组不自相矛盾的信息,最大熵模型存在且唯一。(其形式是指数函数)

例如:根据$w_1,w_2$预测$w_3$。

$P(w_3|w_1,w_2,s)=\cfrac{1}{Z(w_1,w_2,s)}e^{\lambda_1(w_1,w_2,w_3)+\lambda_2(s,w_3)}$.
($Z$是归一化因子,保证$P$概率归一,与参数$\lambda_i$一起需要被训练出来)

但是,最大熵模型的计算量相当大

比如,若搜索的排序需要考虑20种特征。

待排序的网页是$d$。

则有最大熵模型:

其中,归一化因子为

(参数$\lambda_i$通过模型的训练得到)

最原始的最大熵模型训练方法是通用迭代算法(Generalized Lterative Scaling,$GIS$)。

  • 假定第零次迭代的初始模型为等概率的均匀分布(类似PageRank的设定)
  • 用第N次迭代的模型来估算每种信息特征在训练数据中的分布,比较并调节相应模型参数。
  • 重复,直至收敛。

GIS算法是一个典型的期望值最大化算法(Expectation Maximization,EM)。

GIS收敛缓慢,而且不稳定,因此很少有人真的使用。

后来出现了改进迭代算法$IIS$(Improved Iterative Scaling),训练时间缩短了1至2个量级。

吴军提出了更快的最大熵模型快速算法,训练时间再次缩短了1至2个量级。


文艺复兴公司(Renaissance Technologies):利用最大熵模型和其它一些先进的数学工具,成为了世界上最成功的对冲基金公司。

注意:更多相关知识可了解量化交易

条件随机场

句法分析(Sentence Parsing):

  • 一是指根据文法对一个句子进行分析,建立其语法树,即文法分析(Synatactic Parsing);
  • 二是指对一个句子中各成分的语义进行分析,得到对这个句子语义的一种描述(语义树),即语义分析(Semantic Parsing)。

这里主要讨论文法分析。


Eugene Charniack提出原则:选择文法规则,让被分析的句子的语法树概率达到最大。

拉纳帕提则进行了进一步的优化,真正将数学模型和文法分析结合起来。

  • 对任意一个句子进行分词
    • 美联储|主席|本·伯南克|昨天|告诉|媒体|7 000 亿|美元|的|救助|资金|将|借给|上百|家|银行|、|保险公司|和|汽车公司
  • 扫描(从左往右),整合出高一阶的词组
    • (美联储主席)|本·伯南克|昨天|告诉|媒体|(7 000 亿美元)|的|(救助资金)|(将借给)|(上百家)|(银行、保险公司和汽车公司)
  • 重复扫描,整合……
    • 【美联储主席本·伯南克】|昨天|告诉|媒体|【7 000 亿美元的救助资金】|(将借给)|【上百家银行、保险公司和汽车公司】
  • 直到仅剩一个括号为止

容易看出,每次扫描,句子成分数按一定比例缩减,因而这个方法的复杂度是$O(n)$线性的。


上述方法对于模糊的语言处理能力较弱,为了处理更加随意的文法分析,逐渐形成了浅层分析(Shallow Parsing),找到句子中主要的词组已经它们对应的关系即可。

条件随机场使得浅层分析的正确率大大提高。(栅栏图)

条件随机场是隐马尔可夫模型的多元推广版本,此时观测序列的Oi将与前后的状态都相关,即与$S{i-1},S_i,S{i+1}$相关。(S序列仍然是马尔可夫链,但独立输出假设被推广了)

条件随机场是无向图。仍然遵循马尔可夫假设。

整个条件随机场的量化模型就是O序列和S序列的联合概率分布$P(O,S)$:

由于变量过多,不可能有足够的数据来估计这个高维分布。因此,一般要降维处理,通过一些边缘分布(如$P(O_1)$,$P(S_2)$,$P(O_1,S_3)$等)来找出一个符合这些条件的概率分布(通常不止一个满足)。

根据最大熵原理,希望找到一个满足所有边缘分布的熵最大的模型(指数模型)。

每一个边缘分布对应指数模型中的一个特征$f_i$(Feature)。($f_i$的参数可以使用最大熵算法训练)

比如:边缘分布$f_i(O_1,O_2,…,O_n,S_1,S_2,…,S_m)=f_i(x_1)$。

将特征运用到模型之中,有

这时就可以进行浅层文法分析了。(例:Google的文法分析器Gparser

贝叶斯网络

马尔可夫链是状态序列,每个状态值取决于前面有限个状态。

在现实生活中,关系可能是复杂、错综的,形成一个有向图网络。

若在这个网络之中,每一个状态只跟与其直接相连的状态有关,则称为一个贝叶斯网络

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

使用贝叶斯网络必须确定网络的拓扑结构,和各种状态之间的转移概率。

得到拓扑结构称为结构训练,得到转移概率称为参数训练。

从理论上说,贝叶斯网络是一个NP完全问题(现有计算机不可计算)。

但对于某些应用,经过适当简化(如,贪心+蒙特卡洛,利用互信息简化网络等),训练也能被计算机完成。

如Google的Rephil,通过贝叶斯网络完成对词、概念(词类)、文章的联系,将上千万关键词合成了上百万概念的聚类。

人工神经网络

下图来自Here,展示了一个典型的四层人工神经网络(多层感知机)的运作方式:

多层感知机

可以认为神经网络是一种特殊的有向图(90度左旋后的篱笆图)。

  • 所有节点分层,每一层通过有向弧指向上一层节点,但同一层无弧连接,不跨层连接
  • 每条弧有一个权重
  • 完了

神经元函数:为线性模型增加一次非线性变换,从而增强神经网络的分类能力。

感知机

感知机:一个输出层,一个输入层。一个计算夹层。最简单的神经网络。

感知机

详细内容直接参考Here吧。

Minsky指出):感知机无法解决异或问题。(More

多层感知机

实际上神经网络的计算过程就是矩阵运算。相当于:

为了基于线性分类实现复杂的非线性分类,多层的神经网络采用复杂函数拟合,利用隐藏层完成非线性空间到线性的变换。

一般来说,层数越多,神经网络的效果越好。(如下图


神经网络入门

神经网络浅讲:从神经元到深度学习

期望最大化

期望最大化算法(Expectation Maximization Algorithm,EM算法)是上帝的算法。

前面已经介绍过两种文本分类算法:

  • 利用事先设定好的类别对新的文本进行分类
    • 需要事先设定好类别和文本中心(Centroids)
  • 自底向上地将文本两两比较进行聚类
    • 计算时间较长

基于EM算法,提出了一种新的迭代算法(无须事先设定,无须聚类)。

  • 随机挑选类别的中心,然后反复优化直到收敛
    • 要利用到文本TF-IDF向量和余弦算法

记同一类中各个点到中心的平均距离为$d$,不同类中心之间的距离为$D$。

我们希望每次迭代,$d$变小,$D$变大

假设第1类到第K类中分别有$n_1,n_2,…,n_k$个点。每一类到中心的平均距离为$d_1,d_2,…,d_k$。

则有总平均距离

同理

假定有一个点$x$,它在前一次迭代中属于第$i$类,下一次迭代后被被安排到第$j$类。

不难证明


Baum-Welch算法(隐马尔可夫链),GIS算法(最大熵模型)都是典型的EM算法。

EM算法的分布描述:

  • E过程(Expectation):根据已有模型,计算观测数据输入到模型的结果
    • Baum-Welch:计算每个状态转移的次数和输出的次数
    • GIS:计算每一个特征的数学期望值
  • M过程(Maximization):重新计算模型参数,以最大化期望
    • Baum-Welch:根据这些次数重新估计隐含马尔可夫模型的参数
    • GIS:根据数学期望值和实际观测值的比,调整最大熵模型参数

EM算法优化的目标函数必须是一个凸函数,才能确保得到全局最优解。


就到这里吧。