UIUC《文本检索与搜索引擎》课程学习笔记(五)—— 反馈机制与网络检索

UIUC《文本检索与搜索引擎》课程学习笔记(五)—— 反馈机制与网络检索

Contents

引导问题(Guiding Questions)

Develop your answers to the following guiding questions while completing the readings and working on assignments throughout the week.

  • What is relevance feedback? What is pseudo-relevance feedback? What is implicit feedback?
  • How does Rocchio work? Why do we need to ensure that the original query terms have sufficiently large weights in feedback?
  • What is the KL-divergence retrieval function? How is it related to the query likelihood retrieval function?
  • What is the basic idea of the two-component mixture model for feedback?
  • What are some of the general challenges in building a web search engine?
  • What is a crawler? How can we implement a simple crawler?
  • What is focused crawling? What is incremental crawling?
  • What kind of pages should have a higher priority for recrawling in incremental crawling?
  • What can we do if the inverted index doesn’t fit in any single machine?
  • What’s the basic idea of the Google File System (GFS)?
  • How does MapReduce work? What are the two key functions that a programmer needs to implement when programming with a MapReduce framework?
  • How can we use MapReduce to build an inverted index in parallel?
  • What is anchor text? Why is it useful for improving search accuracy?
  • What is a hub page? What is an authority page?
  • What kind of web pages tend to receive high scores from PageRank?
  • How can we interpret PageRank from the perspective of a random surfer “walking” on the Web?
  • How exactly do you compute PageRank scores?
  • How does the HITS algorithm work?

额外阅读材料(Additional Readings and Resources)

  • C. Zhai and S. Massung. Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining, ACM Book Series, Morgan & Claypool Publishers, 2016. Chapters 7 & 10

关键概念(Key Phrases and Concepts)

Keep your eyes open for the following key terms or phrases as you complete the readings and interact with the lectures. These topics will help you better understand the content in this module.

  • Relevance feedback
  • Pseudo-relevance feedback
  • Implicit feedback
  • Rocchio feedback
  • Kullback-Leiber divergence (KL-divergence) retrieval function
  • Mixture language model
  • Scalability and efficiency
  • Spams
  • Crawler, focused crawling, and incremental crawling
  • Google File System (GFS)
  • MapReduce
  • Link analysis and anchor text
  • PageRank and HITS

一、文本检索中的反馈(Feedback in Text Retrieval)

反馈的概念即是,使用原始的结果反过来帮助模型进行相关的处理,改进算法精度。

在文本检索中,我们会学习多种不同的反馈机制。

1.相关性反馈(Relevance Feedback)

在相关性反馈机制中,用户看到检索结果后,可以直接对其中的内容相关性做出判断,这些反馈信息对与检索系统来说十分有用——知道用户感兴趣的究竟是什么。因此,反馈模块把用户的判断作为输入来尝试改善算法。

一般认为,用户的判断结果是可靠的,但是如果想要得到这些判断反馈,需要用户做出一些额外的操作。

但是除非必须,否则用户通常不愿意付出额外的努力。这就是相关性反馈的缺点。

2.伪相关/盲目/自动反馈(Pseudo/Blind/Automatic Feedback)

针对上面相关性反馈的缺点,人们提出了一种近似的算法,即伪相关反馈机制。在这种机制下,不需要用户做额外操作以进行反馈,而是直接认为结果中排名前面(比如前十个)的那些文档是相关的。不过缺点就是,用这种伪反馈机制,反馈回去的结果是不可靠的。

3.盲从反馈(Implicit Feedback)

使用伪相关的方法毕竟还是不大可靠,因此人们又采用了另一种近似的方法——盲从反馈。盲从反馈不同于上面的盲目反馈,它的思想是,认为用户点击了的文档就是相关文档。

这种反馈机制下,反馈结果并不完全可靠,但是不需要用户做额外的努力,一切都由采集到的用户行为来进行了近似。

二、向量空间模型中的反馈-Ricchio(Feedback in Vector Space Model – Rocchio)

1.算法理论(Rocchio Feedback)

  • 一个TR系统应该如何从样本中学习以提高查询精度呢?
    – 正样本:已知相关的一些文档
    – 负样本:已知无关的一些文档
  • 普遍的方法:查询修改
    – 添加新的(加权后的)项(查询表达式)
    – 调整旧的项所占权重

向量空间模型中较为有效的反馈方法是几十年前提出的Rocchio反馈。

图中,我们将文档集表征成一个圈,然后其质心附近是排名靠前的那部分文档。

它的核心思想比较简单,第一次运行算法得出了一些较为相关的文档集(图中的质心q附近的文档),之后我们用这个结果来修正查询,得出新一轮的结果,……,最后使得查询结果的质心不断修正,求出其中最相关的(图中+号,位于新质心qm附近)以及分割出无关的(图中-号)。

其表达公式如下:

一个例子如下:

2.算法的实际应用(Rocchio in Practice)

  • 负样本(无关文档)并不是十分重要(为什么?)
  • 经常会把向量截短(即,仅仅考虑那小部分具有高权重的单词)(基于效率考虑)
  • 避免“过拟合”(保持原始查询语句的高权重)(为什么?)
  • 可以被用在相关性反馈和伪相关反馈机制上(相较于伪反馈,β在相关性反馈中需要被设置成一个更大的值)
  • 通常是健壮且高效的

三、语言模型中的反馈(Feedback in Language Models)

1.语言模型LM中的反馈机制

  • 查询可能性方法并不能天然地支持相关性反馈(我们假设查询是通过组合单词生成的,这样的话对搜索结果进行单词抽样不可行)
  • 解决方案:
    – Kullback – Leibler (KL) 差异检索模型是一种普遍的查询可能性模型
    – 反馈可以通过查询模型评估/更新来达成

2.Kullback-Leibler(KL)差异检索模型(KL Divergence Retrieval Model)

我们直接看一下公式:

对于查询可能性算法,其公式为

\[ f(q,d)=\sum_{w_i\in d,w_i\in q}c(w,q)[log\frac{p_{Seen}(w_i|d)}{\alpha_dp(w_i|C)}]+nlog\alpha_d \space\space\space\space\space\space(3.1) \]

对于KL-divergence,其公式为:

\[ f(q,d)=\sum_{w\in d,p(w|\theta_Q)>0}p(w,\hat\theta_Q)[log\frac{p_{Seen}(w_i|d)}{\alpha_dp(w_i|C)}]+nlog\alpha_d \space\space\space\space\space\space(3.2) \]

两个公式看起来非常相似,除了一个查询语言模型给出的单词概率项

\[ p(w|\hat\theta_Q)=\frac{c(w,Q)}{|Q|} \]

其流程如下:

2.生成混合模型(Generative Mixture Model)

3.总结

  • 反馈=从例子中学习
  • 三种主要的反馈方法
    – 相关性,伪,盲从
  • 对于VSM的Rocchio算法
  • 对于LM的查询模型评估
    – 混合模型
    – 其他模型

四、网络检索(Web Search)

1.网络检索的挑战与机遇(Web Search:Challenges & Opportunities)

  • 挑战
    – 扩展性(并行索引与搜索(MapReduce))
    – 如何处理网络的尺寸问题,并确保覆盖范围合理?
    – 如何快速处理多个用户的查询?
    – 低质量信息与垃圾信息(垃圾信息识别与健壮的排名系统)
    – 网络的动态性
    – 不停地有新页面产生;一些网页可能会经常更新
  • 机遇
    – 许多额外的启发式(例如链接)能够被用于提升搜索精确性(链接分析与多特征量排名)

2.基本的搜索引擎技术(Basic Search Engine Technologies)

3.网络爬虫(Crawler/Spider/Robot)

  • 想要写一个“玩具爬虫”很容易
    – 从一系列“种子网页”出发
    – 抓取(Fetch)网页
    – 解析抓取的网页中的超链接;把它们加入到种子网页队列中
    – 接着不停地访问队列中的网页
  • 一个实际应用的爬虫要复杂得多
    – 健壮性(服务端出错,陷入陷阱等)
    – 爬虫礼仪(服务端负载能力、爬虫禁止协议等)
    – 处理不同的文件类型(PDF,图像等)
    – URL扩展(cgi脚本,内部引用等)
    – 识别冗余页面(雷同、重复等)
    – 发现隐藏的URL(例如,截取一个长URL中的前面一小段)

4.主要的爬虫策略(Major Crawling Strategies)

  • 通常使用广度优先策略(利于平衡服务器负载)
  • 需要并行爬虫
  • 聚焦爬虫(focused crawling)
    – 目标为某一些特定页面(例如,所有关于智能手机的页面)
    – 通常给定了一个查询
  • 如何发现新的页面(它们可能从未被任何旧网页所链接)
  • 增加的/重复的网络页面数量
    – 需要最小化计算代价
    – 能够从过去的经验中习得(某网页的更新频率是每天还是每月)
    – 爬取目标为:1)经常更新的页面 2)经常被访问的页面

5.总结(Summary)

  • 网页检索是文本检索最重要的应用之一
    – 新的挑战:扩展性、效率、信息质量
    – 新的机遇:丰富的链接信息、层次等
  • 爬虫是网页检索不可或缺的部分
    – 初始化爬虫:完整爬取还是聚焦爬取
    – 增长的爬取内容:性能资源优化

五、网络索引(Web Indexing)

1.网络索引概览(Overview of Web Indexing)

  • 标准的IR技术是基础,但是还不够
    – 扩展性
    – 效率
  • Google的贡献:
    – Google文件系统(GFS):分布式文件系统
    – MapReduce:并行计算的软件框架
    – Hadoop:一个开源的MapReduce实现

2.GFS的结构(Architecture)

3.MapReduce:一种并行编程的框架(MapReduce: A Framework for Parallel Programming)

  • 使编程人员进行简单并行任务开发的过程更便捷
  • 特征
    – 隐藏了很多底层细节(网络,存储)
    – 内置的容错机制
    – 自动的负载均衡

4.使用MapReduce实现反向索引(Inverted Indexing with MapReduce)

5.总结(Summary)

  • Web规模索引的需求
    – 将索引信息存放在多台机器上(GFS)
    – 并行地创建索引(MapReduce)
  • GFS和MapReduce都是广泛运用的基础设施

六、链接分析(Link Analysis)

1.网络检索的排名算法(Ranking Algorithm for Web Search)

  • 标准的IR模型可以使用,但是还不够
    – 需要不同的信息
    – 文档包含额外的信息
    – 信息质量层次不齐
  • 主要的扩展
    – 引入链接来提高打分准确性
    – 引入用户的点击量作为反馈
    – 一般而言,依赖机器学习来连接所有功能

2.页面排名:捕获页面的流行度(PageRank:Capturing Page “Popularity”)

  • 直观理解
    – 链接就像是论文中的引用
    – 一个经常被引用的页面通常被认为更有用
  • 页面排名本质上是“引用统计”,但是在此基础上进行了改进
    – 考虑了“间接引用”(被一些本身被大量引用的页面所引用)
    – 引用的平滑处理(每一个页面都具有一个非零的引用计数)
  • 页面排名可以理解为随机冲浪(以此捕获流行度)

3.页面排名算法(The PageRank Algorithm)

4.实际应用中的页面排名(PageRank in Practice)

  • 由于M通常是稀疏矩阵,所以计算可以很有效率
  • 标准化并不影响排名,这能推导出很多公式的变式
  • 零外链(zero-outlink)问题:p(di)的外链数为零
    – 一个可能的解决方案 = 页面缓冲系数(对于没有外链的页面,α=1.0)
  • 多种扩展(例如,特定主题的页面排名)
  • 多种应用(例如,社会网络分析)

5.HIT:捕获权威&枢纽页面(HITS: Capturing Authorities & Hubs)

  • 直观理解
    – 被广泛引用的页面是权威
    – 引用了很多其他页面的页面是枢纽
  • HITS(Hypertext-Induced Topic Search)的核心思想
    – 高质量的权威会被高质量的枢纽所引用
    – 高质量的枢纽会指向高质量的权威
    – 迭代地影响
  • 在图像/网络分析上有很多引用

6.总结(Summary)

  • 链接信息十分有用
    – 锚文本(Anchor text)
    – 页面排名
    – HITS
  • PageRank和HITS算法都在图像或网络领域有很多应用
Tags:


Leave a Reply

Your email address will not be published.

*
*
*

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert