Scalable Inference Algorithms for Determinantal Point Processes

Determinantal Point Processes (DPPs) are probability distributions on subsets of a collection of points that tend to generate diverse configurations of points. This feature makes them suitable as a probabilistic model of diversity. Recently this idea has been exploited extensively in subset selection problems, where given a large set of items such as images, documents, or any other form of collected data, the goal is to select a small, yet diverse and representative subset. However, with the rapid growth of datasets size, in order to utilize DPPs for real-world tasks, we need to design new primitives and inference algorithms that can be run efficiently in these settings. This thesis focuses on two inference tasks for DPPs: In the first part, we study sampling algorithms for DPPs and offer efficient MCMC based algorithms which can be applied in both discrete and continuous domains. In the second part, we consider the problem of determinant maximization which is equivalent to the Maximum a Posteriori encoding for DPPs, and present scalable algorithms in a distributed setting which assumes the input data are arbitrarily split among numerous nodes.

Author dc:creator

• Rezaei, Alireza

Advisor dc:contributor.advisor

• Oveis Gharan, Shayan

• Determinant Maximization
• Determinantal Point Process
• Diverse Subset Selection
• DPP
• Sampling
• Strongly Rayleigh Measures
• Computer science
• Applied mathematics
• Mathematics

Statement dc:rights

• none

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1773/45473

OAI identifier oai:identifier

oai:digital.lib.washington.edu:1773/45473