推荐算法丨物品多样性

Posted on

在做推荐时，除了考虑用户是否对物品感兴趣，还要考虑推荐物品的多样性。如果多样性做得好，可以显著提升推荐系统的核心业务指标。因此，在做完精排后，还需要结合物品的多样性指标进行重排，以选出最终的推荐物品。

物品相似性有两种度量方法：

  • 基于物品属性标签，例如根据一级类目、二级类目、品牌计算相似度：
    • 物品i：美妆、彩妆、香奈儿
    • 物品j：美妆、香水、香奈儿
    • 相似度：
    • 对三个相似度求加权和，权重由人为规定
  • 基于物品向量表征
    • 使用基于内容的向量表征。利用nlp和cv算法提取物品特征。可以使用CLIP方法。
    • 不使用双塔模型学到的物品向量，因为推荐系统头部现象很严重，曝光和点击都集中在少数物品，双塔模型学不好新物品和长尾物品的向量表征。

在推荐的链路上，在粗排和精排的后处理阶段，综合排序模型打分和多样性分数做选择。

  • 粗排和精排用多目标模型对物品做pointwise打分。
  • 对于物品i，模型输出点击率、交互率的预估，融合成分数。
  • 后处理阶段从n个物品选出k个，既要求总分高，也需要有多样性。

MMR

Maximal Marginal Relevance (MMR)来自于搜索算法，根据精排打分和物品相似度，从 n 个物品中选出 k 个价值高、且多样性好的物品。

MMR多样性算法的步骤如下：

  • 已选中的物品S初始化为空集，未选中的物品R初始化为全集{1,···,n}。

  • 选择精排分数最高的物品，从集合R移到S。

  • 做k-1轮循环：

    • 计算未选中物品集合R中所有物品的分数。，其中：

    • 选出分数最高的物品，将其从R移到S。

DPP

行列式点过程 (determinantal point process, DPP) 是一种经典的机器学习方法，是目前推荐系统重排多样性公认的最好方法。

超平形体

一组向量可以确定一个k维超平行体：

  • 要求k≤d，比如d=3维空间中有k=2维平行四边形。

  • 如果v_1,···,v_k线性相关，则体积vol(P)=0。

我们可以借助k维超平行体的体积来衡量物品多样性：

  • 给定k个物品，把他们表征维单位向量（）。
  • 用超平行体的体积衡量物品的多样性，体积介于0和1之间。
  • 如果k个单位向量两两正交，则体积最大化，vol=1。

关于k维超平行体的体积，有如下计算方法：

  • 将k个向量作为矩阵的列向量。
  • 若d≥k，则行列式与体积满足：

行列式点过程DPP

基于以上原理，DPP用行列式来衡量物品多样性，其目标函数可写为： Hulu的论文将DPP应用在推荐系统，使用物品相似度来调节物品得分： 我们令k×k矩阵。设A为n×n矩阵，它的(i,j)元素为。给定向量，需要的时间计算A。为A的一个子矩阵。如果i,j∈S,则是的一个元素。那么，DPP得分可以写成： DPP是个组合优化问题，要求从{1,···,n}中选出一个大小为k的子集S。通常用贪心算法来近似求解DPP。用S表示已选中的物品，R表示未选中的物品，则每一轮从R中选择一个物品i，满足： 也就是说，我们所选择的i，既要价值尽可能高，又要使i加入后物品多样性尽可能高。

但是，要求解这个问题需要计算行列式很多次，而计算行列式需要矩阵分解，代价很大。

  • 对于单个i，计算的行列式需要时间。
  • 对于所有的i∈R，计算行列式需要时间。
  • 我们需要选出k个物品，因此复杂度为。
  • 计算矩阵A的时间复杂度为，因此总时间复杂度为

Hulu的论文设计了一种数值算法，仅需的时间就可以从n个物品挑选出k个物品：

  • Cholesky分解，其中L是下三角矩阵。
  • 的行列式为。
  • 已知，则可以快速求出所有的Cholesky分解，进而求出其行列式。

滑动窗口

在MMR中，我们每一轮都要选出一个物品i，使得： 这里的S指已选中物品的集合。当|S|很大时，很难找出物品i与S中的物品不相似了。即当|S|很大时，相似性sim(i,j)总是约等于1，导致MMR方法失效。

可以使用滑动窗口：设置一个滑动窗口W，比如最近选中的10个物品，用W代替MMR公式中的S： 这种方案下，只考虑最近选中的物品，要求距离较近的物品相似度低，而距离较远的物品相似度可以较高。这也符合实践的需要，当间隔较远时，物品相似度高并不会影响用户体验。

同样的，滑动窗口也可以应用到DPP，使用最近选中物品集合W代替S：

业务规则约束

在实际业务中往往有很多规则应用在重排阶段，这些规则和MMR、DPP等算法结合来满足用户的多样性体验。以小红书为例，可能会出现以下规则：

  • 最多连续出现k篇某种笔记（如图文笔记、视频笔记）。
  • 每k篇笔记最多出现1篇某种笔记（如运营推广笔记）。
  • 前t篇笔记最多出现k篇某种笔记（小红书前4篇笔记为首屏，更容易被用户看到）。

这些业务规则可以和MMR和DPP结合，每一轮都先用规则排除掉R中的部分物品，从剩下的物品中做选择。例如前k篇笔记都是图文笔记，那么下一篇笔记要把图文笔记都排除掉。