S6.多样性

推荐系统的多样性是指在向用户推荐内容时，不仅考虑用户熟悉和感兴趣的内容，还引入一些新颖和不同的选项，以拓宽用户的视野和体验。多样性的引入可以提升推荐系统的推荐效果，提升用户的满意度，增加用户的黏性。

1 相似性的度量

1.1 基于物品属性标签

根据类⽬、品牌、关键词等，可以根据⼀级类⽬、⼆级类⽬、品牌计算相似度

例子

• 物品i：美妆、彩妆、⾹奈⼉
• 物品j：美妆、⾹⽔、⾹奈⼉
• 相似度: \(\text{sim}_1(i,j)=1, \text{sim}_2(i,j)=0, \text{sim}_3(i,j)=1\)

再根据类⽬、品牌、关键词等设置的权重，加权计算总的相似度

1.2 基于物品向量表征

Warning

用召回的双塔模型学到的物品向量不好

1. 双塔模型学习到的物品向量主要用于与用户向量进行内积计算，用于计算用户对物品的兴趣度。而对于物品之间的相似度计算，双塔模型的物品向量可能没有足够的信息来表示物品之间的相似性。
2. 由于推荐系统的头部现象很严重，新物品/长尾物品曝光和点击很少，双塔模型学不好这些物品的特征。

1.3 基于内容的向量表征

根据cv、nlp等技术，将物品的文本信息和图片信息转化为向量表征，然后计算向量之间的相似度。

1. 难点：如何训练CNN、BERT——CLIP目前公认最有效的预训练方法。
2. 思想：对于图片-文本二元组，预测图文是否匹配。
3. 优势：无需人工标注，对于图文笔记平台，天然包含图片+文字，大部分笔记图文相关。

样本的选取(与batch内负样本类似)

1. 正样本：图片直接对应的文字。
2. 负样本：图片中的那部分。

⼀个batch内有m对正样本，⼀张图⽚和m-1条⽂本组成负样本，那么这个batch内⼀共有m(m-1)对负样本

2 提升多样性的方法

推荐系统的链路

粗排和精排的分数⽤pointwise独⽴打分，不考虑物品之间的关联然后对n个候选物品的打分进⾏排序，后处理就是从这n个候选物品（粗排n为⼏千，精排n为⼏百）选出k个，既要总分⾼，也需要它们有多样性，因此：

• 既要考虑n个候选物品的打分 \(\text{reward}_1,\text{reward}_2,\ldots, \text{reward}_n\)
• 也要考虑n个候选物品之间的相似性 \(\text{sim}(i,j)\)

精排的后处理：通常称为重排，它决定了哪k个物品被曝光，以及k个物品曝光的顺序。

2.1 Maximal Marginal Relevance(MMR)

MMR考虑的是物品之间的相似度

2.1.1 MMR多样性算法

1. 已选中的物品S初始化为空集，未选中的物品R初始化为全集 \({1,\ldots,n}\)
2. 选择精排分数 \(\text{reward}_i\) 最⾼的物品，从R移到S
3. 对（2）操作做k-1轮循环，结束后⼀共选出k个物品。由于每次循环S和R的集合情况都发⽣了变化，因此需要重新计算MR和 \(MMR=\arg_{i\in R} \text{MR}_i\)。

当 \(i\) 和选中物品 \(j\) 相似度很⾼时，对物品 \(i\) 的选中起到抑制作⽤ \(\theta\) 参数⽤来平衡物品价值和相似度，\(\theta\) 越⼤，物品价值起作⽤越多，多样性起作⽤越少。

2.1.2 滑动窗口的引入

已选中的物品越多（集合S越⼤），越不容易找出R中的物品i，使得i与S中的物品都不相似——即 \(\max \text{sim}(i,j)\) 总是约等于1，导致MMR算法失效。

设⼀个滑动窗⼝W，⽐如最近选中的10个物品，⽤W代替MMR公式中的S。采用滑动窗口合理性是：没有必要让第30个物品和第⼀个物品也具有很强的不相似。

2.2 重排的规则

1. 最多连续出现k篇某种笔记

   例如，排i到i+4的全都是图⽂笔记，那么排在i+5的必须是视频笔记。

2. 每k篇笔记最多出现1篇某种笔记

   运营推⼴笔记的精排分数会乘⼀个⼤于1的系数（boost），帮助笔记获得更多曝光例如：为了防⽌boost影响体验，限制每k=9篇笔记最多出现1篇运营推⼴笔记即：如果排在第i位的是运营推⼴笔记，那么排i+1到i+8的不能是运营推⼴笔记。

3. 前t篇笔记最多出现k篇某种笔记

   排名前t篇笔记最容易被看到，对⽤⼾体验最重要（⼩红书的top4为⾸屏）⼩红书推荐系统有带电商卡⽚的笔记，过多可能会影响体验，例如：前t=1篇笔记最多出现k=0篇带电商卡⽚的笔记前t=4篇笔记最多出现k=1篇带电商卡⽚的笔记

2.3 MMR+重排规则

重排结合MMR与规则，在满⾜规则的前提下最⼤化MR。具体做法：每⼀轮先⽤规则排除掉R中的部分物品（防⽌违反规则），得到⼦集 \(R'\)，按下⾯规则计算（公式不变），即可符合要求：

\[ \arg_{i\in R'} \{\theta\cdot\text{reward}_i-(1-\theta)\cdot\max_{j\in W}\text{sim}(i,j)\} \]

2.4 DPP(行列式点过程)

DPP的⽬标：从集合中选出多样的物品，它考虑选出的物品集合的多样性，是公认的最好的推荐系统多样性算法。

2.4.1 DPP算法衡量物品多样性

给定k个物品，把它们表征为单位向量 \(v_1, \ldots, v_k\in \mathbb{R}^d\)，要求 \(d\ge k\)，定义：

\[ \text{vol} = \det(V^TV) \]

由于 \(\text{rank}(V'V)=\text{rank}(V)\) (\(V'Vx=0\) 和 \(Vx=0\) 同解)，因此有：

• \(v_1, \ldots, v_k\) 两两正交，此时体积将最⼤化，vol=1，说明物品之间多样性好
• 如果 \(v_1, \ldots, v_k\) 线性相关，此时体积将最⼩化，vol=0，说明物品之间多样性差。

2.4.2 DDP多样性算法原理

\[ \text{Object} = \arg\max_{S:|S|=k} \theta\cdot(\sum_{j\in S}\text{reward}_j) - (1-\theta)\cdot\log \det(V_S^TV_S) \]

1. 记 \(A_S=V_S'V_S\)，\(A=V'V\) 计算 \(A\) 的复杂度为 \(O(n^2d)\) (n个元素，V中每列维度为d)

暴力算法

计算行列式的时间复杂度 \(O(n^3)\)

假设矩阵为 \(A \in \mathbb{R}^{n \times n}\)，那么每一步：

• 第1步：要将第1列下面的 \(n - 1\) 个元素消成 0，

  • 每次消元要对该行的后 \(n - 1\) 个元素做一次线性变换，
  • 复杂度大约是 \((n - 1)^2\)。(有n-1个，且每一个都是n-1维的线性变换)

• 第2步：对 \(n - 2\) 行、每行大约有 \(n - 2\) 个元素进行操作，

  • 是 \((n - 2)^2\) 次。

• …

• 最后是 \(1^2\)。

所以总的计算量是：

\[ \sum_{k=1}^{n - 1} (n - k)^2 = \sum_{k=1}^{n - 1} k^2 = \frac{(n - 1)n(2n - 1)}{6} = O(n^3) \]

1. 采用贪心算法，初始状态下 \(S\) 只有1个物品(reward最大的物品)，然后每次从 \(R\) 中选择一个物品 \(i\)，使得 Object 最大，将 \(i\) 加入 \(S\) 中，直到 \(S\) 中物品数量达到 \(k\)。
2. 对于单个 \(i\) 计算 \(A_{S\cup i}\) 的行列式需要 \(O(|S|^3)\) ，对于R中的所有物品 \(i\)，计算行列式需要 \(O(|S|^3\cdot|R|)\)，重复上述k次，计算行列式的总时间复杂度为：

\[ \sum _{i=1}^kO(i^3\cdot(n-i))=O（nk^4) \]

一些求和公式

• \(\sum_{i=1}^{k} i^3 = \left( \frac{k(k+1)}{2} \right)^2 = O(k^4)\)
• \(\sum_{i=1}^{k} i^4 = \frac{k(k+1)(2k+1)(3k^2 + 3k -1)}{30} = O(k^5)\)

3. 故暴力破解法的总时间复杂度为： \(O(n^2d+nk^4)\)

Hulu快速算法

Cholesky分解

当矩阵 \(A\) 是对称正定矩阵时，可以对其进行 Cholesky 分解，得到下三角矩阵 \(L\)，使得 \(L L^T = A\)。

因此有 \(A\) 的行列式等于 \(L\) 的对角线元素平方的乘积，即：

\[ \det(A) = \prod_{i=1}^n L_{ii}^2 \]

Block增长：

1. 每轮增加一行一列构建矩阵 \(A_{n+1}\)：

\[ A_{n+1}=\begin{pmatrix} A_n & b\\ b^T & c \end{pmatrix} \]

已知 \(A_n\) 的 Cholesky 分解为 \(L_nL_n'\)，则 \(A_{n+1}\) 的 Cholesky 分解为 \(A_{n+1}=L_{n+1}L_{n+1}'\)：

\[ L_{n+1}=\begin{pmatrix} L_n & 0\\ (L_{n}^{-1}b)^T & \sqrt{c-L_n^TL_n } \end{pmatrix} \]

由于 \(A_{S\cup i}=\begin{pmatrix}V_S'V_S=A& V_S'v_i\\v_i'V_S&v_i'v_i=\alpha\end{pmatrix}\)

因此通过 ¹，每次计算 \(A_{S\cup i}\) 的 Cholesky 分解的时间复杂度为 \(O(n^2d+nk^2)\)

2.4.3 DPP的扩展

⽤上述贪⼼算法的问题：随着集合S增⼤，其中相似物品越来越多，物品向量会趋近线性相关，导致⾏列式趋近为0，对数趋于负⽆穷，因⽽做出如下改进：

1. DPP结合滑动窗口

每次计算 \(A_{S\cup i}\) 的 Cholesky 分解时，只考虑 \(S\) 中最近的 \(k\) 个物品。

2. DPP结合规则

实际推荐系统有很多规则约束，例如最多连续出5篇视频笔记（若已经连续出了5篇视 频笔记，下⼀篇必须是图⽂笔记）因此算法不能从R中选择任意物品，它必须按规则排除掉R中的部分物品，从⽽满⾜规则，得到求解公式：

\[ \arg\max_{i\in \mathcal{R'}}\theta\cdot \text{reward}_i+(1-\theta)\cdot\log\det(A_{\mathcal{W} \cup \{i\}}) \]

Footnotes

1. 陈拉明, 张国欣, 周亦立. Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity[A]. Bengio S, Wallach H, Larochelle H, 等. Advances in Neural Information Processing Systems: Proceedings of the 31st Conference on Neural Information Processing Systems (NeurIPS 2018)[C]. Curran Associates, Inc., 2018.