Determinantal point processes (DPPs) have attracted significant attention in
machine learning for their ability to model subsets drawn from a large item
collection. Recent work shows that nonsymmetric DPP (NDPP) kernels have
significant advantages over symmetric kernels in terms of modeling power and
predictive performance. However, for an item collection of size $M$, existing
NDPP learning and inference algorithms require memory quadratic in $M$ and
runtime cubic (for learning) or quadratic (for inference) in $M$, making them
impractical for many typical subset selection tasks. In this work, we develop a
learning algorithm with space and time requirements linear in $M$ by
introducing a new NDPP kernel decomposition. We also derive a linear-complexity
NDPP maximum a posteriori (MAP) inference algorithm that applies not only to
our new kernel but also to that of prior work. Through evaluation on real-world
datasets, we show that our algorithms scale significantly better, and can match
the predictive performance of prior work.

本文介绍了一种线性复杂度的基于 NDPP 内核分解的学习算法和一个线性复杂度的最大后验概率推断算法，使用这些算法可以更好地进行数据集的子集选择，缩短计算时间，并且提升了预测性能。