基于排序学习的混合推荐算法

谢　彬,　唐健常,　唐新怀

(1.南京理工大学 计算机科学与工程学院， 南京 210094; 2.中国电子科技集团公司第三十二研究所,上海 200233; 3.上海交通大学 软件学院, 上海 200240)



基于排序学习的混合推荐算法

谢彬1,2,唐健常3,唐新怀3

(1.南京理工大学 计算机科学与工程学院， 南京 210094; 2.中国电子科技集团公司第三十二研究所,上海 200233; 3.上海交通大学 软件学院, 上海 200240)

为了解决推荐系统如何适应不同的应用场景,以及推荐结果的排序问题,提出以Boosting合并算法为基础模型,以LambdaMART算法为主的更新算法,将排序学习技术运用于混合推荐。基于用户反馈信息的实时更新排序模型,通过学习不同场景中的不同数据,使推荐系统能够适用于不同的应用场景。同时，基于排序评价指标NDCG对混合推荐模型进行了验证。

排序学习; 混合推荐; Boosting合并算法; LambdaMART算法; NDCG

0　引　言

推荐系统已经在众多领域和行业中被广泛地应用,通过十多年的比较与实践,随着推荐需求的变化与推荐质量要求的提高,单一的推荐算法由于自身的缺陷,已经无法满足当今需求,学者们提出了混合推荐。

混合推荐[1]是指综合使用多种推荐技术,使多种算法能够扬长避短,让推荐效果得到提升。文献[2]提出一个相似度混合模型,将用户相似度和物品相似度统一起来,能够充分利用用户评分矩阵中的信息进行推荐。文献[3]提出一种基于内容的协同过滤方法,该算法分析并使用显式数据和隐式数据进行推荐,解决了冷启动问题并降低了计算量和复杂度。文献[4-5]采用线性公式按照一定权重累加合并几种的推荐,从而让推荐效果得到提高。Netflix Prize的获奖算法[6]混合了107种推荐的模型与算法,混合后的推荐效果非常优秀。

笔者将排序学习技术[7]运用到混合推荐系统中来。把各个基础推荐算法的推荐结果作为弱排序器,并使用Boosting合并算法合并出基础排序模型,然后利用用户反馈信息,以LambdaMART算法[8]为更新算法生成实时的综合排序模型,使它的推荐结果在排序评价指标NDCG[9]上表现优秀。同时,通过学习不同场景的不同数据,使得系统能够适用于不同的应用场景。

1　Boosting合并算法

文献[10]提出了RankBoost算法,将多个弱排序器线性叠加,并用顺序实例对集合通过Boosting方法训练学习后,给出一个全局的排序。文献[11]提出了AdaRank方法,通过多次构造弱排序器,并将其结果合并成最终的排序,同时使用AdaBoost方法直接对基于排序的评价指标的损失函数进行优化。

文中参考这两种方法,根据混合推荐的特殊情况,把各个基础推荐算法的推荐结果作为弱排序器,并使用Boosting的方法将它们合并成一个排序模型。

(1)

根据NDCG的计算公式,可知当两个实例之间的顺序发生改变时,NDCG的值也跟着变化。设这两个实例为i和j,可知当Si=Sj,这两个实例的顺序就将发生改变,此时NDCG值也将改变。将式(1)代入,即可计算此时的α值:

(2)

因此,只要枚举所有可以令NDCG值发生改变的α值,即可据此计算出NDCG所有的可能值。同时可以容易的证明:对于只有两个实例相等而产生的α值,NDCG值改变时,必然是相邻两个实例之间的位置互换;而对于多个实例相等而产生的α值,改变位置的实例也必然是连续的。因为如果位置改变的实例之间还有其他实例,那么必然在更小的α值时已经与这些实例中的至少一个发生位置变换,这时该实例的位置已经不再这些实例之间了。

然后需要将各个基础推荐算法的推荐结果作为弱排序器,并进行类似归一化的处理,使其所得的分数能够方便地用于NDCG值的计算中。

根据式(2)计算所有可能的α值,并将α值排序,然后从小到大计算所有可能的NDCG值。NDCG值计算方法如下:

(3)

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

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

Si,t——此时实例i的分数;

ri,t——此时实例i的在序列中的位置。

但是,上面的NDCG值只是一个请求的NDCG值。因此,对于多个请求,可以将全部请求的所有可能的α值计算并排序,然后从大到小,计算对应的NDCG值的改变。于是就可以选择使得NDCG的均值最大的α值作为这两个弱排序器的合并参数。

(4)

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

(5)

式中:x——实例的输入特征;

hi——弱排序器。

根据上述方法α值计算,相比RankBoost算法,无需计算实例对权重分布值,使得此算法的计算量大大降低。

通过限制弱排序器的数量来防止过度拟合,同时这样也减少了计算量。可以重新计算所有的αi,并在计算时固定其他的α不变。于是每次计算都是在最优化两个弱排序器的合并,同时保证每次迭代NDCG值是单调不减的,并设置Δαi的阀值,小于此阀值则不再计算。通过这种方式,而不是引入学习速率,就可以极大的减少计算量。

这种合并方法可以适用于任意的弱排序器,不论这些弱排序器或者训练数据与方法是否有联系。同时这种合并方法迭代次数少,训练速度较快。于是,可以将各个推荐算法的推荐结果进行归一化后作为弱排序器,并使用这种Boosting合并算法获得合并后的基础排序模型。

2　LambdaMART更新算法

Boosting合并算法通过最优化NDCG值的方法,迭代的将弱排序器合并在一起,形成了一个合并后的排序器。然而通过最优化NDCG值的方法将用户的喜好视为了一个整体,因此当有用户新的行为出现,反映用户的变化时,只能重新进行一次Boosting合并算法。但是这样既需要大量的时间重新学习训练,又浪费了过去已经计算过的数据。因此需要一种能够基于用户反馈信息的更新算法。

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

MART是一种迭代的决策树算法,该算法通过构建多棵回归树,并将所有树的结论累加做最终输出结果。其核心就在于,每一棵回归树学习的目标是最终学习目标与之前所有树结论累加的差距,即残差。因此LambdaMART算法可以支持增量学习,能够使用上Boosting合并算法的输出。

观察LambdaMART算法的迭代过程,可以发现每次学习一棵回归树时,最重要的也是最开始的步骤就是计算λi。因为之后所有的计算步骤都需要使用到λi,包括构建当次迭代的回归树,也是据此进行分类创建的。它的计算公式为

(6)

于是，计算λi可以分为两个部分:确定实例对下标集合I所包含的元素;计算对应λij的值。

根据LambdaMART算法的具体过程,可知λij的计算公式:

(7)

其中Si可以通过之前迭代的结论累加Ft-1(xi)计算得来。ΔNDCGij为实例i和实例j交换顺序后的NDCG值变化量。

(8)

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

pj——实例j的位置;

Z——归一化常量。

这时只需要确定实例对下标集合I所包含的元素,就可能很容易的计算对应的λij值了。而已经知道Boosting合并算法输出的排序器能够在不考虑用户新增的反馈信息的情况在,在NDCG指标上给出令人满意的结果。于是将此排序器作为LambdaMART算法的基础模型时,LambdaMART算法之后迭代的残差,即回归树的学习目标就是最终排序与Boosting合并模型排序之间的差距。这部分差距显然是用户新增的反馈信息产生的,所以在LambdaMART算法的迭代中,只需要考虑用户新增的反馈信息即可。于是实例对下标集合I的元素为用户新增的反馈信息所包含的有序实例对的下标。

此时,已经有了基于用户反馈信息的更新算法,但是这个算法还有两个问题需要解决:

第一,随着用户反馈信息的不断增多,如何保证LambdaMART算法不断迭代的回归树的数量。因为如果回归树的数量增多,就意味着最终输出的排序器变得复杂,计算量增大,从而不能够保证移动环境下的即时性需求。

第二,当有用户新的反馈信息时,如何快速训练使得新的反馈信息能够快速的反映到最终输出的排序器上,使得用户能够最快地感受到系统对他的操作、行为的反馈。

第一个问题比较容易解决,因为它没有实时性的要求。因此可以在反馈信息产生的实例对下标集合I的元素数量大于某个阀值或者回归树的数量大于某个阀值时,重新进行Boosting合并算法,更新LambdaMART算法的基础模型。这样就能让迭代的回归树的数量变为0,同时实例对下标集合I变为空集。当然没有必要一大于阀值就立刻重新训练,因为这样会影响用户的体验,完全可以等到凌晨,没有用户使用系统的时候在进行这部分计算。同样也可以在无用户使用系统的时,即使为达到阀值也重新训练,这样能够减少第二天最终输出的排序器的计算量,从而减少系统的响应时间，可以将这种更新归类于大批量数据的更新。

第二个问题的解决,则需要继续将更新的数据量范围进行划分,分为小批量数据的更新和实时数据的更新。具体方法为每当有新的用户反馈信息时,将其加入实例对下标临时集合It中,并用这个临时集合It迭代出一棵临时的回归树。由于只需要进行一次迭代,而且一次迭代中需要计算的实例对数量|It|也不大,因此能够较快的完成这个迭代任务。而当|It|大于某个阀值时,就可以将It合并入I中,将It清空,接着进行T次迭代,将产生的回归树加入到累加函数中。这时虽然I较大,一次迭代时间大于实时更新的那次迭代,但是小批量数据的更新,对实时性的要求已经没有那么高了。

将Boosting合并算法的输出作为基础模型,并使用LambdaMART算法为更新算法,相比无基础模型直接使用LambdaMART算法具有如下几点优势:

第一,Boosting合并算法的迭代次数和单次迭代的计算量远少于直接使用LambdaMART算法的方法,因此大大节省了训练的时间。

第二,Boosting合并算法的输出函数形式更简洁,能够简化最终的排序器,因此在即时推荐时,系统的响应也能更快。

第三,LambdaMART算法每次迭代计算时间是随着随着用户反馈数据的增加。而Boosting合并算法作为基础模型就完全没有这个问题。

3　实验与分析

文中选用两个数据集:HetRec 2011的Last.FM数据集和HetRec 2011的MovieLens数据集。

Last.FM数据集包含了歌手信息,标签信息,用户收听歌手的计数,用户社交信息以及用户对歌手打标签的记录。MovieLens数据集包含了电影信息,标签信息,用户对电影的评分记录以及用户对电影打标签的记录。这两个数据集的统计信息如表1所示。

表1　数据集统计信息

3.1Boosting合并算法的评测

基于MovieLens数据集,以8∶2的比例将数据集分为两个部分,大的部分为训练数据,小的部分为测试数据。对Boosting合并算法的排序结果与没有使用排序学习方法的原始方法排序的综合推荐结果进行训练与测试比较。这里原始方法排序的综合推荐结果是将各个推荐算法结果列表的前几名按顺序合并成最终的推荐结果列表。使用NDCG这个评价指标对上述的两个排序结果进行比较,为方便比较了NDCG@3和NDCG@9和NDCG@15这三个指标,如表2所示。

表2　Boosting合并算法的评测结果

从2表中发现,Boosting合并算法在NDCG指标上的表现均要好于原始合并排序方法。

3.2用户反馈信息更新算法的评测

基于MovieLens数据集,以7∶1∶2的比例将数据集分为三个部分,其中只占1份的数据为更新数据。为方便测试将部分的用户评分记录转化为用户反馈信息。对只用Boosting合并的算法和将Boosting合并算法作为基础模型的更新算法进行训练与测试比较。这里的更新算法是指上文提到的小批量更新算法,没有使用实时更新算法的原因是训练时的用户反馈信息是批量传递给更新算法的。

从表3中发现,更新算法是有意义的,它能够在NDCG指标上的表现更好。同时与表二的Boosting合并算法的测试结果比较,发现加入更新信息后NDCG值也会加大。这意味着大批量更新也是有必要的。

表3　更新算法的评测结果

3.3Boosting与LambdaMART的算法比较

基于MovieLens数据集,对Boosting合并算法和直接使用的LambdaMART算法进行训练与测试比较。纯LambdaMART算法是指将所有的用户评分转化为实例对顺序,并在没有基础模型的情况下直接使用LambdaMART算法多次迭代训练出的排序算法。使用NDCG@9这个评价指标对上述的两个排序结果进行比较,并记录了不同迭代次数对这两个排序算法的影响,如图1所示。

图1　迭代次数的影响

由图1可见,Boosting合并算法只需要30多次迭代,就能够在NDCG@9这个评价指标上达到训练的最佳效果。而无基础模型的LambdaMART算法则需要200多次。同时Boosting合并算法的训练效果略优于LambdaMART算法。

3.4不同数据集模拟不同场景情况的测试

基于MovieLens数据集和Last.FM数据集,将这两个数据集作为不同场景的数据分别对Boosting合并算法进行训练。同时在训练Last.FM数据集时,启用基于社会化的推荐算法。评测结果见表4。

表4　不同场景下的评测结果

由表4可知，Boosting合并算法在不同的训练集下都能够在NDCG指标上有较好的表现。

4　结束语

将排序学习技术运用到混合推荐系统中，通过学习不同场景的不同数据,系统能够适用于不同的应用场景。以Boosting合并算法为基础模型、LambdaMART算法为更新算法的排序学习技术,排序模型能够基于用户反馈信息实现实时更新。实验验证显示，该方法的推荐结果列表能够在排序评价指标NDCG上表现优秀。

[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-),男,湖南省衡阳人，高级工程师,博士研究生,研究方向:计算机基础、软件云计算、大数据应用,E-mail:xiebin-sh@163.com。

10.3969/j.issn.2095-7262.2015.04.018

TP181

2095-7262(2015)04-0445-05

A