Determinantal Point Processes (DPPs) provide an elegant and versatile way to sample sets of items that balance the point-wise quality with the set-wise diversity of selected items. For this reason, they have gained prominence in many machine learning applications that rely on subset selection. However, sampling from a DPP over a ground set of size N is a costly operation, requiring in general an O(N^3) preprocessing cost and an O(Nk^3) sampling cost for subsets of size k. We approach this problem by introducing DppNets: generative deep models that produce DPP-like samples for arbitrary ground sets.   We develop an inhibitive attention mechanism based on transformer networks that captures a notion of dissimilarity between feature vectors.   We show theoretically that such an approximation is sensible as it maintains the guarantees of inhibition or dissimilarity that makes DPP so powerful and unique.   Empirically, we demonstrate that samples from our model receive high likelihood under the more expensive DPP alternative. Selecting a representative sample of data from a large pool of available candidates is an essential step of a large class of machine learning problems: noteworthy examples include automatic summarization, matrix approximation, and minibatch selection. Such problems require sampling schemes that calibrate the tradeoff between the point-wise quality -e.g. the relevance of a sentence to a document summary -of selected elements and the set-wise diversity 1 of the sampled set as a whole.Determinantal Point Processes (DPPs) are probabilistic models over subsets of a ground set that elegantly model the tradeoff between these often competing notions of quality and diversity. Given a ground set of size N , DPPs allow for O(N 3 ) sampling over all 2 N possible subsets of elements, assigning to any subset S of a ground set Y of elements the probability DISPLAYFORM0 where L ∈ R N ×N is the DPP kernel and L S = [L ij ] i,j∈S denotes the principal submatrix of L indexed by items in S. Intuitively, DPPs measure the volume spanned by the feature embedding of the items in feature space (Figure 1 ). BID31 to model the distribution of possible states of fermions obeying the Pauli exclusion principle, the properties of DPPs have since then been studied in depth BID19 BID6 , see e.g.). As DPPs capture repulsive forces between similar elements, they arise in many natural processes, such as the distribution of non-intersecting random walks BID22 , spectra of random matrix ensembles BID37 BID13 , and zerocrossings of polynomials with Gaussian coefficients BID20 ). More recently, DPPs have become a prominent tool in machine learning due to their elegance and tractability: recent applications include video recommendation BID10 , minibatch selection BID46 , and kernel approximation BID28 BID35 .However , the O(N 3 ) sampling cost makes the practical application of DPPs intractable for large datasets, requiring additional work such as subsampling from Y, structured kernels (Gartrell et al., (a) (b ) ( c) φ i φ j Figure 1 : Geometric intuition for DPPs: let φ i , φ j be two feature vectors of Φ such that the DPP kernel verifies L = ΦΦ T ; then P L ({i, j}) ∝ Vol(φ i , φ j ). Increasing the norm of a vector (quality) or increasing the angle between the vectors (diversity) increases the volume spanned by the vectors BID25 , Section 2.2.1).2017; BID34 , or approximate sampling methods BID2 BID27 BID0 . Nonetheless , even such methods require significant pre-processing time, and scale poorly with the size of the dataset. Furthermore , when dealing with ground sets with variable components, pre-processing costs cannot be amortized, significantly impeding the application of DPPs in practice.These setbacks motivate us to investigate the use of more scalable models to generate high-quality, diverse samples from datasets to obtain highly-scalable methods with flexibility to adapt to constantly changing datasets. Specifically , we use generative deep models to approximate the DPP distribution over a ground set of items with both fixed and variable feature representations. We show that a simple, carefully constructed neural network, DPPNET, can generate DPP-like samples with very little overhead, while maintaining fundamental theoretical properties of DPP measures. Furthermore, we show that DPPNETs can be trivially employed to sample from a conditional DPP (i.e. sampling S such that A ⊆ S is predefined) and for greedy mode approximation. We introduced DPPNETs, generative networks trained on DPPs over static and varying ground sets which enable fast and modular sampling in a wide variety of scenarios. We showed experimentally on several datasets and standard DPP applications that DPPNETs obtain competitive performance as evaluated in terms of NLLs, while being amenable to the extensive recent advances in speeding up computation for neural network architectures.Although we trained our models on DPPs on exponentiated quadratic and linear kernels; we can train on any kernel type built from a feature representations of the dataset. This is not the case for dual DPP exact sampling, which requires that the DPP kernel be L = ΦΦ for faster sampling.DPPNETs are not exchangeable: that is, two sequences i 1 , . . . , i k and σ(i 1 ), . . . , σ(i k ) where σ is a permutation of [k], which represent the same set of items, will not in general have the same probability under a DPPNET. Exchangeability can be enforced by leveraging previous work BID45 ; however, non-exchangeability can be an asset when sampling a ranking of items.Our models are trained to take as input a fixed-size subset representation; we aim to investigate the ability to take a variable-length encoding as input as future work. The scaling of the DPPNET's complexity with the ground set size also remains an open question. However, standard tricks to enforce fixed-size ground sets such as sub-sampling from the dataset may be applied to DPPNETs. Similarly, if further speedups are necessary, sub-sampling from the ground set -a standard approach for DPP sampling over very large set sizes -can be combined with DPPNET sampling.In light of our results on dataset sampling, the question of whether encoders can be trained to produce encodings conducive to dataset summarization via DPPNETs seems of particular interest. Assuming knowledge of the (encoding-independent) relative diversity of a large quantity of subsets, an end-to-end training of the encoder and the DPPNET simultaneously may yield interesting results.Finally, although Corollary 1.1 shows the log-submodularity of the DPP can be transferred to a generative model, understanding which additional properties of training distributions may be conserved through careful training remains an open question which we believe to be of high significance to the machine learning community in general.A MAINTAINING LOG-SUBMODULARITY IN THE GENERATIVE MODEL THEOREM 2. Let p be a strictly submodular distribution over subsets of a ground set Y, and q be a distribution over the same space such that DISPLAYFORM0 Then q is also submodular.Proof. In all the following, we assume that S, T are subsets of a ground set Y such that S = T and S, T ∈ {∅, Y} (the inequalities being immediate in these corner cases).
We approximate Determinantal Point Processes with neural nets; we justify our model theoretically and empirically.
{"src": "scitldr-AIC_train", "paper_id": "B1euhoAcKX"}