Learning Determinantal Point Processes in Sublinear Time
This work addresses scalability issues in DPPs for tasks like text modeling, offering a practical solution for handling exponentially large item sets, though it is incremental in improving efficiency within an existing framework.
The authors tackled the problem of efficiently learning and inferring determinantal point processes (DPPs) on large sets, such as for document summarization, by proposing a new low-rank factorization class that enables sublinear-time operations. They demonstrated this with an application to document summarization on 2^500 items, achieving exact inference without approximations.
We propose a new class of determinantal point processes (DPPs) which can be manipulated for inference and parameter learning in potentially sublinear time in the number of items. This class, based on a specific low-rank factorization of the marginal kernel, is particularly suited to a subclass of continuous DPPs and DPPs defined on exponentially many items. We apply this new class to modelling text documents as sampling a DPP of sentences, and propose a conditional maximum likelihood formulation to model topic proportions, which is made possible with no approximation for our class of DPPs. We present an application to document summarization with a DPP on $2^{500}$ items.