融合知識(shí)圖譜的查詢擴(kuò)展模型及其穩(wěn)定性研究*

郝林雪，張 鵬，宋大為，候越先

天津大學(xué) 天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津 300350

融合知識(shí)圖譜的查詢擴(kuò)展模型及其穩(wěn)定性研究*

郝林雪，張 鵬+，宋大為，候越先

天津大學(xué) 天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津 300350

HAO Linxue,ZHANG Peng,SONG Dawei,et al.Research on knowledge graph based query expansion model and its retrieval stability.Journal of Frontiers of Computer Science and Technology,2017,11(1)：37-45.

知識(shí)圖譜；Freebase；查詢擴(kuò)展；有效性；穩(wěn)定性

1 引言

隨著大型結(jié)構(gòu)化語義知識(shí)圖譜的構(gòu)建，如Google的Knowledge Graph、微軟的Satori等，更多的商業(yè)搜索引擎開始將用戶查詢相關(guān)的知識(shí)體系和查詢文檔列表一并展示給用戶，以滿足用戶的信息需求和搜索體驗(yàn)。由于目前大部分Web數(shù)據(jù)仍以文本形式出現(xiàn)（如Web頁面、博客、微博等），如何利用知識(shí)圖譜中豐富的實(shí)體信息提升查詢文檔列表的質(zhì)量，也是信息檢索領(lǐng)域一個(gè)重要的研究方向[1]。

基于外部語料庫的查詢擴(kuò)展模型是一種提升檢索系統(tǒng)性能的有效途徑，其中常用的外部語料庫包括半結(jié)構(gòu)化的Wikipedia數(shù)據(jù)集，以及結(jié)構(gòu)化的Concept-Net和Freebase等知識(shí)圖譜。文獻(xiàn)[1-4]分別研究了Wikipedia、Concept-Net和Freebase等外部語料庫對查詢擴(kuò)展模型的影響。文獻(xiàn)[2]主要研究了如何基于Wikipedia實(shí)現(xiàn)查詢擴(kuò)展模型，其中用到了與偽相關(guān)反饋[5]相似的策略，即在Wikipedia中檢索查詢，將與排序靠前的N篇文檔看作與查詢相關(guān)，并將其作為擴(kuò)展詞來源。故這種擴(kuò)展方法和偽相關(guān)反饋模型有相同的不足，例如當(dāng)前N篇文檔中只有少數(shù)文檔與查詢真正相關(guān)時(shí)，基于這些文檔得到的擴(kuò)展模型反而會(huì)引入噪聲，造成查詢漂移，對檢索結(jié)果產(chǎn)生不利影響，從而降低檢索系統(tǒng)的性能[5-6]。與Wikipedia的半結(jié)構(gòu)化組織方式不同，Concept-Net和Freebase都是基于圖模型構(gòu)建的知識(shí)圖譜，其中頂點(diǎn)表示概念或?qū)嶓w，兩點(diǎn)之間的邊表示兩者之間的語義關(guān)系（如圖1所示）。與文獻(xiàn)[3]中用到的Concept-Net相比，F(xiàn)reebase包含更豐富的實(shí)體信息，如實(shí)體別名、細(xì)粒度的分類信息等，并且大部分Web查詢由實(shí)體（人名、地名等命名實(shí)體或者概念性實(shí)體）構(gòu)成，故本文選用Freebase作為外部擴(kuò)展詞來源。另外，基于外部語料庫構(gòu)建的查詢擴(kuò)展模型是一種全局的擴(kuò)展方法，不依賴于初始檢索結(jié)果，故Freebase作為查詢擴(kuò)展詞來源可在一定程度上穩(wěn)定檢索系統(tǒng)的性能，并減少類似于偽相關(guān)反饋給檢索系統(tǒng)帶來的不利影響[5-6]。文獻(xiàn)[1,4]也利用了Freebase進(jìn)行查詢擴(kuò)展模型的研究，但文獻(xiàn)[4]將查詢相關(guān)的實(shí)體處理成單個(gè)的擴(kuò)展詞，忽略了實(shí)體內(nèi)部各詞項(xiàng)之間的依賴關(guān)系。本文則將每個(gè)實(shí)體看作整體考慮，保留實(shí)體內(nèi)部依賴關(guān)系。與文獻(xiàn)[1]的不同之處在于，本文借鑒了文獻(xiàn)[7]提出的投資組合理論中收益-風(fēng)險(xiǎn)分析方法在信息檢索中的應(yīng)用，研究了如何降低基于知識(shí)圖譜的查詢擴(kuò)展模型給檢索系統(tǒng)帶來的查詢漂移（query-drift）風(fēng)險(xiǎn)。

Fig.1 What is inside Freebase？圖1 Freebase內(nèi)部結(jié)構(gòu)舉例

本文旨在研究基于Freebase的實(shí)體以及實(shí)體屬性信息構(gòu)建的查詢擴(kuò)展模型對檢索系統(tǒng)有效性及穩(wěn)定性的影響，所提出的擴(kuò)展模型主要包括以下三部分內(nèi)容：（1）從Freebase中自動(dòng)匹配與查詢相關(guān)實(shí)體和實(shí)體屬性；（2）利用收益-風(fēng)險(xiǎn)分析方法計(jì)算并優(yōu)化屬性擴(kuò)展詞的權(quán)重；（3）將這些外部擴(kuò)展信息與查詢語言模型結(jié)合，構(gòu)建一個(gè)性能相對穩(wěn)定的查詢擴(kuò)展模型。

本文的實(shí)驗(yàn)在兩個(gè)Web文檔集上進(jìn)行，主要分析了本文所提出的擴(kuò)展模型對檢索系統(tǒng)有效性和穩(wěn)定性的影響。實(shí)驗(yàn)結(jié)果表明，基于Freebase的查詢擴(kuò)展模型，與一元語言模型LM相比平均檢索性能有6%～15%的提升；與基于偽相關(guān)反饋的查詢擴(kuò)展模型RM3相比，有效性和穩(wěn)定性都有不同程度的提升。總體而言，本文提出的基于知識(shí)圖譜的查詢擴(kuò)展模型在兩個(gè)測試數(shù)據(jù)集上整體性能更優(yōu)。

2 模型描述

2.1 外部擴(kuò)展詞初始權(quán)重計(jì)算

給定一個(gè)用戶查詢Q，本文使用相鄰查詢詞組成的子查詢匹配實(shí)體信息[8]，原因是相鄰查詢詞之間存在依賴關(guān)系且包含上下文信息，匹配到的實(shí)體和用戶信息需求更相關(guān)[4]。由于Freebase中實(shí)體之間，實(shí)體與自身屬性之間均是以圖結(jié)構(gòu)存儲(chǔ)的，以某個(gè)實(shí)體（圖中的一個(gè)頂點(diǎn)）為起點(diǎn)，廣度遍歷即可得到與該實(shí)體的屬性信息。本文將這些相關(guān)實(shí)體以及實(shí)體屬性作為查詢的外部特征，并計(jì)算其與查詢的相關(guān)性。在計(jì)算實(shí)體與查詢相關(guān)性時(shí)，考慮了兩種因素的影響：一是子查詢Qs相對于查詢Q的重要性，由兩者所包含詞項(xiàng)數(shù)目的比值來定義；二是子查詢與實(shí)體En的匹配得分rel(En,Qs)（由Freebase API[8]給出）。則實(shí)體En與查詢Q的相關(guān)性得分定義為：

由于Freebase中較為完整地記錄了實(shí)體的屬性信息，但有的屬性信息對本文的查詢擴(kuò)展任務(wù)沒有使用價(jià)值，為了減少噪聲詞的引入，本文只考慮一些常見屬性，如實(shí)體別名、類別、所屬領(lǐng)域等進(jìn)行查詢擴(kuò)展。將遍歷得到屬性信息處理成獨(dú)立詞項(xiàng)分布，每個(gè)屬性詞與查詢的相似性得分定義如下：

式（2）對屬性詞權(quán)重的計(jì)算也考慮了兩方面的因素：一是屬性詞所屬的實(shí)體相對于查詢的權(quán)重；二是屬性詞與查詢本身的相關(guān)性。在計(jì)算時(shí)考慮了屬性詞與各查詢詞的相關(guān)性。在式（2）中，idfq為查詢詞q的逆文檔概率，代表其在查詢中的重要性；cfep表示屬性詞ep在文檔集中出現(xiàn)的次數(shù)；cf#uwN(ep,q)表示屬性詞ep和q共現(xiàn)在一個(gè)大小為N的窗口中的次數(shù)（本文取N為20）。

2.2 基于收益-風(fēng)險(xiǎn)分析方法優(yōu)化屬性詞權(quán)重

利用式（2）計(jì)算外部擴(kuò)展詞初始權(quán)重時(shí)，只考慮了擴(kuò)展詞與查詢的相關(guān)性，并假設(shè)擴(kuò)展詞之間相互獨(dú)立，這樣存在的問題是按照初始權(quán)重排序靠前的擴(kuò)展詞可能只與某些查詢詞相關(guān)，擴(kuò)展后的檢索結(jié)果向這些查詢詞偏移，從而偏離用戶的信息需求。本文參考文獻(xiàn)[7]提出的投資組合理論中收益-風(fēng)險(xiǎn)分析方法在文檔排序上的應(yīng)用，將整個(gè)擴(kuò)展詞列表看成一個(gè)整體，然后將外部擴(kuò)展詞權(quán)重優(yōu)化問題建模成投資組合問題來求解。該優(yōu)化問題中的“投資收益”，是指擴(kuò)展詞與查詢的相關(guān)性大小，相關(guān)性越大，表示收益越大。“投資風(fēng)險(xiǎn)”來源有兩種：一是每個(gè)擴(kuò)展詞可能帶來的查詢擴(kuò)展失敗的風(fēng)險(xiǎn)，即相關(guān)性收益的不確定性；二是考慮擴(kuò)展詞之間的相互影響，在同時(shí)選取這些擴(kuò)展詞可能帶來的冗余性風(fēng)險(xiǎn)[9]。

該擴(kuò)展詞權(quán)重優(yōu)化模型可描述如下：設(shè)屬性擴(kuò)展詞列表中所有擴(kuò)展詞的權(quán)重為隨機(jī)向量(r1,r2,…,rn)，其中每個(gè)變量的均值為E(ri)，即期望收益，由式（2）給出的相似性得分sim(epi,Q)為ri的一個(gè)估計(jì)值。該隨機(jī)向量對應(yīng)的協(xié)方差矩陣記為C，由于各隨機(jī)變量之間不獨(dú)立，C中的非對角元素cij表示擴(kuò)展詞權(quán)重ri和rj的協(xié)方差，由第二種風(fēng)險(xiǎn)來源產(chǎn)生，可解釋為在epi為擴(kuò)展詞的條件下，再選取epj作為擴(kuò)展詞的冗余性風(fēng)險(xiǎn)；C的對角元素cii代表第一種風(fēng)險(xiǎn)來源。本文參考文獻(xiàn)[9]，將協(xié)方差矩陣C中的元素用式（3）或式（4）來估計(jì)：

其中，η為歸一化因子；σ(epi,epj)表示兩個(gè)擴(kuò)展詞之間的相似性，本文用Jaccard相似性系數(shù)來計(jì)算。每個(gè)擴(kuò)展詞權(quán)重的方差cii則用其與所有查詢詞的相似度之和定義。

基于以上對擴(kuò)展詞期望收益以及協(xié)方差矩陣的說明，本文定義外部擴(kuò)展詞列表的相關(guān)性收益E(Rn)為所有擴(kuò)展詞收益的加權(quán)平均（如式（5）所示）。wi表示每個(gè)擴(kuò)展詞對總收益所貢獻(xiàn)的比重，其中wi=1 2i-1，表示與查詢Q相似性得分sim(epi,Q)排在第i位的屬性擴(kuò)展詞為總收益所貢獻(xiàn)的。式（5）中的Var(Rn)定義為擴(kuò)展詞列表中所有擴(kuò)展詞的協(xié)方差之和，表示該擴(kuò)展詞列表用來做查詢擴(kuò)展時(shí)檢索性能存在的風(fēng)險(xiǎn)。

該優(yōu)化模型的目標(biāo)為最大化期望收益E(Rn)，最小化方差Var(Rn)，即最大化函數(shù)為On=E(Rn)-bVar(Rn)，其中b為風(fēng)險(xiǎn)偏好參數(shù)，b＞0表示規(guī)避風(fēng)險(xiǎn)，本文取b=0.05。在優(yōu)化模型實(shí)現(xiàn)過程中，本文借鑒了文獻(xiàn)[7]的序列最大化文檔排序得分收益的方法，并對其進(jìn)行了適當(dāng)?shù)母倪M(jìn)，得到了序列最優(yōu)化擴(kuò)展詞權(quán)重收益的算法，具體優(yōu)化步驟如下：

（1）按照式（2）計(jì)算出的屬性詞初始權(quán)重，選取權(quán)重較大的n個(gè)擴(kuò)展詞組成候選擴(kuò)展詞集合E；并設(shè)已選擴(kuò)展詞集合為S，初始狀態(tài)為空。

（2）將E中權(quán)重最大的擴(kuò)展詞加入S，并將其從E中刪除。

（3）將E中其余的擴(kuò)展詞依次加入集合S，第k個(gè)加入S的擴(kuò)展詞滿足如下條件，該擴(kuò)展詞加入S可以使目標(biāo)函數(shù)的增量最大，即選取一個(gè)擴(kuò)展詞使式（7）最大化。式（7）的值也作為擴(kuò)展詞優(yōu)化后的權(quán)重，記為sim′(epk,Q)。

用以上權(quán)重優(yōu)化模型得到的擴(kuò)展詞既考慮了擴(kuò)展詞與查詢的相關(guān)性，又考慮了降低擴(kuò)展詞之間的冗余以及查詢擴(kuò)展失敗的風(fēng)險(xiǎn)。

2.3 外部擴(kuò)展詞與查詢語言模型的結(jié)合

基于Freebase得到的與查詢相關(guān)的擴(kuò)展實(shí)體及實(shí)體屬性詞兩種加權(quán)特征，可作為影響文檔與查詢相關(guān)性得分的因素整合到文檔排序函數(shù)中：

式（8）由三部分組成：第一部分表示原始查詢Q與文檔D的相似性得分；第二部分表示查詢相關(guān)的實(shí)體EQ與文檔D的相似性得分；最后一部分則表示實(shí)體屬性詞集合EP與文檔D的相似性得分。sim′(ep,Q)即為基于式（7）優(yōu)化后的屬性擴(kuò)展詞與查詢Q的相似性得分。參數(shù)λq、λEn和λep用來調(diào)節(jié)三部分特征在排序函數(shù)的權(quán)重，且三者和為1。表達(dá)式φori(q,D)用來估計(jì)查詢詞q在文檔D對應(yīng)的語言模型中的生成概率，該表達(dá)式的計(jì)算如下：

其中，tfq,D和cfq表示查詢詞q在文檔D以及文檔集C中的詞頻；|D|表示文檔D的長度；|C|表示文檔集C的詞項(xiàng)總數(shù)；β表示用文檔集平滑該生成概率的平滑系數(shù)。表達(dá)式φEn(En,D)和φep(ep,D)的計(jì)算參照式（9）。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

本文在兩個(gè)TREC標(biāo)準(zhǔn)數(shù)據(jù)集WT10G和Clue-Web12B上對所提出的基于知識(shí)圖譜的查詢擴(kuò)展模型進(jìn)行了實(shí)驗(yàn)。兩個(gè)數(shù)據(jù)集的基本情況如表1所示，并且兩個(gè)數(shù)據(jù)集都由Web頁面組成，文檔內(nèi)容以及文檔長度區(qū)別較大，屬于異構(gòu)類型的數(shù)據(jù)集。實(shí)驗(yàn)所用到的查詢?yōu)門REC提供的測試topics的title部分，該部分一般用查詢關(guān)鍵詞來描述，更符合Web用戶的查詢習(xí)慣。

Table 1 Statistics of two TREC test collections表1 兩個(gè)TREC測試數(shù)據(jù)集的統(tǒng)計(jì)信息

本文采用了3種策略來驗(yàn)證基于Freebase的外部擴(kuò)展信息的有效性：（1）取權(quán)值最大的NEn個(gè)相關(guān)實(shí)體構(gòu)建查詢擴(kuò)展模型（對應(yīng)擴(kuò)展模型記為KF-En）；（2）取權(quán)值最大的Nep個(gè)實(shí)體屬性詞進(jìn)行擴(kuò)展（對應(yīng)模型記為KF-EP）；（3）綜合考慮實(shí)體和實(shí)體屬性的影響（對應(yīng)模型記為KF-En-EP）。

用一元語言模型LM和基于偽相關(guān)反饋的查詢擴(kuò)展模型RM3[10]進(jìn)行了對比實(shí)驗(yàn)。實(shí)驗(yàn)中所有模型都是基于Indri[11]的語言模型框架實(shí)現(xiàn)的，文檔集中所有文檔和查詢均按以下方式進(jìn)行預(yù)處理：根據(jù)標(biāo)準(zhǔn)的停用詞表去除停用詞，然后用Porter Stemmer算法提取詞干。

在RM3模型實(shí)現(xiàn)過程中，有3個(gè)重要的參數(shù)需要調(diào)整，即初次檢索返回的前K(5≤K≤10)篇文檔，擴(kuò)展詞個(gè)數(shù)N(10≤N≤100)，以及擴(kuò)展詞與原始查詢的插值系數(shù)λ(0≤λ≤1)。在每個(gè)數(shù)據(jù)集上，3個(gè)參數(shù)分別以步長5、10、0.1進(jìn)行逐步調(diào)整，直至找到平均準(zhǔn)確率（mean average precision，MAP）最優(yōu)的參數(shù)設(shè)置。在調(diào)整本文提出的3種基于Freebase的擴(kuò)展模型的參數(shù)時(shí)，采用了與RM3模型類似的調(diào)參方法。KF-En模型包含兩個(gè)參數(shù)，外部擴(kuò)展實(shí)體的個(gè)數(shù)NEn(1≤NEn≤5)以及擴(kuò)展實(shí)體與原始查詢的插值系數(shù)λEn(0≤λEn≤1)，兩個(gè)參數(shù)的調(diào)整步長分別為1、0.1；KFEP模型中也包含兩個(gè)參數(shù)，外部屬性詞個(gè)數(shù)NEP(5≤NEP≤50)及其與原始查詢的插值系數(shù)λEP(0≤λEP≤1)，兩個(gè)參數(shù)的調(diào)整步長分別為5、0.1。鑒于4個(gè)參數(shù)NEn、λEn、NEP和λEP同時(shí)在模型KF-En-EP中出現(xiàn)，參數(shù)調(diào)整策略參考模型KF-En和KF-EP。

3.2 評價(jià)指標(biāo)

本文采用了基于檢索返回的前1 000文檔平均準(zhǔn)確率（MAP）作為模型有效性的評價(jià)指標(biāo)，MAP也是TREC最為常規(guī)的檢索模型評價(jià)指標(biāo)。由于兩個(gè)測試數(shù)據(jù)集均為Web文檔集，本文也用了TREC Web Track任務(wù)評價(jià)時(shí)常用的NDCG@20和ERR@20兩個(gè)評價(jià)指標(biāo)來評價(jià)模型的有效性。

在評價(jià)模型穩(wěn)定性時(shí)，本文選用了文獻(xiàn)[12]提出的Urisk評價(jià)方法，2013 TREC Web Track任務(wù)將該指標(biāo)作為模型穩(wěn)定性評價(jià)的重要參考指標(biāo)[13]。該評價(jià)指標(biāo)在使用時(shí)，需要有一個(gè)基準(zhǔn)模型作為參照，本文選擇LM作為基準(zhǔn)模型，Urisk定義如下：

其中，|Q|表示查詢個(gè)數(shù)；Q+表示與基準(zhǔn)模型相比，檢索性能提升的查詢集合；Q-表示與基準(zhǔn)模型相比，檢索性能降低的查詢集合。Δq表示待測模型與基準(zhǔn)模型之間的性能差值，對于Q+集合中的查詢，Δq＞0；對于Q-集合中的查詢，Δq＜0。α是對性能下降的查詢的懲罰系數(shù)，α值越大，懲罰力度越大，本文實(shí)驗(yàn)中設(shè)置α=10。由式（10）可以看出，Urisk越大表示模型越穩(wěn)定。

另外，本文也采用文獻(xiàn)[14-15]提出的一種基于偏差方差分解的評價(jià)方法評價(jià)了所提出的擴(kuò)展模型的整體性能。若用平均有效性AP作為單個(gè)查詢的檢索有效性評價(jià)指標(biāo)，該評價(jià)方法可用以下公式定義：

其中，APT表示單個(gè)查詢的最優(yōu)性能，本文取APT=1。式（11）表示待評價(jià)模型的AP與最優(yōu)值A(chǔ)PT的期望平方誤差，該誤差項(xiàng)可以分解為偏差方差兩部分：偏差Bias2(AP)可用來評價(jià)模型有效性，偏差越小表示模型越有效；方差Var(AP)可用來評價(jià)模型的穩(wěn)定性，方差越小模型越穩(wěn)定，故該評價(jià)指標(biāo)的值越小，模型整體性能越好。

3.3 實(shí)驗(yàn)結(jié)果分析

表2給出了KF-En、KF-EP、KF-En-EP擴(kuò)展模型，以及基準(zhǔn)模型LM和對比模型RM3在兩個(gè)測試數(shù)據(jù)集上的評價(jià)結(jié)果。在每個(gè)數(shù)據(jù)集上，性能表現(xiàn)最優(yōu)的模型用粗體標(biāo)出，4種擴(kuò)展模型MAP提高的百分比均是相對于基準(zhǔn)模型LM而言的。

由表2的實(shí)驗(yàn)結(jié)果可知，本文提出的3種基于知識(shí)圖譜的查詢擴(kuò)展模型在兩個(gè)測試數(shù)據(jù)集上MAP有6%～15%不等的提升。而相比之下，常用的查詢擴(kuò)展模型RM3在兩個(gè)數(shù)據(jù)集上的檢索效果不如本文提出的擴(kuò)展模型，且在ClueWeb12B上性能有所下降。出現(xiàn)該現(xiàn)象的原因是ClueWeb12B的初始檢索結(jié)果中排在前面的K篇文檔與查詢相關(guān)的很少（LM的MAP較低），從中提取的擴(kuò)展詞造成了查詢偏移，從而使檢索性能下降，而基于外部知識(shí)圖譜的查詢擴(kuò)展模型則不會(huì)受到初始檢索結(jié)果的影響。另外，表2也表明本文提出的3種擴(kuò)展模型的檢索性能之間也存在差異，KF-En的檢索性能均低于另外兩個(gè)模型，原因是與查詢最為相關(guān)的實(shí)體個(gè)數(shù)較少，從而無法很好地?cái)U(kuò)展查詢來更好地表達(dá)用戶的信息需求。而基于實(shí)體屬性詞的擴(kuò)展模型則充分挖掘了Freebase中與查詢相關(guān)的實(shí)體屬性，故檢索性能提升更為顯著。

Table 2 Average performance of 5 retrieval models on two test collections表2 5個(gè)模型在兩個(gè)數(shù)據(jù)集上的平均性能比較

在分析了本文提出的擴(kuò)展模型有效性相比基準(zhǔn)模型和RM3有所提升之后，接著主要分析了擴(kuò)展模型對檢索系統(tǒng)穩(wěn)定性的影響。表3列出了模型的穩(wěn)定性評價(jià)指標(biāo)Urisk以及總體性能評價(jià)指標(biāo)Bias2+Var在各個(gè)模型上的評價(jià)結(jié)果。Urisk列中最大值用粗體標(biāo)出，表示該模型最穩(wěn)定，Bias2+Var列中最小值用粗體標(biāo)出，表示該模型的整體性能最優(yōu)。由表3可知，本文提出的3個(gè)擴(kuò)展模型均表現(xiàn)得比RM3穩(wěn)定，并且提升了檢索系統(tǒng)的有效性。

Table 3 Comparison of model stability and overall performance表3 模型的穩(wěn)定性以及總體性能的比較

最后，本文主要分析了查詢相關(guān)的實(shí)體及屬性信息能夠提高檢索系統(tǒng)穩(wěn)定性的原因。將數(shù)據(jù)集WT10G和ClueWeb12B對應(yīng)的查詢按難度大小分成5組，查詢的難度參考了LM模型在該查詢上的平均準(zhǔn)確率AP，AP越小表示查詢越難。如圖2所示，查詢難度從左至右依次降低，最左側(cè)的直方圖“0%～20%”表示最難的查詢分組上的MAP值，最右側(cè)的柱狀圖“80%～100%”表示最容易的查詢分組上的MAP值。由圖2（a）可知，對于數(shù)據(jù)集WT10G，在最難的查詢分組“0%～20%”上，本文提出的3個(gè)擴(kuò)展模型MAP值稍微高于LM和RM3；在較難的查詢分組“20%～40%”上，KF-En和KF-En-EP的MAP值顯著高于LM和RM3；在難度適中的查詢分組“40%～60%”以及“60%～80%”上，KF-En-EP的MAP值高于其他模型，而KFEn和KF-EP的檢索效果與RM3相似；在最容易的查詢分組“80%～100%”上，RM3檢索結(jié)果最優(yōu)。由圖2（b）可知，對于數(shù)據(jù)集ClueWeb12B來說，在前3個(gè)較難的查詢分組上模型KF-En和KF-En-EP的MAP值高于其他模型；在較簡單的查詢分組“60%～80%”上，KF-En、KF-EP和KF-En-EP的性能均優(yōu)于LM和RM3；而在最簡單的查詢分組“80%～100%”上，KFEn-EP則表現(xiàn)得優(yōu)于其他模型。綜上對不同難度查詢分組的分析可知，基于知識(shí)圖譜的查詢擴(kuò)展模型不僅有利于提升難查詢的檢索性能，又能減少噪聲詞的引入來保證簡單查詢的檢索性能不被降低，故可以同時(shí)提高檢索系統(tǒng)的有效性和穩(wěn)定性。

Fig.2 MAPof different query subsets on WT10G and ClueWeb12B圖2 數(shù)據(jù)集WT10G和ClueWeb12B上不同難度的查詢分組平均性能

4 結(jié)束語

本文提出了一種基于知識(shí)圖譜的查詢擴(kuò)展模型，該模型主要解決了自動(dòng)匹配與查詢相關(guān)的實(shí)體以及實(shí)體屬性，并利用收益-風(fēng)險(xiǎn)分析方法計(jì)算并優(yōu)化實(shí)體屬性詞的權(quán)重。該方法既考慮了最大化整個(gè)屬性詞列表與查詢的相關(guān)性收益，又兼顧了最小化該屬性詞列表可能帶來的查詢擴(kuò)展失敗的風(fēng)險(xiǎn)。最后將這些外部特征與查詢語言模型結(jié)合構(gòu)建性能更加穩(wěn)定的查詢擴(kuò)展模型。本文實(shí)驗(yàn)在兩個(gè)Web數(shù)據(jù)集上進(jìn)行，實(shí)驗(yàn)結(jié)果表明，本文提出的擴(kuò)展模型與基準(zhǔn)模型LM以及常用擴(kuò)展模型RM3相比，檢索有效性有顯著提升；模型穩(wěn)定性在兩個(gè)數(shù)據(jù)集上都優(yōu)于RM3模型；最后通過對不同難度查詢分組的分析可知，本文提出的查詢擴(kuò)展模型對難查詢檢索性能的提升顯著，對簡單查詢的檢索性能影響較小，故可以使檢索系統(tǒng)更加穩(wěn)定。

未來的研究工作主要包括：（1）本文的研究集中在探索Freebase對檢索模型有效性和穩(wěn)定性的影響，后續(xù)工作擬在其他外部語料庫上驗(yàn)證外部知識(shí)對查詢擴(kuò)展的有效性；（2）本文在計(jì)算實(shí)體與查詢的相似度時(shí)，只考慮到了查詢本身，而用戶查詢一般以少量的關(guān)鍵詞表示，可用的上下文信息較少，下一步工作將考慮融合查詢在文檔中的上下文信息來更準(zhǔn)確地估計(jì)實(shí)體與查詢的相似度。

[1]Dalton J,Dietz L,Allan J.Entity query feature expansion using knowledge base links[C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval,Gold Coast,Queensland,Australia,Jul 6-11,2014.New York:ACM,2014:365-374.

[2]Xu Yang,Jones G J F,Wang Bin.Query dependent pseudorelevance feedback based on Wikipedia[C]//Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval,Boston,USA, Jul 19-23,2009.New York:ACM,2009:59-66.

[3]Kotov A,Zhai Chengxiang.Tapping into knowledge base for concept feedback:leveraging concept net to improve search results for difficult queries[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining,Seattle,USA,Feb 8-12,2012.New York:ACM, 2012:403-412.

[4]Pan Dazhao,Zhang Peng,Li Jingfei,et al.Using Dempster-Shafer's evidence theory for query expansion based on freebase knowledge[C]//LNCS 8281:Proceedings of the 9th Asia Information Retrieval Societies Conference,Singapore,Dec 9-11,2013.Berlin,Heidelberg:Springer,2013: 121-132.

[5]Amati G,Carpineto C,Romano G.Query difficulty,robustness,and selective application of query expansion[C]//LNCS 2997:Proceedings of the 26th European Conference on Information Retrieval,Sunderland,UK,Apr 5-7,2004.Ber-lin,Heidelberg:Springer,2004:127-137.

[6]Collins-Thompson K,Callan J.Estimation and use of uncertainty in pseudo-relevance feedback[C]//Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Amsterdam,The Netherlands,Jul 23-27,2007.New York:ACM, 2007:303-310.

[7]Wang Jun,Zhu Jianhan.Portfolio theory of information retrieval[C]//Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval,Boston,USA,Jul 19-23,2009.New York:ACM, 2009:115-122.

[8]Bollacker K,Evans C,Paritosh P,et al.Freebase:a collaboratively created graph database for structuring human knowledge[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,Vancouver,Canada,Jun 10-12,2008.New York:ACM,2008:1247-1250.

[9]Collins-Thompson K.Estimating robust query models with convex optimization[C]//Advances in Neural Information Processing Systems 21:Proceedings of the 22nd Annual Conference on Neural Information Processing Systems,Vancouver,Canada,Dec 8-11,2008:329-336.

[10]Zhai Chengxiang,Lafferty J.Model-based feedback in the language modeling approach to information retrieval[C]// Proceedings of the 10th International Conference on Information and Knowledge Management,Atlanta,USA,Nov 5-10,2001.New York:ACM,2001:403-410.

[11]Strohman T,Metzler D,Turtle H,et al.Indri:a languagemodel based search engine for complex queries[R].University of Massachusetts Amherst,Center for Intelligence Information Retrieval.

[12]Wang Lidan,Bennett P N,Collins-Thompson K.Robust ranking models via risk-sensitive optimization[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval,Portland,USA,Aug 12-16,2012.NewYork:ACM,2012:761-770. [13]Collins-Thompson K,Bennett P,Diaz F,et al.TREC 2013 Web track guidelines[EB/OL].(2013)[2015-09-28].http:// research.microsoft.com/en-us/projects/trec-web-2013.

[14]Zhang Peng,Song Dawei,Wang Jun,et al.Bias-variance decomposition of IR evaluation[C]//Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval,Dublin,Ireland, Jul 28-Aug 1,2013.New York:ACM,2013:1021-1024.

[15]Zhang Peng,Hao Linxue,Song Dawei,et al.Generalized bias-variance evaluation of TREC participated systems[C]// Proceedings of the 23rd ACM International Conference on Information and Knowledge Management,Shanghai,China, Nov 3-7,2014.New York:ACM,2014:1911-1914.

HAO Linxue was born in 1990.She is an M.S.candidate at Tianjin University.Her research interests include query expansion,information retrieval risk,knowledge base mining and model evaluation,etc.

郝林雪（1990—），女，河南南陽人，天津大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)椴樵償U(kuò)展，信息檢索模型風(fēng)險(xiǎn)研究，知識(shí)庫挖掘，模型評價(jià)方法設(shè)計(jì)等。

ZHANG Peng was born in 1983.He received the Ph.D.degree from Robert Gordon University in 2013.Now he is a lecturer and M.S.supervisor at Tianjin University,and the member of CCF.His research interests include information retrieval,quantum cognitive computing and machine learning,etc.He has published more than 20 papers including journal papers and conference papers.

張鵬（1983—），男，山西高平人，2013年于英國羅伯特戈登大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計(jì)算機(jī)學(xué)院講師、碩士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)樾畔z索，量子認(rèn)知計(jì)算，機(jī)器學(xué)習(xí)等。發(fā)表20余篇期刊及會(huì)議論文，主持1項(xiàng)國家自然科學(xué)基金和1項(xiàng)教育部博士點(diǎn)新教師類基金。

SONG Dawei was born in 1972.He received the Ph.D.degree from Chinese University of Hong Kong in 2000. Now he is a professor and Ph.D.supervisor at Tianjin University,and the member of CCF.His research interests include theory and formal models for context-sensitive information retrieval,multimedia and social media information retrieval,domain-specific information retrieval,user behavior,interaction and cognition in information seeking, text mining and knowledge discovery,etc.He has published more than 100 papers including many top tier international journal papers and conference papers.

宋大為（1972—），男，河北滄州人，2000年于香港中文大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計(jì)算機(jī)學(xué)院教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)樾畔z索理論與模型，多媒體與社會(huì)媒體信息檢索，特定領(lǐng)域信息檢索，信息檢索用戶交互與認(rèn)知，文本挖掘與知識(shí)發(fā)現(xiàn)等。發(fā)表學(xué)術(shù)論文百余篇，主持英國國家工程和物理科學(xué)研究基金委員會(huì)基金項(xiàng)目4項(xiàng)，參與國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973）2項(xiàng)，主持國家自然科學(xué)基金項(xiàng)目1項(xiàng)。

HOU Yuexian was born in 1972.He received the Ph.D.degree from Tianjin University in 2001.Now he is a professor and Ph.D.supervisor at Tianjin University,the director of the Institute of Computational Intelligence and Internet Application,Tianjin University,and the senior member of CCF.His research interests include machine learning, information retrieval and natural language processing,etc.He has published more than 50 papers on main international conferences and journals.

候越先（1972—），男，天津人，2001年于天津大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師，天津大學(xué)網(wǎng)絡(luò)智能信息技術(shù)研究所主任，中國中文信息處理學(xué)會(huì)理事，CCF高級會(huì)員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，信息檢索，自然語言處理等。近年來在主要國際學(xué)術(shù)期刊和會(huì)議上發(fā)表學(xué)術(shù)論文50余篇。

Research on Knowledge Graph Based Query Expansion Model and Its Retrieval Stability*

HAO Linxue,ZHANG Peng+,SONG Dawei,HOU Yuexian
Tianjin Key Laboratory of Cognitive Computing andApplication,Tianjin University,Tianjin 300350,China
+Corresponding author:E-mail:pzhang@tju.edu.cn

This paper aims to construct a query expansion model based on query-related entities and their properties in Freebase,which are used to reconstruct the query for better expressing the user's needs.The relevance score between each property term and the query is measured by the risk-reward analysis in portfolio theory,which is expected to maximize the reward of the relevance scores of property terms and minimize the risk of query expansion failure using these property terms.This paper also proposes a method to integrate these entities and associated properties into the language modeling framework for query expansion.In the experiments,the retrieval effectiveness and stability of the query expansion model solely based on Freebase are evaluated on two Web collections,in comparison with the baseline language model LM and the traditional query expansion model based on pseudo relevance feedback RM3.The experimental results show that the expansion model proposed in this paper outperforms baseline LM by 6%～15%in MAP(mean average precision),and it also performs more effectively and stably than RM3.

knowledge graph;Freebase;query expansion;effectiveness;stability

A

：TP391.3

10.3778/j.issn.1673-9418.1511043

*The National Natural Science Foundation of China under Grant Nos.61402324,61272265(國家自然科學(xué)基金);the National Basic Research Program of China under Grant Nos.2013CB329304,2014CB744604(國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃));the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20130032120044(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金).

Received 2015-10,Accepted 2015-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-12-03,http://www.cnki.net/kcms/detail/11.5602.TP.20151203.1407.006.html

摘 要：旨在構(gòu)建一種基于知識(shí)圖譜Freebase的查詢擴(kuò)展模型，通過從Freebase中抽取與查詢相關(guān)的若干實(shí)體及實(shí)體屬性作為擴(kuò)展詞來重構(gòu)查詢，從而更好地表達(dá)用戶的信息需求。在計(jì)算擴(kuò)展詞權(quán)重時(shí)，參考了投資組合理論中收益-風(fēng)險(xiǎn)分析方法，最大化擴(kuò)展詞和查詢的相關(guān)性收益，同時(shí)也最小化擴(kuò)展詞可能帶來的查詢漂移的風(fēng)險(xiǎn)。最后將查詢相關(guān)的實(shí)體和實(shí)體屬性作為兩種特征和查詢語言模型結(jié)合實(shí)現(xiàn)查詢擴(kuò)展。在兩個(gè)Web數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，用來檢驗(yàn)所提出的擴(kuò)展模型對檢索系統(tǒng)的有效性和穩(wěn)定性的影響。實(shí)驗(yàn)結(jié)果表明，提出的查詢擴(kuò)展模型與一元語言模型LM相比，檢索結(jié)果的平均準(zhǔn)確率（mean average precision，MAP）在兩個(gè)數(shù)據(jù)集上有6%至15%的顯著提升；和基于偽相關(guān)反饋的查詢擴(kuò)展模型RM3相比，有效性及穩(wěn)定性都有不同程度的提升。