UIUC《文本检索与搜索引擎》课程学习笔记(二)—— VSM

UIUC《文本检索与搜索引擎》课程学习笔记(二)—— VSM

Contents

引导问题(Guiding Questions)

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

  • What are some different ways to place a document as a vector in the vector space?
  • What is term frequency (TF)?
  • What is TF transformation?
  • What is document frequency (DF)?
  • What is inverse document frequency (IDF)?
  • What is TF-IDF weighting?
  • Why do we need to penalize long documents in text retrieval?
  • What is pivoted document length normalization?
  • What are the main ideas behind the retrieval function BM25?
  • What is the typical architecture of a text retrieval system?
  • What is an inverted index?
  • Why is it desirable to compress an inverted index?
  • How can we create an inverted index when the collection of documents does not fit into the memory?
  • How can we leverage an inverted index to score documents quickly?

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

The following readings are optional:

  • 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. Chapter 6 – Section 6.3, and Chapter 8.
  • Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images, Second Edition. Morgan Kaufmann, 1999.

关键概念(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.

  • Term frequency (TF)
  • Document frequency (DF) and inverse document frequency (IDF)
  • TF transformation
  • Pivoted length normalization
  • BM25
  • Inverted index and postings
  • Binary coding, unary coding, gamma-coding, and d-gap
  • Zipf’s law

一、向量空间模式的改进实例化(Vector Space Model – Improved Instantiation)

1.简单版VSM存在的问题

我们接着上一章的内容。在简化版的VSM下,有一些相似度相同的文档,但是我们可以看到其中有一些是应该“相关性更强”的,那么我们应该如何实现呢?

在这个例子中:

  1. 匹配了多次“presidential”的文档,应该得到更大的权重
  2. 匹配“presidential”比匹配“about”的重要性更高。

稍后我们就会讨论改进算法。

2.改进的向量表征:关键词频向量(Improved Vector Placement:Term Frequency Vector)

在之前的模式里,我们的向量表征只使用了位向量表征的方式,即出现某关键词则为1,不出现则为0.

在改进的模式下,我们的向量表征需要考虑关键词出现的次数,即关键词对应标志位不再记0,1,而是记其出现次数。这样的方法被称为关键词频向量

在这种表征模式下,文档与询问的相似度仍按照点积的方式计算,但是结果会很不同,让我们来看看它是否解决了之前的问题:

可以看到,我们之前希望让d4的权重更高的想法实现了。

但是这个算法无法解决另一个问题:不同关键词的重要性不同:

下面这个例子中,d2和d3的匹配区别在于,一个是“about”,一个是“presidential”,这里“presidential”的权重本该大一些才对。所以,我们应该想办法解决权重问题。

3.进一步改进的向量表征:转置文档频率(Further Improvement of Vector Placement:Adding Inverse Document Frequency, IDF)

接着上一小节的问题,由于需要区分不同关键词的重要性,这里引入了转置文档频率(IDF),让之前的关键词频向量乘上这个转置文档频率向量,作为新的结果。

那么这个转置词频向量是怎么得到的呢?它的思想概括成一句话:出现得越频繁的词,它的权重越低。

因为,出现得最多的词,是一个泛用的连接词,然后是一个常用的术语(更多与此相关的东西,参考Zipf定律: https://en.wikipedia.org/wiki/Zipf%27s_law

因此关键词W的IDF计算公式可以表示为:文档集的总数加一,除以包含关键词W的文档数,再取对数。

\[ IDF(W)=log[(M+1)/k] \]

之所以取对数而不是采用线性只是一个经验选取,这里还能使用一些别的方式比如双重对数。

它们的一个区别在于,对数形式对于低词频的倾向性更为明显。至于哪个模式更好,是需要经验判断的。

那么我们来看看,这个算法能不能解决之前提到的问题:

可以看到,这个方法能够将d2和d3的重要性区分开来。

3.使用了TF-IDF权重算法的VSM模式(How Effective is VSM with TF_IDF Weighting)

我们将关键词频、转置文档频率结合,就得到了TF-IDF算法,现在可以看看对于之前的文档,是否能够更好地区分它们的重要性呢?

可以看到,在这个算法下,我们能够更为有效的区分文档相关度了。但是,与预期不符合的是,本来d4的相关度应该是最大的,但是这里却是d5.

二、关键词频转换(TF Transformation)

1.TF-IDF的实现细节以及存在的问题(Ranking Function with TF-IDF Weighting )

我们来看看上一节提出的TF-IDF算法公式:

在这个函数下计算,确实考虑到了关键词频、关键词权重的问题,但是有一点可能存在问题的是:如果一个关键词反复出现,那么它会使得该文档的相关度不停地拔高,正如d5中不断出现campaign这样。

(可能有人会问,如果一个关键词反复出现了,那它的IDF是不是降低了,这样能否抵消TF很高带来的影响?答案是否定的,此处的IDF定义的是“包含关键词W的文档数”,只在文档层面统计;而TF表示的是“所有文档中某个关键词出现的总次数”,在文本层面统计了)

2.TF转换(TF Transformation)

现在我们需要处理上一节提出的问题,如何给关键词频对权重的影响设置一个上限?

这里用到的方式就是TF转换,将词频函数由y=x转换为其他有上界或者增长非常慢的函数,比如这里的取对数以及取双重对数:

把不同的TF转换函数命名,目前比较好的一个算法是BM25转换:

\[ y=\frac{(k+1)x}{x+k} \]

3.总结

  • 次线性TF转换(sublinear TF transformation)可以用来
    -对于高关键词频的情况实现“回报抵减”
    -避免出现一个关键词支配一切的情况
  • BM25转换
    -具有上界
    -稳定且有效
  • 使用BM25 TF的排名函数(k>0)

    \[ f(q,d)=\sum_{i=1}^Nx_iy_i=\sum_{w∈q∩d}c(w,q)\frac{(k+1)c(w,d)}{c(w,d)+k}log\frac{M+1}{df(w)} \]

三、文档长度标准化(Doc Length Normalization)

1.枢轴长度标准化(Pivoted Length Normalization)

我们来比较d4和d6两篇文档,两篇文档的长度不同。

较长的文档出现关键词的机会更大,所以如果只统计它们的关键词频TF是不公平的。

因此我们引入了文档长度标准化的概念:

  • 使用文档长度标准化来惩罚一篇较长的文档
    -长文档有更多的机会来匹配任何问题
    -需要避免过度惩罚
  • 一篇文档较长是因为
    -它使用了更多的单词->多一些惩罚
    -它拥有更多的内容->少一些惩罚
    (这意味着,我们并不总是希望惩罚长文档。一个通俗的例子是,直接将几篇文档拼接为一篇新文档)
  • 枢轴长度标准化:使用平均文档长度来作“枢轴”
    -如果文档长度=平均长度,则标准化=1

即有公式:

\[ normalizer=1-b+b\frac{d}{avdl} \]

2.目前最先进的VSM排名函数(State of the Art VSM Ranking Functions)

在之前考虑了多种情况后,我们可以引入目前最先进的VSM排名函数了:

  • 枢轴长度标准化VSM [Singhal et al 96]

    \[ f(q,d)=\sum_{w∈q⌒d}c(w,q)\frac{ln[1+ln[1+c(w,d)]]}{1-b+b\frac{|d|}{avdl}}log\frac{M+1}{df(w)} \]

  • BM25/Okapi [Robertson & Walker 94]

    \[ f(q,d)=\sum_{w∈q∩d}c(w,q)\frac{(k+1)c(w,q)}{c(w,q)+k(1-b+b\frac{|d|}{avdl})}log\frac{M+1}{df(w)} \]

    \[ b∈[0,1] \\ k_1,k_3∈[0,+∞) \]

3.更进一步优化VSM(Further Improvement of VSM)

  • 提升维度的实例化
    -词干词,停用词删除,短语,潜在语义指数(单词聚类)
    -包含短语的词包通常更有效
    -语言和语域标记对于确保“关键词标准化”很重要
  • 提升相似函数的实例化
    -两向量的余弦函数值
    -欧氏距离?
    -点积似乎仍然是最好的(在使用了合理的关键词权重时具有良好的泛用性)

4.更进一步优化BM25(Further Improvement of BM25)

  • BM25F [Robertson & Zaragoza 09]
    -使用BM25来处理文档(“F”=fields)
    -关键想法:连接所有fields的关键词频,然后使用BM25(而不是其他的)
  • BM25+ [Lv & Zhai 11]
    -通过向TF添加一个常数,优化原BM25惩罚长文档的部分。
    -在理论上和实践上的表现都优于BM25

5.对向量空间模式的总结(Summary of Vector Space Model)

  • 相关性(q,d)= 相似度(q,d)
  • 询问和文档都用向量来表示
  • 启发式的排名函数
  • 主要关键词的启发
    -TF权重和转换
    -IDF权重
    -文档长度标准化
  • BM25和枢轴标准化看起来最有效

四、文本检索系统的实施(Implementation of TR Systems)

1.典型的TR系统结构(Typical TR System Architecture)

2.标记化(Tokenization)

  • 词汇单位标准化:具有相同意思的单词应该被映射到同一个指数项上面
  • 流:将单词的各种形式映射到同一个词根形式,例如
    – computer->compute
    – computation->compute
    – computing->compute
  • 一些语言(例如中文)的存储形式会带来挑战

3.索引化(Indexing)

  • 索引化=将文档转化为支持快速搜索的数据结构(做出更多的预处理)
  • 转置索引是用于基本搜索算法领域最流行的索引化方法
  • 可能需要其他索引(例如 文档索引)来做反馈

下面是一个转置索引的例子:

该例子中,对每一个关键词,记录了包含它的文档数,以及它出现的总次数,还有一个关于该关键词在每一个文档中出现的次数的映射表。

4.转置索引应用于快速搜索(Inverted Index for Fast Search)

  • 单关键词询问?
  • 多关键词布尔询问?
    -需要匹配 “A” AND “B”
    -需要匹配 “A” OR “B”
  • 多关键词的核心关键词提问
    -与分离的布尔询问相似(”A” OR “B”)
    -整合了关键词权重
  • 比顺序搜索文档更有效(为什么?)

5.单词的经验分布(Empirical distribution of words)

  • 有很多与具体语言无关的自然语言处理方法
  • 有一些单词出现得非常频繁(例如”the”,”a”,”we”);但是大多数单词出现得很少。
  • 在一篇文献中出现得最多的单词,可能在另一篇中出现得很少

6.齐夫定律(Zipf’s Law)

齐夫定律表示的是,出现频率为第N的单词的频率可以通过如下方式计算:

\[ F(w)=\frac{C}{r(w)^\alpha} \\\alpha≈1,C≈0.1 \]

7.转置索引的数据结构(Data Structures for Inverted Index)

  • 词典:尺寸适中
    -需要快速的随机访问
    -最好是在内存中
    -哈希表,B树等等
  • 数量:巨大
    -希望能顺序访问
    -能够存储在硬盘上
    -可能会包含文档ID,关键词频,关键词条等等
    -需要压缩数据
Tags:


2 Comments

index不要翻译成指数,翻译成“索引”比较合适。

Reply

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