Tag Archives: IR

IR笔记(9): Ranking SVM

昨天随便在网上翻到一篇论文:T. Joachims, Optimizing Search Engines using Clickthrough Data, SIGKDD 02. 发现很有意思,在这里简单写一下。其实基本就是原文的翻译,而且还有很多理解不准确的地方,请大牛指正。

这篇文章感觉应该是所谓Learning to Rank的一个方法吧,大意就是通过分析日志,利用用户的点击信息对检索结果进行更好的排序。在这篇文章里把排序问题转换成了一个分类问题,然后用支持向量机(SVM)训练出一个模型来搞,感觉很好玩。

首先是通常分析系统日志,得到很多“某条结果比另一条结果更相关”这样的信息。需要注意的是这种信息通常是不能简单地通过数一下每个结果链接被点击了多少次来得出的,因为对于通常的Web Search而言,很少有用户能有耐心翻到好几页好几十页之后去看,比如在极端情况下,前几十页全是垃圾,第1000条结果才是最相关的,那么这个结果也几乎不可能有人点击的,反倒是前面的垃圾信息被点击得多些。作者在这里有一个简单的实验,对于不同的IR系统(有的很好,有的较差),统计所谓的Average Ranking,也就是用户所点击的那些结果的排名的平均值(比如用户点击了第1,5,7条结果,那么Average Ranking就是(1+5+7)/3),这样如果理想情况下,用户非常有耐心的话,应该是比较差的系统的Average Ranking会偏高,因为用户感兴趣的信息往往被排在了后面。实验结果与此相反,几个IR系统的结果都差不多,都在6左右。也就是说即使结果较差,用户仍然只关心前面的若干条。这个结果可以说明不能简单地通常计数来排序。

这篇文章里用了一个更有说服力的方法,举例如下,比如用户点击了第1,3,7条结果,我们可以认为用户是从前到后读下来的,也就是说用户认为第3条结果比第2条结果更相关,同样,第7条结果比第2,4,5,6条更相关。这样我们就得到了若干“针对某个Query q,文档d_i比文档d_j更相关”这样的信息。

对于q和d,我们可以定义一些Feature(比如q是否在d的标题中出现,q和d在向量空间中的cos相似度,d自身的PageRank等等)得到一个向量函数$$Phi (q,d_i)$$。类比用SVM解决二分类问题,我们的目标就是找到一个向量w,$$wPhi (q,d_i) > wPhi (q,d_j)$$就表示d_i比d_j更相关,我们应该train出一个w使得这些条件尽可能地满足。这个问题可以套用SVM解决,当然,再加上Kernel Trick的话也可以处理非线性特征的问题。对于SVM的细节我一直弄不太明白,这里就不胡扯淡了,总之是可以这样来搞的。弄一些训练集(即{Query、对应的返回结果、用户的点击情况}这样的Triple),训练出这个w来以后,对于新的Query,就可以用它来排序了。

IR笔记(8) – Probabilistic Model (上)

其实这个我还是有点似懂非懂,请多指教了。这一篇全是公式,呃……

概率模型与前面的向量空间模型有所不同,在向量空间模型里,把每篇文档看作一个向量,通过比较文档向量与Query向量的夹角来计算相似度,而概率模型中,我们考虑的是给定文档和查询,估计出这篇文档是相关文档的概率,即P(R=1 | d,q),(这里d,q分别表示文档和查询),然后把所有文档依此概率值排序。

这个方法看起来是比向量空间模型更靠谱的,但在实际计算中,即使做了相当强的简化,仍然有很多的困难,导致在相当长的一段时间内概率模型的效果比不上向量空间模型。下面具体说一下计算方法:

首先要简化原问题,不考虑TF,只考虑一个词在一篇文档中有没有出现,只有0,1两个取值,这样得到的模型叫BIM。为了后面的形式上简便,我们计算所谓的Odd:

$$O(R|x,q) = frac{P(R=1 | x,q)}{P(R=0 | x,q)}$$ (这里x表示把d二值化以后的向量)

由贝叶斯公式得

$$!O(R|x,q) = frac{P(R=1|q)}{P(R=0|q)}frac{P(x|R=1,q)}{P(x|R=0,q)}$$

容易发现等号右边的第一个分式是与ranking无关的,故可以无视。再假设各单词之间是独立的(类似Naive Bayes里的假设),则有

$$!O(R|x,q)=O(R|q) Pi_t frac{P(x_t|R=1,q)}{P(x_t|R=0,q)}$$

再分x_t取0,1的两种情况:

$$!O(R|x,q)=O(R|q) Pi_{t:x_t=0}frac{P(x_t=0|R=1,q)}{P(x_t=0|R=0,q)} Pi_{t:x_t=1}frac{P(x_t=1|R=1,q)}{P(x_t=1|R=0,q)}$$

然后我们再做一个假设:没有在query中出现的单词,它出现于相关文档和不相关文档的概率是相同的。这样我们就只需考虑在query中出现的单词即可。

我们定义$$p_t=P(x_t=1|R=1,q), r_t=P(x_t=1|R=0,q)$$,于是有

$$O(R|x,q)=O(R|q)Pi_{t:x_t=q_t=1}frac{p_t}{u_t} Pi_{t:x_t=0,q_t=1}frac{1-p_t}{1-u_t}$$

$$=O(R|q)Pi_{t:x_t=q_t=1}frac{p_t(1-u_t)}{u_t(1-p_t)} Pi_{t:q_t=1}frac{1-p_t}{1-u_t}$$

我们可以发现最右边那一项对所有x_t都要计算,所以又与ranking无关了,于是只剩下的中间那个,定义文档的Retrieval Status Value (RSV):

$$!RSV_d = sum_{t:x_t=q_t=1} logfrac{p_t(1-u_t)} {u_t(1-p_t)}$$

则理论上,我们计算出所有的文档的RSV,排序即可。

累死我了,下次继续。

IR笔记(7) – Evaluation

一个IR系统是好是坏,总要有个量化的打分的,下面说一下对IR系统的估价。

首先有一点是,我们说一条文档是相关还是不相关,针对的是用户的Information Need,而不是具体输入的Query。一般来讲Information Need是比较复杂而难以描述的,并不一定能用输入的Query精确表示出。比如我想知道我们学校都有什么样的美女,我在Google里输入“天大 美女”,结果得到的全是“一张美女图背后的惊天大秘密”,而如果我输入“天津大学 美女”,结果就好得多。再比如,用户输入Python,他可能是想关注那个脚本语言,也可能是想了解一下蟒蛇这种动物。当然,要求IR系统从Query中猜出用户的真实意图有点勉为其难,但这确实是我们始终绕不开的最终目标,所谓的Feedback Relevance, Query Expansion等等也都是为此而做的努力。

要做出Evaluation需要三类数据,一系列Information Need(用自然语言或是Query描述),大量的文档集,以及每篇文档与每个Need的相关度(通常是0,1二值,也有多值的,下面以二值为例)。评估的两个重要指标precision(以下称作P)和recall(以下称作R)在前面已经说过了,详细来说的话,对每个Query我们可以统计出四个值:

tp: 相关,且被检索出
fp: 不相关,但被检索出
fn: 相关,未被检出
tn: 不相关,未被检出

那么,P = tp/(tp+fp),R = tp/(tp+fn)。这里可能有一个疑问,就是看上去(tp+tn)/(tp+fp+fn+tn)似乎是一个更合适的选择,它可以表示出IR系统所做出的正确判断的比例。理论上确实是这样的,但实际上,针对每个Query的相关文档数相对整个文档集来说总是很小很小一部分(比如0.1%),如果我们的系统追求(tp+tn)/(tp+fp+fn+tn)最大化,它就会倾向于不检出任何文档,这样就可以得到一个相当高的得分。比如相关文档只占0.1%,那么这个啥活都不干的系统就得到了满分的99.9%,这显然是一个很囧的结果。

然而,用P和R两个值有时候确实不方便,有时候人们会采用一个F-Measure,它是P和R的加权调和平均数,也就是

$$F=frac{1}{alpha frac{1}{p} + (1- alpha) frac{1}{R} }$$

这里的$$alpha$$可以根据不同系统对P和R的不同侧重而调节。

最后说一下对返回结果有序的IR系统的评估,也就是说,我们关心的是系统返回的前k条结果的质量。首先注意一点,随着返回结果数目k的增大,R值一定单调不减,而对于比较正常的系统来说,P值整体来看应该是递减。这样的话,我们就可以在二维坐标上把针对不同k值的(P,R)都画出来并连线,就会得到一个类似下图的东西(图片来自Introduction to Information Retrieval):

Precision-Recall Graph

其中竖直往下的线表示随k增大,暂时没有检到新的相关文档,所以R不变,P降低;往斜上的线表示新的相关文档被检出。在实际中常常取11个典型Recall值(0.0, 0.1, 0.2…1.0)所对应的Precision作为指标。

最近又出现其他的评估方法,比如Mean Average Precision(MAP),这个是指,对于每个Query Q,设与它相关的文档为{d1,d2,…dk},我们用Rk表示随着返回文档数增加最终把dk包含起来时的集合,每个这样的集合对应一个P值,最后求对所有Query所有集合Rk的平均值:

$$MAP(Q) = frac{1}{|Q|} sum_{j=1}^{|Q|} frac{1}{m_j} sum_{k=1}^{m_j} Precision(R_{jk})$$

这里Q表示Query集合,$$m_j$$表示与Query j相关的文档数。

IR笔记(6) – Relevance feedback

本打算仔细看一下第七章,讲的是一个完整的检索系统的实现。但发现多是技术细节,看过一遍后没记住什么。而关于搜索引擎的具体实现似乎有更专门的书作介绍,所以先跳过了,等以后有机会再仔细看。

这次说下另一个比较有意思的东西,Relevance feedback(翻译成“相关性反馈”?)。它是指在第一次返回检索结果之后,用户可以标记出哪些结果是自己认为相关(Relevance,或者翻译成“中肯”?)的,哪些是不相关的,然后系统根据用户的反馈再进行检索,以得到更好的结果。这个过程还可以持续进行下去。这种想法的动机是,在一开始的时候用户自己也往往不清楚自己想要的东西应该怎样用Query表示,但是给已有的结果标记是否相关就相对容易得多。

继续用向量空间模型考虑问题,把Query也看成一个向量,现在用户已经对一些文档进行了“相关”或“不相关”的标记,我们的目标是找到一个新的Query,使得它离相关文档较近而离不相关文档较远。假设所有的文档都做了标记,如果我们用前面所说的Cos相似度的话,这个新Query应该是全部相关文档的质心(centroid,即各个维度的平均数)与全部非相关文档质心之差。但现在用户的标记只是一部分,我们不能跳得太厉害,这样就得到下式:

$$vec q=alpha vec q_0 + beta frac{1}{|D_r|} sum_{vec d_j in D_r} vec d_j – gamma frac{1}{|D_{nr}|} sum_{vec d_j in D_{nr}} vec d_j$$

这里q0是初始的Query,Dr是指相关文档的集合,Dnr是非相关文档的集合。也就是说把q0向着相关文档质心移动一点,背离非相关文档质心移动一点。这里alpha,beta,gamma都是可调的参数。这个貌似叫Rocchio算法。

在实际的搜索引擎中这项技术应用得并不多(Google和百度好像都没有吧?),主要原因大概是这项技术主要是改进Recall,而Web上的搜索大家都不太care这个,Precision相对更重要,而且很少有人有耐心给检索结果一个个作标记。所以恐怕只有在某些专门的场合,比如我们在图书馆费尽心机想找到一本老书的时候,这项技术才比较有用处。基于同样的原因,那三个参数里通常beta设得较高,gamma设得较低,甚至为零,即正反馈的结果更受重视,这也是为了改进Recall。

鉴于用户往往懒得去作标记,这里有两种改进方法:一个叫Pseudo(Blind) Relevance Feedback,指针对用户的Query先进行一次检索,把得到的排名最高K条结果自动标记为相关,然后执行Relevance Feedback算法(个人感觉这个很不靠谱呢-_-);另一个叫Indirect Relevance Feedback,指不显式地要求用户作标记,而从用户接下来行为中去判断,比如用户点击了某条结果链接,那么通常就可以认为这条结果是相关的,对于流量很大的搜索引擎,这样获得的信息已经相当可观。

另外一点是这种方法不止能应用于向量空间模型,还可以用在概率模型中,后面马上要提到。

IR笔记(5) – Vector Space Model

利用上次提到的TF-IDF或其它加权方式,我们可以对每篇文档里的每个单词赋一个权值,这样,一篇文档就可以看作一个向量(vector)——实际上也就是如果把反向索引那个表再看成矩阵,那么每个列向量就对应一篇文档——这样就得到了所谓的向量空间模型。这个模型不只在文本检索中,在分类、聚类等很多问题中都起核心作用。

来看这样一个问题:如何衡量两篇文档的相关程度?这个问题如果解决了,文本检索就可以自然解决,因为一个Query也可以看作一篇(通常是很短的)文档。一个自然的想法是用两个向量之差的长度(即两个向量端点的[欧氏?]距离),但这个选择并不太好,比如有文档A和B,其中B只不过是把A简单地重复了两遍得到的,按理说这两篇文档应该非常相似,但它们的长度差了一倍,所以结果并不好。一个更好的选择是所谓Cosine Similarity,也就是两个向量夹角的余弦值。设两向量分别为$$vec V_1$$和$$vec V_2$$,根据基本的线性代数知识得到:

$$sim(vec V_1,vec V_2) = cos(alpha) = frac{vec V_1 cdot vec V_2}{|vec V_1||vec V_2|}$$

其中分子部分是向量点积,分母部分是两个向量的欧氏长度之积。

进一步地,每次都计算|V|是没有必要的,我们可以直接把长度“归一化”:$$vec v_i = vec V_i / |vec V_i|$$,这样就得到:

$$sim(vec v_1,vec v_2) = vec v_1 cdot vec v_2$$

按照前面所说的,把Query也看作文档,对Query里的每个词t也计算TF-IDF,记为w(t,q),对文档d里的每个词t计算TF-IDF记为wf(t,d),则算法如下:

1. 置所有文档得分Score[d]=0

2. 对Query中的每个词t,扫描t所对应的posting——posting的每个节点处记录着(d,wf(t,d))这一对值,即文档编号和对应的TF-IDF权值——则Score[d] += wf(t, d) * w(t, q)

3. 对每个Score[d]归一化:Score[d] /= length[d],这里length[d]表示向量的长度

4. 选择Score[ ]中最大的K个,这就是最相关的K篇文档

当然这样的计算效率是不高的,难以实用,所以还需要后面提到的各种优化才行。

另外在实际情况中,除了这种相关度,我们还需要考虑其他的东西,比如文档自身也有重要性上的区别,所以我们还需要有一个衡量文档自身重要性的指标(比如大名鼎鼎的PageRank),然后可以把相关度和重要性做一个加权组合。