Deep Learning of Determinantal Point Processes via Proper Spectral Sub-gradient
Authors: Tianshu Yu
Yikang Li
Baoxin Li
Venue:  (2020)
Keywords: determinantal point processes
deep learning
optimization

Abstract: Determinantal point processes (DPPs) is an effective tool to deliver diversity on multiple machine learning and computer vision tasks. Under deep learning framework, DPP is typically optimized via approximation, which is not straightforward and has some conflict with diversity requirement. We note, however, there has been no deep learning paradigms to optimize DPP directly since it involves matrix inversion which may result in highly computational instability. This fact greatly hinders the wide use of DPP on some specific objectives where DPP serves as a term to measure the feature diversity. In this paper, we devise a simple but effective algorithm to address this issue to optimize DPP term directly expressed with L-ensemble in spectral domain over gram matrix, which is more flexible than learning on parametric kernels. By further taking into account some geometric constraints, our algorithm seeks to generate valid sub-gradients of DPP term in case when the DPP gram matrix is not invertible (no gradients exist in this case). In this sense, our algorithm can be easily incorporated with multiple deep learning tasks. Experiments show the effectiveness of our algorithm, indicating promising performance for practical learning problems. 

Published as a conference paper at ICLR 2020
DEEP LEARNING OF DETERMINANTAL POINT PRO- CESSES VIA PROPER SPECTRAL SUB-GRADIENT
Tianshu Yu, Yikang Li, Baoxin Li Arizona State University
(tianshuy, yikangg 1i, baoxin 1i)aaau.
ABSTRACT
Determinantal point processes (DPPs) is an effective tool to deliver diversity in multiple machine learning and computer vision tasks. Under the deep learning framework, DPP is typically optimized via approximation, which is not straight- forward and has some conflicts with the diversity requirement. We note, however, there have been no deep learning paradigms to optimize DPP directly since it involves matrix inversion that may result in computational instability. This fact greatly hinders the use of DPP on some specific objective functions where DPP would otherwise serve as term to measure the feature diversity. In this paper, we devise simple but effective algorithm to optimize the DPP term directly through expressing with L-ensemble in the spectral domain over the gram matrix, which is more flexible than learning on parametric kernels. By further taking into account ad- ditional geometric constraints, our algorithm seeks to generate valid sub- uub-gradients of the DPP term in cases where the DPP gram matrix is not invertible (no gradients exist in this case). In this sense, our algorithm can be easily incorporated with multiple deep learning tasks. Experiments show the effectiveness of our algorithm, indicating promising performance for practical learning problems.
INTRODUCTION
Diversity is desired in multiple machine learning and computer vision tasks (e.g., image hashing (Chen et al. 2017 Carreira-Perping & Raziperchikolaci, 2016)), descriptor learning (Zhang et al. 2017). metric learning (Mishchuk al. (017)) and video summarization (Sharghi et 2018 Liu et al. 2017)), in which sub-sampled points or learned features need to spread out through a specific bounded space. Originated from quantum physics, determinantal point processes (DPP) have shown its power in delivering such properties (Kulesza et al.] 2012] Kulesza & Taskar 201 Compared with other diversity-orient orienteed techniques (e.g., entropy (Zadeh et al. 2017)) and orthogonality (Zhang al. 2017)) DPP shows its superiority it incorporates only one single metric and delivers genuine diversity on any bounded space (Kulesza et al. 2012, Affandi et al. [2013] Gillenwater et al. 2012))
Therefore, DPP has been utilized in a large body of diversity-orienter tasks.
In general, sample points from a DPP tend to distribute diversely within a bounded space A (Kulezza al. 2012). Given a positive semi-definite kernel function : A x A IR, the probability of discrete point set X' C A under a DPP with kernel function i can be characterized as:
(x( x det(Lx)
where L is a |X| x |X') matrix with entry L,j = x(), and x, E X. L is called L-ensemble. Note that A a continuous space, whereas X' is finite. the Hilbert space associated with k. larger determinant implies larger spanned volume, thus the mapped points tend not to be similar or linearly dependent.
DPP can be viewed from two perspectives: sampling and learning. A comprehensive introduction to mathematical fundamentals of DPP for sampling from a discrete space can be found in Kulesza et al. (2012). Based on this, a line of works has been proposed (Kulesza & Taskar 201 [a] Kang 2013; Hennig & Garnett, 2016). In this paper, we concentrate on learning DPPs. In learning of DPP, the term det(L) is typically treated
singleton diversity measurement and is extended to learning paradigms on continuous space (Chao et al.] [015]] Kulesza & Taskar 2010 Affandi et al. 2014).
There generally two lines of strategies to leam DPPs:

---

Published as a conference paper at ICLR 2020
Approximation. This type of methods is to convert DPP into simpler format which can ease and stabilize the computation. low-rank approximation proves powerful in easing the computational burden (Gartrell et al. 2017), in which the gram matrix is factorized as L BB where B E R with m. < n. This decomposition can also reduce the complexity which is originally a cubic time of L| Kulesza & Taskar (201 explicitly expressed the kemne with <(x, y) 01)2 8(y), where measures the intrinsic quality of the feature and 6(-) is function mapping input x to feature space. In this sense, the pairwise similarity is calculated in Euclidean feature space with cosine distance. Elfeki et al. (2019) suggest approximating given distribution by approximating the eigenvalues of the corresponding DPP. As such, the computation can be eased and become stable. Following this, DPP is also applied on some visual tasks, such as video summarization (Sharghi et al., 2018), ranking (Liu et al. (017) and image classification (Xie et al. 2017). It can be noted that the approximation is not straightforward for DPP, thus cannot fully deliver the diversity property (e.g. resulting in -enkdeficcency).
Direct optimization. While the aforementioned methods optimize DPP with specific approximation. a series of efforts also seek to optimize the DPP term directly (Gillenwater et al.] 2014 Mariet &
Sra 2015; Bardenet & Titsias 2015). In this setting, the whole gram matrix L corresponding the pairwise similarity among features is updated directly, which allows accommodating more flexible feature mapping functions rather than approximation. Gillenwater et al. (2014) proposed an
Dnpectation-Maximizan
algorithm to update marginal kernel DPP K
together
with baseline K-Ascent derived from projected gradient ascent (Levitin & Polyak 1966).
Mariet &
Sra 2015)) extended DPP from a fixed-point perspective and Bardenet & Titsias 20155) proposed
to optimize DPP upon a lower bound in variational inference fashion. A key problem of such line
of works is that the computation is not differentiable, making it difficult to be used in deep learning frameworks.
To the best of our knowledge, there is no previous method incorporating DPP as a feature-level diversity metric in deep learning. A key difficulty in doing so is that the calculation of the gradient of (L) involves matrix inversion, which can be unstable and inaccurate in GPUs. Though K- Ascent seems to be a naive rule, it still needs explicit matrix inversion in the first step before the projection procedure. This fact greatly hinders the tight integration of DPP with deep networks. Some alternative methods seek to reach diversity under more constrained settings. For example, Zhang et al. (201)) resorted to global pairwise orthogonality constraint in hyper-sphere and Zadeh et al. (2017) employed statistical moments to measure the diversity. However, compared with DPP, such measurements are unable to fully characterize diversity in an arbitrary bounded space.
In this paper, rather than providing more efficient DPP solvers, we concentrate on delivering a feasible feature-level DPP integration under the deep learning framework. To this end, we revisit the spectral decomposition of DPP and propose a sub-gradient generation method which can be tightly integrated with deep learning. Our method differs from either approximation or direct optimization by introducing a "differentiable direct optimization" procedure, thus can produce genuinely diverse features in continuous bounded space. Our method is stable and scalable the relatively large dataset with a specific mini-batch sampling strategy, which is verified by several experiments on various tasks.
Notations: Bold lower case and bold upper case K represent vector and matrix, respectively. (.) and (r(-) calculate the determinant and trace of a matrix, respectively. @ B is the element-wise product of matrices A and B. |X] and |x] measure the cardinality of finite set X and the L length of a vector x, respectively. (x, y) calculates the inner product of the two vectors. x = diag (X) transforms diagonal matrix X into its vector form x, and vice versa. We refer "positive semi-definite" and "positive definite" to PSD and PD, respectively. Denote the real numbers.
2 BACKGROUND
2.1 DETERMINANTAL POINT PROCESS
L-ensemble expression of DPP requires L to be PSD, whereas kernel expression further constrains K < I (each eigenvalue of K is less than 1). A conversion from to K can thus be written as
K L(L + I) -1 following the truth Σx (Lx)) = det(L + I), which is the marginal normaliza- tion constant given specific L. While there is always conversion from L to K, the inverse may not
2

---

Published as a conference paper at ICLR 2020
exist (Kulesza al. 2012). In practice, one may construct L-ensemble first, then normalize it into marginal kernel. This fact may give rise to the difficulty of deep networks. Since a conversion from K to L might not exist, the network needs carefully adjusting the gradients under specific constraints to ensure the updated L to be valid. As L and K share the same eigenvectors vi, a pair of L and K holds the relation:
K EXTTE = L=
X - V.V!
where X is the ith eigenvalue. It is seen that such conversion is not straightforward to be directly integrated with deep learning framework. Therefore, we optimize ensemble L directly in this paper.
2.2 GAUSSIAN KERNEL
We briefly introduce Gaussian kernel in this section, which works on Hilbert space with infinite dimension. Mercer's 's theorem Friedman et al. (2001) ensures the PSD properties when constructing new kernels with existing ones under a specific procedure. Such procedure also employed in multiple kernel learning paradigms (Affandi et al., 2014, Kulesza & Taskar 2201 Chao et al. 2015). which is out of the scope of this paper. A Gaussian kernel is defined as x(x,,, = exp X; - x,l²/o* where a controlling parameter. Thus an L-ensemble matrix becomes Ly <(x;, X,). According to the definition, L and for any element in the matrix we have Ly E (0, 1]. With Gaussian kernel, we have a nice property 0 < (L) S 1. This can be easily verified by applying geometrie inequality to the eigenvalues of L. Although not tight, this property shows that the determinant value with Gaussian kernel is bounded. This fact inspires version of our algorithm detailed in the next section. Throughout this paper, our discussion is based on the Gaussian kernel unless specified.
3 METHOD
Given vectorized inputs 1, Rhth where 1, ..., n. our goal is to learn map f such that the features X; f[I,) can spread out within bounded feature space S. Hereafter we refer space to an Euclidean bounded space (e.g.. [-1, 1]d) without loss of generality. Given any loss function J, the chain rule of gradient involving DPP is written as:
de) dL OJ det
AJ
(3)
OL
0X
where X refer to the features before DPP layer. While calculating det(L) and 0L/0X is straightforward, the main difficulty lies on the calculation of a (et We will discuss the calculation of this term under two case: 1) When the inversion - can be stably obained, we will derive the gradient of DPP det(L) on Sec 3.1, When L is not invertible or L is difficult to calculate, we give the procedure to handle the case by generating valid sub- sub-gradient in Sec Since our objective is to diverse features, (L)(L) will serve as a (partial) objective term to be directly maximized.
Algorithm DPPSG
Input: K. tolerance A; Output: K
Algorithm DPPSG*
UAUT +
(01 on) t- diag(K)
Input: K, tolerance 0; Output: K UAUT
ior in {1, {1...., n do
K
if [a; A then
(AI...., on) + diag (K)
σ. A A
b = (1 ()(1), Tn) - 0(1, 1).
end if end for
À + diag(b)
K + UÂU
À diag(o 0n)
K K-K K
K + UÂUT
K+ K K-K K
3

---

Published as a conference paper at ICLR 2020
3.1 DERIVATION OF GRADIENT
With kernel K, a DPP regularization term seeks to maximize the possibility of a feature configuration X5, I,..., nt. As this possibility is proportional del(LL, the objective is max del This can become a regularization term where diversity is required. Thus with a general loss function LG. our aim is solve min LG X1 det (L), with the controlling parameter Å 2 0. For the time being, we assume that kernel matrix L is invertible (we will discuss the case when L is not invertible in the next section), hence L - exists. Without loss of generality, we discuss the gradient of the determinant equipped with Gaussian kernel. For other kernels the derivation is analogous. According to Eq (??), Lij can further factorized as:
Lg - exp ( Ex(x - x,1)²
(-En(xy
(4)
x²
where Xiy is the jth dimension of feature X₃. Using chain rule, the derivative of det(L) w.r.t. X can be written as:
0 dde((L) det(L) L ØL
(5)
0x,
0x,1
where the ijth position of OL the corresponding element is:
Txa
- (
x; a²
2(xx Xz1) σ²
exp
(6)
0xH1
Eq 66 be more compactly expressed as:
0L L @ M (i))
0x
where (a is such matrix that, except for the ith column and row, all resting elements are Os. Besides, the ijth and jith elements of M are both 2(x11xx,)) In summary, Eq ( can be
simplified as:
i det (L) = det(L) Tr (L-1 (L (L
(8)
0xæ
To ease the computation and fully utilize the chain rule in deep learning architecture, we peel the DPP loss into two layers, and the corresponding gradient product can be expressed as:
i dLt(LL)
ÖL
(9)
0x
While we can use existing package to obtain OL 0xx reliably, the way to stably calculate (ee((L)/L becomes essential. We will detail in the next section once the term is hard calculate.
3.2 PROPER SPECTRAL SUB-GRADIENT FOR PACK-PROPAGATION
The calculation of the gradient deet L/ØL involves computing the inverse matrix L- However, the kernel matrix not always invertible. This situation happens iff there exists at least pair of features and x, such that eigenvalue results the non-invertibility. This phenomenon is sometimes caused by Relu function, which can map different input values onto an identical one. Even when all features are distinct, the numerical precision (typically on float number GPU) may also lead to failure. We occasionally observed that GPU caleulation of L reports error even eigenvalue is 0. One may imagine a naive replacement of matrix inverse with the pseudo-invert matrices. However, iecudo-inverse will keep the zero eigenvalues intact (still rank -ankddeiicinccy,, and the back- propaparpd gradient will play no part to increase the determinant value (both 0 before and after updates).
X,. In this case, there exist two identical columns/rows of L and the
which can be applied on singular
To address this, we first diverge to consider the objective of DPP max det Since DPP term seeks to maximize the determinant, for configuration (t) at iteration with det (L) = 0, any sufficiently small n sufficing (++(1))+) > 0 with = (t+1) ())) can be a valid ascending direction. Thus give the following definition:
4

---

Published as a conference paper at ICLR 2020
(a)
(b)
Figure 1: (a)-(c): feature distribution of MNIST dataset under different settings. Left and right for training and testing samples, respectively. (a) Contrastive loss for metric learning; (b) Contrastive loss + DPP regularization; (c) Contrastive loss DPP regularization + WGAN regularization. For (c), the features are generally lying in the space [-1 1. 1|2. Zoom in for better view.
Definition 3.1. Proper Sub- Sub-gradient: For PSD matrix L such that det(L) = L is called its proper sub-gradient if L is gra-ggrdient and det + aLL) for sufficiently small a
We see if proper sub- sub-gradient L can be found at det 0, back pack-propagation procedure in deep learning can consequently perform calculation using L. To obtain such L, we first note that L can be cigen-decomposed as following since it is symmetric and PSD:
L UAU
(10)
where U is the orthogonal eigenvector matrix and A's diagonal elements are the corresponding eigenvalues, As has zero eigenvalues, the rank of A is lower than the dimension of L. We sort all cigenvalue into descending order to k (01, .... Ty. O.... 0), where < n. We then employ a simple yet effective amplification procedure by amplifying any eigenvalue smaller than A A.
The amplified eigenvalues are now k = (Ø1,.... xx; A, .... A), where S q. Let the diagonalized amplified eigenvalue matrix be A (w.rt. k), then the modified matrix with small positive determinant can be written as:
L = UAU
(11)
Now that det = - A >>D O. For any O, we can choose a sufficiently small A such that dL) < e. Thus the continuity of this procedure is guaranteed. The difference L. can be viewed proper ascending direction w.r.t. L, by adding L, det(L + É) becomes above 0 well arbitrarily small. It is trivial to prove that L is sub-grade uub-gradient also a proper sub- sub-gradient sufficing Definition 3.1 This procedure is summarized Algorithm and encountering identical too close feature pair x, and Xj.
neighbor of L. thus L is
termed DPPSG. Intuitively, this procedure tries to enhance the diversity by separating them apart from each other.
Inspired by geometric inequality, we provide improved version of the algorithm taking into account the property of Gaussian kernel. First it easy to show that the function II, a is concave in the n)) and the maximal
feasible set Σ, 0, (diagonal of Gaussian gram matrices are 1s, thus objective is reached out iff 0; = Therefore, any point b = (1 (o....... o₂) + 0(1,..., 1) will increase the objective II, ø,. By letting 0 being a small value, the proper uub-gradient becomes Udiag(b- G)UT, where o (oI....,,,)) This version of update differs from DPPSG as generates sub- gradients under geometric constraints. The method is summarized in Algorithm 2 and termed DPPSG*
During implementation, the irregularity of L is examined to determine whether to adopt normal back paekppropagation (in See 3.1) or sub-gradient (in See 3.2). This can be done by verifying the determinant value in the forward pass is less than pre-defined small value 3. This proper sub- gradient based back peckprroaggttion method can be used to integrate to deep learning framework with other objectives involving matrix determinant. We emphasize that method is different from based methods, such as K-Ascent. While projection based methods
the line of gradient-projectto calculate the true gradient then project it back to a feasible set, methods generate proper sub- gradient directly. Without explicitly computing matrix inversion, sub-grade gradicnts, in this case, is more feasible for deep learning framework.
5

---

Published as a conference paper at ICLR 2020
Mini-batch sampling We employed balanced sampling strategy for each mini-batch. Assuming the batch size is n and there are с classes in total, in each mini-batch the distribution samples generally follows the whole training sample distribution utilize the intrinsic diversity of the original data. Besides, mini-batch sampling can constrain the overhead of DPP computation depending only the batch size, which can be viewed constant in practice.
classes. This strategy is considered to
3.3 BOUNDING THE FEATURES WITH WASSERSTEIN GAN
Practically, the features are always required to lie a bounded space. This essential in some applications as bounded space is more controllable. Especially, sometimes one may demand that the features should suffice to pre-defined distribution P. This bounding requirement crucial to the objective of DPP since maximizing determinant tends to draw feature points infinitely apart from each other. naive method to achieve this is to truncate the features or using barrier functions. However, these methods will result in irregularly dense distribution boundary. To overcome this issue, we employ Wasserstein GAN (WGAN) Arjovsky et al. (2017) to enforce the features mapped specific distribution P. As we do not focus WGAN in this paper, readers are referred to Arjovsky et al. (2017) for more details.
the learned feature space
To this end, we randomly sample 7 points &; from the distribution under balanced sampling, which are treated as positive samples. The generator f(-) takes a feature as input and outputs the corresponding embedding. Denote the discriminator h(-) (which is also the mapping from input to feature). Then the WGAN loss for discriminator is:
Lw = Ex-P [x) EI-p(r) [k(f(I)]
(12)
According to the Arjovsky et al. 2017), we incorporate the generator loss Le -E))(((T)] into general loss LG and obtain L LG L + >2Lc, where A > and X2 > are controlling parameters and Lp is the DPP term. In general, the second and third losses serve as regularization. While the DPP term Lp makes the points spread out over the whole space, the WGAN term Lw enforce the points to be under distribution P. These two terms set to negative maximize them. the implementation, Lw and L are trained alternatively.
seek to
mAP-k(%)
mAP-K(%)
10
20
50
100
b-size
10
20
50
baseline
63.90
62.87
61.43
58.65
200
30.50
31,28
32,49
DPPSG
67.22
67.45
65.82
62.78
300
30.78
32.27
32.29
DPPSG*
67.94
68.73
66.32
62.75
400
31.44
33.46
33.51
DPPSG+WGAN
68.07
69.34
66.19
63,40
500
33.97
34.49
35.38
DGPSG*+WGAN
69. 14
70.32
68.04
64.58
Table 2: Impact of batch size (b- size) in CIFAR-100 100 classes
Table 1: Retrieval performance MNIST.
4 EXPERIMENTS
In this section, we conduct two experiments. One is about metric learning and image hashing on MNIST and CIFAR verify the effectiveness of our method, while another is for local descriptor retrieval task based on HardNet (Mishchuk et al. 2017). For the first test.
4.1 VERIFICATION TEST
MNIST This simple dataset is suitable reveal the geometric properties of the features on various
tasks. We test the image retrieval task equipped with contrastive loss I.c = E=()= (x; - xx,)²
E0())00) max (μ (x, x,)².0) under Gaussian DPP regularization, where L(i) indicates the label of the ith feature and x; is the learnt feature. We employ simple network structure for
We choose the batch size for simplicity. One can change this value.

---

Published as a conference paper at ICLR 2020
(a) DPP+WGAN
(b) Lin et al 2015
(c) Binary code histogram
Figure 2: Visualization of 16-bit bit hashing code results on CIFAR- 10. For (c) the histograms up and
down correspond to DPP+WGAN and et al. 2015), respectively. Zoom in for better view.
MNIST. This network consists of 3 convolutional layers (Conv) followed by 2 fully connected layers (FC). Batch normalization (loffe Szegedy, (015) is applied on each layer. The filter number of each Conv are 32, 32 and 64, respectively. The sizes of the filter are identically 5 x 5. For the first Conv, we employ maxpooling. For the other 2 Convs, average pooling is adopted. The dimensions of the last FCs are 200 and 2 (for 2D visualization).
The performance can be found Table I and the feature distribution is visualized in Figure ! From Table I it is observed that the performance retrieval task can be enhanced by adding the DPP and WGAN regularization terms. We see that DPP term can enhance the retrieval performance by avoiding feature points from concentrating too much. In this sense, the learned map around the separating boundary can be much smoother. As retrieval task typically requires the existence of top-k inter-class samples rather than concentrating property, the DPP term is more preferable. In Figure [fc), we see that the feature points generally fall into the pre-defined space 1J The utility of such space is high without sacrificing the retrieval performance. Typically, DPPSG* is slightly superior to DPPSG. Thus in the following test, we only report the performance under DPPSG* setting (termed as DPP* for short).
CIFAR-10 image hashing We conduct image hashing on CIFAR-10 10 which seeks to produce binary code for images. To this end, we follow the binary hashing code generation procedure in Lin et al. (2013) which is activated by Sigmoid function. The number of neurons in the second last layer equals to the number of bits of the hashing codes. is anticipated that DPP regularization can enhance the utility in binary code space since the code can spread out We test two lengths of binary code (12 and 16). We visualize the 16-bit fcature distribution using TSNE (Maaten & Hinton 2008) in Fig. (a) and (b), and the binary code histogram comparison in (c). The quantitative results summarized in Table 2 As Lin et al. (2155) jointly solve binary code generation and classification, report both retrieval performance (mAP) and classification performance (Acc). We our method can significantly enhance the binary space utility while keeping the performance almost intact.
CIFAR-100 metric learning We employ all the convolutional layers in VGG-19 (Simonyan & Zisserman 2014) as the base and discard its final fully connected layers. Thus the output size of this base VGG- 19 network is x 512. We concatenate 3 fully connected layers with ReI.U activation on each after that with dimensions 512, 100 and 20, respectively. Contrastive loss is applied on the 20-dimensional space. We train the whole network from scratch. Aside from mAP, we also report top-k average precision (Precision-k) and the Wasserstein distance to the pre-defined distribution (Gap to P). The performance on coarse (20 classes) and fine (100 classes) levels can be found in Table 3 In either setting, we see that DPP+WGAN significantly outperform the baseline. Thus infer that the DPP term can serve as a regularization not only for the feature itself but also for the smoothness of the mapping. Since the DPP term avoids the features from concentrating too much, the learned mapping should also be from a smoother function family.
Batch size VS. performance We study how batch size influences the performance with DPP regu- larization. To this end, we report the performance on CIFAR- 100 100-class retrieval with different batch sizes. The results are shown in Table 2 Generally, with larger batch size, the algorithm can reach out better mAP. We note the computational efficiency of DPP sub- gradients is high, which adds
Higher binary code space utility can enhance the hashing speed and save the storage.
7

---

Published as a conference paper at ICLR 2020
very slight overhead (even with 500 batch size) to each iteration of common back-propase bock-propagation under contrastive loss, which can be neglected.
& (%)
Precision-H & (%)
Gap to P
10
20
50
10
20
50
mAP-k (%)
Acc
k
50
On coarse (20) classes
12- bit
Baseline
6.98
6.74
6.82
9.44
9.36
9.35
DCH
82.9 83.9 85.9
83.5
DPP*
45.35
48.09
48.74
55.62
53.04
51.08
DPP
81.7 81.9 81.7 89.9
DPPW"
47.30
52.18
54.37
60.60 58.44
57.39
0.046
16-bit
On fine (100) classes
DCH
84.9 85,4
86.7
92.0
Baseline 17.98
18.24
18.06
23.21 23.47
22.76
DPP 83.9 83.7 82.9 91.5
DPP# 28.43
28.49
28.37
35.18
34.79
33.26
DPPW*
30.50
31.28
32.49
40.15 40.76
38.36
0.032
Table 4: Image hashing CIFAR- 10. "Acc" is the classification accu- racy.
Table 3:
Metric learning performance on CIFAR 100 dataset with course (20) and fine (100) classes.
4.2 LOCAL DESCRIPTOR RETRIEVAL
This test utilizes the UBC Phototour dataset (Brown & Lowe 2007). which consists of three subsets (Liberty, Notre Dame, and Yosemite) with around 400k 64 x 64 local patches for each. We follow the protocol Mishchuk et al. (2017) to treat two subsets the training set and the third one as the testing set. As each pair of matched image patches includes only two patches, there is no need to apply balanced sampling in this test. We simply add DPP regularization term the objective of state-of-the
algorithm HardNet (Mishchuk et al.] 2017). The batch size is 512. We report FPR (false positive rate) and FDR (false discovery rate) following Mishchuk al.) (2017); Han et al. (2155). Results are summarized in Table(5) Several baselines are selected for comparison (i.e. SIFT Lowe 1999). MatchNet (Han et al. 2015). TFeat-M (Balntas al. 2016). L2Net (Tian et 2017) and HardNet (Mishchuk et al. (2117)) As the authors improved HardNet after the NeurIPS submission, we also compare with the latest version (termed as HardNet+). We only conduct our method under DPPSG* setting and name our method HardDPP. We see that with DPP regularization, the performance HardNet can be further enhanced. Note that HardNet there is no WGAN integrated as the mapped features lie in the surface of hyper unit sphere. While the sampling strategy of HardNet emphasizes embedding behavior near the margin, DPP regularization can further focus global feature distribution.
Training Testing
Notre Yose Lib
Lib + Yose Notre
Lib Notre Yose
Mean
FDR
FPR
SIFT
29.84
22.53
27.29
26.55
MatchNet
7.04
11.47
3.82
5,65
11.6
8.7
7.74
8.05
TFeat-M
7.39
10.31
3.06
8.06
7.24
6.47
6.64
PCW
7.44
9.84
3.48
3.54
6.56
5.02
5,98
L2Net
3.64
5.29
1.15
1.62
4.43
3.3
3.24
HardNet
3.06
4.27
0.96
1.4
3.04
2.53
3.0
2.54
HardNet+
1.47
2.67
0.62
0.88
2.14
1.65
1.57
HardDPP 1.21
0.70
1.79
1.32
1.31
1.17
Table 5: Performance of UBC Phototour comparison. Notre, Yose and Lib are short for "Notre
Dame", "Yosemite" and "Liberty", respectively. Following HardNet Mishchuk et al. (011). report FPR at true positive rate at 95%. The best results are in bold.
CONCLUSION
In this paper, we investigated the problem of learning diverse features via a determinantal point process under deep learning framework. To overcome the instability in computing the gradient which involves the matrix inverse, we developed an efficient and reliable procedure called proper spectral sub-gra uub-gradient generation. The generated proper sub sub-gradient and performs well in applications. We also considered how to constrain the features into a bounded space, since in such way one ensure the behavior of the network more predictable. To this
replace the true gradient
8

---

Published as a conference paper at ICLR 2020
end, further incorporated Wasserstein GAN into framework. Together, DPP+WGAN showed significant performance on both some common criteria and feature space utility.
ACKNOWLEDGMENTS
The work was supported part by a grant from ONR. Any opinions expressed in this material are those of the authors and do not necessarily reflect the views of ONR.
REFERENCES
Raja Hafiz Affandi, Emily Fox, and Ben Taskar, Approximate inference in continuous determinantal processes. In NIPS, 2013.
Raja Hafiz Affandii Emily Fox, Ryan Adams, and Ben Taskar. Learning the parameters of determi- nantal point process kernels. In ICML, 2014.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. 1rXiv:1701.07880 2017.
Wasserstein
gan. arXiv preprint
Vassileios Balntas, Edgar Riba, Daniel Ponsa, and Krystian Mikolajezyk. Learning local feature descriptors with triplets and shallow convolutional neural networks. In BMVC, 2016.
Rémi Bardenet and Michalis Titsias. Inference for determinantal point processes without spectral knowledge. In NIPS, 2015.
Matthew Brown and David G Lowe. Automatic panoramic image stitching using invariant features. IJCV, 74(1):59-73, 2007.
Miguel A Carreira-Perpinán and Ramin Raziperchikolaci. An ensemble diversity approach to supervised binary hashing. NIPS, 2016.
Wei-Lun Chao, Boqing Gong, Kristen Grauman, and Fei Sha. Large-margin determinantal point processes. In UAI, 2015.
Yong Chen, Hui Zhang, Yongxin Tong, and Ming Lu. Diversity regularized latent semantic match for hashing, Neurocomputing, 230:77-87, 2017.
Mohamed Elfeki, Camille Couprie, Morgane Riviere, and Mohamed Elhoseiny. Gdpp: Learning diverse generations using determinantal point process. In ICML,, 2019.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning, volume 1. Springer series in statistics New York, 2001.
Mike Gartrell, Ulrich Paguet, and Noam Koenigstein. Low-rank factorization of determinantal point processes. In AAAI, 2017.
Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal map inference for determinantal point processes. In NIPS, 2012.
Jennifer A Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar. Expectation-maxxiiiation for learning determinantal point processes. In NIPS, 2014.
Xufeng Han, Thomas Leung, Yangqing Jia, Rahul Sukthankar, and Alexander C Berg. Matchnet: Unifying feature and metric learning for patch-based matching. In CVPR, 2015.
Philipp Hennig and Roman Garnett. Exact sampling from determinantal point processes. arXiv preprint
06840, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 150.00367. 2015.
Byungkon Kang. Fast determinantal point process sampling with application to clustering. In NIPS, 2013.

---

Published as a conference paper at ICLR 2020
Alex Kulesza and Ben Taskar. Structured determinantal point processes. In NIPS, 2010.
Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In JCML, 201 la.
Alex Kulesza and Ben Taskar. Learning determinantal point processes. In UAI, 201
Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 5(2-3):123-22) 226. 2012.
E. Levitin and B. Polyak. Constrained Mininization Methods. USSR Computational Mathematics and Mathematical Physics, 1966.
Kevin Lin, Huei-Fang Yang, Jen-Hao Hsiao, and Chu-Song Chen. Deep learning of binary hash codes for fast image retrieval. In CVPRW, 2015.
Juan Liu, Zhengyang Wu, and Fuxin Li. Ranking video segments with Istm and determinantal point processes. In ICIP, 2017.
David G Lowe. Object recognition from local scale-invarian features. In ICCV, 1999.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9Nov):2577--6655 2008.
Zelda Mariet and Suvrit Sra. Fixed-point algorithms for learning determinantal point processes. In ICML., 2015.
Anastasiia Mishchuk, Dmytro Mishkin, Filip Radenovic, and Jiri Matas. Working hard to know your neighbor's margins: Local descriptor learning loss. In NIPS, 2017.
Aidean Sharghi, Ali Borji, Chengtao Li, Tianbao Yang, and Boqing Gong. Improving sequential determinantal point processes for supervised video summarization. In ECCV, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXi 1559, 2014.
Yurun Tian, Bin Fan, and Fuchao Wu. 1.2-net: Deep learning of discriminative patch descriptor in cuclidean space. In CVPR, 2017.
Pengtao Xie, Ruslan Salakhutdinov, Luntian Mou, and Eric P Xing. Deep determinantal point process for large-scale multi-label classification. In ICCV, 2017.
Sepehr Abbasi Zadeh, Mehrdad Ghadiri, Vahab Mirrokni, and Morteza Zadimoghaddam. Scalable feature selection via distributed diversity maximization. In AAAI, 2017.
Xu Zhang, X Yu Felix, Sanjiv Kumar, and Shih-Fu Chang. Learning spread-out local feature descriptors. In ICCV, 2017.
A APPENDIX
A.1 PARAMETER SET-UP
MNIST Some parameters are set as follows: a == A1 = 103, Au = 10th margin = 0.8, variance for Gaussian kernel a 0.2 and A 10-7 During the training, the batch size each iteration of DPP and WGAN training, we uniformly sample 2, 000 adversarial points from the space [-1, We adopt RMSprop and the learning rate is 10-4 for tests. the testing stage, we sample 2, 000 points from [-1, 1 and calculate the Wasserstein distance with all the testing samples. This procedure conducted 10 times and the mean distance is reported.
200. In
CIFAR-10 image hashing The parameters in the hashing related experiments are used following: variance for Gaussian Kernel a = 2, the coefficients for the loss term of DPP is \₁ = 102 and for the loss term of discriminator and generator in WGAN is 10 and respectively. The batch size is set to 500 and the learning rate is initialized to 0.01 with a changing rate 0.1 at every 150 epoch. The total number of epoch is set to 350 and adopt the Adam optimizer update model.
10

---

Published as a conference paper at ICLR 2020
CIFAR-100 metric learning The parameter setting is as follows: a= 1, A 100, X2 10², margin = 0.8, variance for Gaussian kernel o = 0.2 and A = 10 The rest the settings are the same as those of MNIST test.
A.2 CRITERIA PRECISION-K AND MAP-K
For image retrieval task, we adopt the top-k mean average precision (abbreviated as mAP-k) to evaluate the performance. We also present the top-k average precision (abbreviated as Precision-k), which is calculated as:
(1) JKK- Σ P(b))
Precision( (b,)
(13)
where b is the corresponding class and is the indicator function:
1
if is true positive
T(bb)
(14)
0 if is a false positive
Thus mAP-k is the reweighted version of Precision-k:
mAP(b,) Precision 6,)(K @K
(15)
N
A.3 OVERHEAD OF DPP
Calculating SVD or matrix inversion on large number of features can be time consuming. However, in setting, employed common practice in deep learning mini-batch computation on a whole batch. We can conclude that mini-batch strategy can limit the computational cost such that the extra overhead of DPP only dependent on the batch size (thus other parts of the networks have no impact on this overhead). Therefore, although the complexity of our method is (n²)) only corresponds the batch size rather than whole sample number in our setting, which is much more manageable in practice. We report the average overhead comparison on CIFAR-10 10 hashing task with varying batch sizes (100, 200, 250, 400 and 500) on GTX 1080 GPU as Table
avoid such
6 (time in seconds):
batch size
100
200
250
400
500
overhead-all
0.175
0.263
0.308
0.411
0.493
overhead-DPP
0.011
0.029
0.033
0.042
0.056
Table 6: Overhead of a single batch and DPP calculation on CIFAR-I0 hashing task with varying batch size. Time in seconds.
where "overhead-ar all" and "overhead-De DPP"" refer to the average time cost (s) for single batch on all the computation and only DPP computation (both forward and backward), respectively. We can conclude that, compared to other computation, the extra overhead of DPP is small (even in simple network as CIFAR-10 hashing). Besides, a batch size up to 500 is considered be sufficient in most of the applications. In practice, we did not employ any trick to reduce such overhead (since it is out of the papers focus) but simply utilized standard functions provided by Pytorch.
A.4 SOME BASELINE DETAILS
For MNIST verification test, employed simple backbone. The structure of the back- bone (c5nv_1(5 5)+maxpool+conv_22 255 5)+avepool+conn_333 x +)+avepool+fullyyconn (2000- d)+fully ffullly (on3(10-)) loss) We add DPP and WGAN regularization to the features at "fully cco2"" layer, which is 2-dimensional thus better for visualization.
For CIFAR-10 image hashing task, employ the same network structure high-cited method DCH (Lin et al. 2015). DPP and WGAN loss is applied on the second last fully connected layer (the dimension of this layer corresponds the length of digits in the hashing code).
11

---

Published as a conference paper at ICLR 2020
For CIFAR-100 metric learning task, employ all the convolutional layers of VGG19, concate- nated with 3 fully connected layers (with 512. 100 and 20 dimension). DPP and WGAN loss, together with contrastive loss, is applied on the final fully connected layer (20-dimension). The network is trained from scratch without any pre-training.
A.5 DEGRADATION ON CIFAR-10 10 IMAGE HASHING
For the performance degradation with DPP on hashing task, we can take Figure (c) an example to explain. We see that original DCH features concentrate on several digits (generally 10 digits corresponding to 10 classes), while DPP features diffuse almost the whole discrete space. this sense, if one retrieves the k-th closest hashing code, DCH can find the hashing code with small searching radius. However, one has to greatly enlarge the search radius for k-th closest code DPP feature space since the distribution is much more even. In this sense, DPP will inevitably causes degradation since large searching radius will more likely to reach a code other class. Therefore, we think "utility mAP" is intrinsic conflict and needs to reach trade-off.
12


Reviews:
[{"review_id": "r1l215DtFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Determinantal Point Processes (DPPs) are statistical models that allow efficient sampling of diverse solutions - a problem that is hard with most machine learning modeling frameworks.  However, learning diverse features via DPPs with deep learning frameworks is challenging due the instability in computing the gradient which involves a matrix inverse operation. Better marriage between deep learning and DPPs is an important problem as diversity is crucial in many machine learning problems (even beyond computer vision - the experimental domain of this paper - e.g. in machine translation and document summarization). \n\nThe authors of this paper make several important contribution to this problem. First, they develop an effective sub gradient procedure, proper spectral subgradient generation,  that can replace the true gradient and empirically demonstrate its effectiveness in computer vision applications.  Then, they describe a method for constraining the DPP features into a bounded space to facilitate network predictability. When incorporating Wasserstein GAN into their framework they show performance gains in computer vision tasks: metric learning, image hashing and local descriptor\nretrieval task based on HardNet.\n\nThe paper is overall clearly written, but in some places it is not well edited (to the level that is should be carefully proofread). For example, \"For the first test.\" just before 4.1, and \"showed significance performance\" in the last sentence of the paper. I strongly encourage the authors to carefully edit the paper before publication so that their nice work will be properly presented.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Syl5iFwiKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: the authors introduce a method to learn a deep-learning model whose loss function is augmented with a DPP-like regularization term to enforce diversity within the feature embeddings. \n\nDecision: I recommend that this paper be rejected. At a high level, this paper is experimentally focused, but I am not convinced that the experiments are sufficient for acceptance.\n\n****************************\nMy main concerns are as follows:\n\n- Many mathematical claims should be more carefully stated. For example, the authors extend the discrete DPP formulation to continuous space. It is not clear to me, based on the choice of the kernel function embedding, that the resulting P_k(X) is a probability (Eq. 1). If it is not (using a DPP-based formulation as a regularizer does not require a distribution), the authors should clarify that fact; more generally, the authors should be more careful throughout the paper (for example, det=0 if features are proportional, not necessarily equal; the authors inconsistently switch between DPP kernel L and marginal kernel K throughout computations.)\n\n- The authors do not describe their baselines for several experiments. In tables 1, 2, 3, the baseline is never described (I assume it's the same setup without regularization); I did not find a description of DCH (Tab 4) in the paper (Deep Cauchy Hashing?). The mAP-k metric should also be defined. Furthermore, the authors do not report standard deviations for their experiments.\n\n- A key consideration when using DPPs is their compulational cost: most operations involving them require SVD (which seems to be used in this work), matrix inversion, and often both. This, unsurprisingly, limits the applications of DPPs, and has driven a lot of research focused on improving DPP overhead. I would like to see more discussion in this paper focused on to which extent the DPP's computational overhead remains tractable, and which methods were used (if any) to alleviate the computational burden.\n\n- Finally, the paper itself appears to be somewhat incomplete: sentences are missing or incomplete (Section 4), and numbers are missing in some tables (Table 5).\n\n\n***********************\nQuestions and comments for the authors:\n\n- When computing the proper sub-gradient, are you computing the subgradient as inv(L + \\hat L)?\n\n- You state that by avoiding matrix inversion, your method is more feasible. However, it seems like your method requires SVD, which is also O(N^3); could you please provide more detail for this?\n\n- Could you report number of trials and standard deviations for your experiments?\n\n- Do you have any insight into why DPPs do more poorly than the DCH baseline in Table 4 for mAP-k metrics?\n\n- You might be able to save space by decreasing the space allocated to the exponentiated quadratic kernel.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1g40VNkcr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present an approach to optimize determinantal point processes directly (by gradient descent, instead of . via approximations), so that diversity could be modeled in objective functions for deep learning systems. The approach taken is to express the DPP term as an L-ensemble in the spectral domain over the gram matrix. They also generate sub-gradients for cases where the gradient does not exist (when the gram matrix is not invertible).\n\nThe approach is interesting, and the problem (modeling of diversity constraints) seems important. They have experimental results (on metric learning and image learning tasks) to show that optimization with the DPP + wasserstein  gan constraint (to ensure features lie in a bounded space) result in better quality. However, they do not discuss the performance (comptuational) impact, or compare their approach to other approximation based systems (such as the approach of Elfeki et al).", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most reviewers seems in favour of accepting this paper, with the borderline rejection being satisfied with acceptance if the authors take special heed of their comments to improve the clarity of the paper when preparing the final version. From examination of the reviews, the paper achieves enough to warrant publication. Accept.
Decision: Accept (Poster)