多样性重排：从 MMR 到 RL 端到端学习

1.1 核心矛盾：相关性 vs 多样性

在信息检索和推荐系统中，最朴素的排序策略是按相关性/预测分数降序排列——但这会产生严重的冗余问题：

多样性的本质是：在候选集中选出一个集合，使得这个集合整体的信息量（覆盖度、用户满意度）最大，而不只是追求列表中每个单项的质量。这是一个集合优化问题（Set Optimization），与逐条排序（point-wise ranking）有本质区别。

1.2 两类多样性目标

研究者逐渐发现"多样性"本身存在两种不同出发点，对应两套解法：

而 RL4CTE 则从更高层次出发：用强化学习直接优化用户 session 内总点击数，多样性成为提升长期目标的隐式手段，而非显式约束。

1.3 方法演进时间线

1.4 方法谱系总图

2.0 MMR 在推荐链路的位置

先明确 MMR 做的是哪个环节，以及重排（Re-ranking）和混排（Blending/Fusion）的区别：

2.1 问题定义

MMR 产生于文档摘要和信息检索场景：给定查询 $Q$，从文档集 $R$ 中已选出一个子集 $S$，现在要再挑一篇文档加入 $S$，使得它既与 $Q$ 相关，又与 $S$ 中已有文档不重复。

这是一个非常经典的"边际效益递减"问题：第一篇搜索结果带来很多信息，第二篇如果和第一篇一模一样，边际信息量接近于零。MMR 的贡献就是把"边际相关性"（Marginal Relevance）这个直觉形式化。

2.2 核心公式

每次贪心选下一个文档 $d_i$，选的标准是最大化：

逐项解读：

• $\text{Sim}_1(d_i, Q)$：$d_i$ 与查询 $Q$ 的相关度（TF-IDF cosine 或 BM25 分数）。
• $\max_{d_j \in S}\text{Sim}_2(d_i, d_j)$：$d_i$ 与已选集合 $S$ 中最相似文档的相似度——代表"冗余度"。
• $\lambda \in [0,1]$：$\lambda=1$ 退化为纯相关性排序；$\lambda=0$ 只最大化多样性。

2.3 贪心算法流程

每轮需要计算所有剩余文档的 MMR 分数，总复杂度 $O(k \cdot n)$（$n$ 为候选集大小），是线性时间算法。

2.4 推荐系统实例：快手/淘宝商品搜索重排

场景：用户在电商 App 搜索"跑步装备"，精排输出 top-200 个商品（每个商品有精排分）。现在做 MMR 重排选出 top-20 展示。

每个 item 用商品图文 embedding（维度 128）表示。相似度矩阵（关键值，越高越相似）：A-B 余弦相似度 0.95（都是 React 跑鞋，颜色不同）；A-C 相似度 0.78（都是跑鞋但不同品牌）；A-D 相似度 0.12（鞋 vs 手臂包）。设 $\lambda = 0.6$（略偏相关性）。

2.5 深度分析与局限

3.1 问题背景：视觉浏览发现

这篇论文来自 Amazon Stream——一个类似"无限 feed 流"的时装浏览产品。用户没有明确搜索意图，只是随手滚动，期望被"惊喜"地发现感兴趣的商品。

系统面临两个核心挑战：

• 冷启动 + 曝光不足：新品或冷门商品被曝光少，模型对其点击概率估计不准，容易一直推热门商品。
• 多样性需求：用户研究表明，多样化的展示流能让用户更快发现感兴趣的品类，从而提升 CTR 和停留时长。纯按预测分排序会造成品类聚集。

解决方案分三层：① 相关性打分（Thompson Sampling）→ ② 次模多样化重排 → ③ 个性化类目权重。

3.2 第①层：Thompson Sampling 打分（解决"新品永远不被看见"）

什么是 Beta 分布？

Beta 分布是专门用来描述"一个概率值大概在哪个范围"的分布。它的参数是两个正整数 $\alpha$ 和 $\beta$：

直觉上：$\alpha$ 是"成功的次数"，$\beta$ 是"失败的次数"，均值 = 成功率。方差越大，说明数据越少，对这个成功率越不确定。

Thompson Sampling 的核心思想：对每个商品不是存"一个固定的 CTR 数值"，而是维护一个Beta 分布，表示"这个商品的真实点击率大概在哪个范围"。每次打分时从 Beta 分布里随机抽一个值用，而不是总用均值。

更新规则很简单：如果展示后被点击了，$\alpha$ 加 1；如果没被点击，$\beta$ 加 1。不需要重新训练模型，O(1) 实时更新。

论文中实际使用的打分模型比 Beta 分布更复杂——用 Bayesian Linear Probit 回归，考虑商品属性（品牌、颜色等）：

其中 $\Phi^{-1}$ 是 probit 函数，$x_i$ 是商品属性的权重（也用 Bayesian 后验分布维护）。但核心思想不变：每个参数不是存一个固定值，而是存一个分布，采样时随机抽取。

这一层解决的是：候选池里每个商品的打分（类似精排的功能，但加了探索性）。打完分后，进入第②层做多样化重排。

3.3 第②层：次模多样化重排（解决"品类全是鞋"）

核心目标函数：给定 $n$ 个商品的类目属性向量 $\mathbf{a}_i \in \{0,1\}^d$（one-hot 类目编码）和用户类目偏好向量 $\mathbf{w} \in \mathbb{R}^d$，选 $k$ 个商品子集 $A_k$ 最大化：

逐项翻译成大白话：

• 第一项（多样性项）：对每个类目 $j$，计算 $\log(1 + \text{已选商品中属于 }j\text{ 类的数量}) \times w_j$，然后对所有类目求和。log 保证同一品类选得越多，边际增益越小（这就是"次模"——边际收益递减）。$w_j$ 是类目 $j$ 的权重，来自第③层。
• 第二项（相关性项）：$\sum s(a_i)$ 就是把选入的每件商品的 Thompson Sampling 打分加起来，鼓励整体相关性高。

次模函数的数学定义：集合函数 $f$ 是次模的，当且仅当 $\forall A \subseteq B$，$\forall x \notin B$：

大白话：集合越大，再加一个元素带来的边际收益越小。这保证了贪心算法有 $(1 - 1/e)$ 近似比——虽然贪心不是最优解，但至少不会比最优解差太多。

贪心运行方式：从空集合 $A_0 = \emptyset$ 开始，每轮从候选池中找"加入后 $\varrho$ 增量最大的商品"，选它，重复 k 次。复杂度 $O(dkn)$，用 CELF 加速（利用次模性延迟重计算，实际比暴力快很多）。

3.4 第③层：个性化类目权重（解决"每个人喜好不同"）

① 全局类目权重（Baseline）

先用全局数据给每个类目算一个"基础权重"，作为所有用户的先验：

$c_j$ = 全站类目 $j$ 的总点击数，$v_j$ = 全站类目 $j$ 的总曝光数。$\alpha, \beta$ 是平滑参数（类似 Beta 分布的先验），防止数据少的类目权重为 0。
大白话：每个类目在全站的"受欢迎程度"。

② 个性化用户权重：Dirichlet-Multinomial 模型

对用户 $u$，假设他的类目兴趣比例 $\mathbf{w}_u$ 是一个概率向量（各类目之和=1），用 Dirichlet 分布建模：

大白话翻译：

• $\mathbf{c}_u$ 是用户 $u$ 在各类目的点击次数（比如 Alice：[鞋50, 手表5, 上衣3, 包2]）。这个用 Multinomial（多项分布）建模——每次点击像"掷骰子"，各类目的概率不同。
• $\mathbf{w}_u$ 就是那个骰子的概率向量——我们想要的东西。但它是隐变量，不能直接观测。用 Dirichlet 分布建模"这个概率向量本身的不确定性"。
• Dirichlet 和 Multinomial 是共轭分布（就像 Beta 和 Binomial 是共轭的一样），所以后验均值有简洁公式：

其中 $\boldsymbol{\alpha}_0$ 是先验参数（通常取全局类目权重对应的 $\alpha$ 值），$\|\cdot\|_1$ 是向量各分量之和。
大白话：用户的类目权重 = (用户自己的点击计数 + 全局先验) 的归一化。全局先验防止冷启动用户权重全是 0。

③ 类目兴趣扩散（把隐性兴趣挖出来）

用户 Alice 只点过鞋和手表，从没点过跑步裤——那跑步裤权重为 0 吗？用类目共现矩阵 $M$（$M_{ij}$ = 同时点过类目 $i$ 和 $j$ 的用户比例）做扩散：

大白话：把用户当前的类目权重向量，乘以类目之间的共现矩阵，再归一化。效果是"喜欢鞋的人也喜欢跑步裤"这种关联会被传导过来。

3.5 三层串联：完整流程总结

以用户 Alice（喜欢鞋和手表）为例，从一次首页推荐请求到最终展示的完整链路：

3.6 分析

4.1 核心思想：分布对齐

Steck 提出了一个全新的多样性视角：推荐列表的类目分布应该与用户历史偏好分布一致。

这与 MMR / Adaptive PD 的"内容多样性"不同：后者关注集合内元素之间的差异，Calibrated Rec 关注集合的统计分布与目标分布的偏差（distribution matching）。如果用户兴趣本身就是多元的，纯按分数排序会导致"赢者通吃"——高分类目占据整个列表，用户也感兴趣的低分类目被完全忽略。

4.2 分布度量：KL 散度

定义用户 $u$ 的目标分布 $P(H_u)$ 和实现分布 $Q(L_u)$：

• $H_u$ 是用户历史交互集合，$g(i)$ 是 item $i$ 的类目集合（一个电影可以属于多个类目）。
• $w_{u,i}$ 是用户对 item $i$ 的评分（或隐式反馈权重）。
• $\text{prop}(g|i) = 1/|g(i)|$ 是类目 $g$ 在 item $i$ 中的占比（均分）。

实现分布 $Q(L_u)$ 计算完全类似，只是把 $H_u$ 换成推荐列表 $L_u$，$w_{u,i}$ 换成预测分 $\hat{w}_{u,i}$。

用 KL 散度度量两个分布的偏差：

KL 散度三个关键性质：① $P = Q$ 时 KL = 0（完美校准）；② 对小概率类目的偏差敏感；③ 倾向于均匀分布（防止极端集中）。

4.3 目标函数与优化

最终目标是在相关性和校准之间权衡：

其中 $\text{REL}(L_u) = \sum_{i \in L_u} \hat{w}_{u,i}$，$\lambda \in [0,1]$ 控制权衡：$\lambda=0$ 为纯相关性，$\lambda=1$ 为纯校准。这是 NP-hard 的组合优化问题，用次模贪心求解，保证 $(1-1/e)$ 近似比：

4.4 推荐系统实例：快手短视频 Feed 重排

场景：用户 Bob 在快手刷短视频。Bob 过去 30 天的浏览记录中，看了美食 70%、搞笑 20%、体育 10%。现在要给他生成下一屏的 10 个短视频。

Step 1：目标分布 P（用户历史口味）

直接从 Bob 最近的浏览记录统计各类目的占比：

Step 2：精排直接 top-10 的问题（"赢者通吃"）

精排模型（比如 DeepFM）给每个视频预测一个 CTR 分数。因为 Bob 看美食多，美食视频的 CTR 预估普遍偏高。按分数排序取 top-10：

现在算 KL 散度来量化这个偏差：

• 美食：$0.70 \times \log(0.70/0.80) = 0.70 \times (-0.134) = -0.094$。美食在推荐里占 80%，但 Bob 的目标只有 70%，所以这部分是"过度代表"的，贡献负值。
• 搞笑：$0.20 \times \log(0.20/0.10) = 0.20 \times 0.693 = +0.139$。搞笑在推荐里只占 10%，但 Bob 的目标有 20%，所以这部分是"不足代表"的，贡献正值。
• 体育：$0.10 \times \log(0.10/0.10) = 0$。刚好对齐，不贡献偏差。

KL 总分 = $-0.094 + 0.139 + 0 = +0.045$。值越大 = 偏差越大 = 校准越差。

Step 3：Calibrated 贪心重排（逐个解释每一步）

Calibrated Rec 的目标函数：

设 $\lambda = 0.5$，意思是"一半权重给相关性，一半权重给分布对齐"。贪心过程：每次从候选池里选一个加入列表 $L$，选让目标函数增长最多的那个。

实际工程中的补充考量

4.5 分析

5.1 问题背景

MMR 的 pair-wise 相似度减法只考虑"最像已选中哪篇"，没有捕捉集合整体的多样性结构。两篇文章各自和已选集合相似度都很低，但它们彼此相似——这种情况 MMR 处理不了。

行列式点过程（Determinantal Point Process, DPP）用矩阵的行列式来度量集合的"体积"——行列式越大，意味着集合中的向量越"张成"高维空间，即集合越多样。这是从代数几何角度对多样性的精确刻画。

5.2 DPP 数学基础

给定 $n$ 个 item，每个 item 用向量 $\phi_i \in \mathbb{R}^d$ 表示（embedding），定义核矩阵（Kernel Matrix）$L \in \mathbb{R}^{n \times n}$：

其中 $r_i$ 是 item $i$ 的相关性分数（标量），$\phi_i^T \phi_j$ 是归一化后的 item 间余弦相似度，$\alpha$ 是权衡参数。

DPP 定义子集 $Y \subseteq \{1,...,n\}$ 的概率为：

其中 $L_Y$ 是 $L$ 在 $Y$ 对应行列上的子矩阵。

5.3 MAP 推断

MAP 推断是找最大概率子集，即最大化 $\det(L_Y)$（等价于最大化 $\log \det(L_Y)$）。这是 NP-hard 问题，用贪心近似：

利用行列式的 Schur 补公式，加入一个新 item $i$ 后行列式的增量为：

直觉：这个增量等于 item $i$ 在已选集合 $Y$ 的向量空间中的"剩余分量"的长度平方。如果 $i$ 与 $Y$ 中的 item 高度相似（冗余），增量趋近于 0；如果 $i$ 与 $Y$ 正交（多样），增量接近 $L_{ii} = r_i^2$。

5.4 快速 Cholesky 增量算法

暴力计算每次更新 $\det(L_{Y \cup \{i\}})$ 需要 $O(n^3)$，总复杂度 $O(n^3 k)$，工业场景不可接受。Chen et al. 用 Cholesky 分解实现 $O(Mk^2)$ 的快速增量更新（$M$ 为候选集大小，$k$ 为目标选取数量）。

核心思路：维护一个 Cholesky 分解 $L_Y = C_Y C_Y^T$，当加入新 item $i$ 时：

每轮复杂度 $O(Mk)$，总复杂度 $O(Mk^2)$，比暴力快 $O(n^2/k)$ 倍，实际工业场景 $n \gg k$ 时提速明显。

5.5 滑动窗口流式 DPP

工业推荐系统通常是实时流式服务，商品集合每次请求不同。论文提出滑动窗口 DPP：

• 维护一个大小为 $W$ 的历史窗口，窗口内保存已展示 item 的 embedding。
• 新请求来时，先用 DPP MAP 推断在当前候选集中选出多样子集；同时考虑窗口内已展示 item 的冗余度（避免跨次请求重复）。
• 窗口更新：滑出旧 item，滑入新 item，Cholesky 分解做降秩更新（$O(k^2)$）。

这使得系统可以在毫秒级完成 DPP 重排，支持工业级实时服务。

5.6 推荐系统实例：快手/京东商品详情页"猜你喜欢"

DPP 的核心原理：行列式 = 集合的"体积"

核矩阵 L：把"相关性"和"相似度"融合在一起

核矩阵 $L$ 的每个元素同时考虑了两个因素：

大白话翻译：

• $r_i \cdot r_j$：两个商品的相关性分数乘积。如果两个商品本身质量高（分数高），它们之间的连接就更强——这是"鼓励选高质量商品"的部分。
• $\phi_i^T \phi_j$：两个商品的 embedding 余弦相似度。如果两个商品方向相同（相似），连接也更强——但行列式的数学性质会自动惩罚这种强连接（让体积缩小），所以相似商品不会被同时选中。

DPP 的精妙之处：核矩阵把相关性和相似度融合在一起，但行列式会自动惩罚相似度过高的组合——它们会让行列式变小（体积缩小），从而不会被选。

贪心 MAP 推断：每轮选"撑开体积最多的商品"

5.7 分析

6.1 问题背景：CTR 提升但总点击数下降

作者在优化 Feed 流推荐时发现了一个反直觉的现象：把基础模型从 DeepFM 升级为 DeepFMV2 后，CTR 提升了（从 0.0403 提到 0.0428），但用户每次 session 的总点击数反而下降，同时浏览深度（用户滚动到第几条就离开）也缩短了。

这说明：推荐系统应该优化 session 内的累计总点击数，而不是单条的 CTR。这自然引出了强化学习——因为这是一个序列决策问题，当前推什么会影响用户是否继续浏览，进而影响后续能不能再次推荐。

6.2 CTE 优化目标

定义两个核心概念：

• CTR$(u, t, i_t, \mathcal{H}_t)$：用户 $u$ 在位置 $t$ 看到 item $i_t$ 且浏览历史为 $\mathcal{H}_t$ 的条件点击概率。
• PBR$(u, t, i_t, \mathcal{H}_t)$（Position Bounce Rate）：用户在位置 $t$ 离开（bounce）的条件概率。

Session 内总点击数的期望（Click-Through Expectation, CTE）：

逐项理解：

• $\text{CTR}_t$ 是用户在位置 $t$ 点击的概率（前提是他还没离开）。
• $\prod_{k=1}^{t-1}(1 - \text{PBR}_k)$ 是用户能浏览到位置 $t$ 的概率（前 $t-1$ 个位置都没有 bounce）。
• 两者相乘 = 用户在位置 $t$ 实际贡献一个点击的期望。
• 对所有位置求和 = session 内总点击期望 CTE。

6.3 MDP 建模

将推荐过程建模为 MDP $\mathcal{M} = \langle S, A, P, R, \gamma \rangle$：

• 状态 $s_t$：包含用户画像 $u$、候选集 $\mathcal{I}$、已推荐历史 $\mathcal{H}_{t-1}$、当前位置是否 bounce $B(t, i_t)$。
• 动作 $a_t$：从候选集中选下一个要推的 item。
• 奖励 $R(s_t, a_t)$：用户是否点击了 item $a_t$（即 $C(t+1, a_t) \in \{0,1\}$）。
• 状态转移：由 PBR 决定——以概率 $\text{PBR}_{t+1}$ 进入终止状态（用户离开），以概率 $1 - \text{PBR}_{t+1}$ 继续。
• 累计折扣奖励：$G_t = \sum_{t=0}^{T-1} C(t+1, a_t)$（$\gamma = 1$）等于 CTE。

与已有 DRL 推荐工作的关键区别：状态转移由 bounce（离开行为）驱动，而不是用户的点击/评分反馈。这样状态转移在 session 结束时才触发，避免了对每条推荐实时等待用户反馈的需求——这在工业环境的延迟反馈场景下更现实。

6.4 模型架构与训练

策略网络

策略 $\pi_\theta(a|s)$ 由三层网络组成：

• 融合层（Fusion Layer）：用 FM + MLP 生成每个 item $i$ 与用户 $u$ 的交互 embedding $e_i = \text{MLP}(\text{FM}(\hat{u}, \hat{i}))$。
• 编码层（Encoding Layer）：用 RNN（GRU cell）对候选集内所有 item embedding 序列编码，得到包含上下文的隐状态 $h_i^t$——这使得推荐策略能感知"前面已经推了什么"。
• 预测层：对 $h_i^t$ 做 softmax 得到 action 分布 $\pi_\theta(a|s)$，从中采样选出下一个 item。

仿真环境

直接在线训练 RL 代价高昂，因此用离线日志训练一个仿真环境（Simulation Environment, SE），用于预测给定状态下的 CTR 和 PBR。SE 使用 Transformer 编码器（比策略网络的 RNN 更强，离线训练不受限于在线延迟）。策略网络通过与 SE 交互来训练，而不是直接与真实用户交互。

REINFORCE 训练

用 REINFORCE 策略梯度算法：

其中 $G'_t$ 是带基线的累计奖励，用于减少方差。论文对比了两种基线：

• Whitening：用 episode 内的均值和标准差对 return 做归一化，$G'_t = (G_t - \hat{G}) / \sigma_G$。
• Sampled Baseline（推荐）：对同一状态采样 $N$ 条轨迹，用其余 $N-1$ 条的平均 return 作为基线，$G'_{j,t} = G_{j,t} - \frac{1}{N-1}\sum_{b \neq j} G_{b,t}$。

Sampled Baseline 在实验中表现更好，因为它用"同一状态下的多条轨迹"来估计基线，比全局归一化更精确。

6.5 推荐系统实例：快手 Feed 流——MDP 建模与训练全流程

第一步：把推荐问题建模为 MDP

第二步：CTE 目标——为什么不直接优化 CTR？

系统最大化的不是每条视频的点击率，而是整个 session 的总点击数：

大白话拆解：

• $\hat{\text{ctr}}_t$：第 $t$ 条被点击的概率（来自 SE 预测）
• $\prod_{j=1}^{t-1}(1 - \hat{\text{pbr}}_j)$：用户一直留着看到第 $t$ 条的概率（每一步都没退出）
• 两者相乘 = 用户实际能看到并点击第 $t$ 条的期望值
• 对所有位置求和 = session 总点击期望，这就是 CTE

第三步：完整 session 数值演示

Chris 这次 Feed，对比纯 CTR 策略（方案 A）和 RL4CTE 策略（方案 B）推了 5 条视频：

注意：方案 A 的 PBR 随搞笑视频越叠越多不断上升；方案 B 通过穿插萌宠/美食让 PBR 保持低位。

第四步：策略网络三层结构——模型长什么样？（论文 Section 4.1）

第五步：仿真环境 SE——替代真实用户反馈的"环境模型"

这是 on-policy REINFORCE，必须和环境实时交互：策略选一个 action，环境立刻给 reward，再选下一个。但真实用户的 click/bounce 需要时间才回传，而且 on-policy 探索时会推出很差的内容伤害用户体验。SE 解决这个问题：

SE 输出 CTR/PBR → 怎么变成 reward？

SE 对每一步输出两个值后，分三个层级计算：

REINFORCE 更新时对每个位置 $t$ 单独算一次梯度，用 $G_t^j$ 而不是 $G_0^j$：位置 $t$ 的选择只影响 $t$ 之后的结果，用 $G_t^j$ 排除了 $t$ 之前无关的 reward，方差更小。

第六步：多轨迹采样与 Sampled Baseline——这是关键设计

对同一个用户（同一候选集 $\mathcal{I}$），策略网络不只生成 1 条 list，而是采样 N 条不同的 list（每次策略按概率随机采样，得到不同的序列）。这 N 条轨迹共享同一个用户上下文，用于计算 Sampled Baseline：

大白话：第 $j$ 条轨迹第 $t$ 步的"相对收益" = 它的回报 − 其他 $N-1$ 条轨迹在同一步的平均回报。

完整训练循环（Algorithm 1 逐行解读）

6.6 分析

7.1 设计空间全面对比

7.2 方法适用场景对比

7.3 算法复杂度对比

8.1 核心脉络回顾

这五篇工作勾勒出多样性重排领域 20 年来的演进主线：

8.2 未解决的关键问题

8.3 工程实践建议