淘宝 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如下。参数用来调节监督学习和强化学习训练的比重。初期监督学习的比重较大，随后慢慢减小，逐渐向强化学习偏移。

实验

文中定义了两个离线评估指标，Precision@K和Hit Ratio@K，分别代表覆盖率和准确度。模型上比较了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选择的功能。二是监督学习和强化学习的结合，很多时候初版模型的设计可能并不能和我们最终的线上目标对齐，这时候可以通过一些方法做转换、做结合，都可能会起到一些效果。

推荐阅读

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

太赞了！Springer面向公众开放电子书籍，附65本数学、编程、机器学习、深度学习、数据挖掘、数据科学等书籍链接及打包下载

数学之美中盛赞的 Michael Collins 教授，他的NLP课程要不要收藏？

自动作诗机&藏头诗生成器：五言、七言、绝句、律诗全了

这门斯坦福大学自然语言处理经典入门课，我放到B站了

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。

阅读至此了，点个在看吧 :point_down: