本文是“系统学习推荐算法的第四期”,首发于我的博客
前文指路:精排:推荐系统如何给内容打分?从多目标预估到分数融合
经历了召回的大海捞针、粗排的极速过滤和精排的深度计算推荐,推荐系统似乎已经找出了你最喜欢的视频,按照常理,把前100个高分视频推给你不就行了?但如果这么做,灾难就发生了。由于你最近关注了几个美食博主,系统给你推的第一个视频是红烧肉,第二个是梅菜扣肉,第三个是东坡肉,你一下子看吐了,直接卸载了app。
人是有审美疲劳的,这是精排模型的致命盲区。这时候推荐系统最后一道关卡重排必须出场。他是负责排兵布阵的军师,重排的任务是从精排挑出的100个视频中挑选并排列出一个最佳的十个视频序列
他不关心单个视频的绝对分数,而是要回答一个系统性的问题,在用户看了前三个视频后,第四个位置放什么最合适?为了排好这个阵型,重排层有三个核心目标,优化用户体验、流量调控以及保证算法效率。
打散算法——优化用户体验,保证推荐列表的多样性
为此,工程师设计了打散的规则,不让相似的物料紧挨在一起。同时,打散也是一门妥协的艺术,他对原始序列的改动必须尽可能小,不能对精排辛苦算出的高分序列破坏太大。

分桶打散
第一种方法叫做分桶打散,把不同标签的视频扔进不同的桶里,然后轮流从每个桶里抓取一个视频。这种做法快如闪电,打散效果也立竿见影。但如果游戏桶里的视频远超其他桶,最后游戏视频依然会在末尾扎堆。更关键的是它彻底打乱了精排的顺序,容易导致点击率暴跌。
滑动窗口打散
为了保护精排的劳动成果,第二种方法诞生了:滑动窗口打散。比如工程师设定一个长度为三的扫描窗口,让它在视频序列上滑动。规则是在这个窗口内同类型的视频只能出现一次,如果有重复,就强行把它和后面的视频交换位置,这种方法只做局部微调,计算量极低,最大限度保留了精排给出的高分顺序。


MMR (Maximal Marginal Relevance)(最大边界相关性)
如果想更精确的控制多样性,就要引入第三种方法,最大边界相关性。
MMR 的标准数学公式如下:
$\text{MMR}=>\mathrm{*}>arg\,max{D{i}\in C\setminus S}\left[\lambda \cdot \text{Sim}{1}(D{i},Q)-(1-\lambda )\cdot \max {D{j}\in S}\text{Sim}{2}(D{i},D_{j})\right]$
前半段代表收益,新视频和用户兴趣越匹配,得分越高。后半段代表惩罚视频和刚才展示过的视频越像扣分越多
两者相减算出一个最终得分,只有取得最大平衡的视频才有资格排在下一个。
DPP(行列式点过程)
如果你觉得前三种方法还是不够全局,那么介绍第四种方法,真正的高端算法、DPP算法 行列式点过程
第一步要做的就是构建向量,它把每一个视频变成高维空间里的一个箭头,箭头长度代表精排给出的得分,得分越高箭头越长,箭头之间的夹角代表相似度,如果两个都是美食,夹角趋近于零度,如果是美食和美妆,夹角趋近于90度,垂直。

第二步算体积,从100根箭头中挑出十根,计算它们构成的矩阵的行列式。矩阵的行列式等价于这些箭头在高维空间中撑起的几何体的体积,让它们撑起的体积达到最大。要体积最大,首先每一根箭头都得足够长,也就是单个视频质量必须高。同时箭头和箭头之间必须尽可能的相互垂直岔开,也就是视频内容必须足够多样,不能重叠。
生产环境如何用贪心解决 DPP 的性能问题的?
假设推荐系统需要从100个后选视频中挑出最终展示给你的十个,那么一共会有多少种不同的组合?我们可以简单计算一下,想象前面有十个空位,每个空位都要放入一个不同视频。第一个位置可以从100个视频里任选一个,因此有100种可能。第二个只能从剩下的99个里选,于是有99种可能。第三个位置有98种可能,一直到第十个位置还剩下91个可选的视频。任意一组十个视频内部都可以重新排列出十的阶层,因此还需要把这些重复情况除掉,最终得到的组合数量为100的阶层,除以90的阶层乘十的阶层,算出来有高达17万亿种组合。让计算机去穷举必然严重超时。
那么大厂的工程师到底是怎么在线上跑通 DPP 的呢?答案是贪心算法。每一步只选取当前能让体积增量最大的那一个。第一步,找基石,抓住空间里长度最长的那根箭头,比如一个爆款美食视频。第二步,大面积寻找能和它组成最大平行四边形的第二根箭头。第三步称体积,前两个视频锁定了一个二维平面系统,接着寻找距离该平面垂直高度最高的第三根箭头,以此类推,每一步都挑选能带来最能撑起总体积的箭头,一直挑满十个
人工干预通道
除了优化用户体验,重排层还有一个满足真实的业务需求——重排是推荐系统中唯一的人工干预通道,在真正的商业巨头里,算法再精妙也得为产品运营服务。
比如世界杯期间,即使你平时并不是体育迷,系统也可能适当的提高赛事奇景、热门进球和实时讨论的曝光权重。这时候重排层就会强行介入,不管精排给视频打了几分,他都会动用最高权限给特定的视频推流,或者对某些视频质量不高的视频进行限流。
另外还可以在重排层 过滤掉用户不喜欢的作者、话题等(属于兜底措施)、加入广告 等