基于词语关联度的查询缩略

陈炜鹏，付瑞吉，胡 熠，秦 兵，刘 挺

(1. 哈尔滨工业大学 计算机科学与技术学院社会计算与信息检索研究中心，黑龙江 哈尔滨 150001；2. 腾讯公司搜索平台部，广东 深圳 518057)

1 前言

查询优化是信息检索研究中的一个重要的问题。本文探索有效地滤除冗长查询中冗余成份的方法，提高检索效果。

搜索引擎的一般原理是对于用户提交的搜索关键词，搜索引擎根据关键词在网页索引库中进行检索，最后以一定的排序算法输出相关的文档。显然，用户输入的查询包含的关键词越多，检索的难度越大。在查询中，用户常常在添加很多对于检索关键词的补充和修饰成份，而这些成份对检索效果的提高并没有什么帮助，反而增加了搜索引擎的检索难度。

事实上，对于用户提交给搜索引擎的查询，都是用户对于希望获得的内容的限定，因此我们可以理解为对于用户查询的任何改动，在某种程度上都已经改变了用户的原意。但我们可以删除查询中给搜索引擎提供的“信息量”很小的词，尽可能小地更改用户查询意图，同时改善检索结果。例如,“东海最新军事新闻”中的“最新”就是这种小信息量的词。 而且有的检索关键词的语义可能已经隐含在查询中其他关键词中了，对于这类“零额外信息”的关键词，我们也可以予以删除。例如,查询“广东广州市气候特点”中的“广东”已经蕴含在“广州市”的信息之中了。

本文提出了一种基于关键词之间搭配紧密度的缩略方法，我们首先分析查询关键词之间的依存句法关系，然后结合关键词之间的搭配紧密度，确定冗余关键词，予以删除。同时，我们还将缩略看成是一个子查询选择的过程，将原查询任意去掉一个词即可获得一个子查询，我们在任意一词的子查询集合中，选取与原查询语义最接近的子查询作为缩略。为了评价结果的有效性，我们从“面向机器”的角度，评价查询缩略对于提高检索结果文档召回数量的帮助；从“面向用户”的角度，评价查询缩略对于提高检索质量的帮助。实验结果表明，我们的方法能够提高检索结果的数量和检索质量。

2 相关研究

查询缩略是查询优化中一项重要的方式，引起了很多研究者的关注。国外的学者Bendersky等人[1]和Kumaran等人[2]在TREC语料上的实验结果表明，查询缩略能够提高检索的效果。词冗余[3]和区分查询中补充成分和主要成分的困难[4]，导致搜索引擎不能正确地理解用户提交的自然语言查询的意图。

从关键词发现的角度，Allan等人[3]利用语言和统计的方法发现查询中的核心概念。Bendersky等人[1]利用adaboost分类器给查询中的词赋权，从而确定词的重要性。从排序的角度，Lease等人[4]提出利用排序模型，对查询关键词进行排序，从而确定词的重要性。从子查询排序的角度，Jones等人[5]利用点互信息构建最大生成树，获得子查询集合，并且利用用户的点击信息，从中确定最佳的子查询，证实子查询确实能够提高检索的效果。Balasubramanian等人[6]选取了一些有效的特征，包括文档特征和检索分值特征等，用于三种学习方法对查询进行缩略。以上的方法均是基于语言统计信息的，不能很好地利用检索词之间的关联性信息来确定词的重要性。

验证查询缩略的效果，也是一个重要的问题。Bendersky等人[7]和Lease等人[4]研究都是基于TREC语料，他们分别将缩略前后的查询在TREC语料中检索，从检索的结果集来判断查询缩略的有效性。但是，基于特定语料集上面优化的结果，并不能完全反映在实际搜索引擎中的效果。所以Samuel等人[8]和Guo等人[9]利用搜索引擎的结果，人工标注结果文档，确定优化的效果。以上方法代价比较大。在本文中我们尝试从“面向机器”和“面向用户”两个角度来评价查询缩略的结果。

3 基于词语关联度的查询缩略方法

基于词语关联度的查询缩略，从两个方面来解决查询缩略的问题： 1)基于依存搭配的查询缩略根据依存链两端词的紧密度，发现冗余词；2)基于词语关联度的子查询选择比较子查询与原始查询的紧密度，发现与原查询紧密度最大的子查询。

3.1 基于依存搭配的查询缩略

对于一个冗长查询，我们考察的是关键词之间的蕴含关联，即可能存在某个词的语义已经蕴含在其他的词之中，那么对于这一类词，予以删除。在保证用户的查询意图没有偏移的前提下，召回更多的检索结果，减少“零信息”词对查询结果的影响。我们认为查询词之间的关联关系体现在句法的依存关系之中。对于存在依存句法关联的词，它们存在语义的关联。我们需要发现它们之间的语义蕴含作为缩略的依据，即某个修饰成份经常只充当另一成分的补充。基于搭配的缩略主要的方法是利用依存分析的结果，并且结合词性和命名实体信息，发现一些频繁模式，滤除查询中的一些冗余的修饰关系。

我们主要考察ATT关系(定中关系)、VOB关系(动宾关系)和ADV关系(状中关系)。例如,图1所示的例子中的“电视”和“连续剧”存在“ATT”关系，结合词性和搭配关系，我们删除“电视”。

图1 依存句法分析例子

考察两个词之间的搭配紧密度，一共有三种衡量的方法。分别是：

1) 点互信息。对于搭配的发现，一种以信息论为根据的方法是互信息。对于我们的情况，两个具体词同现的点互信息如式(1)所示。

其中，N代表句子的数目；a代表词wi和词wj共同出现的句子数；b代表词wi出现，词wj不出现的句子数；c代表词wi不出现，词wj出现的句子数。互信息是二元组p(x,y)的概率和两单独词的概率乘积p(x)*p(y) 的似然对数比。考虑两种极端的情况： 两个词的出现是完全互相依赖的(它们是一起出现)或完全独立的(一个词出现不能给出关于其他词出现的任何信息)。对于完全的互相依赖，有式(2)。

也就是说，在完全依赖的二元组中，当它们出现的次数减少时，它们的互信息是增加的。对于完全独立的情况，有式(3)。

互信息是衡量独立性的一种很好的方法，接近0的互信息表明了概率的独立性。

2) 最大似然比。似然比是假设检验的另一种方法。我们考察用式(4)、式(5)两个可选的假设来解释二元组(x，y)的出现频率。假设：

假设1：

假设2：

假设1是独立性假设的形式(x的出现和前面y的出现是独立的)，假设2是非独立性假设的形式化，对于我们感兴趣的搭配，是一个很好的证据。该方法的形式化描述见式(6)。

其中，N代表句子的数目；a表示词wi和词wj共同出现的句子数；b表示词wi出现，词wj不出现的句子数；c表示词wi不出现，词wj出现的句子数；d表示两个词都不出现的句子数。

3) 卡方分布。卡方分布又称χ2统计，可以用于度量词与词独立程度，卡方值越大，独立性越小，相关性越大。令N表示训练语料中的句子总数，c为某一个词，t表示与其搭配的词条，A表示包含c词条且包含t词条的句子频数，B表示不包含c词条但是包含t词条的句子频数，C表示包含c词条但是不包含t词条的句子频数，D是既不包含c词条也不包含t词条的句子频数，则t对于c的卡方值由式(7)计算：

通过观察，我们对ATT、VOB和ADV这三种关系制定如下启发式规则：

• ATT关系。首先我们找出句子中存在ATT关系的词对(a，b)，b依存于a，即b的父亲是a，然后计算它们搭配紧密度，如果这个值超过阈值T_att_association，则说明这两个词之间联系非常的紧密。在这种情况下，我们利用词频比例关系freq(b)/freq(a)来确定删除哪一个词，如果比例超过阈值T_att_freq，删除词b，否则删除词a。

• VOB关系。首先我们找出句子中存在VOB关系的节点对(a，b)，计算它们搭配紧密度，如果这个值超过阈值T_vob_association，则说明这两个词之间联系非常的紧密。然后，我们利用词频比例关系freq(a)/freq(b)来确定删除哪一个词，如果比例超过阈值T_vob_freq，删除词b，否则删除词a。

• ADV关系。首先我们找出句子中存在ADV关系的节点对(a，b)，b的父节点是a，如果(a，b)的搭配紧密度超过阈值T_adv_association，且词a不是“不”、“没”、“没有”、“未”、“非”、“莫”、“未必”等否定副词时，则将其删除。

值得注意的是，每个规则使用的阈值都是不同的。通过对关键词依存搭配的统计，我们发现并删除语义蕴含在其他词中的关键词，达到查询缩略的目的。

3.2 基于词语关联度的子查询选择

查询缩略的本质在于从查询中发现相对不重要的词。对于一个词，如果这个词和查询中的其他词之间的紧密度非常小，可以认为这个词是一个相对不重要的词。基于此，可以将查询缩略看成是原始查询子查询选择的问题，即对于原始查询可以扩展出多个子查询，在这些候选子查询中选择与原始查询最接近的查询。一个好的子查询应该满足： 只保留重要的词。用户在提交查询时，出于语言通畅性的表示，往往采用口语化表达，夹杂很多不重要的关键词，理想的搜索引擎应该给这一类词赋予很低的权重，但是在实际使用中，删除这一类词往往能够带来更好的检索效果。例如，查询“2010世界杯用球的名字叫什么”，如果只保留其中的关键字“2010世界杯用球名字”，检索效果更好。

基于上面的分析，我们通过一个例子来介绍具体的方法：

1) 对于原始查询进行名词短语切分，例如，对于查询“2007年云南省曲靖市中考考生成绩查询”识别为“2007年 云南省 曲靖市 中考 考试 成绩 查询”。

2) 构造原始查询的子查询，即任去一词，构成子查询。“2007年云南省曲靖市中考考试成绩查询”，我们构造子查询“云南省曲靖市中考考试成绩查询”，“2007年曲靖市中考考试成绩查询”等子查询。

3) 对于任一查询，利用统计确定查询词的关联度。公式如下：

4) 对于任意查询，Chi最接近原始查询的子查询，可以认为与原查询最接近，即是语义含义与原查询最接近的子查询。

5) 对于获得的与原查询最接近的子查询，如果与原查询之间的差别如式(9)所示。

我们则认为原查询与子查询的差别非常的小，只要差别在我们容许的δ的范围内，我们可以对子查询继续迭代上述的子查询选择过程，对查询进行进一步缩略，直到不满足公式(9)为止。

基于以上方法，我们即可在不改变用户查询意图的条件下，尽可能地对冗长查询进行缩略优化，改善检索结果。

4 实验和结果

4.1 实验设置

实验部分，我们使用由腾讯公司提供20 022条在SOSO搜索引擎中查询效果不佳的冗长查询，从中随机抽取用作开发和测试*感谢腾讯公司为本课题提供资金和数据支持.。另外，我们使用规模为1.1G的搜狗全网新闻语料库(SogouCA)*http://www.sogou.com/labs/dl/ca.html作为背景语料库，用来统计词语频率等信息。

4.2 评价方法

为了验证基于词关联度的缩略对于检索结果的帮助，我们分别从“面向机器”和“面向用户”两个角度进行评价，前者衡量检索数量的提高，后者衡量检索质量的提高，结合机器自动评价和人工评价来验证本文方法的有效性。

4.2.1 “面向机器”的自动评价

“面向机器”的自动评价，从提升用户的检索体验出发，考察对于一个冗长查询的处理，能否召回更多相关的结果，而这些关键词还要尽量能够包含在检索的效果中。因为冗长的查询容易引起检索结果仅有寥寥几条且没有正确结果，此时帮助用户自动裁剪查询，提高返回结果数是有意义的。我们主要关注两个因素：

1) 返回结果的绝对数量。

将处理后的查询输入SOSO中搜索，返回的结果数比原始冗长查询的结果数有所提高。

2) SOSO返回结果标红的比率(即返回的结果的包含查询关键词的比率)。

具体的计算公式如式(10)所示。

其中l(ei)指的是将查询输入SOSO后，第i条title中标红的关键词去重后的长度；l(q)指的是查询的长度；我们考察搜索结果中前n条title的数量，在实验部分，我们考查前10条。

例如，查询“007街机游戏图片”返回的一条title如图2所示。其中标红的关键词为“街机游戏”，对应的l(ei)为4，而l(q)为9，假如我们只考虑第一条检索结果，则标红率为4/9=0.44，可见这条查询的效果并不好。

图2 搜索结果标红率示例

通过观察，我们认为应该分两种情况考虑我们的评测方法。

首先，我们认为一个查询返回的结果数不超过一定的阈值(countThreshold)时，返回结果数量的提升更为重要，若处理后的查询能让结果数得到提升，我们即认为是一个好的处理。例如，原始长尾查询“6.13号临沂地震”，返回的结果只有127条，在这种情况下，我们认为缩略“临沂地震”，对应搜索结果为847 000，大大提高了返回数，是一个好的处理。

其次，如果原始查询结果数超过阈值(countThreshold)，那么对于搜索结果而言，提升搜索结果的标红率(反映了结果的质量)显得更为重要，在这种情况下，我们要求处理后的查询在标红率应该有所提高。允许返回的结果数有所下降，但不能下降太多，保证在原长尾查询结果数的80%以上。当然，结果数和标红率同时提高是最理想的。

4.2.2 “面向用户”的人工评价

“面向用户”的人工评价， 考察的是缩略后的查询能够提高检索结果的质量，即在保证用户查询意图的前提下，召回更多高质量的检索答案。我们比较缩略前后的查询输入搜索引擎后获取的前10条结果文档集，人工判断缩略后查询返回的文档集是否更好地符合用户的查询意图。两名志愿者参与人工评价，将两名志愿者达成一致的结果作为正确答案。

4.3 实验结果

实验时，我们首先进行基于依存搭配的查询缩略，然后串联地进行基于词语关联度的子查询选择，其中所有的参数都是在开发集上调试获得的经验最优值。开发集是从腾讯公司提供的冗长查询集中随机选取并经过人工标注获得的300条查询。

我们从两个方面展开实验： 一是探索不同的搭配识别方法对查询缩略的影响；二是与其他方法的对比，验证方法的有效性。

4.3.1 搭配识别方法的影响

为了探索不同的搭配紧密度衡量方法对实验结果的影响，我们比较了互信息、最大似然比和卡方分布对结果的影响，我们分别从“面向机器”和“面向用户”两个角度，对100条冗长查询的缩略进行评价，“面向机器”的结果如图3所示，“面向用户”的结果如表1所示。

图3 不同紧密度衡量方法的影响(自动评价)

准确率@1/%平均准确率/%互信息最大似然比卡方分布互信息最大似然比卡方分布64.0065.0068.0052.3555.8956.47

图3中，阈值(countThreshold)为搜索结果阈值，即当搜索结果数量小于countThreshold时，我们更注重结果数的提升，当大于阈值时，我们更注重检索质量(标红率)的提升。从实验结果的比较可以看出，使用卡方分布作为衡量搭配紧密度的方法在“面向机器”的自动评价中，并没有表现出优势，与基于互信息和最大似然比的方法相当；但在“面向用户”人工评价中，得到了比较好的效果。

4.3.2 对比实验

作为参照，我们以利用大规模查询日志统计idf为词权重的方法，作为Baseline。当一个词的idf小于某一阈值时，则认为该词不重要，将其删除。分别在腾讯提供的冗长查询上进行测试，实验结果如图4和表2所示。

图4 自动评测结果

准确率@1/%平均准确率/%BaselineOurMethodBaselineOurMethod52.0068.0044.1256.47

我们从腾讯公司提供的冗长查询中，随机抽取了1 063条查询进行自动评价，平均每条长尾查询提供1.67条候选。随机抽取100条冗长查询进行人工评价，比较缩略前后搜索引擎返回的前10条结果的质量。通过人工查验返回的相关结果集，来确定是否缩略后的相关结果更加切合用户的查询意图。

从对照试验可以看出，不同的搜索结果阈值表现出的结果波动并不是很明显，但是在10 000左右，结果比较好，这可以看出缩略对于提高检索结果的数量比较明显。综上，基于词关联度的缩略能够返回更多“标红”率高的检索结果，提升用户的检索体验。在保证检索数量的情况下，我们的方法能够明显提高冗长查询的检索质量。

5 结论

本文提出了一种基于词语关联的查询缩略的方法。结合依存句法和搭配识别，发现查询中的语义蕴含关系，删除冗余词；基于词语关联的子查询选择，发现信息量小的词，将其删除。为了验证结果的有效性，我们提出了“面向机器”的自动评价方法和“面向用户”的人工评价方法，从返回结果的数量和质量两个角度，对缩略的结果进行评价。实验结果表明，我们的方法能够有效地剔除查询中冗余的成份，提高检索的数量和质量。在下一步的工作中，我们将探索新方法发现更多依存搭配的频繁模式，进一步提高查询缩略的效果。

[1] M Bendersky， W B Croft. Discovering key concepts in verbose queries[C]//Proceedings of SIGIR 08, 2008： 491-498.

[2] G Kumaran， J Allan. A case for shorter queries, and helping user create them[C]//Proceedings of HLT.2007： 220-227.

[3] J Allan, J Callan, W B Croft, et al. INQUERY at TREC-5[C]//Proceedings of the 5th Text Retrieval Conference TREC-5. 1997: 119-132.

[4] M Lease, J Allan, W B Croft. Regression rank: learning to meet the opportunity of descriptive queries[C]//Proceedings of ECIR 2009. 2009: 90-101.

[5] R Jones, D C Fain. Query word deletion prediction[C]//Proceedings of 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2003: 435-436.

[6] N Balasubramanian, G Kumaran, V R Carvalho. Exploring reductions for long web queries[C]//Proceedings of the 33rd international ACM SIGIR Conference on Research and Development in information Retrieval. 2010: 571-578.

[7] G Kumaran, J Allan. Adapting information retrieval systems to user queries. Information Processing and Management[J]. 2008: 1838-1862.

[8] S Huston and W B. Croft. Evaluating verbose query processing techniques[C]//Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in information Retrieval, SIGIR ’10, New York, NY, USA, 2010： 291-298.

[9] J Guo, G Xu, H Li, et al. A unified and discriminative model for query refinement[C]//Proceedings of SIGIR ’08, New York, NY, USA, 2008：379-386.