推荐系统入门九 · 重排 MMR DPP

物品相似度度量

1、基于物品标签，如类目、品牌、关键词等。

2、基于物品向量表征，比较两个物品余弦相似度。注意，用召回的双塔模型学到的物品向量，就不适合做物品相似性表征。而基于CV/NLP提取图文内容的向量表征就很好。

基于物品标签计算相似度：比如有3级类目，以此比较两个物品各级类目，相同的+1，不同的+0，最后对每级类目加权相加计算相似度。

基于物品向量表征计算相似度：由于召回的双塔模型中，热门物品跟冷门物品存在2/8法则，对于新物品比较相似度，无法解决长尾问题。因此，通常使用CNN提取文章图片向量，BERT 提取文章内容向量，两个向量concatenation成一个向量。而BERT需要标注，因此产生新的解决方案 CLIP 。

CLIP 是公认最有效的基于图文内容的物品向量表征最有效的预训练方法。CLIP 是对图片/文本二元组，预测图文是否匹配。优势是无需人工标注。

推荐系统链路中，后处理主要是提升多样性。后处理，需要从n个候选物品中选出 同时兼顾高精排分数和多样性的 TopK。

MMR 多样性算法

Maximal Marginal Relevance

精排给n个候选物品打分，融合后分数为 reward₁, ..., reward_n。把第 i 和第 j 个物品相似度记作 sim(i, j)。从 n 个候选物品中选出k个，既要有高精度排分数，也要有多样性。

MMR计算流程：

1. 将待选的n个物品装入集合R，集合R表示未选中物品集合。创建一个空集合S，表示已选择物品
2. 使用精排给物品打分，记作 reward_i。表示物品i价值，即用户对物品i的价值。
3. max sim(i, j) 计算未选中物品i与已选择物品j相似度，并取最大化j，得到物品i多样性分数。如上公式，若未选中物品与已选中物品相似度越高，则越不利于被选中，有利于推荐物品多样性。
4. θ ∈ (0, 1)，平衡物品价值与多样性。θ越大，则物品价值对排序影响越大，多样性影响越小。
5. MMR 就是对 MR 分数求最大化，每一轮都需要计算未选中物品集合R中所有MR分数，将MR最高分移入已选中物品集合S。因为集合S变动，sim(i, j) 每一轮都不同，因此每一轮都需要重新对R集合全量计算MR分数。

MMR 滑动窗口：

MR分数依赖于集合S，而若集合S数量越大，则未选中物品越可能与集合S中某个物品相似度接近，即 sim(i, j) 接近于最大值（一般sim 取 [0, 1]，也就是接近1）。集合S数量越大，则后续MR分数就会失真，MMR算法失效。

对此，可以设置一个滑动窗口W，即从集合S中选取最新w个物品，用W来代替S即可。

重排规则

重排规则指人为对推荐排序做一些限制，比如限制图文视频推荐内容比例、限制营销内容比例等。推荐算法通常结合MMR和重排规则来排序，规则优先级大于MR得分。通常做法是，MMR每一轮计算出未选中物品的MR排名后，根据规则来过滤掉不符合规则的物品，如第4篇内容不能是营销内容，而MR最高分却是营销内容，那么就应该从MR次高分看是否符合规则……以此过滤。

常见重排规则：

• 图片视频内容，最多连续出现x篇图片内容，或最多连续出现x篇视频内容。
• 运营推广笔记精排分数会乘以大于1的系数（即boost），限制每y篇内容最多出现1篇运营推广笔记。
• 用户首次进入APP前t篇内容，最多出现m篇运营推广或其他特定类型的内容。

DDP 行列式点过程

DDP是目前公认最好推荐算法，其产生于70年代。

del(V_s^TV_s) 指集合S中k个物品向量行列式，k≤d时，等价于这些向量组成的超平形体体积，记作 A_s (k*k) 。

设A为n*n矩阵，其元素a_ij = v_i^Tv_j。给定向量v₁,..., v_k ∈ R^d，d 表示维度，则需要O(n²d)时间计算A。

A_s = V_s^TV_s 为A的一个k*k子矩阵。如果i,j∈S，则a_ij 是A_s的一个元素。

使用贪心算法，优化DDP结果。

暴力算法总时间复杂度是：O(n²d + nk⁴)。

DPP Hulu 解法

Hulu 论文在于优化了DPP算法时间复杂度，仅需O(n²d + nk²) 时间即可从n个物品中选出k个物品。O(n²d) 计算矩阵A是必须的，利用Cholesky分解来计算A所有子行列式。

Cholesky 分解

将矩阵转化为三角矩阵，即 A_S = LL^T，L^T 读作L转置，L是下三角矩阵（对角线以上全为0）。下三角矩阵L的行列式 det(L) 等于L对角线元素乘积。A_S 的行列式为 det(A_S) = det(L)² = ∏_il_ii²。

已知 A_S = LL^T，则可快速求出所有 A_S∪{i} 的Cholesky分解，继而快速求出其行列式。

Cholesky 分解优化DPP暴力算法

Cholesky 分解优化的是DPP算法中 log det(A_S∪{i}) 部分时间复杂度。初始时已选择物品集合 S 只有1个物品向量，A_S是1*1矩阵。

每一轮循环，基于上一轮算出的A_S = LL^T，快速求出A_S∪{i}的Cholesky分解(∀i ∈ R，即所有i属于R)，从而求出 log det(A_S∪{i}A_S∪{i})。

使用Hulu论文 + 滑动窗口 + 推荐规则，来优化推荐算法结果。

超平形体

已知两个向量 v₁, v₂ 可以确定唯一平行四边形。该平行四边形中任意点，都可表示为 x = α₁v₁ + α₂v₂。

如该平行四边形对角点 x = 1*v₁ + 1*v₂ = v₁ + v₂

三维空间超平形体是平行六面体，即不在同一平面的三个向量，可以确定唯一平行六面体。不在同一平面的向量，指向量不相关，即所有向量不能用其中一个向量表示。

如何根据向量，计算平行四边形面积、平行六面体体积。可以通过向量投影计算。

当 v₁, v₂, v₃ 三个向量正交时，平行六面体体积最大。而当三个向量线性相关时，三个向量处于同一平面，即v₃ 可以表示为v₁, v₂组合，此时体积最小，为0。

使用超平形体体积公式来衡量物品多样性

设超平形体体积介于0和1之间，给定k个物品表征为单位向量 v₁,..., v_k ∈ R^d (d ≥ k)，d 表示维度。若物品向量两两正交（多样性好），则体积最大化, vol = 1。若物品全部线性相关，则体积最小（没有多样性），vol = 0。

如果把向量 v₁,..., v_k 作为矩阵 V 的列，每个向量有d维参数。则行列式和体积是等价的，可以用行列式表示体积，以此来表示物品多样性。