K-DPP

[jilljenn]

Quoi mais lol mais fallait m'en parler ! https://github.com/mangaki/notebooks/blob/master/Test%20DPP.ipynb

Do you implement K-DPP with symmetric polynomials? Cos there is another implementation on GitHub that does it. I don't remember where we got inspired from; but I will let you know.

Anyway thanks! I will try to use it.

[guilgautier]

Hi @jilljenn, thanks for reaching out !

What do you mean by ? 🙂

Quoi mais lol mais fallait m'en parler ! https://github.com/mangaki/notebooks/blob/master/Test%20DPP.ipynb

Good point about k-DPPs! At present there is no clear/n implemented of kDPPs in DPPy mainly because I did not take the time to do it properly, but also because k-DPPs are not DPPs except in a very specific case.

Anyway, I'd be happy to help and provide a suitable implementation!

1. Would you like to sample from a kDPP both exactly and approximately using a markov chain ?
2. From a user perspective, do you think it would be better to:
   • have a dedicated FiniteKDPP object or
   • add a method like sample_exact_k_dpp(k=) to the currentFiniteDPP object ?

Actually, most of the bricks are already there see:

• commented section
• here for the symmetric polynomials

Btw, in your notebook:

• since you're building a symmetric kernel you could try the np.linalg.eigh instead of np.linalg.eig
• you are playing with the L kernel of a DPP, see the doc, to avoid any confusion I'd name the kernel L and not K

[guilgautier]

To answer your question:

Do you implement K-DPP with symmetric polynomials?

I do 🙂

Cos there is another implementation on GitHub that does it. I don't remember where we got inspired from; but I will let you know.

Please let me know, I am not aware of an alternative to symmetric polynomials. Except when you have a projection inclusion kernel K, you can apply the chain rule and stop when you have k elements

[guilgautier]

Hi @jilljenn!

I've added a sample_exact_k_dpp method to the FiniteDPP object (see the documentation)

Feel free to give some feedback about this feature and the DPPy project as a whole 🙂

[jilljenn]

Hi! Will do, thanks!

I found where I found it (but it's symmetric polynomials): https://github.com/bdol/bdol-ml/tree/master/dpp

And one of the commits on their repo answered my question for you which was "Why eigh?" Answer: faster and more accurate.

[guilgautier]

Thx for pointing out the other repo :)

Note also that the implementation of the sampler is not the most efficient O(Nr^3) instead of O(Nr^2) where r = expected number of points.

Have a look at the see also section here and mode argument in the sample_exact method

[arsyed]

Hi, Thank you for your work on this library. I tried the sample_exact_k_dpp(size=k) method. However, it fails when k exceeds rank(L). While this is a limit for DPP sampling, I'm not sure that it extends to k-DPPs based on the algorithm 2 in the k-DPP paper (Kulesza and Taskar, 2011). Am I wrong about either this or the way I'm coding it below?

n_grid = 20
# X: 400 examples x 2-D feature space
X = np.mgrid[0:1:1/ngrid, 0:1:1/ngrid].reshape(2, ngrid**2).T
dpp = FiniteDPP('likelihood', **{'L': X.dot(X.T)})
k = 64
dpp.sample_exact_k_dpp(size=k)

[guilgautier]

Hi @arsyed, thanks for your message!

The code you provided seems correct to me (after removing the underscore of n_grid = 20) but you can't hope to sample from a k-DPP with k > rank(L) (rank(L) <= 2 in your case).

I hope the following will help to understand

---

If you think k-DPP(L) as DPP(L) conditioned to fixed cardinality k, then

it fails when k exceeds rank(L). While this is a limit for DPP sampling

if you can't have DPP samples of cardinality k > rank(L) then you can't define the corresponding k-DPP.

For this reason I made the sampler raise an issue.

---

Alternatively, you can have a look at the definition of k-DPP in the docs or [KuTa12, Section 5.1 Equation 173] you will see that

• det L_S or det L_Y is zero for |S| or |Y| = k > rank(L)
• the normalizing constant, if it existed, would also be zero...

---

Note:

1. However, if you take A. Kulesza's (Matlab) code or even convert it to Python you may get something but this is nonsense. This is only due to numerical evaluation of ratios of elementary symmetric polynomials (see docs) that should be 0 for k > rank(L) but are very small on your computer and that cancel out in the ratio...

2. You might add random N(0, sigma^2) features (with sigma small) to increase the rank of your kernel

[arsyed]

Hi @guilgautier, I understand now. Thank you for taking the time to explain this and point out the references!