Determinantal Point Process (DPP)

A Determinantal Point Process (DPP) is a stochastic point process whose probability function is function determinant of some function.

• Context:
  • It can be used to Model Phenomena where Items Repel Each Other, like locations of trees in a forest or seats in a theater.
  • It can be characterized by the property that the probability of finding a point in a given region depends on the determinant of a kernel function evaluated at these points.
  • It can provide a way to select a diverse set of items from a larger set, where the diversity is quantified by the determinant.
  • ...
• Example(s):
  • as in Random Matrix Theory, where eigenvalues of random matrices exhibit repulsion.
  • as in Document Summarization, to choose a diverse set of sentences that cover different aspects of the text.
  • as in Spatial Statistics, for modeling the distribution of trees in a forest.
  • ...
• Counter-Example(s):
  • a Poisson Point Process, which models events occurring independently of each other.
  • a Gaussian Process, which does not inherently model repulsion between points.
• See: Point Process, Matrix Determinant, Stochastic Process, Determinant, Random Matrix.

---

---

References

2023

• (Wikipedia, 2023) ⇒ https://en.wikipedia.org/wiki/Determinantal_point_process Retrieved:2023-11-30.
  • In mathematics, a determinantal point process is a stochastic point process, the probability distribution of which is characterized as a determinant of some function. Such processes arise as important tools in random matrix theory, combinatorics, physics, and wireless network modeling.

2017

• Wray Buntine. (2017). “Introduction to the Determinantal Point Process."
  • QUOTE: Representing objects with feature vectors lets us measure similarity using dot products. Using this notion, the determinantal point process (DPP) can be introduced as a distribution over objects maximising diversity. In this tutorial we will explore the DPP with the help of the visual analogies developed by Kulesza and Taskar in their tutorials and their 120 page Foundations and Trends article "determinantal point processes for machine learning." Topics covered are interpretations and definitions, probability operations, such as marginalising and conditioning, and sampling.

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/determinantal_point_process Retrieved:2015-1-27.
  • In mathematics, a determinantal point process is a stochastic point process, the probability distribution of which is characterized as a determinant of some function. Such processes arise as important tools in random matrix theory, combinatorics, and physics.

2012

• (Kulesza & Taskar, 2012) ⇒ Alex Kulesza, and Ben Taskar. (2013). “Determinantal Point Processes for Machine Learning.” In: Foundations and Trends in Machine Learning, December 2012.
  • QUOTE: Determinantal point processes (DPPs) are elegant probabilistic models of repulsion that arise in quantum physics and random matrix theory. In contrast to traditional structured models like Markov random fields, which become intractable and hard to approximate in the presence of negative correlations, DPPs offer efficient and exact algorithms for sampling, marginalization, conditioning, and other inference tasks. … how DPPs can be applied to real-world applications like finding diverse sets of high-quality search results, building informative summaries by selecting diverse sentences from documents, modeling non-overlapping human poses in images or video, and automatically building timelines of important news stories. …

2010

• (Delvaux, 2010) ⇒ Steven Delvaux. (2010). “Average Characteristic Polynomials for Multiple Orthogonal Polynomial Ensembles.” In: Journal of Approximation Theory, 162(5). doi:10.1016/j.jat.2009.11.008

2009

• (Houghen et al., 2009) ⇒ John B. Houghen, Manjunath Krishnapur, and Yuval Peres. (2009). “Zeros of Gaussian Analytic Functions and Determinantal Point Processes.” Vol. 51. American Mathematical Soc.,
  • BOOK OVERVIEW: The book examines in some depth two important classes of point processes, determinantal processes and 'Gaussian zeros', i.e., zeros of random analytic functions with Gaussian coefficients. These processes share a property of 'point-repulsion', where distinct points are less likely to fall close to each other than in processes, such as the Poisson process, that arise from independent sampling. Nevertheless, the treatment in the book emphasizes the use of independence: for random power series, the independence of coefficients is key; for determinantal processes, the number of points in a domain is a sum of independent indicators, and this yields a satisfying explanation of the central limit theorem (CLT) for this point count. Another unifying theme of the book is invariance of considered point processes under natural transformation groups. The book strives for balance between general theory and concrete examples. On the one hand, it presents a primer on modern techniques on the interface of probability and analysis. On the other hand, a wealth of determinantal processes of intrinsic interest are analyzed; these arise from random spanning trees and eigenvalues of random matrices, as well as from special power series with determinantal zeros. The material in the book formed the basis of a graduate course given at the IAS-Park City Summer School in 2007; the only background knowledge assumed can be acquired in first-year graduate courses in analysis and probability.

---