聯邦搜索中基于詞向量的多樣化信息源選擇算法

王雅蓉 李亮 吳勝利

摘 要：對支持檢索結果多樣化任務的信息源選擇進行了研究。分析了現有研究的不足，提出利用詞向量提取文本的語義特征，在此基礎上實現文檔建模和信息源選擇。采用ClueWeb12b-13數據集構建實驗平臺和進行實驗，基于R方法的評價結果表明，所提出的方法優于現有的方法GLS和MnStD，且在不同條件下性能穩定。

關鍵詞：聯邦搜索；信息源選擇；檢索結果多樣化；詞向量

中圖分類號：TP391.3 文獻標識碼：A

文章編號：2096-1472（2018）-11-01-05

1 引言（Introduction）

聯邦搜索是一種信息檢索形式，主要用于檢索多個分布的、獨立性較高的信息源[1-3]。目前，一些大型的搜索引擎，如LinkedIn等，通過聯邦的方式來完成搜索任務。對于用戶提交的特定查詢，聯邦檢索系統分析各子檢索系統中的數據源，選擇一些相關文檔數目較多者，向那些選中的子檢索系統移交檢索請求，然后回收各子檢索系統的檢索結果并加以合并，最后將合并的結果返回給用戶[3，4]。聯邦搜索使得用戶通過統一的用戶界面同時訪問多個獨立的信息源，可用性較高。

檢索結果多樣化[5，6]是信息檢索的一項重要任務，其目的是使得結果列表中的文檔不僅與查詢相關，而且要求這些文檔覆蓋與查詢相關的各個方面。在大多數的檢索環境中，特別是對于查詢詞較少的短查詢，用戶的查詢意圖往往不夠清晰明確，不同的用戶對某一查詢項也可能存在不同的查詢需求。對于檢索結果進行多樣化處理可以更好地提升用戶的檢索體驗。

支持檢索結果多樣化任務的信息源選擇研究，要求選擇的信息源組合不僅與主查詢相關，而且需要與查詢的一個或多個子主題相關。即被選的數據源不僅要包含較多的相關文檔，而且要覆蓋盡可能多的查詢子主題。這要求算法不僅需要考慮數據源中文檔與查詢的相關性，也需要考慮各數據源之間文檔內容的冗余度和新穎性[7-9]。

對于那些支持信息檢索的結果多樣化算法，一般有兩種不同的假設。一種假設是：對于用戶的任何查詢，搜索引擎預先知道與該查詢相對應的所有子查詢的檢索意圖。另一種假設是搜索引擎無此信息。要使第一種假設成立，需要做大量的準備工作。尤其是對于一些即席查詢（Ad Hoc）而言，準備工作難度和工作量很大。根據假設的不同，結果多樣化算法分為顯式和隱式兩種。類似地，聯邦搜索中的多樣化數據源選擇算法一般也可以分為顯式和隱式兩種。作為一種顯式的信息源選擇算法，Hong和Si[9]提出了DivD和DivS。這兩者均將一種典型的顯式多樣化重排算法PM-2[5]用于聯邦搜索的信息源選擇中。該算法性能較佳。然而由于顯式方法本身依賴于子查詢信息，同時需要計算文檔集與所有子查詢的相關性，計算成本很高，因此這類方法的實際應用價值仍有待商榷。針對這個問題，隱式方法在不依賴額外子查詢信息的前提下，通過其他方法實現多樣化信息源選擇。作為一種隱式的信息源選擇算法，Naini等人提出了一種利用文檔分類來近似子查詢的GLS方法[7]。然而由于文檔集中不相關文檔的數量遠遠多于相關文檔的數量，因此文檔分類與子查詢之間的差異較大，導致算法多樣化性能不足。Benjamin和Wu[8]將投資組合理論應用于聯邦檢索中的信息源選擇，提出了MnStD方法。該方法的主要特點是通過在多樣化重排中加入風險因素，降低所選信息源之間的內容冗余度，提升所選信息源列表的新穎性，從而得到較優的多樣化信息源選擇結果。然而降低風險與多樣化性能也沒有直接的關系，因此算法性能并不出色。由此可見，如何在不依賴額外子查詢的條件下，實現多樣化性能較高的隱式信息源選擇算法是一項具有挑戰性的任務。

本文提出一種利用詞向量的隱式信息源選擇算法WbRS（Word representation-based Resource Selection for search result diversification）。在此基礎上，我們結合文本語義和詞項—詞頻統計兩方面的特征于文檔建模，這樣可以更準確地計算各信息源之間的內容相似度，進一步提高信息源選擇的性能。

2 詞向量（Distributed word representation）

詞向量，也被稱為詞編碼，是詞的分布式特征表述（Distributed Word Representation）[10，11]。它通過深度學習方法將單個詞項表示為m維語義空間中的一個向量。

Bengio[10]利用經典三層神經網絡構建n元語言模型，通過在廣泛的語料庫中訓練模型得到廣泛認可的詞向量，其模型如圖1所示。其中，表示一個詞序列的前n-1個詞。V表示語料庫中所有詞項構成的詞匯表，|V|表示這個詞匯表的大小，即詞項數量。m為語義空間的維度，即詞向量的維度，表示詞項的詞向量，是模型的輸入層。在整個模型中每個詞對應著唯一的1*m維的詞向量。模型通過已知的前n-1個詞，預測第n個詞出現的概率，這n-1個詞的詞向量組成矩陣。模型的隱藏層由偏置項d和激活函數組成。輸出層共有|V|個節點，每個結點的值表示詞序列中下一個詞為的概率，通過激活函數可以得到最終歸一化的概率值。因此，模型輸出層y的計算如式（1）所示。

其中，b為包含|V|個元素的輸出層偏置項。W表示從輸入層到輸出層直連邊的權重矩陣，當模型中不存在直連邊時，將W置為0。U表示從隱藏層到輸出層的權重矩陣，d為隱藏層偏置項，包含h個元素。H為隱藏層權重矩陣。最終通過隨機梯度下降法優化模型中的參數，得到詞匯表中各詞項的詞向量表示。研究表明[11，12]，詞項的這種向量表示可以較為準確地挖掘詞項語義，提取文本內容主題特征，本文將詞向量技術應用至聯邦檢索的信息源選擇中。

3 WbRS算法（Algorithm WbRS）

本節介紹基于詞向量的多樣化信息源選擇算法WbRS。用詞向量對文檔建模，得到文檔在語義層的相似度得分，將這個得分加入到文檔多樣化重排的計算中，最終得到多樣的信息源選擇結果。

WbRS算法第一部分是用詞向量技術訓練樣本相關文檔集，得到文檔內所有詞項的向量表示。樣本相關文檔集指的是，通過有效的檢索系統（如Indri[13]、terrier等）在樣本文檔集中對用戶查詢進行檢索，得到查詢的相關性文檔列表，中所有文檔組成的文檔集即為相關樣本文檔集。V表示這個文檔集的詞匯表。將作為語料庫，利用詞向量技術訓練，得到詞匯表V中各詞項在m維語義空間中的向量表示。V中各詞項的詞向量表示組成|V|*m維的矩陣W。

已有研究利用詞向量技術，在語料庫中訓練得到性能較優的詞項向量表示。其中，Mikolov和Chen等人[14]用循環神經網絡模型來訓練語言模型，提出并開源詞向量技術word2vec。Google利用word2vec在廣泛語料庫上訓練模型，得到并公開了詞向量表示。大量研究表明[12，15，16]，Google采用word2vec模型訓練得到的詞向量表示，在大部分性能評價指標中均取得較優的結果。這些詞向量表示可以準確地挖掘詞項語義[11，12]，直接將其應用至本算法，可以提升算法運行效率，同時保證較好的實驗性能。本文直接將Google通過word2vec技術訓練得到的詞向量表示應用至WbRS算法中。

算法的第二部分，利用word2vec技術得到的詞向量表示計算文檔相似度，并對樣本文檔相關性排序列表進行多樣化重排。首先，利用詞向量矩陣W實現文檔建模，得到各文檔的向量表示。然后，利用這些文檔向量計算文檔間的相似度。最后實現樣本文檔的多樣化重排。

本節擬采用簡潔高效的加權平均方法，根據算法第一部分中詞項在語義空間中的向量表示，將文檔表示為語義空間中的向量。已有研究證明[11，12]，用加權平均的方法處理文檔中的詞向量，具有較高的可行性。WbRS首先統計一篇文檔內所有詞項的出現頻率和文檔內的詞項數量，得到文檔的詞項-詞頻向量表示。另一方面，對照詞向量矩陣W，可以得到文檔內各個詞項的詞向量表示。并由這些詞向量組成文檔的詞向量矩陣。此時，文檔基于詞向量的向量表示，如式（2）所示。

其中，表示文檔中的詞項數量。因此文檔與的相似度計算可以用向量與的向量夾角余弦值表示。

本方法中是文檔內詞項-詞頻得到的文檔向量表示。為由word2vec得到的由文檔內各詞項在語義空間中的詞向量組成的映射矩陣。其中考察了傳統的詞項的詞頻特征，即文檔中出現頻率越高的詞項，對文檔內容越為重要。經過詞向量矩陣映射，將僅考慮詞頻的文檔向量，轉化為在m維語義空間中的文檔向量，通過可以分析文檔的語義相似度。

然而，式（2）中的是僅考慮詞頻的向量，忽略了語料庫中包含某詞項的文檔數，即反文檔頻率IDF。因而，對本節提出的式（2）做出進一步改進，采用TF-IDF加權的詞向量表示。

TF值表示文檔中詞項的出現頻率，是文檔中詞項、詞頻的歸一化度量，描述了詞項在文檔中的重要程度。TF的計算如式（3）。

其中，表示詞項t在文檔中的TF值，表示文檔中詞項t的出現頻數。式（3）中對詞項的出現頻率取對數，使得文檔中某些高頻詞匯和低頻詞匯的TF值更具有可比性。

文檔倒置頻率IDF，表示包含某詞項的文檔數量，它反映了文檔集中某詞項的重要性。因為包含詞項t的文檔越少，則表明這些文檔對詞項t越為重要。詞項t的文檔倒置頻率的經典計算如式（4）所示。

其中，N表示文檔集中的文檔總數，為包含詞項t的文檔數量。基于TF-IDF的文檔詞項向量可以表示為。

用替代式（2）中基于詞項-詞頻的文檔向量表示，可以得到文檔基于TF-IDF權重和詞向量的文檔向量表示。

文檔，相似度可以轉化為求解文檔對應向量與夾角的余弦值，文檔，在語義空間Φ中的相似度計算，如式（6）所示。

相似度計算，如式（6）所示。

其中，表示向量空間中在第t維語義空間中的特征。

結合文檔相似度和文檔的查詢相關度，WbRS方法用經典的貪心選擇策略，對樣本文檔相關性排序列表進行多樣化重排，得到多樣化的文檔排序列表。重排過程中，依次貪心地選擇使得目標函數得分最高的文檔，加入到已排序列表末尾，直到所有文檔被加入重排列表中。目標函數要求候選文檔與查詢保持足夠的相關性，同時要求與中的所有文檔的相似度最小，如式（7）所示。

其中，表示文檔與查詢項的相關度得分，為文檔在向量空間Φ中的內容相似度，為平衡參數。

與傳統的多樣化重排方法不同，WbRS方法在計算文檔相似度過程中，采用基于word2vec和TF-IDF權重的文檔向量得到較為準確的文檔內容相似度。這種方法結合了傳統的TF-IDF權重，綜合考慮了文檔中詞項的出現頻率和文檔倒排頻率，同時基于詞向量技術，將傳統的統計語言模型映射為語義空間中的文檔向量模型，因而可以提高重排列表的多樣化性能。算法中使用加權平均方法，由文檔中各詞項的詞向量計算得到文檔向量，方法簡潔高效且能取得較好的實驗性能。

算法第三部分通過樣本文檔多樣化排序列表，對信息源進行多樣化排名。列表中的各文檔在與查詢相關的同時，文檔之間存在足夠的差異度，這些文檔按照最優順序排列，構成了樣本文檔的多樣化列表。另一方面，由來自各信息源的樣本文檔組成，這些樣本相關文檔在對應的信息源中都存在著一些相似文檔與之對應。中文檔的多樣化排名，反映了各信息源整體的查詢相關性和內容新穎度。各信息源根據樣本文檔在中的排名，獲得不同的分值。并按照各信息源得分對它們進行排名，得到信息源的排名列表，這個得分由公式得到。Cormack等人[17]的研究表明，通過倒數模型，可以將文檔排名轉換為有效的文檔得分。

算法1（基于詞向量的多樣化信息源選擇算法WbRS）

輸入：查詢，中央樣本文檔集相關性排序列表，平衡參數，詞向量矩陣W，目標函數，計分函數G。

輸出：多樣化信息源結果列表R

/*第一部分，構建文檔向量空間模型Φ*/

1 用詞向量技術訓練中文檔，得到詞向量矩陣W

/*第二部分，執行文檔列表多樣化*/

2 for each do

3

4

5 end for

6

7 while || > 0 do

8 for each do

9

10 end for

11

12

13 end while

/*第三部分，信息源排序*/

14

15 for each do

16 for each and do

17

18 end for

19 end for

20 按s值從大到小順序為信息源排序，得到信息源多樣化排序

列表R

21 return R

算法中，表示詞項t在文檔中的TF權重，表示t的IDF權重。為文檔中的詞項數量。為維向量，表示中詞項的TF-IDF權重。為維矩陣，由中各詞項的詞向量表示組成。為1*m維向量，表示文檔在m維語義空間中的向量表示。為信息源的多樣化得分。為候選信息源數量。表示文檔d包含在信息源中。

4 實驗（Experiment）

4.1 數據集

本文實驗數據來自國際信息檢索會議（Text Retrieval Conference， TREC）在網絡檢索任務中提供的Clueweb12-B13英文數據集2。Clueweb12-B13數據集解壓縮后約為1.95T，包含52，343，021篇網頁。本文在ClueWeb12-B13上構建100個子檢索系統，這100個子檢索系統內包含了ClueWeb12-B13的全體文檔。本實驗首先在ClueWeb12-B13中隨機選取1%的網頁文本得到約52萬個網頁文檔，使用K-means算法對這些網頁文檔作簡單的文本聚類，迭代50次得到100個文本聚類中心，這100個聚類中心就對應著聯邦檢索系統的100個子系統。分別計算ClueWeb12-B13上的52，343，021篇文檔與這100個聚類中心的距離，為每篇文檔選擇與之最近的聚類中心，則該文檔被分配至這個聚類中心對應的子檢索系統中。重復這個過程，直至ClueWeb12-B13中的所有文檔都被分配完畢，得到最終的100個子檢索系統。最后，從各子檢索系統中，隨機選取1%的文檔作為各子檢索系統的樣本文檔，這100個子系統的樣本文檔構成中央樣本文檔集。這100個子檢索系統和樣本文檔集，共同構成本文的聯邦檢索實驗環境。表1給出了更多的統計數據。

本實驗選用了TREC Web Track 2013[18]和TREC Web Track 2014[19]中的100個查詢。

4.2 評價方法

經典的基于R多樣化評價方法[8，9]，是聯邦檢索信息源選擇應對檢索結果多樣化常用的評價標準。

其中，表示由算法選出的K個信息源構成的組合，M代表常用的檢索結果多樣化的評價標準，如：ERR-IA、nERR-IA、NRBP、nNRBP、α-nDCG、MAP-IA、P-IA等。

4.3 WbRS算法性能評估與分析

本節采用ReDDE+MMR[7，9]算法作為實驗基線，對比現有的隱式信息源選擇算法研究中最新的研究成果GLS[7]和MnStD[8]算法。設置信息源選擇數=3、5和10，分別考察信息源選擇數量較少，數量適中和數量較多，三種情形下算法的多樣化性能。采用R（ERR-IA@20）、R（nERR-IA@20）、R（α-nDCG@20）、R（NRBP）和R（nNRBP）作為評價標準，實驗對比結果分別如表2—表4所示。

從表2—表4中可以發現，在基于R評價方法的各種多樣化指標中，WbRS算法的實驗性能明顯優于ReDDE+MMR方法，多樣化性能較好。在R（ERR-IA@20），R（nERR-IA@20），R（α-nDCG@20），R（NRBP）和R（nNRBP）多項指標中，WbRS算法性能均表現最佳。其中，在R（ERR-IA@20）評價指標中，=3時，WbRS算法相較于GLS和MnStD算法，多樣化性能分別提升了10.9%和10.7%。=5時，WbRS算法相較于GLS和MnStD算法，多樣化性能分別提升了5.1%和5.1%。=10時，WbRS算法相較于GLS和MnStD算法，多樣化性能分別提升了10.1%和10.2%。在各項指標中，WbRS都有著較優的表現。實驗表明，基于詞向量和TF-IDF權重實現的信息源選擇算法WbRS，可以有效提高信息源選擇的多樣化性能。

4.4 WbRS算法的穩定性觀測與分析

本節對比不同信息源選擇數N_c時WbRS算法的性能，并分析算法的穩定性。設置N_c的范圍為{3，4，5，6，7，8，9，10}，圖2和圖3分別給出在R（MAP-IA@20）與R（P-IA@20）兩種評價指標中，WbRS、GLS和MnStD算法的性能對比。

從圖2和圖3可以發現，隨著N_c的增加，各種算法的R（MAP-IA@20）、R（P-IA@20）評價值均有明顯提升。這表明隨著信息源選擇數的增加，各種算法選擇的信息源組C_K均能覆蓋更多的查詢子主題。其中，WbRS算法的性能始終優于GLS和MnStD，這表明對于信息源選擇數的變化，WbRS算法均能保持較優的多樣化性能，算法性能相對穩定。

5 結論（Conclusion）

本文將自然語言處理的最新研究成果——詞向量技術應用至聯邦搜索中多樣化的信息源選擇研究中。提出了一種隱式的多樣化信息源選擇方法WbRS。實驗結果表明，與最新的隱式多樣化信息源選擇方法MnStD和GLS算法相比，WbRS算法能有效提高信息源選擇結果的多樣化性能，且算法性能較為穩定。

結果合并和結果顯示是聯邦檢索中另兩項重要的任務，也是我們下一步的工作。在結果合并任務中，我們繼續探討基于詞向量技術的方法。在結果顯示任務中，我們將探討層次化的多樣化文檔檢索結果顯示方法。

參考文獻（References）

[1] 楊海鋒，陸偉.聯邦檢索研究綜述[J].圖書情報工作，2015，59（1）：134-143.

[2] 耿騫，劉暢.分布式檢索系統及其體系結構[J].國家圖書館學刊，2004（2）：69-73.

[3] 萬常選，鄧松，劉喜平，等.Web數據源選擇技術[J].軟件學報，2013，24（4）：781-797.

[4] Shokouhi M，Si L.Federated Search[J].Foundations & Trends in Information Retrieval，2011，5（1）：1-102.

[5] Dang V，Croft W B.Diversity by proportionality：an election-based approach to search result diversification[C].International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2012：65-74.

[6] Markowitz H M.Foundations of Portfolio Theory[J].Journal of Finance，1991，46（2）：469-477.

[7] Naini K D，Siberski W，Siberski W.Scalable and Efficient Web Search Result Diversification[J].ACM Transactions on the Web，2016，10（3）：1-30.

[8] Benjamin Ghansah，Shengli Wu.A Mean-Variance Analysis Based Approach for Search Result Diversification in Federated Search[J].International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems，2016，24（02）：195-211.

[9] Hong D，Si L.Search result diversification in resource selection for federated search[C].International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2013：613-622.

[10] Bengio Y，Ducharme R，Vincent P，et al.A neural probabilistic language model[J].Journal of Machine Learning Research，2006，3（6）：1137-1155.

[11] Mnih A，Hinton G.A scalable hierarchical distributed language model[C].International Conference on Neural Information Processing Systems.Curran Associates Inc，2008：1081-1088.

[12] Kusner M J，Sun Y，Kolkin N I，et al.From word embeddings to document distances[C].International Conference on International Conference on Machine Learning.JMLR.org，2015：957-966.

[13] Metzler D，Croft W B.Combining the language model and inference network approaches to retrieval[J].Information Processing & Management，2004，40（5）：735-750.

[14] Mikolov T，Chen K，Corrado G，et al.Efficient Estimation of Word Representations in Vector Space.CoRR abs/1301.3781（2013）.

[15] Goldberg Y，Levy O.word2vec Explained：deriving Mikolov et al.negative-sampling word-embedding method[J].Eprint Arxiv，2014，9：1402-1407.

[16] Levy O，Goldberg Y.Neural word embedding as implicit matrix factorization[J].Advances in Neural Information Processing Systems，2014，3：2177-2185.

[17] Cormack G V，Clarke C L A，Buettcher S.Reciprocal rank fusion outperforms condorcet and individual rank learning methods[C].International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2009：758-759.

[18] Collins-Thompson K，Bennett P，Diaz F，et al.Overview of the TREC 2013 webtrack[C].TREC，2013.

[19] Collins-Thompson K，Macdonald C，Bennett P，et al.TREC 2014 web track overview[C].TREC，2014.

作者簡介：

王雅蓉（1994-），女，碩士生.研究領域：信息檢索.

李 亮（1994-），男，碩士生.研究領域：信息檢索.

吳勝利（1965-），男，博士，教授.研究領域：信息檢索.