| 导语 腾讯神盾开放通用推荐系统一般将推荐问题转化为分类问题，而对于列表推荐场景，推荐问题更近似于排序问题。本文将介绍排序学习技术与推荐算法结合的Pairwise方法及其具体实现 – Pairwise Ranking Factorization Machines (PRFM) 算法，并分享PRFM算法在手Q动漫Feeds流推荐场景的应用，供想在其他场景应用此算法的同学参考。
1. 概述
目前神盾推荐中的算法一般将推荐问题形式化为二元分类问题：以动漫推荐为例，如左图所示，对于用户与他所曝光的物品集合，把点击看作正样本 (标签=1)，未点击看作负样本 (标签=0)，可以构造由<用户，物品>与标签构成的训练样本，用于训练一个二分类模型。
这种方法称为Pointwise方法，即模型在参数训练阶段只考虑对每个<用户，物品>独立的打分，目标是使得所有正样本的打分高于负样本的打分。如左图的例子所示，Pointwise方法的训练目标是：模型给<小蓝，狐妖小红>，<小蓝，浪客剑心>，<小黄，龙珠>的打分都高于<小蓝，妖神记>，<小黄，名侦探柯南>。
仔细思考不难发现Pointwise方法的缺点，比如对小黄来说，只需要模型给<小黄，龙珠>的打分高于<小黄，名侦探柯南>即可，至于<小黄，龙珠>的打分是不是高于<小蓝，妖神记>并不重要。抽象来说就是：Pointwise方法没有考虑对同一个用户而言物品与物品之间的排序关系。
本文介绍的Pairwise方法对Pairwise方法的不足做了改进，训练样本由<用户，物品1，物品2>三元组构成，其中物品1为此用户点击了的物品，物品2为此用户未点击的物品。Pairwise方法侧重于判断物品对<物品1，物品2>是否满足顺序关系 (即<用户，物品1>的打分是否高于<用户，物品2>)。如下图所示，Pairwise方法在模型训练阶段的目标是：<小蓝，狐妖小红娘>打分高于<小蓝，妖神记>，<小蓝，浪客剑心>打分高于<小蓝，妖神记>，<小黄，龙珠>打分高于<小黄，名侦探柯南>。
另一方面，在Pointwise方法的样本构造中，我们简单地将点击看作正样本、未点击看作负样本，等于给Pointwise方法加了一个假设：用户点击的物品是用户明确喜欢的，未点击的物品是用户明确不喜欢的。事实上，点击行为属于隐式反馈，这个假设显得过于强烈。而Pairwise方法的假设更符合实际：相对于用户未点击的物品，用户更喜欢那些他点击了的物品。
Pairwise方法作为排序学习 (learning to rank) 技术与推荐系统算法的结合，近年来得到了学术界与工业界的密切关注与研究。本文介绍的Pairwise Ranking Factorization Machines (PRFM) 算法是Pairwise方法的一种具体实现，我们在神盾推荐中实现了PRFM算法，并应用在手Q动漫首页Feeds流推荐场景。与Pointwise FM算法对比，使用同样的特征，PRFM算法在uv点击率上获得了大约5%的相对提升。
2. PRFM 算法细节
与Pointwise方法一样，Pairwise方法可以选择不同的模型给<用户，物品>打分，如LR、FM等。由于FM模型能节省LR模型在特征工程上的人力消耗，且实践证明FM使用原始特征能比人工调优后的LR取得更好的线上效果 ，因此我们选取FM模型为打分公式。在样本构造方面，对每个用户可以构造许多物品对<物品1，物品2>从而得到<用户，物品1，物品2>的样本实例。如果考虑所有的样本实例，会导致样本过大无法训练，为此我们采取的策略是: 对每个用户随机选取100个物品对。
上述的样本构造与打分模型构成了Pairwise Ranking Factorization Machines (PRFM) 算法。下面介绍关于PRFM算法的一些数学细节，不感兴趣的同学可以跳过这部分。
FM模型的打分公式为：(为由用户特征、物品特征、上下文特征等组成的特征向量)
其中
为需要训练的参数。参数训练中用到的损失函数定义为：
3. 排序算法离线评价指标与参数调优
与分类问题使用AUC作为评价指标不同，用于衡量排序性能的常用评价指标主要有precision at k, MAP (mean average precision), 与NDCG (normalized discounted cumulative gain) at k。下面我们通过一个例子简单介绍这几个指标的定义与计算方法 (如下左图所示的曝光物品列表中，绿色代表用户有点击的物品，灰色代表用户未点击的物品)。
Precision at k: (Prec@k)
用户有点击的物品在列表的前k个物品中的比例，值越大表示推荐质量越高。如左图的例子，列表(a)的precision at 5 = 2 / 5 = 0.4，列表(b)的precision at 5 = 1 / 5 = 0.2。对每个用户可以计算一个Precision at k，对所有用户取平均即得到用户集合的precision at k。
MAP (mean average precision):
可以看成precision at k的加强版，把用户有点击的物品在列表中出现的位置加入指标的计算中，值越大表示推荐质量越高。AP (average precision) 指在每个用户有点击的物品所在位置k求一次precision at k，然后求平均。如列表(a)的AP=(1/2 2/4)/2=0.5，列表(b)的AP=(1/4 2/7)/2=0.268，由此可见，从precision at 10的角度看，列表(a)与(b)没有优劣之分，但从AP的角度看，列表(a)优于列表(b)。同样地对每个用户可以计算一个AP，对所有用户取平均即得到用户集合的MAP。
NDCG (Normalized Discounted Cumulative Gain) at k: (NDCG@k)
NDCG at k的计算较为复杂，不在这里详细介绍，感兴趣的同学可以自行搜索 。简单来说，在NDCG的计算中，用户有点击的物品在列表中出现得越靠前被认为越有价值，与MAP的思路一致。
了解算法的离线评价指标后，我们可以对其进行参数调优。与Pointwise FM算法 相同，PRFM算法可以调优的参数有：模型参数初始化时使用的正态分布标准差(init_std)、正则化系数(reg)、隐向量维度(factor)。下图展示了在手Q动漫Feeds流上的调优示例，根据调优结果我们决定使用的参数为：init_std=0.005，reg=0.0001，factor=100。
注：橙色框表示调整的参数，绿色框表示各指标的最大值
4. 算法改进计划
上文中提到，PRFM算法的样本构造方法是对每个用户随机选取100个<物品1，物品2>的物品对，但有研究表明，使用不同的抽样策略可以提升模型效果 (见参考资料1)。例如：对每个用户，将物品对<物品1，物品2>按物品1与物品2在曝光列表中出现的位置之差从大到小排序，取排在前面的100个。此抽样策略的思路是：物品1与物品2在曝光列表中出现的位置之差越大，表示在这个物品对中，相对用户未点击的物品，用户有点击的物品排得越靠后，即<物品1，物品2>的在列表中顺序关系错误，模型更需要在这些物品对上进行训练。后续我们将在神盾推荐中尝试各种不同的抽样策略，再把经验分享给大家，欢迎感兴趣的同学与我们一起探索！
参考资料
1. PRFM论文 (http://wnzhang.net/papers/lambdafm.pdf)
2. 排序评价指标 (https://spark.apache.org/docs/2.2.0/mllib-evaluation-metrics.html#ranking-systems)
