【王树森推荐系统】重排04：DPP 多样性算法（上）

概述

• DPP 的中文翻译是行列式点过程，机器学习领域很早就有关于 DPP 的研究
• DPP 的目标是从一个集合中选出尽量多样化的物品，这与我们重排的目标非常契合
• DPP 是目前推荐系统领域（2022-11-06）公认最好的多样性算法

超平行体

二维空间的超平行体

• 2 维空间的超平行体就是平行四边形
  

• 平行四边形中的点可以表示为：$x={\alpha }_1{v}_1+{\alpha }_2{v}_2$。下图的红点落在平行四边形的正中心上
  

• 系数 ${\alpha }_1$ 和 ${\alpha }_2$ 的取值范围是 $[0,1]$
  

三维空间的超平行体

• 3 维空间的超平行体是平行六面体
  

• 平行六面体中的点可以表示为：$x={\alpha }_1{v}_1+{\alpha }_2{v}_2+{\alpha }_3{v}_3$

• 系数 ${\alpha }_1,{\alpha }_2,{\alpha }_3$ 的取值范围是 $[0,1]$

数学定义

• 一组向量 $v_1,\cdot \cdot \cdot ,v_k\in R^d$（这些向量是超平行体的边，它们都是 $d$ 维向量） 可以确定一个 k 维超平行体：P(v1,⋅⋅⋅,vk)={α1v1+⋅⋅⋅+αkvk∣0≤α1,⋅⋅⋅,αk≤1}P(v_1,···,v_k)=\{\alpha_1v_1+···+\alpha_kv_k|0 \le \alpha_1,···,\alpha_k\le1\}P(v1​,⋅⋅⋅,vk​)={α1​v1​+⋅⋅⋅+αk​vk​∣0≤α1​,⋅⋅⋅,αk​≤1}
• 要求 $k\le d$，比如 $d=3$ 维空间中有 $k=2$ 维平行四边形，但是在 $d=2$ 维空间不能有 $k=3$ 维的平行六面体
• 如果 $v_1,\cdot \cdot \cdot ,v_k$ 线性相关，则体积 $vol(P)=0$。（例：有 $k=3$ 个向量，落在一个平面上，则平行六面体的体积为 0）

平行四边形的面积

• 两个向量正交：两个向量的点积为 $0$
  
  
  

平行六面体的体积

衡量物品多样性

• 给定 $k$ 个物品，把它们表征为单位向量 $v_1,\cdot \cdot \cdot ,v_k\in R^d(d\ge k)$
• 之前说过最好用 CLIP 学到的图文内容进行表征，这些向量都是 $d$ 维的，$d$ 必须大于等于 $k$。为什么呢？：
  • 三维的空间中可以有二维的平行四边形，但是二维空间却不能有平行六面体
• 用超平行体的体积衡量物品的多样性，体积介于 0 和 1 之间
• 如果 $v_1,\cdot \cdot \cdot ,v_k$ 两两正交（多样性好），则体积最大化，$vol=1$
• 如果 $v_1,\cdot \cdot \cdot ,v_k$ 线性相关（多样性差），则体积最小化，$vol=0$
• 把它们作为矩阵 $V\in R^{d\times k}$
  
• 设 $d\ge k$，行列式和体积满足：
  
• 因此，可以用行列式 $det(V^{T}V)$ 衡量向量 $v_1,\cdot \cdot \cdot ,v_k$ 的多样性