第六章
1.信息量等于不确定性的多少。
2.香农用“比特”这个概念来度量信息量。
3.变量的不确定性越大,熵也就越大。
4.信息是消除不确定性的唯一办法。
5.网页搜索本质上就是要从大量网页中,找到和用户输入的搜索词最相关的几个网页。网页搜索的本质上也是利用信息消除不确定性的过程。如果提供的信息不够多,那么会有很多相关的结果。这时正确的做法是挖掘新的隐含信息,比如网页本身的质量信息。如果这些信息还是不够消除不确定性,不妨再问问用户。这就是相关搜索的理论基础。合理利用信息,而非玩弄什么公式和机器学习算法,是做好搜索的关键。
6.条件熵。
7.H(X)>=H(X|Y),多了Y的信息之后,关于X的不确定性下降了。
8.信息的作用在于消除不确定性。
9.所谓的两个事件相关性的量化度量,就是在了解其中一个Y的前提下,对消除另一个X不确定性所提供的信息量。
10.词义的二义性:真正简单却非常实用的方法是使用互信息。首先从大量的文本中找出和总统布什一起出现的互信息量最大的一些词,再用同样的方法找到和灌木丛一起出现的互信息最大的词。有了这两组词,在翻译Bush时,看看上下文哪类相关的词多就可以了。
11.相对熵也用来衡量相关性,但和变量的互信息不同,它用来衡量两个取值为正数的函数的相似性。
12.对于两个完全相同的系数,它们的相对熵等于零。
相对熵越大,两个函数的差异越大。
对于概率分布或者概率密度函数,如果取值均大于零,相对熵可以度量两个随机分布的差异性。
13.信息熵是不对称的。为了让它对称,詹森和香农提出一种新的相对熵的计算方法,将上面的不等式取平均。
14.词频率-逆向文档频率:TF-IDF
15.语言模型是为了用上下文预测当前的文字。
16.信息熵正是对不确定性的衡量,因此信息熵能直接用于衡量统计语言模型的好坏。当然,因为有了上下文的条件,所以对高阶的语言模型,应该用条件熵。如果再考虑到从训练语料和真实应用的文本中得到的概率函数有偏差,就需要再引入相对熵的概念。贾里尼克从条件熵和相对熵出发,定义了一个称为语言模型复杂度的概念,直接衡量语言模型的好坏。复杂度是在给定上下文的条件下,句中的每个位置平均可以选择的单词数量,一个模型的复杂度越小,每个位置的词就越确定,模型越好。

第七章 贾里尼克和现代语言处理
1.今天数字通信中应用最广的两个算法:BCJR算法和维特比算法。

第八章 简单之美-布尔代数和搜索引擎
1.简历一个搜索引擎大致需要做这样几件事:自动下载尽可能多的网页;建立快速有效的索引;根据相关性对网页进行公平准确的排序。
2.所有的数学和逻辑运算,加、减、乘、除、乘方、开方等等,全部都能转换成二值的布尔运算。
3.对于一个用户输入的关键词,搜索引擎要判断每篇文献是否含有这个关键词,如果一篇文献含有它,我们则相应地给这篇文献一个逻辑值——真(true/1),否则,给一个逻辑值——假(false/0)。一篇文献对于上面每一个条件,都有一个true或者false的答案。根据上述真值表就能算出每篇文献是不是要找的。
4.在布尔代数的“世界”里,万物都是可以量子化的。
5.搜索引擎的技巧:建索引。
6.信息检索是基于数据库的。数据库的查询语句(SQL)支持各种复杂的逻辑组合,但是背后的基本原理是基于布尔运算的。
7.最简单的索引结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献,就有多少位数,每一位对应一篇文献,1代表相应的文献有这个关键字。
8.由于这些二进制数中的绝大部分位数都是0,只需要记录那些等于1的位数即可。于是,搜索引擎的索引就变成了一张大表:表的每一行对应一个关键词,而每一个关键词后面跟着一组数字,是包含该关键词的文献序号。
9.整个索引非常大,所以这些索引需要通过分布式的方式存储到不同的服务器上。普遍的做法是根据网页的序号将索引分成很多份,分别储存在不同的服务器中。每当接受一个查询时,这个查询就被分发到许许多多的服务器中,这些服务器同时并行处理用户请求。
10.随着互联网上内容的增加,数据增加对服务器带来压力。因此,需要根据网页的重要性、质量和访问的频率建立常用和非常用等不同级别的索引。常用的索引需要访问速度快,附加信息多,更新也要快。而非常用的要求就低多了。

第十章 图论和网络爬虫
1.遍历:自动下载互联网所有的网页。
2.互联网实际上就是一张大图——把每一个网页当做一个节点,把那些超链接当做连接网页的弧。
3.有了超链接,我们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫。
4.网络爬虫如何下载整个互联网:先下载这个网页,然后通过分析这个网页,可以找到页面里的所有超链接。接下来,下载并分析这家门户网站的邮件等网页,又能找到其他相连的网页。让计算机不停地做下去,就能下载整个的互联网。当然,也要记录哪个网页下载过了,以免重复。在网络爬虫中,人们使用一种“散列表”而不是一个记事本记录网页是否下载过的信息。
5.一个商业的网络爬虫需要有成千上万个服务器,并且通过高速网络连接起来。
6.定理:如果一个图能从一个顶点出发,每条边不重复地遍历一遍回到这个顶点,那么每一顶点的度必须为偶数。
证明:加入能够遍历图的每一条边各一次,那么对于每个顶点,需要从某条边进入顶点,同时从另一条边离开这个顶点。进入和离开顶点的次数是相同的,因此每个顶点有多少进入的边,就有多少条出去的边。也就是说,每个顶点相连的边的数量是成对出现的,即每个定点的度数是偶数。
7.网络爬虫在工程上实现要考虑的细节:

  • BFS还是DFS?
    原理基本上是BFS,但是一个网页里还是DFS。网络爬虫对网页遍历的次序不是简单的BFS或者DFS,而是有一个相对复杂的下载优先级排序的方法。管理这个优先级排序的子系统一般称为调度系统,由它来决定当一个网页下载完成后,接下来下载哪一个。当然在调度系统里需要存储那些已经发现但是尚未下载的网页的URL,它们一般存在一个优先队列里。而用这种方式遍历整个互联网,在工程上和BFS更相似。因此在爬虫中,BFS的成分多一些。
  • 页面分析和URL的提取
    互联网早期,URL都是以文本的形式防在网页中,前后都有明显的标识,很容易提取出来。但是现在很多网页是用一种脚本语言生成的。打开网页的源代码,URL不是直接可见的文本,而是运行这一段脚本后才能得到的结果。因此,网络爬虫的页面分析就变得复杂得多,它要模拟浏览器运行一个网页,才能得到里面隐含的URL。有些网页的脚本写得非常不规范,以致于解析起来非常困难,但是这些网页还是可以在浏览器中打开,说明浏览器可以解析。因此需要做浏览器内核的工程师来写网络爬虫中的解析程序。
  • 记录哪些网页已经下载过的小本本——URL表
    用一个散列表记录哪些网页已经被下载过。但是,如果同时有上千台服务器一起下载网页,维护一张统一的散列表就不是那么简单了。首先,这张散列表会大到一台服务器都存储不下,其次,由于每个下载服务器在开始下载前和完成下载后都要访问和维护这张表,以免不同的服务器做重复的工作。这个存储散列表的服务器的通信就成了整个爬虫系统的瓶颈。
    一般都采用这样的技术:首先明确每台下载服务器的分工,也就是说在调度时一看到某个URL就知道要交给哪台服务器去下载,以免很多服务器都要重复判断某个URL是否需要下载。然后,在明确分工的基础上,判断URL是否下载就可以批处理了。比如每次向散列表(一组独立的服务器)发送一大批询问,或者每次更新一大批散列表的内容,这样通信的次数就大大减少了。

第十章 PageRank-Google的民主表决式网页排名技术
1.对于一个特定的查询,搜索结果的排名取决于两组信息:关于网页的质量信息以及这个查询与每个网页的相关性信息。
2.在互联网上,如果一个网页被其他很多网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。实际上的算法更加复杂。因为排名高的网页的连接更可靠,于是要给这些链接以较大的权重。即网页排名高的网站贡献的链接权重大。
3.把问题变成一个二维数组相乘的问题。他们先假定所有的网页的排名都是相同的,并且根据这个初始值,算出各个网页的第一次迭代排名,然后再根据第一次迭代排名算出第二次的排名。不论初始值如何选取,这种算法都能保证网页排名的估计值能收敛到排名的真实值。
4.这么大的矩阵相乘,计算量是非常大的,佩奇和布林两人利用稀疏矩阵的计算技巧,大大简化了计算量。
5.并行计算工具:MapReduce.
6.网页排名算法的高明之处在于它把整个互联网当做一个整体看待。
7.由于网页之间链接的数量相比互联网的规模非常稀疏,因此计算网页的网页排名也需要对零概率或者小概率事件进行平滑处理。
8.网页排名的计算主要是矩阵相乘。这种计算很容易分解成许多小任务,在多台计算机上并行处理。

03-14 11:17