主题：[推荐]《An Introduction to Information Retrieval》参考译文之九——相关度反馈和查询扩展

9 相关度反馈和查询扩展（Relevance feedback and query expansion）
在很多情况下，相同的概念可以使用不同的词语来表达，这个就是同义词问题，它对信息检索系统的召回度有着重要的影响。如检索“aircraft”可以匹配“plane”等。一般而言。用户都是通过手工调整查询词语来完成这样的扩展检索。如果系统能够提供一种自动化或者部分用户介入的机制来完成这个操作，将会极大减轻用户使用的负担。
目前，解决这个问题主要采用两种重要方法，一是全局方法，一是局部方法。全局方法对查询的扩展是独立于查询词语本身特点和相关的返回结果，对查询词语的改变将会产生新的查询请求。具体包含以下方法：根据同义词库进行查询扩展、通过自动同义词生成方法来扩展查询、采用拼写矫正的方法进行查询扩展等。
局部方法则通过根据最初的查询文档结果来进一步调整查询。具体的方法包含：相关度反馈、伪相关度反馈（也被称为盲相关度反馈）、间接相关度反馈。
在上述各种方法中，相关度反馈方法是最为成功的方法。

9．1 相关度反馈和伪相关度反馈
相关度反馈的主要思想就是让用户对最初查询结果的命中文档中，对这些文档的相关度作出评价，以调整查询来得到更为合理的命中结果。主要包含以下过程：
1）用户提交短小简单的初始查询
2）系统返回最初的检索结果
3）用户标记这些文档相关还是不相关
4）系统根据用户的反馈生成更好的信息需求表达方式
5）系统返回修正过的查询检索结果
相关度反馈的过程可以对上述做法反复迭代进行。这里的主要思想在于假设人们在不清楚文档集合的情况下，很难直接构造有效的查询表达式，所以反复进行的查询修正就可以改善这一现象。这种不断进行的查询改进可以有效的追踪不断进化的用户信息需求，也就是说，用户看到更多的文档会加强对自己信息需求的理解。
图片搜索是一种应用相关度反馈的极好案例。采用这种方式，用户不仅可以更容易得到搜索结果，而且在这种情况下，由于用户难以准确的通过词语表达他们的信息需求，相反他们非常清楚哪些图片相关、哪些图片不相关，所以相关度反馈提供了一种非常简单有效的查询表达方式。
可以参考下面的演示网站：
http://nayana.ece.ucsb.edu/imsearch/imsearch.html

9．1．1 Rocchio算法
Rocchio算法是一种经典的相关度反馈算法，它根据文档向量空间模型来对相关度反馈信息进行建模。
相关度反馈的核心在于得到一个改进的查询向量，它最大化与相关文档的相似度，最小化与不相关文档的相似度。也就是为：

此主题相关图片如下：

根据余项相似度方法，优化的查询向量可以表达为：

此主题相关图片如下：

看得出来，优化后的查询相关文档集合质心向量和不相关文档集合质心向量的差异向量。然而，这种说法意义并非很大，原因在于无法得到相关文档的完整集合。

此主题相关图片如下：

Rocchio算法于70年代提出，并应用于Salton的SMART检索系统之中。在真实的检索环境下，我们只具有用户的查询表达式和关于相关文档和不相关文档的不完整信息。算法采用以下公式：

此主题相关图片如下：

其中，q0代表着初始查询向量，Dr和Dnr分别代表着已知的相关文档集合和不相关文档集合。同时还有三个参数用于调节不同部分的权重，它可以在是否信任已经作出相关度判断的文档集合和是否信任查询向量之间取得平衡。如果拥有大量的已经作出相关度判断的文档集合，后两个参数可以适当调大一些。从初始查询q0开始，新的查询向量不断趋近于相关文档集合的质心，远离不相关文档的质心。最后得到的查询向量可以按照文档向量空间模型的方法计算命中的最终文档。在实际计算中，也可以忽略不相关文档的作用，如将其对应的权重参数设置为0即可。算法的运行效果如下所示：

此主题相关图片如下：

相关度反馈技术对查询精准度和召回度都有明显的提高作用，在实际情况中，对于召回度的提高更为明显，主要原因在于两个，一是这种技术扩展了查询，另一个是也是用户的行为使然：用户为了得到更高的召回度，必须花费更多的时间去检查命中结果和进行迭代计算。试验发现，正相关反馈的效果要比负相关反馈的效果更有价值，所以大部分信息检索系统就将最后一个权重参数设置的很小。常见的权重参数组合为1、0.75和0.15。很多诸如图片检索系统甚至只允许正反馈。还有的替代方法只关注具有最高排序权重的不相关文档，也就是说，此时的|Dnr|为1，这种方式被称为IDE DEC－HI方法，试验表明它的效果最为有效，并且能够取得最为一致的性能。

9．1．2 概率相关度反馈
9．1．3 什么时候使用相关度反馈
要想成功的使用相关度反馈，就必须满足一些基本条件。
首先，最为重要的是用户必须具有足够的知识能够给出初始查询，并且这个查询和自己的真实信息需求非常接近。但是，也应当看到还有很多情况，仅仅依*相关度反馈是难以奏效的。如
误拼：如果用户键入的词语是误写的词语，在文档中都没有出现，相关度反馈方法并不奏效。
跨语言检索：根据词语区分度来计算，不同语言的文档难以聚类形成较为紧密的集合，而同一语言的文档往往更易于聚成一类。
用户使用的词语和文档集合中的词语不匹配：如果用户查询laptop，而文档都使用notebook，则相关度查询会失效。
其次，相关度反馈方法要求文档整体结构具有良好的特点。在理想情况下，在所有相关文档中的词语分布要和用户标注的相关文档中的情况一致，不相关文档集合中的词语分布情况要和相关文档集合中的词语分布情况不一样。如果所有相关文档都可以紧密的聚类成一个单一的集合中，效果将会很好。Rocchio相关度反馈算法隐式的认为所有的相关文档可以构成一个单一的整体，这是通过聚类的质心来表达的。如果相关文档具有多个聚类的话，该方法效果将会大打折扣。造成多个聚类的原因主要有以下几种：不同的文档子集使用不同的词汇形式，如Burma和Myanmar；查询的结果可能含有多个彼此无关的内容，如较长句子组成的查询；一些通用概念，涉及到很多彼此关系不甚密切的若干特指概念，如feline。
良好的文档编辑内容可以为解决此类问题提供有效的途径。如一篇对各种不同团体对缅甸情况的观察报道可以介绍大量由不同团体使用的术语，这样便可以形成文档聚类。
用户通常对相关度反馈技术并不在意，而且也不愿去显式表达反馈信息，甚至不愿延长搜索的交互机会。可以这么说，有时都能难理解为什么经过相关度反馈处理后会得到某些文档查询结果。
另外，相关度反馈也有实际的问题。由相关度反馈过程生成的较长查询，通常没有很好的效率，往往导致较高的计算成本和冗长的响应时间。一个特别的处理方法就是只对相关文档中的一些重要词语进行重新加权，如具有最高词频的前20个词语等。一些实验结果表明使用受限数量的词语可以取得更好的查询结果 ，而也有人指出使用更多的词语可以取得更好的检索质量 。

9．1．4 Web上的相关度反馈
很多搜索引擎都可以提供相似网页或者相关网页的服务：用户在检索结果中选择某个满足检索需求的文档，便可以据此文档得到更多类似的文档。这也可以看成是相关度反馈的一种简单形式。但是，从整体来看，相关度反馈技术的使用面很小。Excite搜索引擎最初可以提供完整的相关度反馈技术，但是由于使用较少，该项功能已经被削弱。在Web网络上，大部分用户都很少使用高级检索，而且都希望能在一次交互的情况下完成检索。这也充分说明一方面相关度反馈技术很难被一般用户理解，另一方面相关度反馈技术主要用于提高检索的召回度，而一般情况下，搜索引擎并不在意得到较高的召回度。
有人研究了用户使用Excite搜索引擎的情况。大约4%的用户使用了相关度反馈选项，而且这主要是通过命中结果旁边的“More like this”来完成，大约70%的用户只会查看结果网页的第一页，对于使用相关度反馈的用户而言，命中结果大概可以提高2/3 。
现在更为常见的使用方式就是使用点击流数据，所谓点击流数据就是用户点击了命中结果的哪些链接，这些点击间接提供了反馈信息 ， 。使用Web网页之间的链接结构也可以被看成是一种隐式的反馈获取技术，只不过反馈信息的提供者不是浏览网页的用户而是网页的作者（虽然在实际中，很多网页作者也是网页的浏览者）。

9．1．5 相关度反馈的评价
使用相关度反馈技术可以增强检索的质量。经验表明，一次相关度反馈就可以取得很好的效果，多次使用的效用增加幅度也会边际递减。另外，成功的使用相关度反馈技术需要足够多的判断文档，否则结果会表现出与真实用户信息需求较大的差异。一般而言，至少5篇判断文档才能够有效。
不过，在对相关度反馈进行评价时，要注意多方面因素的影响。如常见的方法就是测试在进行初始查询时的查准度—召回度曲线，然后继续计算修改过的查询所产生的查准度—召回度曲线，比较此曲线即可得到评价结果。不过，这样做似乎总是可以发现相关度反馈可以提高检索质量，平均可以达到50%的精确度。然而，这存在着欺骗。这些获得的提高很大程度上来自于用户已对一些文档做出判断，所以这些文档就可以取得较高的排名。所以，为了取得公平，我们必须只对那些没有被用户判断过的文档进行评价。这些没有被用户评价过的命中文档被称为剩余文档集合（residual collection），被用于在接下来的检索中进行评价。不过，这种方法也有问题，实际测量往往表明修正后的查询检索质量往往低于先前的查询检索质量。如果相关文档数量很少的话，这种情况更为明显，因此很多相关文档都已在上一轮检索后被用户评价过了。而且，使用不同相关度反馈技术所产生的各种检索质量可以进行对比，然而，是否采用相关度反馈技术所反映的检索性能并不能直接比较，因为集合大小不一样，而且相关文档的数量也有不同。
所以，第三种方法就是采用上述两个集合，一个用于初始查询和相关度判断，另一个用于比较评价。初始查询和修正查询都可以在第二个集合上进行比较检索质量。
可能最好的评价方法就是进行用户调研，可以采用基于时间序列的分析方法，如用户采用相关度反馈技术可以多快的得到相关文档和在指定时间段内用户可以得到多少相关文档等。这样做可能更为公平和接近于真实系统的使用情况。

9．1．6 伪相关度反馈
也被称为盲相关度反馈，它可以自动化的进行查询扩展。该方法首先进行正常的检索得到初始的命中检索集合，然后假设头k条文档就是相关文档，并据此进行相关度反馈。
这种方法效果不错。证据表明它比全局分析方法还要有效，对TREC的随机查询也会显著的效果提升。当然，这样做也存在着潜在的问题。如用户要检索“copper mines”，在得到的命中结果中，前面的很多文档都涉及到Chile，此时的相关度反馈就会导致查询偏向关于Chile的文档。

9．1．7 间接相关度反馈
这种方法也被称为隐式相关度反馈，虽然隐式方法可能不如显式方法更为可信，但是显然要比伪相关度反馈方法更为可信，毕竟伪相关度反馈方法没有使用任何用户的判断信息。另外，由于一般用户并不愿提供显式的反馈信息，所以利用隐式反馈信息就成为诸如搜索引擎等很多大型信息检索系统中较为简单易行的处理方法。
在Web网络上，DirectHit会将用户查看较多的文档放置在网页命中结果的较高位置，它认为对文档链接的点击可以被看成是对查询相关的认可。除此以外，还可以采用很多其他类型的假设，如在结果列表中显示的文档摘要也可以被看成能够反映文档的相关性，因为用户据此进行判断以决定是否查看该文档。在早期的DirectHit搜索引擎中，点击信息是在全局范围内收集的，没有根据不同的用户或者查询主题进行分别的收集。这也是一种常见的点击流挖掘技术。现在，这些技术已经广泛的被应用于对广告查询结果的排序上。

9．2 查询重构（query reformulation）的全局方法
9．2．1 查询重构所需的词语工具
在搜索过程中的很多用户支持方法有助于用户更加清楚的看见自己的查询是否真正得到完全的执行。这些支持信息包括以下内容，查询是否含有停用词，哪些词语被截取，命中的结果数量，词语是否被自动转换为词组进行检索等。信息检索系统往往还会通过同义词库或者受控词表来提示更多的搜索词语建议。用户甚至可以查看索引中的词语，以决定选择最为合适的词语。

9．2．2查询扩展
在查询反馈中，用户通过标记文档是否相关给出额外的反馈输入信息，这些信息被用来重新调整查询词语的权重。在查询扩展中，用户往往通过提供更多的词语来实现反馈信息的输入。很多搜索引擎都会使用这种方式来让用户选择可以替代的查询建议词语。问题的关键在于如何生成用户查询的替代内容，常见的形式就是利用全局分析方法。如使用同义词库等。对于查询中的每个词语，系统都会对其进行同义词扩展，给出相关的其他词语形式。同义词库的使用还可以结合词语加权方法，如对新增的词语可以赋予相对原有查询词语较低的权重。
构造同义词库的方法有以下几种：
1）使用一些人工编辑的受控词表。对于每个概念，都可以给出规范的词语形式。常见的有国会主题标目（Library of Congress Subject Headings）和杜威十进制编目系统（Dewey Decimal system）。对于那些具有良好组织形式的资源而言，使用这些受控词表很常见，如Medline使用统一医学语言系统（Unified Medical Language System，UMLS），用户键入canceer就会自动得到neoplasms相关检索词。有些系统的工作方式也和Yahoo的方式不一样，Yahoo采用主动提示的方式，而PubMed系统则自动进行查询扩展，除非用户仔细检查提交的查询词语，否则他们可能都不会意识到已经进行了查询扩展操作。
2）使用手工同义词表。这些词表往往由人工编辑，和受控词表不一样，它们往往并非十分规范。UMLS就是就是一个例子。Statistics Canada也维护着一个由英语和法语组成的双语词表，包含首选词语、同义词、宽泛词（broader term）和下位词（narrower term）。
3）自动生成的词表。利用词语共现统计方法对大量文档内容进行分析可以自动生成相关词表。
4）利用查询日志信息重构查询。通过日志观察其他用户手工重构查询的方式，来对新用户提供建议。这需要巨大的查询日志信息，常常应用于Web搜索中。
基于同义词库的查询扩展方法无需用户主动输入反馈信息，可以增加召回度，所以被广泛的应用于各种科学工程领域的信息检索系统中。除了可以利用全局信息进行查询扩展，也可以使用局部信息进行，如通过对返回文档结果的分析得到扩展的查询词语等。

9．2．3 自动化的词表生成方法
有两种方法可以自动生成词表：一种方法是利用词语的共现情况，位于同一篇文档或者同一个段落中的若干词语应当更可能具有相似的语义，所以只需利用文本的统计信息即可找到相似词语；第二种方法通过语义分析技术，探索文本词语间的语义关系和依赖性，如说到一个可以生长、烹饪、可食用和可消化的实体，你必会想到食物这个概念。比较两者，简单利用词语共现的方法更为鲁棒，不会因为解析器的错误而产生误差，但是使用语义关系分析的方法则更为精确。
计算同义词共现度的最简单方式就是根据词语之间的相似程度。可以先构造一个词语文档矩阵A，每个单元格Atd代表着词语t和文档d的权重，这个权重需要对长度进行规范化处理，也就是说要消除词频绝对数量产生的影响。然后，可以计算C=AAT，这样Cu,v就代表了词语u和词语v之间的相似程度，值越大，相关性越密切。
当然，这种方式生成的词表质量是个问题。词语的模棱两可易引入不相关词语。如查询“Apple computer”可能会得到“Apple red fruit computer”。通常情况下，这样的同义词表会具有较高的假阳性和假阴性。而且，由于自动词表中的词语和文档关系密切，而且这些文档也是构造索引的文档集合，所以这样的查询扩展不会产生更多的额外文档。
查询扩展可以有效提高召回度。但是，人工维护词表具有太高的成本，而且还要随着科技和术语本身的发展而不断更新词表。一般而言，维护一个面向特定领域的专题词表是必要的，通用性词表难以对某些特定领域的专门词语给出丰富的说明。
在另一方面，查询扩展却会降低精确度，特别是在查询包含很多专指不明确的词语时。如用户查询“interest rate”，扩展后的查询却为“interest rate fascinate evaluate”，不太可能有用。
总体来说，查询扩展技术远没有相关度反馈技术更为成功，虽然它和伪相关度反馈技术具有差不多的效果。但是，从用户理解的容易度上看，它则更易于用户理解。