摘要
行列式点过程 (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] 的已知精确实现具有
描述普通的DDP在解决MAP这类np困难问题时算法复杂度过大
DPP 的基本特征是它为彼此具有差异性的项目集分配更高的概率[30]。在某些应用中,所选项目显示为序列,并且负面交互作用仅限于附近的几个项目之间。例如,当向用户推荐一长串项目时,每次只有该序列的一小部分引起用户的注意。在这种情况下,要求彼此远离的项目具有多样性是没有必要的。针对这种情况开发快速算法是本文的另一个动机。
Contributions. 在本文中,我们提出了一种新颖的算法来大大加速 DPP 的贪婪 MAP 推理。通过增量更新 Cholesky 因子,我们的算法将复杂度降低至
此外,我们还使我们的算法适应仅在滑动窗口内需要多样性的场景。假设窗口大小为
最后,我们将我们提出的算法应用于推荐任务。推荐多样化的项目为用户提供了发现新颖和偶然项目的探索机会,也使服务能够发现用户的新兴趣。正如公共数据集和在线 A/B 测试的实验结果所示,与已知方法相比,基于 DPP 的方法在相关性和多样性之间具有良好的权衡。
- 加速 DPP 的贪婪 MAP 推理
- 滑动窗口内多样性的场景
- 算法应用于推荐任务,结果优秀
背景与相关工作
Notations. 集合用大写字母表示,如
行列式点过程
DPP 是一种优雅的概率模型,能够表达负面交互作用 [30]。形式上,离散集
选择子集
的概率正比于其行列式大小: 矩阵可以看着是一组向量的集合,而矩阵的行列式的物理意义为矩阵中的各个向量张成的平行多面体体积的平方。这些向量彼此之间越不相似,向量间的夹角就会越大,张成的平行多面体的体积也就越大,矩阵的行列式也就越大,对应的商品集合的多样性也就越高。当这些向量彼此正交的时候,多样性达到最高。
在某些应用中,我们需要对
比如推荐重排过滤出固定大小的子集
除了第 11 节中介绍的 DPP MAP 推断的工作之外,其他一些工作建议抽取样本并返回概率最高的样本。在[16]中,当
推荐多样性
提高推荐多样性一直是机器学习和信息检索中的一个活跃领域。一些作品在通用环境中解决了这个问题,以实现任意相关性和相异性函数之间的更好权衡[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 推理算法的快速实现。在每次迭代中,项目
每次选择使
最大化的i(这里的i需要排除已经选的,也就是从剩下未选的中挑选)
添加到
Cholesky分解是将Hermitian正定矩阵分解为下三角矩阵及其共轭转置的乘积。
其中行向量
矩阵乘法
此外,根据等式(3) ,可得
矩阵行列式性质
因此, (2) 相当于
被消去
一旦等式(6)被求解,等式(3)的
j求出来了,并加入了被选择矩阵
其中
对于每个项目
通过将等式(4)和等式(8)组合,我们推导出
的增量更新公式
增量更新
最初,
在第
滑动窗口内的多样性
在一些应用中,选定的项目集显示为序列,并且仅在滑动窗口内需要多样性。将窗口大小表示为
其中
在第 3 节中,我们展示了当
完整的算法在算法 2 中进行了总结,第 10-21 行显示了如何在删除最早的项后就地更新
改进推荐多样性
在本节中,我们描述了一种基于 DPP 的方法,用于向用户推荐相关且多样化的项目。对于用户
该方法需要三个输入:候选项目集
相似度矩阵
可以使用物品embedding向量得到
为了将DPP模型应用到推荐任务中,我们需要构建核矩阵。如[30]中所示,核矩阵可以写为 Gram 矩阵,
最终项目向量表征为a与b的特征向量归一化后求点积(等价于余弦相似度)再乘上a和b在排序模型上的分数
我们可以将
当
当选择的子矩阵内向量都相互正交时,向量构成的物体在向量空间中体积最大,即行列式值最大
[11,51,8]中的方法的一个很好的特点是它们涉及一个可调参数,允许用户调整相关性和多样性之间的权衡。根据等式。 (12),原来的DPP模式并没有提供这样的机制。我们将
其中
然后算法1和算法2可以很容易地修改为用核矩阵最大化(15)
请注意,推荐任务需要相似度
Comments | NOTHING