小叽导读：在线推荐服务根据商品的特征和用户的信息推荐多个商品。 现如今很大比例的用户通过手机访问电商平台。 但是一些推荐的商品并没有被用户看到。为了解决在线推荐场景中的伪曝光问题并提高推荐商品的CTR，我们首次尝试了bandit框架，并且在传统的bandit算法上进行了多项改进，取得了不错的效果。
作者 | 天裂、海凯、一尘、理欣
在这篇文章中，我们做出了五个关键贡献来解决伪曝光问题并提高点击率：
由于传统的contextual bandit问题只推荐一个商品而不是一组商品，我们首先把在线推荐问题model成一个创新的Contextual Multiple-Play Bandit问题。我们利用了一个线性的奖励模型 （linear reward model）来适应大规模的候选商品。
我们提出了一个新的方法来解决伪曝光问题。我们使用用户看到这些商品的可能性作为样本的奖励的权重。
为了提高CTR，商品之间的相似度被用来改进线性奖励模型。
我们提供了算法的理论分析并且证明了我们的算法具有亚线性的（sublinear）regret。
我们利用淘宝的真实数据集进行了测试。结果显示我们的算法在两种CTR测量方法下分别比Learning to Rank（LTR）方法分别提高了15.1%和12.9%，并且显著的超过了其他contextual bandit算法。
- 介绍
随着电商平台的普及，很大一部分用户开始通过移动设备来访问电商平台，比如亚马逊和淘宝。在推荐场景中，一列商品会基于用户和商品的信息被推荐出来。由于屏幕的限制，只有一部分商品能被第一时间看到，剩下的商品需要滑动屏幕来翻页并查看剩下的商品。在这个过程中，用户可以点击一个吸引他的商品并查看商品详情。查看之后用户还可以返回推荐列表浏览其他商品并且点击多个商品。如果没有商品吸引到用户，特很有可能直接退出推荐场景或者淘宝应用。
在这个过程当中，用户很有可能在浏览完所有商品之前就离开了推荐场景，这种现象称为伪曝光。举例来讲，如果我们向一个用户推荐了5个商品，他点击了第一个商品并查看了这个商品的详情，之后他返回了推荐列表查看了第二和第三个商品，但是并没有点击这两个商品。我们只知道五个商品被推荐给用户然后他点击了第一个。由于已有的研究一般会假设所有的商品都被用户查看了，第三个位置之后的商品会被当做负样本。这些有偏差的负样本会使得学习效果下降。
这篇文章是为了解决在线推荐场景中的伪曝光问题并提高推荐商品的CTR。我们采用了bandit框架：一种在线推荐的常用算法。在应用bandit框架的过程中，有一些挑战需要被解决。
第一，多个商品需要被选出。但是传统的bandit算法一般只选择一个。并且大量的商品和用户会导致收敛缓慢。尽管multiple-play bandit算法[7,10,18] 已经被踢出来选择多个商品，但是他们都没有考虑到context。
第二，由于伪曝光的存在，一些数据可能不适合直接用来学习。如果我们直接利用数据进行学习，用户真正的喜好就不会被准确的学到。商品的位置会对伪曝光问题产生很大的影响。尽管已经有一些工作考虑了位置信息，比如Cascade Model [5] 和 Position-Based Model [15]，但是伪曝光问题没有被他们考虑进去。
第三，为了探索用户的潜在兴趣，相似的商品要避免一起出现在一个推荐列表里。在multi-armed bandit问题中，相似度信息被用来当做Lipschitz条件来限制相似的商品会得到相似的奖励 [2,9,20]。但是他们没有考虑推荐多个商品。
在这篇文章中，我们提出一种创新的contextual multiple-play bandit 算法来解决这些挑战。我们的贡献主要有五方面：
我们把在线推荐问题model成了一个创新的contextual multiple-play bandit的问题并且利用了线性奖励模型来有效的利用样本。
为了解决伪曝光问题，我们提出了一个方法来估计不同位置的商品被用户看到的的概率，并且利用它作为样本的权重。
为了推荐多样化的商品，我们考虑了商品的cosine相似度并提出了一个混合的线性模型来表达商品信息，相似度和奖励的关系。
我们分析了算法的regret。对于第T回合，m个推荐商品，d 维商品信息，我们证明了
有概率达到
的regret。
我们利用淘宝的真实数据集测试了我们的算法。结果显示我们的算法在两种CTR测量方法下分别比Learning to Rank（LTR）方法分别提高了15.1%和12.9%，并且显著的超过了其他contextual bandit算法。
2.相关工作
Multiple-play bandit方法被提出来拓展传统bandit算法并在每个回合推荐多个arm。EXP3.M 算法是EXP3算法的拓展 [7]。主要的思路是每回合基于EXP3选出多个arm。两个框架Rank Bandit Algorithm (RBA) [18] 和Independent Bandit Algorithm (IBA) [10] 也被提出。这两个框架都是在每个位置运行一个MAB算法来选择多个商品。
在RBA中，如果不同位置的MAB算法选了同一个arm，位置较低的算法的奖励为0。在IBA中，为了防止重复，位置较高的MAB所选择的arm会从位置较低的MAB候选集中去除掉。Thompson Sampling也被拓展并给出了理论分析[11]。最近multiple-play bandits算法被用在预算限制下来最大化累积奖励[23, 24]。但是这些算法没有考虑context。这回导致收敛速度较慢并且不适合应用到大规模的真是问题当中。
伪曝光问题主要是由商品的位置引起的。利用点击模型来model位置的影响已经在一些工作中出现了。The Cascade Model [5] 分别和 multi-armed bandit, combinatorial bandit, contextual bandit 和 contextual combinatorial bandit 结合 [13, 14, 17, 25]。
在combinatorial bandit 中，算法推荐一组商品但是只收到一个关于集合的点击反馈。The Cascade Model假设一个用户从上到下观察推荐出来的文档直到找到一个相关的。Wen et al. [22]将UCB算法和Independent Cascade Model 结合来解决在线影响力传播问题，由于Cascade Model无法解决多种点击的情形，Position-Based Model被考虑[12, 15]用来估计位置对于点击率的影响。
Komiyama et al. [12]与传统的bandit不同，他们考虑了广告的影响。Katariya et al. [8] 结合了bandit算法和Dependent Click Model，其中Dependent Click Model将cascade model拓展为多个点击。他们都假设用户浏览了所有的商品。但是在我们的问题中，我们假设在移动设备中一些商品无法被用户看到并且利用了position-based model来估计用户看到不同位置的商品的概率。
3.问题描述和公式化表达
在这一章中，我们首先提供了问题描述并且叙述了移动电商平台遇到的两个挑战。我们之后公式化的定义了contextual multiple-play bandit problem和两个CTR评价标准。
3.1问题描述
随着手机的普及，更多的消费者倾向于通过手机客户端来访问电子商务平台。与网页不同，移动应用上的界面是有限的并且只能显示几个商品。
比如说图一a和b分别展示了3个和2个商品。利用有限的空间找到用户的兴趣是一件困难的事情并且主要要两个挑战需要被克服。
第一，探索和利用之间的平衡非常重要。由于在推荐场景中用户一般不会提供额外的关于他们兴趣的信息，用户的浏览和搜索记录经常被用来当做用户的先验知识。但是利用这些知识推荐出来的商品会和搜索引擎的非常相似。这和推荐场景发掘用户潜在兴趣的目标不太一致。解决这一问题的关键是探索和利用之间的平衡。由于有限的屏幕尺寸，这一问题在移动端尤其重要。探索需要在没有先验知识的情况下找到用户的潜在兴趣。同时，利用能够促使用户点击更多的商品并且滑动屏幕来探索更多。这个探索/利用的困境之后会被我们被转化为multiple-play contextual bandit问题。
第二，我们获取的数据是不完美的。数据无法显示哪些商品没有被用户看到。我们的数据是从淘宝的天天特价场景得到的（图一b）。在该场景中，12个商品会被推荐给一个用户。但是由于有限的屏幕的空间，只有一个会被用户第一眼完整的看见。剩下的商品是否被用户看到是无法从数据中得知的。这种现象我们称之为伪曝光。解决这个问题的一个思路是估计这些商品被看到的概率并利用这概率作为样本的权重。我们在第四章利用了点击率模型来估计这个概率。
3.2 Formulation
基于context信息推荐多个商品的问题可以被自然地解释为contextual multiple-play bandit 问题。一个contextual multiple-play bandit 方法M在一个离散的回合t=1,2,3,...T。在每个回合t，M会观测到当前的用户u(t)和一个包含了m个arm候选集合A(t)和一个集合X(t) ，包括了每个商品的a的d维的向量x(t,a)。算法M会基于观测到的信息选择一个子集S(t)包含K个商品。之后会收到这些商品的奖励r(t,a)。另外，商品的排序L也会被算法M观测到。算法M之后会基于这些信息(R,x,L)更新选择策略。主要的符号在表一中被展示。
我们对推荐的集合定义了两种奖励方程：
点击的和：我们用个商品的点击之和来测量推荐集合的吸引力，我们首先定义奖励方程：
推荐集合的点击：为了避免用户退出，我们希望推荐的商品集合A(t)至少有一个商品吸引用户并且被用户点击。从这个角度，推荐集合的奖励被设为1，如果至少一个商品被点击，也就是：
在我们的推荐问题当中，我们将推荐集合中的商品视为bandit问题中的arm。当一个被展现的商品被点击了，奖励r会被设为1，否则是0。利用这种设定，奖励的期望就是商品的点击率（CTR）。因此，选择一个商品来最大化CTR就相当于最大化期望的奖励。
- 算法
在本章，我们首先通过结合了Independent Bandit Algorithm (IBA)和一个线性奖励模型，提出了一种contextual multiple-play bandit算法。为了解决伪曝光问题，我们在第4.2章中在线性奖励模型中估计了不同位置的曝光概率，并将其作为样本的权重。为了进一步提高CTR，在4.3章中我们将相似度信息和线性奖励模型相结合。
4.1 Independent Bandit Algorithm with Linear Reward Model
在提出算法之前，我们首先介绍 Independent Bandit Algorithm (IBA) 和 LinUCB算法。IBA是一个multiple-play bandit框架用来推荐一组arms。IBA依次运行K个独立的Multi-Armed Bandit (MAB) 算法。推荐的集合记录了K个算法的选择。更高位置的MAB选择出来的商品会从较低位置的商品候选集合里面去除掉，用来确保同一个商品不会被重复选取。R(t,S_t)是一组奖励向量。如果第k个算法推荐商品被点击了，那奖励向量的第k个元素为1否则为0。
LinUCB算法[16] 是由Li et al.提出的。在contextual bandit中，算法能够观测到商品的一些context信息并且选择一个最好的arm来获得最高的奖励。为了利用context信息，LinUCB算法提出了线性假设，假定context信息和奖励呈线性关系。LinUCB的目标是找到一个最好的参数来通过更定的context预测奖励并选出一个最大化奖励的arm。
在LinUCB算法中，岭回归（ridge regression）被用来解线性回归模型
。我们构建一个m*d维矩阵X，这个矩阵的每一行里包含了推荐集合S(t)其中一个元素的context。R(t)是推荐集合S(t)的奖励。利用岭回归解为：
我们定义两个参数：
第k个位置的在线更新的方程为：
商品a(t)的 upper confidence bound 为：
其中
是岭回归的标准方差，是一个预先设定好的参数，决定了探索概率。
我们提出 IBALinUCB 算法来结合IBA和LinUCB，具体的细节在算法一中展现。第四行调用了第k个LinUCB算法来选择第k个商品。在第五行，选出来的商品被添加到了推荐集合中，之后算法会得到这个推荐集合的奖励。第12行和第13行初始化了参数，第十五行给出了计算了upper confidence bound的公式。第19和20行定义了参数的更新方式。
4.2 IBALinUCB with Sample Weight
我们基于算法1提出了新的算法来解决伪曝光问题。之前的工作显示点击率很严重的依赖于位置，位置靠前的商品比较容易被点击[6]。因此我们提出了样本权重来来估计商品被用户看到的概率并且提出了一个新的线性模型。我们首先介绍用来估计权重的点击率模型。
Position-Based Model (PBM) [4] 假设点击率r(a) 是由位置和商品吸引力决定的，也就是
其中w(l)是第l位置的影响力，
是商品的吸引力。可以解释成用户看到的商品以后的点击率。为了解决伪曝光问题，我们把w(l)看做用户看到第l位置的商品的概率。我们将其作为样本的权重，并提出了一个新的线性奖励模型：
其中theta是一个未知的向量参数。w(l)能够被看做一个常数，因为它可以被提前学出来[15]。由于我们的目标是预测r，我们将权重w(l)和x(a)相结合，并给出新的参数更新公式：
第k个位置的标准差是：
所以用来选择商品的upper confidence bound是：
其中alpha是一个被给定的常数。由于参数w(k)对每个位置来讲是一个常数并且和商品不相关，我们可以在选择商品的时候忽略它。我们使用和LinUCB相同的公式来减少计算：
加入sample weight的IBALinUCB算法被仔细的描述在了算法二。第一行重新使用了算法一的IBA框架。第二行定义了在第k个位置选择最好的商品的方程，第11行展现了参数A和b的更新方式。
4.3 IBAHybridUCB with similarity information and Sample Weight
由于用户没有在推荐场景中搜索特定的商品，直觉上推荐多种种类的商品可以提高CTR。相似度信息很广泛的被用在推荐方面，比如说[19]。在bandit问题中，相似度信息被作为Lipschitz条件，用来限制拥有相似的信息的商品会接收到相似的奖励 [2,9,20]。但是这些算法在每回合只推荐一个商品并收到一个奖励。在这一章我们利用了cosine相似度来实现多样化的推荐。我们采用了混合线性模型来利用相似度信息：
其中z(a)是一个我们建立的相似度向量，beta是一个对所有商品都相同的未知的向量参数。
我们现在先介绍建立相似度向量的方式。IBA框架依次运行K个MAB算法对应着K个位置。在第t个回合，对于第k个位置，前k-1个位置的被选择的商品是已知的，我们把这些已经选出来的商品表示成一个集合S(t,k-1)。之后我们对于商品
计算相似度向量。对于每个a，我们用相似度信息填满z(a)。具体的构建方式在算法三中被展现。第五行计算了a和b的相似度信息，其中
。
在构建好之后，我们给出基于HybridUCB[16]算法的修改后的更新方式。
算法四给出了加入了相似度信息和样本权重的IBAHybridUCB算法。第一行中我们忽略了IBA框架，因为在算法一中展示过。我们定义了两个函数来选择商品和更新参数。第二行的函数是用来基于upper confidence bound选择商品。第14行是更新参数的方程。
- 理论分析
我们在这一章分析了我们算法的regret。我们首先分析了LinUCB+SW算法，之后给出了HybridUCB+SW算法的regret。我们首先根据第三章的奖励方程给出在T回合的regret定义。奖励的和的regret为：
其中S(t,*)是t回合的最佳推荐集合。集合的奖励的regret为：
对于IBALinUCB+SW算法，我们首先证明最优解选择了值最大的前K商品，这一点对于Regret(sum)是显然的，对于Regret(set)，我们利用了排序不等式来证明。之后。我们展现了在IBA框架下，LinUCB+SW独立的达到了亚线性regret。
我们先重述LinUCB算法的regret [3]：
我们有：
尽管第k个位置的LinUCB+SW会根据前k-1个位置的决定，但是LinUCB+SW是一个随机算法并且线性模型是对每个LinUCB+SW都成立的。因此，每个LinUCB+SW都可以取得定理1中的regret：
证明：
对于Regret(set)的bound，首先我们注意到：
下面的引理证明了第k个算法选择了第k高的商品：
根据这个引理，我们得到如下定理：
LinUCB+SW算法的regret分析也可以适用于HybridUCB+SW。尽管我们的算法的理论分析和LinUCB算法相似，但是基于真实数据的实验结果显示我们的算法比LinUCB要好很多。
6.实验结果
在本章，我们描述了实验细节。首先我们定义了我们的评价标准。其次我们介绍了从淘宝获取的真实数据集，描述了数据收集和处理的细节。我们也分析了伪曝光问题在数据中的存在情况。最后，我们利用三组实验来评价我们的算法。不同算法的对比，探索参数的影响，以及推荐商品个数的影响在最后一章被测试。
6.1评价标准
和我们的奖励标准一致，我们提出两个评价标准：
累积的CTR: 在每个回合，一个奖励向量会被算法接收到，我们用奖励向量的1范数作为标准：
。
集合的CTR：如果其中一个商品被点击，集合的CTR为1，否则为0，我们用集合奖励的期望来定义第二个评价标准
6.2数据收集和处理
我们使用的数据是由淘宝提供的。我们利用了淘宝中推荐场景的一天的数据，其中12个商品会从900多个商品中被选择出来被展现给180k个用户。这个场景有两个特征，第一推荐的商品数量被固定在12个，移动客户端不会再推荐新的商品。第二，用户只会看到第一个商品和第二个商品的一部分。在图一b中，第一个商品被红色的框标记。为了观察剩下的商品，用户需要滑动屏幕。
我们的数据集有180k条数据，每个数据包含了一个用户ID，12个商品的ID，每个商品的context向量和一个对应着12个商品的点击向量。Context向量是一个56维的向量包含了一些用户和商品的信息，比如商品的价格和销量，用户的购买力。我们去除了没有点击的数据，因为我们无法得知用户真实的喜好，如果他不惦记任何商品。
为了展现伪曝光问题，图2展现了最后一个点击的位置。圆圈外的数字是最后一个点击的位置。只有6.2%的记录中最后一个商品被点击了。如果我们假定最后一个被点击的位置之后的商品会存在伪曝光问题，那么对于最后一个点击位置是1的记录，的商品会存在伪曝光问题，那么通过加权和大概54%的样本被伪曝光问题影响到。这个百分数是一个粗略的估计，因为也有可能一些在最后一个点击之后的商品被用户看到了。
此外，我们利用了denoising autoencoder [21]来给数据降维。这个encoder有4个隐藏层，神经元数量分别是25,10,10,25和一个56个神经元的输出层。ReLU作为隐藏层的激活方程。输入的向量x被一个随机向量扰动，输入为0.95x+0.05*noise，其中noise是一个0到1中的随机向量。目标是最小化MSE的损失。我们采用第二个隐藏层的输出来作为新的context。这个提炼的context被用在之后的所有实验中。
Sample weight. 数据的权重主要是由页面的结构决定的。由于一个页面的结构在长时间内都不会变，我们可以假定位置影响是一个常数[15]。我们利用EM算法来计算[4]。
6.3 对比算法
我们利用5个对比算法来展现我们算法的表现。第一个是一个不利用context的融合了PBM的bandit算法。接下来的两个算法是两个广泛使用的contextual bandit 算法。第四个是淘宝使用的Learning to Rank（LTR）算法。最后一个算法是我们在第4.1章引入的算法。
PBM-UCB [15]：PBM-UCB算法是结合了PBM模型和UCB算法。该算法的upper confidence bound 被用来选择最好的商品：。
LinUCB-k：该算法是LinUCB算法的直接拓展。在每个回合算法会选择前K个商品。在展示之后算法将会收到这些商品的奖励，并根据LinUCB算法更新参数。
RBA+LinUCB：Ranked Bandit Algorithm [18]在每个位置运行一个bandit算法。但是如果在第k个位置的算法选择了一个已经被选择了的商品，这个位置将会收到0奖励，并且会被一个不重复的随机商品替代。
LTR：Learning to Rank（LTR）是一个淘宝使用的深度学习算法，利用了30天的数据来进行训练。神经网络的输出是一个56维的向量，被用作商品context的权重。由于我们的数据就是由该模型进行排序的，我们直接选择数据中前K个商品作为对比。
IBALinUCB：我们在算法一中介绍了这个算法，他被用作对比算法，来展现权重的影响。
6.4结果
我们进行了3组实验设置了不同的K和来展现我们算法的效果。第一组实验我们展现了随着步数变化的曲线，当K为3和6 时。之后，我们展现了变化所产生的影响。最后一组实验展现了当推荐个数K变化时各个算法的最终表现。我们的IBAhybrid+SW算法在大多数情况下表现的最好。
6.4.1随着步数增加的表现
图三展示了我们的算法在两种标准下的表现。子图a和c展现了标准下K=3和6时的表现。另外两幅图展现了在标准下的表现。IBAhybridUCB+SW算法达到了最好效果。
当K=3时，前两幅图中其他算法和IBAhybridUCB+SW的差距要比后两幅图中大很多。当K=6时，尽管我们的算法也比LTR算法的表现高出10%，但是IBAhybridUCB+SW和IBALinUCB的差距比较小。原因是次优的算法会达到和最好的算法相似的效果，当K比较大的时候。比如说，当推荐的策略是次优的，最好的商品被排在了第4或者第5，这件商品在K=6时也会被展示出来。这个次优的策略会得到和最优策略相同的奖励。因此算法会倾向于学习一个次优解，而不是最优解，当K较大时，这个目标会比学习最优策略要容易很多。因此其他对比算法会在K较大时效果较好，但是我们的算法被K的影响较少。
6.4.2随着alpha变化的表现
第二组实验中，我们展现alpha 在[0.01,0.6] 取值的表现。结果在图4中被展现。我们的算法在大多数情况下比其他算法要好很多。在最高点IBAhybridUCB+SW算法会比IBALinUCB+SW算法表现更好。下面是我们的一些观察。第一，当时，几乎所有算法表现的都很差，由于缺乏的探索。
第二，几乎所有算法在为0.1和0.3时表现较好。原因是随着的增长，来自方差的扰动会加剧，算法会更倾向于探索，因此表现会下降。
第三，IBAhybridUCB+SW算法在较小时表现较好。这个表现和相似度信息的使用有关。IBAhybridUCB+SW算法会倾向于基于相似度信息来进行有效探索并学习到最优的策略。因此算法可以更加高效的学习，即便探索系数很小。
6.4.3随着变化的表现
我们利用算法推荐不同数目的商品并将结果展现在表2当中。LTR算法被当做基准算法，带有百分号的数字是CTR提升的比例。这个表格展现了所有算法的和。一个更大的CTR代表了算法更好的利要交给了数据并学到了更好的推荐策略。由于候选集合中的商品数目是固定的，我们通过改变K的值来展现算法在不同的比例变化时的表现。
为了更好地展现结果，我们利用柱状图（图5）展现了结果。第一我们能够观测到我们的算法会比LTR算法高出10%，展现了在线推荐更适合动态的环境。在对比算法中，IBALinUCB算法表现的比其他算法好而PBM-UCB由于缺乏利用context，表现的较差。
实验效果显示我们的算法在K=3时效果较好。IBAHybridUCB+SW算法在两种标准下分别提高了15.1%和12.9%。而IBALinUCB+SW分别提高了12.1%和10.8%。这个结果和[16]中的结果相同，在这篇文章中，作者展现了contextual bandit algorithm当较小时表现较好。如我们之前提到的，当较大时，次优的策略也可以得到与最优策略相似的结果。因此当较小的时候，算法的CTR能够更准确地展示了效果。更重要的是，这个优点在实际问题中很重要，因为在这些场景中从几百件商品中选出十几件商品推荐给用户。
7.结论
在这个文章中，我们专注于在大规模移动电商平台中解决伪曝光问题。第一，我们将在线推荐问题描述为contextual multiple-play bandit算法。第二，为了解决伪曝光问题，我们利用了PBM模型，来估计用户看到商品的概率，并提出了一个样本权重的方法来利用这个概率。第三，相似度信息被加入到我们的线性奖励模型中来推荐多种商品并提高CTR。第四，我们针对两种标准提供了亚线性的regret理论分析。最后，我们利用淘宝的真实数据进行了3组实验来估计我们的算法。结果显示我们的算法相对于一个监督学习算法和其他bandit算法来讲，能够显著的提高CTR效果。
原文发布时间为：2018-12-12
本文作者：搜索事业部
本文来自云栖社区合作伙伴“ 阿里巴巴机器智能”，了解相关信息可以关注“ 阿里巴巴机器智能”。
