Determinantal Point Processes

Determinantal point processes (DPPs) arise in random matrix theory and quantum physics as models of random variables with negative correlations. Among many remarkable properties, they offer tractable algorithms for exact inference, including computing marginals, computing certain conditional probabilities, and sampling. DPPs are a natural model for subset selection problems where diversity is preferred. For example, they can be used to select diverse sets of sentences to form document summaries, or to return relevant but varied text and image search results, or to detect non-overlapping multiple object trajectories in video. In our recent work, we discovered a novel factorization and dual representation of DPPs that enables efficient inference for exponentially-sized structured sets. We developed a new inference algorithm based on Newton identities for DPPs conditioned on subset size. We also derived efficient parameter estimation for DPPs from several types of observations. We demonstrated the advantages of the model on several natural language and vision tasks: extractive document summarization, diversifying image search results and multi-person articulated pose estimation problems in images.