{'fraction_non_alphanumeric': 0.03171269557912423, 'fraction_numerical': 0.009135776541005985, 'mean_word_length': 4.812328349099786, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Wasserstein Learning of Determinantal Point Processes

Determinantal point processes (DPPs) have received significant attention as an elegant probabilistic model for discrete subset selection. Most prior work on DPP learning focuses on maximum likelihood estimation (MLE). While efficient and scalable, MLE approaches do not leverage any subset similarity information and may fail to recover the true generative distribution of discrete data. In this work, by deriving a differentiable relaxation of a DPP sampling algorithm, we present a novel approach for learning DPPs that minimizes the Wasserstein distance between the model and data composed of observed subsets. Through an evaluation on a real-world dataset, we show that our Wasserstein learning approach provides significantly improved predictive performance on a generative task compared to DPPs trained using MLE.


Introduction
Generative models have enjoyed a great deal of success in the recent years due to their ability to capture insights from data distributions. Those models have generally been applied to continuous data by training them using maximum likelihood estimation (MLE) or, more recently, using adversarial learning with the well-known Generative Adversarial Networks framework [12,15].
When dealing with discrete data, generative models trained with MLE suffer from a bias due to the asymmetrical definition of MLE. Equivalent to minimizing a Kullback Leibler divergence, the MLE cost function pays extremely low cost for generating low-quality samples. Consequently, a generative model trained by MLE tends to cover the full data distribution at the expense of covering unnecessary regions [2,23]. On the other hand, when considering adversarial learning of discrete generative models, one usually exploits the gradient of the discriminator's loss when optimizing the generator. However, since the gradient computation requires backpropagation through the generator's output, i.e. the data, adversarial approaches are difficult to apply when generating discrete data. Depending on the generative model and the structure of the data, there are some ways to overcome this issue. For instance, [19] was the first to define a sampling scheme with the use of a Gumbel softmax distribution, and several generalizations of this softmax trick have been recently proposed in the literature [26,14].
In this work, we address the problem of training a determinantal point process (DPP), a probabilistic model for subsets drawn from a large collection of items. A DPP parameterizes a probability distribution over the combinatorial space of subsets of elements drawn from J , which is a discrete space composed of M distinct items. DPPs are appealing models for this setting, since they are known to also capture interactions between elements within subsets. More importantly, they offer efficient polynomial-time algorithms for most probabilistic inference operations over the space of 2 M possible subsets, such as normalization, learning, and sampling [10,18]. In order to move away from the standard MLE learning framework [8,22], which may suffer from the flaw described above, we define a new learning scheme for DPPs based on the minimization of the Wasserstein distance between the samples generated by the DPP and the training data. Compared to MLE, one of the main benefits of this Wasserstein-based approach is that it allows us to define a transportation cost function (e.g a Jaccard distance) that induces a bias on the assumed structure of the space of subsets. Minimizing this cost function allows the learning to take into account differences between pairs of subsets and to reduce the distance between subsets based on their similarities. We argue that this Wasserstein-based scheme leverages more information from the data and results in a better approximation of the target distribution.
The contributions of this work are the following: 1.) We present a new framework when learning DPPs that minimizes the Wasserstein distance between the DPP and data composed of observed subsets. This framework can be applied to any generative probabilistic model for discrete sets. 2.) Leveraging recent work on a DPP sampling algorithm with computational complexity that is sublinear in the size of the ground set [3], and stochastic softmax tricks for gradient estimation of discrete distributions [14], we present a differentiable DPP sampling algorithm that can scale to large ground sets. 3.) We evaluate our Wasserstein learning approach on a real-world dataset, and show substantial improvements in predictive performance compared to DPPs trained using MLE. This experimental evaluation is one of the first to focus on a generative modeling task for DPPs. In order to ensure that the DPP defines a probability distribution, all principal minors of L must be non-negative: det(L J ) ≥ 0. Matrices that satisfy this property are called P 0 -matrices [4,Definition 1]. Several decompositions of L that partially cover the P 0 space are known. One common decomposition that covers the space of symmetric P 0 -matrices exploits the fact that L ∈ P 0 if L is positive semidefinite (PSD) [29]. Any symmetric PSD matrix can be written as the Gramian matrix of some set of vectors: L := V V , where V ∈ R M ×K . We restrict our work in this paper to such symmetric DPPs with this decomposition, since efficient sampling algorithms, such as [3], are only available for symmetric DPPs. There are decompositions of L that partially cover the nonsymmetric P 0 [9]; we leave an investigation of Wasserstein learning of nonsymmetric DPPs for future work.
In this work we use the DPP-VFX sampling algorithm [3], which has computational complexity sublinear in M , and is therefore one of the most efficient exact sampling methods for DPPs. DPP-VFX relies on a connection between ridge leverage scores [1] and DPPs to implement a distortion-free intermediate sampling method that enables this sublinear time complexity. Since DPP-VFX requires a base DPP sampling algorithm, we propose to use the Cholesky-based DPP sampling approach [20,28].
Estimating gradients in discrete settings The Wasserstein learning approach requires computing gradients over discrete subset samples drawn from a DPP. Two families of approaches for discrete gradient estimation are score function estimators, such as REINFORCE [30], and continuous relaxations of discrete distributions, most of which are based on the Gumbel-Max trick [21]. REINFORCE has the drawback of high variance, making it impractical in many cases. While techniques for variance reduction exist [24], they often involve highly engineered control variates. Relaxed gradient estimators incorporate bias in order to reduce variance, and are often easier to implement [26]. We choose the relaxation approach, and leverage recent work on stochastic softmax tricks [19,26], which is a unified framework for structured relaxations of discrete combinatorial distributions. In particular, we use stochastic softmax tricks to develop a differentiable version of the DPP-VFX sampling algorithm, with a differentiable version of the Choleksy-based approach as the base DPP sampling algorithm. As far as we are aware, this is the first instance of a differentiable DPP sampling algorithm.

Learning DPPs via Wasserstein minimization
The classical approach for learning a DPP kernel given a collection of subsets is to maximize the likelihood of data samples drawn from the same distribution as the one used for obtaining training examples [8,9]. One advantage of optimizing the (log) likelihood is that the likelihood of samples has a closed form expression with respect to the model parameters. Since that expression is continuously differentiable, a gradient ascent algorithm is a natural solution for solving the problem. Instead of likelihood maximization, we propose a DPP learning approach that minimizes the Wasserstein distance between the training data and samples generated by the model. This optimization scheme seeks to improve the approximation of the generative distribution of the data.
The Wasserstein distance is a distance between probability distributions defined on a given metric space. We let X n = {x 1 , · · · , x n } denote the training dataset of size n with empirical distribution µ = n i=1 a i δ xi , where δ refers to the Dirac distribution, and Y n = {y 1 , · · · , y n } be the collection of n sets sampled from the DPP model with distribution ν = m i=1 b i δ yi , where the a i and b i follow a uniform distribution. Given a transportation cost d defined on 2 M × 2 M , the Wasserstein distance between µ and ν seeks an optimal coupling P defined on [1, n] 2 that minimizes the cost of transporting mass from µ to ν [27]. When dealing with discrete sets of items, we argue that the use of the Jaccard distance [17] as as transportation cost function is a good choice. The Jaccard distance between two sets takes into account both the difference in length and in the items chosen: Since the cost function needs to be differentiable, we use a differentiable proxy for Jaccard distance. For x ∈ X n and y ∈ Y n , the differentiable Jaccard distance d S is defined as follows: where x, ∈ {0, 1} M is a binary indicator vector and y ∈ [0, 1] M is a continuous relaxation of a binary vector, with y k , k ∈ [1, M ] being the inclusion probability of item k in the sample. By combining the definition of the Wasserstein distance with the chosen cost function in (1), we define the following Wasserstein optimization problem for DPPs: where {x 1 , · · · , x n } is the training data, {y 1 , · · · , y n } is a collection of n subsets drawn from the DPP, and α ≥ 0 is a tunable hyperparameter for regularization. Recall that we use the decomposition L = V V for the DPP kernel. For the sake of completeness, the algorithm used to solve this optimization scheme is described in Algorithm 1. Solving the optimization problem defined in Eq. 2 with backpropagation requires computing the gradient on minibatches with respect to the parameters V , and thus a differentiable sampling algorithm is needed. We use an estimation of the Wasserstein distance on a minibatch [5] by computing a Earth Mover distance, and consider a new differentiable formulation of the DPP-VFX sampling algorithm [3], shown in Algorithm 2 in Appendix A. We apply the Gumbel softmax trick to the base Poisson, and multinomial, and Bernoulli sampling steps in DPP-VFX. Combined with a differentiable DPP Cholesky-based sampler (Algorithm 6), this sampler generates continuous relaxations of binary indicator vectors for subsets; see Appendix A for details.

Experiments
We perform experiments on the Amazon Baby Registries dataset. This dataset consists of registries or "baskets" of baby products, and has been used in prior work on DPP learning [7,9,11,22]. The  Figure 1: Precision plot for the generated subsets from each model that have a Jaccard distance of at most with at least one subset in the test set, for ∈ (0, 1], for the Amazon apparel dataset. registries contain items from 15 different categories, such as "apparel", with a catalog of up to 100 items per category. We evaluate on the most popular apparel category, which contains 14,970 registries, as well as the popular diaper and feeding categories.

Setup and evaluation metrics
A small set consisting of 300 randomly-selected baskets is kept for validation, and a further random selection of 2000 baskets is used for testing. We implement our models using PyTorch [25]; Adam [16] is used for optimization, in conjunction with the solver from the POT package [6].
We use the low-rank symmetric DPP (SDPP) [8] and the low-rank nonsymmetric DPP (NDPP) [9], both trained using MLE, as baseline models for all experiments. We evaluate these baselines and our Wasserstein DPP model (WDPP) model on a subset generation task, where we estimate the Wasserstein distance (WD) between subsets sampled from the model and subsets in the test set by computing the Earth Mover's distance between these two subset collections using POT [6].

Results
Consistent with prior work, we see that the MLE NDPP outperforms the MLE SDPP on the test log-likelihood metric. However, we also observe that MLE is not directly connected to the generative task, and higher performance on test log-likelihood does not result in higher performance on the WD metric. As expected, since the Wasserstein learning approach directly optimizes a proxy for the generative task, the WDPP model significantly outperforms the baseline models in terms of WD.
To provide some evidence of the connection between the WD metric and the quality of generated subsets, Fig. 1 shows the percentage of generated subsets from each model that have a Jaccard distance of at most with at least one subset in the test set, for ∈ (0, 1]. For any given , we see that WDPP outperforms MLE models. This highlights that the WDPP, by being able to take the Jaccard distance into account, exploits the underlying structure of the combinatorial space 2 M , while the MLE-trained models do not and thus treat all subsets as completely different. We present additional experimental results in Appendix C. These results provide further evidence that, compared to MLE DPPs, the WDPP model recovers significantly more structure, and is able to generate subsets that are substantially closer to observed data.

Conclusion
We have presented a new Wasserstein learning approach for DPPs. Unlike conventional MLE learning approaches for DPPs, this learning approach optimizes a proxy for discrete subset generation.
Empirical results indicate that the proposed approach leads to substantially improved generative performance compared to MLE. This approach is fully general, and can be readily applied to other families of models for discrete subsets. We leave such an investigation for future work.

A Differentiable DPP-VFX Sampling Algorithm
As indicated in Section 2, we have leveraged stochastic softmax tricks (SST) [26] to develop a differentiable version of the DPP-VFX sampling algorithm [3]. Compared to other DPP sampling algorithms, DFF-VFX can be substantially faster, since it has time complexity sublinear in M . DPP-VFX uses a connection between ridge leverage scores [1] and DPPs to implement a distortion-free intermediate sampling method that enables this sublinear time complexity. The first step of the sampling algorithm downsamples the items in [[M ]] i.i.d. with probability proportional to the ridge leverage score of each item, and then runs a conventional DPP sampling algorithm on this thinned or downsampled set of items, whose cardinality is much smaller than M . We use a differentiable version of the Cholesky-based DPP sampling algorithm [20,28] on this thinned set of items. When downsampling the items, the first step is to select the number of items that will be kept using a Poisson sampling step, followed by a multinomial sampling step that selects the items that will be included in the downsampled set. Finally, a Bernoulli sampling step is used to perform rejection sampling, in order to ensure that the final exact DPP sample will be contained within the downsampled set.
Our differentiable DPP-VFX sampling algorithm is presented in Algorithm 2, where β is a kernel rescaling parameter that ensures that the Poisson parameter (s * e s/q ) is equal to the catalog size M . Differentiable versions of the Poisson, multinomial, Bernoulli, and Cholesky-based samplers invoked by Algorithm 2 are shown in Algorithm 3, Algorithm 4, Algorithm 5, and Algorithm 6, respectively. Input: λ, temperature τ STEP 1: {Truncate the total support and compute the probabilities of the integers from 1 to 2 * λ} massLogProb ← log(Poisson λ (i)) for i in [0, ..., 2 * λ] STEP 2: {Differentiable sampling using the Gumbel Softmax trick over the massLogProb log mass probability distribution} oneHotSample ∼ GumbelSoftmax τ (massLogProb) STEP 3: {Rearrange the one-hot-vector sample into the desired output format using matrix operations} sstPoissonSample ← I· oneHotSample return sstPoissonSample

A.1 Gumbel-Softmax trick
Our differentiable DPP sampling approach relies on the Gumbel-Softmax reparameterization trick [13], which is an efficient gradient estimator that replaces the non-differentiable sample from a discrete distribution with a differentiable sample from a Gumbel-Softmax distribution. The Gumbel-Max trick provides a simple and efficient way to draw samples z from a discrete distribution with where g 1 ...g k are i.i.d samples drawn from Gumbel(0, 1). The softmax is used as a continuous, differentiable approximation to argmax, and generates k-dimensional sample vectors y ∈ ∆ k−1 , where each component y i is: where τ is the temperature hyperparameter. As the softmax temperature τ approaches 0, samples from the Gumbel-Softmax distribution become one-hot and the Gumbel-Softmax distribution becomes identical to the categorical distribution p(z). Table 1 We perform a grid search using a held-out validation set to select the best performing hyperparameters for each model and dataset. The hyperparameter settings used for each model and dataset are described below.

B Hyperparameters for experiments in
Baseline MLE SDPP [7]. For this model, we use K for the number of item feature dimensions for the symmetric component V , and α for the regularization hyperparameter for V . We use the following hyperparameter settings: • All datasets: K = 30, α = 0, batch-size = 200.
Baseline MLE NDPP [9]. For this model, to ensure consistency with the notation used in [9], we use D to denote the number of item feature dimensions for the symmetric component V , and D to denote the number of item feature dimensions for the nonsymmetric components, B and C. As described in [9], α is the regularization hyperparameter for the V , while β and γ are the regularization hyperparameters for B and C, respectively. We use the following hyperparameter settings: • All datasets: D = D = 30, α = β = γ = 0, batch-size = 200.
During WDPP training, we anneal both the learning rate and α. Fig. 2 shows a plot of the kernels learned by the MLE SDPP and WDPP models for the Amazon feeding dataset. We see more apparent structure in the WDPP kernel, suggesting that our Wasserstein learning approach allows the DPP to capture more structure from the data than when trained using MLE. In Fig. 3 we compare a portion of the empirical marginal item distribution with the marginals captured by the MLE SDPP and WDPP models when trained on the Amazon diaper dataset. We see that WDPP appears to learn a better approximation of the true marginal distribution of the items in the data. Finally, Table 2 shows a collection of some of the most common non-singleton subsets (modes) from the test set, and samples generated by the WDPP, SDPP, and NDPP models, for the Amazon apparel dataset. Compared to the DPPs trained by MLE, we see that our WDPP model generates subsets that are much closer to subsets found in the empirical test set.