摘要

行列式点过程 (DPP) 是一种优雅的排斥概率模型，可应用于各种机器学习任务，包括摘要和搜索。然而，在许多应用中发挥重要作用的 DPP 的最大后验 (MAP) 推理是 NP 困难的，即使是流行的贪心算法在计算上仍然过于昂贵，无法在大规模实时场景中使用。为了克服计算挑战，在本文中，我们提出了一种新算法来大大加速 DPP 的贪婪 MAP 推理。此外，我们的算法还适应仅在结果序列中邻近的少数项之间需要斥力的场景。我们应用所提出的算法来生成相关且多样化的推荐。实验结果表明，我们提出的算法比最先进的竞争对手要快得多，并且在多个公共数据集上提供了更好的相关性-多样性权衡，这也在在线 A/B 测试中得到了证实。

引言

行列式点过程（DPP）首次在[33]中引入，用于给出热平衡状态下费米子系统的分布。 DPP 精确地描述了费米子的排斥力，因此可以自然地对多样性进行建模。除了其在量子物理和随机矩阵[35]中的早期应用之外，它最近还被应用于各种机器学习任务，例如多人姿势估计[27]、图像搜索[28]、文档摘要[29]、视频摘要[19]、产品推荐[18]和推文时间线生成[49]。与图模型等其他概率模型相比，DPP 的一个主要优点是它允许多项式时间算法进行多种类型的推理，包括调节和采样 [30]。

一个例外是重要的最大后验（MAP）推理，即找到概率最高的项目集，这是 NP 难的[25]。因此，优选计算复杂度低的近似推理方法。 [17]中提出了一种近乎最优的 DPP MAP 推理方法。然而，该算法是一种基于梯度的方法，在每次迭代中评估梯度的计算复杂度很高，这使得它对于大规模实时应用来说不切实际。另一种方法是广泛使用的贪婪算法[37]，其合理性在于 DPP 中集合的对数概率是子模的。尽管其理论保证相对较弱[13]，但由于其有希望的实证表现而被广泛使用[29,19,49]。贪婪算法 [17, 32] 的已知精确实现具有 $O\left(M^{4}\right)$ 复杂度，其中 $M$ 是项目总数。 Han 等人最近的工作 [20] 通过引入一些近似值，将复杂性降低到 $O\left(M^{3}\right)$，但这会牺牲准确性。在本文中，我们提出了一种复杂度为 $O\left(M^{3}\right)$ 的贪婪算法的精确实现，并且根据经验，它的运行速度比近似算法 [20] 快得多。

描述普通的DDP在解决MAP这类np困难问题时算法复杂度过大

DPP 的基本特征是它为彼此具有差异性的项目集分配更高的概率[30]。在某些应用中，所选项目显示为序列，并且负面交互作用仅限于附近的几个项目之间。例如，当向用户推荐一长串项目时，每次只有该序列的一小部分引起用户的注意。在这种情况下，要求彼此远离的项目具有多样性是没有必要的。针对这种情况开发快速算法是本文的另一个动机。

Contributions. 在本文中，我们提出了一种新颖的算法来大大加速 DPP 的贪婪 MAP 推理。通过增量更新 Cholesky 因子，我们的算法将复杂度降低至 $O\left(M^{3}\right)$，并在 $O\left(N^{2} M\right)$ 时间内运行返回$N$项，可用于大规模实时场景。据我们所知，这是第一次以如此低的时间复杂度精确实现 DPP 贪婪 MAP 推理。

此外，我们还使我们的算法适应仅在滑动窗口内需要多样性的场景。假设窗口大小为$w<N$，则复杂度可以降低到$O(w N M)$。这一特性使其特别适合我们需要在短滑动窗口内多样化的长序列项目的场景。

最后，我们将我们提出的算法应用于推荐任务。推荐多样化的项目为用户提供了发现新颖和偶然项目的探索机会，也使服务能够发现用户的新兴趣。正如公共数据集和在线 A/B 测试的实验结果所示，与已知方法相比，基于 DPP 的方法在相关性和多样性之间具有良好的权衡。

• 加速 DPP 的贪婪 MAP 推理
• 滑动窗口内多样性的场景
• 算法应用于推荐任务，结果优秀

背景与相关工作

Notations. 集合用大写字母表示，如$Z$，$\#Z$表示$Z$中元素的个数。向量和矩阵分别用粗体小写字母和粗体大写字母表示。 $(\cdot)^{\top}$ 表示参数向量或矩阵的转置。 $\langle\mathbf{x}, \mathbf{y}\rangle$ 是两个向量 $\mathbf{x}$ 和 $\mathbf{y}$ 的内积。给定子集 $X$ 和 $Y，\mathbf{L}_{X, Y}$ 是 $\mathbf{L}$ 的子矩阵，行中按 $X$ 索引，列中按 $Y$ 索引。为了符号简单起见，我们设 $\mathbf{L}_{X, X}=\mathbf{L}_{X}, \mathbf{L}_{X,\{i\}}=\mathbf{L} _{X,i}$ 和 $\mathbf{L}_{\{i\},X}=\mathbf{L}_{i,X}$ 。$\operatorname{det}(\mathbf{L} )$是 $\mathbf{L}$ 的行列式，并且按照惯例 $\operatorname{det}\left(\mathbf{L}_{\empty}\right)=1$。

行列式点过程

DPP 是一种优雅的概率模型，能够表达负面交互作用 [30]。形式上，离散集 $Z=\{1,2, \ldots, M\}$ 上的 DPP $\mathcal{P}$ 是 $2^{Z}$（ 的所有子集的集合）上的概率测度Z。当 $\mathcal{P}$ 对空集给出非零概率时，存在一个矩阵 $\mathbf{L} \in \mathbb{R}^{M \times M}$ 使得对于每个子集 $Y \subseteq Z$，$Y$的概率为$\mathcal{P}(Y) \propto \operatorname{det}\left(\mathbf{L}_{Y}\right)$，其中$\mathbf{L}$ 是一个实数正半定 (PSD) 核矩阵，由 $Z$ 的元素索引。在此分布下，许多类型的推理任务（包括边缘化、条件化和采样）都可以在多项式时间内执行，但 MAP 推理除外。

选择子集$Y$的概率正比于其行列式大小：

矩阵可以看着是一组向量的集合，而矩阵的行列式的物理意义为矩阵中的各个向量张成的平行多面体体积的平方。这些向量彼此之间越不相似，向量间的夹角就会越大，张成的平行多面体的体积也就越大，矩阵的行列式也就越大，对应的商品集合的多样性也就越高。当这些向量彼此正交的时候，多样性达到最高。

在某些应用中，我们需要对 $Y$ 施加基数约束，以最高概率返回固定大小的子集，从而产生 $k$-DPP [28] 的 MAP 推断。

比如推荐重排过滤出固定大小的子集

除了第 11 节中介绍的 DPP MAP 推断的工作之外，其他一些工作建议抽取样本并返回概率最高的样本。在[16]中，当$\mathbf{L}$的特征分解可用时，提出了一种复杂度为$O\left(N^{2} M\right)$的快速采样算法。尽管[16]和我们的工作都旨在加速现有算法，但方法本质上是不同的：我们依赖于增量更新 Cholesky 因子。

推荐多样性

提高推荐多样性一直是机器学习和信息检索中的一个活跃领域。一些作品在通用环境中解决了这个问题，以实现任意相关性和相异性函数之间的更好权衡[11,9,51,8,21]。然而，他们仅使用成对的差异来表征列表的整体多样性属性，这可能无法捕获项目之间的一些复杂关系（例如，一个项目的特征可以描述为另外两个项目的简单线性组合）。其他一些工作试图构建新的推荐系统以通过学习过程促进多样性[3,43,48]，但这使得算法不太通用并且不适合直接集成到现有的推荐系统中。

一些工作提出根据分类信息定义相似性度量[52,2,12.45,4,44]。然而，语义分类信息并不总是可用，并且基于它们定义相似性可能不可靠。其他几项工作提出基于解释[50]、聚类[7,5,31]、特征空间[40]或覆盖范围[47,39]来定义多样性度量。

在本文中，我们应用 DPP 模型和我们提出的算法来优化相关性和多样性之间的权衡。与基于成对差异的现有技术不同，我们的方法定义了整个子集的特征空间中的多样性。请注意，我们的方法与现有的基于 DPP 的推荐方法本质上不同。在[18,34,14,15]中，他们提出向购物篮中的产品推荐互补产品，关键是学习DPP的核矩阵来表征物品之间的关系。相比之下，我们的目标是通过 MAP 推理生成相关且多样化的推荐列表。

我们论文中考虑的多样性与[1, 38]中的总体多样性不同。当多样性改善更偏向于差异化每个推荐列表中的项目时，增加总体多样性会促进长尾项目。

Fast Greedy MAP推理

在本节中，我们将介绍 DPP 贪婪 MAP 推理算法的快速实现。在每次迭代中，项目

每次选择使$\log \operatorname{det}\left(\mathbf{L}_{Y_{\mathrm{g}} \cup\{i\}}\right)-\log \operatorname{det}\left(\mathbf{L}_{Y_{\mathrm{g}}}\right)$最大化的i（这里的i需要排除已经选的，也就是从剩下未选的中挑选）

添加到 $Y_{\mathrm{g}}$。由于 $\mathbf{L}$ 是一个 PSD 矩阵，因此它的所有主要次要矩阵也是 PSD。假设 $\operatorname{det}\left(\mathbf{L}_{Y_{\mathrm{g}}}\right)>$0 ，并且 $\mathbf{L}_{Y_{\mathrm {g}}}$ 的 Cholesky 分解 是 $\mathbf{L}_{Y_{\mathrm{g}}}=\mathbf{V}\mathbf{V}^{\top}$，其中 $\mathbf{V}$ 是可逆下三角矩阵。对于任何 $i\in Z\backslash Y_{\mathrm{g}}$，$\mathbf{L}_{Y_{\mathrm{g}}\cup\{i\}}$ 的 Cholesky 分解可以为派生为

Cholesky分解是将Hermitian正定矩阵分解为下三角矩阵及其共轭转置的乘积。

其中行向量 $\mathbf{c}_{i}$ 和标量 $d_{i} \geq 0$ 满足

矩阵乘法

此外，根据等式(3) ，可得

矩阵行列式性质$\displaystyle \begin{vmatrix} A&B\\ 0&D \end{vmatrix}=(\det A)(\det D)$

 

因此， (2) 相当于

$\operatorname{det}\left(\mathbf{L}_{Y_{\mathrm{g}}}\right)$被消去

一旦等式(6)被求解，等式(3)的 $\mathbf{L}_{Y_{g} \cup\{j\}}$ 的 Cholesky 分解为

j求出来了，并加入了被选择矩阵

其中 $\mathbf{c}_{j}$ 和 $d_{j}$ 很容易获得。因此，在将新项添加到 $Y_{\mathrm{g}}$ 后，$\mathbf{L}_{Y_{g}}$ 的 Cholesky 因子可以有效更新。

对于每个项目 $i，\mathbf{c}_{i}$ 和 $d_{i}$ 也可以增量更新。在等式(6)被求解后，定义 $\mathbf{c}_{i}^{\prime}$ 和 $d_{i}^{\prime}$ 为新的需求求解的向量和标量，其中

$i \in Z \backslash\left(Y_{\mathrm{g}} \cup\{j\}\right)$。根据等式(4)和等式(7)，我们有：

通过将等式(4)和等式(8)组合，我们推导出

$\mathbf{c}_{i}^{\prime}$的增量更新公式

等式(4)意味着：

$d_{i}^{\prime 2}$增量更新

最初，$Y_{\mathrm{g}}=\emptyset$，并且方程。 (5) 意味着$d_{i}^{2}=\operatorname{det}\left(\mathbf{L}_{i i}\right)=\mathbf{L}_{i i}$。完整的算法总结在算法 1 中。 对于无约束 MAP 推理，停止标准是 $d_{j}^{2}<1$ ，或者当施加基数约束时 $\# Y_{\mathrm{g}}>N$ 。对于后一种情况，我们引入一个小数 $\varepsilon>0$ 并将 $d_{j}^{2}<\varepsilon$ 添加到计算 $1 / d_{j}$ 的数值稳定性的停止标准中。

在第 $k$ 次迭代中，对于每个项目 $i \in Z \backslash Y_{\mathrm{g}}$，更新 $\mathbf{c}_{i}$ 和 $d_{i}$ 涉及两个长度为 $k$ 的向量的内积，导致整体复杂度为 $O(k M)$。因此，算法 1 运行 $O\left(M^{3}\right)$ 时间进行无约束 MAP 推理，并在 $O\left(N^{2} M\right)$ 时间内返回 $N$ 个项目。请注意，这是通过给$\mathbf{c}_{i}$ 和 $d_{i}$.额外的$O(N M)$ (对于无约束条件 $O\left(M^{2}\right)$）空间得到的。

滑动窗口内的多样性

在一些应用中，选定的项目集显示为序列，并且仅在滑动窗口内需要多样性。将窗口大小表示为 $w$。我们修改公式(2)

其中 $Y_{\mathrm{g}}^{w} \subseteq Y_{\mathrm{g}}$ 包含 $w-1$ 最近添加的项目。当$\# Y_{\mathrm{g}} \geq w$时，对方法[32]进行简单修改即可解决(11) 复杂度为$O\left(w^{2} M\right)$。我们调整我们的算法以适应这种情况，以便选择。 [10] 可以在 $O(w M)$ 时间内解决。

在第 3 节中，我们展示了当 $\mathbf{V}、\mathbf{c}_{i}$ 和 $d_{i}$ 可用时如何有效地选择新项目。对于公式(10) $\mathbf{V}$ 是 $\mathbf{L}_{Y_{\mathrm{g}}}$ 的 Cholesky 因子。解决 (11) 后，我们可以为$\mathbf{L}_{Y_{\mathrm{g}}{ }^{w} \cup\{j\}}$类似地更 $\mathbf{V}$, $\mathbf{c}_{i}$, and $d_{i}$。当$Y_{\mathrm{g}}^{w}$中的项数为$w-1$时，要更新$Y_{\mathrm{g}}^{w}$，我们还需要删除$Y_{\mathrm{g}}^{w}$ 中最早添加的项目。补充材料中给出了当最早添加的项被删除时更新 $\mathbf{V}、\mathbf{c}_{i}$ 和 $d_{i}$ 的详细推导。

完整的算法在算法 2 中进行了总结，第 10-21 行显示了如何在删除最早的项后就地更新 $\mathbf{V}、\mathbf{c}_{i}$ 和 $d_{i}$。在 $k \geq w$ 的第 $k$ 次迭代中，更新 $\mathbf{V}$，所有 $\mathbf{c}_{i}$ 和 $d_{i}$ 需要 $O\left( w^{2}\right)、O(w M)$ 和 $O(M)$ 时间，分别。算法 2 的总体复杂度为 $O(w N M)$，返回 $N \geq w$ 项。补充材料中讨论了数值稳定性。

改进推荐多样性

在本节中，我们描述了一种基于 DPP 的方法，用于向用户推荐相关且多样化的项目。对于用户$u$，配置文件项集$P_{u}$ 被定义为用户喜欢的项集。基于$P_{u}$，推荐系统向用户推荐项目$R_{u}$。

该方法需要三个输入：候选项目集 $C_{u}$、分数向量 $\mathbf{r}_{u}$（指示 $C_{u}$ 中项目的相关程度）以及 PSD 矩阵$\mathbf{S}$ 量化每对项目的相似度。前两个输入可以从许多传统推荐算法的内部结果中获得。第三个输入，相似度矩阵$\mathbf{S}$，可以根据项目的属性、与用户的交互关系或两者的组合来获得。这种方法可以被视为平衡项目相关性及其相似性的排名算法。

相似度矩阵$\mathbf{S}$可以使用物品embedding向量得到

为了将DPP模型应用到推荐任务中，我们需要构建核矩阵。如[30]中所示，核矩阵可以写为 Gram 矩阵，$\mathbf{L}=\mathbf{B}^{\top} \mathbf{B}$，其中 $\mathbf{ B}$列 是表示项目的向量。我们可以将每个列向量 $\mathbf{B}_{i}$ 构造为项目得分 $r_{i} \geq 0$ 和归一化特征向量 $\mathbf{f}_{i} \in \mathbb{R}^{D}$($\left\|\mathbf{f}_{i}\right\|_{2}=1$)的乘积。核矩阵 $\mathbf{L}$ 的实体可以写为

最终项目向量表征为a与b的特征向量归一化后求点积（等价于余弦相似度）再乘上a和b在排序模型上的分数

我们可以将 $\left\langle\mathbf{f}_{i}, \mathbf{f}_{j}\right\rangle$ 视为衡量项目 $i$ 和项目 $j$ 之间的相似度，即$\left\langle\mathbf{f}_{i}, \mathbf{f}_{j}\right\rangle=\mathbf{S}_{i j}$。因此，用户$u$的核矩阵可以写为$\mathbf{L}=\operatorname{Diag}\left(\mathbf{r}_{u}\right)\cdot\mathbf{S}\cdot \operatorname{Diag}\left(\mathbf{r}_{u}\right)$，其中 $\operatorname{Diag}\left(\mathbf{r}_{u}\right)$ 是对角矩阵，其对角向量是$\mathbf{r}_{u}$。 $R_{u}$ 的对数概率为

当 $R_{u}$ 的项目表示正交时，方程（13）中的第二项最大化，因此它促进了多样性。它清楚地展示了 DPP 模型如何融合推荐项目的相关性和多样性。

当选择的子矩阵内向量都相互正交时，向量构成的物体在向量空间中体积最大，即行列式值最大

[11,51,8]中的方法的一个很好的特点是它们涉及一个可调参数，允许用户调整相关性和多样性之间的权衡。根据等式。 (12)，原来的DPP模式并没有提供这样的机制。我们将 $R_{u}$ 的对数概率修改为

其中$\theta \in[0,1]$。这对应于带有内核的 DPP$\mathbf{L}^{\prime}=\operatorname{Diag}\left(\exp \left(\alpha \mathbf{r}_{u}\right)\right) \cdot \mathbf{S} \cdot \operatorname{Diag}\left(\exp \left(\alpha \mathbf{r}_{u}\right)\right)$其中$\alpha=\theta /(2(1-\theta))$.我们还可以得到边际收益log-probability $\log \mathcal{P}\left(R_{u} \cup\{i\}\right)-\log \mathcal{P}\left(R_{u}\right)$

然后算法1和算法2可以很容易地修改为用核矩阵最大化(15)

请注意，推荐任务需要相似度 $\mathbf{S}_{i j} \in[0,1]$，其中 0 表示最多样化，1 表示最相似。当归一化向量 $\left\langle\mathbf{f}_{i}, \mathbf{f}_{j}\right\rangle$ 的内积可以取负值时，可能会违反这一点。在极端情况下，最多样化的对 $\mathbf{f}_{i}=-\mathbf{f}_{j}$，但相应子矩阵的行列式为 0 ，与 $\mathbf{ 相同f}_{i}=\mathbf{f}_{j}$。为了保证非负性，我们可以采用线性映射，同时保持 $\mathbf{S}$ 为 PSD 矩阵，例如，