基于詞語關(guān)聯(lián)度的查詢縮略

陳煒鵬，付瑞吉，胡 熠，秦 兵，劉 挺

(1. 哈爾濱工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院社會計算與信息檢索研究中心，黑龍江 哈爾濱 150001；2. 騰訊公司搜索平臺部，廣東 深圳 518057)

1 前言

查詢優(yōu)化是信息檢索研究中的一個重要的問題。本文探索有效地濾除冗長查詢中冗余成份的方法，提高檢索效果。

搜索引擎的一般原理是對于用戶提交的搜索關(guān)鍵詞，搜索引擎根據(jù)關(guān)鍵詞在網(wǎng)頁索引庫中進(jìn)行檢索，最后以一定的排序算法輸出相關(guān)的文檔。顯然，用戶輸入的查詢包含的關(guān)鍵詞越多，檢索的難度越大。在查詢中，用戶常常在添加很多對于檢索關(guān)鍵詞的補(bǔ)充和修飾成份，而這些成份對檢索效果的提高并沒有什么幫助，反而增加了搜索引擎的檢索難度。

事實(shí)上，對于用戶提交給搜索引擎的查詢，都是用戶對于希望獲得的內(nèi)容的限定，因此我們可以理解為對于用戶查詢的任何改動，在某種程度上都已經(jīng)改變了用戶的原意。但我們可以刪除查詢中給搜索引擎提供的“信息量”很小的詞，盡可能小地更改用戶查詢意圖，同時改善檢索結(jié)果。例如,“東海最新軍事新聞”中的“最新”就是這種小信息量的詞。 而且有的檢索關(guān)鍵詞的語義可能已經(jīng)隱含在查詢中其他關(guān)鍵詞中了，對于這類“零額外信息”的關(guān)鍵詞，我們也可以予以刪除。例如,查詢“廣東廣州市氣候特點(diǎn)”中的“廣東”已經(jīng)蘊(yùn)含在“廣州市”的信息之中了。

本文提出了一種基于關(guān)鍵詞之間搭配緊密度的縮略方法，我們首先分析查詢關(guān)鍵詞之間的依存句法關(guān)系，然后結(jié)合關(guān)鍵詞之間的搭配緊密度，確定冗余關(guān)鍵詞，予以刪除。同時，我們還將縮略看成是一個子查詢選擇的過程，將原查詢?nèi)我馊サ粢粋€詞即可獲得一個子查詢，我們在任意一詞的子查詢集合中，選取與原查詢語義最接近的子查詢作為縮略。為了評價結(jié)果的有效性，我們從“面向機(jī)器”的角度，評價查詢縮略對于提高檢索結(jié)果文檔召回數(shù)量的幫助；從“面向用戶”的角度，評價查詢縮略對于提高檢索質(zhì)量的幫助。實(shí)驗結(jié)果表明，我們的方法能夠提高檢索結(jié)果的數(shù)量和檢索質(zhì)量。

2 相關(guān)研究

查詢縮略是查詢優(yōu)化中一項重要的方式，引起了很多研究者的關(guān)注。國外的學(xué)者Bendersky等人[1]和Kumaran等人[2]在TREC語料上的實(shí)驗結(jié)果表明，查詢縮略能夠提高檢索的效果。詞冗余[3]和區(qū)分查詢中補(bǔ)充成分和主要成分的困難[4]，導(dǎo)致搜索引擎不能正確地理解用戶提交的自然語言查詢的意圖。

從關(guān)鍵詞發(fā)現(xiàn)的角度，Allan等人[3]利用語言和統(tǒng)計的方法發(fā)現(xiàn)查詢中的核心概念。Bendersky等人[1]利用adaboost分類器給查詢中的詞賦權(quán)，從而確定詞的重要性。從排序的角度，Lease等人[4]提出利用排序模型，對查詢關(guān)鍵詞進(jìn)行排序，從而確定詞的重要性。從子查詢排序的角度，Jones等人[5]利用點(diǎn)互信息構(gòu)建最大生成樹，獲得子查詢集合，并且利用用戶的點(diǎn)擊信息，從中確定最佳的子查詢，證實(shí)子查詢確實(shí)能夠提高檢索的效果。Balasubramanian等人[6]選取了一些有效的特征，包括文檔特征和檢索分值特征等，用于三種學(xué)習(xí)方法對查詢進(jìn)行縮略。以上的方法均是基于語言統(tǒng)計信息的，不能很好地利用檢索詞之間的關(guān)聯(lián)性信息來確定詞的重要性。

驗證查詢縮略的效果，也是一個重要的問題。Bendersky等人[7]和Lease等人[4]研究都是基于TREC語料，他們分別將縮略前后的查詢在TREC語料中檢索，從檢索的結(jié)果集來判斷查詢縮略的有效性。但是，基于特定語料集上面優(yōu)化的結(jié)果，并不能完全反映在實(shí)際搜索引擎中的效果。所以Samuel等人[8]和Guo等人[9]利用搜索引擎的結(jié)果，人工標(biāo)注結(jié)果文檔，確定優(yōu)化的效果。以上方法代價比較大。在本文中我們嘗試從“面向機(jī)器”和“面向用戶”兩個角度來評價查詢縮略的結(jié)果。

3 基于詞語關(guān)聯(lián)度的查詢縮略方法

基于詞語關(guān)聯(lián)度的查詢縮略，從兩個方面來解決查詢縮略的問題： 1)基于依存搭配的查詢縮略根據(jù)依存鏈兩端詞的緊密度，發(fā)現(xiàn)冗余詞；2)基于詞語關(guān)聯(lián)度的子查詢選擇比較子查詢與原始查詢的緊密度，發(fā)現(xiàn)與原查詢緊密度最大的子查詢。

3.1 基于依存搭配的查詢縮略

對于一個冗長查詢，我們考察的是關(guān)鍵詞之間的蘊(yùn)含關(guān)聯(lián)，即可能存在某個詞的語義已經(jīng)蘊(yùn)含在其他的詞之中，那么對于這一類詞，予以刪除。在保證用戶的查詢意圖沒有偏移的前提下，召回更多的檢索結(jié)果，減少“零信息”詞對查詢結(jié)果的影響。我們認(rèn)為查詢詞之間的關(guān)聯(lián)關(guān)系體現(xiàn)在句法的依存關(guān)系之中。對于存在依存句法關(guān)聯(lián)的詞，它們存在語義的關(guān)聯(lián)。我們需要發(fā)現(xiàn)它們之間的語義蘊(yùn)含作為縮略的依據(jù)，即某個修飾成份經(jīng)常只充當(dāng)另一成分的補(bǔ)充?；诖钆涞目s略主要的方法是利用依存分析的結(jié)果，并且結(jié)合詞性和命名實(shí)體信息，發(fā)現(xiàn)一些頻繁模式，濾除查詢中的一些冗余的修飾關(guān)系。

我們主要考察ATT關(guān)系(定中關(guān)系)、VOB關(guān)系(動賓關(guān)系)和ADV關(guān)系(狀中關(guān)系)。例如,圖1所示的例子中的“電視”和“連續(xù)劇”存在“ATT”關(guān)系，結(jié)合詞性和搭配關(guān)系，我們刪除“電視”。

圖1 依存句法分析例子

考察兩個詞之間的搭配緊密度，一共有三種衡量的方法。分別是：

1) 點(diǎn)互信息。對于搭配的發(fā)現(xiàn)，一種以信息論為根據(jù)的方法是互信息。對于我們的情況，兩個具體詞同現(xiàn)的點(diǎn)互信息如式(1)所示。

其中，N代表句子的數(shù)目；a代表詞wi和詞wj共同出現(xiàn)的句子數(shù)；b代表詞wi出現(xiàn)，詞wj不出現(xiàn)的句子數(shù)；c代表詞wi不出現(xiàn)，詞wj出現(xiàn)的句子數(shù)。互信息是二元組p(x,y)的概率和兩單獨(dú)詞的概率乘積p(x)*p(y) 的似然對數(shù)比。考慮兩種極端的情況： 兩個詞的出現(xiàn)是完全互相依賴的(它們是一起出現(xiàn))或完全獨(dú)立的(一個詞出現(xiàn)不能給出關(guān)于其他詞出現(xiàn)的任何信息)。對于完全的互相依賴，有式(2)。

也就是說，在完全依賴的二元組中，當(dāng)它們出現(xiàn)的次數(shù)減少時，它們的互信息是增加的。對于完全獨(dú)立的情況，有式(3)。

互信息是衡量獨(dú)立性的一種很好的方法，接近0的互信息表明了概率的獨(dú)立性。

2) 最大似然比。似然比是假設(shè)檢驗的另一種方法。我們考察用式(4)、式(5)兩個可選的假設(shè)來解釋二元組(x，y)的出現(xiàn)頻率。假設(shè)：

假設(shè)1：

假設(shè)2：

假設(shè)1是獨(dú)立性假設(shè)的形式(x的出現(xiàn)和前面y的出現(xiàn)是獨(dú)立的)，假設(shè)2是非獨(dú)立性假設(shè)的形式化，對于我們感興趣的搭配，是一個很好的證據(jù)。該方法的形式化描述見式(6)。

其中，N代表句子的數(shù)目；a表示詞wi和詞wj共同出現(xiàn)的句子數(shù)；b表示詞wi出現(xiàn)，詞wj不出現(xiàn)的句子數(shù)；c表示詞wi不出現(xiàn)，詞wj出現(xiàn)的句子數(shù)；d表示兩個詞都不出現(xiàn)的句子數(shù)。

3) 卡方分布?？ǚ椒植加址Qχ2統(tǒng)計，可以用于度量詞與詞獨(dú)立程度，卡方值越大，獨(dú)立性越小，相關(guān)性越大。令N表示訓(xùn)練語料中的句子總數(shù)，c為某一個詞，t表示與其搭配的詞條，A表示包含c詞條且包含t詞條的句子頻數(shù)，B表示不包含c詞條但是包含t詞條的句子頻數(shù)，C表示包含c詞條但是不包含t詞條的句子頻數(shù)，D是既不包含c詞條也不包含t詞條的句子頻數(shù)，則t對于c的卡方值由式(7)計算：

通過觀察，我們對ATT、VOB和ADV這三種關(guān)系制定如下啟發(fā)式規(guī)則：

? ATT關(guān)系。首先我們找出句子中存在ATT關(guān)系的詞對(a，b)，b依存于a，即b的父親是a，然后計算它們搭配緊密度，如果這個值超過閾值T_att_association，則說明這兩個詞之間聯(lián)系非常的緊密。在這種情況下，我們利用詞頻比例關(guān)系freq(b)/freq(a)來確定刪除哪一個詞，如果比例超過閾值T_att_freq，刪除詞b，否則刪除詞a。

? VOB關(guān)系。首先我們找出句子中存在VOB關(guān)系的節(jié)點(diǎn)對(a，b)，計算它們搭配緊密度，如果這個值超過閾值T_vob_association，則說明這兩個詞之間聯(lián)系非常的緊密。然后，我們利用詞頻比例關(guān)系freq(a)/freq(b)來確定刪除哪一個詞，如果比例超過閾值T_vob_freq，刪除詞b，否則刪除詞a。

? ADV關(guān)系。首先我們找出句子中存在ADV關(guān)系的節(jié)點(diǎn)對(a，b)，b的父節(jié)點(diǎn)是a，如果(a，b)的搭配緊密度超過閾值T_adv_association，且詞a不是“不”、“沒”、“沒有”、“未”、“非”、“莫”、“未必”等否定副詞時，則將其刪除。

值得注意的是，每個規(guī)則使用的閾值都是不同的。通過對關(guān)鍵詞依存搭配的統(tǒng)計，我們發(fā)現(xiàn)并刪除語義蘊(yùn)含在其他詞中的關(guān)鍵詞，達(dá)到查詢縮略的目的。

3.2 基于詞語關(guān)聯(lián)度的子查詢選擇

查詢縮略的本質(zhì)在于從查詢中發(fā)現(xiàn)相對不重要的詞。對于一個詞，如果這個詞和查詢中的其他詞之間的緊密度非常小，可以認(rèn)為這個詞是一個相對不重要的詞。基于此，可以將查詢縮略看成是原始查詢子查詢選擇的問題，即對于原始查詢可以擴(kuò)展出多個子查詢，在這些候選子查詢中選擇與原始查詢最接近的查詢。一個好的子查詢應(yīng)該滿足： 只保留重要的詞。用戶在提交查詢時，出于語言通暢性的表示，往往采用口語化表達(dá)，夾雜很多不重要的關(guān)鍵詞，理想的搜索引擎應(yīng)該給這一類詞賦予很低的權(quán)重，但是在實(shí)際使用中，刪除這一類詞往往能夠帶來更好的檢索效果。例如，查詢“2010世界杯用球的名字叫什么”，如果只保留其中的關(guān)鍵字“2010世界杯用球名字”，檢索效果更好。

基于上面的分析，我們通過一個例子來介紹具體的方法：

1) 對于原始查詢進(jìn)行名詞短語切分，例如，對于查詢“2007年云南省曲靖市中考考生成績查詢”識別為“2007年 云南省 曲靖市 中考 考試 成績 查詢”。

2) 構(gòu)造原始查詢的子查詢，即任去一詞，構(gòu)成子查詢?！?007年云南省曲靖市中考考試成績查詢”，我們構(gòu)造子查詢“云南省曲靖市中考考試成績查詢”，“2007年曲靖市中考考試成績查詢”等子查詢。

3) 對于任一查詢，利用統(tǒng)計確定查詢詞的關(guān)聯(lián)度。公式如下：

4) 對于任意查詢，Chi最接近原始查詢的子查詢，可以認(rèn)為與原查詢最接近，即是語義含義與原查詢最接近的子查詢。

5) 對于獲得的與原查詢最接近的子查詢，如果與原查詢之間的差別如式(9)所示。

我們則認(rèn)為原查詢與子查詢的差別非常的小，只要差別在我們?nèi)菰S的δ的范圍內(nèi)，我們可以對子查詢繼續(xù)迭代上述的子查詢選擇過程，對查詢進(jìn)行進(jìn)一步縮略，直到不滿足公式(9)為止。

基于以上方法，我們即可在不改變用戶查詢意圖的條件下，盡可能地對冗長查詢進(jìn)行縮略優(yōu)化，改善檢索結(jié)果。

4 實(shí)驗和結(jié)果

4.1 實(shí)驗設(shè)置

實(shí)驗部分，我們使用由騰訊公司提供20 022條在SOSO搜索引擎中查詢效果不佳的冗長查詢，從中隨機(jī)抽取用作開發(fā)和測試*感謝騰訊公司為本課題提供資金和數(shù)據(jù)支持.。另外，我們使用規(guī)模為1.1G的搜狗全網(wǎng)新聞?wù)Z料庫(SogouCA)*http://www.sogou.com/labs/dl/ca.html作為背景語料庫，用來統(tǒng)計詞語頻率等信息。

4.2 評價方法

為了驗證基于詞關(guān)聯(lián)度的縮略對于檢索結(jié)果的幫助，我們分別從“面向機(jī)器”和“面向用戶”兩個角度進(jìn)行評價，前者衡量檢索數(shù)量的提高，后者衡量檢索質(zhì)量的提高，結(jié)合機(jī)器自動評價和人工評價來驗證本文方法的有效性。

4.2.1 “面向機(jī)器”的自動評價

“面向機(jī)器”的自動評價，從提升用戶的檢索體驗出發(fā)，考察對于一個冗長查詢的處理，能否召回更多相關(guān)的結(jié)果，而這些關(guān)鍵詞還要盡量能夠包含在檢索的效果中。因為冗長的查詢?nèi)菀滓饳z索結(jié)果僅有寥寥幾條且沒有正確結(jié)果，此時幫助用戶自動裁剪查詢，提高返回結(jié)果數(shù)是有意義的。我們主要關(guān)注兩個因素：

1) 返回結(jié)果的絕對數(shù)量。

將處理后的查詢輸入SOSO中搜索，返回的結(jié)果數(shù)比原始冗長查詢的結(jié)果數(shù)有所提高。

2) SOSO返回結(jié)果標(biāo)紅的比率(即返回的結(jié)果的包含查詢關(guān)鍵詞的比率)。

具體的計算公式如式(10)所示。

其中l(wèi)(ei)指的是將查詢輸入SOSO后，第i條title中標(biāo)紅的關(guān)鍵詞去重后的長度；l(q)指的是查詢的長度；我們考察搜索結(jié)果中前n條title的數(shù)量，在實(shí)驗部分，我們考查前10條。

例如，查詢“007街機(jī)游戲圖片”返回的一條title如圖2所示。其中標(biāo)紅的關(guān)鍵詞為“街機(jī)游戲”，對應(yīng)的l(ei)為4，而l(q)為9，假如我們只考慮第一條檢索結(jié)果，則標(biāo)紅率為4/9=0.44，可見這條查詢的效果并不好。

圖2 搜索結(jié)果標(biāo)紅率示例

通過觀察，我們認(rèn)為應(yīng)該分兩種情況考慮我們的評測方法。

首先，我們認(rèn)為一個查詢返回的結(jié)果數(shù)不超過一定的閾值(countThreshold)時，返回結(jié)果數(shù)量的提升更為重要，若處理后的查詢能讓結(jié)果數(shù)得到提升，我們即認(rèn)為是一個好的處理。例如，原始長尾查詢“6.13號臨沂地震”，返回的結(jié)果只有127條，在這種情況下，我們認(rèn)為縮略“臨沂地震”，對應(yīng)搜索結(jié)果為847 000，大大提高了返回數(shù)，是一個好的處理。

其次，如果原始查詢結(jié)果數(shù)超過閾值(countThreshold)，那么對于搜索結(jié)果而言，提升搜索結(jié)果的標(biāo)紅率(反映了結(jié)果的質(zhì)量)顯得更為重要，在這種情況下，我們要求處理后的查詢在標(biāo)紅率應(yīng)該有所提高。允許返回的結(jié)果數(shù)有所下降，但不能下降太多，保證在原長尾查詢結(jié)果數(shù)的80%以上。當(dāng)然，結(jié)果數(shù)和標(biāo)紅率同時提高是最理想的。

4.2.2 “面向用戶”的人工評價

“面向用戶”的人工評價， 考察的是縮略后的查詢能夠提高檢索結(jié)果的質(zhì)量，即在保證用戶查詢意圖的前提下，召回更多高質(zhì)量的檢索答案。我們比較縮略前后的查詢輸入搜索引擎后獲取的前10條結(jié)果文檔集，人工判斷縮略后查詢返回的文檔集是否更好地符合用戶的查詢意圖。兩名志愿者參與人工評價，將兩名志愿者達(dá)成一致的結(jié)果作為正確答案。

4.3 實(shí)驗結(jié)果

實(shí)驗時，我們首先進(jìn)行基于依存搭配的查詢縮略，然后串聯(lián)地進(jìn)行基于詞語關(guān)聯(lián)度的子查詢選擇，其中所有的參數(shù)都是在開發(fā)集上調(diào)試獲得的經(jīng)驗最優(yōu)值。開發(fā)集是從騰訊公司提供的冗長查詢集中隨機(jī)選取并經(jīng)過人工標(biāo)注獲得的300條查詢。

我們從兩個方面展開實(shí)驗： 一是探索不同的搭配識別方法對查詢縮略的影響；二是與其他方法的對比，驗證方法的有效性。

4.3.1 搭配識別方法的影響

為了探索不同的搭配緊密度衡量方法對實(shí)驗結(jié)果的影響，我們比較了互信息、最大似然比和卡方分布對結(jié)果的影響，我們分別從“面向機(jī)器”和“面向用戶”兩個角度，對100條冗長查詢的縮略進(jìn)行評價，“面向機(jī)器”的結(jié)果如圖3所示，“面向用戶”的結(jié)果如表1所示。

圖3 不同緊密度衡量方法的影響(自動評價)

準(zhǔn)確率@1/%平均準(zhǔn)確率/%互信息最大似然比卡方分布互信息最大似然比卡方分布64.0065.0068.0052.3555.8956.47

圖3中，閾值(countThreshold)為搜索結(jié)果閾值，即當(dāng)搜索結(jié)果數(shù)量小于countThreshold時，我們更注重結(jié)果數(shù)的提升，當(dāng)大于閾值時，我們更注重檢索質(zhì)量(標(biāo)紅率)的提升。從實(shí)驗結(jié)果的比較可以看出，使用卡方分布作為衡量搭配緊密度的方法在“面向機(jī)器”的自動評價中，并沒有表現(xiàn)出優(yōu)勢，與基于互信息和最大似然比的方法相當(dāng)；但在“面向用戶”人工評價中，得到了比較好的效果。

4.3.2 對比實(shí)驗

作為參照，我們以利用大規(guī)模查詢?nèi)罩窘y(tǒng)計idf為詞權(quán)重的方法，作為Baseline。當(dāng)一個詞的idf小于某一閾值時，則認(rèn)為該詞不重要，將其刪除。分別在騰訊提供的冗長查詢上進(jìn)行測試，實(shí)驗結(jié)果如圖4和表2所示。

圖4 自動評測結(jié)果

準(zhǔn)確率@1/%平均準(zhǔn)確率/%BaselineOurMethodBaselineOurMethod52.0068.0044.1256.47

我們從騰訊公司提供的冗長查詢中，隨機(jī)抽取了1 063條查詢進(jìn)行自動評價，平均每條長尾查詢提供1.67條候選。隨機(jī)抽取100條冗長查詢進(jìn)行人工評價，比較縮略前后搜索引擎返回的前10條結(jié)果的質(zhì)量。通過人工查驗返回的相關(guān)結(jié)果集，來確定是否縮略后的相關(guān)結(jié)果更加切合用戶的查詢意圖。

從對照試驗可以看出，不同的搜索結(jié)果閾值表現(xiàn)出的結(jié)果波動并不是很明顯，但是在10 000左右，結(jié)果比較好，這可以看出縮略對于提高檢索結(jié)果的數(shù)量比較明顯。綜上，基于詞關(guān)聯(lián)度的縮略能夠返回更多“標(biāo)紅”率高的檢索結(jié)果，提升用戶的檢索體驗。在保證檢索數(shù)量的情況下，我們的方法能夠明顯提高冗長查詢的檢索質(zhì)量。

5 結(jié)論

本文提出了一種基于詞語關(guān)聯(lián)的查詢縮略的方法。結(jié)合依存句法和搭配識別，發(fā)現(xiàn)查詢中的語義蘊(yùn)含關(guān)系，刪除冗余詞；基于詞語關(guān)聯(lián)的子查詢選擇，發(fā)現(xiàn)信息量小的詞，將其刪除。為了驗證結(jié)果的有效性，我們提出了“面向機(jī)器”的自動評價方法和“面向用戶”的人工評價方法，從返回結(jié)果的數(shù)量和質(zhì)量兩個角度，對縮略的結(jié)果進(jìn)行評價。實(shí)驗結(jié)果表明，我們的方法能夠有效地剔除查詢中冗余的成份，提高檢索的數(shù)量和質(zhì)量。在下一步的工作中，我們將探索新方法發(fā)現(xiàn)更多依存搭配的頻繁模式，進(jìn)一步提高查詢縮略的效果。

[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.