We aim to understand theory and applications of diversity-inducing probabilities (and, more generally, "negative dependence") in machine learning, and develop fast algorithms based on their mathematical properties.
Probability measures that induce diversity have numerous applications in machine learning. For example, to summarize or sketch large data sets or large matrices, or to scale nonlinear machine learning methods like kernel methods or neural networks, we need to select a small, representative subset of items from a large collection. In other cases, we may want to add prior knowledge about repulsion (e.g., location of objects), or obtain more interpretable models. All of these applications can be phrased as drawing a representative sample of items from a diversity-inducing probability measure. Measures that are particularly suitable and often induce theoretical guarantees for applications are Determinantal Point Processes (DPPs) and, more generally, Strongly Rayleigh measures. These are characterized by strong negative dependencies. However, algorithms for these measures so far were not practically scalable. In this project, we develop new applications and algorithms, e.g. fast sampling methods with provable polynomial running times and good empirical performance. These algorithms build on a better understanding of the involved probability measures and their mathematical properties, such as deep algebraic and geometric relations with special classes of polynomials and special polyhedra. In addition, we aim to extend our methods and analyses to related measures and variations (e.g., conditioning on constraints).
