謝　彬,　唐健常,　唐新懷

(1.南京理工大學 計算機科學與工程學院， 南京 210094; 2.中國電子科技集團公司第三十二研究所,上海 200233; 3.上海交通大學 軟件學院, 上海 200240)

?

基于排序學習的混合推薦算法

謝彬1,2,唐健常3,唐新懷3

(1.南京理工大學 計算機科學與工程學院， 南京 210094; 2.中國電子科技集團公司第三十二研究所,上海 200233; 3.上海交通大學 軟件學院, 上海 200240)

為了解決推薦系統(tǒng)如何適應不同的應用場景,以及推薦結果的排序問題,提出以Boosting合并算法為基礎模型,以LambdaMART算法為主的更新算法,將排序學習技術運用于混合推薦?；谟脩舴答佇畔⒌膶崟r更新排序模型,通過學習不同場景中的不同數(shù)據(jù),使推薦系統(tǒng)能夠適用于不同的應用場景。同時，基于排序評價指標NDCG對混合推薦模型進行了驗證。

排序學習; 混合推薦; Boosting合并算法; LambdaMART算法; NDCG

0　引　言

推薦系統(tǒng)已經(jīng)在眾多領域和行業(yè)中被廣泛地應用,通過十多年的比較與實踐,隨著推薦需求的變化與推薦質量要求的提高,單一的推薦算法由于自身的缺陷,已經(jīng)無法滿足當今需求,學者們提出了混合推薦。

混合推薦[1]是指綜合使用多種推薦技術,使多種算法能夠揚長避短,讓推薦效果得到提升。文獻[2]提出一個相似度混合模型,將用戶相似度和物品相似度統(tǒng)一起來,能夠充分利用用戶評分矩陣中的信息進行推薦。文獻[3]提出一種基于內容的協(xié)同過濾方法,該算法分析并使用顯式數(shù)據(jù)和隱式數(shù)據(jù)進行推薦,解決了冷啟動問題并降低了計算量和復雜度。文獻[4-5]采用線性公式按照一定權重累加合并幾種的推薦,從而讓推薦效果得到提高。Netflix Prize的獲獎算法[6]混合了107種推薦的模型與算法,混合后的推薦效果非常優(yōu)秀。

筆者將排序學習技術[7]運用到混合推薦系統(tǒng)中來。把各個基礎推薦算法的推薦結果作為弱排序器,并使用Boosting合并算法合并出基礎排序模型,然后利用用戶反饋信息,以LambdaMART算法[8]為更新算法生成實時的綜合排序模型,使它的推薦結果在排序評價指標NDCG[9]上表現(xiàn)優(yōu)秀。同時,通過學習不同場景的不同數(shù)據(jù),使得系統(tǒng)能夠適用于不同的應用場景。

1　Boosting合并算法

文獻[10]提出了RankBoost算法,將多個弱排序器線性疊加,并用順序實例對集合通過Boosting方法訓練學習后,給出一個全局的排序。文獻[11]提出了AdaRank方法,通過多次構造弱排序器,并將其結果合并成最終的排序,同時使用AdaBoost方法直接對基于排序的評價指標的損失函數(shù)進行優(yōu)化。

文中參考這兩種方法,根據(jù)混合推薦的特殊情況,把各個基礎推薦算法的推薦結果作為弱排序器,并使用Boosting的方法將它們合并成一個排序模型。

(1)

根據(jù)NDCG的計算公式,可知當兩個實例之間的順序發(fā)生改變時,NDCG的值也跟著變化。設這兩個實例為i和j,可知當Si=Sj,這兩個實例的順序就將發(fā)生改變,此時NDCG值也將改變。將式(1)代入,即可計算此時的α值:

(2)

因此,只要枚舉所有可以令NDCG值發(fā)生改變的α值,即可據(jù)此計算出NDCG所有的可能值。同時可以容易的證明:對于只有兩個實例相等而產(chǎn)生的α值,NDCG值改變時,必然是相鄰兩個實例之間的位置互換;而對于多個實例相等而產(chǎn)生的α值,改變位置的實例也必然是連續(xù)的。因為如果位置改變的實例之間還有其他實例,那么必然在更小的α值時已經(jīng)與這些實例中的至少一個發(fā)生位置變換,這時該實例的位置已經(jīng)不再這些實例之間了。

然后需要將各個基礎推薦算法的推薦結果作為弱排序器,并進行類似歸一化的處理,使其所得的分數(shù)能夠方便地用于NDCG值的計算中。

根據(jù)式(2)計算所有可能的α值,并將α值排序,然后從小到大計算所有可能的NDCG值。NDCG值計算方法如下:

(3)

式中:t——第t個α值;

It——在此α值相交的實例集;

Si,t——此時實例i的分數(shù);

ri,t——此時實例i的在序列中的位置。

但是,上面的NDCG值只是一個請求的NDCG值。因此,對于多個請求,可以將全部請求的所有可能的α值計算并排序,然后從大到小,計算對應的NDCG值的改變。于是就可以選擇使得NDCG的均值最大的α值作為這兩個弱排序器的合并參數(shù)。

(4)

使用上述方法來合并多個弱排序器,合并多個弱排序器的Boosting模型:

(5)

式中:x——實例的輸入特征;

hi——弱排序器。

根據(jù)上述方法α值計算,相比RankBoost算法,無需計算實例對權重分布值,使得此算法的計算量大大降低。

通過限制弱排序器的數(shù)量來防止過度擬合,同時這樣也減少了計算量?？梢灾匦掠嬎闼械摩羒,并在計算時固定其他的α不變。于是每次計算都是在最優(yōu)化兩個弱排序器的合并,同時保證每次迭代NDCG值是單調不減的,并設置Δαi的閥值,小于此閥值則不再計算。通過這種方式,而不是引入學習速率,就可以極大的減少計算量。

這種合并方法可以適用于任意的弱排序器,不論這些弱排序器或者訓練數(shù)據(jù)與方法是否有聯(lián)系。同時這種合并方法迭代次數(shù)少,訓練速度較快。于是,可以將各個推薦算法的推薦結果進行歸一化后作為弱排序器,并使用這種Boosting合并算法獲得合并后的基礎排序模型。

2　LambdaMART更新算法

Boosting合并算法通過最優(yōu)化NDCG值的方法,迭代的將弱排序器合并在一起,形成了一個合并后的排序器。然而通過最優(yōu)化NDCG值的方法將用戶的喜好視為了一個整體,因此當有用戶新的行為出現(xiàn),反映用戶的變化時,只能重新進行一次Boosting合并算法。但是這樣既需要大量的時間重新學習訓練,又浪費了過去已經(jīng)計算過的數(shù)據(jù)。因此需要一種能夠基于用戶反饋信息的更新算法。

LambdaMART算法是LambdaRank算法[12]使用MART的版本,其中Lambda是MART求解過程使用的梯度。而LambdaRank算法又是在RankNet算法[13]的基礎上改進而來。

MART是一種迭代的決策樹算法,該算法通過構建多棵回歸樹,并將所有樹的結論累加做最終輸出結果。其核心就在于,每一棵回歸樹學習的目標是最終學習目標與之前所有樹結論累加的差距,即殘差。因此LambdaMART算法可以支持增量學習,能夠使用上Boosting合并算法的輸出。

觀察LambdaMART算法的迭代過程,可以發(fā)現(xiàn)每次學習一棵回歸樹時,最重要的也是最開始的步驟就是計算λi。因為之后所有的計算步驟都需要使用到λi,包括構建當次迭代的回歸樹,也是據(jù)此進行分類創(chuàng)建的。它的計算公式為

(6)

于是，計算λi可以分為兩個部分:確定實例對下標集合I所包含的元素;計算對應λij的值。

根據(jù)LambdaMART算法的具體過程,可知λij的計算公式:

(7)

其中Si可以通過之前迭代的結論累加Ft-1(xi)計算得來。ΔNDCGij為實例i和實例j交換順序后的NDCG值變化量。

(8)

式中:pi——實例i的位置;

pj——實例j的位置;

Z——歸一化常量。

這時只需要確定實例對下標集合I所包含的元素,就可能很容易的計算對應的λij值了。而已經(jīng)知道Boosting合并算法輸出的排序器能夠在不考慮用戶新增的反饋信息的情況在,在NDCG指標上給出令人滿意的結果。于是將此排序器作為LambdaMART算法的基礎模型時,LambdaMART算法之后迭代的殘差,即回歸樹的學習目標就是最終排序與Boosting合并模型排序之間的差距。這部分差距顯然是用戶新增的反饋信息產(chǎn)生的,所以在LambdaMART算法的迭代中,只需要考慮用戶新增的反饋信息即可。于是實例對下標集合I的元素為用戶新增的反饋信息所包含的有序實例對的下標。

此時,已經(jīng)有了基于用戶反饋信息的更新算法,但是這個算法還有兩個問題需要解決:

第一,隨著用戶反饋信息的不斷增多,如何保證LambdaMART算法不斷迭代的回歸樹的數(shù)量。因為如果回歸樹的數(shù)量增多,就意味著最終輸出的排序器變得復雜,計算量增大,從而不能夠保證移動環(huán)境下的即時性需求。

第二,當有用戶新的反饋信息時,如何快速訓練使得新的反饋信息能夠快速的反映到最終輸出的排序器上,使得用戶能夠最快地感受到系統(tǒng)對他的操作、行為的反饋。

第一個問題比較容易解決,因為它沒有實時性的要求。因此可以在反饋信息產(chǎn)生的實例對下標集合I的元素數(shù)量大于某個閥值或者回歸樹的數(shù)量大于某個閥值時,重新進行Boosting合并算法,更新LambdaMART算法的基礎模型。這樣就能讓迭代的回歸樹的數(shù)量變?yōu)?,同時實例對下標集合I變?yōu)榭占?。當然沒有必要一大于閥值就立刻重新訓練,因為這樣會影響用戶的體驗,完全可以等到凌晨,沒有用戶使用系統(tǒng)的時候在進行這部分計算。同樣也可以在無用戶使用系統(tǒng)的時,即使為達到閥值也重新訓練,這樣能夠減少第二天最終輸出的排序器的計算量,從而減少系統(tǒng)的響應時間，可以將這種更新歸類于大批量數(shù)據(jù)的更新。

第二個問題的解決,則需要繼續(xù)將更新的數(shù)據(jù)量范圍進行劃分,分為小批量數(shù)據(jù)的更新和實時數(shù)據(jù)的更新。具體方法為每當有新的用戶反饋信息時,將其加入實例對下標臨時集合It中,并用這個臨時集合It迭代出一棵臨時的回歸樹。由于只需要進行一次迭代,而且一次迭代中需要計算的實例對數(shù)量|It|也不大,因此能夠較快的完成這個迭代任務。而當|It|大于某個閥值時,就可以將It合并入I中,將It清空,接著進行T次迭代,將產(chǎn)生的回歸樹加入到累加函數(shù)中。這時雖然I較大,一次迭代時間大于實時更新的那次迭代,但是小批量數(shù)據(jù)的更新,對實時性的要求已經(jīng)沒有那么高了。

將Boosting合并算法的輸出作為基礎模型,并使用LambdaMART算法為更新算法,相比無基礎模型直接使用LambdaMART算法具有如下幾點優(yōu)勢:

第一,Boosting合并算法的迭代次數(shù)和單次迭代的計算量遠少于直接使用LambdaMART算法的方法,因此大大節(jié)省了訓練的時間。

第二,Boosting合并算法的輸出函數(shù)形式更簡潔,能夠簡化最終的排序器,因此在即時推薦時,系統(tǒng)的響應也能更快。

第三,LambdaMART算法每次迭代計算時間是隨著隨著用戶反饋數(shù)據(jù)的增加。而Boosting合并算法作為基礎模型就完全沒有這個問題。

3　實驗與分析

文中選用兩個數(shù)據(jù)集:HetRec 2011的Last.FM數(shù)據(jù)集和HetRec 2011的MovieLens數(shù)據(jù)集。

Last.FM數(shù)據(jù)集包含了歌手信息,標簽信息,用戶收聽歌手的計數(shù),用戶社交信息以及用戶對歌手打標簽的記錄。MovieLens數(shù)據(jù)集包含了電影信息,標簽信息,用戶對電影的評分記錄以及用戶對電影打標簽的記錄。這兩個數(shù)據(jù)集的統(tǒng)計信息如表1所示。

表1　數(shù)據(jù)集統(tǒng)計信息

3.1Boosting合并算法的評測

基于MovieLens數(shù)據(jù)集,以8∶2的比例將數(shù)據(jù)集分為兩個部分,大的部分為訓練數(shù)據(jù),小的部分為測試數(shù)據(jù)。對Boosting合并算法的排序結果與沒有使用排序學習方法的原始方法排序的綜合推薦結果進行訓練與測試比較。這里原始方法排序的綜合推薦結果是將各個推薦算法結果列表的前幾名按順序合并成最終的推薦結果列表。使用NDCG這個評價指標對上述的兩個排序結果進行比較,為方便比較了NDCG@3和NDCG@9和NDCG@15這三個指標,如表2所示。

表2　Boosting合并算法的評測結果

從2表中發(fā)現(xiàn),Boosting合并算法在NDCG指標上的表現(xiàn)均要好于原始合并排序方法。

3.2用戶反饋信息更新算法的評測

基于MovieLens數(shù)據(jù)集,以7∶1∶2的比例將數(shù)據(jù)集分為三個部分,其中只占1份的數(shù)據(jù)為更新數(shù)據(jù)。為方便測試將部分的用戶評分記錄轉化為用戶反饋信息。對只用Boosting合并的算法和將Boosting合并算法作為基礎模型的更新算法進行訓練與測試比較。這里的更新算法是指上文提到的小批量更新算法,沒有使用實時更新算法的原因是訓練時的用戶反饋信息是批量傳遞給更新算法的。

從表3中發(fā)現(xiàn),更新算法是有意義的,它能夠在NDCG指標上的表現(xiàn)更好。同時與表二的Boosting合并算法的測試結果比較,發(fā)現(xiàn)加入更新信息后NDCG值也會加大。這意味著大批量更新也是有必要的。

表3　更新算法的評測結果

3.3Boosting與LambdaMART的算法比較

基于MovieLens數(shù)據(jù)集,對Boosting合并算法和直接使用的LambdaMART算法進行訓練與測試比較。純LambdaMART算法是指將所有的用戶評分轉化為實例對順序,并在沒有基礎模型的情況下直接使用LambdaMART算法多次迭代訓練出的排序算法。使用NDCG@9這個評價指標對上述的兩個排序結果進行比較,并記錄了不同迭代次數(shù)對這兩個排序算法的影響,如圖1所示。

圖1　迭代次數(shù)的影響

由圖1可見,Boosting合并算法只需要30多次迭代,就能夠在NDCG@9這個評價指標上達到訓練的最佳效果。而無基礎模型的LambdaMART算法則需要200多次。同時Boosting合并算法的訓練效果略優(yōu)于LambdaMART算法。

3.4不同數(shù)據(jù)集模擬不同場景情況的測試

基于MovieLens數(shù)據(jù)集和Last.FM數(shù)據(jù)集,將這兩個數(shù)據(jù)集作為不同場景的數(shù)據(jù)分別對Boosting合并算法進行訓練。同時在訓練Last.FM數(shù)據(jù)集時,啟用基于社會化的推薦算法。評測結果見表4。

表4　不同場景下的評測結果

由表4可知，Boosting合并算法在不同的訓練集下都能夠在NDCG指標上有較好的表現(xiàn)。

4　結束語

將排序學習技術運用到混合推薦系統(tǒng)中，通過學習不同場景的不同數(shù)據(jù),系統(tǒng)能夠適用于不同的應用場景。以Boosting合并算法為基礎模型、LambdaMART算法為更新算法的排序學習技術,排序模型能夠基于用戶反饋信息實現(xiàn)實時更新。實驗驗證顯示，該方法的推薦結果列表能夠在排序評價指標NDCG上表現(xiàn)優(yōu)秀。

[1]BURKE R. Hybrid recommender systems: survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370.

[2]WANG J, DE VRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion[C]//Proceedings of the 29th annual international ACM SIGIR conference on research and development in information retrieval. ACM, 2006: 501-508.

[3]CREMONESI P, TURRIN R, AIROLDI F. Hybrid algorithms for recommending new items[C]//Proceedings of the 2nd international workshop on information heterogeneity and fusion in recommender systems. ACM, 2011: 33-40.

[4]MIRANDA T, CLAYPOOL M, GOKHALE A, et al. Combining content-based and collaborative filters in an online newspaper[C]//In Proceedings of ACM SIGIR Workshop on Recommender Systems. ACM, 1999: 56-60.

[5]PAZZANI M J. A framework for collaborative, content-based and demographic filtering[J]. Artificial Intelligence Review, 1999, 13(5/6): 393-408.

[6]BELL R M, KOREN Y, VOLINSKY C. The bellkor solution to the netflix prize[J]. SIGKDD Explorations, 2007(9): 80-84.

[7]LIU T Y. Learning to rank for information retrieval[J]. Foundations and Trends in Information Retrieval, 2009, 3(3): 225-331.[8]BURGES C J C. From ranknet to lambdarank to lambdamart: An overview[J]. Learning, 2010(11): 23-581.

[9]WANG YINING, WANG LIWEI, LI YUANZHI, et al. A Theoretical analysis of normalized discounted cumulative gain (NDCG) ranking measures[C]//JMLR: Workshop and Conference Proceedings, 2013: 1-30.

[10]XU J, LI H. Adarank: a boosting algorithm for information retrieval[C]//Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2007: 391-398.

[11]PLATT T, HOMFMAN. Learning to rank with nonsmooth cost functions[J]. Learning, 2010(10): 23-581. 193-200.

[12]BURGES C, SHAKED T, RENSHAW E, et al. Learning to rank using gradient descent[C]//Proceedings of the 22nd international conference on Machine learning. ACM, 2005: 89-96.

[13]FREUND Y, IYER R, SCHAPIRE R E, et al. An efficient boosting algorithm for combining preferences[J]. The Journal of machine learning research, 2003(4): 933-969.

(編輯李德根)

Hybrid recommendation base on learning to rank

XIEBin1,2,TANGJianchang3,TANGXinhuai3

(1.College of Computer Science & Engineering, Nanjing University of Science & Technology, Nanjing 210094, China; 2.The Thirty-Second Research Institute of China Electronic Technology Group Corporation, Shanghai 200233, China; 3.School of Software, Shanghai Jiaotong University, Shanghai 200240, China)

This paper is a study of the way recommender system is adapted to different scenarios and the ranking of recommendation result. The paper proposes a hybrid recommendation algorithm which works by using boosting merging algorithm as the base model, applying LambdaMART update algorithm based on user feedback information and using ranking learning technology. The study is validated by the verification of the corresponding hybrid recommendation model using ranking evaluation index NDCG.

learning to rank; hybrid recommendation; boosting merging algorithm; lambdaMART algorithm; NDCG

2015-06-26

謝彬(1976-),男,湖南省衡陽人，高級工程師,博士研究生,研究方向:計算機基礎、軟件云計算、大數(shù)據(jù)應用,E-mail:xiebin-sh@163.com。

10.3969/j.issn.2095-7262.2015.04.018

TP181

2095-7262(2015)04-0445-05

A