何炜俊，艾丹祥

(广东工业大学 管理学院，广州 510520)

E-mail ：china072547@vip.qq.com

1 引 言

推荐系统(Recommender Systems，RS)通过分析用户记录(User Profile)和商品属性(Item Attribute)的关系，达到过滤冗余内容的目的，能有效应对信息过载问题.众所周知，基于近邻的协同过滤(Neighborhood-based Collaborative Filtering，CF)是最常见的推荐技术.该技术有两种类型：基于用户的方法(UserCF)和基于商品的方法(ItemCF).其核心都是根据历史交易记录寻找相似的用户或商品.CF假设：用户兴趣和商品属性都是相对静止的.比如，用户过去喜欢什么，将来也喜欢什么；歌曲过去很流行，将来也很流行.该假设限制了以CF为基础的推荐模型在现实生活的高效应用：无法长期地准确匹配用户需求和商品属性.

在此背景下，以多臂赌博机(Multi-armed Bandits，MAB)建模的互动式推荐系统应运而生[1].MAB推荐具有以下几个特点：1)连续互动，即用户对推荐结果产生反馈，而系统根据反馈信息实时改进预测策略(比如，发现新兴趣).此过程周而复始；2)隐式互动，即用户很少会直接对商品评分，取而代之的是点击、购买或订阅等隐式行为；3)稀疏互动，即大多数用户都不会频繁地与系统进行互动，因此推荐次数是有限的.MAB是强化学习的经典范例，属于开发-探索(Exploitation & Exploration，EE)策略.开发(Exploitation)是利用现有反馈信息，从已知商品中选择期望收益最高的进行推荐；探索(Exploration)是不依赖现有反馈信息，去发现期望收益更高的未知(新)商品.然而开发和探索是相互冲突的，过度的开发会陷入局部最优解，过度的探索则会浪费有限的推荐机会.因此只有权衡开发和探索，才能获得长期的最佳推荐效果.

现有的MAB推荐算法能有效地应对在线场景下的动态推荐问题.然而，这类研究大多以改进推荐准确性(Accuracy)为首要目标.“以预测精度为中心”的推荐模型往往会牺牲推荐结果的多样性(Diversity)和新颖性(Novelty)[2]，Adomavicius通过定量实验表明，过度地改进预测精度会大幅度地降低推荐多样性和新颖性[16].这种推荐系统从越来越狭窄的范围内挑选商品(如热门商品)，使推荐结果的信息效用降低，很难给用户营造新鲜的体验感[3]，甚至还会使用户感到厌烦[4].相反，较高的多样性和新颖性的推荐结果能有效地提升用户的体验满意度和忠诚度[5]，增加商品销售额和销售种类[6]，还能避免推荐系统产生过度专门化(Overspecialized)问题[7].因此，多样性和新颖性同样应该作为有效推荐的目标[8].

图1 “用户-系统”互动式推荐过程Fig.1 Interactive recommendations of users and systems

针对上述问题，本文提出一种基于MAB的多目标互动式推荐系统，旨在产生兼顾准确性、多样性和新颖性的商品推荐列表.该推荐系统的互动推荐过程如图1所示.首先，构建考虑推荐准确度、多样度和新颖度的标量函数，以此挑选若干个加权期望收益较高的候选商品组成推荐列表，展示给目标用户.之后，用户对推荐列表做出反馈(如点击、购买或订阅等)，系统则根据反馈信息更新多目标推荐模型，并为用户产生新的推荐列表.“用户-系统”的互动式推荐过程不断循环，使系统能够及时适应用户兴趣和物品属性的变化，提供兼顾准确性、多样性和新颖性的推荐服务.

2 相关研究

2.1 多目标推荐研究

将多目标决策分析(Multiple Objective Decision Making，MODM)方法应用于推荐系统是有价值的，详细表述参见文献[9].厍向阳等提出一种多目标的混合推荐系统，并行混合了7种子推荐算法，再用遗传算法挑选加权准确度、多样度和新颖度较优的商品[10]；Chai通过结合Pareto最优法和Promethee多准则决策法，提出一种多目标免疫优化推荐算法，旨在产生准确、多样和新颖的结果[11]；Cai提出基于适应性评估(GBFE)和分割知识挖掘(PBKM)策略的多目标推荐算法(MaOEAs)，旨在提升推荐精确率、召回率、覆盖率、多样度和新颖度[12]；等等.

然而，上述研究成果构建的多目标推荐系统均不具有实时性，其模型和数据源都是离线的(在推荐之前建立)，无法及时接收用户的反馈，无法适应用户兴趣和商品属性的动态变化.

2.2 基于多臂赌博机的推荐研究

基于MAB的推荐系统被广泛应用于现实生活中在线或上下文敏感的推荐平台，如电商Amazon、新闻Google News和流媒体YouTube等等.基于此，MAB推荐自然也受到众多学者的关注.比如，成石等提出融合矩阵分解和MAB的推荐系统，分析商品实际评分和预测评分的偏差，以矩阵分解技术求得用户和商品的属性，并对上述的属性使用MAB完成推荐[13]；王高智等提出基于内容和协同过滤的MAB推荐系统，综合考虑内容和用户相似度，结合最近邻算法，以用户和近邻用户的反馈信息进行MAB推荐[14]；Wang等提出结合MAB的互动式协同过滤推荐算法，先在离线情况下使用潜在狄利克雷(LDA)主题技术为商品聚类，然后在MAB推荐中使用粒子学习(Particle Learning)技术改进商品相似度的计算方式，使在线推荐结果更准确[15]；等等.

然而上述MBA推荐系统也存在一些缺陷，包括：1) 只关注改进推荐的准确性指标(如精确率、召回率和平均绝对误差等)，却未提及其他重要推荐指标(如多样度和新颖度等)；2) 在一次推荐中，一个MAB只能动态推荐一个商品，也只能收集一个反馈信息.在现实中，用户更愿意看到由多个推荐商品组成的推荐列表.在此背景下，Radlinski提出由多个MAB并列而成的排列多臂赌博机算法(Ranked bandits，RB)[16].

基于RB的推荐系统能够同时推荐多个商品和接收多个反馈信息，尤其适合于网页排序和推荐.Slivkins等发现在文本推荐中，用户经常找不到适合自己的答案，为此整合两大MAB模型(Ranked bandits和Lipschitz Bandits)以提高推荐文本的准确度[17].Louёdec等也发表了类似的研究成果，在一次推荐中，RB忽略了列表位置的相关性(不同位置赌博机挑选物品的过程是独立的)，据此提出Multiple-play Bandits(MPB)推荐算法以提升推荐列表的预测准确性[18].当前的RB推荐研究同样存在过度追求预测精度而忽视了其他重要推荐指标的不足.

综上，本文立足于现有的MAB(包括RB)互动式推荐研究，参考已有的多目标离线推荐研究，提出一种多目标的互动式推荐系统.

3 基于多臂赌博机建立互动式推荐框架

互动式推荐模型的常见构建方法是MAB算法.在MAB推荐模型中，赌博机的m个手臂依序对应m个候选商品.区别于注重一次性收益最大化的离线推荐，MAB互动式推荐注重长期推荐的累积收益最大化.在第t次推荐中，系统以某种策略为用户挑选商品.该商品被推荐完之后，会获得服从某种固定概率分布的收益值(Reward).收益值可以是用户对所推荐商品的反馈，同时也是系统对该商品获得的奖励/惩罚(将影响以后系统挑选该物品的概率).简单地，若用户点击该商品，则收益为1；若用户没有点击，则收益值为0.由于用户兴趣和物品属性会随时间改变，使得每个候选商品的期望收益也是动态变化的.系统需要优化推荐策略，以使长期累积收益最大化(或遗憾最小化).

每个商品的期望收益都具备3个特征[19]：1)随机性(Stochastic)：每个商品的期望收益都是一个服从某种固定概率分布的随机变量.不同商品的概率分布可以不同，分布形态和具体参数可以未知；2)对抗性(Adversarial)：每种商品的期望收益可以动态改变，但是所有商品的期望收益不能同时取零；3)马尔科夫性(Markovian)：商品的期望收益变化过程是一个马尔科夫过程.

系统挑选商品时，既要兼顾开发，也要兼顾探索，既推荐已知商品，也勘探未知(新)商品.常见的权衡开发-探索策略包括[20]：随机法、ε-Greedy、Softmax、Upper Confidence Bound(UCB)、BayesUCB、LogUCB、LinUSB 和Thompson Sampling(TS)等.本文使用ε-Greedy方法.

基于ε-Greedy的推荐策略如下：以ε的概率探索，随机挑选商品；或以(1-ε)的概率开发，挑选期望遗憾值最低的商品.在第t次推荐，假设最高收益值为rmax，商品i的期望收益为ri(t)，则选取i的遗憾值为[rmax-ri(t)].系统的目标是在推荐总次数T内，使累积遗憾值LT最低.

(1)

算法1展示了基于多臂赌博机的互动式推荐算法.第t次推荐将承接第(t-1)次更新得到的MAB模型.图2为其运作过程.

基于MAB的推荐模型仅使用一台赌博机A1，所以在一个推荐流程中，只可以推荐一个商品i(t)，也只能收集一个商品的反馈信息.但在很多实际应用中，系统常常需要为用户展示由k个商品组成的推荐列表，并能收集多个商品的反馈信息，由此发展出由多个MAB排列组成的排列(多臂)赌博机算法：在商品列表P={p1，p2，…，pk}中，赌博机Aj挑选位置为j(1≤j≤k)的推荐商品pj.

算法1.基于多臂赌博机的互动式推荐算法

输入：一种模型A1；目标用户u；候选商品Im

输出：单个推荐商品i(t)

1.重复推荐t=1，2，…，T

2. 基于ε-Greedy的推荐策略挑选商品i(t)

3. 为u展示推荐i(t)，并记录反馈：

4. 若u点击i(t)，令rt=1；否则，令rt=0

5. 更新模型：Update MAB(u(t)，i(t)，rt，A1)

6.返回步骤2，直到完成T次推荐

图2 基于多臂赌博机的“用户—系统”互动式推荐流程Fig.2 Interactive recommendations between users and systems based on MAB

算法2展示了基于排列赌博机的互动式推荐算法.类似地，第t次推荐将承接第(t-1)次更新得到的RB模型.图3为其运作过程.需要说明的是，在实际应用中用户大多以从前到后的顺序浏览商品列表，因此规定：当u点击列表位置为j的商品pj时，奖励赌博机Aj，即rjt=1.此外，位置在j之前的赌博机(A1，A2，…，Aj-1)都没有奖励，即rgt=0(g

算法2.基于排列赌博机的互动式推荐算法

输入：k个赌博机A={A1，A2，…，Ak}；目标用户u；候选商品Im

输出：商品推荐列表P={p1，p2，…，pk}

1.重复推荐t=1，2，…，T

2. 重复j=1，2，…，k： #赌博机Aj依序挑选列表位置为j的商品；

3. 基于ε-Greedy的推荐策略挑选商品ij(t)

4. 当j>1，#判断当前位置商品是否在靠前位置已经被推荐了(避免同一商品被重复推荐)

5. 若ij(t)∈{i1(t)，i2(t)，…，ij-1(t)}，

6.pj←挑选遗憾值次之且未被推荐的商品

7. 否则，pj←ij(t)

8. 为u展示列表P={p1，p2，…，pk}，并记录反馈：

9. 若u点击pj且pj==ij(t)，令rjt=1；否则，令rjt=0

10. 更新模型：Update RB(u(t)，ij(t)，rjt，A)

11. 返回步骤2，直到完成T次推荐

上述MAB(包括RB)推荐模型挑选商品的策略只考虑了预测准确性，即尽量使推荐商品被用户点击，而没有考虑推荐多样性和新颖性，下文将以此为基础，在推荐商品过程中同时考虑多个目标：准确性、多样性和新颖性.

图3 基于排列赌博机的“用户—系统”互动式推荐流程Fig.3 Interactive recommendations between users and systems based on RB

4 基于多臂赌博机的多目标互动式推荐方法

4.1 多目标函数

本方法采用标量函数(Scalarization Functions)将原多目标规划转化为单目标规划问题.基于理想点法构建标量函数，以挑选出加权遗憾值最低的商品.假设所有候选商品在样本空间内，以遗憾值高低进行排序是有意义的[21].本函数挑选的商品能够达到帕累托最优，即不存在其他替代商品，能够改善其中的一个目标却不牺牲任何其他目标.

标量函数的构建过程如下：

先计算Q个目标的理想点(最高收益值)：

(2)

再计算每个商品ij的遗憾值(实际收益与最高收益的偏差)，以欧氏距离法加权求和，得到标量函数：

(3)

(4)

算法3展示了Aj为列表位置j挑选推荐商品pj的策略.

算法3.挑选商品的策略(多目标)

输出：推荐商品pj

1.初始化：商品挑选函数SelectItem；商品遗憾数组ItemRegret[ ]

3. 重复i=1，2，…，m，#遍历所有商品

5. OptimalItem←argmin(ItemRegret[])

6. 返回 OptimalItem }

4.2 推荐指标的计算方法

4.2.1 商品准确度

在第t次推荐过程中，将以商品ij在之前(t-1)次推荐过程的平均点击通过率(Click-Through Rate，CTR)作为其准确度分数：

(5)

其中，rd(ij)为第d次推荐中ij的实际收益值(若被点击，取1；否则，取0).例如，在u的前10次推荐服务中，若ij被点击2次，则再在第11次推荐中，ij的准确度分数为0.2.

4.2.2 商品多样度

这里的商品多样度分数是指ij在集合S中的多样度，记为div(ij|S)，用于衡量ij和S所包含商品的差异性.多样度的计算方法借鉴文献[23]：

(6)

(7)

其中，S为第j个位置之前的推荐商品组成的新集合；dis(ij，il)为商品ij和il的余弦距离(aq和bq为ij和il的商品属性值，如评分、流行度等).若S为空(如j=1时)，则令div(ij|S)=1.例如，在A4挑选第4个位置的推荐商品时，S为前3个位置商品组成的集合{i1，i2，i3}，ij和i1、i2、i3的距离分别为0.90、0.91和0.92，因此div(ij|S)=0.91.

4.2.3 商品新颖度

借鉴文献[23]的方法计算商品新颖度.对于ij，先计算其流行度pol(ij)：

(8)

其中，sel(ij)为之前的推荐过程中A挑选ij的次数.例如，有5个商品，在前10次推荐中(单次推荐两个商品)，分别被挑选了8次、6次、2次、2次和2次.到了第11次，这5个商品的流行度分别为0.4、0.3、0.1、0.1和0.1.

对pol(ij)取对数，则新颖度分数为：

nov(ij)=-log2pol(ij)

(9)

值得注意的是，所有商品的准确度、多样度和新颖度分数计算完成之后，都务必进行标准化处理(本方法采用Z-Score标准化)，再由分数值构成期望收益矩阵Sm*Q，其中m为商品数，Q为目标数.例如，s11，s12，s13分别为第一个候选商品的准确度、多样度和新颖度分数.

从上述计算过程可知，一个商品如果在之前被赌博机挑选并被用户点击的次数多，则其后续的准确度分数会升高；然而，如果被过多的挑选，又会降低其新颖度分数.对于一些开始过时的热门商品，容易被赌博机挑选却不被用户接受，就会出现准确度和新颖度分数同时下降的情形.另外，当新商品与原列表中商品的差异性较大时，则更容易被选中.这将有效避免推荐列表出现“千篇一律”的不良后果.

4.3 模型更新策略

分析状态空间模型(State Space Model)的线性系统：

(10)

(11)

(12)

(13)

算法4.权重更新策略

值得注意的是，系统会为每个用户存储其独有的权重向量(个性化的体现).对于一个特定用户，随着用户与系统互动次数的增多，推荐结果越来越能够满足其需求.对于新用户，系统会更注重预测准确度，旨在与用户建立信任关系；而对于老用户，系统会更注重多样度和新颖度，旨在拓宽用户视野，带来新鲜和惊奇感，从而提升用户体验满意度和忠诚度.

4.4 算法描述

算法5.基于多臂赌博机的多目标互动式推荐算法

输出：商品推荐列表P={p1，p2，…，pk}

1.重复推荐t=1，2，…，T

2.计算商品期望收益SM*P#第4.2节

3. 依序用第j个赌博机Aj挑选列表位置为j的商品；重复j=1，2，…，k

5. 或以ε的概率探索：随机选择ij(t)}

6. 当j>1， #避免同一商品被重复推荐

7. 若ij(t)∈{i1(t)，i2(t)，…，ij-1(t)}，

8.pj←挑选遗憾值次之且未被推荐的商品

9. 否则，pj←ij(t)

10. 为u展示列表P={p1，p2，…，pk}，并记录反馈：

11. 若u点击pj且pj==ij(t)，令rjt=1；否则，令rjt=0

14.返回步骤2，直到完成T次推荐

图4 基于多臂赌博机的多目标互动式推荐流程Fig.4 Multi-objective interactive recommendations between users and systems based on MAB

5 实验验证

为验证本研究所提出的互动式推荐系统的有效性，将采用标有时间戳的离线数据进行在线模拟实验.

5.1 数据集与评估指标

本实验将在Hetrec2011-LastFM-2k数据集上进行，该数据为来自英国网络电台和音乐社区网站的真实数据，记录用户收听音乐的信息，包含有1，892个用户和17，632个商品(音乐家)，其中“用户-商品选择关系”占比(非零元素比例)为0.05%.

为了提升推荐效率，需要选取互动实验之前的部分历史数据进行预处理，为每个用户存储适当大小的候选商品Im.采用基于用户的协同过滤算法[20]进行Top-N过滤，只有排名前100的商品才可进入互动式环节.

模拟Last.FM网站中的用户—系统互动过程：在当次推荐t，用户点击展示的音乐家，系统根据用户反馈改进下次推荐(t-1)的推荐模型(算法5).在预处理时间点后的数据，只有427个用户有超过40次的元组<用户，音乐家>.为这里的427个用户分别模拟40次互动式推荐实验.

将推荐实验获得的含有多个商品的推荐列表作为评估对象，从准确度、多样度和新颖度3个方面构建推荐效果的评估指标.

受限于实验数据的数据结构，在一个时间戳中，用户只选择推荐列表R中的一个商品.因此，在当次推荐中，只要用户点击R，则视R为推荐成功.区别于离线推荐，在线推荐最常用的准确度评估方法是点击率，即平均CTR(R)：

(14)

其中，rd(R)为在第d次推荐中，用户对R的反馈(点击，取1；否则，取0).

列表多样度div(R)：

(15)

其中，d(ij，il)为商品ij和il的距离，见式(6).

列表新颖度nov(R)：

(16)

其中，sel(i)为在过去，商品i被点击的次数.

5.2 对比模型

将本方法模型和现有的部分经典MAB推荐方法模型的推荐效果进行对比：

1) 排列多臂赌博机模型(RB[16])：由多个MAB并列而成的列表推荐算法(算法2)，该模型只关注推荐的准确性.

2) 上边界多臂赌博机模型(UCB[25])：从置信区间的角度权衡“开发-探索”，无需人为设定探索参数.一个UCB只能推荐一个商品，因此参考RB的设计思路，并列多个UCB才能产生商品推荐列表.该模型只关注推荐得准确性.

3) 本方法模型(MOMAB)：探索参数ε取0.2时[26]，能够较好地权衡“开发-探索”冲突.

4) 固定权重模型：为了验证MOMAB模型权重更新策略的有效性，构建固定权重的参照模型，即保持标量函数中的权重一直不变(去除算法4)，除此之外的其他操作与MOMAB模型完全相同.根据权重选取的不同，可分为：

5.3 结果分析

本方法模型MOMAB与RB模型、UCB模型和固定权重模型的推荐效果评估对比如图5、图6、图7所示.

图5、图6和图7分别为在40次的“用户-系统”互动推荐中(T=40)，各模型的推荐列表(商品数k=5)在准确度、多样度和新颖度指标的表现情况.按照由优到劣的顺序，准确度的表现为：UCB、MOMAB、RB、M2、M1、M3和M4；多样度的表现为：M3、M4、MOMAB、M1、M2、RB和UCB；新颖度的表现为：M4、MOMAB、M3、M1、M2、RB和UCB.

6 结束语

针对许多现有推荐技术面临的两大挑战(缺乏实时性；缺乏多样性和新颖性)，本文提出一种以多臂赌博机建模的多目标互动式推荐系统.其主要创新点为：1)多目标推荐.采用理想点法构建多目标规划模型，并将其转换成单目标规划问题，同时优化推荐准确性、多样性和新颖性；2)具有实时性.实际应用中，“用户兴趣是变化的”、“潮流是变化的”“商品是有生命周期的”、“季节效应”等时间效应因素，影响着用户对推荐商品的体验满意度.本方法参考卡尔曼滤波器，给出权重迭代策略，能根据用户的反馈，优化各目标权重，实时调整推荐策略，适应用户不断变化的需求(用户独一无二的反馈信息决定了推荐的个性化).

关于未来的研究方向：1)同时优化更多的重要推荐指标，比如：覆盖率、惊喜性和效用性.在现实中，合理又综合地评估推荐系统优劣是困难的.许多推荐目标是对立冲突的，但又是至关重要的；2)考虑推荐列表不同位置的影响.显然，在一个界面中，相对于靠后显示的推荐商品，靠前显示的往往更容易被用户点击.所以，靠前的位置可以适当增加多样性和新颖性的权重；3)更进一步MAB的开发-探索冲突.如前所述，只有同时兼顾开发和探索的推荐方案，才能在强化学习过程中实现长期的累计收益最大化.本研究仅尝试了较为简单的ε-Greedy方法.事实上，还可以更多地尝试更先进的权衡EE方法(见第3节).