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.

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 ( Kxx Kxy ) Kyx Kyy

= 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:
• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic