多样性问题回顾

• 精排给 $n$ 个物品打分：$rewar{d}_1,\cdot \cdot \cdot ,rewar{d}_n$
• $n$ 个物品的向量表征：$v_1,\cdot \cdot \cdot ,v_n\in R^d$，通常是基于图文内容计算出来的向量
• 在精排的后处理阶段（即重排），需要从 $n$ 个物品中选出 $k$ 个物品，组成集合 $S$
  • 价值大：分数之和 ${\sum }_{j\in S}rewar{d}_j$ 越大越好
  • 多样性好：$S$ 中 $k$ 个向量组成的超平行体 $P(S)$ 的体积越大越好
• 集合 $S$ 中的 $k$ 个物品的向量作为列，组成矩阵 $V_S\in R^{d\times k}$
  
• 以这 $k$ 个向量作为边，组成超平行体 $P(S)$
• 体积 $vol(P(S))$ 可以衡量 $S$ 中物品的多样性，多样性越好则体积越大
• 设 $k\le d$，行列式和体积满足：这个公式说明行列式和体积是等价的，因此可以用行列式衡量多样性，多样性越好，则行列式越大
  

行列式点过程（DPP）

• DPP 是一种传统的统计机器学习方法：DPP 要求从 $n$ 个候选物品中选出 $k$ 个组成集合 $S$，使得行列式的对数最大化
• 严格来说这个公式叫 K-DPP，在这里不做区分
  
• Hulu 的论文将 DPP 应用在推荐系统：现在工业界的推荐系统大多是用类似的方法，左边的项越大，表示越符合用户的兴趣，右边的项越大，表明多样性越好
  
  
• 设 $A$ 为 $n\times n$ 的矩阵，它的元素 $(i,j)$ 元素为 $a_{ij}=v_i^T{v}_j$
• 给定向量 $v_1,\cdot \cdot \cdot ,v_n\in R^d$，需要 $O(n^{2}d)$ 时间计算 $A$
• $A_S=V_S^T{V}_S$ 为 $A$ 的一个 $k\times k$ 子矩阵。如果 $i,j\in S$，则 $a_{ij}$ 是 $A_S$ 的一个元素

• DPP 是个组合优化问题，从集合 {1,⋅⋅⋅,n}\{1,···,n\}{1,⋅⋅⋅,n} 中选出一个大小为 $k$ 的子集 $S$

• 精确求解 DPP 是不可能的，因为 DPP 是一个 NP-Hard 问题

• 用 $S$ 表示已选中物品，用 $R$ 表示未选中物品，贪心算法求解：我们希望添加的物品 $i$ 让行列式尽量大，物品 $i$ 不能和集合中的任何物品相似，不然会让行列式接近 0
  

• 总结贪心算法每轮选择一个物品 $i$，这个物品不仅要有较高的价值，还不能和已经选中的物品相似

求解 DPP

暴力算法

• 贪心算法求解：
  
• 对于集合 $R$ 中的所有物品 $i$ ，我们都得计算这样的行列式，算法的难点就在计算行列式，简单粗暴计算行列式计算量会非常大
  
• 对于单个 $i$，计算 AS∪{i}A_{S \cup \{i\}}AS∪{i}​ 的行列式需要 $O(|S{|}^3)$ 时间。想要计算行列式，需要对矩阵 $A_S$ 做特征分解，时间复杂度都是 $O(|S{|}^3)$
• 对于所有的 $i\in R$，计算行列式需要时间 $O(|S{|}^3\cdot |R|)$，做了那么多计算，只能从 $R$ 中选出一个物品
• 需要求解上式 $k$ 次才能选出 $k$ 个物品。如果暴力计算行列式，那么总时间复杂度为：$O(|S{|}^3\cdot |R|\cdot k)=O(n{k}^4)$，其中 $S$ 的大小不超过 $k$，$R$ 的大小不超过 $n$
• 暴力算法的总时间复杂度为：$O(n^{2}d+n{k}^4)$，其中 $O(n^{2}d)$ 是计算矩阵 $A$ 的时间，$n{k}^4$ 是计算行列式的时间，$n$ 的量级是几百，$k$ 和 $d$ 的量级都是几十。这个时间复杂度看起来 ok，但是其实不可行，推荐系统留给多样性算法的时间也就十毫秒左右，这个算法太慢了

Hulu 的快速算法

• Hulu 的论文设计了一种数值算法，仅需 $O(n^{2}d+n{k}^2)$ 的时间从 $n$ 个物品中选出 $k$ 个物品
• 给定向量 $v_1,\cdot \cdot \cdot ,v_n\in R^d$，需要 $O(n^{2}d)$ 时间计算 $A$
• 用 $O(n{k}^2)$ 时间计算所有行列式（有效利用 Cholesky 分解避免大部分计算）
• Cholesky 分解 $A_S=L{L}^T$（$A_S$ 为对称半正定矩阵），其中 $L$ 是下三角矩阵（对角线以上的元素全零）
• Cholesky 分解可供计算 $A_S$ 的行列式
  • 下三角矩阵 $L$ 的行列式 $det(L)$ 等于 $L$ 对角线元素乘积
  • $A_S$ 的行列式为 $det(A_S)=det(L{)}^2={\prod }_i{l}_{ii}^2$
• 已知 $A_S=L{L}^T$，则可以快速求出所有 AS∪{i}A_{S \cup \{ i \}}AS∪{i}​ 的 Cholesky 分解，因此可以快速算出所有 AS∪{i}A_{S \cup \{i \}}AS∪{i}​ 的行列式
• 思想在于：已知矩阵 $A_S$ 的 Cholesky 分解，那么给 $A_S$ 添加一行或一列，不需要重新算一遍 Cholesky 分解，否则代价很大。给矩阵添加一行或一列，Cholesky 的代价非常小，有办法快速算出变化的地方，这样就不用完整算一遍 Cholesky 分解，这样就可以快速算出行列式

Hulu算法总结

• 每一轮求解这个问题，选出物品 $i$。求解的难点在蓝色框，需要算这个行列式，如果暴力计算行列式代价非常大，Hulu算法降低了计算行列式的代价，使得 DPP 可以被用在推荐系统中，哪怕只给十毫秒的时间
  
• 初始 $S$ 中只有一个物品，$A_S$ 是 $1\times 1$ 的矩阵
• 每一轮循环，基于上一轮算出的 $A_S=L{L}^T$，快速求出 AS∪{i}A_{S \cup \{i\}}AS∪{i}​ 的 Cholesky 分解 $(\forall i\in R)$，从而求出 logdet(AS∪{i})logdet(A_{S \cup \{i\}})logdet(AS∪{i}​)

DPP 的扩展

滑动窗口

• 用 $S$ 表示已选中的物品，用 $R$ 表示未选中的物品，DPP 的贪心算法求解：
  
• 随着集合 $S$ 增大，其中相似物品越来越多，物品向量会趋于线性相关
• 行列式 $det(A_S)$ 会坍缩到零，对数趋于负无穷，此时 DPP 失效
• 我们使用 $W$，即最近选中的物品代替 $S$，不考虑更前面的，新选中的物品只需要考虑与滑动窗口的相似性即可

规则约束

• 有很多规则约束，例如最多连续出 5 篇视频笔记（如果已经连续出了 5 篇视频笔记，下一篇必须是图文笔记）
• 有了这些规则便不能任意选择物品，而要选择符合规则约束的物品
  
• 用规则排除掉 $R$ 中的部分物品，得到子集 $R^{\prime }$，然后求解：区别在于只在 $R^{\prime }$ 中选择