arXiv:1709.05976v3 [cs.LG] 10 Nov 2017

Leveraging Distributional Semantics for
Multi-Label Learning
Rahul Wadbude

Vivek Gupta

Piyush Rai

IIT Kanpur
warahul@iitk.ac.in

Microsoft Research
t-vigu@microsoft.com

IIT Kanpur
piyush@iitk.ac.in

Nagarajan Natarajan

Harish Karnick

Prateek Jain

Microsoft Research
t-nanata@microsoft.com

IIT Kanpur
hk@iitk.ac.in

Microsoft Research
prajain@microsoft.com

Abstract
We present a novel and scalable label embedding framework
for large-scale multi-label learning a.k.a ExMLDS (Extreme
Multi-Label Learning using Distributional Semantics). Our
approach draws inspiration from ideas rooted in distributional
semantics, specifically the Skip Gram Negative Sampling
(SGNS) approach, widely used to learn word embeddings
for natural language processing tasks. Learning such embeddings can be reduced to a certain matrix factorization. Our
approach is novel in that it highlights interesting connections
between label embedding methods used for multi-label learning and paragraph/document embedding methods commonly
used for learning representations of text data. The framework
can also be easily extended to incorporate auxiliary information such as label-label correlations; this is crucial especially
when there are a lot of missing labels in the training data. We
demonstrate the effectiveness of our approach through an extensive set of experiments on a variety of benchmark datasets,
and show that the proposed learning methods perform favorably compared to several baselines and state-of-the-art methods for large-scale multi-label learning. To facilitate end-toend learning, we develop a joint learning algorithm that can
learn the embeddings as well as a regression model that predicts these embeddings given input features, via efficient gradient based methods.

Introduction
Modern data generated in various domains are increasingly
"multi-label" in nature; images (e.g. Instagram) and documents (e.g. Wikipedia) are often identified with multiple
tags, online advertisers often associate multiple search keywords with ads, and so on. Multi-label learning is the problem of learning to assign multiple labels to instances, and
has received a great deal of attention over the last few
years; especially so, in the context of learning with millions of labels, now popularly known as extreme multi-label
learning (Jain, Prabhu, and Varma 2016; Bhatia et al. 2015;
Babbar and Schölkopf 2017; Prabhu and Varma 2014).
The key challenges in multi-label learning, especially when there are millions of labels, include a) the
data may have a large fraction of labels missing, and
b) the labels are often heavy-tailed (Bhatia et al. 2015;
Submitted to Thirty-Second Association for the Advancement of
Artificial Intelligence, AAAI 2018 (www.aaai.org). Do not distribute.

Jain, Prabhu, and Varma 2016) and predicting labels in
the tail becomes significantly hard for lack of training data. For these reasons, and the sheer scale of
data, traditional multi-label classifiers are rendered
impracticable. State-of-the-art approaches to extreme
multi-label learning fall broadly under two classes: 1)
embedding based methods, e.g. L EML (Yu et al. 2014),
W SABIE
(Weston, Bengio, and Usunier 2010),
S LEEC (Bhatia et al. 2015), P D -S PARSE (Yen et al. 2016)),
and 2) tree-based methods (Prabhu and Varma 2014;
Jain, Prabhu, and Varma 2016). The first class of approaches
are generally scalable and work by embedding the highdimensional label vectors to a lower-dimensional space and
learning a regressor in that space. In most cases, these methods rely on a key assumption that the binary label matrix is
low rank and consequently the label vectors can be embedded into a lower-dimensional space. At the time of prediction, a decompression matrix is used to retrieve the original
label vector from the low-dimensional embeddings. As corroborated by recent empirical evidence (Bhatia et al. 2015;
Jain, Prabhu, and Varma 2016), approaches based on
standard structural assumptions such as low-rank label matrix fail and perform poorly on the tail. The
second class of methods (tree-based) methods for
multi-label learning try to move away from rigid
structural
assumptions
(Prabhu and Varma 2014;
Jain, Prabhu, and Varma 2016), and have been demonstrated to work very well especially on the tail labels.
In this work, we propose an embedding based
approach, closely following the framework of
S LEEC (Bhatia et al. 2015), that leverages a word vector embedding technique (Mikolov et al. 2013) which has
found resounding success in natural language processing
tasks. Unlike other embedding based methods, S LEEC has
the ability to learn non-linear embeddings by aiming to
preserve only local structures and example neighborhoods.
We show that by learning rich word2vec style embedding
for instances (and labels), we can a) achieve competitive multi-label prediction accuracies, and often improve
over the performance of the state-of-the-art embedding
approach S LEEC and b) cope with missing labels, by
incorporating auxiliary information in the form of labellabel co-occurrences, which most of the state-of-the-art
methods can not. Furthermore, our learning algorithm

admits significantly faster implementation compared to
other embedding based approaches. The distinguishing
aspect of our work is that it draws inspiration from distributional semantics approaches (Mikolov et al. 2013;
Le and Mikolov 2014), widely used for learning non-linear
representations of text data for natural language processing
tasks such as understand word and document semantics,
classifying documents, etc.
Our main contributions are:
1. We leverage an interesting connection between the problem of learning distributional semantics in text data analysis and the multi-label learning problem. To the best of
our knowledge, this is a novel application.
2. The proposed objectives for learning embeddings can be
solved efficiently and scalably; the learning reduces to a
certain matrix factorization problem.
3. Unlike existing multi-label learning methods, our method
can also leverage label co-occurrence information while
learning the embeddings; this is especially appealing
when a large fraction of labels are missing in the label
matrix.
4. We show improvement in training time as compared to
state-of-art label embedding methods for extreme multilabel learning, while being competitive in terms of label
prediction accuracies; we demonstrate scalability and prediction performance on several state-of-the-art moderateto-large scale multi-label benchmark datasets.
The outline of the paper is as follows. We begin by setting
up notation, background and describing the problem formulation in Section . In Section , we present our training algorithms based on learning word embeddings for understanding word and document semantics. Here we propose two
objectives, where we progressively incorporate auxiliary information viz. label correlations. We present comprehensive
experimental evaluation in Section , and conclude.

Problem Formulation and Background
In the standard multi-label learning formulation, the
learning algorithm is given a set of training instances
{x1 , x2 , . . . , xn }, where xi ∈ Rd and the associated label
vectors {y1 , y2 , . . . , yn }, where yi ∈ {0, 1}L. In real-world
multi-label learning data sets, one does not usually observe
irrelevant labels; here yij = 1 indicates that the jth label is
relevant for instance i but yij = 0 indicates that the label is
missing or irrelevant. Let Y ∈ {0, 1}n×L denote the matrix
of label vectors. In addition, we may have access to labelL×L
label co-occurrence information, denoted by C ∈ Z+
(e.g., number of times a pair of labels co-occur in some external source such as the Wikipedia corpus). The goal in multilabel learning is to learn a vector-valued function f : x 7→ s,
where s ∈ RL scores the labels.
Embedding-based approaches typically model f as a com′
posite function h(g(x)) where, g : Rd → Rd and
′
h : Rd → RL . For example, assuming both g and h
as linear transformations, one obtains the formulation proposed by (Yu et al. 2014). The functions g and h can be

learnt using training instances or label vectors, or both.
More recently, non-linear embedding methods have been
shown to help improve multi-label prediction accuracies
significantly. In this work, we follow the framework of
(Bhatia et al. 2015), where g is a linear transformation, but
h is non-linear, and in particular, based on k-nearest neighbors in the embedded feature space.
′
In S LEEC, the function g : Rd → Rd is given by
′
′
g(x) = V x where V ∈ Rd ×d . The function h : Rd → RL
is defined as:


n
h z; {zi , yi }i=1 =

1 X
yi ,
|Nk |

(1)

i∈Nk

where zi = g(xi ) and Nk denotes the k−nearest neighbor
training instances of z in the embedded space. Our algorithm
for predicting the labels of a new instance is identical to that
of S LEEC and is presented for convenience in Algorithm 1.
Note that, for speeding up predictions, the algorithm relies
on clustering the training instances xi ; for each cluster of
instances Qτ , a different linear embedding gτ , denoted by
V τ , is learnt.
Algorithm 1 Prediction Algorithm
Input: Test point: x, no. of nearest neighbors k, no. of
desired labels p.
1. Qτ : partition closest to x.
2. z ← V τ x.
3. Nk ← k nearest neighbors of z in the embedded instances of Qτ .
4. s = h(z; {zi , yi }i∈Qτ ) where h is defined in (1).
return top p scoring labels according to s.
In this work, we focus on learning algorithms for the functions g and h, inspired by their successes in natural language
processing in the context of learning distributional semantics (Mikolov et al. 2013; Levy and Goldberg 2014). In particular, we use techniques for inferring word-vector embeddings for learning the function h using a) training label vectors yi , and b) label-label correlations C ∈ RL×L .
Word embeddings are desired in natural language processing in order to understand semantic relationships between words, classifying text documents, etc. Given a text
corpus consisting of a collection of documents, the goal
is to embed each word in some space such that words appearing in similar contexts (i.e. adjacenct words in documents) should be closer in the space, than those that do
not. In particular, we use the word2vec embedding approach (Mikolov et al. 2013) to learn an embedding of instances, using their label vectors y1 , y2 , . . . , yn . S LEEC also
uses nearest neighbors in the space of label vectors yi in order to learn the embeddings. However, we show in experiments that word2vec based embeddings are richer and
help improve the prediction performance significantly, especially when there is a lot of missing labels. In the subsequent
section, we discuss our algorithms for learning the embeddings and the training phase of multi-label learning.

Learning Instance and Label Embeddings
There are multiple algorithms in the literature for
learning
word
embeddings
(Mikolov et al. 2013;
Pennington, Socher, and Manning 2014). In this work,
we use the Skip Gram Negative Sampling (SGNS) technique, for two reasons a) it is shown to be competitive in
natural language processing tasks, and more importantly b)
it presents a unique advantage in terms of scalability, which
we will address shortly after discussing the technique.
Skip Gram Negative Sampling. In SGNS, the goal is to
′
learn an embedding z ∈ Rd for each word w in the vocabulary. To do so, words are considered in the contexts in which
they occur; context c is typically defined as a fixed size window of words around an occurrence of the word. The goal is
to learn z such that the words in similar contexts are closer
to each other in the embedded space. Let w′ ∈ c denote a
word in the context c of word w. Then, the likelihood of observing the pair (w, w′ ) in the data is modeled as a sigmoid
of their inner product similarity:

Note that Nk (yi ) denotes the k-nearest neighborhood of ith
instance in the space of label vectors 1 or instance embedding. After learning label embeddings zi , we can learn the
function g : x → z by regressing x onto z, as in S LEEC.
Solving (3) for zi using standard word2vec implementations can be computationally expensive, as it requires training multiple-layer neural networks. Fortunately, the learning can be significantly sped up using the key observation
by (Levy and Goldberg 2014).
(Levy and Goldberg 2014) showed that solving SGNS objective is equivalent to matrix factorization of the shifted positive point-wise mutual information (SPPMI) matrix defined
as follows. Let Mij = hyi , yj i.


Mij ∗ |M |
P
PMIij (M ) = log P
k M(k,j)
k M(i,k) ∗

SPPMIij (M ) = max(PMIij (M ) − log(k), 0) (4)
Here, PMI is the point-wise mutual information matrix of M
and |M | denotes the sum of all elements in M . Solving the
problem (3) reduces to factorizing the shifted PPMI matrix
M.
Finally, we use ADMM (Boyd et al. 2011) to learn the re1
P (Observing (w, w′ )) = σ(hzw , zw′ i) =
. gressors V over the embedding space formed by z . Overall
i
1 + exp(h−zw , zw′ i)
training algorithm is presented in 2.
To promote dissimilar words to be further apart, negative sampling is used, wherein randomly sampled negAlgorithm 2 Learning embeddings via SPPMI factorizaative examples (w, w′′ ) are used. Overall objective fation (E X MLDS1).
vors zw , zw′ , zw′′ that maximize the log likelihood of obInput. Training data (xi , yi ), i = 1, 2, . . . , n.
serving (w.w′ ), for w′ ∈ c, and the log likelihood of
c := SPPMI(M ) in (4), where Mij =
′′
′′
1. Compute M
P (not observing (w, w )) = 1 − P (Observing (w, w )) for
hy
,
y
i.
randomly sampled negative instances. Typically, n− negai j
c), and preserve top d′ singular
tive examples are sampled per observed example, and the
2. Let U, S, V = svd(M
resulting SGNS objective is given by:
values and singular vectors.
3. Compute the embedding matrix Z = U S 0.5 , where
X X

′
log σ(hzw , zw′ i) +
max
Z ∈ Rn×d , where ith row gives zi
z
4. Learn V
s.t. XV T
=
Z using
w
w ′ :(w ′ ,w)
(2)

ADMM
(Boyd
et
al.
2011),
where
X
is
the
matrix
X

n−
with xi as rows.
log σ(−hzw , zw′′ i) ,
#w ′′
return V, Z
w

where #w denotes the total number of words in the vocabulary, and the negative instances are sampled uniformly over
the vocabulary.

Embedding label vectors
We now derive the analogous embedding technique for
multi-label learning. A simple model is to treat each instance
as a "word"; define the "context" as k-nearest neighbors of
a given instance in the space formed by the training label
vectors yi , with cosine similarity as the metric. We then arrive at an objective identical to (2) for learning embeddings
z1 , z2 , . . . , zn for instances x1 , x2 , . . . , xn respectively:
max

z1 ,z2 ,...,zn

n  X
X
i=1

j:Nk (yi )


log σ(hzi , zj i) +

n− X
log σ(−hzi , zj ′ i)
n ′
j




,

(3)

We refer to Algorithm 2 based on fast PPMI matrix factorization for learning label vector embeddings
as E X MLDS1. We can also optimize the objective 3 using a
neural network model (Mikolov et al. 2013); we refer to this
word2vec method for learning embeddings in Algorithm 2
as E X MLDS2.

Using label correlations
In various practical natural language processing applications, superior performance is obtained using joint models
for learning embeddings of text documents as well as individual words in a corpus (Dai, Olah, and Le 2015). For example, in PV-DBoW (Dai, Olah, and Le 2015), the objective while learning embeddings is to maximize similarity
1
Alternately, one can consider the neighborhood in the ddimensional feature space xi ; however, we perform clustering in
this space for speed up, and therefore the label vectors are likely to
preserve more discriminative information within clusters.

between embedded documents and words that compose the
documents. Negative sampling is also included, where the
objective is to minimize the similarity between the document
embeddings and the embeddings of high frequency words.
In multi-label learning, we want to learn the embeddings
of labels as well as instances jointly. Here, we think of labels as individual words, whereas label vectors (or instances
with the corresponding label vectors) as paragraphs or documents. As alluded to in the beginning of Section , in many
real world problems, we may also have auxiliary label correlation information, such as label-label co-occurrence. We
can easily incorporate such information in the joint modeling approach outlined above. To this end, we propose the
following objective that incorporates information from both
label vectors as well as label correlations matrix:
max Oz,z̄ = µ1 Oz̄1 + µ2 O2z + µ3 O3 {z,z̄}
z,z̄

O1z̄ =

L 
X
i=1

X


log σ(hz̄i , z̄j i) +

j:Nk (C(i,:))



n1− X
′
log σ(−hz̄i , z̄j i) ,
L ′

(5)

(6)

j

O2z =

n 
X
i=1

X

j:Nk (M (i,:))


log σ(hzi , zj i) +



n2− X
log σ(−hzi , zj ′ i) ,
n ′

(7)

L  X
X
i=1

n3−
L

j:yij =1

X
j′


log σ(hzi , z̄j i) +

log σ(−hzi , z̄j ′ i)

Algorithm 3 Learning joint label and instance embeddings
via SPPMI factorization (E X MLDS3).
Input. Training data (xi , yi ), i = 1, 2, . . . , n and C (labellabel correlation matrix) and objective weighting µ1 ,µ2
and µ3 .
b := SPPMI(A) in (4); write
1. Compute A


µ2 M µ3 Y
,
A=
µ3 Y T µ1 C
Mij = hyi , yj i, Y is label matrix with yi as rows.
b and preserve top d′ singular
2. Let U, S, V = svd(A),
values and singular vectors.
3. Compute the embedding matrix Z = U S 0.5 ; write
 
Z1
Z=
,
Z2
′

j

O3{z,z̄} =

objective efficiently utilizes label-label correlations to help
improve embedding and, importantly, to cope with missing
labels. The complete training procedure using SPPMI factorization is presented in Algorithm 3. Note that we can use
the same arguments given by (Levy and Goldberg 2014) to
show that the proposed combined objective (5) is solved by
SPPMI factorization of the joint matrix A given in Step 1 of
Algorithm 3.

(8)




Here, zi , i = 1, 2, . . . , n denote embeddings of instances
while z̄i , i = 1, 2, . . . , L denote embeddings of labels.
Nk (M (i, :)) denotes the k-nearest neighborhood of ith instance in the space of label vectors. Nk (C(i, :)) denotes the
k-nearest neighborhood of ith label in the space of labels.
Here, M defines instance-instance correlation i.e. Mij =
hyi , yj i and C is the label-label correlation matrix. Clearly,
(7) above is identical to (3). O1z̄ tries to embed labels z̄i in a
vector space, where correlated labels are closer; O2z tries to
embed instances zi in such a vector space, where correlated
instances are closer; and finally, O3{z,z̄} tries to embed labels
and instances in a common space where labels occurring in
the ith instance are closer to the embedded instance.
Overall the combined objective O{z,z̄} promotes learning
a common embedding space where correlated labels, correlated instances and observed labels for a given instance
occur closely. Here µ1 ,µ2 and µ3 are hyper-parameters to
weight the contributions from each type of correlation. n1−
negative examples are sampled per observed label, n2− negative examples are sampled per observed instance in context of labels and n3− negative examples are sampled per observed instance in context of instances. Hence, the proposed

where rows of Z1 ∈ Rn×d give instance embedding and
′
rows of Z2 ∈ RL×d give label embedding.
4. Learn V
s.t. XV T
=
Z1 using
ADMM (Boyd et al. 2011), where X is the matrix
with xi as rows.
return V, Z

Algorithm 4 Prediction Algorithm with Label Correlations
(E X MLDS3 prediction).
Input: Test point: x, no. of nearest neighbors k, no. of
desired labels p, V , embeddings Z1 and Z2 .
1. Use Algorithm 1 (Step 3) with input Z1 , k, p to get
score s1 .
3. Get score s2 = Z2 V x
4. Get final score s = kss11 k + kss22 k .
return top p scoring labels according to s.

At test time, given a new data point we could use the Algorithm 1 to get top p labels. Alternately, we propose to use Algorithm 4 that also incorporates similarity with label embeddings Z2 along with Z1 during prediction, especially when
there are very few training labels to learn from. In practice,
we find this prediction approach useful. Note the zi corresponds to the ith row of Z1 , and z̄j corresponds to the j th
row of Z2 . We refer the Algorithm 3 based on the combined
learning objective (5) as E X MLDS3.

Experiments
We conduct experiments on commonly used benchmark
datasets from the extreme multi-label classification repository provided by the authors of (Prabhu and Varma 2014;
Bhatia et al. 2015) 2 ; these datasets are pre-processed, and
have prescribed train-test splits. Statistics of the datasets
used in experiments is shown in Table 1. We use the standard,
practically relevant, precision at k (denoted by Prec@k) as
the evaluation metric of the prediction performance. Prec@k
denotes the number of correct labels in the top k predictions. We run our code and all other baselines on a Linux
machine with 40 cores and 128 GB RAM. We implemented
our prediction Algorithms 1 and 4 in M ATLAB. Learning
Algorithms 2 and 3 are implemented parlty in Python and
partly in M ATLAB. The source code will be made available
later. We evaluate three models (a) E X MLDS1 i.e. Algorithm 2 based on fast PPMI matrix factorization for learning
label embeddings as described in Section , (b) E X MLDS2
based on optimizing the objective (3) as described in section
, using neural network (Mikolov et al. 2013) (c) E X MLDS3
i.e. Algorithm 3 based on combined learning objective (5).
Compared methods.
following baselines.

We compare our algorithms with the

1. S LEEC (Bhatia et al. 2015), which was shown to outperform all other embedding baselines on the benchmark
datasets.
2. L EML (Yu et al. 2014), an embedding based method. This
method also facilitates incorporating label information
(though not proposed in the original paper); we use the
code given by the authors of L EML which uses item features3 . We refer to the latter method that uses label correlations as L EML -I MC.
3. FAST XML
method.

(Prabhu and Varma 2014),

a

tree-based

4. P D -S PARSE (Yen et al. 2016), recently proposed embedding based method
5. P FASTRE XML (Jain, Prabhu, and Varma 2016) is an extension of FAST XML; it was shown to outperform all
other tree-based baselines on benchmark datasets.
6. D I SMEC (Babbar and Schölkopf 2017) is recently proposed scalable implementation of the O NE - VS -A LL
method.
7. DXML (Zhang et al. 2017) is a recent deep learning solution for multi-label learning
8. O NE - VS -A LL (Zhang et al. 2017) is traditional one vs all
multi-label classifier
We report all baseline results from the the extreme classification repository. 4 , where they have been curated; note that
all the relevant research work use the same train-test split for
benchmarking.
2

http://manikvarma.org/downloads/XC/XMLRepository.html
https://goo.gl/jdGbDPl
4
http://manikvarma.org/downloads/XC/XMLRepository.html

Hyperparameters. We use the same embedding dimensionality, preserve the same number of nearest neighbors for learning embeddings as well as at prediction
time, and the same number of data partitions used in
S LEEC (Bhatia et al. 2015) for our method E X MLDS1and
E X MLDS2. For small datasets, we fix negative sample size
to 15 and number of iterations to 35 during neural network
training, tuned based on a separate validation set. For large
datasets (4 and 5 in Table 1), we fix negative sample size
to 2 and number of iterations to 5, tuned on a validation set.
In E X MLDS3, the parameters (negative sampling) are set
identical to E X MLDS1. For baselines, we either report results from the respective publications or used the best hyperparameters reported by the authors in our experiments, as
needed.
Performance evaluation. The performance of the compared methods are reported in Table 3. Performances of the
proposed methods E X MLDS1 and E X MLDS2 are found
to be similar in our experiments, as they optimize the same
objective 3; so we include only the results of E X MLDS1 in
the Table. We see that the proposed methods achieve competitive prediction performance among the state-of-the-art
embedding and tree-based approaches. In particular, note
that on Medialmill and Delicious-200K datasets our method
achieves the best performance.
Training time. Objective 3 can be trained using a neural
network, as described in (Mikolov et al. 2013). For training
the neural network model, we give as input the k-nearest
neighbor instance pairs for each training instance i, where
the neighborhood is computed in the space of the label
vectors yi . We use the Google word2vec code5 for training. We parallelize the training on 40 cores Linux machine
for speed-up. Recall that we call this method E X MLDS2.
We compare the training time with our method E X MLDS1,
which uses a fast matrix factorization approach for learning
embeddings. Algorithm 2 involves a single SVD as opposed
to iterative SVP used by S LEEC and therefore it is significantly faster. We present training time measurements in Table 2. As anticipated, we observe that E X MLDS2 which
uses neural networks is slower than E X MLDS1 (with 40
cores). Also, among the smaller datasets, E X MLDS1 trains
14x faster compared to S LEECon Bibtex dataset. In the large
dataset, Delicious-200K, E X MLDS1 trains 5x faster than
S LEEC.
Coping with missing labels. In many real-world scenarios, data is plagued with lots of missing labels. A desirable
property of multi-label learning methods is to cope with
missing labels, and yield good prediction performance with
very few training labels. In the dearth of training labels, auxiliary information such as label correlations can come in
handy. As described in Section , our method E X MLDS3 can
learn from additional information. The benchmark datasets,
however, do not come with auxiliary information. To simulate this setting, we hide 80% non-zero entries of the training label matrix, and reveal the 20% training labels to learning algorithms. As a proxy for label correlations matrix C,
we simply use the label-label co-occurrence from the 100%

3

5

https://code.google.com/archive/p/word2vec/

Table 1: Dataset statistics
Dataset
Bibtex (Katakis, Tsoumakas, and Vlahavas 2008)
Delicious (Tsoumakas, Katakis, and Vlahavas 2008)
EURLex-4K (Loza Mencía and Fürnkranz 2008)
rcv1v2 (Lewis et al. 2004)
Delicious-200K (Tsoumakas, Katakis, and Vlahavas 2008)
MediaMill (Snoek et al. 2006)

Feature
1836
500
5000
47236
782585
120

Label
159
983
3993
101
205443
101

Train
4880
12920
15539
3000
196606
30993

Test
2515
3185
3809
3000
100095
12914

Table 2: Comparing training times (in seconds) of different methods
Method
E X MLDS1
E X MLDS2
S LEEC

Bibtex
23
143.19
313

Delicious
259
781.94
1351

Eurlex
580.9
880.64
4660

Mediamill
1200
12000
8912

Delicious-200K
1937
13000
10000

Table 3: Comparing prediction performance of different methods(− mean unavailable results). Note that although SLEEC performs slightly
better, our model is much faster as shown in the results in Table 2. Also note the performance of our model in Table 5 when a significant
fraction of labels are missing is considerably better than SLEEC
Dataset

Bibtex

Delicious

Eurlex

Mediamill

Delicious-200K

Prec@k
P@1
P@3
P@5
P@1
P@3
P@5
P@1
P@3
P@5
P@1
P@3
P@5
P@1
P@3
P@5

E X MLDS1
63.38
38.00
27.64
67.94
61.35
56.3
77.55
64.18
52.51
87.49
72.62
58.46
46.07
41.15
38.57

Embedding Based
DXML
S LEEC
L EML
63.69
65.29
62.54
37.63
39.60
38.41
27.71
28.63
28.21
67.57
68.10
65.67
61.15
61.78
60.55
56.7
57.34
56.08
77.13
79.52
63.40
64.21
64.27
50.35
52.31
52.32
41.28
87.37
84.01
88.71
72.6
67.20
71.65
52.80
56.81
58.39
44.13
47.50
40.73
39.88
42.00
37.71
37.20
39.20
35.84

training data, i.e. C = Y T Y where Y denotes the full training matrix. We give higher weight µ1 to O1 during training
in Algorithm 3. For prediction, We use Algorithm 4 which
takes missing labels into account. We compare the performance of E X MLDS3with S LEEC, L EML and L EML -I MCin
Table 5. Note that while S LEEC and L EML methods do not
incorporate such auxiliary information, L EML -I MC does. In
particular, we use the spectral embedding based features i.e.
SVD of Y Y T and take all the singular vectors corresponding to non-zero singular values as label features. It can be
observed that on all three datasets, E X MLDS3 performs
significantly better by huge margins. In particular, the lift
over L EML -I MC is significant, even though both the methods use the same information. This serves to demonstrate
the strength of our approach.

P D -S PARSE
61.29
35.82
25.74
51.82
44.18
38.95
76.43
60.37
49.72
81.86
62.52
45.11
34.37
29.48
27.04

Tree Based
P FASTRE XML
FAST XML
63.46
63.42
39.22
39.23
29.14
28.86
67.13
69.61
62.33
64.12
58.62
59.27
75.45
71.36
62.70
59.90
52.51
50.39
84.22
83.98
67.33
67.37
53.04
53.02
41.72
43.07
37.83
38.66
35.58
36.19

Others
O NE - VS -A LL
D I SMEC
62.62
39.09
28.79
65.01
58.88
53.28
79.89
82.40
66.01
68.50
53.80
57.70
83.57
65.60
48.57
45.50
38.70
35.50

Table 4: Evaluating competitive methods in the setting where 80%
of the training labels are hidden
Dataset
Bibtex
Eurlex
rcv1v2

Prec@k
P@1
P@3
P@5
P@1
P@3
P@5
P@1
P@3
P@5

E X MLDS3
48.51
28.43
20.7
60.28
44.87
35.31
81.67
52.82
37.74

S LEEC
30.5
14.9
9.81
51.4
37.64
29.62
41.8
17.48
10.63

L EML
35.98
21.02
15.50
26.22
22.94
19.02
64.83
42.56
31.68

L EML -I MC
41.23
25.25
18.56
39.24
32.66
26.54
73.68
48.56
34.82

Joint Embedding and Regression. We extended SGNS
objective for joint training i.e. learning of embeddings Z and
regressor V simultaneously.

∇V

Ot+1
= Oti + η∇V Oi
i
Gradient of objective 3 w.r.t to V i.e. ∇V Oi is describe in
detail below :
Given,

∇V

Kij = hzi zj i = hzTi zj i
′

zi = V xi , where V ∈ Rd ×d

max

z1 ,z2 ,...,zn

n  X
X
i=1

j:Nk (yi )


log σ(hzi , zj i) +



n− X
′
log σ(−hzi , zj i) ,
n ′

(9)

n  X
X
i=1

j:Nk (yi )


log σ(hV xi , V xj i) +



n− X
′
log σ(−hV xi , V xj i) ,
n ′

n  X
X
i=1

j:Nk (yi )

Ot+1
= Oti + η∇V Oi
i

(10)


 n− X

log σ(Kij ) +
log σ(−Kij ′ ) ,
n ′
j

rewriting for only ith instance, we have
X
 n− X

log σ(Kij ) +
Oi =
log σ(−Kij ′ ) ,
n ′
j

j:Nk (yi )

X

∇V Oi =

σ(−Kij )∇V Kij −

n− X
σ(Kij ′ )∇V Kij ′
n ′

here, ∇V Kij can be obtain through,
∇V Kij = V (xi xTj + xj xTi ) = zi .xTj + zj .xTi
Sometime cosine similarity perform better then dot product because of scale invariant, in that case the gradient would
modify to :

Kij = h

zi zj
hzTi zj i
i=
kzi k kzj k
kzi kkzj k

∇V hzi zj i = ∇V (V xi )zj + ∇V (V xj )zi
=

hzi xTj i

To implement joint learning, we modified the existing
public code of state of art embedding based extreme
classification approach AnnexML (Tagami 2017a) 6 , by
replacing the DSSM 7 training objective by word2vec
objective, while keeping cosine similarity, partitioning
algorithm, and approximate nearest prediction algorithm
same. For efficient training of rare label, we keep the coefficient ratio of negative to positive samples as 20:1, while
training. We used the same hyper-parameters i.e.embedding
size as 50, number of learner for each cluster as 15,
number of nearest neighbor as 10, number of embedding
and partitioning iteration both 100, gamma as 1, label
normalization as true, number of threads as 32. We obtain state of art result i.e. similar (some dataset slightly
better also) to D I SMEC (Babbar and Schölkopf 2017),
PPD SPARSE
(Yen et al. 2017)
and
ANNEX ML (Tagami 2017b) on all large datasets, see table 5
for details results.

Conclusions and Future Work

j

j:Nk (yi )

+

hzj xTi i

=V

(hxi xTj

+

xj xTi i)

1
1
,c =
kzi k
kzj k

Gradient update after tth iteration for ith instance,

j

V

(14)

∇V Kij = −ab3 czi (xi )T − abc3 zj (xj )T + bc(zi xTj + zj xTi )

rewriting with s.t.t V and Kij , we obtained

max

−1
−1 T −3
1
= ∇V zj zTj 2 =
zj zj 2 ∇V zj zTj =
kzj k
2
−1 T −3
zj zj 2 xj zTj
2

a = zTi zj , b =

j

V

(13)

Let,

Objective 3 :

max

−1
1
−1 T −3
= ∇V zi zTi 2 =
zi zi 2 ∇V zi zTi =
kzi k
2
−1 T −3
zi zi 2 xi zTi
2

(11)

We proposed a novel objective for learning label embeddings
for multi-label classification, that leverages word2vec embedding technique; furthermore, the proposed formulation
can be optimized efficiently by SPPMI matrix factorization. Through comprehensive experiments, we showed that
the proposed method is competitive compared to state-ofthe-art multi-label learning methods in terms of prediction
accuracies. We also extended SGNS objective for joint learning of embeddings Z and regressor V and obtain state of art
results. We proposed a novel objective that incorporates side
information, that is particularly effective in handling missing
labels.
6

(12)

7

Code: https://research-lab.yahoo.co.jp/en/software/
https://www.microsoft.com/en-us/research/project/dssm/

Table 5: Performance on multiple large datasets with Joint Learning

Prec@1
Prec@2
Prec@3
Prec@4
Prec@5
nDCG@1
nDCG@2
nDCG@3
nDCG@4
nDCG@5

AmazonCat-13K
93.05
86.56
79.18
72.06
64.54
93.05
89.60
87.72
86.35
85.92

Wiki10K-31K
86.82
80.44
74.30
68.61
63.68
86.82
81.89
77.22
72.92
69.13

Delicious-200K
47.70
43.67
41.22
39.37
37.98
47.70
44.63
42.75
41.34
40.27

References
[Babbar and Schölkopf 2017] Babbar, R., and Schölkopf, B.
2017. Dismec: Distributed sparse machines for extreme
multi-label classification. In Proceedings of the Tenth ACM
International Conference on Web Search and Data Mining,
WSDM ’17, 721–729. New York, NY, USA: ACM.
[Bhatia et al. 2015] Bhatia, K.; Jain, H.; Kar, P.; Varma, M.;
and Jain, P. 2015. Sparse local embeddings for extreme
multi-label classification. In Advances in Neural Information Processing Systems, 730–738.
[Boyd et al. 2011] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.;
and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends R in Machine Learning 3(1):1–
122.
[Dai, Olah, and Le 2015] Dai, A. M.; Olah, C.; and Le, Q. V.
2015. Document embedding with paragraph vectors. arXiv
preprint arXiv:1507.07998.
[Jain, Prabhu, and Varma 2016] Jain, H.; Prabhu, Y.; and
Varma, M. 2016. Extreme multi-label loss functions for
recommendation, tagging, ranking & other missing label applications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, 935–944. ACM.
[Katakis, Tsoumakas, and Vlahavas 2008] Katakis,
I.;
Tsoumakas, G.; and Vlahavas, I. 2008. Multilabel text
classification for automated tag suggestion. ECML PKDD
discovery challenge 75.
[Le and Mikolov 2014] Le, Q. V., and Mikolov, T. 2014. Distributed representations of sentences and documents. In
ICML, volume 14, 1188–1196.
[Levy and Goldberg 2014] Levy, O., and Goldberg, Y. 2014.
Neural word embedding as implicit matrix factorization. In
Advances in neural information processing systems, 2177–
2185.
[Lewis et al. 2004] Lewis, D. D.; Yang, Y.; Rose, T. G.; and
Li, F. 2004. Rcv1: A new benchmark collection for text categorization research. Journal of machine learning research
5(Apr):361–397.
[Loza Mencía and Fürnkranz 2008] Loza Mencía, E., and
Fürnkranz, J. 2008. Efficient pairwise multilabel classifica-

WikiLSHTC-325K
62.15
48.37
39.58
33.52
29.10
62.15
57.00
55.20
54.77
54.84

Wikipedia-500K
62.27
49.60
41.43
35.68
31.42
62.27
55.23
52.11
50.59
49.88

Amazon-670K
41.47
38.58
36.35
34.20
32.43
41.47
39.73
38.41
37.31
36.46

tion for large-scale problems in the legal domain. Machine
Learning and Knowledge Discovery in Databases 50–65.
[Mikolov et al. 2013] Mikolov, T.; Sutskever, I.; Chen, K.;
Corrado, G. S.; and Dean, J. 2013. Distributed representations of words and phrases and their compositionality. In
Advances in neural information processing systems, 3111–
3119.
[Pennington, Socher, and Manning 2014] Pennington,
J.;
Socher, R.; and Manning, C. D. 2014. Glove: Global
vectors for word representation. In EMNLP, volume 14,
1532–1543.
[Prabhu and Varma 2014] Prabhu, Y., and Varma, M. 2014.
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, 263–272. ACM.
[Snoek et al. 2006] Snoek, C. G.; Worring, M.; Van Gemert,
J. C.; Geusebroek, J.-M.; and Smeulders, A. W. 2006. The
challenge problem for automated detection of 101 semantic
concepts in multimedia. In Proceedings of the 14th ACM
international conference on Multimedia, 421–430. ACM.
[Tagami 2017a] Tagami, Y. 2017a. Annexml: Approximate
nearest neighbor search for extreme multi-label classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17, 455–464. New York, NY, USA: ACM.
[Tagami 2017b] Tagami, Y. 2017b. Learning extreme multilabel tree-classifier via nearest neighbor graph partitioning.
In Proceedings of the 26th International Conference on
World Wide Web Companion, WWW ’17 Companion, 845–
846. Republic and Canton of Geneva, Switzerland: International World Wide Web Conferences Steering Committee.
[Tsoumakas, Katakis, and Vlahavas 2008] Tsoumakas, G.;
Katakis, I.; and Vlahavas, I. 2008. Effective and efficient
multilabel classification in domains with large number of
labels. In Proc. ECML/PKDD 2008 Workshop on Mining
Multidimensional Data (MMD’08), 30–44.
[Weston, Bengio, and Usunier 2010] Weston, J.; Bengio, S.;
and Usunier, N. 2010. Large scale image annotation: learning to rank with joint word-image embeddings. Machine
learning 81(1):21–35.
[Yen et al. 2016] Yen, I. E.-H.; Huang, X.; Ravikumar, P.;

Zhong, K.; and Dhillon, I. 2016. Pd-sparse: A primal
and dual sparse approach to extreme multiclass and multilabel classification. In International Conference on Machine
Learning, 3069–3077.
[Yen et al. 2017] Yen, I. E.; Huang, X.; Dai, W.; Ravikumar,
P.; Dhillon, I.; and Xing, E. 2017. Ppdsparse: A parallel
primal-dual sparse method for extreme classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17,
545–553. New York, NY, USA: ACM.
[Yu et al. 2014] Yu, H.-F.; Jain, P.; Kar, P.; and Dhillon, I.
2014. Large-scale multi-label learning with missing labels. In International Conference on Machine Learning,
593–601.
[Zhang et al. 2017] Zhang, W.; Wang, L.; Yan, J.; Wang, X.;
and Zha, H. 2017. Deep extreme multi-label learning. arXiv
preprint arXiv:1704.03718.

Leveraging Distributional Semantics for
Multi-Label Learning
A2. SGNS Objective as Implicit SPPMI
factorization
The SGNS (Mikolov et al. 2013) objective is as follows:

Oi =

X

M
X

log(σ(Kij )) +

j∈Si

Ek∼PD [log(σ(−Kik ))]

k∼PD
0.75

where, PD = (#k)
#D , D is collection of all word-context
pairs and Kij represent dot-product similarity between the
embeddings of a given word (i) and context (j).
Here, #k represent total number of word-context pairs
with context (k).

Ek∼PD [log(σ(−Kik ))]

k∼PD

X (#k)0.75
log(σ(−Kik ))
#D

Ek∼PD [log(σ(−Kik ))] =

k∼PD

Ek∼PD [log(σ(−Kik ))] =
+

X

k∼PD &k6=j

(#j)0.75
log(σ(−Kij ))
#D

(#k)0.75
log(σ(−Kik ))
#D

Therefore,
Ej∼PD [log(σ(−Kij ))] =

O{i,j} = log(σ(Kij )) +

(#j)0.75
log(σ(−Kij ))
#D

M (#j)0.75
log(σ(−Kij ))
|S| #D

Let γKij = x, then
∇x O{i,j} = σ(−x) −

M (#j)0.75
σ(x)
|S| #D

equating ∇x J{i,j} to 0, we get :


e2x − 

1
M (#j)0.75
|S| #D





− 1 ex − 

1
M (#j)0.75
|S|
#D



=0

If we define y = ex , this equation becomes a quadratic
equation of y, which has two solutions, y =- 1 (which is
invalid given the definition of y) and
y=

1
M (#j)0.75
|S|
#D

=

Here |S| = #(i, j) and M = µ#(i) i.e. µ proportion of total
number of times label vector (i) appear with others.


#(i, j)(#D)
− log(µ)
Kij = log
#(i)(#j)0.75


P (i, j)
Kij = log
− log(µ)
P (i)P (j)
Here P(i,j),P(i) and P(j) represent probability of cooccurrences of {i, j} , occurrence of i and occurrence of j
respectively,
Therefore,
Kij = PMIij − log(µ) = log(P (i|j)) − log(µ)

M

|S|
X

O{i,j} = log(σ(Kij )) +

Substituting y with ex and x with Kij reveals :


#D ∗ |S|
Kij = log
M ∗ (#j)0.75

#D ∗ |S|
M ∗ (#j)0.75

Note that P M I + is inconsistent, therefore we used the
sparse and consistent positive PMI(PPMI) metric, in which
all negative values and nan are replaced by 0:
PPMIij = max(PMIij , 0)
Here, PMI is point wise mutual information and PPMI
is positive point wise mutual information. Similarity of two
{i, j} is more influenced by the positive neighbor they share
than by the negative neighbor they share as uninformative i.e.
0 value. Hence, SGNS objective can be cast into a weighted
matrix factorization problem, seeking the optimal lower ddimensional factorization of the matrix SPPMI under a metric which pays more for deviations on frequent #(i, j) pairs
than deviations on infrequent ones.
Using a similar derivation, it can be shown that noisecontrastive estimation (NCE) which is alternative to (SGNS)
can be cast as factorization of (shifted) log-conditionalprobability matrix


#(i, j)
Kij = log
− log(µ)
(#j)

