Maximizing Induced Cardinality Under a Determinantal Point Process
Determinantal point processes (DPPs) are well-suited to recommender systems where the goal is to generate collections of diverse, high-quality items. In the existing literature this is usually formulated as finding the mode of the DPP (the so-called MAP set). However, the MAP objective inherently assumes that the DPP models "optimal" recommendation sets, and yet obtaining such a DPP is nontrivial when there is no ready source of example optimal sets. In this paper we advocate an alternative framework for applying DPPs to recommender systems. Our approach assumes that the DPP simply models user engagements with recommended items, which is more consistent with how DPPs for recommender systems are typically trained. With this assumption, we are able to formulate a metric that measures the expected number of items that a user will engage with. We formalize this optimization of this metric as the Maximum Induced Cardinality (MIC) problem. Although the MIC objective is not submodular, we show that it can be approximated by a submodular function, and that empirically it is well-optimized by a greedy algorithm.
The authors have addressed most of my concerns in their response, and I hope to see the changes they mentioned reflected in the final version.  ----------  The paper proposes an alternative objective for diverse subset selection using determinant point processes (DPPs). For the task of selecting a best subset from the ground set, the authors argue that instead of the maximum a posterior (MAP) objective, a more suitable objective is to maximize the expected number of items in the subset that the user will engage with, which is termed the maximum induced cardinality (MIC) objective. The paper proceeds to investigate theoretical properties of the MIC objective, and proposes an approximation algorithm for optimizing MIC by observing that the objective, while not sub-modular, is fractionally sub-additive.  Overall, the paper is clearly written and appears technically sound. However, while I tend to agree with the intuition that the MIC might be a more suitable objective than MAP in practice, my major concern is that this hypothesis has not been verified/justified with any empirical evidence in the experiments. I believe that this is an important aspect as the hypothesis is not a widely acknowledged fact, and its plausibility greatly affects the significance of the theoretical and methodological contributions made in this paper; thus at least some form of evidence should be provided to justify the motivation of the paper. I understand that as the authors mentioned on line 228, a truly sound comparison between MIC and MAP should be done via a live system on real data, but I believe that simpler simulations or experiments could be enough to shed some light and provide some empirical support for the hypothesis and convince readers of its potential practical importance. Such experiments could be performed on simulated or offline data (e.g., website recommendations/transactions history), or using crowdsourcing tools (e.g., Amazon Mechanical Turk). Some of the evaluation methods used in the DPP papers (Kulesza et al., Gillenwater et al., among others) could also be borrowed here.  On the technical side, I have some more specific comments:  - The authors noted on line 115 that when the DPP kernel is low-rank, MAP can fail dramatically. However, by Corollary 4.1, it seems that when L is low-rank, some eigenvalues of B could be large, which would result in a small value of c, indicating poor approximation quality of \hat{f} to f?  - Line 169: in the summand, what is the index j for?  - In terms of running time complexity, how does the approximate MIC algorithms (GIC, PIC, and SIC) compare with the state-of-the-art approximate MAP algorithm? If SIC is significantly more efficient than the current MAP algorithm, this could also be a potential reason to prefer MIC over MAP.  - Since PIC was used in the experiments, I feel that at least some details regarding the projection onto the space of PSD M-matrices should be included in the main text. In Section 5 of the supplementary material, the authors states that they found “flipping the signs of any positive off-diagonal elements, then projecting to the PSD cone by truncating negative eigenvalues at zero worked best”, and “if the PSD projection resulted in any positive off-diagonal elements, we simply iterated the process of flipping their signs and projecting to the PSD cone until the resulting matrix satisfied all requirements”. I’m not sure if the sign-flipping is a standard/theoretically justified approach of projecting on to the space of M-matrices, and whether the latter iterative procedure would be guaranteed to terminate?  - Minor point: In the experiments using the graph Laplacian, I feel that instead of/in addition to a simple Erdos-Renyi model, using a more realistic random graph model (e.g., the stochastic blockmodel, the preferential-attachment model, etc.) that obeys the many properties found in real-world networks (power-law degree distributions, clustering, small-world property, etc.) could be more informative.