Kinnari's Blog

推荐系统——重排

3 min
NOTE

这是 b 站王树森推荐系统课程的笔记，记录到了重排，之后的物品冷启动和提分部分我没有学，所以也没有笔记。索引如下：

在粗排、精排每个步骤之后，需要将提取出来的物品进行排序，既需要质量高，又需要多样性好（注意粗排之后也需要）。

怎么突然联想到国外招生的 diversity 要求了（

对图文笔记形式的物品，可以使用 CLIP 模型计算相似度，从而估计多样性。

Maximal Marginal Relevance (MMR) 算法

有 nn 个物品，打分为 r1,r2,…,rnr_{1},r_{2},\dots,r_{n}，物品 i,ji,j 的相似度为 sim(i,j)\text{sim}(i,j)

这 nn 个物品中选出的物品集合为 S\mathcal{S}，未选中的物品集合为 R\mathcal{R}，计算 R\mathcal{R} 中每一个物品的 marginal relevance 分数：

MRi=θ⋅ri−(1−θ)⋅max⁡j∈Ssim(i,j)\text{MR}_{i} = \theta \cdot r_{i} - (1-\theta)\cdot \max_{j\in \mathcal{S}} \text{sim}(i,j)

θ\theta 为超参，选择使 MRi\mathrm{MR}_{i} 最大的物品从 R\mathcal{R} 放入 S\mathcal{S}，反复进行这个操作，直到选出需要数量的物品。

缺点：当 S\mathcal{S} 非常大时，最大相似性 max⁡j∈Ssim(i,j)\max_{_{j\in \mathcal{S}}}\mathrm{sim}(i,j) 会很大（接近 11），导致算法退化，多样性变差。可以使用滑动窗口，即使用最近选入的若干物品集合代替全集 S\mathcal{S}（可以理解为离得远的物品可以相似，因为用户感觉不到这种相似性）。

可以对 S\mathcal{S} 进行一些规则筛选，以适合具体业务

DPP 算法

给定 kk 个物品，表征为单位向量 v1,v2,…,vk∈Rd,d≥kv_{1},v_{2},\dots,v_{k}\in \mathbb{R}^{d},d\geq k，作为矩阵 V∈Rd×kV\in \mathbb{R}^{d\times k} 的列，可以计算这些向量构成超平行 dd 维体的体积 vol(P(v1,…,vk))\text{vol}(\mathcal{P}(v_{1},\dots,v_{k})) 来衡量多样性，而

det⁡(V⊤V)=vol(P(v1,…,vk)2\det(V^{\top}V) = \text{vol}(\mathcal{P}(v_{1},\dots,v_{k})^{2}

故可以通过计算行列式来衡量多样性，目标函数：

arg⁡max⁡S:∣S∣=klog⁡det⁡(VS⊤VS)\arg\max_{\mathcal{S}:\lvert \mathcal{S} \rvert =k} \log \det(V_{\mathcal{S}}^{\top}V_{\mathcal{S}})

应用在 MMR 算法上，就是：

arg⁡max⁡S:∣S∣=kθ⋅(∑j∈Srj)+(1−θ)⋅log⁡det⁡(VS⊤VS)\arg\max_{\mathcal{S}:\lvert \mathcal{S} \rvert =k} \theta \cdot\left( \sum_{j\in \mathcal{S}}r_{j} \right) + (1-\theta)\cdot \log \det(V_{\mathcal{S}}^{\top}V_{\mathcal{S}})

记 AS=VS⊤VSA_{\mathcal{S}}=V_{\mathcal{S}}^{\top}V_{\mathcal{S}}，则 aij=vi⊤vja_{ij}=v_{i}^{\top}v_{j}，使用贪心寻找下一个物品：

arg⁡max⁡i∈Rθ⋅ri+(1−θ)⋅log⁡det⁡(AS∪{i})\arg\max_{i\in \mathcal{R}} \theta \cdot r_{i} + (1-\theta)\cdot \log \det(A_{\mathcal{S}\cup \{ i \}})

（为了快速求解这个式子有很多数学推导，这里就不记录了）

推荐系统