Extreme Classification via Adversarial Softmax Approximation
Authors: Robert Bamler
Stephan Mandt
Venue:  (2020)
Keywords: Extreme classification
negative sampling

Abstract: Training a classifier over a large number of classes, known as 'extreme classification', has become a topic of major interest with applications in technology, science, and e-commerce. Traditional softmax regression induces a gradient cost proportional to the number of classes C, which often is prohibitively expensive. A popular scalable softmax approximation relies on uniform negative sampling, which suffers from slow convergence due a poor signal-to-noise ratio. In this paper, we propose a simple training method for drastically enhancing the gradient signal by drawing negative samples from an adversarial model that mimics the data distribution. Our contributions are three-fold: (i) an adversarial sampling mechanism that produces negative samples at a cost only logarithmic in C, thus still resulting in cheap gradient updates; (ii) a mathematical proof that this adversarial sampling minimizes the gradient variance while any bias due to non-uniform sampling can be removed; (iii) experimental results on large scale data sets that show a reduction of the training time by an order of magnitude relative to several competitive baselines.


Published as a conference paper at ICLR 2020
EXTREME CLASSIFICATION VIA ADVERSARIAL SOFTMAX APPROXIMATION
Robert Bamler & Stephan Mandt
Department of Computer Science University of California, Irvine (rbamler, mandt ) @uci.edu
ABSTRACT
Training a classifier over a large number of classes, known as 'extreme classi- fication', has become a topic of major interest with applications in technology, science, and e-commerce. Traditional softmax regression induces gradient cost proportional to the number of classes C, which often is prohibitively expensive. A popular scalable softmax approximation relies uniform negative sampling, which suffers from slow convergence due a poor signal-to- to-iosse ratio. In this paper, we propose simple training method for drastically enhancing the gradient signal by drawing negative samples from an adversarial model that mimics the data distri- bution. Our contributions three-fold: (i) adversarial sampling mechanism that produces negative samples at a cost only logarithmic C, thus still resulting in cheap gradient updates; (ii) a mathematical proof that this adversarial sampling minimizes the gradient variance while any bias due to non-uniform sampling can be removed; (iii) experimental results on large scale data sets that show a reduction of the training time by an order of magnitude relative to several competitive baselines.
INTRODUCTION
In many problems in science, healthcare, e-commerce, one is interested in training classifiers over an enormous number of classes: a problem known as 'extreme classification' (Agrawal et al., 2013; Jain et al., 2016; Prabhu & Varma, 2014; Siblini et al., 2018), (). For softmax (aka multinomial) regression, each gradient step incurs a cost proportional to the number of classes C. As this may be prohibitively expensive for large C, recent research has explored more scalable softmax approximations which circumvent the linear scaling in C. Progress in accelerating the training procedure and thereby scaling up extreme classification promises to dramatically improve, e.g., advertising (Prabhu et al., 2018), recommender systems, ranking algorithms (Bhatia et al., 2015; Jain al., 2016), and medical diagnostics (Bengio al., 2019; Lippert et al., 2017; Baumel al., 2018)
While scalable softmax approximations have been proposed, each one has its drawbacks. The most popular approach due its simplicity is 'negative sampling' (Mnih & Hinton, 2009; Mikolov et al., 2013), which turns the problem into binary classification between so-called 'positive samples' from the data set and 'negative samples' that are drawn random from some (usually uniform) distribution over the class labels. While negative sampling makes the updates cheaper since computing the gradient no longer scales with C, induces additional gradient noise that leads poor signal- to-noise ratio of the stochastic gradient estimate. Improving the signal-to-noise ratio in negative sampling while still enabling cheap gradients would dramatically enhance the speed of convergence.
In this paper, we present an algorithm that inherits the cheap gradient updates from negative sampling while still preserving much of the gradient signal of the original softmax regression problem. Our approach rests on the insight that the hignal-tonoiise ratio in negative sampling is poor since there is no association between input features and their artificial labels. If negative samples were harder to discriminate from positive ones, learning algorithm would obtain better gradient signal close to the optimum. Here, we make these arguments mathematically rigorous and propose non- non-uniform sampling scheme for scalably approximating softmax classification scheme. Instead of sampling labels uniformly, our algorithm uses an adversarial auxiliary model to draw 'fake' labels that are more realistic by taking the input features of the data into account. We prove that such procedure

---

Published as a conference paper at ICLR 2020
reduces the gradient noise of the algorithm, and in fact minimizes the gradient variance in the limit where the auxiliary model optimally mimics the data distribution.
A useful adversarial model should require only little overhead to be fitted to the data, and it needs to be able to generate negative samples quickly in order to enable inexpensive gradient updates. We propose probabilistic version of decision tree that has these properties. As side result of our approach, we show how such an auxiliary model can be constructed and efficiently trained. Since almost hyperparameter-free
does not cause extra complications when tuning models.
The final problem that we tackle is to remove the bias that the auxiliary model causes relative to our original softmax classification. Negative sampling is typically described as softmax approximation; however, only uniform negative sampling correctly approximates the softmax. In this paper, we show that the bias due non-uniform negative sampling can be easily removed test time.
The stucture of our paper reflects our main contributions as follows:
1. We present a new scalable softmax approximation (Section 2). We show that non-uniform sampling from an auxiliary model can improve the signal-to-noise ratio. The best perfor- mance achieved when this sampling mechanism adversarial, i.c., when it generates fake labels that are hard to discriminate from the true ones. To allow for efficient training, such adversarial samples need to be generated at a rate sublinear (e.g.. logarithmic) in C.
2. We design a new, simple adversarial auxiliary model that satisfies the above requirements (Section 3). The model is based efficiently pre-trained and included into our approach, and requires only minimal tuning.
probabilistic version of decision tree. It can be
3. We present mathematical proofs that (i) the best signal-to-noiss ratio in the gradient is obtained if the auxiliary model best reflects the true dependencies between input features and labels, and that (ii) the involved bias to the softmax approximation can be exactly quantified and cheaply removed at test time (Section 4).
4. We present experiments on two classification data sets that show that our method outperforms all baselines by at least one order of magnitude in training speed (Section 5).
We discuss related work in Section 6 and summarize our approach in Section 7.
AN ADVERSARIAL SOFTMAX APPROXIMATION
We propose an efficient algorithm to train a classifier over a large set of classes, using an asymptotic equivalence between softmax classification and negative sampling (Subsection 2.1). To speed up convergence, we generalize this equivalence to model-based negative sampling in Subsection 2.2.
2.1 ASYMPTOTIC EQUIVALENCE OF SOFTMAX CLASSIFICATION AND NEGATIVE SAMPLING
Softmax Classification (Notation). We consider a training data set D = {xx; Bs) of N data points with K -idimensiooal feature vectors i; E K Each data point has single label yi E ) from a discrete label set V A softmax classifier is defined by set of functions { hye that map feature vector æ and model parameters to a score (x, 0) E IR for each label y. Its loss function is
Σ cSv((.)))) ].
E (8)
Σ
Ex 0) + log
(Z.g)ED
While the first term encourages high scores Ey 0) for the correct labels y, the second term en- courages low scores for all labels y' E V. thus preventing degenerate solutions that set all scores to infinity. Unfortunately, the sum over y' E y makes gradient based minimization of E (0) expensive if the label set y is large. Assuming that evaluating single score Ey (I., 0) takes O(K) time, each gradient step costs (KC),, where C | is the size of the label set.
Negative Sampling. Negative sampling turns classification over a large label set y into binary classification between so-called positive and negative samples. One draws positive samples (x.
2

---

Published as a conference paper at ICLR 2020
from the training set and constructs negative samples (z, 3²) by drawing random labels y' from some noise distribution Pa- One then trains a logistic regression by minimizing the stochastic loss function
Eneg.sampl (x)
E log (E, x)) log (- (x, +))]
where 1'~ Pn (2)
(a.y)ED
with the sigmoid function (2) + Here, we used the same score functions Ey as in Eq. 1 but introduced different model parameters & so that we can distinguish the two models. Gradient steps for l sagpl (o) cost only O(K) time there is sum over all labels y' E E
Asymptotic Equivalence. The models in Eqs. 1 and Eq. 2 are exactly equivalent in the non- parametric limit, i.e., if the function class x +> Ey (2. 8) is flexible enough to map z to any possible score. A further requirement is that Pr in Eq. 2 is the uniform distribution over Y If both conditions hold, follows that 0* and di minimize Eq. and Eq. 2, respectively, they learn identical scores,
Ex 07) Ey x²) + const.
(for uniform pn).
As consequence, one is free to choose the loss function that is easier to minimize. While gradient steps are cheaper by a factor of ((C)) for negative sampling, the randomly drawn negative samples increase the variance of the stochastic gradient estimator and worsen the signal-to-noise ratio of the gradient, slowing-down convergence. The next section combines the strengths of both approaches.
2.2 ADVERSARIAL NEGATIVE SAMPLING
Overview. We propose generalized variant of negative sampling that reduces the gradient noise. The main idea is to train with negative samples y/ that are hard to distinguish from positive samples. We draw y' from a conditional noise distribution Pn(y(>>) (z) using an auxiliary model. This introduces bias, which we remove at prediction time. In summary our proposed approach consists of three steps:
1. Parameterize the noise distribution (o [z) by an auxiliary model and fit it to the data set.
2. Train a classifier via negative sampling (Eq. 2) using adversarial negative samples from the auxiliary model fitted in Step above. For our proposed auxiliary model, drawing negative sample costs only O(k log C') time with some < K, i.e., it is sublinear C.
3. The resulting model has a bias. When making predictions, remove the bias by mapping it to an unbiased softmax classifier using the generalized asymptotic equivalence in Eq. 5 below.
We elaborate on the above Step 1 in Section 3. In the present section, we focus instead on Step 2 and its dependency on the choice of noise distribution Pa, and on the bias removal (Step 3).
Why Adversarial Noise Improves Learning. We first provide some intuition why uniform nega- tive sampling not optimal, and how sampling from a non-uniform noise distribution may improve the gradient signal. We argue that the poor gradient signal is caused by the fact that negative samples are too easy to distinguish from positive samples. data set with many categories is typically com- prised of several hierarchical clusters, with large clusters of generic concepts and small sub-clusters of specialized concepts. When drawing negative samples uniformly across the data set, the correct label will likely belong to different generic concept than the negative sample. For example, an image classifier will therefore quickly Iearn to distinguish, e.g., dogs from bicycles, but since negative samples from the same cluster are rare, it takes much longer to learn the differences between a Boston Terrier and a French Bulldog. The model quickly learns to assign very low scores Ey Φ) < to such 'obviously wrong' labels, making their contribution to the gradient exponentially small,
Va log (y- (z. o))[ (Ey o)) VoSy 6)1l2
(4)
e V (z, 0)]l
for Ey < O.
A similar vanishing gradient problem was pointed out for word embeddings by Chen et al. (2018). Here, the vanishing gradient due to different word frequencies, and a popular solution is therefore to draw negative samples from nonuniform but unconditional noise distribution (a()")) based on the empirical word frequencies (Mikolov et al., 2013). This introduces a bias which does not matter for word embeddings since the focus is not classification but rather on learning useful representations.
3

---

Published as a conference paper at ICLR 2020
Going beyond trequency-udjusted negative sampling, we show that one drastically improve the procedure by generating negative samples from an auxiliary model. We therefore propose to generate negative samples y Po(y'(=1 [>) conditioned on the input feature This has the advantage that the distribution of negative samples can be made much more similar to the distribution of positive samples, leading to better signal-to-noise ratio. One consequence is that the introduced bias can no longer be ignored, which is what we address next.
Bias Removal. Negative sampling with a nonuniform noise distribution introduces a bias. For a given input feature vector z, labels y' with high noise probability Ps. (v'(aar) are frequently drawn as negative samples, causing the model to learn a low score Ey Φ²). Conversely, low Ps |x) leads to an inflated score Eor (z, o²). ). It turns that this bias can be easily quantified via generalization of Eq. 3. We prove in Theorem (Section 4) that in the nonparametric limit for arbitrary Pa (v/ [z),
Sy(r, 0*) Ey( + (ug + const.
(nomparametric limit and arbitrary po). (5)
Eq. 5 is an asymptotic equivalence between softmax classification (Eq. 1) and generalized negative sampling (Eq. 2). While strict equality holds only in the nonparametric limit, many models are flexible enough that Eq. 5 holds approximately in practice. Eq. 5 allows us to make unbiased predictions by mapping biased negative sampling scores Ey (a, x²) to unbiased softmax scores (x, 0*). There is no need to solve for the corresponding model parameters 0*, the scores (x, 0*) suffice for predictions.
Regularization. In practice, softmax classification typically requires a regularizer with some strength X > prevent overfitting. With the asymptotic equivalence in Eq. 5, regularizing the softmax scores (x, 0) is similar to regularizing E, (z, Φ) + log Pa (3/2²) in the proposed generalized negative sampling method. We thus propose use the following regularized variant of Eq. 2,
(teg.) "neg. samp. (Ø)
Σ
- log (Sv 6)) + ((5 Φ) + log Pog
(6)
N
(x. log o Ey (z, x)) + X (z, Φ) + log log pa(((())))) y (m(ll())
Comparison to GANs. The use of adversarial negative samples, i.e., negative samples that are designed to 'confuse' the logistic regression in Eq. 2, bears some resemblance to generative adversarial networks (GANs) (Goodfellow et al., 2014). The crucial difference that GANs are generative models, whereas we train a discriminative model over discrete label space y The 'generator' in our setup only needs to find a rough approximation the (conditional) label distribution because the final predictive scores in Eq. 5 combine the 'generator scores' log Pa 1)) with the more expressive "discriminator scores' Ey (2, σ²). ). This allows us to use a very restrictive but efficient generator model (see Section 3 below) that can keep constant while training the discriminator. By contrast, the focus in GANs is on finding the best possible generator, which requires concurrent training of a generator and discriminator via potentially unstable nested min-max optimization.
CONDITIONAL GENERATION OF ADVERSARIAL SAMPLES
Having proposed general approach for improved negative sampling with adversarial auxiliary model Pa. (Section 2), we now describe a simple construction for such a model that satisfies all requirements. The model is essentially a probabilistic version of decision tree which is able to conditionally generate negative samples by ancestral sampling. Readers who prefer to proceed can skip this section without loosing the main thread of the paper.
Our auxiliary model has the following properties: (i) it can be efficiently fitted to the training data D requiring minimal hyperparameter tuning and subleading computational overhead over the training of the main model: (ii) drawing negative samples y' ~ Pa(3' (x) scales only Ologg [)]). thus improving over the linear scaling of the softmax loss function (Eq. 1); and (iii) the log likelihood log Pa (n(y) can be evaluated explicitly so that we can apply the bias removal in Eq. 5. Satisfying requirements (i) and (ii) on model efficiency comes at the cost of some model performance. This an acceptable trade-off since the performance of Pa affects only the quality of negative samples.
Model. Our auxiliary model for Pa is inspired by the Hierarchical Softmax model due to Morin & Bengio (2005). It is balanced probabilistic binary decision tree, where each leaf node is mapped
4

---

Published as a conference paper at ICLR 2020
uniquely to label y E y. A decision tree imposes hierarchical structure on V/ which can impede performance if it does not reflect any semantic structure in y. Morin & Bengio (2005) rely on an explicitly provided semantic hierarchical structure, or "ontology'. Since ontology is often not available, we instead construct a hierarchical structure in a data driven way. Our method has some similarity to the approach by Mnih & Hinton (2009), but it is more principled in that we fit both the model parameters and the hierarchical structure by maximizing single log likelihood function.
To sample from the model, one walks from the tree's root some leaf. At each node v. one makes binary decision Ç E } whether to continue to the right child (ç - 1) or to the left child (ç = -)). Given a feature vector 2;, we model the likelihood of these decisions as ar (<(ww, + by)). where the weight vector wy and the scalar bias by are model parameters associated with node Denoting the unique path Ty from the root node v/ to the leaf node associated with label as sequence of nodes and binary decisions, Ty = ((Po: Co), (I),S))....) the log likelihood of the training set 'D is thus
L = Σ Po
Σ log a (C(w) x ba)) (x.N)ED (MIS)ER
Σ
(R.y)ED
Greedy Model Fitting. We maximize the likelihood L in Eq. 7 over (i) the model parameters wP and b, of all nodes v. and (ii) the hierarchical structure, i.e. the mapping between labels y and leaf nodes. The latter involves an exponentially large search space, making exact maximization intractable. We use a greedy approximation where we recursively split the label set y into halves and associate each node v with a subset Vi S y We start at the root node vn with V = 3 and finishing at the leaves with single label per leaf. For each node v, we maximize the terms in L that depend on w, and b These terms correspond to data points with a label y E V,, leading to the objective
Ly
Σ
log o (G (1r, b.)).
(EN)EDAVE))
We alternate between a continuous maximization of C, over w, and by, and a discrete maximization over the binary indicators Sy E {+1} that define how we split Y. into two equally sized halves. The continuous optimization is over a convex function and converges quickly to machine precision with Newton ascent, which is free of hyperparameters like learning rates. For the discrete optimization, note that changing Ey for any y E Vn from -1 to 1 (or from to - 1) increases (or decreases) C, by (w bu). bu) log a (ww bu)] Σ xED,
Σ [logo ZED
Here, the sums over D, run over all data points in D with label y. and the second equality is an algebraic identity of the sigmoid function. We maximize E, over all Cy under the boundary condition that the split be into equally sized halves by setting Gy + 1 for the half of y E Ve with largest A, and Gy +- 1 for the other half. If this changes any Gy then we switch back to the continuous optimization. Otherwise, we have reached a local optimum for node v, and we proceed to the next node.
Technical Details. In the interest of clarity, the above description left out the following details. Most importantly, to prioritize efficiency over accuracy, we preprocess the feature vectors x and project them to a smaller space RR& with from Pn thus costs only O(k log ( time. This dimensionality reduction only affects the quality of negative samples. The main model (Eq. 2) still operates on the full feature space R Second, we add quadratic regularizer -A, (I (/,,,,,lll_ 1|2 2 + 63
K using principal component analysis (PCA). Sampling
L., with strength Xn set by cross validation. Third, we introduce uninhabited padding labels [ is not a power of two. We ensure that Pa(i (r) = 0 for all padding labels ý by setting by to very large positive negative value if either of v/s children contains only padding labels. Finally, we initialize the optimization with b, < 0 and by setting w. R to the dominant eigenvector of the covariance matrix of the set of vectors (Enep, xJve
THEORETICAL ASPECTS
We formalize and prove the two main premises of the algorithm proposed in Section 2.2. Theorem 1 below states the equivalence between softmax classification and negative sampling (Eq. 5), and Theorem 2 formalizes the claim that adversarial negative samples maximize the signal-to-noise ratio.
5

---

Published as a conference paper at ICLR 2020
Theorem 1. In the nonparametric limit, the optimal model parameters 9" and ø' that minimize sofumar (8) in Eq. and Eneg sampt (Ø) in Eq. 2. respectively, satisfy Eq. 5 for all x in the data set and all y V. Here, the "const." term on the right-hand side of Eq. 5 is independent of y.
Proof. Minimizing Csottmax (0) fits the maximum likelihood estimate of a model with likelihood pe (y(y)z) = (zv(2.0) /Za /Zz with normalization ZØ(x) = Eyey Ey (5,(2,0) In the nonparametric limit, the score functions (x, 0) are arbitrarily flexible, allowing for perfect fit, thus
PD (x) pe- (u/z) = elvlx.0)) (Zaaa00//-(aa (Zg-(x)
(nonparametric limit).
(10)
Similarly, feeg sampl (Ø) the maximum likelihood objective of binomial model that discriminates
positive from negative samples. The nonparametric limit admits again perfect fit so that the learned
ratio of positive rate a (E, ()) to negative rate ( x)) equals the empirical ratio,
(o(y
o ((,((x,0")
Pn (2) (2-6,(2,07) = elv(2,0)
(nonparametric limit)
(11)
where we used the identity a(z)/o(-z) = e², Inserting Eq. 10 for pD and taking the logarithm leads to Eq. 5. Here, the "const." term works out to log Zø. (x), which is indeed independent of y. O
Signal-to-Noiss Ratio. In preparation for Theorem 2 below, we define quantitative measure for the signal-to-noise ratio (SNR) stochastic gradient descent (SGD). In the vicinity of the minimum ø of a loss function {(ő), the gradient g Hr(á o²) is approximately proportional to the Hessian Hy at 6² SGD estimates g via stochastic gradient estimates 9. whose noise is measured by the covariance matrix Cov(g. 9]. Thus, the eigenvalues {1) of the matrix A := He Cov(g. g] measure the SNR along different directions in parameter space. We define overall sealar SNR vj as
== Σ, 1/n:
Tr|A-|| Tr(Coviê. 91 "
(12)
Here, we sum over the inverses 1/1; rather than π7 so that ij S min, 77 and thus maximizing ñ encourages large values for all 77.- The definition in Eq. 12 has the useful property that î is invariant under arbitrary invertible reparameterization of Φb Expressing & in terms of new model parameters d' maps H2 to J HJ and Cov(ğ. 0] to J Covll. J. where J == B is the Jacobian. Inserting into Eq. 12 and using the cyclic property of the trace, Tr[PQ] Tr(QP]. all Jacobians cancel.
Theorem 2. For negative sampling (Eq. 2) in the nonparametric limit, the signal-to-non ratio îj defined in Eq. 12 is maximal if Pr PD. i.e. adversarial negative samples.
Proof. In the nonparametric limit, the scores (x, o) can be regarded as independent variables for all and y. We therefore treat the scores directly as model parameters, using the invariance of f under reparameterization. Using only Eq. 2, Eq. 11. I, and properties of the o-function, we show in Appendix A. that the Hessian of the loss function is diagonal this coordinate system, and given by
He diag(az.))
with azzyy pa(p)) (z)
(13)
and that the noise covariance matrix is block diagonal,
Covlğ, .) diag(C,) with blocks
C₂ = N diag(az.) Nan,.... T
(14)
where Ozz,; (az,,)yey denotes a |)/l-dimensional column vector. Thus, the trace in Eq. 12 is
]
= Σ Tr Cr diag
= N Σ Tr 20 diag
- = N Σ y 2 Σ Oxr
x
wEY
(15)
We thus have to maximize Eyey Ouay for each x in the training set. We find from Eq. 13 and Eq. 11,
Σ az Ep((ola) [o (z, xy))] = Ep((vl=) yEy
(13)
E Ep.ly m)) [ (Po(yl
(16)
Pr(2]z)
with f()) = 11(11 Using Jensen's inequality for the concave function f. we find that the right-hand side of Eq. 16 has the upper bound f (Epp(o))a) (po(yl=)/p<(/lal = =11 = 2. which
reaches precisely if the argument of / in Eq. 16 is a constant, i.e., iff pa(y)x)) po(y(>)) Vy ). n

---

Published as a conference paper at ICLR 2020
Table 1: Sizes of data sets and hyperparameters. N number of training points; C number of categories (after preprocessing); = learning rate; À = regularizer, o prior variance.
Size data set
adv. neg. S. uniform
x freq. neg. S.
Data set
(proposed)
neg.
NCE
A&R
OVE
N-1,644,302
p=0.01
p=0.003 =
p=0.001
p=0.01
0=0.02 -0 0
p=
Wikipedia-500K
C=217,244
2=0.001
A=10-5
0=0.00
N=490,449
p=0.01
p=0.01
p=0.003
p=0.01
p=0.1
0=0.03
Amazon-670K
C-213,874
0-000
--0000
A=10-5
o0
-11
5 RESULTS
We evaluated the proposed adversarial negative sampling method on two established benchmarks by comparing speed of convergence and predictive performance against five different baselines.
Datasets, Preprocessing and Model. We used the Wikipedia-500k and Amazon-670K data sets from the Extreme Classification Repository (Bhatia et al.) with K = 512-dimensional XMI-CNN features (Liu al., 2017) downloaded from (Saxena). As oth data sets contain multiple labels per data point we follow the approach in (Ruiz et al., 2018) and keep only the first label for each data point. Table shows the resulting sizes. We fit liner model with scores Ey (I, の) = x Wy + by. where the model parameters are the weight vectors Wy E R-K and biases by E R for each label y.
Baselines. We compare our proposed method to five baselines: (i) standard negative sampling with a uniform noise distribution; (ii) negative sampling with an unconditional noise distribution pa (3/)) set to the empirical label frequencies; (iii) noise contrastive estimation (NCE, see below); (iv) 'Augment and Reduce' (Ruiz et al., 2018); and (v) 'One vs. Each' (Titsias, 2016). We do not compare to full softmax classification, which would be unfeasible on the large data sets (see Table 1; a single epoch of optimizing the full softmax loss would scale as O(CC))). However, we provide additional results that compare softmax against negative sampling on a smaller data set in Appendix A.2.
NCE (Gutmann & Hyvärinen, 2010) is sometimes used as a synonym for negative sampling in the literature, but the original proposal of NCE is more general and allows for nonuniform base distribution. We use our trained auxiliary model (Section 3) for the base distribution of NCE. Compared our proposed method, NCE uses the base distribution only during training and not for predictions. Therefore, NCE has to re-learn everything that is already captured by the base distribution. This is less of an issue in the original setup for which NCE was proposed, namely unsupervised density estimation over a continuous space. By contrast, training supervised classifier effectively means training a separate model for each label y E V, which is expensive if y is large. Thus, having to re-learn what the base distribution already captures is potentially wasteful.
of
Hyperparameters. We tuned the hyperparameters for each method individually using the val- idation set. Table 1 shows the resulting hyperparameters. For the proposed method and base- lines (i)-(iii) we used an Adagrad optimizer (Duchi et al., 201 1) and considered learning rates P {0.0003, 0.001, 0.003, 0.01, 0.03) and regularizer strengths (see Eq. 6) X (10-3,3 5,3 x "o-5,....,,03, 0.033. For 'Augment and Reduce' and "One vs. Each' we used the implementation published by the authors (Ruiz), and tuned the learning rate p and prior variance of. For the auxiliary model, we used a feature dimension of k = 16 and regularizer strength X, = 0.1 for both data sets.
10-5 .....
Results. Figure shows our results on the Wikipedia-500K data set (left two plots) and the Amazon- 670K data set (right two plots). For each data set, we plot the the predictive log likelihood per test data point (first and third plot) and the predictive accuracy (second and fourth plot). The green curve in each plot shows our proposed adversarial negative sampling methods. Both our method and NCE (orange) start slightly shifted to the right to account for the time to fit the auxiliary model.
Our main observation is that the proposed method converges orders of magnitude faster and reaches better accuracies (second and third plot in Figure 1) than all baselines. On the (smaller) Amazon-677 670K data set, standard uniform and frequency based negative sampling reach slightly higher predictive
7

---

Published as a conference paper at ICLR 2020
Widppedia-00K
Wikipedia-S0OK
Amazon-670K
Amozon
Reath MA Waolhooo
accurarc
.10%
adversorial ieg. (pmpieedd
freo, based neg, campl
NCE (Gusmann at al. 2010] uniform sampl
-30
-10
70%
-12
training
treniin
training
tneining
Figure I: Learning curves for our proposed adversarial negative sampling method (green) and for five different baselines on two large data sets (see Table 1).
log likelihood, but our method performs considerably better in terms of predictive accuracy on both data sets. This may be understood as the predictive accuracy is very sensitive to the precise scores of the highest ranked labels, small change in these scores can affect which label is ranked highest. With adversarial negative sampling, the training procedure focuses on getting the scores of the highest ranked labels right, thus improving in particular the predictive accuracy.
RELATED WORK
Efficient Evaluation of the Softmax Loss Function. Methods to speed up evaluation of Eq. 1 include augmenting the model by adding auxiliary latent variables that can be marginalized over analytically (Galy-Fajou et al., 2019; Wenzel et al., 2019; Ruiz et al., 2018; Titsias, 2016). More closely related to our work are methods based on negative sampling (Mnih & Hinton, 2009; Mikolov et al., 2013) and noise contrastive estimation (Gutmann & Hyvärinen, 2010). Generalizations of negative sampling to non-uniform noise distributions have been proposed, e.g., in (Zhang & Zweigenbaum, 2018; Chen et al., 2018; Wang et al., 2014; Gutmann & Hyvärinen, 2010). Our method differs from these proposals by drawing the negative samples from conditional distribution that takes the input feature into account, and by requiring the model to learn only correlations that are already captured by the noise distribution. We further derive the optimal distribution for negative samples, and we propose an efficient way to approximate it via an auxiliary model. Adversarial training (Miyato et al., 2017) is a popular method for training deep generative models (Tu, 2007; Goodfellow et al., 2014). By contrast, our method trains a discriminative model over a discrete set of labels (see also our comparison to GANs at the end of Section 2.2).
A different sampling baseed approximation of softmax classification is 'sampled softmax' (Bengio et al., 2003). It directly approximates the sum over classes y' in the loss (Eq. 1) by sampling, which is biased even for uniform sampling distribution. A nonuniform sampling distribution can remove or reduce the bias (Bengio & Senécal, 2008; Blanc Rendle, 2018: 8; Rawat et al., 2019). By contrast, our method uses negative sampling, and it uses nonuniform distribution to reduce the gradient variance.
Decision Trees. Decision trees (Somvanshi & Chavan, 2016) are popular in the extreme classifica- tion literature (Agrawal al., 2013; Jain et al., 2016; Prabhu & Varma, 2014; Siblini al., 2018; Weston et al., 2013; Bhatia et al., 2015; Jasinska et al., 2016). Our proposed method employs probabilistic decision tree that similar to Hicrarchical Softmax (Morin & Bengio, 2005; Mikolov et al., 2013). While decision trees allow for efficient training and sampling in O(log C)) time, their hierarchical architecture imposes structural bias. Our proposed method trains more expressive model without such structural bias top of the decision tree to correct for any structural bias.
7 CONCLUSIONS
We proposed simple method to train a classifier over large set of labels. Our method is based scalable approximation to the softmax loss function via generalized form of negative sampling. By generating adversarial negative samples from auxiliary model, we proved that we maximize the signal-to-noise ratio of the stochastic gradient estimate. We further show that, while the auxiliary model introduces a bias, we can remove the bias at test time. We believe that due its simplicity, our method can be widely used, and we publish the code of both the main and the auxiliary model.
httpp:://g wwwb. wtt../ooo///acccc wabbaavveeeeeeee
-negat vie samp1 ing
8

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
Stephan Mandt acknowledges funding from DARPA (HR001119S00) NSF (FW-HTF-RM), and Qualcomm.
REFERENCES
Rahul Agrawal, Archit Gupta, Yashoteja Prabhu, and Manik Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In Proceedings of the 22nd international conference on World Wide Web, pp. 13-24. ACM, 2013.
Tal Baumel, Jumana Nassour- Kassis, Raphael Cohen, Michael Elhadad, and Noemie Elhadad. Multi- label classification of patient notes: case study on icd code assignment. In Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Samy Bengio, Krzysztof Dembezynski, Thorsten Joachims, Marius Kloft, and Manik Varma. Extreme classification (dagstuhl seminar 18291). Schloss Dagstubl-Laiimiiz7Zenruuu fuer Informatik, 2019.
Yoshua Bengio and Jean-Sébastien Senécal. Adaptive importance sampling to accelerate training of neural probabilistic language model. IEEE Transactions on Neural Networks, 19(4)711-7222 2008.
Yoshua Bengio, Jean-Sébastien Senécal, et al. Quick training of probabilistic neural nets by impor- tance sampling. In AISTATS, pp. 1-9, 2003.
Kush Bhatia, Kunal Dahiya, Himanshu Jain, Yashoteja Prabhu, and Manik Varma. The extreme classi- fication repository: Multi-label datasets & code. http:/ /man ikaaraa org/ downloads
XC/XMLRepository html. Accessed: 2019-05-23.
Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma, and Prateck Jain. Sparse local embeddings for extreme multi-label classification. In Advances in neural information processing systems, pp. 730-738, 2015.
Guy Blanc and Steffen Rendle. Adaptive sampled softmax with kernel based sampling. In Interna- lional Conference on Machine Learning, pp. 589-598, 2018.
Long Chen, Fajie Yuan, Joemon M Jose, and Weinan Zhang. Improving negative sampling for word representation using self-embeddes features. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. ACM, 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, (0000l):2121211555 2011.
Théo Galy-Fajou, Florian Wenzel, Christian Donner, and Manfred Opper. Multi-class gaussian process classification made conjugate: Efficient inference via data augmentation. In Uncertainty in Artificial Intelligence, 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, pp. 2672-2680, 2014.
Michael Gutmann and Aapo Hyvärinen.
estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for rec- ommendation, tagging, ranking & other missing label applications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 935-944. ACM, 2016.
Kalina Jasinska, Krzysztof Dembezynski, Róbert Busa-Fekete, Karlson Pfannschmidt, Timo Klerx, and Eyke Hullermeier. Extreme f-measure maximization using sparse probability estimates. In International Conference Machine Learning, pp. 1435-1444, 2016.

---

Published as a conference paper at ICLR 2020
Christoph Lippert, Riccardo Sabatini, M Cyrus Maher, Eun Yong Kang. Seunghak Lee, Okan Arikan, Alena Harley, Axel Bernal, Peter Garst, Victor Lavrenko, et al. Identification of individuals by trait prediction using shole-genone sequencing data. Proceedings of the National Academy of Sciences, (14(38):10166) 10166-11111611177 2017.
2017.
Jingzhou Liu, Wei-Cheng Chang, Yuexin Wu, and Yiming Yang. Deep learning for extreme multi- label text classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp- 115-124. ACM, 2017.
Eneldo Loza Mencia and Johannes Fürnkranz. Efficient pairwise multilahel classification for large- scale problems in the legal domain. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 50-65. Springer, 2008.
Tomas Mikolov, Iya Sutskever, Kai Chen, Greg $ Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pp. 3111-3119, 2013.
Takeru Miyato, Andrew M Dai, and Ian Goodfellow. Adversarial training methods for semi-supervised text classification. 2017.
Andriy Mnih and Geoffrey E Hinton. A scalable hierarchical distributed language model. In Advances in neural information processing systems, pp. 1081-1088, 2009.
Frederic Morin and Yoshua Bengio. Hicrarchical probabilistic neural network language model. In Aistats, volume pp. 246-252. Citeseer, 2005.
Yashoteja Prabhu and Manik Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 263-272. ACM, 2014.
Yashoteja Prabhu, Anil Kag, Shrutendra Harsola, Rahul Agrawal, and Manik Varma. Parabel: Partitioned label trees for extreme classification with application to dynamic search advertising. In Proceedings of the 2018 World Wide Web Conference, pp. 993-1092 1002. International World Wide Web Conferences Steering Committee, 2018.
Ankit Singh Rawat, Jiecao Chen, Felix Yu, Ananda Theertha Suresh, and Sanjiv Kumar. Sampled softmax with random fourier features. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Francisco JR Ruiz. Augment and reduce github repository. franrruia // augment- hengucet-rrduce... reduce. Accessed: 2019-05-23.
https::/github..co
Francisco JR Ruiz, Michalis K Titsias, Adji B Dieng, and David M Blei. Augment and reduce: Stochastic inference for large categorical distributions. In International Conference on Machine Learning, pp. 4400-4409, 2018
Siddhartha Saxena. Xml-enn github repository. http::://gitttub.comm Accessed: 2019-05-23.
CNN.
Wissam Siblini, Pascale Kuntz, and Frank Meyer. Craftml, an efficient clustering- random forest for extreme multi-label learning. In The 35th International Conference Machine Learning. (ICML 2018), 2018
Madan Somvanshi and Pranjali Chavan. A review of machine learning techniques using decision tree and support vector machine. 2016 International Conference on Computing Communication Control and automation (ICCUBEA), pp. 1-7. IEEF, 2016.
Michalis K Titsias. One-vs-each approximation to softmax for scalable estimation of probabilities. In Advances in Neural Information Processing Systems, pp. 4161-4166 2016.
Zhuowen Tu. Learning generative models via discriminative approaches. In 2007 IEEE Conference Computer Vision and Pattern Recognition, pp. 1-8. IEFE, 2007.
10

---

Published as a conference paper at ICLR 2020
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In Ewenty-Eightt AAAI conference on artificial intelligence, 2014.
Florian Wenzel, Théo Galy-Fajou, Christan Donner, Marius Kloft, and Manfred Opper. Efficient gaussian process classification using polya-gamma data augmentation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5417-5424, 2019.
Jason Weston, Ameesh Makadia, and Hector Yee. Label partitioning for sublinear ranking, In International Conference on Machine Learning, pp. 181-189, 2013.
Zheng Zhang and Pierre Zweigenbaum. Gneg: Staph-based negative sampling for word2vec. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 566-571, 2018.

---

Published as a conference paper at ICLR 2020
APPENDIX
A.1 DETAILS OF THE PROOF OF THEOREM 2
In the nonparametric limit, the score functions (z Φ) are so flexible that they can take arbitrary values for all x in the data set and all y E y. Taking advantage of the invariance of nj under reparameterization, we parameterize the model directly by its scores. We use the shorthand faw = Ey (z, Φ), and we denote the collection of all scores over all z and y E y by boldface & = (Exy)ay
Hessian. Eq. defines the loss /ucg.sampl. as stochastic function. SGD minimizes its expectation,
((E) == E Bllacg.san samp. (E)]
Σ> Σ (D(())) log (fx,y) Pa(y)z) log or (--x2
(A1)
where the over runs over all feature vectors in the training set. We obtain the gradient
Iz.y Ver., {(E) = (pD(y)>) o( + Pa(y/z) (E2.y)
(A2)
where we used the relation V, log (z) o(-2). The gradient is vector whose components span all combinations of x and y. The Hessian matrix H, contains the derivatives of each gradient compo- nent JN.y by each coordinate Şz.g. Since Ju.y in Eq. A2 depends only the single coordinate Er.y- only the diagonal parts of the Hessian are nonzero, i... the components with x = I and y = ÿ. Thus,
He diag(ax..)
with
On Veew Ua.9
(A3)
Using the identity (2o(z) = o()) we find
Cg.yy
(yl=) + pn(y==)] of (a (Ez.u))
(A4)
Since we evaluate the Hessian in the nonparametric limit at the minimum of the loss, the scores Enr,y satisfy Eq. 11, i.e.,
PD(U|z) ((-Ex.)) = = ((...)))))))))))
(A5)
This allows us to simplify Eq. A4 by eliminating PDD
Ozyy -P(ll (S((E.)) + ol o0(-f.,)]] (Ex..)) Pa(v(æ) (Ex.y)
(A6)
=1
Eqs. A3 and A6 together prove Eq. 13 of the main text.
Noise Covariance Matrix. SGD uses estimates é of the loss function in Eq. A1, obtained by drawing positive sample (I, y) ~ DD and a label for the negative sample y' ~ Po(y ()), thus
{(E) = N (Er,y) + log o (-Ea.r))
(A7)
where the factor of N = [D] is because the sum over x in Eq. A1 scales proportionally to the size of the data set D (in practice one typically normalizes the loss function by N without affecting the signal to noise ratio). One uses to obtain unbiased gradient estimates ğ. We introduce new symbols i and ÿ for the components ÿž.9 of the gradient estimate to avoid confusion with the x and drawn from the data set and the y/ drawn from the noise distribution Eq. A7 above. Since the scores are independent variables in the nonparametric limit, the derivative Ves.; Sn.y is one if 7 = x and ÿ y. and zero otherwise. We denote this by indicator functions 12=z and 1ø=y- Thus, we obtain
Ea. ((E) = - (-(((-Ee.g)))
a (Ev.y) ) 12=z
(A8)
We evaluate the covariance matrix of 9 at the minimum of the loss function. Here, [E]] = = 0, and thus Covlğ, 9] Elğ ğ [[]] Elg II simplifies to Elg ğ J. Introducing yet another pair of indices
i and to distinguish the two factors of g. we denote the components of the covariance matrix
Cov Nov[ga.w Iz.5l = ((z,)) v'pp [0 9a.5) :]
(A9)
Here, the expectation is over PD (z. y) (n (x) = po PD (2)22) Pn (z) We start with the evalu- ation of the expectation over ær using Ez-pol
Enl
where the sum runs over all x in the
A1

---

Published as a conference paper at ICLR 2020
data set. 2 2 or x # i, then either one of the two gradient estimates 9 in the expectation the right-hand side of Eq. A9 vanishes. Therefore, only terms with - = 3 contribute, and the covariance matrix is block diagonal in x as claimed in Eq. 14 of the main text. The blocks Cg of the block diagonal matrix have entries
(Cz) g.8 g = Covlle.g Ix.gl E (vll))) (a) [d..y 92.0]
(A10)
where we find for the product dz.ū In. by inserting Eq. A8 and multiplying out the terms,
Ia.ū :2.0
N2
[ Ex. 1 + (Ex,g)) 1 1y=v) g=
(A11)
- -o(-Ea,s) (En.. ( j
o (Ex.5) ol ol I
Taking the expectation in Eq. A10 leads to the following substitutions:
1 10=y + pD()))); 1:=y - (ū]xx; 18=y' p=())z);; 1 - Pn(0(x). (A12)
Thus, we find,
(C = N (pp((Tl))) of (- + pn ( o (Ln.i)
(A13)
- -PD(i)>) Pa (ū
o (Sm (o( pD ((nn ol o(
Using Eq. A5, we can again eliminate PD.
(Ca) - N (p (T) o
+ p (mlx)) (Ex,,))) 1
2p
(E2.)))
N as.00 (o(-En))) + o (Ex.5) 1 A== 2 20r. Uz.g
= =N 1--
2 i 0 oz
(A14)
Eq. A14 the component-wise explicit form of Eq. 14 of the main text.
A.2 EXPERIMENTAL COMPARISON BETWEEN SOFTMAX CLASSIFICATION AND NEGATIVE SAMPLING
We provide additional experimental results that evaluate the performance gap due to negative sampling compared to full softmax classification on a smaller data set. Theorem states an equivalence between negative sampling and softmax classification. However, this equivalence strietly holds only (i) in the nonparametric limit, (ii) without regularization, and (iii) if the optimizer really finds the global minimum of the loss function. In practice, all three assumptions hold only approximately.
Data Set and Preprocessing. To evaluate the performance gap experimentally, we used "EURLex- 4K" data set (Bhatia et al.; Mencia & Fürnkranz, 2008), which is small enough to admit direct optimization of the softmax loss function. Similar to the preprocessing of the two main data sets described in Section 5 of the main text, we converted the multi-class classification problem into single-class classification problem by selecting the label with the smallest ID for each data point, and discarding any data points without any labels. We split off 10% of the training set for validation, and report results on the provided test set. This resulted in training set with N 13,960 data points and C' = 3,687 categories. As in the main paper, we reduced the feature dimension to K 512 (using PCA for simplicity here).
Model and Hyperparameters. due to negative sampling in general. We therefore fitted the same affine linear model as described in Section 5 of the main text using the full softmax loss function (Eq. 1) and the simplest form of negative sampling (Eq. 2), i.c., negative sampling with uniform noise distribution. We added a quadratic regularizer with strength À both loss functions.
The goal of these experiments is evaluate the performance gap
A2

---

Published as a conference paper at ICLR 2020
For both methods, tested the same hyperparameter combinations as in Section on the validation set using early stopping. For softmax, we extended the range tested learning rates up to p = 10 as higher learning rates turned out perform better in this method (this can be understood due to the low gradient noise). The optimal hyperparameters for softmax turned out to be a learning rate of p 0.3 and regularization strength À = 3 10-1, For negative sampling. we found p = 3 x 10-3 and X = 3 x 10
Results. We evaluated the predictive accuracy for both methods. With the full softmax method, we obtain 33.6% correct predictions on the test set, whereas the predictive accuracy drops to 26.4% with negative sampling. This suggests that, when possible, minimizing the full softmax loss function should be preferred. However, in many cases, the softmax loss function is too expensive.
A3


Reviews:
[{"review_id": "H1lmZ7TpKr", "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": "The paper presents a method for negative sampling for softmax when dealing with classification of data to one from a large number of classes. Its main idea is to negative sample those classes which lead to higher signal to noise ratio than for uniform negative sampling. This is based on building an auxilary model using decision tree from which the adversarial negative classes are sampled, so that the distribution of the negative samples can be close to the positive ones leading to higher SNR while training. The proposed method is compared to other methods for negative samping on two publicly available large-scale datasets from the extreme classification with XML-XNN features. \n\nPositives :\n1. The proposed approach with adversarial negative sampling using an auxilary model seems interesting \n2. It scales well to datasets with large number of classes.\n\nNegatives :\nThe experimental evaluation of the proposed approach lacks completeness and does not look convincing for the following reasons : \n1. It misses out a recent state-of-the-art method (Slice) for negative sampling on same datasets [1], which also addresses the same problem of sampling most promising negative classes but in a different way. Furthermore, [1] also compares against many other sota methods missed out in this paper on the many other datasets datasets including those in this paper but in a more general multi-label setting.\n2. The paper only compares against other negative sampling approaches such as AandR, NCE, and does not show what happens when no negative sampling is done such as done in (DiSMEC) [2]. This is important to understand what (if at all) is lost by doing approximation as proposed. For instance, a quick experiment reveals that DiSMEC can give about 19% accuracy on Wiki500 dataset, which is better than that achieved by the proposed method. Though it is computationally expensive but due to its simplicity, it must be discussed nevertheless to give a complete picture.\nInstead the OVE baseline used in the paper seems quite sub-optimal in the first place, and hence stronger baselines [1,2] for which the code and results are readily available and have been duly tested in the community must be used and discussed.\n\nAnother aspect that the paper misses out is the role of fat-tailed distribution [3,4] of the instances among labels, which is a property of typical datasets in this regime. It is possible that one can get good accuracy but poor performance on tail-labels due to approaximations. The performance on tail-labels on appropriate metrics other than accuracy, such as MacroF1, should be evaluated.\n\nAlso, the proposed approach must be tested on more datasets including the smaller ones such as EURLex (also used in works referenced in the paper) on which it is easier to compare with other methods (such as DiSMEC, Slice and AttentionXML [5]) without encountering computational constraints and also bigger ones such as Amazon3M, also avilable from the repository. \n\nFinally, it must be investigated if the proposed method can be extended to the multi-label setting or are there inherent limitations of the model in this setting. The possibility to extend it to the general multi-label setting would make this approach more promising and directly comparable to wide range of algorithms.\n\n[1] H. Jain,  V. Balasubramanian,  B. Chunduri and M. Varma, Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches, in WSDM 2019.\n[2] R. Babbar, and B. Schölkopf, DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification in WSDM, 2017.\n[3] H. Jain, Y. Prabhu, and M. Varma, Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking & Other Missing Label Applications in KDD, 2016.\n[4] R. Babbar, and B. Schölkopf, Data Scarcity, Robustness and Extreme Multi-label Classification in Machine Learning Journal and European Conference on Machine Learning, 2019.\n[5] AttentionXML: Extreme Multi-Label Text Classification with Multi-Label Attention Based Recurrent Neural Networks, NIPS 2019", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gf7y-RtB", "reviewer": "AnonReviewer1", "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": "This paper focuses on efficient and fast training in the extreme classification setting where the number of classes C is very large. In this setting, naively using softmax based loss function incurs a prohibitively large cost as the cost of computing the loss value for each example scales linearly with C. One way to circumvent this issue is to only utilize a small subset of negative classes during the loss computation. However, uniformly sampling this subset from all the negative classes suffers from the slow convergence as such sampled negatives are not very informative for the underlying classification task. \n\nThe paper proposes a method to sample the negatives in a non-uniform manner. In particular, given an example, an adversarial auxiliary model that is tasked with tracking the data distribution samples the hardest (adversarial) negatives for the example. The proposed method to sample negatives has a computational cost log(C) and reduces the noise in the gradient. The authors then demonstrate the utility of their proposed approach on two well-established extreme classification datasets, i.e., Wikipedia-500K and Amazon-670K. The proposed method shows improvement over some natural baselines in terms of the wall-time for the convergence of the training process.\n\nComments\n\n1. The paper has some nice contributions and discusses the key ideas in reasonable detail. However, the reviewer feels that the authors gloss over many relevant prior works and fail to put their results in the right context. There has been quite a bit of work on non-uniformly sampling \"hard\" negative classes. For example, see [1], [2], [3], [4]. In fact, [3] and [4] propose methods to sample negatives from a distribution that closely approximates the softmax distribution at the cost that scales logarithmically in C, essentially providing the hard negative without having to keep an auxiliary model. Can the authors discuss their work in the context of these works?\n\n[1] Reddi et al., Stochastic Negative Mining for Learning with Large Output Spaces.\n[2] Grave et al., Efficient softmax approximation for GPUs.\n[3] Blanc and Rendle, Adaptive Sampled Softmax with Kernel-based Sampling.\n[4] Rawat et al., Sampled Softmax with Random Fourier Features.\n \n2. In experiments, the authors do not include the performance of softmax loss (eq. (1)) due to its large computational cost. However, it would be nice to compare the proposed method with eq. (1) at least for slightly smaller datasets from the extreme classification repository. \n\n3. In Sec. 4, \"We formalize and proof...\" --> \"We formalize and prove...\"\n\n4. In Sec. 1, \"We present experiments on several two classifications...\" ---> \"We present experiments on two classifications...\"\n\n5. Table 1 seems to have some typos. E.g., N is the same for both the data sets. Please fix these issues.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeL_F-q9B", "reviewer": "AnonReviewer2", "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": "This work addresses the problem of training softmax classifiers when the number of classes is extreme. The authors improve the negative sampling method which is based on reducing the multi-class problem to a binary class problem by introducing randomly chosen labels in the training.  Their idea is generating the fake labels nonuniformly from an adversarial model (a decision tree). They show convincing results of improved learning rate.\nThe work is very technical in nature, but the proposal is presented in detail and in a didactic way with appropriate connections to alternative methods, so that it may be useful for the non-expert (as me).\nThat is the reason why I recommend to accept this work: even not being an expert I found the paper educative in introducing the problem and interesting in explaining the proposal. ", "extra_scores": {"experience_assessment": "I have read many 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": {}}]

Author rebuttal:

Meta-review: The paper proposes a fast training method for extreme classification problems where number of classes is very large. The method improves the negative sampling (method which uses uniform distribution to sample the negatives) by using an adversarial auxiliary model to sample negatives in a non-uniform manner. This has logarithmic computational cost and minimizes the variance in the gradients. There were some concerns about missing empirical comparisons with methods that use sampled-softmax approach for extreme classification. While these comparisons will certainly add further value to the paper, the improvement over widely used method of negative sampling and a formal analysis of improvement from hard negatives is a valuable contribution in itself that will be of interest to the community. Authors should include the experiments on small datasets to quantify the approximation gap due to negative sampling compared to full softmax, as promised.
Decision: Accept (Poster)