老徐书房

推荐算法实战-9-重排

 
  • 2024年 04月07日

本文是推荐算法实战系列第9篇文章。

前面文章包括：

  1. 推荐系统简介
  2. 特征工程
  3. embedding
  4. 精排
  5. 召回（1）：传统召回以及召回中的loss设计
  6. 召回（2）：word2vec召回、FM召回和双塔召回
  7. 召回（3）：图卷积
  8. 粗排

本文介绍推荐系统另一朵红花，重排。

前面介绍的召回、精排和粗排只关心单个物料与用户的匹配度，属于point-wise的预估模型。没有考虑同一个打分结果的上下文，相似的物料会被模型打上相似的分数，排序时在相邻的位置，造成推荐结果同质化，引起用户审美疲劳。

重排在精排之后，将精排的打分结果序列作为一个整体，属于list-wise预估模型，考虑以什么顺序呈现给用户才能带来最好的用户体验。

重排的重点在于精排输出结果的相关性与多样性之间的平衡。

本文介绍三类重排方法：基于规则的、基于上下文感知（Context-aware Learning-to-Rank，LTR）、基于行列式点过程（DPP）。

1、基于启发式规则的重排

精排的结果是按照精排分降序排列的一个序列。重排在精排结果上，引入打散规则，主要考虑：

  • 避免相似的物料扎堆，最大化整个或者局部序列的多样性。
  • 对原始精排序列的改动尽可能小，因为精排分已经代表用户对物料的喜好度。

一种打散规则是“滑窗打散”。在一个长度为K的滑动窗口内，相似物料最多出现n次。

  • 初始时，所有物料按照精排打分降序排列。
  • 从头开始依次滑动窗口。
  • 在每个窗口内，判断相似物品（例如，属于同一个类目）出现次数，如果违反打散目标，则将本窗口内的相似物品与下一个窗口内的其它物品对调。
  • 在对调过程中，尽量减少对原精排序列的改动（备注，此处只是示意，更严谨的方法暂略）。
  • 直到该窗口满足打散规则后，继续滑动到下一个窗口，依次处理。
  • 最后的窗口如果没有其它物料可供对调，不做处理。

另一种打散规则是“分桶打散”。

在电商场景下，精排模型通常以最大化成交额为优化目标，排在前面的物料价格偏贵。我们希望展示给用户的排序结果，在价格带上呈现多样性。可以按照商品价格构建高、中、低三个桶。将精排结果按照价格区间插入对应的桶。每个桶内还是按照精排分降序排列。最后，按照高-中-低顺序从三个桶中抽取头部物料排列成最终结果。

以上两种都是启发式的，还有一类算法，将“相关性”与“多样性”量化，并基于贪心算法实现。其中最著名的是MMR算法（Maximal Marginal Relevance）。

\[Next = argmax_{t \in R-S} \Big[ \lambda \times Reward(u,t) - (1 - \lambda) \times Sim(S,t)) \Big]\]
  • 核心思想是：每次从精排集合中挑选一个加入重排集合，条件为：精排分越高越好，以及与重排集合重复度、相似性越低越好。
  • R：全体精排结果。
  • S：当前重排结果。
  • R-S：R中剩余的精排集合。
  • Reward(u,t)：候选物品选入重排集合的reward，通常是精排得分，越高越好。
  • Sim(S,t)：候选物品与当前重排集合S的重复度和相似性得分，衡量把它引入重排集合后对多样性的影响。越低越好。
  • $\lambda$: 超参数，调和“相关性”与“多样性”。
  • 括号里面的式子表示将候选物料t引入S后带来的边际收益。（Marginal Relevance）。

实现Sim有多种方法。其一，基于物料集合的的画像分布的熵来衡量集合的多样性。

\[Sim(S,t) = -Entropy(T_s \cup T_t)\]
  • $Ts = {Tag_i : n_i}, i \in [1, N_t]$是当前重排集合S的标签分布。
  • $T_t$是当前候选物料t的标签分布。
  • 用熵来表示标签分布的多样性。
  • t加入S后，S的熵增加越多，说明t与s的相似度越低。

如果嫌画像的扩展性不好，还可以用物料向量来定义相似性。

\[Sim(S,t) = max_{s \in S} E_t \cdot E_s\]
  • $E_t$：候选物料的embedding。
  • $E_s$: 已经加入重排结果集的物料s的embedding。
  • embedding可以来自双塔粗排、召回，也可以由内容团队提供。
  • S中有多个物料，严格来讲，应该考虑t与S中所有物料两两相似性之和，或者S引入t之后的集合的相似性（可以表达为两两相似性之和）。但是，这样计算比较麻烦，为了简化问题，直接选取S中与t相似性最大的物品作为代表，表示集合S与t的相似性，故有取max操作。

Airbnb在MMR的基础上，改进后提出了MLR（Mean Listing Relevance)。其核心思想是在MMR的基础上考虑位置bias。后插入物料曝光位置靠后，对相关性和多样性的影响也削弱了。

MLR将候选物料t插入重排结果集第p个位置时的边际收益如下：

\[MLR(u,S,t,p) = \lambda \times c(p) \times Reward(u,t) - (1 - \lambda) \times d(p) \times Sim(S,t)\]
  • c(p)：位置p上的相关性的折扣。用位置p上的后验CTR表示。p越大，位置越靠后，c(p)越小，相关性收益越小。
  • d(p)：位置p上的多样性的折扣。用d(p)=1/p来表示。p越大，位置越靠后，d(p)越小，对多样性的损失越小。
  • （备注：dp为何不用后验ctr校正？）

以上种种基于启发式规则的重排算法，都只考虑了两个物体的相似性，而没有考虑集合整体的多样性。 集合的多样性优化问题，可以理解为求集合中所有物料向量围成的体积最大，在数学上有专门的算法可以解决，比如DPP算法。

2、DPP重排

DPP算法数学气息浓厚，暂时略过。

3、LTR重排

还有一类重排方法，训练一个专门的重排模型。重排模型与之前的召回、粗排、精排等有一些本质上的不同：

  • 之前的模型都是单点估计point-wise，候选集中的物料彼此独立，互不影响。
  • 重排是listwise模型，评估的是一个完整的排序结果的好坏，候选集中的物料不再独立，而是相互影响。这类算法称为Context-aware Learning-to-Rank。

重排模型的优化目标为：

\[min \frac{1}{|B|} \sum_{(S,Y) \in B} \sum_{i \in [ 1, |S|]} Loss \Big( Y_i, F_{rr}(S_i, Context(S,i)) \Big)\]
  • (S,Y)是batch中的一条样本。S是某次曝光的物料序列。Y是用户对S的反馈序列。（备注，一个样本是一个曝光序列，包含多个曝光物品吗？样本如何组织？）
  • $S_i$：曝光序列中第i个位置的物料。$Y_i$是用户对Si的反馈。
  • Frr：重排模型。预测Si被用户交互的概率。它不仅与Si有关还与上下文有关。（ 备注，如何在特征中表示上下文？）
  • Loss：可以是普通的交叉熵。

从优化公式，可以看出重排模型的两个关键点：

  • 第一，如何表达序列中的Si。常规的比如物料Id，分类、标签、画像等必不可少，还有其它两类重要信息：
    • 一类是用户对Si的个性化信息，比如精排模型的打分。
    • 另一类是Si在候选集中的排名、位置等信息，能够刻画Si与它的邻居之间的相对关系的特征。
  • 第二，Frr模型的选择。凡是能用于序列建模的模型，都可以用上。

上述训练过程依赖顺序已知的序列S，在训练阶段是存在的。但是预测阶段，这个顺序是我们的预测目标，是无法作为模型输入的。

一个粗暴的方法是，列出精排集合所有可能的排列组合，将每一个候选排序作为输入，送给重排模型打分，然后从中挑选收益最大的那个序列，作为重排的预估排序：

\[argmax_{S \in Permute(X)} \sum_{i \in [1, |S|]} Utility(S_i, F_{rr}\Big( S_i, Context(S, i) \Big))\]
  • X: 精排的输出物料集合。
  • Permute（X）：X通过排列组合生成的所有候选序列。
  • Utility: 收益函数。以电商场景为例，它既与Si被购买的概率（Frr的结果）有关，也与Si自身的属性有关（e.g 价格）。
  • 先遍历单个序列的所元素得到这个序列的总收益。再遍历所有候选序列得到总收益最大的序列作为输出。

这种穷举法，能帮助我们理解重排线上预测的流程以及它与精排的不同，但是它无法满足线上的时延要求，因此无法部署上线。

实践中，需要降低序列搜索的时间复杂度，常用方法是greedy search 和beam search。

下面介绍两个案例。

3.1、阿里的miRNN模型

miRNN是淘宝2018年提出的重排模型，其核心思想包括：

  • 训练时，用RNN建模曝光序列中当前物料的上下文，
  • 预测试，用Beam search搜索候选序列。

用RNN建模某物料在上下文影响下的购买概率：

\[\begin{aligned} P(S_i | S_1, ..., S_{i-1}) &= sigmoid( \pmb {W_h h_i}) \\ h_i &= RNN(h_{i-1}, Fe(S_i)) \end{aligned}\]
  • $h_{i-1}$: $[S_1, S_2,…S_{i-1}]$被RNN压缩后的状态向量，作为Si的上下文。注意，在RNN方案中，Si的上下文只包含它前面的物料。
  • ${h_i}$: i之前的信息和当前物料信息Fe（Si)，通过RNN压缩成状态向量。Fe（Si）表示当前物料的特征提取函数。
  • 再将hi映射成购买概率。Wh是待学习的权重。

重排的特征工程关键的一项是“序列内排名类指标”。例如

\[price_{global} = \frac{price - price_{min}}{price_{max} - price_{min}}\]
  • price: 当前物料的价格。
  • $price_{global}$:喂入重排模型的价格特征。
  • $price_{max}, price_{min}$：当前序列S的最高价格、最低价格。注意与特征工程中的min-max归一化的差异。

线上预测时，用Beam search取代Greedy search。

  • 二者都是在已知当前的“最优子序列”的基础上，把第i个元素追加到序列尾部时新的序列收益最大。
  • Greedy search，每一步扩展序列时，只在当前候选序列中挑选收益最大的那一个。只能保证局部最优，无法保证全局最优。一个全局最优的序列，有可能因为前面几步得到的子序列收益交叉而被提前放弃了。
  • Beam search，是每一步扩展序列时，在候选序列中挑选收益最大的前K个子序列。扩展了搜索空间，提高了容错性，降低好的序列被提前放弃的概率。

（备注，这种预测方式，和LLM语言模型生成单词时非常类似，每次吐一个item并计算一次预估分和收益分。前面的子序列会影响后面item的预估分。直到得到一个完整的序列。）

3.2、阿里的PRM模型

PRM(Personalized Re-ranking Model)是阿里2019年提出的重排模型。有三个关键步骤： 第一，如何表达物料Si。

\[E_{S_i} = concat(X_i, PV_i) + PE_i\]
  • $E_{S_i}$ : 物料Si喂入模型的向量。
  • $X_i$:物料自身属性组成的向量。例如，itemid的embedding。
  • $PV_i$: 用户对物料i的个性化信息。一种方法是，像精排一样，把用户画像、行为序列等特征，扔进重排模型，让重排模型学习用户对物料的个性化信息。但是这样做，重排模型太复杂，时间开销比较大。PRM的做法是取精排模型倒数第二层sigmoid之前的输出向量作为特征PV，这样将全部用户信息、物料信息、还有二者之间的交叉都压缩进去了。架构上改动也比较小，精排发往重排的请求中包含它筛选出的物料id，和这些物料的PV向量。
    • （备注：为何用PVi，不直接用精排输出的精排分数？）
  • $PE_i$:物料i在精排排序中的排名的embedding。体现物料i与其它物料的相对位置关系。

第二，如何建模候选集中物料的相互关系（上下文）。 PRM用transformer取代RNN，有三个有点：

  • Transformer中，上下文既包括前面的物料，也包括后面的物料。
  • 没有RNN随着序列变长，建模能力下降的缺点。RNN不擅长建模长距离序列依赖。
  • RNN只能由前向后顺序计算，transformer可以在序列任意位置并发计算。

其缺点是，计算复杂，耗时高。时间开销与序列长度的平方成正比。

第三，如何生成结果序列 如果在Beam search和greedy search中反复调用transformer，时间开销太大，无法满足线上实时性要求。

PRM做了简化：先计算出每个位置上被用户选中交互的概率scores，再按照scores降序排序输出：

\[Scores = softmax(F^{N_x}W_F + b_F)\]
  • $F^{N_x}$: Transformer最后一层的输出，Nx是transformer的Encoder层数。$F^{(N_x)}$是一个形状为（B，L，d）的矩阵。B是batch size。L是输入序列（精排结果）的长度。d是encoder的输出维度。
  • $W_F \in R^{d \times 1}, b_F \in R^L$: 将$F^{N_x}$映射成[B,L]的logits。
  • 最后，将logits经过softmax映射成各个位置上的交互概率。
  • (备注：这种方式，与LLM序列生成式模型不一样，它一次就完整的输出了整个序列中每个位置的得分，不用一个item一个item的预估。问题：它的输入是什么？如何把输出的位置和itemid对应上？)

PRM的这种排序方法，认为重排只不过是在精排排序上的一次微调，“一步到位”，省去了搜索最优序列的麻烦。

本文总访问量次

搜索