UIUC《文本检索与搜索引擎》课程学习笔记(四)—— 概率检索模型与统计语言模型

UIUC《文本检索与搜索引擎》课程学习笔记(四)—— 概率检索模型与统计语言模型

Contents

引导问题(Guiding Questions)

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

  • Given a table of relevance judgments in the form of three columns (query, document, and binary relevance judgments), how can we estimate p(R=1|q,d)?
  • How should we interpret the query likelihood conditional probability p(q|d)?
  • What is a statistical language model? What is a unigram language model? How many parameters are there in a unigram language model?
  • How do we compute the maximum likelihood estimate of the unigram language model (based on a text sample)?
  • What is a background language model? What is a collection language model? What is a document language model?
  • Why do we need to smooth a document language model in the query likelihood retrieval model? What would happen if we don’t do smoothing?
  • When we smooth a document language model using a collection language model as a reference language model, what is the probability assigned to an unseen word in a document?
  • How can we prove that the query likelihood retrieval function implements TF-IDF weighting if we use a collection language model smoothing?
  • How does linear interpolation (Jelinek-Mercer) smoothing work? What is the formula?
  • How does Dirichlet prior smoothing work? What is the formula?
  • What are the similarities and differences between Jelinek-Mercer smoothing and Dirichlet prior smoothing?

额外阅读材料(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. Chapter 6 – Section 6.4

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

  • p(R=1|q,d) ; query likelihood, p(q|d)
  • Statistical and unigram language models
  • Maximum likelihood estimate
  • Background, collection, and document language models
  • Smoothing of unigram language models
  • Relation between query likelihood and TF-IDF weighting
  • Linear interpolation (i.e., Jelinek-Mercer) smoothing
  • Dirichlet Prior smoothing

一、概率检索模型的基本概念(Probabilistic Retrieval Model – Basic Idea)

在之前的内容中,我们讨论了基于向量空间模型(VSM)的排名方法。在这一章中,我们会讨论一种新的方法。在基于向量空间的模型中,我们将排名结果看作一系列二进制随机变量构成的矢量,其中R=1表示文档与查询相关。而在概率检索模型中,我们定义了一个排名函数来表达某个文档与某个查询相关的概率。即

  • 概率模型(Probabilistic models): f(d,q) = p(R=1|d,q), R∈{0,1}
    – 传统的概率模型是BM25
    – 语言模型是查询似然(Query Likelihood)
    – 还有一种随机性差异模型PL2

(slide中黑框部分“如果一个用户喜欢文档q,那么他输入查询q的概率是多少”现在看起来似乎有一些绕弯子,get不到点的话先看后面的引导内容)

1.基本思想(Basic Idea)

下面我们来看一个例子帮助理解:

每当用户输入一个查询,并且点击返回结果中的某个文档时,我们将其R记为1,即相关。

要注意的是,可能用户这次在查询q1的时候点击了文档d1,下一个同样查询q1的用户却没点击d1,这个时候,d1到底和q1是否相关呢?

现在我们收集了大量的用户行为数据,想要构建一个函数f(q,d),然后通过大量数据训练它来判定文档d与查询q相关的概率是多少。

在基本思想中,我们简单地将其转化为

\[ f(q,d)=p(R=1|d,q)=\frac{count(q,d,R=1)}{count(q,d)} \space\space\space\space\space\space(1.1) \]

也就是已知样本中,“认为文档d与查询q相关”的用户行为占“所有查询q”的用户行为数的比例。

现在,有关已知查询和已知文档的问题解决了,但是更进一步:如果我想用这个函数来判别之前没见过的文档和之前没见过的查询,又该怎么办呢?

当我们进入这一步的时候,就是试图用近似(appropriate)的方法来解决问题了,于是我们引出了下面的问题。

2.查询似然检索模型(Query Likelihood Retrieval Model)

先解决一个方面,为了近似的处理那些没见过的文档,我们需要换一个角度来思考:

我们假定用户是因为喜欢文档d才输入查询q的。

那么对于没见过的文档d2的处理问题就转换为了:

看其与已知文档d1的信息特征是否相同,如果信息特征相同,那么就认定用户同样会喜欢这个文档。

这个时候,我们之前提出的概率检索模型函数f(q,d)中的d就变成了d(n1,n2, … )也就是一个用信息特征来表征的量。

课程中还将这个f(q,d)进一步变成了p(q|d)也就是一个条件概率问题。

二、统计语言模型(Statistical Language Model)

1.什么是统计语言模型LM(What is a Statistical Language Model?)

  • 一个关于单词序列的概率分布
    – p(“Today is Wednesday”)≈0.001
    – p(“Today Wednesday is”)≈0.0000000001 (因为其不符合语法)
    – p(“The eigenvalue is positive”)≈0.00001
  • 与上下文相关
  • 也可以理解为一种用于“生成文本”的概率机制,所以它通常也被称作生成模型。

2.为什么一个LM很有用(Why is a LM Useful?)

  • 它将自然语言中的一些不确定性给量化出来了
  • 使得我们能够回答如下一些问题:
    – Given that we see “John” and “feels”, how likely will we see “happy” as opposed to “habit” as the next word?  (speech recognition)
    – Given that we observe “baseball” three times and “game” once in a news article, how likely is it about “sports”? (text categorization, information retrieval)
    – Given that a user is interested in sports news, how likely would the user use “baseball” in a query? (information retrieval)

3.最简单的语言模型:Unigram语言模型 (The Simplest Language Model: Unigram LM)

  • 通过独立(independently)生成每一个单词的方法来生成文本
  • 因此,p(w1,w2,…,wn)=p(w1)p(w2)…p(wn)
  • 参数:{p(wi)} p(w1)+p(w2)+…+p(wN)=1(N是向量尺寸)
  • 文本=根据这个单词分布来绘制的样本
  • 这就意味着,该模型下并未考虑单词顺序问题

4.基于Unigram语言模型的文本生成(Text Generation with Unigram LM)

我们来看一个例子。

使用统计语言模型的时候,我们遵循概率最大的原则,提出最大概率的那种可能性。

在这个例子中,第一个文本最高概率的单词是”text”和”mining”,这就明确的指出了其主题为“文本挖掘”;同理第二个文本的主题是“健康”。

4.对Unigram语言模型的评估(Estimation of Unigram LM)

还是上面的例子,但是这次我们换一个角度来看问题。

假设现在我们有一篇100词的文章,我们统计出了其中不同单词出现的次数,现在的问题是,如何根据该文本生成一个分布。这里的做法是,简单地将计数归一化(用某个单词的出现次数除以单词总数)得到单词出现概率。这种做法在这里被叫做最大似然估计(maximum likelihood estimation)

5.用语言模型进行主题表达(LMs for Topic Representation)

现在我们已经能够使用语言模型来提取出一个文档的特征量了,那么接下来就可以试着用它了。这里我们试着用它进行主题表达:

首先可以看到,这里三种类型文档的高频词汇都是the,a,is等常见词,但是再往后看,就有一些区分了:文档B中的词汇依然是常用词,所以这里把它判定为一篇普通文档;文档C中的词汇与计算机有关,所以判定它为一篇计算机科学论文;文档D中的单词倾向性更强,同时包含文本和计算机词汇,因此把它判定为文本挖掘论文。

三、查询可能性检索模型(Query Likelihood Retrieval Function)

1.用样本文档生成查询(Query Generation by Sampling Words from Doc)

看一个例子,

P(q=”presidential campaign”|d=”… news of presidential campaign … presidential candidate …”),

“查询可能性”的思路是,假如一个用户正在阅读这篇文档,那么他有多大的可能性会进行这个查询呢?

2.查询可能性有意义吗(Does Query Likelihood Make Sense?)

现在假设我们提出一个查询可能性的简单计算方法:

\[ P(q)=\prod \frac{c(word_i,d)}{|d|} \space\space\space\space\space\space (3.1) \]

即,将查询q拆解为单词,进行查询q的可能性为每个单词在文档中出现的概率的积。我们可以看到,在下图的例子中,一切都如我们所预期的那样。

可是,如果是下面这个例子,在查询有有未出现在文档中的单词,此时的计算结果是零,这是否是我们想要的呢?

3.进阶模型:从文本模型中提取单词(Improved Model:Sampling Words from a Doc Model)

在上面的例子中,之所以会出现可能性为零的结果,是因为查询中出现了不在文档中的单词,所以这里提出的对应改进措施是,认为用户可以绘制一句不一定所有单词来自于文档的查询,而是实际上从文档模型中提取单词。

现在我们假设文档模型也是用Unigram语言生成的,即也是(单词,概率)的形式组成的一张表。我们假定这个模型没有为任何单词指定零概率,而是给一个别的概率,这样就能解决问题了。

(可是到底是怎么给出其他概率的呢?并没有说。)

4.基于查询可能性的排名函数(Ranking Function Based on Query Likelihood)

总之,现在提出了一个新的查询可能性计算模型,并且对于一篇文档,我们计算出了很多个查询的可能性,那么我们该如何使用它呢?

返回了一系列结果,我们自然需要对这些查询按照可能性进行排名。

考虑一个特殊情况:如果一个查询中有很多未在文档中出现的单词,而在文本模型中它们的概率又很小,此时的可能性乘积结果就是一个非常小的数了,那就退化成了0。针对这种情况,课堂中提出了使用log函数的方法,即不使用p而是使用log(p)以此处理乘积很小的情况。

四、统计语言模型(Statistics Language Model)

1.估计文档模型中单词的概率(How to Estimate p(w|d) ?)

上一节内容中,我们挖了一个坑:对于文档中不存在的单词,我们从文档模型中去找它的概率,来避免零概率这样的计算结果,但是那个词在文档模型中的概率又是怎么确定的呢?

我们来看看之前的方法:我们直接从文档中统计出每个单词的概率,然后画出一张“单词-概率”的关系图。我们把之前的方法称作最大似然估计(Max Likelihood Estimate),可以看到它的函数图像是一个阶梯型的。

现在我们要在横坐标上放置不存在于文档中的单词,该怎么找到它对应的概率?答案自然是“函数拟合”,可是现在这个阶梯型的函数似乎不大好进行拟合,那么该怎么办呢?我们的方法是将函数图形平滑化,以此生成一个易于计算的拟合函数模型,这样找出没见过的词对应的概率。这样就解决了(单词,概率)的映射问题,接下来要解决(单词,横坐标)的对应位置问题。

2.如何平滑化一个语言模型(How to smooth a LM ?)

  • 关键问题:一个没见过的词,我们该如何分配它的概率呢?
  • 我们假设一个没见过的词的概率与它在相关语言模型中的概率成比例。
  • 概率唯一性:相关语言模型=数据集语言模型

3.平滑化的排名函数(Rewriting the Ranking Function with Smoothing)

对于原始的排名函数而言,只考虑了存在于文档中的单词,而将其平滑化的方法我们已经讨论了,即按一定比例从相关语言模型中引入概率。这体现在函数上其实就是多了些来自于语言模型的求和项。要注意的是,在这里,文档中出现过的词最终也会引入平滑项。

4.总结(Summary)

  • 对于单词概率的平滑化在计算可能性的时候很有必要
  • 一般化的思想:单词概率平滑化
    – 一个未出现过的单词的概率与其在相关集合中的概率成比例
    – 由此导出了使用TF-IDF权重和文档长度标准化的普适排名公式
    – 评分主要仍是取决于查询中每个单词项所对应的权重
  • 尽管如此,我们到底应该怎么样进行平滑化?

五、平滑化的方法(Smoothing Method)

前面我们已经提出了一个基本的平滑化框架,那么到底应该如何进行平滑化呢?

1.线性插值法(Jelinek-Mercer Smoothing)

顾名思义,线性插值法使用一个固定的转换系数λ,系数越大,曲线越平滑。

\[ p(w|d)=(1-\lambda)\frac{c(w,d)}{|d|}+\lambda p(w|C),\lambda \in [0,1] \space\space\space\space\space(5.1) \]

2.狄里克雷进阶法/贝叶斯法(Dirichlet Prior(Bayesian) Smoothing)

这是一种动态的方法,其表达式中的μ是一个动态的参数。

\[ p(w|d)=\frac{c(w,d)+\mu p(w|C)}{|d|+\mu}=\frac{|d|}{|d|+\mu} \frac{c(2,d)}{|d|}+\frac{\mu}{|d|+\mu}p(w|C),\mu\in [0,\infty) \space\space\space\space\space(5.2) \]

3.总结(Summary)

  • 两种平滑化方法
    – Jelinek-Mercer: 固定影响参数的线性插值
    – Dirichlet Prior:增加了伪计数;自适应的插值法
  • 两种方法都能用于最先进的检索功能,其理论前提的假设明晰(启发式较少)
    – 也使用了TF-IDF权重和文档长度标准化
    – 只有一个平滑化参数

4.查询可能性概率模型总结(Summary of Query Likelihood Probabilistic Model)

  • 高效的查询函数使用了简洁的概率模型
    – 假设1:相关性(q,d)=p(R=1|q,d)≈p(q|d,R=1)≈p(q|d)
    – 假设2:各查询单词都是独立产生的
    – 假设3:使用p(w|C)进行平滑化
    – 假设4:JM或Direchlet进阶平滑化
  • 与VSM相比更少的启发式
  • 目前有更多的相关拓展
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