主题：[推荐]《An Introduction to Information Retrieval》参考译文之七——完整信息检索系统中的分值计算问题

7 完整信息检索系统中的分值计算问题

7．1 分值的有效计算和排序
前文已经说明计算余弦相似度的算法，对于查询如“jealous gossip”，可以看出两个明显得特点：一是单位向量只有两个非零的元素；二是如果没有其他查询词语的权重，则两个元素的值相等，都为0.707。
事实上，计算余弦相似度的主要目的在于结果排序，所以我们实际关心的问题是相对权值，而非绝对权值。所以，为了方便可以不使用单位向量v(d)，而使用新的向量V(d)，这个查询向量将所有非零的成员皆设置为1。对于任何文档d而言，余弦相似度V(q)×v(d)是所有文档中查询词项权重的总和。可以按照前文所述的标记交操作算法得到最终的结果。由于文档向量中的非零元素设置为1，则原有算法中的成绩和操作变成了单纯的和操作。
该算法直接遍历倒排索引中的查询词语权值并对其求和，这和处理一般的布尔查询差不多，只是多个对每篇文档分配一个正的权值。
在得到权值以后，最后的步骤就是挑出最高权值的K个文档，这可以使用堆（heap）结构来实现。假设有J篇文档具有非零的权值，构造这样的堆结构只需2J次比较，而且检索前面K个文档也只需LogJ次比较。

下面介绍一些求前K篇高权重文档的非精确算法。
事实上，在处理海量规模文档时采用一些非精确算法完全可以满足用户的要求，这样做还可以极大了降低计算开销。退一步说，即便是精确度较差也并非大事，因为毕竟余弦相似度只是一种揣测用户所认为的文档相关度的方法。
从上述算法可以看出，计算余弦相似度是导致算法性能降低的主要因素，所以减少需要计算的文档数量是非常重要的。而且所得到的候选文档集合规模也会对进一步挑选前K篇文档的性能产生重要影响。
下面的这些方法基本上都采用如下思路：首先从所有文档中挑选出A篇文档，K<A<<N，但是这些文档应尽可能的包含前K篇高权值文档；其次，返回A篇文档中的前K篇高权值文档。
为此，我们必须拥有一些必要的参数来进行选择，得这些参数需要很多经验。不过，这些启发式方法非常适合自由文本检索的要求，而非纯粹的布尔检索和词组检索。

1）索引消除法（Index elimination）
它的意思是指利用索引文件进行文档的筛选。对于一个包含多个词语的查询而言，可以想象只有包含至少一个查询词语的文档才有必要被考虑。除此以外，还可以借助下面的一些启发式规则：
一是只考虑那些倒文档频率超过一定阈值的查询词语，在遍历标记列表的时候，只需遍历那些具有较高倒文档频率的词语。这样做的好处在于由于较低倒文档频率的词语通常具有较长的标记列表，因此不去对其遍历将能极大的减少需要计算的文档量。事实上，这些具有较低倒文档频率的词语通常多为停用词，对分值的计算意义不大。如查询“catcher in the rye”，我们只需对catcher和rye的标记列表进行遍历。在考虑查询相关的情况下，阈值也可以适当调整。
二是应当尽可能考虑那些包含较多查询词语的文档，极端的情况就是包含全部词语。在可以在遍历标记列表的时候完成。不过，这也存在一定负面影响，那就是可能得到的满足条件的文档数量会少于K。

2）优胜列表法（Champion lists）
这种方法有时也被称为（fancy lists）或者（top docs），它对字典中的每个词语预先计算和其具有较高相关性的r篇文档，r也需要事先定下来。对于tf/idf方法而言，就意味着词语t所得到的这些r篇文档应该具有较高词语tf值，这些r篇文档被称为词语t的优胜列表。
对于查询q而言，得到文档集合A的方法就是合并每个查询词语对应的优胜列表文档，接下来只对这些文档计算余弦相似度。这里最为关键的问题在于r值的选取，r值显然与查询要求高度相关。直觉可以看出r值应当比K值大，特别在使用索引消除法的时候更是如此。由于r值是在索引构建时确定，而K值是与查询要求相关，所以只有到查询时才能得到。所以，有可能也会得到的候选文档数量少于K。另外，对于不同的词语也可以使用不同的r值，如对于罕用词可以设置较高的r值。

3）静态质量分值和排序（Static quality scores and ordering）
在很多搜索引擎系统当中，都有对所有文档的一种质量测度值g(d)，它与查询无关，所以可以被称为是静态质量分值，一般取值在0到1之间。比如对于Web上的新闻信息而言，g(d)可以根据Web用户对其的评论数量来设定。
所以，文档的最终权值就可以设定为g(d)和前文所述的查询相关权值之和。如何组合两者，复杂的方法可以使用诸如机器学习等方法来得到组合策略，比较简单的做法就是直接相加。显然，虽然最终的取值可以会因为组合方法不同而不同，但是我们实际所关心的数值只是它们的相对取值。
取得上述文档最终权值后，可以对标记列表中所有词语的标记按照文档的g(d)数值来降序排序
对于这样的标记列表仍然可以进行交操作算法，事实上，标记列表中的标记并不一定非要按照文档号来排序，只要按照一个合理的次序就可以。
按照这个思路，可以改进前文的优胜列表法。给定一个选择好的r值，对于词语t维持一个全局优胜列表，它含有具有最高g(d) + tf-idf值的r篇文档。列表中的所有词项既可以按照文档号也可以按照静态质量分值来排序。在查询时，只对这些全局优胜列表中的文档计算它们的最终权值。显然，这样做可以使得检索的范围限定在具有较高权值的文档集合中。
上述思想可以继续扩展。如对于每个词语还可以维护两个甚至更多的标记列表，这些标记列表分别保存不同的文档，每个标记列表都按照g(d)排序。其中第一个标记列表的文档都是具有最高的t词语tf值。剩下的标记列表依次类推。在检索时，首先使用第一个标记列表进行匹配计算，如果能够得到K篇文档则停止计算，如果不够K篇文档，则继续搜索剩下的标记列表。

4）影响排序法（Impact ordering）

5）聚类剪除法（Cluster pruning）

7．2 信息检索系统的构造
7．2．1 多层索引结构（Tiered indexes）
正如前文所述，可以采用多层索引结构来提高计算性能，如图所示：

此主题相关图片如下：

图中所显示的第一层索引，相应的tf阈值为20，而第二层索引的tf阈值为10。所以对第一层索引得检索可以得到tf值至少高于20的有关文档。每个词语的标记都按照文档号排序。

7．2．2 查询词语的位置关系
Web用户广泛的采用自由文本检索方法来使用搜索引擎，用户往往只是键入一些没有任何逻辑操作符关联的若干词语，而所命中的文档往往也都包含这些全部或者部分词语，而且这些词语在文档中的位置往往很*近，显然这样的文档很能够反映用户的真正查询请求。
假设用户的查询由t1、…、tk组成，设w为包含这些全部词语的文档d中相关词语最短的词语序列，也被称为最小滑窗（window）。如只有一句话的文档“The quality of mercy is not strained”，查询“strained mercy”的最小滑窗为“mercy is not strained”，长度就是4。显然，滑窗长度越短，文档和查询的匹配程度越高。对于没有含有任何查询词语的文档而言，可以设w为一个非常大的数值。另外，在考虑滑窗计算的时候，还可以忽略停用词。这种位置加权的文档权重计算方法和一般的余弦相似度计算方法不同，更类似于Google搜索引擎采用的软连接（soft conjunctive）语义方法。

7．2．3 查询解析和分值计算方法的设计
很多诸如搜索引擎之类的面向一般用户的信息检索系统，往往会将复杂的查询操作隐藏在简单的处理界面后，所以自由文本查询（free text query）较为流行。给定很多不同要求的索引，信息检索系统如何来处理诸如“rising interest rates”之类的检索请求呢？也就是说，现在我们已经研究了很多不同的文档权值计算方法，在没有用户明确指定的情况下，该组合使用哪些方法呢？
要想回答这个问题，就依赖于以下几个条件：用户群的特点、查询的分布和文档集合的特点等。所以，这就需要一个查询解析器来对用户输入的查询词语进行解析，将其生成可以执行的不同查询请求。如对于上述的例子而言，首先将其看成是一个词组查询，使用向量空间模型来计算包含这三个词语的文档权值；其次，如果满足条件的文档数量太少，则自动将其转换为两两词语组合的查询请求，如“rising interest”和“interest rates”，仍然使用向量空间模型来计算包含这三个词语的文档权值；最后，如果结果文档数量还是太少，则使用这三个单独的词语分别查询满足条件的文档。
事实上，在计算文档权值的时候，不仅使用向量空间模型，而且还会使用静态质量分值、位置加权和各种其他的因素。特别是有些文档可能会在很多步骤中被计算权值，所以必要的时候还可以累计这些文档的权值。不过，如何设计这个累计算法呢？
答案依赖于环境。在很多企业环境下，应用程序构造者往往已经具有了一些分值计算工具，可以手工调整诸如分值计算功能或者查询解析功能等。不同的环境下文档集合的稳定性各不一样，如在Web环境下，文档集合的变化是经常的。此时使用手工调整等方式显然不切实际，更多的方法应当使用诸如机器学习等。

7．2．4 组装
如图所示：

此主题相关图片如下：

图中的文档信息流首先被进行语义处理，包括语言和格式检验、标识化和词根处理等。得到的标识被继续送往两个模块：一个是被存储在文档缓存中，这些缓存的内容可以生成在结果页面中的网页内容摘要；另一个是被送往索引处理器，生成包括字段索引、位置索引和其他一些索引形式。用户所发出的自由文本查询则被进行索引搜索，有时还进行必要的拼写校正以得到候选的查询词语，这通常发生在原始用户查询的返回结果不足的时候。最后得到的文档结果被送往分值处理模块，并排序后输出到用户端。

7．3 向量空间模型方法和其他查询操作方法的结合
向量空间模型方法主要适用于自由文本查询的要求，不过，也可以和传统的很多检索方法结合起来。可以从两个角度来审视向量空间方法和其他查询操作方法的关系，一是有经验的用户可能需要表达较为复杂的查询请求，所以可以从系统是否满足用户要求的角度来观察，二是借助能够对查询进行评价的索引，可以检查这些方法的最终效果。
向量空间模型不像传统的布尔模型，它将用户查询看成是一个词语的序列，并忽略相关的查询操作符，对匹配的文档进行权值的计算并排序输出。对自由文本查询的简单理解就是被检索的文档至少含有一个查询词语。但是，近些年来的研究和实践都表明。很多诸如Google之类的搜索引擎开始关注查询词语的相关性问题，也就是说，位于一齐的若干词语彼此之间存在着语义关联，所以被检索的文档应可能的含有全部或者更多的查询词语。

7．3．1 布尔检索的结合
向量空间索引可以用于回答布尔查询问题，因为只要含有词语t的文档d就会在文档d的向量元素中存储一个非零的元素值。但是，反之并不一定，因为布尔索引中并没有具体的词语权值。所以，将两种检索方法结合起来，从用户的观点来看也是很难做到的。可以这样理解向量空间检索，它是一种特征累积（evidence accumulation）的计算形式，文档中的词语权值汇总成文档的最终权值。而布尔检索只是允许用户选择（selecting）文档是否含有查询词语，文档只有满足和不满足这两种情况，文档之间没有任何相对的权值问题。从数学角度来看，可以使用所谓的p-norms方法来组合两种方法，但是并不存在实际的真实系统实现。

7．3．2 通配符检索的结合
两者使用不同形式的索引，若说相同，只是在基本层次上都使用标记和字典等数据形式。如果搜索引擎系统允许用户在进行自由文本查询的时候使用通配符，那就意味着含有通配符的查询实际上对应着很多个查询向量，如查询“rom* restaurant”，满足条件的查询向量有“rome restaurant”和“roman restaurant”等。向量空间检索方法和以前一样，对搜索到的文档计算分值并排序。不过，如果文档同时含有rome和roman的话，应该比只含有一个词语的文档具有更高的权值。

7．3．3 词组检索的结合
使用文档向量表达文档会丢失部分信息，如丢失了词语之间的次序关系。即便是使用双词（biword）表达向量元素，这些不同双词元素的权值也不是互相独立的，如“German shepherd”词组对应自己的双词元素，但是对于German和shepherd两个词项元素而言，它也有非零的权值。而且，诸如idf之类的数值都需要考虑双词问题。这显然会极大的增加处理难度。所以，向量空间索引一般不能用于词组检索。而且，我们也没有什么好方法能够对词组整体进行权值的计算，毕竟我们只能得到文档中每个词语的相对权值。
所以，这现实的信息检索系统中，这两个方法只能互相补充，不能合而为一。