一種基于listwise的在線學(xué)習(xí)書(shū)目排序檢索算法*

李 茜，周華健，楊浩運(yùn)，殷海兵

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

1 引言

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

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

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

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

2 相關(guān)工作

2.1 listwise

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

(1)

其中,N是當(dāng)前查詢(xún)關(guān)鍵字的候選記錄總數(shù)，φ是變換函數(shù)，φ(s)=e(s),s是由評(píng)分函數(shù)f輸出的相關(guān)度分?jǐn)?shù)得分，π表示根據(jù)候選記錄真實(shí)相關(guān)度分?jǐn)?shù)從大到小排序?qū)?yīng)索引序號(hào)的列表，sπ(u)表示在有序列表π中第u個(gè)索引序號(hào)處的預(yù)測(cè)分?jǐn)?shù)。對(duì)于每個(gè)查詢(xún)樣本(特征值為x)，根據(jù)式(1)會(huì)得出基于候選記錄有序列表真值的損失函數(shù)，如式(2)所示：

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

(2)

其中，ω是權(quán)重系數(shù)矩陣，f為評(píng)分函數(shù)，s=f(ω,x)=ωTx。已有結(jié)論表明，(1-MAP)可以通過(guò)基于listwise學(xué)習(xí)排序算法定義的損失函數(shù)來(lái)限定[11]。

2.2 在線學(xué)習(xí)

在線學(xué)習(xí)算法是一種高效且可擴(kuò)展的機(jī)器學(xué)習(xí)算法[13]，近年來(lái)被廣泛應(yīng)用于文檔和視頻等信息檢索應(yīng)用中。通常，在線學(xué)習(xí)排序算法在應(yīng)用訓(xùn)練實(shí)例時(shí)，訓(xùn)練實(shí)例按照順序到達(dá)神經(jīng)網(wǎng)絡(luò)，并且僅被應(yīng)用1次。在每一次的迭代過(guò)程中，通過(guò)測(cè)量預(yù)測(cè)值和真實(shí)值之間的損失是否小于容錯(cuò)率，來(lái)判定模型權(quán)重系數(shù)是否需要更新。通常，在線學(xué)習(xí)算法的目標(biāo)是最小化整個(gè)預(yù)測(cè)序列中的累積錯(cuò)誤。

最近，文獻(xiàn)[7]將在線學(xué)習(xí)算法與pairwise學(xué)習(xí)排序算法相結(jié)合提出online-pairwise算法。該算法首先通過(guò)理論推導(dǎo)得出其損失值是(1-MAP)的上限值，然后利用在線獲得的數(shù)據(jù)，使用隨機(jī)梯度下降算法最小化損失函數(shù)，從而使性能評(píng)價(jià)指標(biāo)MAP最優(yōu)，獲得精準(zhǔn)的排序模型。這樣，就可以在保證pairwise算法性能優(yōu)勢(shì)前提下，提高算法的有效性。

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

3 在線學(xué)習(xí)書(shū)目排序檢索算法

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

3.1 online-listwise算法

(1)online-listwise算法。

首先基于listwise算法將查詢(xún)關(guān)鍵字對(duì)應(yīng)的候選記錄排序列表作為訓(xùn)練實(shí)例；然后利用在線學(xué)習(xí)排序算法的訓(xùn)練過(guò)程，每一次迭代過(guò)程中隨機(jī)選取一個(gè)訓(xùn)練數(shù)據(jù)用作訓(xùn)練，并且僅被應(yīng)用1次；最后通過(guò)最小化損失值獲取精準(zhǔn)的排序模型。

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

(3)

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

MAP是信息檢索中常用的評(píng)價(jià)指標(biāo)，表示平均正確率，即多個(gè)查詢(xún)輸入(query)對(duì)應(yīng)平均精確度AP(Average Precision)的均值，可表達(dá)如下：

(4)

其中，q是query序號(hào)，進(jìn)行了Q次查詢(xún)。對(duì)于某次檢索而言，平均精確度AP可表達(dá)為：

(5)

其中，假設(shè)有V個(gè)檢索結(jié)果，v為檢索結(jié)果隊(duì)列中的排序位置，Pc(v)為前v次檢索結(jié)果的準(zhǔn)確率，rel(v) 表示位置v的文檔是否與查詢(xún)輸入query相關(guān)，相關(guān)為1，不相關(guān)為0。

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

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

(6)

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

ωt+1=ωt-ηt▽?duì)?ωt;xt,yt)

(7)

其中,ηt是在第t次迭代過(guò)程中的學(xué)習(xí)率，xt和yt是第t次在線迭代過(guò)程中接收到的訓(xùn)練數(shù)據(jù)，并且 ▽?duì)?ωt;xt,yt)的定義如式(8)所示：

▽?duì)?ωt;xt,yt)=

(8)

經(jīng)過(guò)推導(dǎo)，關(guān)于MAP可以得到如下結(jié)論：

(9)

Figure 1 Process of online learning bibliographic sorting retrieval algorithm圖1 在線學(xué)習(xí)書(shū)目排序檢索算法的流程

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

(10)

(11)

所以,當(dāng)T→∞時(shí)，式(11)便會(huì)近似于式(12):

(12)

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

(2) 最小化損失函數(shù)。

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

(13)

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

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

(14)

因此，通過(guò)使用自適應(yīng)學(xué)習(xí)率和式(7)更新網(wǎng)絡(luò)參數(shù)，使排序模型結(jié)果更加精準(zhǔn)和更快收斂。Online-listwise算法實(shí)現(xiàn)流程如算法1所示。

算法1 online-listwise算法

輸入：訓(xùn)練集數(shù)據(jù){(x1,y1),(x2,y2)…,(xT,yT)},學(xué)習(xí)率ηt，容錯(cuò)率ε。

輸出：排序模型ωT。

初始化權(quán)重系數(shù)ωt;

fori=1 toTdo

輸入(xt,yt)到神經(jīng)網(wǎng)絡(luò)并且計(jì)算▽?duì)?ωt;xt,yt)；

更新權(quán)重系數(shù)：ωt+1=ωt-ηt▽?duì)?ωt;xt,yt)；

利用式(12)計(jì)算訓(xùn)練集的損失函數(shù)值loss；

ifloss<εthen

break；

end if

end for

3.2 應(yīng)用online-listwise算法

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

這樣可以根據(jù)圖書(shū)館內(nèi)書(shū)目數(shù)據(jù)庫(kù)，基于online-listwise算法思想訓(xùn)練排序模型，最后將訓(xùn)練好的排序模型應(yīng)用到關(guān)鍵字檢索系統(tǒng)中，從而可利用排序模型根據(jù)查詢(xún)關(guān)鍵字輸出相關(guān)候選記錄的相關(guān)度預(yù)測(cè)值，并根據(jù)預(yù)測(cè)值輸出相關(guān)候選記錄的有序列表S1，S2,…,Sm，以實(shí)現(xiàn)圖書(shū)館的高效檢索功能。在線學(xué)習(xí)書(shū)目排序檢索算法的流程如圖1所示。

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

4.1 測(cè)試數(shù)據(jù)集-LETOR3.0

眾所周知，LETOR3.0是一個(gè)基準(zhǔn)數(shù)據(jù)集，在信息檢索領(lǐng)域典型的學(xué)習(xí)排序算法，例如pairewise、pointwise和listwise算法都在該數(shù)據(jù)集上進(jìn)行了排序性能測(cè)試[12]。LETOR3.0中的文檔數(shù)據(jù)庫(kù)列表如表1所示。

Table 1 List of document databases in LETOR3.0表1 LETOR3.0中的文檔數(shù)據(jù)庫(kù)列表

由于學(xué)者們?cè)贚ETOR3.0上測(cè)試了許多學(xué)習(xí)排序算法并給出了相應(yīng)的結(jié)果，本文采用LETOR3.0作為測(cè)試數(shù)據(jù)集，以方便比較不同算法的排序性能。

4.2 性能測(cè)試結(jié)果

本文通過(guò)相同的交叉驗(yàn)證方案對(duì)不同的算法進(jìn)行排序性能測(cè)試。為了評(píng)估檢索性能，采用書(shū)目檢索領(lǐng)域中廣泛使用的性能評(píng)價(jià)指標(biāo)MAP和NDCG。一方面，在線學(xué)習(xí)排序算法僅與pairwise算法相結(jié)合,因此，本文選取了pairwise類(lèi)典型算法RankSVM和online-pairwise類(lèi)典型算法OGDR作比較。另一方面，由于online-listwise算法采用了自適應(yīng)學(xué)習(xí)率使排序模型的結(jié)果更加精準(zhǔn)和更快收斂，因此本文將基于Adam算法進(jìn)行學(xué)習(xí)率更新的online-listwise算法和采用自適應(yīng)學(xué)習(xí)率的online-listwise算法進(jìn)行了比較。本文最后測(cè)試了listwise、online-listwise、RankSVM、Adam和OGDR算法的排序性能。首先測(cè)試了上述幾種算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的性能評(píng)價(jià)指標(biāo)MAP，結(jié)果如表2所示。根據(jù)表2可以得出以下結(jié)論：

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

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

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

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

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

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

Figure 2 Cumulative time consumption on CPU圖2 CPU累計(jì)時(shí)間消耗

5 結(jié)束語(yǔ)

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