Expectation-Maximization for Learning Determinantal Point Processes
A determinantal point process (DPP) is a probabilistic model of set diversity compactly parameterized by a positive semi-definite kernel matrix. To fit a DPP to a given task, we would like to learn the entries of its kernel matrix by maximizing the log-likelihood of the available data. However, log-likelihood is non-convex in the entries of the kernel matrix, and this learning problem is conjectured to be NP-hard [1]. Thus, previous work has instead focused on more restricted convex learning settings: learning only a single weight for each row of the kernel matrix [2], or learning weights for a linear combination of DPPs with fixed kernel matrices [3]. In this work we propose a novel algorithm for learning the full kernel matrix. By changing the kernel parameterization from matrix entries to eigenvalues and eigenvectors, and then lower-bounding the likelihood in the manner of expectation-maximization algorithms, we obtain an effective optimization procedure. We test our method on a real-world product recommendation task, and achieve relative gains of up to 16.5% in test log-likelihood compared to the naive approach of maximizing likelihood by projected gradient ascent on the entries of the kernel matrix.
The paper presents and EM algorithm for learning Determinantal Point Processes. The method combines several nontrivial ingredients: eigendecomposition of the kernel, optimisation on the Stiefel manifold, representation of DPPs as mixtures of elementary DPPs, and lower-bounding the log-likelihood by Jensen 's Inequality.  The experiments show favourable behaviour of the proposed approach compared to a simpler "K-Ascent" scheme. Quality: As far as I can tell the method is well-founded, and is believable that the methods should work as stated. However,the evaluation of the method could be improved. The experiments are quite limited and do not compare against alternative approaches for subset selection (e.g. those mentioned in the introduction), so it is not clear how much we benefit from the DPP approach.Clarity: The paper is not particularly clearly written. write-up is somewhat sloppy and hard to follow. Not all notation is defined and sometimes definition comes after using it. The writing is also unnecessarily convoluted at times, mostly because the text is structured to describe a process how one ends up with the finally proposed approach, with side-remarks of possible alternative approaches and problems interleaved with the main thread. I would have preferred to present the developed method as clearly as possible and postpone discussion to a later stage.Originality: For me the paper looks quite original, I am not aware of similar work.Significance: I think the method derived in the paper presents a solid advance and a useful contribution to subset selection literature.Details:- p.2. line 81 the marginal kernel K is not defined before use. What kind of kernel qualifies as marginal kernel?- p.2. l 100: V is not defined- p.3. l 159: "minimises the change to Frobenius norm" is unclearly stated. It would be better to say "chooses the closest (in Frobenius norm) PSD matrix to Q".- p 4. I found this section hard to understand. Rather than referring to [26] it would be nice to outline your (simpler) approach directly so that the reader is not forced to lookup the more complex original method.  - p.4 line 189: what does "weight" refer to?- p. 7 line 324. I don't quite get the rationale in (30). Why is m_{ij} not used here? Why would simply using the empirical covariance matrix as the kernel not have worked as initialisation?