导读
互联网搜索推荐广告排序系统的重排序模块，对精排生成的Top-N结果重新排序，生成Top-K个物品列表，最终展示给用户，在系统中发挥着至关重要的作用。本文将总结回顾下工业级搜索推荐广告系统重排序的经典工作和发展路线。
1. 重排序简介
在互联网应用中，例如电商（淘宝、京东、拼多多、亚马逊）、信息流（头条、微博、微信看一看）、搜索（百度、Google)、社交（Facebook)、短视频（抖音、快手、微信视频号）等、生活服务（饿了么、美团），搜索推荐广告的排序系统从海量的物品中选取Top-K个商品展现给用户，为用户提供个性化的服务。排序系统一般包括召回（亿级）、粗排（十万级）、精排（千级）、重排序（百级）等多个阶段。精排阶段完成对物品进行pointwise的打分，计算出精排排序分数，然后按分数降序排列，生成Top-N个物品的序列。重排序阶段对精排生成的Top-N个物品的序列进行重新排序，生成一个Top-K个物品的序列，作为排序系统最后的结果，直接展现给用户。例如，下图展示了淘宝搜索和推荐重排序的结果。在搜索系统中，短query具有歧义、宽泛性，用户的兴趣也是多样的，通过展示多样（品牌、风格、价格）的结果，可以给用户更多选择机会和新发现。在推荐系统中，为用户展示多种素材类型（视频、商品、频道、主题）等，有助于提升浏览深度和用户停留时长。
（1）为了建模多个物品间的互相影响，从而生成更好的Top-K物品序列，提升效率：精排模型通常学习的是物品pointwise的得分，直接根据精排分数排序，无法考虑多个商品间的影响，而且同质化严重（相似的商品得分相似所以位置接近，但同时点击的概率很少），缺少发现性，用户体验很差。(2) 多样性：通过重排序提升Top-K商品的信息覆盖度、减少信息冗余。通常query包含多种信息需求，通过展示多种类型的商品，能够提升Top-K商品的覆盖度，同时避免无效曝光多个类似的物品。多样性能带来发现性：用户发现多种商品、新的兴趣，同时系统能了解更多用户。合适的多样性，通常对实现重排序目标有重要的作用。(1) 短期目标：提升结果的效率（点击、购买、GMV等）；提升结果的多样性、发现性和用户体验；降低负反馈（结果同质化严重、看/点/买了还推）。(2) 长期目标：提升用户流量深度、停留时长；提升用户复访、留存、长期用户价值。（1）解空间大。重排序问题是从Top-N个商品的排列，生成Top-K个商品的排列，解空间（
）为指数级，生成最优解为NP-hard问题。
(2) 每种Top-K个商品的排列的reward难以预测。（3）海量的状态空间（用户状态）和解空间，导致难以有效探索和学习。
重排序的主要工作包括 MMR [1-5], DPP [6-9], Context-aware List-wise Model [10-15], 基于Reinforcement Learning [16-22]的方法。（2）模型：模型如何设计的（假设条件、模型结构）？如何训练的（损失函数）？如何预测的（贪心等）？通常将用户在Top-K个商品的真实反馈行为作为ground truth。如果重排序模型能将用户点击的商品排到更前面，NDCG越高，重排序效率指标越好。在论文 [23]里，作者提出的α-NDCG指标能同时表达结果的准确度和多样性。重排序结果有比较高的α-NDCG，意味着Top-K结果的效率高（能将用户点击的物品排到前面）、多样性好。通常q (query) 和d (document)都包含多个维度的信息，q和d相关的条件是至少一个维度有交集。如果让评测者评价q和d是否相关，存在一定的评价误差，用α来衡量，如下面所示：排序结果中，第k个位置的增益gain定义如下：其中r表示前面k-1个与query相关的个数，相当于出现信息重复会对增益进行惩罚。多个位置的累积增益Cumulative Gain为：考虑位置降权（希望将用户点击的物品排到前面）的Discounted Cumulative Gain为：除以最优排序的DCG后的Normalized Discounted Cumulative Gain为：
3. 重排序模型详细介绍
3.1 MMR: Maximal Marginal Relevance [1-5]在SIGIR 1998论文[1]里，作者定义了经典的MMR方法：
其中Q是搜索查询query, D是候选的相关物品（例如精排后的结果），S是MMR算法已经选取的物品，Sim1用来衡量物品Di和query Q的相似度，Sim2用来衡量物品间的相似度，
是平衡相关度（例如CTR）和多样性的超参数。公式中
建模了当前候选的物品
和搜索query
的相似度，
表示当前候选的物品
和搜索已经选取的物品的最大相似度。
MMR算法的思想是：采取贪心策略，生成top K结果列表。第一次，先选取相关度最高的物品。然后，每次选取和查询query匹配度高、和已经选取的物品最大相似度低的物品。相似度函数
和
可以不同，根据业务需求来定。
MMR成功应用到Microsoft [3]、Amazon [5]、JD的搜索推荐系统中。例如，在工业级电商信息流推荐系统中，相似度函数
为精排分数，
为添加新商品前后选取的商品集合的类目分布的KL距离，再结合后续的业务规则，构成了简单有效的重排序模块。
3.2 DPP: Determinantal Point Processes [6-9]DPP [6-7]，即行列式点过程，成功应用到Google [6]、Hulu [7]、Huawei [8]、Microsoft [9]等推荐系统中。模型的输入包括：（1）物品的精排分数（2）任意两个物品间的pairwise距离（可以基于jaccard、embedding等计算）。模型优化目标是：生成Top-K结果的效率和多样性。其中效率通过是否能将用户点击的物品排到靠前的位置来衡量。DPP [6] 包括基于Kernel Parameterization和基于深度学习的版本。（1）基于Kernel Parameterization的DPP：在Kernel Parameterization中，基于输入的Top-N个物品的精排分数、任意两个物品间的pairwise距离，来定义一个N * N 的 DPP kernel matrix：
在这个矩阵中：对角线的元素基于物品的精排分数计算，衡量了物品的质量；其他元素由对应的两个物品的精排分数和它们的pairwise共同决定，同时建模了物品的质量和多样性信息。从N个物品中选取K个元素，这K个元素对应的矩阵是N * N的矩阵由对应位置元素构成的子矩阵。例如，当K=2时，我们选取 N * N 矩阵的第 1, 2行和列，构成了一个小的子矩阵，这个子矩阵的行列式同时衡量了这两个选取的元素的质量和多样性。当这两个元素的精排分数越大、相似度越低，那么对应的行列式值越大，结果越好，如下面所示：
因此，DPP模型中，从Top-N生成Top-K的任务，对应了从 N * N的矩阵中选出一个 行列式值最大的 K * K的小矩阵，对应的K个元素，就是重排序的最优结果，即效率和多样性都很好。在基于Kernel Parameterization的DPP中，模型参数只有α和σ，可以通过Grid Search来搜索最优解（如下图所示），其中基于NDCG衡量生成结果的好坏，即是否将用户实际点的物品排到前面。
在基于Kernel Parameterization的DPP中，基于输入的Top-N个物品的精排分数、任意两个物品间的pairwise距离，人工定义了一个矩阵。基于Deep Learning的DPP中，定义矩阵中的元素如下所示：其中，f函数的输入为精排模型最后一层隐藏向量，g函数的输入为物品的向量表示。
基于Deep Learning的DPP，通过MLE来学习模型参数，即最大化用户实际交互的物品的log-likelihood。
学习完模型参数后，在生成Top-K结果时，作者使用了Greedy的方法。DPP在Youtube视频推荐中取得了很好的线上效果：
3.3 Context-aware List-wise Model [10-15]Context-aware List-wise Model [10-15]，通过建模精排模型生成的Top-N个物品间的互相影响关系，来生成Top-K结果。包括miRNN [10], DLCM [11], PRM [12], EdgeRec [13], PRS [14], AirbnbDiversity [15]等，成功应用到淘宝搜索、推荐、Airbnb搜索的重排序中。在淘宝搜索中，每个商品是否会购买，会受到周围展示的商品的影响。例如周围同类目商品比当前商品显著贵，那么当前商品购买的概率可能就比较高。miRNN中，作者使用RNN来建模context信息，优化淘宝搜索重排序，生成Top-K列表结果，来实现电商GMV最大化的目标。淘宝搜索中，需要生成一个Top-K的商品列表，其对应的期望GMV，基于商品价格、预估购买每个商品的概率来计算：
优化目标是，生成一个Top-K列表结果，使得期望GMV最大化：
这个问题可以分解成两个问题：（1）估计每个商品在Top-K列表上下文下购买的概率。（2）有效找到最优Top-K排列。
在论文中，作者使用全局信息来建模多个商品列表的context信息，即基于多个商品的属性特征特征（例如价格）的最大值、最小值，来归一化每个商品的属性特征，生成全局特征。再结合商品自身的属性特征，来表达每个商品。对于问题1，即预测给定排列情况下每个商品购买的概率，作者采用RNN来建模，即考虑前面已经选取的物品对后面商品购买的影响。
对于问题2，即有效找到最优Top-K排列，作者基于学习得到的购买预测RNN模型，和Beam Search来解决。miRNN模型，在淘宝搜索线上取得了很好的GMV收益。
DLCM中，通过建模精排生成的Top-N列表中物品间的互相影响，来优化搜索结果。基于的motivation是：通过建模排生成的Top-N列表中物品信息，可以补充query的信息。通过建模Top物品的局部信息，来改进排序结果。具体地说，DLCM中，作者将精排生成的Top-N列表的逆序作为RNN模型的输入，生成Top-N列表中物品的新的分数。逆序的作用是，可以最大程度将精排分高的物品信息，保存到到RNN的隐藏向量中，来补充query的信息，这样其他和精排分高的物品相似的物品的得分也会比较高，从而改进了排序结果。
作者通过用户实际反馈数据，来学习模型参数，即希望该重排序模型将用户点击的物品排在前面。PRM中，作者使用Transformer来建模生成的Top-N列表中物品间的互相影响，来生成重排序结果，应用到淘宝推荐。每个物品的信息包括：物品特征、精排模型的最后一层向量（即基于用户和物品生成的向量信息）。
和DLCM方法一样，作者通过用户实际反馈数据，来学习模型参数，即希望该重排序模型将用户点击的物品排在前面。EdgeRec中，作者通过RNN和attention建模精排生成的Top-N列表信息、最近的点击物品序列、曝光给用户未点击的物品序列 ，来生成Top-K结果，应用到淘宝推荐。通过端计算，实现系统ms级别响应用户反馈。模型结构如下：中间的部分为通过RNN建模精排生成的Top-N列表信息，左侧为通过RNN和attention建模曝光给用户未点击（不感兴趣）的物品序列，右侧部分为通过RNN和attention建模用户点击（感兴趣）的物品序列，从而推荐出更多和点击商品相似、和曝光未点击商品不相似的物品。
PRS中，作者将重排模块拆分成召回、排序两个部分。
在召回部分，作者估计当前排列情况下下一个商品的reward, 通过Beam Search，来生成候选Top-K结果集合。其中当前排列情况下下一个商品的reward，基于当前排列情况下下一个商品点击的概率、继续翻页的概率来计算 （可以通过模型来学习这两个概率）。在排序部分，和DLCM类似，通过RNN来建模Top-N物品的关联关系，生成新的得分。3.3.6 AirbnbDiversity [15]Airbnb搜索重排序模块多样性的优化，参见Airbnb搜索：重排序阶段如何优化搜索结果多样性？。3.4 Reinforcement Learning [16-22]基于强化学习优化重排序模块的方法，包括 Evolution Strategy [16]，Slate-Q [17,18]，Seq2slate [19]， GAttN [20] 等。实用RL来优化重排序看起来是很直接和顺其自然的（seq2seq生成+基于reward的优化），但难点在于状态空间和action空间是海量的、reward难以计算，因此优化时比较困难。3.4.1 Evolution Strategy [16]电商的搜索推荐排序中，通常基于物品的CTR、CVR、价格，和排序公式来进行排序。这些排序公式，通常包括一些超参数，即系统可以选取的action。其中，作者通过linear model来实现从用户状态到action的映射。
这篇论文中，作者通过Evolution Strategy，学习linear model的参数，在每种状态（state) 下，选取最佳超参数（action）来优化目标。
生成Top-K问题的难点之一，在于生成的Top-K列表的reward难以估计，Slate-Q中作者通过假设近似，将生成的Top-K列表的reward分解到每个item的reward，来解决这个问题：
其中A为Top-K列表，P(i|s, A)为给定Top-K列表下每个商品的选取概率（根据CTR进行归一化计算）， Q(s,i)为每个item的reward。作者通过DNN同时预测物品的CTR和Q value，基于SARSA学习Q网络参数。最后，作者通过贪心算法，生成Top-K列表，应用到Youtube视频推荐中，取得了很好的线上效果：
基于强化学习的视角，重排序，即基于Top-N的序列生成Top-K的序列并且使得Top-K的reward最大。其中，序列生成可以基于Pointer Network。难点在于状态空间和解空间太大，因此这个RL问题实际上是比较难以优化的。作者在这篇论文里，给出了一些实用的优化方法。
GAttN中，作者基于Self-Attention编码精排生成的Top-N列表，基于Pointer Network生成Top-K的结果，然后基于RL来优化模型，应用到淘宝推荐。
https://github.com/guyulongcs/Awesome-Deep-Learning-Papers-for-Search-Recommendation-Advertising/tree/master/4_Post-ranking。
[1] 1998 (SIGIR) [MRR] The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries[2] 2005 (WWW) Improving Recommendation Lists Through Topic Diversification[3] 2009 (Microsoft) (WSDM) Diversifying Search Results[4] 2010 (WWW) Exploiting Query Reformulations for Web Search Result Diversification[5] 2016 (Amazon) (RecSys) Adaptive, Personalized Diversity for Visual Discovery[6] 2018 (Google) (CIKM) [DPP] Practical Diversified Recommendations on YouTube with Determinantal Point Processes[7] 2018 (Hulu) (NIPS) [DPP] Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity[8] 2020 (Huawei) (Arxiv) Personalized Re-ranking for Improving Diversity in Live Recommender Systems[9] 2021 (Microsoft) Diversity on the Go! Streaming Determinantal Point Processes under a Maximum Induced Cardinality Objective[10] 2018 (Alibaba) (IJCAI) [miRNN] Globally Optimized Mutual Influence Aware Ranking in E-Commerce Search[11] 2018 (SIGIR) [DLCM] Learning a Deep Listwise Context Model for Ranking Refinement[12] 2019 (Alibaba) (RecSys) [PRM] Personalized Re-ranking for Recommendation[13] 2020 (Alibaba) (CIKM) [EdgeRec] EdgeRec - Recommender System on Edge in Mobile Taobao[14] 2021 (Alibaba) (Arxiv) [PRS] Revisit Recommender System in the Permutation Prospective[15] 2020 (Airbnb) (KDD) Managing Diversity in Airbnb Search[16] 2019(Alibaba) (WWW) [Value-based RL] Value-aware Recommendation based on Reinforcement Profit[17] 2019 (Google) (IJCAI) [SlateQ] SLATEQ - A Tractable Decomposition for Reinforcement Learning with Recommendation Sets[18] 2019 (Google) (Arxiv) Reinforcement Learning for Slate-based Recommender Systems - A Tractable Decomposition and Practical Methodology[19] 2019 (Google) (Arxiv) Seq2Slate - Re-ranking and Slate Optimization with RNNs[20] 2019 (Alibaba) (KDD) [GAttN] Exact-K Recommendation via Maximal Clique Optimization[21] 2019 (Google) (WSDM) [Top-K Off-Policy] Top-K Off-Policy Correction for a REINFORCE Recommender System[22] 2021 (Google) (WSDM) User Response Models to Improve a REINFORCE Recommender System[23] 2008 (SIGIR) [α-NDCG] Novelty and Diversity in Information Retrieval Evaluation[24] https://github.com/guyulongcs/Awesome-Deep-Learning-Papers-for-Search-Recommendation-Advertising
