李 茜，周華健，楊浩運，殷海兵

(杭州電子科技大學圖書館,浙江 杭州 310018)

1 引言

伴隨著信息網絡社會來臨，圖書館管理與服務也處于變革與發(fā)展時期。由于信息網絡化使圖書館逐步從傳統手工服務走向計算機網絡化服務，因此越來越多的圖書館文獻信息加入到互聯網[1]。一方面將人類智慧的沉淀與結晶轉化為人類可共享的資源，另一方面亦可將網上無序的資源轉化為可供利用、借鑒的有序資源。就目前我國圖書館事業(yè)發(fā)展的狀況看，能夠將網上資源重新整序、組合和再利用的圖書館不多，而多數圖書館僅停留在本館資源的利用上[2]。例如，利用計算機對文獻進行著錄、標引形成系統的書目數據庫，讀者通過局域網或因特網從不同的檢索途徑查找所需要的文獻信息。以書目數據庫的檢索途徑為例，目前有幾種讀者可利用的檢索方式，如：文獻題名、責任者、出版社、分類號、主題詞等，卻無法根據既具有實用價值又被廣大用戶常常利用的關鍵字，檢索到所需求的文獻信息，這無疑給用戶利用文獻信息資源帶來了不便，也背離了“讀者至上”的辦館原則[3,4]。因此，如何利用查詢關鍵字對搜索引擎召回的候選記錄進行有效排序是圖書館書目檢索的核心問題，是圖書館關鍵字高效查詢的關鍵所在[5,6]。

隨著機器學習技術快速發(fā)展，通過機器學習算法來獲取精準的排序模型已經得到廣泛的應用。迄今為止，常用學習排序算法主要分為3種[7]：pointwise、pairwise和listwise。pointwise算法利用機器學習預測當前查詢關鍵字單個候選記錄的排序值，簡單地將排序問題歸結為線性分類或回歸問題[8,9]；pairwise算法將候選記錄作為一個訓練實例，并且將排序問題歸結為從候選記錄實例集合中學習分類或回歸模型的任務[10]。然而，pointwise和pairwise算法都不能夠在訓練過程中直接通過最小化損失值獲得精準的排序模型。因此，學術界提出了listwise算法解決這一問題，它將候選記錄的排序列表作為訓練實例，并且通過最小化在預測列表和真實列表上定義的損失函數來優(yōu)化排序模型[11]。

雖然學術界對3種學習排序算法進行了廣泛研究，但它們都面臨相似的挑戰(zhàn)。在訓練過程中，上述3種排序算法都不能利用在線獲得的數據更新排序模型。因此，隨著書目檢索數據量越來越多，訓練過程中算法有效性差的問題越來越明顯。為了解決該問題，學術界提出了將在線學習算法應用到學習排序算法中。在線學習是一種有效的機器學習算法，在訓練排序模型時，每一次迭代過程中隨機選取一個訓練數據用作訓練，且僅被應用一次，通過最小化整個預測序列的累計錯誤，使排序模型性能最優(yōu)。迄今為止，在線學習只應用到了pairwise算法中，一定程度提高了算法的有效性。

由于pairwise算法在整體排序性能表現上不如listwise算法[12]，為了進一步提高算法性能，本文基于listwise算法提出一種在線學習排序算法，記為online-listwise算法。在訓練過程中，該算法將整個候選記錄的排序列表作為訓練實例，利用在線獲得的數據更新排序模型。本文的主要貢獻在于：首先，將在線學習與學習排序算法相結合，然后通過理論推導得出online-listwise算法的損失值是1-MAP(Mean Average Precision)的上限值，從而可通過最小化損失值使MAP最優(yōu)。為了在訓練排序模型時，能夠實現盡快收斂，通過理論推導得出基于online-listwise算法的自適應學習率。因此，可根據圖書館的書目數據庫，利用online-listwise算法在極短時間內訓練出性能優(yōu)越的排序模型，用于書目檢索系統中，根據讀者輸入的關鍵字輸出相關候選記錄的有序排序列表。

2 相關工作

2.1 listwise

Listwise算法能獲得良好的排序性能，在信息檢索領域引起廣泛的研究。listwise算法將整個候選記錄的排序列表作為訓練實例，并且最小化在預測列表和真實列表上定義的損失函數來優(yōu)化排序模型。listwise算法的損失函數是基于Luce模型[7]定義的，如式(1)所示：

(1)

其中,N是當前查詢關鍵字的候選記錄總數，φ是變換函數，φ(s)=e(s),s是由評分函數f輸出的相關度分數得分，π表示根據候選記錄真實相關度分數從大到小排序對應索引序號的列表，sπ(u)表示在有序列表π中第u個索引序號處的預測分數。對于每個查詢樣本(特征值為x)，根據式(1)會得出基于候選記錄有序列表真值的損失函數，如式(2)所示：

L(f:x,π)=-logP(π|φ(f(ω,x)))

(2)

其中，ω是權重系數矩陣，f為評分函數，s=f(ω,x)=ωTx。已有結論表明，(1-MAP)可以通過基于listwise學習排序算法定義的損失函數來限定[11]。

2.2 在線學習

在線學習算法是一種高效且可擴展的機器學習算法[13]，近年來被廣泛應用于文檔和視頻等信息檢索應用中。通常，在線學習排序算法在應用訓練實例時，訓練實例按照順序到達神經網絡，并且僅被應用1次。在每一次的迭代過程中，通過測量預測值和真實值之間的損失是否小于容錯率，來判定模型權重系數是否需要更新。通常，在線學習算法的目標是最小化整個預測序列中的累積錯誤。

最近，文獻[7]將在線學習算法與pairwise學習排序算法相結合提出online-pairwise算法。該算法首先通過理論推導得出其損失值是(1-MAP)的上限值，然后利用在線獲得的數據，使用隨機梯度下降算法最小化損失函數，從而使性能評價指標MAP最優(yōu)，獲得精準的排序模型。這樣，就可以在保證pairwise算法性能優(yōu)勢前提下，提高算法的有效性。

到目前為止，在線學習算法僅應用于pairwise學習排序算法，但該算法相比較于listwise算法存在一定的性能差距。因此,本文提出了online-listwise算法，通過該算法可以在保證listwise算法性能前提下，在訓練過程中實現在線更新排序模型并提高算法有效性。

3 在線學習書目排序檢索算法

由于listwise算法在檢索方面出色的性能優(yōu)勢，在書目檢索應用中常采用listwise算法訓練排序模型。但是，隨著書目檢索數據量越來越多，利用listwise算法訓練排序模型的時間復雜度越來越高。在線學習排序是一種有效且可擴展的機器學習算法，將在線學習與listwise算法結合，可以在保證listwise算法訓練排序模型性能優(yōu)勢前提下，減少訓練過程時間消耗。

3.1 online-listwise算法

(1)online-listwise算法。

首先基于listwise算法將查詢關鍵字對應的候選記錄排序列表作為訓練實例；然后利用在線學習排序算法的訓練過程，每一次迭代過程中隨機選取一個訓練數據用作訓練，并且僅被應用1次；最后通過最小化損失值獲取精準的排序模型。

如何確保online-listwise算法的性能，是本文需要解決的關鍵問題。在listwise算法中，排序數據的特征值用x=[x1,x2, …,xN]∈Rd×N表示，N是候選記錄總數; 第n個候選記錄的特征值xn是一個d×1維矩陣；這些數據的相關度分數(標簽值)是y=[l1,l2,…,lN]，其中l(wèi)n表示xn的標簽值。將y中元素按從大到小進行排序，得到調整順序后版本y′，取y′中各個元素在y中對應序號構成有序列表πy。比如：x=[x1,x2,x3,x4,x5],其標簽值為y=[34,32,33,31,35], 標簽值未排序索引值是{1,2,3,4,5}; 在標簽值排序后有序列表πy中存儲索引值{5,1,3,2,4}。有序列表πy隨機獲取索引序號α=πy(i)和β=πy(j)滿足：如果xα≥xβ，則lα≥lβ。已有的結論表明,listwise算法的損失函數定義[7]如式(3)所示：

(3)

其中τ(·)表示損失函數，πy(i)表示在列表πy中第i個位置索引序號，f(xπy(i))=ωTxπy(i)是從數據特征到預測值的映射函數關系。在本文中，f(ω,x)=ωTx，是一個線性函數關系。所以,在下文的推導中，用τ(ω;x,y)替代τ(f;x,y)。

MAP是信息檢索中常用的評價指標，表示平均正確率，即多個查詢輸入(query)對應平均精確度AP(Average Precision)的均值，可表達如下：

(4)

其中，q是query序號，進行了Q次查詢。對于某次檢索而言，平均精確度AP可表達為：

(5)

其中，假設有V個檢索結果，v為檢索結果隊列中的排序位置，Pc(v)為前v次檢索結果的準確率，rel(v) 表示位置v的文檔是否與查詢輸入query相關，相關為1，不相關為0。

已有的結論表明式(3)中的損失函數是(1-MAP(f;x,y))的上限值[14]，如式(6)所示：

1-MAP(ωT;x,y)≤

(6)

其中,ml是標簽值等于l的標簽數量。K是標簽值列表y中的最大值。xt和yt是第t次在線迭代過程中接收到的訓練數據，T表示迭代次數。ω是神經網絡里的權重系數矩陣，ωt和ωT分別表示第t和T次迭代權重系數矩陣，ω*表示最優(yōu)權重矩陣。當數據中給定的標簽值K>2時，那么在計算MAP時，需要給定1個固定常數k*，若候選記錄的標簽值大于k*，則認為是相關，反之，則認為不相關。 為了得出online-listwise算法的損失值是(1-MAP)的上限值，本文首先采用在線梯度下降算法進行網絡參數更新,如式(7)所示：

ωt+1=ωt-ηt▽τ(ωt;xt,yt)

(7)

其中,ηt是在第t次迭代過程中的學習率，xt和yt是第t次在線迭代過程中接收到的訓練數據，并且 ▽τ(ωt;xt,yt)的定義如式(8)所示：

▽τ(ωt;xt,yt)=

(8)

經過推導，關于MAP可以得到如下結論：

(9)

Figure 1 Process of online learning bibliographic sorting retrieval algorithm圖1 在線學習書目排序檢索算法的流程

參考文獻[7]中定理3可得出以下不等式：

(10)

(11)

所以,當T→∞時，式(11)便會近似于式(12):

(12)

通過上述理論推導可以得出,online-listwise算法的損失函數是(1-MAP)的上限值，即式(6)，因此在訓練過程中可通過最小化損失函數使MAP達到最佳，從而實現高效檢索。

(2) 最小化損失函數。

傳統的學習排序算法，是在獲得一批訓練數據后，利用隨機梯度下降算法更新網絡參數，其中學習率是保持不變的[12]。由于在線學習排序算法是即時處理在線獲得的數據，更新排序模型，與傳統的學習排序算法的訓練過程完全不一樣，所以為了解決將基于傳統學習排序算法的學習率直接應用到在線學習排序算法中，導致排序模型精準度低和收斂過慢的問題，本文根據實驗統計結果得出基于online-listwise算法的自適應學習率ηt，如式(13)所示：

(13)

其中,‖xi-xj‖≤D，D是不同特征值X之間最大差值，t是迭代的次數，G是符合G-Lipschitz連續(xù)的收斂參數。參數D和G需滿足如式(14)所示的不等式：

|f(xi)-f(xj)|≤G×D,G≥0

(14)

因此，通過使用自適應學習率和式(7)更新網絡參數，使排序模型結果更加精準和更快收斂。Online-listwise算法實現流程如算法1所示。

算法1 online-listwise算法

輸入：訓練集數據{(x1,y1),(x2,y2)…,(xT,yT)},學習率ηt，容錯率ε。

輸出：排序模型ωT。

初始化權重系數ωt;

fori=1 toTdo

輸入(xt,yt)到神經網絡并且計算▽τ(ωt;xt,yt)；

更新權重系數：ωt+1=ωt-ηt▽τ(ωt;xt,yt)；

利用式(12)計算訓練集的損失函數值loss；

ifloss<εthen

break；

end if

end for

3.2 應用online-listwise算法

在應用online-listwise算法訓練排序模型時，一方面，根據上述理論推導，可直接通過最小化式(11)所示的損失函數，使排序性能MAP最優(yōu)，從而保證排序模型的性能；另一方面，為減少訓練排序模型的時間，訓練數據按順序到達神經網絡且僅被應用1次，而且將式(12)所示學習率應用到訓練過程中，使排序模型能夠盡快收斂。

這樣可以根據圖書館內書目數據庫，基于online-listwise算法思想訓練排序模型，最后將訓練好的排序模型應用到關鍵字檢索系統中，從而可利用排序模型根據查詢關鍵字輸出相關候選記錄的相關度預測值，并根據預測值輸出相關候選記錄的有序列表S1，S2,…,Sm，以實現圖書館的高效檢索功能。在線學習書目排序檢索算法的流程如圖1所示。

4 實驗結果

4.1 測試數據集-LETOR3.0

眾所周知，LETOR3.0是一個基準數據集，在信息檢索領域典型的學習排序算法，例如pairewise、pointwise和listwise算法都在該數據集上進行了排序性能測試[12]。LETOR3.0中的文檔數據庫列表如表1所示。

Table 1 List of document databases in LETOR3.0表1 LETOR3.0中的文檔數據庫列表

由于學者們在LETOR3.0上測試了許多學習排序算法并給出了相應的結果，本文采用LETOR3.0作為測試數據集，以方便比較不同算法的排序性能。

4.2 性能測試結果

本文通過相同的交叉驗證方案對不同的算法進行排序性能測試。為了評估檢索性能，采用書目檢索領域中廣泛使用的性能評價指標MAP和NDCG。一方面，在線學習排序算法僅與pairwise算法相結合,因此，本文選取了pairwise類典型算法RankSVM和online-pairwise類典型算法OGDR作比較。另一方面，由于online-listwise算法采用了自適應學習率使排序模型的結果更加精準和更快收斂，因此本文將基于Adam算法進行學習率更新的online-listwise算法和采用自適應學習率的online-listwise算法進行了比較。本文最后測試了listwise、online-listwise、RankSVM、Adam和OGDR算法的排序性能。首先測試了上述幾種算法在標準數據集上的性能評價指標MAP，結果如表2所示。根據表2可以得出以下結論：

(1) online-pairwise算法與pairwise算法相比，MAP平均下降了0.015。

(2) 與listwise算法相比，online-listwise算法在6個數據集上平均下降了0.026。但是，online-listwise算法往往比Adam算法性能表現更好。

(3) 在數據集NP04、HP03、HP04和OH上，online-listwise算法與RankSVM算法相比，MAP平均增加了0.015。在其他數據集上，online-listwise算法與RankSVM算法相比，MAP平均下降了0.015，造成這種現象的原因是listwise算法與RankSVM算法相比性能較差。

(4) 在數據集NP04、HP03、HP04和OH上，online-listwise算法與online-pairwise算法相比，MAP平均增加了0.020。在其他數據集上，online-listwise算法的性能不如online-pairwise算法的，造成這種現象的原因同樣是listwise算法與RankSVM算法相比性能較差。

Table 2 MAP of each algorithm表2 各算法的MAP

為了進一步評估算法訓練排序模型效率，還統計了listwise算法和online-listwise算法訓練排序模型的累計CPU時間消耗，如圖2所示。從圖2可以清楚地看到，與listwise算法相比，online-listwise算法顯著提高了訓練排序模型的效率。

Figure 2 Cumulative time consumption on CPU圖2 CPU累計時間消耗

5 結束語

本文提出了一種基于listwise在線學習的排序算法，旨在保證listwise算法性能前提下，降低排序模型訓練復雜度。在具有數百萬甚至數十億次的書目大規(guī)模查詢應用中，首先說明listwise算法面臨有效性的挑戰(zhàn)，然后探索利用在線學習算法來應對該挑戰(zhàn)。本文從理論上證明了通過最小化online-listwise損失值，可以獲得最佳排序性能MAP。另外，使用隨機梯度下降算法最小化online-listwise損失函數的過程中，將固定學習率轉換為自適應學習率，以便快速實現收斂。最后，在LETOR數據集上的測試結果表明：本文算法具有較好的檢索準確率和速度，不僅可應用于海量書目高效檢索，還可應用于其它信息檢索任務。