Press "Enter" to skip to content

淘宝 at KDD 2019,解决推荐中带约束的Top-K优化问题

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

今天介绍的这篇文章,来自于阿里巴巴搜索推荐事业部被KDD 2019录取的Research Oral,解决的是在推荐领域里,带约束的Top-K的问题。我们知道,传统的推荐模型都是基于Top-K做推荐的,基于CTR这类指标的评估分数,将排序的前K个结果推荐给用户。但是 往往推荐场景又是存在一定业务约束的,比如一组商品里需要具备足够的多样性 ,这就需要对商品之间的关系进行建模。本文目标即考虑生成一个包含K个结果的带约束的最优化集合,称为 Exact-K 。

 

 

论文:https://arxiv.org/abs/1905.07089

 

代码:https://github.com/pangolulu/exact-k-recommendation

 

摘要

 

最优化带约束的Top-K的问题可以建模为图论中的经典问题—— K团 ,即在图中找到一个K个节点的完全子图,这是一个NP hard的问题。作者提出了GAttN这个模型,利用了Transformer里的self-attention的结构, 输出一个具有内部关系的商品卡片集合 ,而不是单独对每件商品打分。同时,作者提出了另一个方法RLfD, 用强化学习直接优化目标 。文章认为,GAttN是有效率的(efficient),而RLfD是有效充分的(sufficient),最终在模型中用一个参数来调节监督学习和强化学习的比重。

 

背景

 

在很多推荐场景中,我们都需要把多个商品推荐给用户。一方面,我们需要提高页面的整体效率,例如优化点击率,另一方面,为了保障推荐体验,同屏中的商品往往需要满足一定的限制,例如保证多样性。这种带约束的组合优化问题,称为Exact-K。

 

 

问题定义

 

给定一个包含N个商品的集合S,从中选择K个商品组成集合A展示给用户,使得用户对这一屏的点击率最高。假设A中商品两两之间需要满足一定的条件限制C,如果满足限制则权重为1,否则为0。因此Exact-K的问题可以形式化为:

 

 

类比图论中的概念,S中的N个商品作为图中的N个节点,如果商品之间满足了约束条件,则有边相连, 我们需要优化的是在图中找到一个最大的子团 ,既是K团(K个节点的完全子图),又最大化效率。

 

 

方法

 

基于贪心的baseline方法

 

对于给定的用户和候选集合S,计算每个节点的CTR,基于贪心的算法,从当前候选中选择CTR最高的节点,加入到集合A中,把剩下的商品中和A没有相连的节点去掉,重复直到A中有K个商品。 这个方法的问题有两点 :a、CTR的计算没有考虑约束;b、不一定是最优解。

 

GAttN

 

模型整体框架上采用了Encoder-Decoder的结构,如下图:

 

 

Input:输入是商品侧特征和用户侧特征的concat。

 

Encoder:由于输入的商品是无序的,因此Encoder选择了Transformer里的Multi-head Self-Attention,而不是LSTM或RNN等序列结构。

 

Decoder:要输出包含K个节点的完全子图,在结构上首先选择了循环神经网络。具体是采用了pointer-network的做法,用attention的机制,让Decoder从Encoder的输出中,依次选择一个商品加入A。输出集合是A的概率为:

 

 

划重点 :为了确保当前选择的商品和之前选择的在一个完全子图中,通过添加mask的方式,让不满足约束的商品不会被选到。

 

RLfD

 

目前Decoder阶段能计算的是每个阶段的交叉熵损失,这个过程是有监督的, 而优化的最终目标是让集合A的整体点击率最高 ,所以考虑到和实际的目标对齐,用强化学习中的policy-gradient的思路来优化。直接用policy-gradient会比较低效,所以先用监督学习的方法对网络参数进行预训练。

 

监督学习:用线上的真实日志训练交叉熵模型:

 

 

强化学习:由于实际的reward非常稀疏,借鉴逆强化学习的思路,先训练一个奖励估计器,基于历史数据训练一个给定商品集合A和用户的二分类模型。然后用这个奖励估计器,通过policy-gradient的方法训练网络:

 

 

组合:模型最终loss如下。参数用来调节监督学习和强化学习训练的比重。初期监督学习的比重较大,随后慢慢减小,逐渐向强化学习偏移。

 

 

实验

 

文中定义了两个离线评估指标,[email protected]和Hit [email protected],分别代表覆盖率和准确度。模型上比较了Pointwise、Pairwise、Listwise的做法,数据集选择了MovieLens和淘宝自己的数据集Taobao。结果如下:

 

 

可以看到Listwise的方法要远好于Pointwise和Pairwise,证明了上下文建模的重要性。文中还有一些ablation的分析。

 

attention:由于用到了self-attention的结构,可以看到帽子这个商品,对围巾、手套有更高的权重,而对伞这个商品相对较低。

 

 

超参:平衡监督学习和强化学习的参数,最优解在0.5。真实使用时,最开始设为1,只用监督学习的Loss,然后逐渐加入强化学习的方法,效果进一步达到最优,从而兼顾了sufficiency和efficiency。

 

 

总结: 笔者认为本文的亮点有两处 。一是Encoder-Decoder结构的设计,特别是Decoder处用pointer-network的思路,加上mask复现约束条件,就可以达到Exact-K选择的功能。二是监督学习和强化学习的结合,很多时候初版模型的设计可能并不能和我们最终的线上目标对齐,这时候可以通过一些方法做转换、做结合,都可能会起到一些效果。

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注