排序算法实验研究论文

免费查阅文献的刊物，你可以看看（计算机科学与应用）等等这些

在CTR预估中，为了解决稀疏特征的问题，学者们提出了FM模型来建模特征之间的交互关系。但是FM模型只能表达特征之间两两组合之间的关系，无法建模两个特征之间深层次的关系或者说多个特征之间的交互关系，因此学者们通过Deep Network来建模更高阶的特征之间的关系。因此 FM和深度网络DNN的结合也就成为了CTR预估问题中主流的方法。有关FM和DNN的结合有两种主流的方法，并行结构和串行结构。两种结构的理解以及实现如下表所示： 今天介绍的NFM模型(Neural Factorization Machine)，便是串行结构中一种较为简单的网络模型。 我们首先来回顾一下FM模型，FM模型用n个隐变量来刻画特征之间的交互关系。这里要强调的一点是，n是特征的总数，是one-hot展开之后的，比如有三组特征，两个连续特征，一个离散特征有5个取值，那么n=7而不是n=3.                      可以看到，不考虑最外层的求和，我们可以得到一个K维的向量。对于NFM模型，目标值的预测公式变为：                      其中，f(x)是用来建模特征之间交互关系的多层前馈神经网络模块，架构图如下所示： mbedding Layer 和我们之间几个网络是一样的，embedding 得到的vector其实就是我们在FM中要学习的隐变量v。 Bi-Interaction Layer 名字挺高大上的，Bi是Bi-linear的缩写，这一层其实是一个pooling层操作，它把很多个向量转换成一个向量，，其实它就是计算FM中的二次项的过程，因此得到的向量维度就是我们的Embedding的维度。最终的结果是：                      Hidden Layers就是我们的DNN部分，将Bi-Interaction Layer得到的结果接入多层的神经网络进行训练，从而捕捉到特征之间复杂的非线性关系。 在进行多层训练之后，将最后一层的输出求和同时加上一次项和偏置项，就得到了我们的预测输出：                      NFM模型将FM与神经网络结合以提升FM捕捉特征间多阶交互信息的能力。根据论文中实验结果，NFM的预测准确度相较FM有明显提升，并且与现有的并行神经网络模型相比，复杂度更低。 NFM本质上还是基于FM，FM会让一个特征固定一个特定的向量，当这个特征与其他特征做交叉时，都是用同样的向量去做计算。这个是很不合理的，因为不同的特征之间的交叉，重要程度是不一样的。因此，学者们提出了AFM模型（Attentional factorization machines），将attention机制加入到我们的模型中。 论文： Neural Factorization Machines for Sparse Predictive Analytics

关于推荐系统中的reranking问题。作者信息： 文章比较简单，思想也不错，并且据称实践中也给力。简单翻一下。 摘要：排序是推荐系统的一个核心问题，目的是给用户一个“排好序的”item list。通常这个ranking function是从labeled dataset里学到的，通过优化全局表现。这个function对每个item给一个得分。但是这个function可能是次优的，因为它是对每个item“独立”应用的，而且没有显式地考虑item之间的关系，也没有考虑用户偏好的不同。于是这篇文章就提出了PRM。这个reranking模型可以接在任何排序模型后面。它直接优化整个的推荐列表，通过“使用transformer结构来encode列表中的item信息”。其中，这个transformer用了self-attention机制，它直接对任意pair的item间的联系建了模。通过加入一个预训练好的学习用户偏好的embedding，效果还会进一步提升。实验结果有离线也有在线，都是显示出PRM的牛逼。 1  introduction 通常推荐系统的流程是：若干召回->粗排->排序->重排。若干召回的目的是从超级大的item集合中挑出一部分；粗排是从召回的这些中再挑出一部分（一般千级别）；排序是从粗排的这些中再挑出一部分；重排是对排序出来的这些（一般最多也就几十的量级）重新排个序展示给用户。其实排序和重排序没有本质的区别，只是量级问题而已。我感觉。所以没必要太区分排序和重排序，反正都能用。 “排好序”的item list对用户的满意度有很大影响，对推荐系统的收益也有很大影响。现在已经有很多排序算法了。典型的排序一般只考虑了user-item pair features, 但是没考虑其他item的影响。虽然pairwise和listwise 的learning to rank方法尝试解决这个问题，通过把item-pair或者item-list当做输入，但是他们只专注于对label数据（点击）的优化，没有显示考虑特征空间中item之间的关系。 一些工作就尝试考虑item之间的关系，然后改善一些排序模型给出的“序”，这就是reranking。核心思想就是encode intra-item patterns到特征空间，然后打分。目前最好的encode方法是RNN-based的，比如GlobalRerank, DLCM。他们按次序输入初始list，然后按时间步输出encoded vector。然鹅，rnn-based方法在对“list中的item之间的交互”的建模上能力有限。The feature information of the previous encoded item degrades along with the encoding distance. 受到机器翻译中的transformer结构启发，文章提出用transformer来学item之间的交互影响。transformer结构用了self-attention机制，这就使得任意两个item之间都是直接产生关系，不用随着编码距离变远而降低。同时，比rnn好的一点在于可以并行化，效率高。 不仅是item之间的交互，个性化的encoding也要考虑进来。推荐系统的reranking是user-specific的，决定于用户的偏好。比如说，对于价格敏感的用户，你就应该加大价格的权重。经典的全局的encoding也许不是最优，就是因为忽略了用户之间的不同。例子，用户想比价的时候，就应该集中展示不同价格的相似物品；用户没有明显购买欲望的时候，推荐就应该更多样化。于是提出的PRM就既考虑了item之间的相互关系，也考虑了个性化。 论文贡献：（这里可以不用看，不影响。其实主要就是model和data。。problem和evaluation不是应该的吗。。） 2  相关工作 rerank是在ranking模型后的提升，在这些ranking模型中，learning to rank是最广泛使用的方法之一。learning to rank(LTR)可以概括成三类：pointwise\pairwise\listwise。这些都是学的global scoring function，对于某个特征的权重是全局学来的（也就是不个性化）。这样不行啊。 后面简单介绍了下其他人在reranking方面的工作。有的用单向GRU来encode整个list到每个item。有的用LSTM啊什么什么的。他们的能力受到encoding distance的限制。transformer不受这个影响，因为任意item之间距离是O(1)的。而且，用decoder来序列产出list的话，不适用于线上，受不了这个延迟啊。也有提出了groupwise方法的，也可以冰箱，但是计算开销太大了。 3  reranking model formulation LTR在信息检索和推荐系统里用的很多。它的loss function： 其中R是所有用户的请求集合；I_r 是对于请求r的候选集；x_i是item i的特征表示; y_i是item i的label，也就是是否点击。P是预测的点击概率，theta是前置排序模型的参数； 光有x还不够，还需要（a）item-pair之间的相互影响（b）用户物品之间的交互。所谓（a）其实可以直接从LTM模型给出的 对于请求r的初始list S_r 中学到，有一些工作已经探索过了。但是还没有探索（b）的。不同用户的item-pair相互作用应该是不同的。本文会引入一个个性化矩阵PV来学习user-specific encoding function。loss是： 其中 S_r 是前置排序模型给出的初始排序， theta尖 是reranking模型的参数，X是特征矩阵。比较两个损失函数，其实很像，只是多了个PV而已。 4  personalized re-ranking model 模型结构 三部分：输入层、编码层、输出层 input layer 输入层的目标就是学习初始list中所有item的综合表达。前置排序模型给出初始list，记为 S = [i_1, i_2, ..., i_n] ；item的原始的特征矩阵 X \in \Re^{n*d_{feature}} （跟ranking模型一样的）. X的每一行是item i的特征向量x_i 。 Personalized Vector (PV). 其实初始的list可以部分反映用户的偏好了（毕竟是排序出来的东西），但还不够。Figure 1(b)里，把 X 和 PV 拼起来，得到中间embedding矩阵 E^{'} \in \Re ^{n*(d_{feature}+d_{pv})} : PV是由一个预训练的模型产出的（后面介绍）。 Position Embedding (PE)。 为了利用list的序列信息，我们又加了一个位置embedding PE \in \Re ^{n*(d_{feature}+d_{pv})}，可以看到这个维数跟E' 一样。PE是可学习的，这样效果会略好。 最后用一个简单的feed-forward网络把E'' 映射到 E \in \Re ^{n*d} , d是encoding层的输入维数（显然）：下面公式等号右边的E应该带两撇 encoding layer encoding层的目标是集成一下“item-pair之间的相互关系”和其他信息（包括用户偏好、初始list里的顺序）。这里就引进了transformer。因为transformer在NLP任务里太屌了呀，尤其是在机器翻译中的编解码能力超过rnn系列。而且自注意力机制很适合reranking，因为任意两个item都产生了关系（反复在说这一点）。图1(a)是一个基本结构示意。图1(b)里可以看到，encoding模型包括N_x 个transformer块，每个块包含一个注意力层和一个前向网络层。 Attention Layer: 这里其实就是基本的attention，可以参考 刘岩：详解Transformer （Attention Is All You Need） The Illustrated Transformer ，感觉讲的很好。 然后为了表示更复杂的关系，用多头attention： Feed-Forward Network: 文章里说前向网络主要是增强模型的非线性和对不同维度输入向量的交互。注意这里的前向其实是residual connection（不觉得跟resnet很像吗），虽然这里没有提，但是实验结果里分析了。 Stacking the Encoding Layer: 一个attention加一个ffn当成一个块，多个块stacking就可以得到更复杂的高维的交互信息。 Output Layer 输出层就是对每个item给个分数。这里只用了一个线性层，加softmax（全连接嘛）。 在训练阶段，用点击数据作为label，并最小化损失函数： Personalized Module 在这部分，说一下怎么得到PV。图1(c)就是本文用的结构。H是用户历史。loss是 D是展示给用户的物品集合，theta' 是模型参数，y_i 是label。最后用 sigmoid 之前的隐藏层作为 pv_i 表示。 图1(c)只是其中一种结构，其他的模型也可以用在这里，比如FM, FFM, DeepFM, DCN, FNN, PNN等。 5  实验结果 其实论文的实验结果大都没什么好看的。反正都是说提出的东西最屌。这篇文章里的实验部分有一个优点，就是做了ablation study，让大家知道哪部分最重要。 数据 一个是雅虎的数据，一个是电商数据（虽然没说，想也知道是淘宝）。 雅虎数据其实不适合直接用，所以做了一些转换。（不重要。。其实我没仔细研究=.=） baseline 考虑了实际情况，比如说rnn的（GlobalRerank）不用，并行太困难了；再比如开销大的（Seq2Slate\GlobalRerank）不用，线上撑不住。主要是四个： evaluation metrics 这两个显然都是越大越好，它们是用来离线评价的。线上的话用更有说服力的指标： PV:：物品总展示 IPV：物品总点击 CTR：点击率，IPV/PV GMV：用户在推荐的物品上花的总钱数 experimental settings 对于baseline和PRM，关键的超参数是一致的。具体就不写了，不重要。 离线实验 雅虎数据集上的实验 探索两个问题：0. PRM是不是真的最好？为什么？ 1. 不同的LTR提供初始list，表现是不是不同？ 看文章之前我就可以回答这两个问题了，PRM当然最好，接不同的LTR表现当然不同。。 结果： 雅虎数据集不包含用户相关信息，所以没有personalized module，所以叫模型叫PRM-base。即使这样，它也最厉害。PRM-BASE比DLCM表现好，主要是因为transformer牛逼。 然后做了ablation study看看这些部件哪个贡献大。 其中，PE是位置embedding，RC是残差连接。 去掉PE效果严重下降，这就是说初始list里的顺序很重要（人家排序模型辛辛苦苦排出来的，能不重要么）。残差连接和dropout影响不大，可以说明模型不太有梯度消失和过拟合问题。block是先增后减，因为太多会过拟合。注意力的头数影响不大，跟NLP不太一样。考虑到开销问题，推荐用1个就够了。 电商数据的离线实验 探索问题：加上personalized module的话，PRM表现怎么样？ 这里偷懒了，直接用线上的DNN-based LTR作为前置排序模型，而且直接就不比其他baseline了，只比DLCM。（感觉不太严谨。。。不过影响不大） 结果可以看到，PRM-BASE还是好过DLCM，而加了Personalized-pretrain就更好了。PV很关键。PRM-Personalized-Pretrain两个优势： 预训练模型可以完全利用用户的更长的log，来提供更通用、更好的用户偏好表示。 PV学好了，PRM可以从中学到更好的encoding，更个性化了。 online experiments 当然也做了线上ab实验。结论一致。 注意力权重可视化 探索问题：自注意力机制真的能学到有意义的信息吗？ 画了几个热力图，可以看到相关的确实相关，挺合理的。 6  结论和未来 PRM好啊，用transformer既学了item之间的依赖关系也学了用户和item之间的交互关系。 作者认为优化一下label空间也会有用。 下一步要研究reranking实现多样性。