推荐系统学习（重排序）

重排序

重排序的必要性：

重排序定义：

对精排生成的Top-N个物品的序列进行重新排序，生成一个Top-K个物品的序列，作为推荐系统最后的结果，直接展现给用户。

必要性：

1. 建模物品间的互相影响：精排模型通常学习的是物品pointwise的得分，直接根据精排分数排序，无法考虑多个商品间的影响，而且同质化严重（相似的商品得分相似所以位置接近，但同时点击的概率很少），缺少发现性，用户体验较差。

2. 多样性：重排序提升Top-K商品的信息覆盖度、减少信息冗余。通过展示多种类型的商品，能够提升Top-K商品的覆盖度，同时避免无效曝光多个类似的物品。多样性能带来发现性：用户发现多种商品、新的兴趣，同时系统能了解更多用户。合适的多样性，通常对实现重排序目标有重要的作用。

重排目标：

1. 短期目标：提升结果的效率（点击、购买、GMV等）；提升结果的多样性、发现性和用户体验；降低负反馈（结果同质化严重、看/点/买了还推）。
2. 长期目标：提升用户流量深度、停留时长；提升用户复访、留存、长期用户价值。

存在问题：

1. 解空间大：重排序问题是从Top-N个商品的排列，生成Top-K个商品的排列，解空间（$A^N_K$）为指数级，生成最优解为NP-hard问题。
2. 每种Top-K个商品的排列的reward难以预测
3. 海量的状态空间（用户状态）和解空间，导致难以有效探索和学

推荐系统中的多样性

物品相似性的度量

物品属性标签方法

1. 物品属性标签：类目、品牌、关键词等
2. 根据一级类目、二级类目、品牌等标签计算相似度：对以上三个相似度求加权和得到物品相似度，权重由人为设定。

物品向量表征

在召回的双塔模型中，物品塔学习物品的向量计算相似度，但是由于长尾数据的问题，这种方法实际效果并不好。一般来说，更多地应用基于内容的向量表征。（CLIP）

提升多样性的方法

MMR 多样性算法

原理

Maximal Marginal Relevance（MMR）是最早来自于搜索排序的算法，使用相关性进行排序。要解决的问题设定如下：

1. 精排给 n 个候选物品打分，融合之后的分数为$reward_1,...,reward_n$;
2. 把第 i 和 j 个物品的相似度记作 $sim(i,j)$ ;
3. 根据以上两个值，从 n 个物品中选出 k 个作为曝光的结果，要求既要有高精排分数，也要有多样性。

不妨记选择的物品集合为 $S$ ，未选中的物品集合为 $R$ 。那么计算集合 $R$ 中每个物品 $i$ 的 Marginal Relevance 分数： $MRi=θ⋅reward_i−(1−θ)⋅max_{j∈S}\{sim(i,j)\}$ ，其中 $θ$ 是超参数，用于调整精排分数与多样性的权重占比。

基于该分数，此则 MMR 的基本思想为贪心：

1. 已选中的物品 $S$ 初始化为空集，未选中的物品 $R$ 初始化为全集 ${1,...,n}$ ；
2. 选择精排分数 $reward_i$ 最高的物品，然后从集合 $R$ 移到 $S$ ；
3. 重复上一步做 $k−1$ 轮循环：计算集合中 $R$ 中所有物品的分数 $\{MR_i\}_{i∈R}$ 、选出分数最高的物品，将其从 R 移到 S

其标准公式如下：

$M M R=\operatorname{Arg} \max _{D_{i} \in R \backslash S}\left[\lambda \operatorname{Sim}_{1}\left(D_{i}, Q\right)-(1-\lambda) \max _{D_{j} \in S} \operatorname{Sim}_{2}\left(D_{i}, D_{j}\right)\right]$

实际应用

在实际应用，该公式存在问题：

1. 已选中的物品越多（即集合 S 越大时），越难找出物品 $i∈R$ ，使得 $i$ 与 $S$ 中的物品都不相似；
2. 具体分析下原因：设 $sim$ 的取值范围为 $[0,1]$ 。当 S 很大时，多样性分数 $max_{j∈S}\{sim(i,j)\}$ 总是约等于 1 ，导致 MMR 算法失效。

针对这个问题提出的解决方案就是：设置一个滑动窗口 W （比如最近选择的10个物品），用 W 代替公式中的 S 。则得到使用滑动窗口的 MMR 公式：

$\operatorname{argmax}_{i \in R}\left\{\theta \cdot \operatorname{reward}_{i}-(1-\theta) \cdot \max _{j \in W}\{\operatorname{sim}(i, j)\}\right\}$

滑动窗口的应用存在直观解释：给用户曝光的物品应当具有多样性，也就是物品两两之间不相似；但没有必要让第30个物品与第1个物品不相似，用户看到第30个物品时大概率已经忘记了第1个物品是什么了。换言之，两个离得远的物品可以相似，并不会影响用户体验；但如果两个离得近物品就应当有较大差异，否则用户能感知到缺乏多样性。

业务规则约束下的应用

1. 每一轮先用规则排除掉 $R$ 中的部分物品，得到子集 $R^′$ ；

2. MMR 公式中的 $R$ 替换成子集 $R^′$：

DPP 多样性算法

原理

行列式点过程 (Determinantal Point Process, DPP) 是一种经典的机器学习方法，它的目标就是如何从一个集合中选出多样化的物品，与重排的目标契合。首先介绍一下其数学背景：

超平行体：

在二维和三维空间中，超平行体就是平行四边形和平行六面体。而在任意维上的定义为：

1. 在 d 维空间中，一组向量 $v_1,...,v_k∈R_d$ 可以确定一个 $k$ 维超平行体： $P(v_1,...,v_k)={α_1v_1+...+α_kv_k|0≤α_1,...,α_k≤1}$
2. 这里要求 $k≤d$ ，例如 $d=3$ 空间中有 $k=2$ 维平行四边形

对于超平行体如何求面积（二维）和体积（三维），实际上使用的是施密特（Schmidt）正交化的思想，将不正交的向量组转化为正交的向量组，方便计算面积与体积。如果都是单位向量时，什么条件下超平行体能取最大和最小的体积，显然存在如下结论：

1. 不妨设 $v_1$、$v_2$、$v_3$ 都是单位向量；
2. 当三个向量正交时，平行六面体为正方体，体积最大化 $vol(P)=1$ ；
3. 当三个向量线性相关时，体积最小化 $vol(P)=0$ 。

实际应用

在实际应用中，则：

1. 给定 $k$ 个物品，将它们表征为单位向量 $v_1,...,v_k∈R_d$ ；（$k≤d$）

2. 把它们作为矩阵 $V∈R^{d×k}$ 的列；

3. 设 $k≤d$ ，则行列式与体积满足： $det(V^TV)=vol(P(v_1,...,v_2))^2$ ；

4. 因此，可以用行列式 $det(V^TV)$ 衡量向量 $v_1,...,v_k$ 的多样性

个人在参考资料基础上，推导了k维超平行体体积与行列式的关系：

1. 不妨设列向量 $v_1, v_2, ..., v_k∈R_d$，其中 $d≥k$

2. 对向量组执行 Gram–Schmidt 正交化，得到一组两两正交向量$u_1, u_2,... ,u_k$，并记$r_{i i}=\left\|u_{i}\right\| \quad(i=1, \ldots, k)$，显然有：$\operatorname{vol}\left(P\left(v_{1}, \ldots, v_{k}\right)\right)=\prod_{i=1}^{k} r_{i i}$

3. 令 $Q=\left[\frac{u_{1}}{r_{11}} \cdots \frac{u_{k}}{r_{k k}}\right] \in \mathbb{R}^{d \times k}$。它满足 $Q^{\mathrm T}Q=I_k$。再令

   $R=\left[\begin{array}{cccc}r_{11} & * & \ldots & * \\0 & r_{22} & \ldots & * \\\vdots & \vdots & \ddots & \vdots \\0 & 0 & \ldots & r_{k k}\end{array}\right] \in \mathbb{R}^{k \times k},$

   那么 Gram–Schmidt 过程可写为

   $V=QR.$

4. 因为 $R$ 上三角，对角线上恰好是 $r_{11},\dots ,r_{kk}$，故$\operatorname{det}\left(R^{\mathrm{T}} R\right)=\left(\prod_{i=1}^{k} r_{i i}\right)^{2}=\operatorname{vol}\left(P\left(v_{1}, \ldots, v_{k}\right)\right)^{2}$

5. 由 $V=QR$ 及 $Q^{\mathrm T}Q=I_k$ 得：$V^{\mathrm{T}} V=R^{\mathrm{T}} Q^{\mathrm{T}} Q R=R^{\mathrm{T}} R$，从而有：

   $\operatorname{det}\left(V^{\mathrm{T}} V\right)=\operatorname{det}\left(R^{\mathrm{T}} R\right)=\operatorname{vol}\left(P\left(v_{1}, \ldots, v_{k}\right)\right)^{2}$

因此之前所介绍的多样性问题可以被如下描述：

1. 设有 n 个物品，向量表征为：$v_1,...,v_n∈R_d$ ，精排给这些物品打分为： $reward_1,...,reward_n$ ；

2. 现在从 n 个物品中选出 k 个物品，组成集合 S ，要求：

   • 价值大：分数之和 $∑_{j∈S}reward_j$ 越大越好；

   • 多样性好：$S$ 中 $k$ 个向量组成的超平行体 $P(S)$ 的体积越大越好。

3. 将集合 $S$ 中的 $k$ 个物品向量组成矩阵 $V_S∈R_{d×k}$ ，其中 $k≤d$ 。此时有 $det(V_S^TV_S)=vol(P(S))^2$ ，说明行列式等价于体积，故实际使用行列式衡量多样性。

同样，DPP也可以使用滑动窗口且可以被约束，具体执行原理与MMR一致。

相关工作：

Hulu LLC

Hulu 对该应用研究的主要贡献在于提出了**快速求解的方法。**一般来说，DPP 的求解思想如下,暴力算法的总时间复杂度为：$O(n^2d+nk^4)$：

1. 设 A 为 $n×n$ 的矩阵，它的 $(i,j)$ 元素为 $a_{ij}=v_i^Tv_j$ ；给定向量 $v_1,...,v_n∈R_d$ ，则需要 $O(n^2d)$ 时间计算 $A$ ；
2. 那么 $A_S=V_S^TV_S$ 是 A 的一个 $k×k$ 子矩阵，如果 $i,j∈S$ 时，则 $a_{ij}$ 是 $A_S$ 的一个元素；替换后的 DPP 应用在推荐系统的公式写作：$argmax_{S:|S|=k}\{θ⋅(∑j∈Srewardj)+(1−θ)⋅log(det(AS))\}$ 。
3. DPP 是个组合优化问题，从集合 ${1,...,n}$ 中选出一个大小为 $k$ 的子集 $S$ 。用 $S$ 表示已选中的物品，用 $R$ 表示未选中的物品，使用贪心算法求解： $argmax_{i∈R}\{θ⋅reward_i+(1−θ)⋅log(det(A_S∪\{i\}))\}$ ，寻找下一个物品 $i$ 且该物品价值尽量大、多样性尽量好。
4. 其中 $A_S∪\{i\}$ 可以这样理解：寻找下一个物品 $i$ ，给集合 $S$ 添加一个新物品，所以在原本 $A_S$ 的基础上添加了一行一列。同时，我们希望添加的物品 $i$ 使得行列式尽可能大，也就是说不能与集合 $S$ 中的物品相似，否则行列式接近于零。

Hulu 的论文设计了一种快速数值算法，使用Cholesky 分解花费 $O(nk^2)$ 时间计算所有行列式，仅仅需要 $O(n^2d+nk^2)$ 的时间从 n 个物品中选出 k 个物品。该算法思想如下：

1. Cholseky 分解 $A_S=LL^T$ ，其中 $L$ 是下三角矩阵；
2. Cholseky 分解得到可供计算 $A_S$ 的行列式：

​ 下三角矩阵 L 的行列式 $det(L)$ 等于 $L$ 对角线元素乘积；故 $A_S$ 的行列式为 $det(A_S)=det(L)^2=∏_il_{ii}^2$ ；

3. 每一轮循环，基于上一轮的 $A_S=LL^T$ ，可以快速求出所有 $A_S∪\{i\}$ 的 Cholseky 分解，因此可以快速算出所有 $A_S∪\{i\}$ 的行列式。

Context-aware List-wise Model

Context-aware List-wise Model，通过建模精排模型生成的Top-N个物品间的互相影响关系，来生成Top-K结果。包括miRNN, DLCM, PRM, EdgeRec, PRS, AirbnbDiversity等，成功应用到淘宝搜索、推荐、Airbnb搜索的重排序中。

miRNN and miRNN-attention

在电商情境下，重排序的一个体现是“如果一件物品周围有质量相似但价格高得多的物品，那么它被购买的概率就很高”。不同于搜索引擎等“点击”“浏览”为目的的情景，电商平台关注的是GMV（商品交易总额）。因此，阿里团队提出了优化GMV期望的重排方法。

优化目标

某一排序的整体GMV期望：

$E(\mathrm{GMV} \mid o)=\sum_{i=1}^{N} v(i) p(i \mid c(o, i))$

其中 $c(o, i)$ 表示排序$c(o, i) = (o1,..., o_{d_i}−1; o_{d_i}+1, ... ,o_N )$, $p(i|c(o, i))$ 表示商品在此排列下的购买概率，$v(i)$ 表示商品i的价格。因此，优化的目标就是找到排序$o^*$让GMV的期望最大：

$o^{*}=\arg \max _{o \in O} \sum_{i=1}^{N} v(i) p(i \mid c(o, i))$

因此，衍生出如下两个问题：

1. 如何估计$p(i|c(o, i))$
2. 如何高效地找到$o^*$

Global Feature Extension

这是一种简化方式。其提出背景为$O$的全排列为$N!$个，需要高效表达。这个的做法是考虑一个排列中其它商品对当前商品的影响，但是不考虑商品具体顺序带来的影响。

我们先看一个单独物品。一个物品$i$可以被表示为一个特征向量$f_l(i)$，可以被称作局部特征，通常情况下每个维度都是实数。在这个基础上，某一物品$i$受到组内其他物品的影响可以建模为一个全局特征向量$f_g(i)$。将二者拼接，即$f(i) = (f_l(i),f_g(i))$，可以用这个去预测$p$从而解决问题1：

$\begin{aligned}f_{\min } & =\min _{1 \leq j \leq N} f_{l}(j) \\f_{\max } & =\max _{1 \leq j \leq N} f_{l}(j) \\f_{g}(i) & =\frac{f_{l}(i)-f_{\min }}{f_{\max }-f_{\min }}\end{aligned}$

这里的公式描述的不太清楚，实际上对$f_{min}$和$f_{max}$并不是取固定的$j$，而是取得全局最大or最小。时间复杂度为$O(Nd)$，$d$为特征维度，即对每个维度都要找到最大和最小值。

可以看到，处理后的全局特征带了context信息，拼接全局特征和这个商品的局部特征过包含3个隐层的DNN，以交叉熵作为loss训练模型，就可以计算$p(i|c(o, i))$。为缓解位置未考虑的带来的偏差，模型实际将位置偏差乘进来：$bias(d_i) p(i|c(o,i))$

Ranking as Sequence Generation

第二种简化方法只考虑排在这个商品前面的商品对它的影响，不考虑排在这个商品后面的商品对它的影响，可以表示为$p(i|c(o,i)) = p(i|o_1,o_2,...,o_{d_i−1})$,

这个假设有两个好处：

1. 符合用户的习惯，用户一般是从上往下浏览，一般只会关注排这个商品前面的商品
2. 在这个假设的基础上可以采用beam search算法高效的搜索出接近最优的商品排列组合

以最基础的RNN为例，最后问题就转化成了序列生成问题（类似于文本生成），区别于文本生成困惑度这些指标，该问题的优化目标是最大化GMV的期望，且满足序列中物品必须有且仅出现一次。因此可以使用Beam search（集束搜索），其本质上为对贪心算法的放宽，即不再是选择当前最高得分的物品，而是保留前$k$个，类似于dfs的贪心。

对于当前的基础RNN，其算法核心为:

miRNN + attention

miRNN的提出是在LSTM和上面的基础RNN训练结果出现长序列效果不佳的问题，发现这两个学不到长期依赖，具体来说在计算第20位的商品时，排在前4位的商品对它几乎没有影响。这不符合排在前几位影响最大的直观感受，因此论文提出了结合了attention机制的RNN模型（miRNN）：

其核心机制在于，$p(o_i|o_1,...,o_{i-1})$不仅和原来一样依赖当前隐藏层向量$h_i$，也依赖于前面所有的$h$加权和：

$\begin{aligned}p\left(o_{i} \mid o_{1, \ldots, i-1}\right) & =\operatorname{sigmoid}\left(W_{h} h_{i}+W_{c} c_{i}\right) \\h_{i} & =\operatorname{RNN}\left(h_{i-1}, f\left(o_{i}\right)\right) \\c_{i} & =\sum_{j=1}^{i-1} \alpha_{i j} h_{j}\end{aligned}$

其目的是让之前的所有物品都有直接影响，$\alpha$的计算如下，实际上是Softmax 归一化的形式：

$\alpha_{i j}=\frac{\exp \left(g_{i j}\right)}{\sum_{k=1}^{i-1} \exp \left(g_{i k}\right)}$

其中:

$g_{i j}=\operatorname{ReLU}\left(W_{g}\left[\begin{array}{l}a_{i} \\a_{j}\end{array}\right]\right) \\ a_{i}=\operatorname{ReLU}\left(W_{a}\left[\begin{array}{c}p o s_{i} \\h_{i}\end{array}\right]\right)$

对于$\alpha_i$是物品的表征，包含了位置以及特征信息，最后通过$g$ 体现交互。

具体A/B实验效果也体现了注意力机制的对长序列的效果。

参考文献：
​ [1] MMR 多样性算法

​ [2] Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity

​ [3] Globally Optimized Mutual Influence Aware Ranking in E-Commerce Search

​ 推荐系统｜个人学习笔记 - 知乎

​ 推荐系统中的重排算法 - 知乎