Jason (jcreed) wrote,
Jason
jcreed

Been reading about determinantal point processes.

A DPP, call it P, is a random variable that take values on the powerset 2X of some set X, with a particular sort of distribution that encourages "variety" of the points of X that get selected to be in the set that is outcome of the random variable.

To define a DPP, you pick a kernel K, a symmetric positive semi-definite N x N matrix (whose eigenvalues are never any more than 1) where N is the cardinality of X, and then the marginal probability distribution of P is determined by

Pr[P ⊇ S] = det(KS)

for any S ⊆ X, where KS means the matrix K trimmed down to just the rows and columns that correspond to the elements of X that are actually in S.

To unpack some intuition about this, consider the singleton and doubleton cases of S.

Pr[x ∈ P] = Pr[P ⊇ {x}] = det(Kxx) = Kxx
so the diagonal of K tells us the marginal probabilities of each particular element of X belonging to P in isolation.

Pr[{x,y} ⊆ P] = det(KxxKxy)
KyxKyy

= KxxKyy - Kxy2
so all of the off-diagonal elements of K tell us how much potential elements of P "repel" each other, in the sense that the joint probability of having the two of them is less than they would be if they were independent.

Apparently this kind of distribution is good for (among other things) search result display, because you don't necessarily want to show the top results for a query --- they might all be very similar to each other. You want the similar ones to "repel" each other a bit, and prefer choosing different ones to better cover the space of what someone might want from a query.
Tags: determinants, math
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 2 comments