1、重排

重排是精排后的一个阶段，主要负责在最终展示结果前对精排后的排序列表进行进一步优化和调整（微调）。重排核心目标是保证一定相关性的前提下，提高结果的多样性，从而提升用户体验，满足用户在不同方面的需求，避免搜索结果过于单一、相似和同质化，为用户提供更丰富、全面的信息。

2、单点估计方法

2.1、分桶

将搜索结果按照文档属性（如类目、来源、形态、样式等）进行分桶
每个桶中的文档按照精排打分降序排序后，再按照指定规则从不同桶中交替抽取结果展示

2.2、滑动窗口

将候选文档按精排打分从高到低降序排序
确定滑动窗口的大小 N（窗口大小可以是固定的，或根据实际情况动态调整）
选择前 N 个候选项，作为滑动窗口中的初始内容
根据业务需求，设置打散规则，确保滑动窗口内的内容多样化，避免相似内容集中在一起。具体的，对滑动窗口中的内容，检查其是否满足多样性约束。如果不满足，则通过交换、重排序或替换等方式调整窗口内的文档，直到满足多样性要求为止
窗口向右滑动一个单位，去掉窗口左边的第一个结果，并加入窗口右侧新的结果
逐步滑动窗口并优化多样性，直到所有搜索结果都被处理完毕，或者达到预设的多样性目标

2.3、MMR

设有一组候选文档 $ D = {d_1, d_2, \dots, d_m} $，需要从中选择一组结果 $ S \subseteq D $，其中每个结果 $ d_i $ 都有一个与查询 $ Q $ 的相关性评分（精排模型打分） $ \text{Rel}(d_i) $，在满足相关性的同时要避免选择与已选结果 $ S $ 中内容过于相似的文档。MMR（Maximal Marginal Relevance） 打分函数为：

\[\text{MMR}(d) = \lambda \cdot \text{Rel}(d) - (1 - \lambda) \cdot \max_{d' \in S} \text{Sim}(d, d')\]

其中：

$ \text{Rel}(d) $ 是文档 $ d $ 与查询 $ Q $ 的相关性得分
$ \text{Sim}(d, d’) $ 是文档 $ d $ 与已选结果集 $ S $ 中某个文档 $ d’ $ 的相似度（可以用余弦相似度或其它度量方法计算）
$ \lambda $ 是一个权重参数，用于平衡相关性和多样性之间的权衡，通常 $ 0 \leq \lambda \leq 1 $
- 如果 $ \lambda = 1 $，MMR算法完全关注相关性
- 如果 $ \lambda = 0 $，MMR算法完全关注多样性（最小化相似度）
$ S $ 是已选结果集，即在当前选择阶段之前已经选择的结果集合

2.4、DPP

DPP（Determinantal Point Processes），行列式点过程 是一种用于选择和排序多样化子集的概率模型，其通过最大化子集的行列式来鼓励选择之间的多样性。DPP 本质是一种在给定集合中选择子集的概率分布，能够有效地避免相似项的集中出现，从而实现多样性的优化。

2.4.1、相似度矩阵

给定一个候选集合 $ X = {x_1, x_2, \dots, x_n} $，每个元素 $ x_i $ 对应一个文档对象。DPP基于 相似度矩阵 来建模对象之间的关系。矩阵 $ K $ 是一个对称矩阵，其中每个元素 $ K_{ij} $ 表示对象 $ x_i $ 和 $ x_j $ 之间的相似度。

相似度矩阵：
\[K = \begin{pmatrix} K_{11} & K_{12} & \dots & K_{1n} \\ K_{21} & K_{22} & \dots & K_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ K_{n1} & K_{n2} & \dots & K_{nn} \end{pmatrix}\]
其中，$ K_{ij} $ 是项 $ x_i $ 和项 $ x_j $ 之间的相似度。

更具体的，将 DPP 模型应用于搜索/推荐任务，需要构建核矩阵。核矩阵可以写成 Gram 矩阵 $K=B^{\top} B$，其中 $B$ 的列是表示文档/物品的向量。将每个列向量 $B_{i}$ 构建为文档相关性得分 $r_{i}\geq 0$ 与一个归一化向量 $f_{i}\in R^{D}$（满足 $\left|f_{i}\right|_{2}=1$）的乘积。核矩阵 $K$ 中的元素可以写成：

\[K_{i j}=\left\langle B_i, B_j\right\rangle=\left\langle r_i f_i, r_j f_j\right\rangle=r_i r_j\left\langle f_i, f_j\right\rangle \tag{a}\]

其中 $\left\langle f_{i}, f_{j}\right\rangle=S_{i j}$ 为衡量文档 $i$ 和文档 $j$ 之间相似性的数值。因此，用户查询 $u$ 的核矩阵可以写成：

\[K=\operatorname{Diag}\left(r_{u}\right)\cdot S\cdot\operatorname{Diag}\left(r_{u}\right)\]

其中 $\operatorname{Diag}\left(r_{u}\right)$ 是对角线向量为 $r_{u}$ 的对角矩阵。

$K_{R_u}$ 表示被文档子集 $R_{u}$ 索引的核矩阵的子矩阵，衡量文档子集 $R_{u}$ 的相关性和多样性的对数概率为：

\[\log\operatorname{det}\left(K_{R_u}\right)=\sum_{i\in R_u}\log\left(r_{u, i}^2\right)+\log\operatorname{det}\left(S_{R_u}\right) \tag{b}\]

等式 (b) 中等号的右边两项分别衡量相关性和多样性，第二项在 $R_{u}$ 的文档表示正交时最大化（促进多样性）。

核矩阵（或称为Gram矩阵）是一个对称矩阵，其中的元素表示数据点对之间的相似性。给定数据集 $ X = { x_1, x_2, \dots, x_n } $，核矩阵 $ K $ 的元素 $ K_{ij} $ 表示数据点 $ x_i $ 和 $ x_j $ 之间的相似度，通常通过核函数（Kernel Function）计算：
\[K_{ij} = k(x_i, x_j)\]
其中，$ k(x_i, x_j) $ 是核函数，表示数据点 $ x_i $ 和 $ x_j $ 之间的相似性度量。

线性核：$ k(x_i, x_j) = x_i^T x_j$

高斯核（RBF核，Radial Basis Function）：$k(x_i, x_j) = \exp\left(-\frac{| x_i - x_j |^2}{2\sigma^2}\right)$

多项式核（Polynomial Kernel）：$k(x_i, x_j) = (x_i^T x_j + c)^d$

Sigmoid核：$k(x_i, x_j) = \tanh(\alpha x_i^T x_j + c)$

2.4.2、DPP 概率模型

DPP 能够将复杂的概率计算转换成简单的行列式计算，基于 DPP 的多样性算法通过计算核矩阵的行列式找到候选中相关性和多样性最大的子集。

如上给定一个候选集合 $ X = {x_1, x_2, \dots, x_n} $，并给定一个子集 $ S \subseteq X $。行列式点过程 $P$ 是在 $X$ 的所有子集的集合 $2^X$ 上的概率测度。当 $P$ 对空集赋予非零概率时，存在一个矩阵 $K \in R^{n \times n}$ 使得每个子集 $S \subseteq X$，$S$ 的概率为：

\[\mathbb{P}(S)\propto d e t(K_{S})\]

其中 $K$ 为一个实数半正定矩阵核矩阵，由 $X$ 的元素索引。

将上述公式归一化后，DPP 选取的概率由以下公式给出：

\[\mathbb{P}(S) = \frac{\det(K_S)}{\sum_{S^{'} \in \mathbb{X}} \det(K_{S^{'}})} = \frac{\det(K_S)}{\det(K + I)}\]

$ K_S $：是子集 $ S $ 中所有项之间的相似度矩阵。即，如果 $ S = {x_1, x_3, x_4} $，那么 $ K_S $ 是矩阵 $ K $ 的一个子矩阵，只包含 $ x_1, x_3, x_4 $ 之间的相似度
$ \mathbb{X} $：是 $X$ 中所有子集的集合
$ \det(K_S) $：是子集 $ S $ 的行列式，行列式越大，表示子集内项之间的多样性越高。即子集内的项之间越不相似，行列式的值就越大
$ \det(K + I) $：是对矩阵 $ K $ 加上单位矩阵 $ I $ 之后的行列式

半正定矩阵（Positive Semi-Definite Matrix）： 给定实对称矩阵 $ A \in \mathbb{R}^{n \times n} $ ，若对于任何非零向量 $ \mathbf{x} \in \mathbb{R}^n $，都有：
\[\mathbf{x}^T A \mathbf{x} \geq 0\]
则矩阵 $A$ 为半正定矩阵。半正定矩阵的特征值是非负的，如果矩阵 $ A $ 的所有特征值都是正的，那么它被称为 正定矩阵（Positive Definite Matrix）。半正定矩阵通常与向量空间中的二次型相关联。具体地，对于矩阵 $ A $ 和向量 $ \mathbf{x} $，二次型 $ \mathbf{x}^T A \mathbf{x} $ 代表一个标量，描述了向量 $ \mathbf{x} $ 在矩阵 $ A $ 所定义的度量空间下的 “大小”。如果 $ A $ 是半正定的，意味着任何向量在该空间中都不会导致负值，因此矩阵 $ A $ 没有 “反向” 的作用，也就是说，它没有 “使向量反向拉伸” 的作用。半正定矩阵对应的二次型是一个凸函数，几何上可以理解为在定义该函数的空间中，每个切面都是向上的，这样的函数值总是保持非负值。

2.4.3、最大化行列式

在 DPP 模型中，每次选择一个子集时，选择的概率取决于该子集内元素的相似度。为了最大化多样性，DPP 会通过最大化子集的行列式来选择最优子集。即在候选文档集合中选取可以最大化后验概率的文档子集，DPP 的 最大后验概率（MAP） 推断可被描述为：

\[S_{\mathrm{map}}=\arg\max_{S \subseteq X} \det(K_S)\]

如上，选择子集的过程为在给定的候选集合 $ X $ 中，通过选择一个子集 $ S $ 来 最大化其行列式，即最大化 $ \det(K_S) $，确保子集的多样性尽可能高。

行列式的几何解释： 行列式表示由矩阵的列（或行）所张成的向量空间的体积。如果将矩阵的列向量（或行向量）看作是空间中的向量，那么行列式的大小与这些向量的排列密切相关。

行列式为0：如果矩阵的行列式为零，表示矩阵的列向量（或行向量）是线性相关的，即这些向量不张成一个高维空间

行列式大于0：如果矩阵的行列式大于零，表示矩阵的列向量在特征空间中是线性独立的，即它们占据了不同的维度，能够覆盖一个较大的空间

线性独立性与多样性：如果多个向量是线性独立的，那么它们无法通过线性组合来表示其他向量，意味着这些向量在空间中占据了不同的维度。

高行列式 → 线性独立：当矩阵的行列式较大时，意味着矩阵中的列向量（或行向量）是线性独立的，说明这些向量在特征空间中分布得较广泛

低行列式 → 线性相关：当行列式较小或为零时，矩阵中的列向量是线性相关的，这意味着这些向量之间的相似度很高，不能有效地覆盖多维空间，导致内容的多样性较低

2.4.4、MAP 推断

DPP 的最大后验概率（MAP）推断是一个 NP-Hard 问题，DPP 通常使用 贪心算法 来逐步选择元素，直到达到所需的子集大小。即每次迭代中，选择文档 $j$ 添加到结果集合 $S_{g}$ 中：

\[j=\arg\max_{i\in Z\backslash S_{g}}\log\det(K_{S_{g}\cup\{i\}})-\log\det(K_{S_{g}}) \tag {1}\]

由于 $K$ 是半正定矩阵，其所有主子矩阵也是半正定矩阵。假设 $\det(K_{S_{g}}) > 0$，$K_{S_{g}}$ 的Cholesky分解为 $K_{S_{g}}=VV^{T}$，其中 $V$ 是可逆下三角矩阵。对于任何 $i \in Z\backslash S_{g}$，$K_{S_{g}\cup{i}}$ 的Cholesky分解可以推导为：

\[K_{S_g \cup \{i\}} = \begin{bmatrix} K_{S_g} & K_{S_g,i} \\ K_{i,S_g} & K_{ii} \end{bmatrix} = \begin{bmatrix} V & 0 \\ c_i & d_i \end{bmatrix} \begin{bmatrix} V & 0 \\ c_i & d_i \end{bmatrix}^{\top} \tag {2}\]

其中行向量 $c_i$ 和标量 $d_i \geq 0$ 满足：

\[Vc_i^{\top} = K_{S_g,i}, \tag {3}\] \[d_i^2 = K_{ii} - \|c_i\|^2_2 \tag {4}\]

根据等式 (2) 可以推导出

\[\det(K_{S_g \cup \{i\}}) = \det(VV^{\top}) \cdot d_i^2 = \det(K_{S_g}) \cdot d_i^2 \tag {5}\]

因此，(1) 等式可以简化为：

\[j = \arg\max_{i \in Z \setminus Y_g} \log(d_i^2) \tag {6}\]

等式 (6) 被求解后，根据等式 (2)，$K_{S_g \cup {j}}$ 的Cholesky分解变为

\[L_{Y_g \cup \{j\}} = \begin{bmatrix} V & 0 \\ c_j & d_j \end{bmatrix} \begin{bmatrix} V & 0 \\ c_j & d_j \end{bmatrix}^{\top} \tag {7}\]

其中 $c_j$ 和 $d_j$ 是现成可用的。因此，可以在向 $S_g$ 添加新项目（文档）后有效更新 $K_{S_g}$ 的Cholesky因子。

对于每个项目 $i$，$c_i$ 和 $d_i$ 也可以增量更新。定义 $c_i’$ 和 $d_i’$ 为 $i \in Z \setminus (S_g \cup {j})$ 的新向量和标量。则有：

\[\begin{bmatrix} V & 0 \\ c_j & d_j \end{bmatrix} \begin{bmatrix} c_i' \\ d_i' \end{bmatrix}^{\top} = K_{S_g \cup \{j\},i} = \begin{bmatrix} K_{S_g,i} & K_{ji} \end{bmatrix} \tag {8}\]

结合等式 (8) 和 (3)：

\[c_i' = \left[ c_i \ \ \left(K_{j i}-\left\langle c_{j},c_{i}\right\rangle\right)/d_{j} \right] \doteq \left[ c_i \ \ e_i \right] \tag {9}\]

则等式（4）为：

\[d_i'^2 = K_{ii} - \|c_i'\|^2_2 = K_{ii} - \|c_i\|^2_2 - e_i^2 = d_i^2 - e_i^2\]

最初，$Y_g = \emptyset$，并且根据等式 (5)，$d_i^2 = \det(K_{ii}) = K_{ii}$。对于无约束MAP推断，停止条件是 $d_{2j} < 1$，或者当施加基数约束时 $S_g > N$。对于后者，引入小数 $\varepsilon > 0$ 并添加 $d_{2}^{j} < \varepsilon$ 到停止标准中，以计算 $1/d_j$ 的数值稳定性。

其中 $F^{\left(N_{x}\right)}$ 是 $N_{x}$ 个 Transformer 编码器块的输出。$W^{F}$ 是可学习的投影矩阵，$b^{F}$ 是偏置项。

3、上下文感知建模

传统的单点估计或启发式打散（如 MMR、DPP）假设文档彼此独立，贪心选取。而基于上下文感知的重排模型认为：一个文档被点击的概率，不仅取决于它自身，还极大地取决于它周围排着什么文档（Context）。

根据系统推断（Inference）和生成最终列表范式的不同，工业界将上下文感知重排分为两大流派：基于打分的重排（Scoring-based）和基于序列生成的重排（Generation-based）。

3.1、基于打分的重排

这类方法的逻辑是：给定一个初始的精排候选列表，将其作为一个整体输入给模型。模型通过捕捉列表内文档的相互影响，直接输出每个文档修正后的得分，最后根据新得分进行一次性重排。

3.1.1、PRM

PRM（Generative Rerank Network）采用 Transformer 结构实现个性化重排。具体的，PRM 模型由输入层、编码层和输出层组成，输入层将初始列表中的所有文档/物品的特征向量进行编码，编码层使用 Transformer 结构来捕捉文档/物品间的相互影响，输出层生成每个文档/物品的点击概率。

PRM 的输入为原始特征矩阵 $X\in R^{n\times d_{\text{feature}}}$ 和个性化矩阵 $PV\in R^{n\times d_{\text{pv}}}$ 拼接（$PV$ 取精排模型的倒数第二层的输出向量），同时利用初始列表中的顺序信息，将排名的向量表示 $P E\in R^{n\times\left(d_{\text{feature}}+d_{p v}\right)}$ 注入输入向量中：

\[E=\left[\begin{array}{c}x_{i_{1}}; p v_{i_{1}}\\ x_{i_{2}}; p v_{i_{2}}\\ \ldots\\ x_{i_{n}}; p v_{i_{n}}\end{array}\right]+\left[\begin{array}{c}p e_{i_{1}}\\ p e_{i_{2}}\\ \ldots\\ p e_{i_{n}}\end{array}\right]\]

使用一个简单的前馈网络将特征矩阵 $E\in R^{n\times\left(d_{\text{feature}}+d_{p v}\right)}$ 转换为 $E\in R^{n\times d}$，即 $E=E W^E+b^E$。

PRM 的输出层使用一个线性层后接一个 softmax 层来为每个项目 $i=i_{1},\ldots, i_{n}$ 生成一个分数 $\operatorname{Score}(i)$ 来对项目进行一步重新排序：

\[\operatorname{Score}(i)=\operatorname{softmax}\left(F^{\left(N_x\right)} W^F+b^F\right), i\in\mathcal{S}_r\]

3.1.2、局限性：为何无法保证全局最优？

基于打分的重排虽然在打分前融合了上下文特征，但其本质依然是 Pointwise（单点估计） 结合 一次性排序（Sort） 的逻辑。这种机制虽然推理极快，但在工业界实际落地中，面临两个无法彻底解决的 “全局最优” 陷阱：

陷阱一：上下文错位（排序悖论）：

假设输入模型的初始列表顺序是 [Doc C, Doc A, Doc B]，Doc A 是在被 Doc C 和 Doc B 包围的输入上下文中计算出了一个高分。然而，系统根据打分重新排序后，最终展示给用户的列表可能变成了 [Doc A, Doc B, Doc C]。

这就产生了一个悖论：模型用来打分评估的上下文，被最后的 Sort 操作破坏了。Doc A 在新的输出上下文中，其真实的点击率可能已经配不上之前预估的高分。

陷阱二：边际收益递减与信息冗余:

由于是一次性打分，模型无法动态感知 “已排好文档” 对 “后排文档” 的价值挤压。

假设用户搜索泛意图词 “苹果”（70% 找手机，30% 找水果）。精排召回了 Doc A (iPhone 15)、Doc B (MacBook)、Doc C (红富士)。模型为了单点准确率，独立打分结果是：$\text{Score}(A)=0.7$、$\text{Score}(B)=0.65$、$\text{Score}(C)=0.3$。最终排序为 [A, B, C]。

但真实的业务逻辑是：当排在第一位的 Doc A 满足了用户的科技意图后，高度同质化的 Doc B 的边际收益将急剧衰减。为了让整个列表的总收益（即全局最优）最大化，排在第二位的最佳选择理应是 Doc C（去覆盖剩余 30% 的水果意图），哪怕 Doc C 的绝对分数很低。

基于独立打分再排序的方法，由于缺乏自回归的动态评估能力，无法打破这种信息冗余的困境。

3.2、基于序列生成的重排

为了追求列表的全局最优，生成式重排抛弃了 “对单 Item 打分再排序” 的思路，将重排问题转化为序列生成问题。

假设候选集为 $X$，目标是生成一个长度为 $L$ 的最优序列 $Y = (y_1, y_2, \dots, y_L)$。根据生成策略的不同，细分为一阶段式和二阶段式。

3.2.1、一阶段式重排

一阶段式重排的核心定义是：直接从庞大的序列搜索空间中，端到端地自回归生出一个最优序列。

模型在解码阶段，每一步 $t$ 根据当前的内部状态 $s_t$ 和已经生成的历史序列 $y_{<t}$，直接从剩余候选集中挑选一个条件概率最大的 Item 加入序列。为了实现这一过程并避免局部最优，这类模型高度依赖特定的解码算法，并演进出了多种经典架构。

miRNN

miRNN（mutual influence RNN）将排序问题视为序列生成问题，使用循环神经网络（RNN）模型来估计点击/购买概率。RNN模型通过迭代计算每个文档/商品的点击/购买概率，并使用 beam search 算法序列生成最优排序。

设 $S=(1,\cdots,N)$ 为待排序的文档集合，$O$ 表示 $S$ 的所有排列集合，$o = (o_1, …, o_N) \in O $ 是一个排列，用户在 $ o $ 中点击文档 $ i $ 的概率表示如下：

\[p(o_i|o_1,...,o_{i−1}) = \text{sigmoid}(W_h h_i) \\ h_i = \text{RNN}(h_{i−1}, f(o_i))\]

其中，$h_{i−1}$ 是序列 $[o_1,…,i−1]$ 的 RNN 向量（上下文表示），$f(o_i)$ 表示提取当前排列为 $o_i$ 的文档特征。

Beam Search

MMR 和 DPP 都是基于贪心策略（Greedy Search），在每一步仅选择当前状态下使目标效用函数（如相关性与多样性的平衡）最大化的文档加入候选列表。贪心策略适合快速生成候选结果，但当对全局最优解有更高要求时，无法达到整体最优解。

Beam Search 是一种启发式搜索算法，用于在序列生成过程中保留多个最优候选，以避免局部最优解。在每个步骤中，算法保留 $ k $ 个具有最高评分的部分序列（称为 beam width 或 beam size），并基于这些部分序列扩展生成新的候选，直至达到所需的序列长度。

初始化
- 设定 beam size 为 $ k $
- 初始化空序列集合 $ B_0 = {[]} $
迭代生成序列
- 对于每个时间步 $ t = 1, 2, \dots, L $：
  - 扩展候选序列: 对于当前的每个部分序列 $ s_{1:t-1} \in B_{t-1} $ 和每个候选内容 $ x \in X \setminus s_{1:t-1} $，生成新的序列 $ s_{1:t} = [s_{1:t-1}, x] $
  - 计算序列得分: 为每个新序列 $ s_{1:t} $ 计算得分函数 $ \text{Score}(s_{1:t}) $，该得分函数考虑序列的相关性和多样性
  - 选择 top-k 序列: 从所有新生成的序列中选择得分最高的 $ k $ 个，构成新的部分序列集合 $ B_t $
终止条件
- 当达到预定的序列长度 $ L $ 或满足其他终止条件时，停止迭代
- 从最终的序列集合 $ B_L $ 中选择得分最高的序列作为输出

Seq2slate

Seq2Slate 的核心是 Seq2Seq 架构，利用循环神经网络（RNN）实现，模型输入是候选集合列表，输出是排序后的结果。Seq2Slate 包含编码器和解码器两个部分：

编码器（Encoder）： 将输入的项目序列编码为上下文向量
解码器（Decoder）： 解码器则根据该上下文向量逐步生成新的项目序列。在每一步，解码器通过指针网络（Pointer Network）选择下一个最优项目，形成新的排序

Seq2Slate 流程可以描述为：

编码器 输入候选集合 $ X = {x_1, x_2, \dots, x_n} $：
\[h_i = \text{Encoder}(x_i), \quad i \in \{1, 2, \dots, n\}\]
生成隐藏状态序列：
\[H = \{h_1, h_2, \dots, h_n\}\]
解码器初始化 初始化解码器的隐藏状态 $ s_0 $ ，可以用编码器的全局信息初始化。
生成上下文向量 对于第 $ t $ 步解码，解码器隐藏状态更新为：
\[s_t = \text{Decoder}(s_{t-1}, y_{t-1})\]
其中 $ y_{t-1} $ 是上一步选中的输出内容。
注意力机制 解码器生成注意力权重 $ \alpha_t $：
\[e_{t,i} = v^\top \tanh(W_h h_i + W_s s_t + b)\] \[\alpha_{t,i} = \frac{\exp(e_{t,i})}{\sum_{j \notin Y_{1:t-1}} \exp(e_{t,j})}, \quad i \in \{1, 2, \dots, n\}\]
其中：
- $ v, W_h, W_s, b $ 是可学习的参数
- $ e_{t,i} $ 表示当前状态 $ s_t $ 与候选项 $ x_i $ 的相关性
- 为避免重复选择，softmax 分母只包括尚未被选中的索引
输出索引选择 根据注意力权重选择输出项索引：
\[y_t = \arg\max_{i} \alpha_{t,i}\]
终止条件 当输出序列长度达到预定值 $ L $ 或其他终止条件满足时，停止解码。

3.2.2、二阶段式重排

如果在每一步采用贪心搜索，极易陷入局部最优；如果使用大 Beam Size，虽然能缓解局部最优，但依然是基于步进概率的累加，缺乏对整个列表生成完毕后的整体业务价值的宏观评估。

为了解决局部最优陷阱，业内演进出了二阶段式重排（生成-评估框架）。它将重排严格解耦为两个独立的阶段：

阶段一：序列生成
- 从 $N!$ 的巨大搜索空间中，启发式地探索并生成 $K$ 个具有较高潜力的候选序列集合（Slates）
  - Beam Search (集束搜索)：这是最常用的生成算法。如 Seq2Slate 和 miRNN 模型在解码时，每一步保留得分最高的 Top-$B$ 个部分序列，最终生成 $K$ 个完整的不同候选序列
  - 强化学习/生成器网络：利用一个轻量级的策略网络（Policy Network）或指针网络（Pointer Network），根据当前状态自回归地采样出多个不同的完整序列
阶段二：序列评估
- 将生成阶段吐出的 $K$ 个候选序列，分别作为一个完整的整体（List/Slate）输入给评估模型，打出全局分数，并选出得分最高的唯一序列展示给用户
  - 评估器网络：$Score(Slate_k) = \text{Evaluator}(Slate_k)$
  - 选择最优：$Slate_{optimal} = \arg\max_{k \in \{1, \dots, K\}} Score(Slate_k)$

GRN

GRN（Generative Rerank Network）采用评估器（Evaluator）和生成器（Generator）实现上下文感知重排序框架。

1、评估器（Evaluator）：

评估器采用双向 LSTM 和自注意力机制来建模标注的最终排序列表中的上下文信息，其目标是更精确地预测每个文档/物品在最终排序列表中的上下文交互概率：

\[E\left(x_v^t\mid u,\mathcal{V};\Theta^E\right)=\sigma\left(f\left(f\left(f\left(x_u\oplus x_v^t\oplus h_t\oplus a_t\right)\right)\right)\right)\]

其中，$x_{u} $ 和 $x_{v}^{t}$ 分别为用户和最终排名列表 $\mathcal{V}$ 中第 $t$ 个物品的向量表示，$h_{t}$ 是 LSTM 的输出状态，$a_{t}$ 是自注意力机制的输出，$f(x)=\operatorname{ReLU}(W x+b)$，$\sigma(\cdot)$ 是逻辑函数。评估器的参数集为 $ \Theta^{E}= { W, b } $，即 Bi-LSTM 和 MLP 的参数联合。

2、生成器（Generator）：

生成器，结合 GRU、注意力机制和指针网络来逐步选择输入排序列表中的物品。生成器的目标是学习一个重排序策略，以生成最终的排序列表。生成器包含演化层、激活层、选择层：

演化层（Evolving Layer）
- 用户的意图或兴趣会随着时间的推移而变化，演化层采用 GRU 模块，在每一步将序列信息提炼为目标用户的状态表示，以学习目标用户在浏览历史中的动态表示。在第 $t$ 步，设 $\mathcal{S}=\left[x_{s}^{0}, x_{s}^{1},\ldots, x_{s}^{t-1}\right]$ 是从输入排名列表 $C$ 中选出的 $t-1$ 个项目，GRU 模块的输出可以计算如下：
\[\begin{aligned}z_{t}&=\sigma\left(W_{z} x_{l}^{t-1}+U_{z} h_{t-1}\right)\\ r_{t}&=\sigma\left(W_{t} x_{l}^{t-1}+U_{t} h_{t-1}\right)\\ \widetilde{h}_{t}&=\tanh\left(W x_{l}^{t-1}+U\left(r_{t} h_{t-1}\right)\right)\\ h_{t}&=\left(1-z_{t}\right) h_{t-1}+z_{t}\widetilde{h}_{t}\end{aligned}\]
- 其中$W_{z}, U_{z}, W_{t}, U_{t}, W$和 $U$ 是可训练的变量，$H=\left[h_{1},\ldots, h_{t}\right]$ 表示选定列表 $\mathcal{S}$ 的序列编码。
激活层（Activating Layer）
- 激活层在选定的项目的顺序表示条件下，使用注意力机制来计算每个剩余项目的重要性权重。给定输入排名列表中第 $j$ 个剩余项目的表示 $x_{c}^{j}$ 和已选择列表的序列表示 $H$，采用加权和生成输入排名列表中第 $j$ 个项目的新表示，相应的注意力权重如下：
\[\begin{aligned} a_h^i&=\frac{\exp\left(h_i W x_c^j\right)}{\sum_{i=1}^t\exp\left(h_i W x_c^j\right)}\\ a_c^j&=\sum_{i=1}^t a_h^i h_i\end{aligned}\]
选择层（Selector Layer）
- 在获得输入排名列表中项目的表示 $a_{c}^{j}$ 之后，采用指针网络选择最合适的项目加入到最终排名列表中。对于输入排名列表 $C$ 中的第 $j$ 个项目 $x_{c}^{j}$，在第 $t$ 步采用 MLP 实现特征交互：
\[\tilde{s}_c^j=f\left(f\left(f\left(x_u\oplus x_c^j\oplus a_c^j\right)\right)\right)\]
- 之后采用 softmax 函数将向量 $\tilde{s}_{c}^{j}$ 归一化：
\[s_c^j=\frac{\exp\left(\tilde{s}_{c}^{j}\right)}{\sum_j^m\exp\left(\tilde{s}_{c}^{j}\right)}\]
- 其中 $m$ 为 $C$ 中项目的数量。随后在第 $t$ 步，生成器将选择具有最高选择概率的项目（排除已选中的项目）：
\[G^t\left(u, C;\Theta^G\right)=x_c^{\operatorname{arg} \max_j s_c^j} \quad \text{ s.t.} x_c^{\operatorname{arg} \max_j s_c^j} \notin\mathcal{S}\]

3、优势奖励：

GRN 采用交叉熵损失函数训练评估器，并使用策略梯度和优势奖励训练生成器。优势奖励包括自我奖励和差分奖励：

\[r\,\bigl(x_{o}^{t}\mid u,O\bigr)=r^{\mathrm{s e l f}}\left(x_{o}^{t}\mid u,O\right)+r^{\mathrm{diff}}\left(x_{o}^{t}\mid u,O\right)\]

其中，$r^{\mathrm{self}}$ 是自我奖励，$r^{\mathrm{diff}}$ 是差分奖励，$x_{o}^{t}$ 为生成的最终排名列表 $O=\left[x_{o}^{1},\ldots,x_{o}^{n}\right]$ 中第 $t$ 个项目。

Self reward（自奖励）：
- 自奖励指项目在最终排名列表中自身的交互概率所带来的奖励，奖励由评估器（Evaluator）预测：
\[r^{\text{self}}\left(x_o^t\mid u, O\right)=E\left(x_o^t\mid u, O;\Theta^E\right)\]
Differential reward（差分奖励）：
- 差分奖励指一个项目在最终排名列表中对其他项目交互概率的影响所带来的额外奖励，即使其自身的交互概率较低，但如果有助于提升后续项目的选择概率，仍应给予正向奖励。差分奖励通过比较包含某个项目时和其他项目交互概率的总和与不包含该项时的概率总和之间的差异来计算
\[\begin{aligned} r^{\text{diff}}\left(x_o^t\mid u, O\right)=&\sum_{x_o^i\in O^{-}} E\left(x_o^i\mid u, O;\Theta^E\right)-\\ &\sum_{x_o^i\in O^{-}} E\left(x_o^i\mid u, O^{-};\Theta^E\right)\end{aligned}\]
- 其中，$O^{-}$ 是 $O$ 中不包含 $x_o^t$ 的集合。

4、训练流程：

训练过程如下步骤迭代，直到生成器的参数收敛：

使用列表交互记录来训练评估器直到参数收敛
生成器为评估器生成最终的排名列表
通过基于评估器的优势奖励的策略梯度更新生成器参数

4、混排

在真实的搜索引擎与推荐流中，精排结束后的结果往往涉及多种体裁（如自然图文、短视频、直播卡片、商业广告等）。混排（Mixed Ranking / Blending）的核心命题是：在极其有限的屏幕展示坑位（Slots）中，如何决定插入哪些体裁、插入在什么位置，才能在保障整体用户体验（用户价值）不严重受损的前提下，最大化平台的整体收益（商业价值）。

4.1、带约束的优化目标建模

混排过程可以抽象为一个队列选择问题。假定在一次搜索/推荐请求中，精排阶段返回了一个按照用户价值从大到小排列的原生队列，广告系统返回了一个按照商业价值从大到小排列的广告队列。定义变量 $x_i \in {0, 1}$ 表示是否把一个广告放入位置 $i$：

如果 $x_i = 1$，那么将当前广告队列的第一个物料放入位置 $i$，然后将其从广告队列中移除
如果 $x_i = 0$，那么将当前原生队列的第一个物料放入位置 $i$，然后将其从原生队列中移除

设在位置 $i$ 时：

广告的商业价值为 $r_i^a$，用户价值为 $u_i^a$
原生内容不具备商业价值，其用户价值为 $u_i^o$

则将排序问题转化成了如下带约束的优化目标：

\[\max \sum_{i} x_{i} r_{i}^{a} - \frac{w}{2}\|x\|^2\] \[\text{s.t.} \sum_{i} x_{i} u_{i}^{a} + (1-x_{i}) u_{i}^{o} \geq C\] \[x_i \in \{0, 1\}\]

其中，$C$ 是一个人工设定的参数（代表系统对整体用户体验把控的底线阈值），$-\frac{w}{2}\|x\|^2$ 作为正则项控制分配的平滑性。这个优化目标的物理含义极其明确：在保证总用户价值不低于 $C$ 的约束下，最大化总商业价值。

4.2、对偶求解与影子价格 (Shadow Bid)

上述带约束的优化问题通过拉格朗日乘子法等对偶求解方式，可以得到一个非常简单的解析解形式决定位置 $i$ 上的内容归属：

\[x_i = \begin{cases} 1, & r_i^a + \alpha u_i^a - \alpha u_i^o > 0 \\ 0, & \text{其他} \end{cases}\]

$\alpha$：在求解优化问题的过程中通过约束参数 $C$ 计算出来的对偶变量，被称为影子价格（Shadow Bid）。它的作用是将用户价值兑换成等值的商业价值，从而实现跨维度的直接比较
物理含义：在每个位置 $i$，比较一下原生队列和广告队列头部物料的总价值。如果广告的商业价值和用户价值之和 $(r_i^a + \alpha u_i^a)$ 大于原生内容的用户价值 $(\alpha u_i^o)$，那么就排广告（$x_i = 1$），否则排原生内容（$x_i = 0$）

4.3、异构价值的比较难题

虽然通过影子价格 $\alpha$ 实现了理论上的换算，但在真实的线上工业环境中，这种不同体裁价值的直接比较仍然存在许多需要慎重考虑的问题：

4.3.1、体裁分数的方差差异与校准

不同体裁的价值分数往往具有不同的方差（Variance）。例如，短视频的点击率预估方差可能远大于普通图文，短视频的点击率（pCTR）可能分布在 [0.01, 0.25]（高方差、长尾），而普通图文/普通商品的 pCTR 可能极其集中在 [0.05, 0.10]（低方差）。

如果直接使用原始的预估分进行 $\alpha$ 兑换和比较，短视频的高分头部（Upper Tail）将拥有绝对的数值碾压优势。这会导致在某次混排请求中，图文内容被高方差的短视频挤压，不仅破坏了搜索结果的多样性，还会挫伤图文创作者的流量生态。

所以，在直接相加的比较公式 $(r_i^a + \alpha u_i^a > \alpha u_i^o)$ 中，方差较大的体裁会产生更大的分数波动。这种波动会导致在不同时间段或不同用户群体中，某一种体裁被大量曝光，进而带来整体流量结构的不稳定。

保证不同形态的物料能够在一个绝对公平的标尺下竞争，可以在混排融合前引入以下几种解法：

1、Z-Score 标准化：

将比较的基准从 “绝对预估分” 转换为 “该物料在自身体裁中的相对优秀程度”。通过对各自队列内的分数进行滚动窗口（如过去 1 小时）的零均值、单位方差转换：

\[\tilde{u}_i^o = \frac{u_i^o - \mu_{o}}{\sigma_{o}} , \quad \tilde{u}_i^a = \frac{u_i^a - \mu_{a}}{\sigma_{a}}\]

其中 $\mu$ 和 $\sigma$ 分别代表该体裁预估分的均值和标准差。转换后，图文的 “Top 1%” 与短视频的 “Top 1%” 在数值尺度上被强行拉齐，消除了大方差体裁的霸榜效应。

2、CDF 分位数映射：

由于深度学习模型的输出往往不是标准的正态分布（多为极度长尾的分布），Z-Score 依然会有偏差。一种做法是采用累积分布函数（CDF），将绝对分数映射为 [0, 1] 区间内的分位数。

此时，混排引擎不再比较绝对值 $0.15$ 和 $0.08$，而是比较 “战胜了 99% 短视频的候选物料” 和 “战胜了 95% 图文的候选物料”，从而实现严格的生态折算。

3、基于软约束的动态偏置：

如果业务生态强行要求某种弱势体裁的曝光占比必须达到 $\beta$（例如为了扶持新业务，直播卡片必须占 10%），系统会在融合算分公式中引入一个特定体裁的偏置项 $b_{type}$：

\[\text{Score}(i) = V_{\text{com}}(i) + \alpha \cdot V_{\text{user}}(i) + b_{type(i)}\]

一旦流式计算引擎（如 Flink）监控到图文或某类原生体裁的实际曝光占比跌破安全安全阈值，系统会自动放大对应的偏置项 $b_{type(i)}$。这种方法相当于给弱势体裁强行 “加温”，在混排的剧烈竞争中实现软性的多样性保底。

4.3.2、$\alpha$ 的动态调节难题

在真实业务中，流量、用户大盘和广告预算是实时变化的，固定的约束 $C$ 和计算出的 $\alpha$ 无法适应环境漂移。针对如何动态求解或逼近最优的 $\alpha$，业内演进出了以下工程解法：

1、PID 动态水位控制：

将 $\alpha$ 视为一个动态调节阀。如果当天插入了太多商业化内容导致大盘体验跌破红线 $C$，产生误差 $e_t$。PID 控制器会实时调大 $\alpha$ 的值，迫使系统出更多的优质自然内容。

\[\alpha_t = \alpha_{t-1} + K_p \cdot e_t + K_i \sum e_t + K_d (e_t - e_{t-1})\]

2、强化学习求解：

固定的 $\alpha$ 忽略了用户的个性化耐受度（有人极度反感广告，有人喜欢看带货）。前沿方案采用 Actor-Critic 等强化学习框架，将系统状态 $s_t$（用户敏感度画像、上下文）输入网络，实时生成千人千面的 $\alpha$ 向量，在不触怒敏感用户的前提下实现长期 LTV（生命周期价值）的最大化。

3、JECB (Joint End-to-End Cross-channel Bidding)：

一些平台引入了跨通道联合出价机制。平台充当 “虚拟广告主”，为用户的自然点击/转化进行虚拟出价。例如，平台认为用户的一次自然点击价值 $0.5$ 元，从而强行将 $V_{user}$ 转化为货币单位，与广告直接同台竞价。

5、强化学习在重排中的应用

前面探讨的重排与混排策略，无论是启发式的 MMR，还是深度学习的 Seq2Slate，其优化目标大多局限于当前页面（Page/Slate）的单次反馈最大化。

如果想要最大化用户的长期生命周期价值（LTV, Long-Term Value）—— 如总停留时长、长期 GMV、次日留存率，传统方案存在如下缺陷：

独立假设：传统模型将用户的每次下拉刷新视为孤立事件（I.I.D 假设），未对样本间的时序依赖进行建模，默认用户偏好与状态不随历史交互序列发生动态变化，忽略了连续交互过程中的用户状态转移特性。因此无法刻画历史交互序列对用户实时决策状态的因果影响，也无法捕捉连续内容曝光对用户体验的累积负向效应。易因连续同质化推送引发用户疲劳，导致用户直接退出、停留时长提前终止
即时反馈：无论采用 Pointwise 还是 Listwise 范式构建损失函数，其参数优化的唯一锚点均为即时奖励对应的即时交互标签，无法对用户长期生命周期价值对应的延迟回报进行信用分配与梯度传导，天然存在短视性优化偏差。短期内可实现点击通过率（CTR）等即时指标的显著提升，但用户点击后因内容预期与实际价值背离，会产生体验反感与平台信任流失，直接导致用户次日留存率等核心长期指标下滑，形成 “以牺牲用户长期价值为代价换取短期指标增长” 的负向循环
信息茧房：传统监督学习排序模型因核心优化目标锚定短期即时搜索推荐精准度与即时 CTR 最大化，易催生信息茧房效应

强化学习可以将会话建模为连续的状态转移，能够识别用户的疲劳状态节点，通过策略性穿插平台内容唤醒用户兴趣、维持会话粘性，从而拉长总停留时长。依托贝尔曼方程实现对未来累计折扣回报的全局优化，能够以短期单次点击的适度让步为代价，优先推送高可信度、高价值的优质内容，持续构建用户对平台的长期信任，对齐用户生命周期价值最大化的目标。此外，强化学习天生具备探索机制，愿意牺牲局部坑位去试探用户的新品类兴趣，从而培养用户、拓宽商业化盘子。

5.1、基于马尔可夫决策过程 (MDP) 的序列建模

在强化学习框架下，搜索引擎被建模为一个智能体（Agent），用户被视为环境（Environment）。重排过程被严格定义为一个马尔可夫决策过程（MDP），由五元组 $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ 构成：

状态空间 (State, $s_t \in \mathcal{S}$)：在时间步 $t$，智能体观测到的环境状态。包括用户的静态画像、当前 Query、历史交互序列，以及用户在当前 Session 中刚刚产生的情绪与疲劳度反馈
动作空间 (Action, $a_t \in \mathcal{A}$)：智能体做出的决策。在重排/混排中，动作通常定义为生成一个排列好的完整文档序列（Slate），或输出一组混排的动态权重参数（如 $\alpha$ 向量）
状态转移概率 ($\mathcal{P}(s_{t+1} \mid s_t, a_t)$)：用户看到搜索结果 $a_t$ 并产生交互后，其内在兴趣和意图发生转移的客观规律
奖励函数 (Reward, $r_t \in \mathcal{R}$)：智能体下发搜索结果后获得的即时反馈。这也是融合多目标的终极形态：
- \[r_t = w_1 \cdot \text{Click} + w_2 \cdot \text{DwellTime} + w_3 \cdot \text{Purchase} - w_4 \cdot \text{Dislike}\]
折扣因子 ($\gamma \in [0, 1)$)：平衡短期收益与长期收益的超参数

强化学习的优化目标，是寻找一个最优的排序策略 $\pi^*(a_t \mid s_t)$，最大化期望的累积折扣回报:

\[J(\pi) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{T} \gamma^t r_t \right]\]

5.2、Actor-Critic 与 DDPG

由于重排的动作空间（连续的融合权重，或海量物品的组合排列）极其庞大，传统的 Q-Learning 无法处理。工业界目前的主流标配是基于 Actor-Critic（演员-评论家）框架的深度确定性策略梯度算法（DDPG, Deep Deterministic Policy Gradient）。

5.2.1、Critic 网络：长期价值评估

Critic 网络 $Q(s, a \mid \theta^Q)$ 扮演 “评论家” 的角色，预估在状态 $s_t$ 下采取动作 $a_t$ 后，未来能够获得的长期总收益（Q-value）。其通过最小化时序差分误差（TD Error）逼近真实的贝尔曼方程：

\[L(\theta^Q) = \mathbb{E}_{s_t, a_t, r_t, s_{t+1}} \left[ \left( y_t - Q(s_t, a_t | \theta^Q) \right)^2 \right]\]

其中，目标值 $y_t = r_t + \gamma Q(s_{t+1}, \mu(s_{t+1}) \mid \theta^{Q’})$。这种机制使得模型能够量化当前决策对未来所有步骤深远的影响。

5.2.2、Actor 网络：重排策略生成

Actor 网络 $\mu(s \mid \theta^\mu)$ 根据当前状态 $s_t$ 直接输出确定性的重排动作。Actor 网络的更新不再依赖传统的监督学习标签，而是沿着 Critic 网络指出的 “长期收益变大” 的梯度方向进行更新：

\[\nabla_{\theta^\mu} J \approx \mathbb{E}_{s_t} \left[ \nabla_a Q(s, a | \theta^Q)|_{s=s_t, a=\mu(s_t)} \nabla_{\theta^\mu} \mu(s | \theta^\mu)|_{s=s_t} \right]\]

5.3、工程落地

强化学习在推荐和搜索中落地，面临线上试错代价过高的情况。如果直接用未经训练的 Actor 网络向真实用户随机下发重排序列，会导致大盘核心指标暴跌。

为了解决这个问题，工业界通常引入了基于生成模型的世界模型：

离线仿真： 利用历史的百亿级 User-Item 交互日志，预训练高保真深度学习用户环境模拟器。输入 $(s_t, a_t)$，可以预测出用户的反馈 $r_t$ 和下一步状态 $s_{t+1}$
虚拟预训练： RL 智能体在仿真环境中完成大规模虚拟重排任务的策略探索与试错学习，通过海量迭代优化更新 Actor-Critic 网络参数，直至网络收敛至稳定的策略最优解
线上微调： 将预训练收敛的 Actor 策略部署至线上生产环境，结合小流量真实探索数据开展轻量级微调，保障安全与业务正向收益

6、总结

搜索重排是信息检索中不可或缺的环节，其目标是在精排阶段生成的候选列表基础上，通过更复杂的模型和策略，进一步优化列表的质量，平衡效率与多样性并使业务价值最大化。

重排所面临的挑战有：

上下文一致性问题： 打分时的上下文与最终展现的上下文不一致，影响模型效用
多目标优化冲突： 点击率、转化率、多样性、用户满意度等目标间存在冲突，难以找到最佳平衡点
全局最优性难以实现： 贪心策略无法考虑后续决策对当前排序的反作用，导致全局优化受限
计算效率与在线部署： 重排序算法复杂度较高，需要在高效计算与实时响应间找到平衡
用户需求的多样化： 不同用户在不同场景下的需求千差万别，单一策略难以覆盖

在上述挑战下，重排可以从以下几个方向发展：

上下文感知的深度建模
- 利用 Transformer 等模型构建全局上下文，动态调整排序决策
- 考虑候选内容的历史交互、用户偏好与序列特征，提升个性化排序效果
生成式重排的广泛应用
- 加强序列生成-序列评估的联动，确保生成序列的全局最优性
- 引入强化学习增强生成策略，提升长期用户满意度
多目标协同优化
- 建立统一的多目标优化框架，综合短期和长期目标进行排序
- 动态调整权重，实现点击率与多样性、内容公平性间的有效平衡
高效模型设计与部署
- 利用模型压缩、知识蒸馏等技术降低计算成本
- 探索轻量化、高效的模型架构以适应实时应用场景
用户互动与反馈机制
- 引入用户显性或隐性反馈，构建交互式重排序优化框架
- 动态调整排序决策以适应用户需求的变化
长期生态建设
- 优化长尾内容的曝光，激励内容创作者积极参与
- 综合考虑用户体验与平台生态，促进系统长期健康发展

参考文献

The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries
Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity
Determinantal point processes for machine learning
k-DPPs: Fixed-size determinantal point processes
Globally Optimized Mutual Influence Aware Ranking in E-Commerce Search
Seq2Slate: Re-ranking and Slate Optimization with RNNs
Personalized Re-ranking for Recommendation
GRN: Generative Rerank Network for Context-wise Recommendation

排序-重排