多層克隆選擇的排序?qū)W習(xí)方法研究

武宇婷，張子旸，田玉玲，張弘弦

(1.太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，太原 030024；2.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200030)

排序?qū)W習(xí)是信息檢索領(lǐng)域最受關(guān)注的技術(shù)之一，并且廣泛應(yīng)用于文檔分類、文本處理、產(chǎn)品分級及其他涉及排序問題的領(lǐng)域。排序?qū)W習(xí)提供了一種優(yōu)秀的自動化框架進(jìn)行特征組合，這些組合可以查詢依賴特征，如通過現(xiàn)存搜索引擎給文檔賦予分?jǐn)?shù)，也可以是查詢獨(dú)立特征，如pagerank信息。

排序?qū)W習(xí)作為一種機(jī)器學(xué)習(xí)技術(shù)，從訓(xùn)練集的角度可以分為監(jiān)督式學(xué)習(xí)和半監(jiān)督式學(xué)習(xí)。監(jiān)督式學(xué)習(xí)中，排序?qū)W習(xí)算法都使用一組帶有標(biāo)簽的查詢文檔對作為訓(xùn)練數(shù)據(jù)去訓(xùn)練排序模型[1]；而在非監(jiān)督式學(xué)習(xí)中，排序?qū)W習(xí)算法使用一小部分有標(biāo)簽的查詢文檔對將多數(shù)無標(biāo)簽的查詢文檔作為訓(xùn)練集[2]。訓(xùn)練數(shù)據(jù)中，文檔與查詢是否相關(guān)取決于相關(guān)性標(biāo)簽，通常這些標(biāo)簽都是人工進(jìn)行判斷。從學(xué)習(xí)過程的角度，排序?qū)W習(xí)可以分為批處理學(xué)習(xí)和在線學(xué)習(xí)。經(jīng)典的排序?qū)W習(xí)算法大多屬于批處理學(xué)習(xí)，學(xué)習(xí)過程中將一次性使用全部的訓(xùn)練數(shù)據(jù)，通常使用的數(shù)據(jù)集是微軟發(fā)布的LETOR數(shù)據(jù)集[3]。批處理排序?qū)W習(xí)只需要一個訓(xùn)練過程，一旦模型訓(xùn)練完成就可以應(yīng)用于新的查詢和新的語料庫，根據(jù)特征計(jì)算相關(guān)性并學(xué)習(xí)最終模型的過程只需要進(jìn)行一次。在線排序?qū)W習(xí)將排序?qū)W習(xí)問題建模，用戶和搜索引擎之間持續(xù)循環(huán)交互，搜索引擎隨時提供給用戶最好的搜索結(jié)果，搜索引擎可以與交互的用戶學(xué)習(xí)并改善排序模型[4]。在經(jīng)典排序?qū)W習(xí)的基礎(chǔ)上，文獻(xiàn)[5]提出一種在線排序?qū)W習(xí)框架，在線排序?qū)W習(xí)允許檢索系統(tǒng)直接與用戶點(diǎn)擊反饋來優(yōu)化自身性能。

排序?qū)W習(xí)技術(shù)可以根據(jù)不同的應(yīng)用場景，結(jié)合不同領(lǐng)域的特征知識來產(chǎn)生面向特定問題的排序模型，如文獻(xiàn)[6]使用排序?qū)W習(xí)解決專家檢索問題，并在計(jì)算機(jī)科學(xué)的學(xué)術(shù)出版物數(shù)據(jù)集上進(jìn)行試驗(yàn)。文獻(xiàn)[7]使用排序?qū)W習(xí)技術(shù)構(gòu)建了一個熱門手機(jī)游戲預(yù)測系統(tǒng)，并發(fā)現(xiàn)了MART算法在訓(xùn)練模型及預(yù)測樣本時具有最好的精度。文獻(xiàn)[8]闡述了排序?qū)W習(xí)在軟件工程領(lǐng)域任務(wù)中所帶來的價值。奚凌然等人提出一種結(jié)合LPA半監(jiān)督學(xué)習(xí)的排序方法，基于已標(biāo)注訓(xùn)練數(shù)據(jù)使用Pairwise模型的Ranking SVM 進(jìn)行排序?qū)W習(xí)[9]。文獻(xiàn)[10]提出了一種基于深度學(xué)習(xí)的新的兩兩排序算法，并將其應(yīng)用于圖像重新排序。

排序?qū)W習(xí)算法的關(guān)鍵是選擇待優(yōu)化的損失函數(shù)。在IR(信息檢索，Information Retrieval)中，排序結(jié)果是使用IR評價指標(biāo)進(jìn)行評價的，因此評價指標(biāo)函數(shù)是用于優(yōu)化的損失函數(shù)。但是，評價指標(biāo)函數(shù)不能達(dá)到傳統(tǒng)機(jī)器學(xué)習(xí)技術(shù)對損失函數(shù)的要求，大多數(shù)優(yōu)化算法要求損失函數(shù)是平滑函數(shù)或者是凸函數(shù)，而IR評價指標(biāo)函數(shù)是基于位置不連續(xù)也不可微的，現(xiàn)有的算法很多是通過最小化IR評價指標(biāo)函數(shù)的上界函數(shù)解決平滑問題[11]，這些方法包括RankBoost，RankSVM，ListNet，AdaRank等算法。這些算法依賴于損失函數(shù)的數(shù)學(xué)解析性質(zhì)，其明顯的缺陷在于損失函數(shù)是IR指標(biāo)的上界函數(shù)，并不能保證上界函數(shù)的最優(yōu)解就是IR評價指標(biāo)函數(shù)的最優(yōu)解。針對這個問題，已有學(xué)者提出了基于生物理論的排序?qū)W習(xí)方法，其顯著特征是直接對IR評價指標(biāo)函數(shù)進(jìn)行優(yōu)化而無需選擇替代函數(shù)，使訓(xùn)練結(jié)果比傳統(tǒng)方法更精確，例如，基于遺傳算法的排序?qū)W習(xí)方法及其改進(jìn)算法[12]，基于免疫規(guī)劃的排序?qū)W習(xí)方法[13]。

本文將IR評價指標(biāo)函數(shù)直接作為親和力函數(shù)，根據(jù)克隆選擇理論產(chǎn)生親和力最高的抗體(排序函數(shù))，避免了使用損失函數(shù)的方法所帶來的缺陷；將改進(jìn)的克隆選擇算法應(yīng)用于排序?qū)W習(xí)，提出了一個直接優(yōu)化IR指標(biāo)函數(shù)的排序?qū)W習(xí)算法——基于多層克隆選擇的排序?qū)W習(xí)算法(RankMCSA)。算法使用多層進(jìn)化的方法逐步得到最優(yōu)的排序函數(shù)，同時使用滿二叉樹的方法表示抗體，將一個查詢及其相關(guān)文檔集和對應(yīng)的相關(guān)性判定作為抗原，定義了對二叉樹按層變異的規(guī)則。算法直接使用IR指標(biāo)MAP(mean average precision)作為進(jìn)化過程中的親和力函數(shù)。

1 排序?qū)W習(xí)

信息檢索中的一個核心問題就是決定文檔與用戶的信息需求是否相關(guān)并進(jìn)行排序，排序的目的是根據(jù)每個文檔與用戶查詢之間的相關(guān)度定義文檔的順序，最后把相關(guān)文檔排在檢索列表的較高位置。在測試階段，給定一個查詢，系統(tǒng)返回一個文檔的排序列表，它是按照相關(guān)性分值降序排列，而相關(guān)性分值是使用排序函數(shù)進(jìn)行計(jì)算的。在訓(xùn)練階段，給出一組查詢和每個查詢各自對應(yīng)的相關(guān)文檔列表，以及以全序的方式表達(dá)文檔排列的相關(guān)性判定。學(xué)習(xí)的目的是構(gòu)建一個排序函數(shù)，基于學(xué)習(xí)的排序方法能夠組合更多的特征，具有更強(qiáng)的適應(yīng)性。圖1給出了基于學(xué)習(xí)的方法處理IR排序問題的一般框架。

圖1 信息檢索領(lǐng)域排序?qū)W習(xí)一般框架Fig.1 A general framework of rank method with information retrieval

給定一個查詢集合Q={q1,…,q|Q|}，其中每一個查詢qi都有一個相關(guān)的文檔列表為di={di1,di2,…,di,n(qi)}，n(qi)是文檔列表的大小。創(chuàng)建的訓(xùn)練數(shù)據(jù)集由查詢及其相關(guān)文檔對(qi,dij)組成，文檔對的相關(guān)性判定表明了qi和dij之間的關(guān)系，相關(guān)性判定由標(biāo)簽制定者分配，qi相關(guān)文檔的標(biāo)簽列表為yi={yi1,yi2,…,yi,n(qi)}.相關(guān)性判定可以是以下幾種情況：

a.一個類標(biāo)簽，如相關(guān)和不相關(guān)；

b.一個等級，如絕對相關(guān)，可能相關(guān)，不相關(guān)；

c.一個順序，如k，意味著dij排在第k位置；

d.一個分?jǐn)?shù)，如sim(qi,dij)，表示qi和dij之間的相關(guān)性分?jǐn)?shù)。

對每一個查詢文檔對(qi,dij)，一個特征抽取器φ都會產(chǎn)生一個特征向量x=φ(qi,dij)描述qi和dij之間的匹配。特征包含了經(jīng)典IR特征(如tf，idf，BM25)，以及其他高級特征(如 PageRank)。學(xué)習(xí)算法的輸入包含訓(xùn)練實(shí)例、特征向量和對應(yīng)相關(guān)性判定，表示為(qi,di,yi)，整個訓(xùn)練集可表示為

(1)

式中：m是查詢的數(shù)量。訓(xùn)練的輸出是一個排序函數(shù)f，f(qi,dij)期望能夠給出qi和dij“真”的相關(guān)性判定，f作用在文檔列表di上就得到預(yù)測的文檔順序πi=f(qi,di).在訓(xùn)練階段，學(xué)習(xí)算法生成一個排序函數(shù)，學(xué)習(xí)過程旨在將假設(shè)空間中的排序函數(shù)所輸出的相關(guān)性判定的有關(guān)指標(biāo)(如分類精度，錯誤率，MAP等)進(jìn)行優(yōu)化。在測試階段，對于qi，排序函數(shù)得到的πi關(guān)于yi的評價函數(shù)為E(πi,yi).評價函數(shù)通常包括MAP，NDCG@n(Normalized Discounted Cumulative Gain)，P@n.

2 多層克隆選擇的排序?qū)W習(xí)方法

2.1 排序?qū)W習(xí)框架

在多層克隆選擇的排序?qū)W習(xí)中，初始抗體庫P0作為框架的第0層，使用訓(xùn)練集進(jìn)行進(jìn)化過程的學(xué)習(xí)；進(jìn)化完成后，從抗體庫中按照一定比例選擇一組最佳抗體構(gòu)成新的抗體庫；抗體的選擇按照抗體在訓(xùn)練集和驗(yàn)證集上的平均表現(xiàn)而定，其選擇的比例由選擇因子SELECTFACTOR∈(0,1)決定；選擇的抗體數(shù)量不為1則進(jìn)入到下一層繼續(xù)進(jìn)化，直到得到的抗體庫中只有1個抗體，則停止進(jìn)化，并將該抗體作為最優(yōu)排序函數(shù)。多層克隆選擇的排序?qū)W習(xí)框架如圖2所示。

圖2 RankMCSA框架Fig.2 The frame of RankMCSA

2.2 排序?qū)W習(xí)過程

在排序?qū)W習(xí)框架的每一層中最關(guān)鍵的兩個操作是進(jìn)化過程和選擇過程。進(jìn)化過程利用了克隆選擇算法，克隆選擇算法具有學(xué)習(xí)、搜索、進(jìn)化等能力，可以在假設(shè)空間中找到一批較優(yōu)解?？寺∵x擇算法中，抗體庫中的抗體朝著抗原識別率高的方向進(jìn)化，通過計(jì)算抗原-抗體親和力來進(jìn)行選擇、克隆、成熟、再選擇等操作，最終獲得一個高親和力的抗體庫。為了進(jìn)一步篩選出更高親和力抗體，再計(jì)算每個抗體在訓(xùn)練集和驗(yàn)證集上的平均親和力，優(yōu)先選擇平均親和力大的抗體進(jìn)入下一層進(jìn)行進(jìn)一步進(jìn)化，直到篩選出一個最佳抗體。

3 克隆選擇架構(gòu)

3.1 進(jìn)化過程

進(jìn)化過程借鑒了克隆選擇算法，并對其進(jìn)行改進(jìn)，改進(jìn)后的進(jìn)化過程能夠在訓(xùn)練集上進(jìn)行學(xué)習(xí)，最終可以得到一批較優(yōu)的排序函數(shù)。進(jìn)化過程主要存在兩個方面的改進(jìn)：

1) 記憶高親和力抗體的方式。進(jìn)化過程將選擇出的高親和力抗體與成熟抗體集進(jìn)行合并，并去除冗余，以保證優(yōu)秀抗體被保留下來。用于排序?qū)W習(xí)的訓(xùn)練數(shù)據(jù)集是靜態(tài)集合，作為抗原集，具有相對穩(wěn)定性。

2) 添加錄取因子。傳統(tǒng)方法不能控制成熟抗體集中優(yōu)秀抗體的錄取比率，如果單純通過克隆因子的增長降低錄取率則不能保證抗體多樣性，且不能精確控制錄取率。理論上錄取率越高，說明被錄取抗體多樣性越差，抗體質(zhì)量越低。改進(jìn)算法的克隆選擇過程中，通過判斷錄取率是否高于期望值來精確控制錄取率，保證在期望的低錄取率下選擇抗體，以提高抗體質(zhì)量，如果錄取率高，則隨機(jī)產(chǎn)生一定數(shù)量的抗體加入到待選抗體集。進(jìn)化過程如圖3所示。

圖3 每一層中抗體庫的進(jìn)化流程圖Fig.3 The evolutionary flow chart of antibody library with each layer

3.2 抗體、抗原和親和力

在排序?qū)W習(xí)中，抗體表示排序函數(shù)，即計(jì)算查詢文檔對相關(guān)度的函數(shù)，表示為bi=f(x).由抗體組成的集合稱為抗體庫P，將其定義為

(2)

將查詢文檔對表示為一個多維實(shí)數(shù)特征向量，這個向量通常是通過特定的特征提取獲得。實(shí)數(shù)向量在函數(shù)中充當(dāng)變量的角色，抗體可以根據(jù)不同的實(shí)數(shù)向量計(jì)算相應(yīng)查詢文檔對的相關(guān)性分值，函數(shù)中除了包含變量之外，通常還需要運(yùn)算符和常數(shù)。如f(x)=(2×x1+3×x2)/(4-x3)；其中，特征向量x=(x1,x2,x3)是一個3維的實(shí)數(shù)向量，運(yùn)算符是集合{+,×,/-}中的元素，常數(shù)為2，3，4.

根據(jù)以上分析，可知抗體由3種不同元素組合而成，組成抗體的元素稱為基因，則抗體的基因庫定義如下：

基因庫I為一個三元組I={F,O,C}，F(xiàn)為特征集、O為運(yùn)算符集、C為常數(shù)集。

本文中定義基因庫如下：

F={fi|fi∈x,i∈Z∧i∈[1,dimension(x)]}，dimension(x)是向量x的維數(shù)。

O={+,-,×,/} ,

C=

{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0,

2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0} .

在排序?qū)W習(xí)中，抗原定義為以查詢?yōu)閱挝坏奈臋n列表和標(biāo)簽列表

gi=(qi,di,yi) .

(3)

由抗原組成的抗原集定義抗原庫R

(4)

親和力函數(shù)計(jì)算抗體與抗原的相關(guān)度，在排序?qū)W習(xí)中親和力函數(shù)定義為IR評價指標(biāo)函數(shù)

affinity(bi,gj)=E(πi,yi) .

(5)

衡量某個抗體bi的好壞不能僅僅以個別抗原的親和力為標(biāo)準(zhǔn)，而是要以抗原庫的所有抗原的親和力的平均值為標(biāo)準(zhǔn)。所以，評價指標(biāo)計(jì)算方法E(πj,yj)一般設(shè)置為MAP，因?yàn)樵撝笜?biāo)衡量排序函數(shù)在整個測試集上的平均表現(xiàn)?？贵wbi在抗原庫R上的平均親和力定義如下:

(6)

抗體的數(shù)據(jù)結(jié)構(gòu)使用滿二叉樹結(jié)構(gòu)，樹表示法由于更加容易理解與計(jì)算，抗體樹內(nèi)部節(jié)點(diǎn)表示運(yùn)算符，葉子節(jié)點(diǎn)表示特征和常數(shù)。一個抗體表示一個候選的排序函數(shù)，中序遍歷滿樹后，得到候選函數(shù)的表達(dá)式。葉子節(jié)點(diǎn)中的特征隨機(jī)從F和C中獲取，抗體的最后表達(dá)式不要求覆蓋所有的特征，并且同一個特征可以在一個樹的葉子中出現(xiàn)多次。通過使用滿二叉樹表達(dá)抗體，如圖4所示的樹通過中序遍歷即可生成函數(shù)(3-f1)+(f2×0.3).

圖4 抗體樹表示Fig.4 The representation with antibody tree

3.3 選擇過程

在抗體庫P0進(jìn)化結(jié)束后，需要選擇優(yōu)秀的抗體進(jìn)入下一層P1繼續(xù)進(jìn)化。選擇的抗體數(shù)量由選擇因子fSEL確定，第i層抗體庫Pi的抗體數(shù)量定義如下:

|Pi|=round(fSEL·|Pi-1|) .

(7)

式中：i≥1，fSEL∈(0,1).

為了選擇最佳抗體，計(jì)算抗體Abi在訓(xùn)練集D和驗(yàn)證集V上的平均親和力

(8)

式中，F(xiàn)AVA(bi,D)表示抗體bi在訓(xùn)練集D上的親和力。將抗體庫Pi-1中所有抗體按照公式(8)計(jì)算后，根據(jù)公式(7)選擇親和力最高的抗體進(jìn)入下一層繼續(xù)進(jìn)化。當(dāng)抗體庫中抗體數(shù)量為1時，整個訓(xùn)練過程結(jié)束并將該抗體作為最優(yōu)的排序函數(shù)。

3.4 算法描述

基于多層克隆選擇的排序?qū)W習(xí)利用一個多層的克隆選擇過程學(xué)習(xí)最優(yōu)的排序函數(shù)。學(xué)習(xí)過程主要包括以下幾個步驟：

1) 隨機(jī)生成一個原始排序函數(shù)集作為第0層的抗體庫，初始化由查詢文檔對構(gòu)成的訓(xùn)練集D、驗(yàn)證集V；

2) 遍歷每一個排序函數(shù)，計(jì)算其在訓(xùn)練集上的MAP；

3) 根據(jù)MAP的大小對排序函數(shù)進(jìn)行選擇、克隆、變異，并迭代操作這些過程直到滿足迭代終止條件，進(jìn)化完成后根據(jù)選擇因子fSEL選擇一定數(shù)量優(yōu)秀的排序函數(shù)進(jìn)入下一層；

4) 持續(xù)對排序函數(shù)集合進(jìn)行進(jìn)化，直到獲得一個最優(yōu)排序函數(shù)。

多層克隆選擇的排序?qū)W習(xí)算法描述如下：

輸入：訓(xùn)練集D，驗(yàn)證集V.

參數(shù)：N(抗體庫大小)，n(待克隆抗體數(shù)量)，T(迭代次數(shù))，d(替換抗體數(shù)量)，α(錄取因子)，β(克隆因子)，fSEL(選擇因子)。

Step2：計(jì)算每個排序函數(shù)bi∈P在D上的MAP；

Step3：根據(jù)MAP的值，從P中選擇n個最高M(jìn)AP的排序函數(shù)組成Pn；

Step4：對Pn中的排序函數(shù)進(jìn)行克隆得到克隆集C，MAP越高克隆副本越多，C的大小為Nc；

Step5：對C中的排序函數(shù)進(jìn)行變異得到成熟集C*，MAP越高，變異層數(shù)越少，C*的大小為Nc；

Step6：將Pn與C*合并，去除相同排序函數(shù)，得到P*；

Step7：IfN/P*>αthen隨機(jī)生成(N/α-|P*|)個排序函數(shù)加入到P*；

Step8：從P*中選擇MAP最高N個排序函數(shù)組成P*；

Step10：重復(fù)Step1到Step9，直到滿足迭代次數(shù)大于T；

Step11：從P中選擇若干最好排序函數(shù)，進(jìn)入到下一層。如果P中只剩下一個排序函數(shù)，則算法停止并返回這個最優(yōu)的排序函數(shù)。

3.5 克隆與變異

抗體庫中的每個抗體克隆的數(shù)量與平均親和力成正比。每個抗體的克隆數(shù)量表示為

NCLO=round(β×n×FAVA) .

(9)

式中：β是克隆因子；n是選擇抗體的數(shù)量；FAVA是抗體的平均親和力；round函數(shù)對小數(shù)點(diǎn)后1位四舍五入，最后得到一個整數(shù)?？寺『蟮乃锌寺】贵w的數(shù)量為

(10)

抗體變異方法使用的是子樹替換方式，根據(jù)親和力選擇抗體的一個內(nèi)部節(jié)點(diǎn)，然后通過隨機(jī)生成一個樹去替換該節(jié)點(diǎn)為根的整個子樹。變異操作需要滿足以下規(guī)則：

1) 替換后的節(jié)點(diǎn)編號要符合整個樹的編號順序。

2) 替換子樹的特征與被替換子樹的特征完全相同且不重復(fù)，新子樹特征節(jié)點(diǎn)排列是隨機(jī)的。這樣做是為了變異后的抗體同樣能夠完全覆蓋所有特征且不重復(fù)。

分層變異策略定義如下：

根據(jù)親和力計(jì)算變異發(fā)生的層數(shù)l.

l∈[0,H-1]∧l∈Z.H為樹的高度，第0層為抗體的根節(jié)點(diǎn)。

1) 隨機(jī)選擇該層的一個內(nèi)部節(jié)點(diǎn)n，獲取以該節(jié)點(diǎn)為根的子樹高度h.

2) 獲取該節(jié)點(diǎn)為根的特征子節(jié)點(diǎn)數(shù)組f[].為了保留原有特征節(jié)點(diǎn)編號，將其隨機(jī)掛載進(jìn)新的子樹上，這樣整個抗體的特征仍然不重復(fù)且完全覆蓋所有特征。

3) 創(chuàng)建高度為(h-1)的子樹t.

4) 創(chuàng)建包含f[]所有元素的葉子節(jié)點(diǎn)l[]，數(shù)量為2(h-1).

5) 隨機(jī)選取l[]中的葉子，掛載到t上面，構(gòu)成一個高度為h的子樹。

6) 用子樹t替換子樹n.

在變異時，抗體根據(jù)抗體親和力選擇變異層，親和力越大所選變異層越大，替換子樹越小。

假設(shè)親和力FAVA∈[Fmin,Fmax]，樹的高度為H，要使得l∈[0,H-1]∧l∈Z，則變異層的計(jì)算方法如下

(11)

對于不在親和力區(qū)間內(nèi)的親和力值，采用下面策略：

IfFAVA∈(0,Fmin) thenl=0 ,

IfFAVA∈(Fmax,1) thenl=H-1 .

親和力區(qū)間根據(jù)經(jīng)驗(yàn)確定，所選區(qū)間和實(shí)際相關(guān)度的變化區(qū)間越相符，則所選的層次數(shù)越有效。親和力區(qū)間與數(shù)據(jù)集有關(guān)，不同的數(shù)據(jù)集親和力差別較大，具體的區(qū)間范圍要根據(jù)實(shí)際情況而定。

4 排序?qū)W習(xí)實(shí)驗(yàn)

實(shí)驗(yàn)使用數(shù)據(jù)集LETOR3.0中的OHSUMED數(shù)據(jù)集以及LETOR4.0中的MQ2007，MQ2008數(shù)據(jù)集。LETOR數(shù)據(jù)集包含了IR相關(guān)的特征，查詢文檔對的相關(guān)性判斷和用于交叉驗(yàn)證的數(shù)據(jù)分區(qū)，并且還提供了標(biāo)準(zhǔn)的評價工具以及用于比較的基線結(jié)果。LETOR數(shù)據(jù)集全部采用5-fold交叉驗(yàn)證的方式，算法的運(yùn)行結(jié)果是5-fold的平均結(jié)果。

評價指標(biāo)使用了MAP(mean average precision)，NDCG(normalized discounted cumulative gain)和P@n.實(shí)驗(yàn)所用的評價工具是LETOR提供的標(biāo)準(zhǔn)評價工具，保證和基線比較的正確性。MAP的計(jì)算方法如公式(12)和(13)

(12)

(13)

式中：P@k(q)為位置k的準(zhǔn)確率；位置k的文檔標(biāo)簽為l(k)；l(k)等于1表示文檔相關(guān)，等于0表示文檔不相關(guān)；m是該查詢相關(guān)的文檔數(shù)量。MAP只支持二值相關(guān)性判斷。另一個指標(biāo)為NDCG支持多個相關(guān)度判斷，對某個位置j來說，查詢集上所有查詢的平均值NDCG(j)越大，表示相關(guān)性越大的文檔排序越靠前，計(jì)算方法如式(14)：

(14)

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

利用所提出的算法對每個fold的訓(xùn)練集進(jìn)行訓(xùn)練，訓(xùn)練結(jié)束后得到一個最優(yōu)的排序函數(shù)。使用該函數(shù)計(jì)算測試集中的每個查詢文檔對的相關(guān)性分值，得到一個包含相關(guān)性分值的預(yù)測文件。使用LETOR提供的標(biāo)準(zhǔn)測試工具對預(yù)測文件進(jìn)行處理得到最后的MAP和NDCG評價結(jié)果。每次實(shí)驗(yàn)的5-fold的平均結(jié)果是算法在該數(shù)據(jù)集上的運(yùn)行結(jié)果。實(shí)驗(yàn)中，所提出的RankMCSA算法分別在OHSUMED和MQ2008數(shù)據(jù)集上執(zhí)行10次，每次執(zhí)行都是5-fold交叉驗(yàn)證，最后的實(shí)驗(yàn)結(jié)果是10次實(shí)驗(yàn)的平均值。所提出的算法在2個數(shù)據(jù)集實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

4.2 實(shí)驗(yàn)結(jié)果

本文將RankMCSA與下面4種基線方法進(jìn)行比較：RankSVM,RankBoost,ListNet和AdaRank-MAP.表2顯示了2個數(shù)據(jù)集的MAP值的比較。圖5顯示了OHSUMED數(shù)據(jù)集上RankMCSA算法的NDCG@n值的比較，圖6顯示OHSUMED數(shù)據(jù)集上RankMCSA算法的P@n值的比較，圖7是MQ2008數(shù)據(jù)集上RankMCSA算法的NDCG@n值的比較，圖8是MQ2008數(shù)據(jù)集上RankMCSA算法的P@n值的比較。

表1 實(shí)驗(yàn)參數(shù)Table 1 Experiment parameter

表2 RankMCSA算法的MAP值比較Table 2 The comparison of MAP's values above the algorithm of RankMCSA

圖5 OHSUMED數(shù)據(jù)集上RankMCSA的NDCG@n值的比較Fig.5 The comparison of NDCG@n's values of RankMCSA above the data sets of OHSUMED

圖6 OHSUMED數(shù)據(jù)集上RankMCSA的P@n值的比較Fig.6 The comparison of P@n's values of RankMCSA above the data sets of OHSUMED

圖7 MQ2008數(shù)據(jù)集上RankMCSA的NDCG@n值的比較Fig.7 The comparison of NDCG@n's values of RankMCSA above the data sets of MQ2008

圖8 MQ2008數(shù)據(jù)集上RankMCSA的P@n值的比較Fig.8 The comparison of P@n's values of RankMCSA above the data sets of MQ2008

表2中，RankMCSA在OHSUMED上的MAP比RankSVM高出2.1%，比RankBoost高出0.3%；但是比ListNet和AdaRank-MAP分別低0.69%和1.3%.在MQ2008上RankMCSA比RankSVM高出1.7%，比AdaRank-MAP高出0.2%，比RankBoost和ListNet低0.02%，幾乎相同。對于NDCG@n指標(biāo)，從圖5可以看出OHUSMED上RankMCSA明顯好于RankSVM和RankBoot，但稍遜于ListNet和AdaRank-MAP.而從圖7可以看出MQ2008上RankMCSA與基線算法的差別并不明顯，平均表現(xiàn)與基線持平。對于P@n指標(biāo)，從圖6可以看出OHSUMED上RankMCSA明顯優(yōu)于RankBoost和RankSVM，但對比ListNet和AdaRank-MAP仍顯不足。從圖8可以看出RankMCSA仍然表現(xiàn)穩(wěn)定，平均表現(xiàn)與基線算法持平。從圖5-圖8中可以看出，RankMCSA比基線算法更穩(wěn)定，波動較小，這說明該算法不僅能將相關(guān)度高的文檔排在前面，而且對高排名位置敏感程度低，從而避免出現(xiàn)高排名的文檔相關(guān)度高低差別大的情況。

從以上結(jié)果中可以看出，RankMCSA是一種能夠產(chǎn)生有效排序函數(shù)的排序?qū)W習(xí)算法，在2個數(shù)據(jù)集上明顯優(yōu)于RankSVM，RankBoost.在OHSUMED集合上，在某些情況下優(yōu)于ListNet，如NDCG@4～NDCG@7，P@5,P@6，與AdaRank-MAP相比略顯不足。在MQ2008上，各個算法的差別并不明顯，這也證明了RankMCSA算法的有效性。算法仍然有可以提升的空間，隨著抗體庫大小、克隆因子以及選擇因子的提高，算法的運(yùn)行結(jié)果會進(jìn)一步得到改進(jìn)。

5 結(jié)束語

本文提出了一種基于多層克隆選擇的排序?qū)W習(xí)方法，用于學(xué)習(xí)IR中的排序函數(shù)。它使用一種按層變異的方法和一種多層的克隆選擇架構(gòu)逐步進(jìn)化抗體庫，每一層進(jìn)化完成后選擇一定數(shù)量的優(yōu)秀抗體進(jìn)入下一層，直到最后遴選出最優(yōu)排序函數(shù)；這種方法對于生成復(fù)雜的、非線性排序函數(shù)非常有效。同時使用滿二叉樹的方法表示抗體，將一個查詢及其相關(guān)文檔集和對應(yīng)的相關(guān)性判定作為抗原，定義了對二叉樹按層變異的規(guī)則。算法在OHSUMED和 MQ2008數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明RankMCSA能夠在更少的迭代次數(shù)以及更少的訓(xùn)練時間內(nèi)產(chǎn)生更好的排序函數(shù)；不僅能將相關(guān)度高的文檔排在前面，而且對高排名位置敏感程度低，從而避免出現(xiàn)高排名的文檔相關(guān)度高低差別大的情況。