🔄推荐广告算法链路-Rerank演进
type
status
date
slug
summary
tags
category
icon
password
Status
一：推荐广告算法链路
如图，这里我们不做推荐系统还是计算广告的具体区分，我们按用户推荐或者广告触发，在推送或者播放请求的场景里，以item候选缩减的视角来观测整个算法链路的构建。
起点是数十万，甚至是百万级的候选item，例如商品SKU，而终点是若干最终推荐出来的Item，例如推荐系统中通常会有若干陈列的item，而广告播放场景中可能最终只会取Top1的最终广告为用户进行广告播放。
Item的数目从数十万到十的量级，中间经历了一些硬性的条件过滤，以直接刨除不符合条件的候选，然后进入到候选召回环节，将候选缩减到万的级别，在进入粗排阶段，将候选量级缩减到千的级别，最终过精排输出了数百的序，经过ReRank进行序的重新排列，最终根据应用场景做截断，截断成TopN还是Top1。
而整个过程，以信息流为例，包含在了从用户滑屏触发到Item推荐或者广告播放出来的底层逻辑中，用时可能仅仅是100个毫秒。
所以，为什么看着整个链路逻辑图如此繁复，最核心的诉求在于，如何在短短的100ms内在数十万的候选中，快速筛选出合适的Item推送出去，以达到业务目标最大化，例如广告的流量效率最大化，推荐的转化最大化等目标的实现。
基于候选的量级缩减以及时效的要求，这就对应于不同阶段的定义，模型实现逻辑，工程逻辑有不同的要求，各司其职，最终才能使得整体业务收益的增长或者说最大化。
抛开基于条件硬性过滤的Filter逻辑不说，我们从真正能缩减量级的召回说起。关于推荐的召回，对于熟悉经典的同学来说，第一反应应该就是所谓的多路召回。
热点召回基本上就是基于历史统计的信息做非个性化的热点Top召回；纯粹照顾新item的冷启动召回；i2i的话基本是直接计算item与item的相关度，但是实现手法上又有不同的选择，比如直接计算item之间的表面语义相关，又或者基于itemCF协同的逻辑融入user与item的交互行为计算i2i的相关性，甚至同类别，同个聚类下的item集合都可以作为召回逻辑；u2i的话，传统逻辑就是基于userCF的协同，拿到user与item的关系；除此之外，还有给item打标签的，然后同时给user也打标签，通过检索逻辑做标签匹配的召回等等。
如上这种多路召回的逻辑，典型特色就是种类繁多，逻辑各异，也不知道是谁想出来的，理解起来太费劲了。这些召回逻辑的有一个共同特点就是快，能够在短短10ms左右时间把符合召回逻辑的候选给筛选出来，那么要么是直接内存查找数据，要么是通过倒排索引提前构建好索引，然后进行检索召回。
而如上的逻辑不管是查表还是规则，大部分都依赖于离线的计算，哪怕是诸如上了一些聚类，协同过滤的模型，都是离线建模，离线预测，在线数据加载，然后内存检索的路子。
这是候选多、响应时长短导致的工程限制。
而为什么会出现这么多不同逻辑的召回，本质上离不开召回阶段的能力定义--为后续排序阶段提供更多潜在的候选，更多的可能性。所以多路召回中才有忽略了个性化的优质候选，与推荐标的物相关的item候选召回逻辑，以及有用户行为个性化的协同推荐逻辑，或者兴趣标签相关的召回逻辑等。
从不同维度为排序阶段提供输入候选，本义上还是为后续排序阶段提供更多潜在的有用Item候选，如何定义有用，则涉及到精排的建模目标，以最常见的pCTR为例，即预测当前user对于候选item的点击率如何，以广告为例，同样是pCTR预估（先不讨论更为复杂的转化等问题），只是最终排序是叠加了bid之后的eCPM。
除此之外，多路召回的另一层产品逻辑的意义在于，提供多种逻辑的召回，从而增加了候选item的多样性，从而提升了用户体验。
但为了满足多样性带来的多路逻辑召回，首先需要解决的是融合问题，因为下游粗排对于能够接受处理的候选item数量是有限的，以透传下游一千候选为例，众多的召回逻辑，其计算逻辑是不同，有基于静态统计，有基于简单的标签匹配，有基于简单的协同模型离线计算，所以很难放在一个维度上进行截断。
目前仍然采用传统多路召回的系统中大部分采用的是配比融合，即每一路按比例进行Top融合，最终取够既定的数量item透传给下游。
但这种逻辑有很大的硬伤。
其一，这种比例搭配很多时候只能靠拍脑袋来决定，无法量化衡量其合理性。
其二，抛开不一定叠加的重排不论，召回之后至少尚有粗排精排，而粗排精排的建模目标非常明确，就以常规的点击率场景为例，优化的就是单次user与item的pCTR最大化，简单点说就是哪个pCTR大就排在前头。会不会存在比如热点召回的item都被粗排干掉了？又或者基于i2i的召回大部分排序靠后？这是完全有可能的，所以最终很有可能哪怕你在比例逻辑中设置了较大的比例，但最终经过了粗排精排之后大概率被丢弃了，多路了个寂寞。
因此，近些年才有两个核心主流的方向在引导召回往向量召回方向发展，以及一直强调召回粗排与精排的整体目标一致性。
关于向量召回，可以参考向量召回的双塔模型结构图。
二：ReRank
回到所谓的“背叛”，直观上看到的是将精排的序重新打乱，但我们需要更深入理解为什么要去打乱。
本质上可以回到业务逻辑的建模目标这个问题上，包括以什么LTR（Learning to Rank）的方法去建模，以什么逻辑去构造样本，特别是正样本的界定。
对于召回阶段，以当前主流的向量召回为例，在构建主流的双塔模型的时候，我们通常是按pointwise的逻辑去构建样本的。
以推荐为例，大部分时候应该是将user点击的数据作为正样本，本质上是区分点击与未点击。而广告也差不多，可能更多时候会进一步考量点击之后的深度转化，例如是否下载，进一步激活APP，产生购买付费等等。
对于排序阶段来说，更是对于单个USER在单次请求场景中是否会点击/转化等行为的预测，所以，不管是主流召回还是排序，其模型目标都是一样的。
两者更多时候是对于负样本的构造逻辑差异，这就是知乎“石塔西”所提到的“召回阶段的负样本为王”，召回偏重于对于全局数据的感知，所以需要让模型“看”到一些没有见过的负样本（大盘随机，或者构造），而排序则是在曝光的基础上做是否点击/转化的预测，其场景是有微小差异的。
但这种差异不影响他们的大目标保持一致。
至于说精排前面的粗排，本质上就是工程效率层面的妥协，可以认为是轻量级、简化版的精排，简化在于模型复杂度降低、超参的减少、特征范围的缩减，目的在于进一步通过轻量的方式缩小候选，确保时效。
当然目前还有一种逐步趋于主流的粗排做法，那就是真正的LTR，即直接让粗排学习精排的序，确保的是序尽可能的保持一致，而不是过去那种计算pCTR/pCVR，然后再根据值来排序。粗排LTR的模式更是一种完全向精排拟合目标靠拢的模式了。
我们再来看重排序ReRank。
首先需要明确的一点，那就是Rerank的目标不再是按照单次业务价值最大化进行排序，所谓单次业务价值最大化，如推荐中的点击率，广告中的eCPM（CPAbid*pCTR*pCVR）等。其考虑更多的是多次用户行为的连带效果，甚至侧重于用户的体验提升。
比如，重排所最常见的做法，那就是提升序的组合多样性，从而避免用户多次接受到的推送都是重叠的，从而引起的用户反感，加大了用户的流失率。
这就是排序与重排的矛盾之处了，从目标构建的角度上，也就是从本质的方向上是相异的，排序不会考虑多次用户触达之后的形成的相互影响作用，只根据单次互斥的user*item的pCTR（或者是pCVR，又或者是叠加了bid因素之后的综合指标）来进行排序，而忽略了形成序之后的相互影响，即排序更关注单次的短期收益，而重排试图站在全局的视野，或者中长期的收益角度去构建建模目标。
典型如一些短视频的推荐系统，在不断的滑动视频的过程中，这种前后序的组合是严重相互影响的，特别是前文对于后文的影响。除了类似这种滑动逻辑的短视频、信息流场景，购物场景也同样，橱窗商品的组合陈列应该看成是一个整体，而非单纯若干个独立个体按某个指标的排序，橱窗商品的陈列对于整体用户的体验，甚至是提升购买意愿都是有作用的。
但对于广告场景来说，这种上下文的相互影响会小很多，因为广告本身会有播放推送的频度控制，且有一些相同广告主的播放次数限制等策略，所以相互影响会弱化很多，反而是嵌入广告的载体上下文对其有影响，比如信息流中嵌入的广告。广告的重排序有些特殊，这个我们后面再拆解，我们继续回到重排的目标构建的角度上。
重排的当前处理逻辑，很多都是以提升Item的多样性的方式来提升用户的体验，这是一种非常通用的重排做法逻辑。但是，我们继续思考一个点，任何商业场景本质上都不是做慈善，增加了偌大的成本（算法成本/机器成本），绝不是单纯为了提升用户的体验，博取用户的好感，从而损伤商业转化。
因此，最终的目的依然是商业目标，只是从单次商业转化的目标转换成了中长期的，或者是整体评估的商业目标。
例如短视频中的视频推荐，排序侧重于单个视频item的点击率（或单个视频的播放时长）提升，从而形成初始的序，缩减候选，但重排阶段则可以以滑动窗口作为视角，如何组合若干个视频，从而使得用户的观看整体时长最长，或者用户滑动的视频个数最多。
再以电商购物为例，在排序阶段通常按照商品点击率，又或者是购买转化率为目标进行建模，最终按点击率或者转化率进行排序，缩减候选。但是，在重排阶段，完全可以以推荐商品组合的角度，提升用户整体的购买转化，甚至是GMV，或者是在整体点击转化率不降低的前提下，提升用户的整体组合购买导致的客单提升。
不管是短视频场景还是电商场景，都从单纯的item组合多样性的基本角度，过渡到业务场景的终极目标，比如短视频追求的用户整体时长，电商场景所追求的购买GMV。
因此，在重排阶段提升多样性只是途径而已，并且还是比较浅层的方式方法，而终极的目标一定是全局，甚至是从生态角度考虑，最终通过序的相互影响，序的陈列组合来达到整体全局业务目标的提升。
这就是排序阶段侧重的是单个item的价值最大化，而重排的意义则在于全局目标的组合优化，甚至是生态格局的重塑，通过序的重新排列之后，让整个业务生态更加的合理，更关注中长期的稳定收益。
所以，重排与召回排序本就不是一路“人”，他“格局”更大，站的更高、看的更远。
那为什么在早些年的时候，更少人会关注到重排序的定位呢？从而导致了如上个章节所言，与排序阶段相比，重排变成了一个可有可无的算法链路阶段。这从十几年积攒下来的相关论文也可以看出来，两者的研究积累不在一个数量级上，重排的弱势可见一斑。
这是由外部环境所决定的，任何技术的推动的快慢都是由其所能产生的收益所决定的，而收益的定义取决于当前业务所最迫切的业务目标。
在门户网站时代，哪有什么推荐系统，但流量增长不一样吭呲吭呲的往上涨，当用户逐步对于媒体有体验诉求时，本质上也是因为流量增速放缓了，所以导致了需要通过个性化的服务来提升用户体验，提高用户的粘度。其中，尤其是互联网广告的发展，高度追求ROI的广告模式，使得这个业务场景在排序的道路上越走越远。
但是，2018年之后，随着移动智能手机的基本全面普及和覆盖，流量红利基本见顶，媒体内容高度同质化，进入到相杀阶段，连投广告投竞品都成了主流，这意味着流量已经进入了高度存量维护的阶段了，也就那个时候行业高喊所谓的“私域流量”，本质上也是做存量。
作为广告从业者，一个非常明显的例子就是，从2021年到2022年，广告主一个明显的变化趋势就是，深度转化中越来越追求留存，对于浅度转化的投放模式越来越不满，或者缩减投放预算，将预算放到深度转化中，且反向逼迫DSP平台加大深度转化的成本达标率。
这个真实的例子非常显式的说明，流量主急了（广告主本质上也是流量主，广告的本质是导流嘛），更多关注于用户的体验，稳住流量才有长期的收益。
从上面逻辑中，我们可以看到存量流量的维护重要程度比我们想象中还要严峻，而对于系统生态的格局的重塑必然要从单次收益最大化，走向长久收益最大化。
这是一个大趋势。
但难度又恰巧在这里，如何在单次请求中考虑中长期的收益最大化，这是一种责任，又是一种挑战。
并且这种挑战的难度在于不是单纯的考虑多样性，以及通过多样性来提升用户体验，而在于如何量化多样性对于体验的提升，甚至在于体验提升之后如何满足于中长期的持续收益。
我们来看看，ReRank是怎么样关注业务的中长期收益的，以及从技术上如何实现从体验多样性到生态终极目标的底层演进。
三：从多样性到生态终极目标的演进
对于重排早期的研究，不管是产品经理还是算法从业者，更多关注的是如何通过重排对于序的resort之后，达到优化用户体验的目的，而优化用户体验进一步拆解到序的调整层面，即如何避免连续推出的item高度一致，从而让用户产生厌倦感。
总之，业务的优化目标很明确了，输出序的多样性。那么，拆解到算法层面的建模目标是什么，损失函数如何定义，效果如何评估？
先聊评估，没有明确的评估方式来界定数据的好坏就不用谈如何建模了。对于推荐，早期比较常用的评估方式是DCG或者进化版的NDCG，其公式如下。
DCG（Discounted cumulative gain）从命名翻译上，应该拆分为Discounted和 cumulative gain，后者统计的是累积增益，说直白点就是对于输出列表累积item评估的好坏集合，所以reli表达的就是对应i的相关度如何。当加了Discounted之后，需要考虑的是随着位置变化不同，理论上增益带来的影响也不同，说的更直白点就是排在前头的理论上更重要，权重更大（反过来如果预估错误，损耗也比较大），所以从实现逻辑上直接做了一个1/log2(i+1)做位置衰减。
而NDCG需要解决的问题是量化归一的问题，即序的长短不一会导致通过西格玛累和的方式不公平（显然更长的，DCG更大），最理论最大值的归一，分母中的IDCGp就是items集合中所有候选相关性排序，然后对应位置p的最大DCG。
后续又有其他类似MRR（倒数排序法）、MAP（平均精度均值法）等等，大体上没有很大的差别，都是对于输出序的item进行打分，然后再结合输出的位置进行综合加权，最终计算一个评估分值出来，来对比两个序的好坏。顺带提一下，搜索的结果的评估也非常类似，综合评估的是整个序，而不是单个item。
而对于多样性的评估，还不能直接抄NDCG的作业，毕竟NDCG中对于单个item的评估是不考虑上下文相互影响的，所以有了改进版的α-NDCG（2008年在SIGIR发表的《Novelty and Diversity in Information Retrieval Evaluation》）。
从论文中可以看到，基本还是以DCG为基本逻辑，核心改动点在于对于增益的定义。增加了两个调整，一个是每叠加一个item，会计算当前第k个item与前面k-1个item的信息增益gain，越低惩罚越大，从而控制多样性。其次，本身序的位置也对整体评分产生影响，位置越靠后权重越小。
重点的改进在于上文对于下文的影响，改进对于当前item的评分加权或者惩罚，而惩罚项则是多样性带来的信息增益，理论上增益越多惩罚越小，增益越小，惩罚越高，意味着越相似。通过这种方式让序不但要考虑推荐的合理性，还得考虑上下文的相互影响。
这是评估方式，进一步看算法内部如何实现这种多样性的差异的，我们以古老的MMR开始。
MMR(Maximal Marginal Relevance)算法又叫最大边界相关算法，此算法在设计之初是用来计算Query文本与被搜索文档之间的相似度，然后对文档进行rank排序的算法（1998 发表在SIGIR的《The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries》）。
其中 Q 是 Query文本，C 是被搜索文档集合，R是一个已经求得的以相关度为基础的初始集合,Arg max[*]指的是搜索返回的K个的句子的索引。中括号中，左边部分代表的是文档Q中某个句子d与整篇文档的相似程度，而右边代表文档中某个句子di与已经抽取的摘要句子dj的相似程度。整个公式所代表的含义是，在不断抽取摘要的过程中，希望尽可能的抽取能够代表通篇文档含义的句子，但是抽取的句子之间的信息增益尽量最大，意味着摘要包含的信息越丰富。
这就是既要又要的逻辑了，跟我们的重排多样性一样的尿性。通过重排提升用户多样性体验，所以要确保序的item排列让item之间保持多样性，拉开差异，但是又要同时保持序中的每个item对于转化是最佳的，或者说较好的。
在整体列表重排的过程中，评估细节参考了MMR，但是上层策略采用的是贪心算法，来生成TopK的结果列表，对于Sim计算的具体逻辑可以替换，其中具体偏向于相关性还是多样性，通过λ来调整，往大了调则倾向于相关度，往小了调则加大了多样性的权重，最终取决于业务场景的定位。
看着像个数学游戏了，但λ调大调小，真的对于我们最终的体验和终极目标有效果吗？我们稍后再进行分析。
再来看一个同样是追求多样性的早期论文，与MMR不同，DPP（Determinantal Point Processes，行列式点过程）虽然数学逻辑也算比较早了，但是应用于推荐检索系统的排序调整中算比较新了（MMR是1998年的古董），并且正儿八经的用到了谷歌、Hulu、华为等推荐的多样性重排结果调整的场景里，算是有大厂背书的经典方法了（例如，2018年Hulu在NIPS发表的《Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity》）。
与MMR解决问题的过程不同，但其要解决的目标基本是一致的，即要保持item组合分布的高质量（转化），又要保证其多样性。
聊DPP的数学推导逻辑比较复杂，本身也并非笔者所擅长的，所以我们尽量用简短的逻辑来理解这个过程，本质上DPP是通过行列式点过程的方式来实现效用与多样性的平衡，与MMR的差异在于，DPP通过后验概率来求解最大组合子集矩阵，在效率上和扩展性上会比MMR高很多，至于相关性（效用）与多样性的平衡，同样支持参数的调节来进行两端倾向性的调整。
对比MMR与DPP，如果抛开计算逻辑的具体过程与理论细节，本质上定义问题以及需要解决的问题并没有质的差别，差异在于方式方法，以及效率扩展性、合理量化性等维度。
基于MMR与DPP经典算法的开头，沿着同时优化多样性与效能（转化）的逻辑，我们看一下airbnb的重排序进化的逻辑，信息来自于AirBnb2020年发表在KDD的《Managing Diversity in Airbnb Search》，可以一窥Airbnb是如何考虑重排的。
早期的airbnb的重排在保证相关性（论文用的是Relevance，但笔者认为转化率之类的可能更能代表这个维度，但说airbnb就按airbnb的定义来）与多样性diversity采用的依然是MMR那一套，同时通过显式的公式组合来平衡相关性与多样性。
其做的微操优化有三个笔者觉得是可以借鉴的（不一定说是套在自身业务中，而是说可以结合自身业务是否需要深入改造）。
其一是根据业务对于多样性进行定义，airbnb非常明确表明了关注位置、价格、大小、房间类型等等，这非常符合显式优化的逻辑，关注什么指标就优化什么维度的指标。
其二是通过关注的多样性属性组成item的listing，并且通过向量的方式来计算多样性与相关性，这种表达方式在那个时候来说是一个创新（放在现在‘万物皆可embedding’的年代，可能就有点不够看了），并且在实现的时候需要考虑的是不同维度其向量表征占据向量位数的问题，比如房屋类型理论上占据一位即可，而位置如果是经纬度可能需要2位，价格是一个连续值，是不是需要分箱操作，分箱大小决定其占位，而不同的占位长度在计算多样性与相关性的是否是否会有影响，如何显式地操控不同维度地多样性体现等等，这些都是细节。
其三是，在计算Relevance时，用max替换掉了原论文的mean表征组合的表征方法。这里说不上好与不好，以max取值为例，通常推荐跳转的场景，如果用户点击了推荐item，电商与airbnb这种橱窗陈列的产品形态，一旦点击了就会跳转，所以采用max的方式来表征这个组合的Relevance程度，笔者觉得是没有问题的。
但是，如果放到信息流短视频这种就不一定了，因为那个场景是不会跳转的，只会播放，并且很多时候Relevance追求的是播放时长或者点击率，那么此时就需要考虑整个组合在推送阶段用户比如点开的总次数、总时长、总点击率等等。因此，看着只是一个MMR，结合自身的业务场景，还是有值得推敲的地方的。
对于Airbnb来说，重排优化的下一站，是脱离了显式的经验平衡Relevance与Diversity的模式，而是采用机器学习自动学习的逻辑。我们不定义什么程度 λ的多样性对于我们业务就是好的，我们挑选出好的组合与不好的组合，定义不同的损失，灌入特征样本，然后让有监督的pairwise模型来学习，最终模型说什么是好的什么就是好的。
因此，回到了机器学习的主流逻辑中，那么除了业务定义List组合的好坏，那么对于技术层面，最重要的则是如何定义损失，损失定义好了，通过梯度求解自然就可以优化模型了。
如前文所说，Airbnb对于其自身所追求的结果多样性非常的明确，对于价格多样性与位置多样性异常的执着，对于整个模型定义了Lh=Lr+Ldl+Ldp，其中Lr是相关性的损失（文中没说啥啥，大概率是 cross entropy）,而Ldl与Ldp分别对应位置与价格。
说到这，熟悉排序的同学应该坐不住了，这丫的不是ESMM吗？本质上就是多目标融合，两个支路用不同的样本进行建模，然后网络顶部用不同的目标优化函数，然后终极目标用多目标的损失进行融合，简单点就直接相加，做的骚气点就是多个损失加个Gate门控，说白了就是加个权重超参，让样本+模型自动学门控的参数，至于倾向于效果损失还是多样性损失，本质上是取决于样本的定义与挑选了。
其实这就很“机器学习”了，也是我们作为从业者必须具备的素质，学会定义问题，需要知道整个建模流程中，哪些环节可以深度影响，哪些环节是机械调参、机械调优。这就是很多时候资深算法工程师会说，首先需要先学会定义问题，学会定义样本，挑选优化样本，挑选特征，定义损失，最后才是一些机械的超参。因为按照这个顺序调优，是效率最大化的路径。
回到Airbnb的论文，其中多样性的损失定义是个重点，Airbnb对于多样性的Listing进行分桶，并且分桶内进行与目标值的二值label判断（多样性高了还是低了），并且对于不同的bucket还做了融合加权，外层套了交叉熵cross entropy，所以给了个很骚气的surrogate cross entropy loss命名。确实为其他业务场景如何量化多样性损失提供了一个比较明确的思路。
至于论文后续的一些优化，这里就不做重点陈述了，包括融入了上下文特征，将精排的结果融合LSTM得到Query Context Embedding，再融入重排模型中做重排的。笔者没有重点看了，前面的内容重点看是因为涉及到了重排演进的主流思路。