1.背景

在许多推荐场景中，我们都需要一次性推荐一屏的物品给用户，如下图所示两个例子（Taobao和YouTube）：

在论文中我们将这种场景称之为exact-K recommendation问题，这个问题的目标是优化提高这一屏物品被点击或者满足目标用户需求的概率。于此同时，为了保障推荐的体验，同一屏中的物品往往要满足一定的限制，比如推荐物品之间需要具有一定的多样性。Exact-K推荐问题可以看做是带约束的组合优化问题，Top-K的方法则看做是一种启发式的贪心解法。下面我们介绍论文中如果对该问题进行端到端的求解，并重点介绍论文中提出来的“Graph Attention Networks (GAttN)”模型和“Reinforcementfrom Demonstrations (RLfD)”训练方法。

2.问题定义

**2.1Exact-K Recommendation问题
**

对于给定的包含N个物品的候选集合，我们的目标是从中选择K个物品的集合，并将这K个物品作为一屏推荐给用户，使得用户对这一屏的点击率最高。在这里，我们把A会被用户u点击或者满足用户u需求的概率定义为，同时，A中的物品两两之间有时需要满足一定的条件限制，定义为：

可以理解为两个物品之间的某种限制，如果满足限制，则，如果不满足限制，则。当然，物品之间有时也不需要条件限制，此时。根据上面的定义，我们可以把Exact-K Recommendation问题形式化表示为下面的组合优化问题：

论文中从图论的角度，可以重新理解我们刚才定义的问题。首先，把S中包含的N个物品作为图中的N个节点，其中节点代表物品。如果物品之间的限制条件为空也就是时，那么图中两两节点之间的都有边相连，如果C不为时，只有满足了条件的物品之间在图中相应节点才有边相连。既然要求推荐的K个物品两两之间都要满足条件，因此问题变为了图论中一个非常经典的问题，即在图中找到一个K个节点的完全子图，也就是K团。同时问题是最优化问题，相应的我们需要求解“最大”的K团，这里“最大”是一个泛化的概念。举个例子如下：

2.2节点权重估计方法

论文中首先介绍了一种基础的方法，过程如下：

1. 对于给定的用户u和候选集合S，首先构造一张无向图；
2. 计算图中每个节点的点击率CTR；
3. 基于贪心算法，从当前的候选集合中选择点击率最高的一个节点，加入到推荐结果集A中，并把至少与A中一个物品不相连的物品从当前的候选集中去掉；
4. 重复第3步直到得到包含K个物品的推荐结果集合A。

这个方法非常类似Top-K推荐的思路，计算每个物品的点击率，然后从大到小进行展示，但这个方法的缺点也非常明显：

1. 点击率预估是单独针对一个物品来计算的，而且K个物品之间的组合关系也没有很好的考虑；
2. 该方法启发式地将“最大”K团问题转化成了预估每个节点的权重然后求“最大权重和”的K团，并没有直接地对目标进行优化，可能得不到最优解。

3.方法

3.1Graph Attention Networks

文章提出的方法称为Graph Attention Networks，简称为GAttN，整体的框架采用Encoder-Decoder的方法，如下图所示：

• 3.1.1 Input

对于给定的图，图中每个节点对应的物品的特征记作，用户u的特征记作。因此Encoder的每个阶段的输入计算如下：

• 3.1.2 Encoder

传统的Encoder一般选择循环神经网络如LSTM或GRU，但在这个问题里顺序是没有意义的，因为输入的各个物品之间是无序的。尽管各个物品之间无序，但它们之间的相互影响还是需要考虑的。所以，这里的Encoder选择的是Transformer里面Multi-head Self-Attention机制。其中，Encoder具体包含三个sub-layers，如下所示：

• 3.1.3 Decoder

对于Decoder来说，要输出K个物品集合A，代表图中的一个包含K个节点的完全子图。这里使用的是循环神经网络，输出的集合是A的概率计算方式如下：

其中，这里代表的是encoder的输出（图中每个节点的embedding），代表的是decoder的参数。得到输出是集合A的概率可以表示为得到A中所有物品的联合概率分布。这里使用循环神经网络来建模联合概率分布，在得到时，输入包含两部分，一个是上一个阶段的隐藏层状态，另一个是上一阶段的输出，因此可以得到下面的式子：

其中，

这样可以得到Decoder每个阶段的隐藏层状态，那么如何得到当前选择的物品呢？参考下面的网络结构图：

这里采用pointer-network的做法，首先使用一个attention机制，先让decoder回顾（glimpse）一遍所有的encoder输出，作为当前输出的上下文：

接下来，我们要计算选择每个物品的概率分布，首先这里需要注意的一点是，Decoder每个阶段的输出组合起来，应该是图中的一个团，因此，要确保当前选择的物品能够与之前选择的物品在同一个完全子图中，如果不能满足这个条件，需要通过添加mask的方式，确保其不会被选择到：

3.2 Reinforcement Learning from Demonstrations

回顾我们的优化目标是整个一屏的推荐结果集合A的点击概率最高，按照监督学习的思路，Decoder阶段使用的是RNN的结构，我们只能计算每个阶段的交叉熵损失，因此网络的优化目标和实际想要的目标是存在一定的gap的。因此，可以考虑通过强化学习中policy-gradient的思路直接优化目标。但是直接使用policy-gradient的方法，其训练是比较低效的，前面的探索效率可能无法得到有效的保证。因此，可以认为监督学习方法是“有效率的（efficient）”，而强化学习的方法是“有效充分的（sufficient）”。

综上所述，我们采取的思路是，结合了监督学习和强化学习，通过监督学习的方式对网络参数进行一定的预训练，再通过策略梯度的方式进一步修正网络参数。我们将使用监督学习的方法称作Learning from Demonstrations，使用强化学习的方法称作Learningfrom Rewards。

• 3.2.1 Learning from Demonstrations

我们将从历史日志中收集的一批真实的训练数据称作，通过定义通过交叉熵损失训练模型：

上面的公式存在的一个问题就是，训练阶段时，Decoder输入的是真实的物品，而在预测时，Decoder输入的是上一阶段输出的物品，这就容易导致错误积累的问题，这个问题在很多NLP的生成任务上都有讨论。因此我们设置在训练阶段时，Decoder输入也直接使用上一阶段输出的物品，则损失函数变为：

• 3.2.2 Learning from Rewards

这里复用强化学习的基本概念，把作为状态state的话，decoder阶段输出的组合A可以看作动作action，而policy则是联合概率分布。强化学习可以通过定义reward来直接优化问题的目标，因此我们定义了一个simulator来计算state和action对应的reward，直接使用历史数据作为reward的话显然是不够的，因为大量的(state, action)组合没有出现过。因此我们借鉴了逆强化学习（InverseReinforcement Learning）的思路，来训练一个奖励估计器（Reward Estimator）。这个估计器也比较简单，即基于历史数据来训练一个给定物品集合A和用户u的二分类模型，然后定义损失函数是logloss：

有了这个奖励估计器，就可以通过策略梯度的方法训练网络：

其中，奖励函数归一化到-1到1之间。

由于通过REINFORCE方法训练policy时奖励函数是delayed，并且“正反馈”也很稀疏（一般来说用户点的少看得多），这样也会导致训练时很难收到正向的reward，使得训练变得很不稳定，并且收敛很慢。因此，我们借鉴了“爬山法”的思想，每次保存5个结果，并从这5个结果中选择能获得最大奖励的一个结果进行模型训练。

• 3.2.3 Combination

结合上文说的两种训练方式，模型的最终loss为：

这里有一个非常重要的参数来调节监督学习训练和强化学习训练的相对比重，而且可以根据训练过程做相应的调整（如初期设置较大的监督学习比重，随后慢慢变小，逐渐向强化学习方式偏移）。整个Reinforcement learning from Demonstrations方法可以总结为下面算法流程：

4.实验

4.1 实验评估方法

首先我们不能使用传统的排序方法的评价指标，如NDCG或MAP等，这些方法依赖对每个物品进行打分或者假设一个“好”的物品应该排在靠前的位置，因此并不适用于Exact-K推荐的问题。这里我们定义了两种离线实验的评估指标，分别定义为Precision@K和Hit Ratio@K：

其中，Hit Ratio是一个基于覆盖率的指标，解释为生成的物品集合A里面有多少是覆盖到用户真实偏好的物品集合的；Precision是一个基于准确度的指标，解释为生成的物品集合A中是否包含了用户点击的物品。

4.2 Baseline比较方法

在文章中我们比较了三种典型的排序学习方法：Pointwise、Pairwise和Listwise的方法。其中，Listwise方法最符合我们的问题，因为同样考虑了排序物品之间的上下文信息。其中代表性的工作是发表在SIGIR 2018的DLCM方法，该方法使用了GRU的循环神经网络对排序物品进行建模，同样地我们任务将GRU替换成Transformer效果会有进一步的提升。但是上述方法只是使用了监督学习的方法对问题进行求解。

4.3 实验数据集

首先，我们使用了公开的MovieLens数据构造了我们问题的数据集，其中分别构造了MovieLens(K=4, N=20) 和MovieLens(K=10, N=50) 两种数据集设置。于此同时，我们也使用了淘宝线上真实的数据集Taobao(K=4, N=50)，这个数据集的使用场景可以参考我们另一篇论文（已被CIKM2019接受）：https://arxiv.org/pdf/1907.01639。

4.4 实验结论

整体的实验结果如下表所示：

可以看到我们的方法在所有数据集上都达到了最优的表现，于此同时可以看出Listwise的效果要远好于Pairwise和Pointwise方法，证明了论文中所说的上下文建模的重要性，同时基于Transformer的Listwise方法要优于基于GRU的方法，也验证了引入Multi-head Self-Attention对上下文建模的优势。

在论文中，我们也做了多组的ablation tests，优于篇幅的原因这里就不一一介绍。这里只强调一下一个相对来说最重要的超参数，用于调节训练时监督学习loss和强化学习loss的比重。如下图所示：

在图中可以看出，在时效果最好。进一步看，当只使用监督学习loss（也就是）时，我们可以初步得到一个较好的“次优解”，后面当逐渐加入强化学习方法时（减小），效果会进一步提升达到更优的解。这也验证了我们在论文中提出的“Reinforcement Learning from Demonstrations”的训练方法，可以达到兼顾sufficiency-and-efficiency的效果。

关于我们

在猜你喜欢团队工作，你将要解决的问题域涉及对上亿用户在几十亿商品池中的推荐问题，不仅仅要考虑CTR、成交金额等业务指标，还需要系统化的解决上千万卖家流量博弈的机制设计，以及推荐系统与用户的交互体验。团队内的算法工程师和科学家将与你一起解决世界上规模最大电商平台上最困难的业务技术难题。在过去的几年间，猜你喜欢团队所负责的场景核心用户指标一直保持非常高的增长速度，目前组内成员多来自国内外知名院校和研究所，近年在SIGKDD、AAAI、CIKM、WWW等学术会议上发表多篇论文。欢迎加入我们！邮箱：gongyu.gy@alibaba-inc.com

论文已被接收在SIGKDD 2019 research track oral。