# Review of Extreme Multilabel Classification

Arpan Dasgupta<EMAIL_ADDRESS>
Department of Computer Science, CSTAR
International Institute of Information Technology, Hyderabad
Hyderabad-500032, India Siddhant Katyan<EMAIL_ADDRESS>
Department of Computer Science, CSTAR
International Institute of Information Technology, Hyderabad
Hyderabad-500032, India Shrutimoy Das<EMAIL_ADDRESS>
Department of Computer Science, CSTAR
International Institute of Information Technology, Hyderabad
Hyderabad-500032, India Pawan Kumar<EMAIL_ADDRESS>
Department of Computer Science, CSTAR
International Institute of Information Technology, Hyderabad
Hyderabad-500032, India

###### Abstract

Extreme multilabel classification or XML, in short, has emerged as a new
subtopic of interest in machine learning. Compared to traditional multilabel
classification, here the number of labels is extremely large, hence the name
extreme multilabel classification. Using classical one versus all
classification wont scale in this case due to large number of labels, same is
true for any other classifiers. Embedding of labels as well as features into
smaller label space is an essential first step. Moreover, other issues include
existance of head and tail labels, where tail labels are labels which exist in
relatively smaller number of given samples. The existence of tail labels
creates issues during embedding. This area has invited application of wide
range of approaches ranging from bit compression motivated from compressed
sensing, tree based embeddings, deep learning based latent space embedding
including using attention weights, linear algebra based embeddings such as
SVD, clustering, hashing, to name a few. The community has come up with a
useful set of metrics to identify the correctly the prediction for head or
tail labels.

Keywords: extreme classification, head and tail labels, compressed sensing,
deep learning, attention

##  1 Introduction

Extreme multilabel classification (XMC or XML) is an active area of research.
It is multilabel classification problem, where the number of labels are very
large going upto milions. The traditional classifiers such as one-vs-all, SVM,
neural networks, etc, cannot be applied directly due to two major reasons.
Firstly, the large number of labels creates a major bottleneck as it is not
possible to have a simple classifier for each label due to memory constraints.
Secondly, the presence of some labels which have very few samples in their
support make learning about these labels a challenge. These kinds of labels
are called tail labels and they will be a major problem which several methods
will specially focus on.

This XML comes up in several contexts, such as finding appropriate tags for a
Wikipedia page from the title or the full document, finding other items which
are frequently bought together from the name or description of the item and
finding appropriate tags for Ads from the Ad description. These are all real-
time applications, thus, memory and time constraints are an extremely
important factor in developing XML algorithms.

Table 1: Table of Common Notations Notation | Meaning
---|---
$\mathbb{R}$ | The set of real numbers
$\text{round}(\cdot)$ | Rounds the argument to 0 or 1
$\lVert\,{\cdot}\,\rVert_{F}$ | Frobenius norm of the argument
$\lVert\,{\cdot}\,\rVert_{\text{tr}}$ | Trace norm of the argument
$\lVert\,{\cdot}\,\rVert$ | Norm of the argument
$I$ | Identity matrix of appropriate dimension
$I_{k}$ |  Matrix containing the first $k$ columns of the identity matrix
$X^{\dagger}$ |  Pseudo-inverse of $X$
$\text{tr}(A)$ |  Trace of the matrix $A$
$A^{T}$ |  Transpose of the matrix $A$
$A^{-1}$ |  Inverse of the matrix $A$
$\text{ln}(\cdot)$ | Natural logarithm of the argument
$\phi$ | The empty set
$\nabla_{x}f$ |  Jacobian of $f$ with respect to $x$
$\nabla_{x}^{2}f$ |  Hessian of $f$ with respect to $x$
$V_{1:k}$ |  First $k$ columns of matrix $V$
$\text{rank}(A)$ |  Rank of matrix $A$
$\text{card}(S)$ |  Cardinality of the set $S$
$\text{vec}(A)$ |  Stack the columns of matrix $A$ to get a vector
$\text{nnz}(A)$ |  Number of non zero entries in the matrix $A$
$\mathbb{E}[X]$ |  Expected value of the random variable $X$
AUPRC | Area under the precision-recall curve
i.i.d | Independent and identically distributed
CG | Conjugate Gradient Method

##  2 Problem Formulation and Important Definitions

Though different papers in XML use different notation, recent papers
consistently use the following notation which will be followed in this review
paper too. The features are represented by the matrix $X\in\mathbb{R}^{n\times
d},$ where $n$ is the number of samples or instances, and $d$ represents the
the dimension of the features. The label matrix is represented by
$Y\in\\{0,1\\}^{n\times L},$ where $L$ represents the total number of labels.
Here $y_{il}=1$ represents that the $i-$th sample contains $l-$th label as
ground truth. Individual features and labels for a sample is represnted by
$x_{i}$ and $y_{i},$ where $i$ represents the sample in consideration. The
complete dataset is hence represented by $D=\\{x_{i},y_{i}\\}_{i=1}^{n}$.

Some other notation that appear several times are:

  1. 1.

$k$ which generally defines the dimension of the embedded space or the number
of children in a tree.

  2. 2.

$h$ which generally depicts a linear learner.

  3. 3.

$P$ which represents the compression matrix for mapping features from the
original or the embedded space.

These terms have been kept consistent throughout the paper, but have been
redefined in the context if it conflicts with a previous definition.

##### Ranking:

The problem of extreme classification requires the model to predict a set of
labels, which will be relevant to the given test sample. However, most models
do not produce binary results, instead, they provide a relevance score based
ranking for which labels are most likely according to the score. The exact
labels, if required, can be selected using a thresholding based on the
confidence. Thus, XML can be conceived of a ranking based problem instead of a
classification problem. Even the most common metrics used in XML expect a
ranking based output from the algorithm.

##### Head and Tail Labels:

The number of samples are not evenly distributed among the labels in a typical
XML problem. For example, in the Wiki-500K dataset Bhatia et al. (2016), 98%
of labels have less than 100 training instances. Thus, some of the labels have
enough data for the models to learn while most do not have enough data. These
are called head and tail labels respectively. Most models trained directly
without keeping the data distribution in mind are likely to develop an
implicit bias towards the head labels. Thus, tail-label based metrics are an
useful tool for measuring the effectiveness of a model.

Figure 1: The tail label distribution of $4$ popular XML datasets. The tail
labels have very less frequency as compared to the most frequent (head)
labels. Further, this imbalance grows with an increasing number of labels in
the dataset.

##  3 Datasets and Metrics

###  3.1 Datasets

There are different kinds of datasets which are used for benchmarking XML
results. One set of datasets is obtained from Amazon reviews and titles
scraped from internet archives. The reviews, titles and product summary are
used for prediction of the correct product tags McAuley and Leskovec (2013),
McAuley et al. (2015b) and McAuley et al. (2015a). Wikipedia based datasets
are used for prediction of tags on Wikipedia articles using the article or
just the titles Zubiaga (2012). The dataset EurLex formulates large scale
multilabel classification problems European legislature legal documents Loza
Mencía and Fürnkranz (2008). Other proprietary datasets such as that of
advertisement bids on bing are used by some methods.

###  3.2 Metrics

The following metrics are defined on the predicted score vector $\hat{y}\in
R^{L}$ and ground truth label vector $y\in\\{0,1\\}^{L}.$

##### Precision@k:

The most commonly used metric for measuring the performance of XML algorithms
is P@$k$. Here P@$k$ measures what fraction of the top-$k$ predicted labels
are present in the actual set of positive labels for the test data point.
Formally, P@$k$ is represented by

$P@k:=\frac{1}{k}{\sum_{l\in\text{rank}_{k}(\hat{y})}}y_{l}.$

##### DCG@k and nDCG@k:

Discounted Cumulative Gain (DCG) and Normalized Discounted Cumulative Gain
(nDCG) are common metrics for measuring the peformance of a ranking system.
Here DCG@$k$ measures how much the ground truth scores of each of the top $k$
labels predicted by the algorithm add up to. A log term for the positions is
added to ensure that better ordering is rewarded. Here nDCG@$k$ is a modified
version of the same metric which makes sure that the final score is well
bounded for better comparison.

$\displaystyle\text{DCG@k}:={\sum_{l\in\text{rank}_{k}(\hat{y})}}\frac{y_{l}}{\log(l+1)},\quad\quad\text{nDCG@k}:=\frac{\text{DCG}@k}{\sum_{l=1}^{\min(k,||y||_{0})}\frac{1}{\log(l+1)}}.$

##### Propensity Based Metrics:

Jain et al. (2016) proposes a version of all the above metrics which take into
account the fact that tail label predictions are performed well. The value
$p_{l}$ represents the propensity score of label $l$ which ensures that the
label bias is removed. This prevents models from achieving a high score from
just correctly predicting head labels and completely ignoring tail labels. The
corresponding versions of the metrics P@$k$, DCG@$k$ and nDCG@$k$ are called
PSP@$k$, PSDCG@$k$ and PSnDCG@$k$.

$\text{PSP}@k:=\frac{1}{k}{\sum_{l\in\text{rank}_{k}(\hat{y})}}\frac{y_{l}}{p_{l}}.$
$\text{PSDCG}@k:={\sum_{l\in\text{rank}_{k}(\hat{y})}}\frac{y_{l}}{p_{l}\log(l+1)}.$
$\text{PSnDCG}@k:=\frac{\text{PSDCG}@k}{\sum_{l=1}^{\min(k,||y||_{0})}\frac{1}{\log(l+1)}}.$

##  4 Review

There are several categories of methods for performing extreme classification.
We have broadly divided them into four categories based on the basic
philosophy of the algorithm.

###  4.1 Compressed Sensing

Figure 2: General flow of CS based methods

The methods in this category are based on the concept of compressing the label
space into a smaller, more manageable embedding space. The idea behind this
method comes from signal-processing, where the compressed sensing technique
can be used for signal reconstruction from much fewer samples than required,
due to the sparsity. In the extreme multi-label scenario, the idea is to
recover the original labels from predictions in a smaller label space. Again,
The compression operation is valid due to the sparsity of the original label
space.

Broadly, there are 3 steps in this procedure -

  1. 1.

Compression: The original label space is compressed into a smaller vector
space. This method of compression can use a simple linear transformation using
an orthogonal matrix, hashing functions, clustering based approaches etc.

  2. 2.

Learning: Since after compression, the output space is much smaller, methods
like binary relevance (predicting each element in the output space
individually using a binary classifier) become viable.

  3. 3.

Reconstruction: During prediction, the output in the compressed space must be
converted back to the original label space. This can be done using methods
such as solving optimization algorithms, using inverse projection matrices,
subset prediction algorithms etc.

The paper Hsu et al. (2009) was the first to make use of this technique. The
application of compressed sensing in the XML problem was motivated from the
observation that even though the label space of multi-label classification may
be very high dimensional, the label vector for a given sample is often sparse.
This sparsity of a label vector is be referred to as the output sparsity. The
proposed method utilizes the sparsity of $\mathbb{E}[y|x]$ rather than that of
$y$. $y$ may be sparse but $\mathbb{E}[y|x]$ may have a large support. This
may happen if there are many similar labels.

The proposed method proceeds in three steps. First, it compresses
$\\{(x_{i},y_{i})\\}$ to $\\{(x_{i},h_{i})\\},$ where $g_{i}=Py_{i}\in R^{k}$
using a random compression matrix $P\in\mathbb{R}^{k\times L}$ where $k$ is
determined by the required sparsity level $s$. It is ensured that $k$ is
logarithmic with respect to $L$. Next, for $j=1:k$, a function $h_{j}(x)$ is
learnt to predict $g_{i}[j]$ for every sample $i$. Finally, during prediction,
for an input vector $x$, compute $H(x)=[h_{1}(x),\dots,h_{k}(x)].$ Then solve
an optimization problem for finding a $s$-sparse vector $\tilde{y}$ such that
$P.\tilde{y}$ is closest to $H(x)$ by some pre-defined metric.

The goal of the problem is to learn a predictor $F:X\rightarrow Y$ such that
the error $\mathbb{E}_{x}||F(x)-\mathbb{E}(y|x)||_{2}^{2}$ is minimized. The
label space dimension $L$ is very large but $\mathbb{E}(y|x)$ of the
corresponding label vector $y\in Y$ is $s$-sparse. Given a sample
$\\{(x_{i},y_{i})\\}_{i=1}^{n},$ we obtain a compressed sample
$\\{(x_{i},Py_{i})\\}_{i=1}^{n}$ and then learn a predictor $H$ with the
objective of minimizing the error
$\mathbb{E}_{x}||H(x)-\mathbb{E}(Py|x)||_{2}^{2}.$ Then, the prediction
$\mathbb{E}(y|x)$ can be obtained by composing the predictor $H$ of
$\mathbb{E}(Py|x)$ with a reconstruction algorithm
$R:\mathbb{R}^{K}\rightarrow\mathbb{R}^{L}.$ The algorithm $R$ maps the
predictions of compressed labels $h\in\mathbb{R}^{k}$ to predictions of $y\in
Y$ in the original output space. This mapping is done by finding a sparse
vector $\tilde{y}$ such that $P\tilde{y}$ closely approximates the compressed
labels $h.$

The compression step can be ensured to give a close approximation of the
original feature vector if the compression matrix $P$ maintains certain
isometry properties as explained in the paper. For the reconstruction
algorithm, a greedy sparse compressed sensing reconstruction algorithm called
Orthogonal Matching Pursuit (OMP) is used, first proposed in Pati et al.
(1993).

#####

Figure 3: An example of the hypercube representation. Each axis represents
whether a specific label is present. The entire label space is represented by
the set of vertices.

The previously stated method reduces the feature space significantly, enabling
the method to train efficiently on large number of labels, but solving an
optimization problem using OMP everytime during prediction is expensive. In
the paper Tai and Lin (2012), a method is proposed which performs label space
reduction efficiently and handles fast reconstruction. An SVD based approach
is adopted for finding an orthogonal projection matrix which captures the
correlation between labels. This allows easier reconstruction using the
transpose of the projection matrix. The paper also uses a hypercube to model
the label space of multi-label classification. It shows that algorithms such
as binary relevance (BR, also called one-vs-all), compressive sensing (CS) can
also be derived from the hypercube view.

The hypercube view aims to represent the label set $\mathcal{Y}$ of a given
sample using a vector $y\in\\{0,1\\}^{L},$ where $\ell\in y$ iff $\ell^{th}$
component of $y$ is 1. As shown in Figure 3 (with $L=3$), each vertex of an
$L$-dimensional hypercube represents a label set $\mathcal{Y}$. Each component
of $y$ corresponds to one axis of a hypercube, which indicates the presence or
absence of a label $\ell$ in $\mathcal{Y}.$

One vs All classification (also called Binary Relevance) and the Compressed
Sensing Methods discussed can be formulated to be operations on this
hypercube. The Binary Relevance method can be interpreted as projecting the
hypercube into each of the $L$ dimensions before predicting. Using the
hypercube view, each iteration of CS can be thought of as projecting the
vertices to a random direction before training. Since $K\ll L,$ this new
subspace is much smaller than the original space that the hypercube belongs
to.

Using the hypercube view, each iteration of CS can be thought of as projecting
the vertices to a random direction before training. Since $K\ll L,$ this new
subspace is much smaller than the original space that the hypercube belongs
to. Thus, the label-set sparsity assumption, which implies that only a small
number of vertices in the original hypercube are of relevance for the multi-
label classification task, allows CS to work on a small subspace.

A framework called Linear Label Space Transformation (LLST) is proposed by the
paper, which focuses on a $K$-dimensional subspace of $\mathbb{R}^{L}$ instead
of the whole hypercube. Each vertex $v$ of the hypercube is encoded to the
point $h$ in the $K$-dimensional space by projection. Then, a multi-
dimensional regressor $r(x)$ is trained to predict $h$. Then, LLST maps $r(x)$
back to a vertex of the hypercube in $\mathbb{R}^{L}$ using some decoder $D$.
LLST basically gives a more formal definition to compressed sensing based
methods in the XML context, although it assumes that the compression step must
be linear.

Algorithm 1 Linear Label Space Transformation (LLST)

1:Encode $\\{(x_{n},y_{n})\\}$ to $\\{(x_{n},h_{n})\\}$ where $h_{n}=Py_{n}$
is a point on the $K$-dimensional space obtained using a projection matrix
$P\in\mathbb{R}^{K\times L}.$

2:For $k=1:K,$ learn a function $r_{k}(x)$ from
$\\{(x_{n},h_{n}[k])\\}_{n=1}^{N}.$

3:For each input vector $x,$ compute
$r(x)=[r_{1}(x),r_{2}(x),\cdots,r_{K}(x)].$

4:Return $D(r(x))$ where $D:\mathbb{R}^{K}\rightarrow\\{0,1\\}^{L}$ is a
decoding function from the $K$-dimensional subspace to the hypercube.

The choice of the decoder $D$ depends on the choice of projection $P$. For BR,
we can simply take $P=I$ as the projection, and $D$ as the component-wise
round(.) function. For CS, the projection matrix, $P$, is chosen randomly from
an appropriate distribution and $D$, the reconstruction algorithm involves
solving an optimization problem for each different $x$.

Taking advantage of the hypercube sparsity in large multi-label classification
datasets, we can take $K\ll\ell$ for the LLST algorithm, which in turn will
reduce the computational cost. The proposed Principle Label Space
Transformation (PLST) approach seeks to find the projection matrix $P$ and the
decoder $D$ for such an $K$-dimensional subspace through SVD. This method is
described below.

The label sets of the given examples are stacked together to form a matrix
$Y\in\mathbb{R}^{L\times N}$ such that each column of the matrix $Y$ is one of
the occupied vertices of the hypercube. The matrix $Y$ is then decomposed
using SVD such that

$Y=U\Sigma V^{T}\Rightarrow U^{T}Y=\Sigma V^{T}\text{ (since }UU^{T}=I).$ (1)

Here, $U\in\mathbb{R}^{L\times L}$ is a unitary matrix whose columns form a
basis for $Y$, $\Sigma\in\mathbb{R}^{L\times N}$ is a diagonal matrix
containing the singular values of $Y$ and $V\in\mathbb{R}^{N\times N}$ is also
a unitary matrix. Assume that the singular values are ordered
$\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{L}.$

The second line in (1) can be seen as a projection of $Y$ using the projection
matrix $U^{T}.$ If we consider the singular vectors in $U$ corresponding to
the $K$ largest singular values, we obtain a smaller projection matrix
$P=U_{K}^{T}=[u_{1}\>u_{2}\>\cdots\>u_{K}]^{T}$ that maps the vertices $y$ to
$\mathbb{R}^{K}.$ The projection matrix $P$ using the principle directions
guarantees the minimum encoding error from $\mathbb{R}^{L}$ to
$\mathbb{R}^{K}.$ Because $P=U_{K}^{T}$ is an orthogonal matrix, we have
$P^{-1}=P^{T}.$ Thus, $U_{K}$ can be used as a decoder $D$ to map any vector
$r\in\mathbb{R}^{K}$ to $U_{K}.r\in\mathbb{R}^{L}.$ Subsequently, a round
based decoding is done to get the label vector. To summarize, first PLST
performs SVD on $Y$ and obtain $U_{M}^{T}$, and then runs LLST with $P$ as
$U_{M}^{T}$. The decoder $D$ now becomes
$D(r(x))=\text{round}(U_{M}\cdot(x)).$

#####

PLST only considers labl-label correlations during the label space
dimensionality reduction (LDSR). In the paper nan Chen and tien Lin (2012), a
LSDR approach is explored which takes into account both the label and the
feature correlations. The claim is that, such a method will be able to find a
better embedding space due to the incorporation of extra information. The
paper also provides an upper bound of Hamming loss, thus providing theoretical
guarantees for both PLST and the proposed method, conditional principal label
space transformation (CPLST). The method uses the concept of both PLST and
Canonical Correlaion Analysis (CCA) to find the optimal embedding matrix.

Let $Z\in\mathbb{R}^{n\times L}$ such that $z=y-\bar{y},$ where
$\bar{y}=\frac{1}{n}\sum_{i=1}^{n}y_{i}$ is the estimated mean of the label
set vectors. Let $V\in\mathbb{R}^{k\times L}$ be a projection matrix,
$t=zP^{T},t\in\mathbb{R}^{k}$ is the embedded vector of $z$. Let $r$ be the
regressor to be learned such that $r(x)=t$, for a sample $x\in\mathbb{R}^{d}.$
Let the predictions be obtained as $h(x)=\text{round}(V^{T}r(x)+\bar{y})$ with
$V$ having orthogonal rows. In this setting, for round based decoding and
orthogonal linear transformation $V$, the Hamming loss is bounded by

$HL_{\text{train}}\leq
c\bigg{(}\underbrace{\|r(X)-ZP^{T}\|_{F}^{2}}_{\text{Prediction
error}}+\underbrace{\|Z-ZP^{T}P\|_{F}^{2}}_{\text{Encoding error}}\bigg{)}.$
(2)

Canonical Correlation Analysis (CCA) is a method generally used for feature
space dimensionality reduction (FSDR). In the context of this method, it can
be interpreted as feature aware Label Space Dimensionality Reduction (LSDR).
The CCA is utilized for analysis of linear relationship between two multi-
dimensional variables. It finds two sets of basis vectors
$(w_{x}^{(1)},w_{x}^{(2)},\cdots)$ and $(w_{z}^{(1)},w_{z}^{(2)},\cdots)$ such
that the correlation coefficient between the canonical variables
$c_{x}^{(i)}=Xw_{x}^{(i)}$ and $c_{z}^{(i)}=Zw_{z}^{(i)}$ is maximized, where
$w_{x}^{(i)}\in\mathbb{R}^{d},w_{z}^{(i)}\in\mathbb{R}^{L}$.

A different version of the algorithm, called Orthogonally Constrained CCA
(OCCA) preserves the original objective of CCA and specifies that $W_{Z}$ must
contain orthogonal rows to which round based decoding can be applied. Then,
using the hamming loss bound (2), when $P=W_{Z}$ and $r(X)=XW_{X}^{T},$ OCCA
minimizes $||r(X)-ZW_{Z}^{T}||$ in (2). That is, OCCA is applied for the
orthogonal directions $P$ that have low prediction error in terms of linear
regression.

After some simplification, the objective for OCCA becomes

$\begin{split}\underset{PP^{T}=I}{\min}||HZP^{T}-ZP^{T}||_{F}^{2}\approx\underset{PP^{T}=I}{\min}\text{tr}(PZ^{T}(I-H)ZP^{T}),\end{split}$
(3)

where $H=XX^{\dagger}$.

Thus, for minimizing the objective in (3) we only need the eigenvectors
corresponding to the smallest eigenvalues of $Z^{T}(I-H)Z$, or the
eigenvectors corresponding to the largest eigenvalues of $Z^{T}(H-I)Z$.

It can be seen that OCCA minimizes the prediction error in the Hamming Loss
bound (2) with the the orthogonal directions $V$ that are relatively simpler
to learn in terms of linear regression. In contrast, PLST minimizes the
encoding error of the bound (2) with the “principal” components. The two
algorithms OCCA and PLST can be combined to minimize the two error terms
simultaneously with the “conditional principal” directions. Then, the
optimization problem becomes

$\begin{split}\underset{W,\,PP^{T}=I}{\max}\text{tr}\bigg{(}PZ^{T}HZP^{T}\bigg{)}.\end{split}$
(4)

This problem can be solved by taking the eigenvectors with the largest
eigenvalue of $Z^{T}HZ$ as the rows of $P$. This $P$ minimizes the prediction
error as well as the encoding error simultaneously. This obtained P is useful
for the label space dimensionality reduction. The final CPLST algorithm is
described below.

Algorithm 2 Conditional Principal Label Space Transformation

1:Let $Z=[z_{1},\cdots,z_{N}]^{T}$ with $z_{n}=y_{n}-\bar{y}.$

2:Perform SVD of $Z^{T}HZ$ to obtain $Z^{T}HZ=A\Sigma B$ with
$\Sigma=\text{diag}(\sigma_{1},\ldots,\sigma_{N})$ such that
$\sigma_{1}\geq\cdots\geq\sigma_{N}.$ Let $P_{K}$ contain the top $K$ rows of
$B$.

3:Encode $\\{(x_{n},y_{n})\\}_{n=1}^{N}$ to $\\{(x_{n},t_{n})\\}_{n=1}^{N},$
where $t_{n}=P_{K}z_{n}.$

4:Learn a multi-dimensional regressor $r(x)$ from
$\\{(x_{n},t_{n})\\}_{n=1}^{N}.$

5:Predict the label-set of an instance $x$ by
$h(x)=\text{round}(P_{K}^{T}r(x)+\bar{y}).$

While CPLST provides a good bound on the error and shows theory behind the
matrix compression based methods, it does not perform very well and also takes
considerable time for prediction.

#####

The paper Cissé et al. (2013), takes a novel approach to multilabel
classification problem. The concept of Bloom filters Bloom (1970) is used to
reduce the problem to a small number of binary classifications by representing
label sets as low-dimensional binary vectors. However, since a simple bloom
filter based approach does not work very well, the approach designed in this
paper uses the observation that many labels almost never appear together in
combination with Bloom Filters to provide a robust method of multi-label
classification.

Bloom Filters are space efficient data structures which were originally
designed for approximate membership testing. Bloom Filter (BF) of size $B$
uses $K$ hash functions, where each one maps from number of labels $L$ to
$\\{1,\cdots,B\\}$, which are denoted as $h_{k}:L\rightarrow\\{1,\cdots,B\\}$
for $k\in\\{1,\cdots,K\\}$. The value of $h_{k}(\ell)$ is random and chosen
uniformly from $\\{1,\cdots,B\\}$. Each of the hash functions define a
representative bit of the entire bit vector of size $B$. The bit vector of a
label $\\{\ell\\}$ is obtained by concatenating all $h_{k}(\ell)$. There are
at most $K$ non-zero bits in this bit vector. A subset $y\subseteq L$ is
represented by a bit vector of size $B$, defined by the bitwise-OR of the bit
vectors of each of the labels in $y$. The Bloom Filter predicts if the label
is present in the set or not, by testing if the encoding of the set contains
$1$ at all the representative bits of the label’s encoding. If the label is
present, the answer is always correct, but if it is not present, there is a
chance of a false positive.

Bloom filters can be naively applied to extreme classification directly. Let
$L$ be the number of labels. Each individual label is encoded into a
$K$-sparse bit vector of dimension $B$ such that $B\ll\ell$, and a disjunctive
encoding of label sets (bit-wise-OR of the label codes that appear in the
label set) represents the encoding of the entire label set. For each of the
$B$ bits of the coding vector, one binary classifier is learned. Thus, the
number of classification tasks is reduced from $L$ to $B$. If $K>1$, the
individual labels can be encoded unambiguously on far less than $L$ bits.
Also, the classifiers can be trained in parallel independently. However,
standard BF is not robust to errors in the predicted representation. Each bit
in the BF is represents multiple labels of the label set. Thus, an incorrectly
prediction of a bit, may cause inclusion (or exclusion) of all the labels
which it represents from the label set.

This problem can be tackled by taking into consideration the fact that the
distribution of the label sets for real world datasets is not uniform. If it
is possible to detect a false positive from the existing distribution of
labels, then we can correct it. For example, if $y$ is the set of labels and
$\ell\notin y$ is a false positive given $\mathbb{e}(y),$ then $\ell$ can be
detected as a false positive if it is known that $\ell$ never appears together
with the labels in $y$. Thus, this method uses the non-uniform distribution of
label sets to design the hash functions and a decoding algorithm to make sure
that any incorrectly predicted bit has a limited impact on the predicted label
set.

This paper develops a new method called the Robust Bloom Filter (RBF) which
utilizes the fact that in most real-world datasets, many pairs of labels do
not occur together, or co-occur with a very small probability. This allows it
to improve over simple random hash functions. This is done in two ways,
clustering and error correction.

During label clustering, the label set $L$ is partitioned into $P$ subsets
$L_{1},\cdots,L_{P}$ such that clusters $(L_{1},\cdots,L_{P})$ are mutually
exclusive , i.e., no target set of a sample contains labels from more than one
of each of the clusters $L_{p},p=1,\cdots,P$. If the disjunctive encoding of
Bloom filters is used, and if the hash function are designed such that the
false positives for every label set can be detected to be mutually exclusive
of the other labels. The decoding step can then detect this and perform
correction on the bit. If for every bit, the labels in whose encodings it
appears is mutually exclusive, then we can ensure a smooth decoding procedure.
More clusters will result in smaller encoding vector size $B$, which will
result in fewer number of binary classification problems. Further, the
clustering is performed after removing head labels, as they co-occur too
frequently to divide into mutually exclusive subsets. For finding the label
clustering, the co-occurrence graph is built, and the head labels are removed
using the degree centrality measure (Degree Centrality is defined as the
number of edges incident on a vertex). The remaining labels are then clustered
using the Louvain Algorithm Blondel et al. (2008). The maximum size of each
cluster is fixed to control the number of clusters.

As the second step, assuming that the label set $L$ is partitioned into
mutually exclusive clusters (after removing the head labels), given a
parameter $K$, we can construct the required $K$-sparse encodings by following
two conditions: (1) two labels from the same cluster cannot share any
representative bit (2) two labels from different clusters can share at most
$K-1$ representative bits, ie. they cannot have the exact same encoding. Let
$K$ denote the number of hash functions, $R$ denote the size of the largest
cluster, $Q$ denote the number of bits assigned to each label such that
$B=R.Q$, $Q\geq K$ and $P\leq\binom{Q}{K}.$ For a given
$r\in\\{1,\cdots,R\\},$ which is the $r$-th batch of $Q$ successive bits, $Q$
bits are used for encoding the $r$-th label of each cluster. In this way, the
first condition is satisfied. Also, this encoding can be used for $P$ labels.
Now, for a given batch of $Q$ bits, there are $\binom{Q}{K}$ different subsets
of $K$ bits. Thus, we can have at most $\binom{Q}{K}$ label clusters. The $P$
labels (one from each cluster) are injectively (one-one) mapped to the subsets
of size $K$ to define the $K$ representative bits of these labels. Thus, these
encoding scheme satisfies condition 2 as no two subsets in $\binom{Q}{K}$
shares more than $K-1$ indexes. Using a BF of size $B=R.Q,$ we have $K$-sparse
label encodings that satisfy the two conditions for $L\leq R.\binom{Q}{K}$
labels partitioned into $P\leq\binom{Q}{K}$ mutually exclusive clusters of
size at most $R.$ In terms of compression ratio $\frac{B}{L},$ this encoding
scheme is most efficient when the clusters are perfectly balanced, and the
number of partitions $P$ is exactly equal to $\binom{Q}{K}$ for some $Q.$ An
implementation of this scheme is shown in Table 2 (for $Q=6$ bits, $P=15$
clusters, $K=2$ representative bits and $R=2$).

(a)  bit index |  representative for labels |  bit index |  representative for labels
---|---|---|---
$1$ |  $\\{1,2,3,4,5\\}$ |  $7$ |  $\\{16,17,18,19,20\\}$
$2$ |  $\\{1,6,7,8,9\\}$ |  $8$ |  $\\{16,21,22,23,24\\}$
$3$ |  $\\{2,6,10,11,12\\}$ |  $9$ |  $\\{17,21,25,26,27\\}$
$4$ |  $\\{3,7,10,13,15\\}$ |  $10$ |  $\\{18,22,25,28,29\\}$
$5$ |  $\\{4,8,11,13,15\\}$ |  $11$ |  $\\{19,23,26,28,30\\}$
$6$ |  $\\{5,9,12,14,15\\}$ |  $12$ |  $\\{20,24,27,29,30\\}$

(b)  cluster index |  labels in cluster |  cluster index |  labels in cluster
---|---|---|---
$1$ |  $\\{1,15\\}$ |  $9$ |  $\\{9,23\\}$
$2$ |  $\\{2,16\\}$ |  $10$ |  $\\{10,24\\}$
$3$ |  $\\{3,17\\}$ |  $11$ |  $\\{11,25\\}$
$4$ |  $\\{4,18\\}$ |  $12$ |  $\\{12,26\\}$
$5$ |  $\\{5,19\\}$ |  $13$ |  $\\{13,27\\}$
$6$ |  $\\{6,20\\}$ |  $14$ |  $\\{14,28\\}$
$7$ |  $\\{7,21\\}$ |  $15$ |  $\\{15,29\\}$
$8$ |  $\\{8,22\\}$ |  |

Table 2: Representative bits for 30 labels partitioned into $P=15$ mutually
exclusive label clustersof size $R=2$, using $K=2$ representative bits per
label and batches of $Q=6$ bits. The table on the right gives the label
clustering. The injective mapping between labels and subsets of bits is
defined by
$g:\ell\rightarrow\\{g_{1}(\ell)=(1+\ell)/6,g_{2}(\ell)=1+\ell\text{mod}6\\}$
for $\ell\in\\{1,...,15\\}$ and, for $\ell\in\\{15,...,30\\},$ it is defined
by $\ell\rightarrow\\{(6+g_{1}(\ell-15),6+g_{1}(\ell-15)\\}$

During the prediction procedure, given an sample $x$ and the encoding
predicted $\mathrm{\hat{e}(x)}$, the predicted label set
$d(\mathrm{\hat{e}(x)})$ is computed by a two-step process. Firtsly, cluster
identification is performed by picking whichever cluster has maximum number of
representative bits, and close to the number of representative bits close to
that of $\mathrm{\hat{e}(x)}$. Secondly, the correctl labels within the
cluster are found by using probabilistic sampling under the assumption that
whichever label in the cluster has the most representative bits in common with
$\mathrm{\hat{e}(x)}$ is the most likely to occur. If logistic regression is
used as base learners for binary classification, the posterior probabililty
can be used for computing the cluster scores instead of the binary decisions.
The cluster which maximizes the cluster score is chosen. The advantage of
using a randomized prediction for the labels is that a single incorrectly
predicted bit does not result in too many predicted labels.

The paper also provides some theoretical bounds on the error by deriving that
each incorrectly predicted bit in the BF cannot imply more than two
incorrectly predicted labels. However, R-BF still does not show very good
results, probably due to the assumption that labels from different clusters
will never co-occur, which highly limits the output space.

#####

The paper Jasinska and Karampatziakis (2016) also takes a similar approach to
encoding the labels. A method called Log Time Log Space Extreme classification
(LTLS) is proposed which transforms the multi-label problem with $L$ labels
into a structured prediction problem by encoding the labels as edges of a
trellis graph. This enables inference and training in order which is
logarithmic in the number of labels along with reduced model size.

First, a trellis graph with $O(\log_{2}(L))$ steps is built, each with $2$
states, a root, and a sink vertex as shown in the figure 4. There are $E$
edges in the graph. A path from the root to the sink $s$ is a vector of length
$E$. There are $L$ paths in the graph. Each label $l$, $l\in\\{1,\dots,L\\}$,
is assigned to path $s_{l}$. Additional edges are used if the number of labels
is not power of $2$. This step is equivalent to binary encoding of number of
labels. The number of edges $E\leq\log_{2}(L)+1$. Each edge in the above
trellis corresponds to a function $f$ we learn. For a label $l$, the encoding
vector has $1$ at places where the edge is part of the corresponding path
$s_{l}$, or has $0$ otherwise.

Figure 4: Vertex $0$ is the source and vertex $7$ is the sink. Every path from
source to the sink represents a label.

During prediction, given an input $x$, the algorithm predicts $E$ values from
each of the binary classifiers. The value at each edge $e_{i}$ is a function
$f_{i}:\mathcal{X}\rightarrow\mathbb{R}$ which can be assumed to be a simple
linear regressor. The score $F(x,s_{l})$ of label $l$ is the sum of values in
the path $s_{l}$.

$\displaystyle F(x,s_{l})=\sum_{i\in s_{l}}f_{i}(x).$ (5)

For prediction of the final labels from the label scores, we can use the
scheme where top-k labels correspond to $k$ longest paths in the trellis graph
(which can be found using DP based list Viterbi algorithm Seshadri and
Sundberg (1994)).

Despite the unique approach, the algorithm failed to give very high scores
compared to emerging tree based and linear algebra based methods. Subsequent
work was done by Evron et al. (2018) which attempted different graph
structures, but it was only applicable for multi-class classification.

#####

Although Cissé et al. (2013) uses hashing based label space compression
technique, it makes assumptions about the co-occurrence of label which leads
to reduction in performance. The paper Medini et al. (2019), proposes Merged
Averaged Classifiers via Hashing (MACH) which is a hashing based approach to
XML which utilizes something similar to a count sketch data structure instead
of bloom filters for performing universal hashing. This reduces the task of
extreme multi-label classification to a small number of parallelizable binary
classification tasks.

Sketch Charikar et al. (2002) is a data structure that stores a summary of a
dataset in situations where the whole data would be prohibitively costly to
store. The count-sketch is a specific type of sketch which is used for
counting the number of times an element has occurred in the data stream. Let
$S=q_{1},q_{2},\cdots,q_{n}$ be a stream of queries, where each
$q_{i}\in\mathcal{O}$ which is the set of objects queried. Let
$h_{1},\cdots,h_{t}$ be $t$ hash functions from $\mathcal{O}$ to
$\\{1,\cdots,b\\}$. Count sketch data structure consists of these hash
functions along with a $t\times b$ array of counters $C$, where $t$ is the
number of hash functions and $b$ is the number of buckets for each hash table.
There are two supported operations: (1) Insert new element $q$ into sketch
$C$, which is performed by adding $1$ for each hash function $t$ at position
$C[t][h_{t}(q)]$ (2) Count the number of times element $q$ has occurred,
performed by $F_{t=1...T}(C[t][h_{t}(q)])$ where $F$ can be mean, median or
minimum.

If we use only one hash function, then we get the desired count value in
expectation but the variance of the estimates is high. To reduce the variance,
$t$ hash functions are used and their outputs are combined. This concept is
utilized by the proposed method.

The method Merged-Averaged Classifiers via Hashing (MACH) randomly merges $L$
classes into $B$ random-meta-classes or buckets $(B\ll L)$ using randomized
hash functions. This merging of labels into meta classes gives rise to a
smaller multi-label classification problem and classifiers such as logistic
regression or a deep network is used for this meta-class classification
problem. Let $R$ be the number of hash functions. Then, the classification
algorithm is repeated independently for $R=O(\text{log }L)$ times using an
independent 2-universal hashing scheme each time. During prediction, the
outputs of each of the $R$ classifiers is aggregated to obtain the prediction
class (The aggregation scheme may be median, mean or min). This is the step
where an estimate like method of the count sketch data structure is used. The
advantage of MACH stems from the fact that since each hash function $h_{j}$ is
independent, training the $R$ classifiers are trivially parallelizable. The
parameters $B$ and $R$ can be tuned to trade accuracy with both computation
and memory. The algorithms are described below.

Algorithm 3 Train

1:Data :  $X\in\mathbb{R}^{N\times d},Y\in\mathbb{R}^{N\times L}$

2:No. of buckets, $B$, no of hash functions, $R$

3:Output :  $R$ trained classifiers

4:initialize $R$ 2-universal hash functions $h_{1},h_{2},\cdots,h_{R}$

5:initialize result as an empty list

6:for $i=1:R$ do

7: $Y_{h_{i}}\leftarrow h_{i}(Y)$

8: $M_{i}={\tt trainClassifier}(X,Y_{h_{i}})$

9: Append $M_{i}$ to result

10:end for

11:Return  result

Algorithm 4 Predict

1:Data :  $X\in\mathbb{R}^{N\times d},Y\in\mathbb{R}^{N\times L}$

2:Input : $M=M_{1},M_{2},\cdots,M_{R}$

3:Output : $N$ predicted labels

4:load $R$ 2-universal hash functions $h_{1},h_{2},\cdots,h_{R}$ used in
training

5:initialize $P$ as an empty list

6:initialize $G$ as a $(|N|*L)$ matrix

7:for $i=1:R$ do

8: $P_{i}=\text{getProbability}(X,M_{i})$

9: Append $P_{i}$ to $P$

10:end for

11:for $j=1:\ell$ do

12: /*$G[:,j]$ indicates the $j^{th}$ column in matrix $G$*/

13: $G[:,j]=(\sum_{r=1}^{R}P_{r}[:,h_{r}(j)])/R$

14:end for

15:Return argmax$(G,axis=1)$ //whichever label has the highest probability for
a given sample

The paper is able to prove a bound on the error due to the theorem that if a
pair of classes is not indistinguishable, then there is at least one
classifier which provides discriminating information between them. If the loss
function used is softmax, then we get the multiclass version of MACH. For a
multilabel setting, the loss function can be binary cross-entropy.

##### Comparison between above stated methods

  1. 1.

Compressed Sensing Hsu et al. (2009), even though it provides theoretical
bounds, does not perform very well in the results and prediction times. It is
consistently outperformed by PLST Tai and Lin (2012).

  2. 2.

CPLST nan Chen and tien Lin (2012) outperforms PLST but is much slower and
less scalable.

  3. 3.

R-BF Cissé et al. (2013) and LTLS Jasinska and Karampatziakis (2016)
outperform the results of CPLST but are outperformed by Medini et al. (2019).

Compressed Sensing Based Methods
---
Algorithm |  Compression |  Learning |  Reconstruction
CS |  Compression Matrix obtained from compression methods such as OMP |  Simple regressors in the reduced space |  Solving an optimization problem
PLST |  Compression matrix obtained from SVD |  Simple regressors in the reduced space |  Round based decoding after multiplying with transpose of compression matrix
CPLST |  Compression matrix obtained from a combination of OCCA and PLST, considering both feature-label and label-label correlations |  Simple regressors in the reduced space |  Round based decoding after multiplying with transpose of compression matrix
R-BF |  Ecodes every subset of labels into a bit encoding by ’OR’ operation on individual labels |  Binary Classifiers for each bit in encoding |  An algorithm based on identification of the closest labels included within the predicted encoding
LTLS |  Each label is assigned to a path in a trellis graph and a corresponding bit vector is obtained |  Regressors at each edge predict the weight of the edges |  Longest path algorithms are used to find the top k paths and corresponding labels are predicted
MACH |  Universal hash functions are used to assign each label a bucket. Multiple hash functions are used to iterate the process. |  Multi label classifiers are used to predict the corresponding meta labels for each hash function |  A sketch-like aggregation function is used to find the predicted labels from the predicted meta-labels

###  4.2 Linear Algebra

The methods in this category do not follow any specific structure, but are
heavily reliant on simple Linear Algebra based optimizations, which allow the
methods to gain an advantage over simply embedding in a lower dimensional
space like in compressed sensing based methods. The methods may end up working
like compressed sensing ones, but generally aim to do some improvement over
them. For example, LEML converts the entire process of compression, prediction
and decoding in CPLST to one step directly and proves the equivalence. SLEEC
on the other hand refutes the usage of the low-rank assumption used in most of
the embedding methods and develops a KNN based distance preserving embeddings.
PD-SPARSE develops a method for optimizing the XML problem in both primal and
dual spaces and obtain sparse embeddings. A summary of each method is provided
at the end of the section.

#####

Subset-selection is one of the most common methods utilized to make the
extreme classification problem tractable. The core idea was to find a good
representative subset of labels on which a simple classifier can be learnt and
the predictions can be scaled back to the full label set. The paper Bi and
Kwok (2013) performs a subset selection on the labels to form a smaller label
space which approximately spans the original label space. The labels are
selected via a randomized sampling procedure where the probability of a label
being selected is proportional to the leverage score of the label on the best
possible subset space.

Balasubramanian and Lebanon (2012) has previously attempted the label
selection procedure. This paper assumes that the output labels can be
predicted by the selected set of labels. It solves an optimization problem for
selecting the subset. However, the size of the label subset cannot be
controlled explicitly and also the optimization problem quickly becomes
intractable. To address this issue, this paper models the label subset
selection problem as a Column Subset Selection Problem (CSSP).

The method Column Subset Selection Problem (CSSP) seeks to find exactly $k$
columns of $Y$ such that these columns span $Y$ as well as possible, given a
matrix $Y\in\mathbb{R}^{n\times L}$ and an integer $k$. For this purpose, an
index set $C$ of cardinality $k$ is required such that
$||Y-Y_{C}Y_{C}^{\dagger}Y||_{F}$ is minimized. Here, $Y_{C}$ denotes the sub-
matrix of $Y$ containing the columns indexed by $C$ and $Y_{C}Y_{C}^{\dagger}$
is the projection matrix on the $k$-dimensional space spanned by the columns
of $Y_{C}.$ In Boutsidis et al. (2009), this problem is solved in two stages :
a randomized stage and a deterministic stage. Let $V_{k}^{T}$ denote the
transpose of the matrix formed by the top $k$ right singular vectors of $Y.$
In the randomized stage, a randomized column selection algorithm is used to
select $\theta(k\log k)$ columns from $Y.$ Each column $i$ of $V_{k}^{T}$ is
assigned a probability $p_{i}$ which corresponds to the leverage score of the
$i^{th}$ column of $Y$ on the best rank $k$ subspace of $Y.$ It is defined as
$p_{i}=\frac{1}{k}||(V_{k}^{T})_{i}||_{2}^{2}.$ The randomized stage of the
algorithm samples from the columns of $Y$ using this probability distribution.
In the deterministic stage, a rank revealing QR (RRQR) decomposition is
performed to select exactly $k$ columns from a scaled version of the columns
sampled from $Y.$

In the extreme classification setting, the objective of the label subset
selection problem can be stated as

$\underset{C}{\min}\,||Y-Y_{C}Y_{C}^{\dagger}Y||_{F}.$ (6)

The approach proposed in this paper directly selects the $k$ columns of the
label matrix $Y.$ The algorithm is given in Algorithm 5. First, a partial SVD
of $Y$ is computed to pick the top $k$ right singular vectors,
$V_{k}\in\mathbb{R}^{n\times k}.$ Then, the columns in $Y$ are sampled with
replacement, with the probability of selecting the $i^{th}$ column being
$p_{i}=\frac{1}{k}||(V_{k})^{T}_{i}||_{2}^{2}.$ However, instead of selecting
$\Theta(k\log k)$ columns, the sampling procedure is continued until $k$
different columns are selected. It has been shown that if the number of trials
is $T=\frac{2c_{0}^{2}k}{\epsilon^{2}}\log\frac{c_{0}^{2}k}{\epsilon^{2}}$
(which is in $O(k\log k)$) for some constants $c_{0}$ and $\epsilon,$ then the
algorithm gives a full rank matrix $(V_{k})^{T}_{C}$ with high probability.
Once the $k$ columns have been obtained, $k$ classifiers are learned.

Algorithm 5 Multi-label classification via CSSP (ML-CSSP)

Compute $V_{k},$ the top $k$ right singular vectors of $Y.$

Compute the sampling probability $p_{i}$ for each column in $Y$ as defined
above.

$C\leftarrow\Phi$

while  $|C|<k$ do

Select an integer from $\\{1,2,\ldots,L\\}$ where the probability of selecting
$i$ is equal to $p_{i}.$

if  $i\notin C$ then

$C\leftarrow C\cup\\{i\\}$

end if

end while

Train the classifier $f(x)$ from $\\{x^{i},y_{C}^{i}\\}_{i=1}^{n}.$

Given a new test point $x,$ obtain its prediction $h$ using $f(x)$ and return
$\hat{y}$ by rounding $h^{T}Y_{C}^{\dagger}Y$

The minimizer of the objective (6) satisfies

$Y\approx Y_{C}Y_{C}^{\dagger}Y.$ (7)

From (7), it can be seen that each row of $Y$ can be approximated as the
product of each row of $Y_{C}$ with $Y_{C}^{\dagger}Y.$ Now, given a test
sample $x\in\mathbb{R}^{d},$ let $h\in k$ denote the prediction vector. Then,
using (7), the $L$-dimensional prediction vector can be obtained as
$h^{T}Y_{C}^{\dagger}Y.$ The elements of the $L$-dimensional output vector are
further rounded to get a binary output vector.

Empirical results show that ML-CSSP gives lower RMSE compared to other methods
available at that time. The given CSSP algorithm is also compared to the two-
stage algorithm of Boutsidis et al. (2009) and the results show that the
number of sampling trials and encoding error is better for the proposed
algorithm. As the number of selected labels $k$ is increased, training error
increases as the number of learning problems increase while the encoding
errors decrease as $k$ is increased, as expected. ML-CSSP is able to achieve
lower training errors than PLST Tai and Lin (2012) and CPLST nan Chen and tien
Lin (2012) as selected labels are easier to learn than transformed labels.

#####

In the paper Yu et al. (2013), the problem of extreme classification with
missing labels (labels which are present but not annotated) is addressed by
formulating the original problem as a generic empirical risk minimization
(ERM) framework. It is shown that the CPLST nan Chen and tien Lin (2012), like
compression based methods, can be derived as a special case of the ERM
framework described in this paper.

The predictions for the label vector are parameterized as
$f(\mathrm{x};Z)=Z^{T}\mathrm{x},$ where $Z\in\mathbb{R}^{d\times L}$ is a
linear model. Let $\ell(\mathrm{y},f(\mathrm{x};Z))\in\mathbb{R}$ be the loss
function. The loss function is assumed to be decomposable, i.e.,

$\ell(\mathrm{y},f(\mathrm{x};Z))=\sum_{j=1}^{L}\ell(y^{j},f^{j}(\mathrm{x};Z)).$

The motivation for the framework used in this paper comes from the fact that
even though the number of labels is large, there exists significant label
correlations. This reduces the effective number of parameters required to
model them to much less than $d\times\ell,$ which in turn constrains $Z$ to be
a low rank matrix.

For a given loss function $\ell(\cdot)$ and no missing labels, the parameter
$Z$ can be learnt by the canonical ERM method as

$\begin{split}\hat{Z}&=\underset{Z\,:\,\text{rank}(Z)\leq
k}{\text{argmin}}J(Z)=\sum_{i=1}^{n}\sum_{j=1}^{L}\ell(Y_{ij},f^{j}(x_{i};Z))+\lambda
r(Z),\\\ \end{split}$ (8)

where $r(Z):\mathbb{R}^{d\times L}\rightarrow\mathbb{R}$ is a regularizer. If
there are missing labels, the loss is computed over the known labels as

$\begin{split}\hat{Z}&=\underset{Z\,:\,\text{rank}(Z)\leq
k}{\text{argmin}}J(Z)=\underset{(i,j)\in\Omega}{\sum}\ell(Y_{ij},f^{j}(x_{i};Z))+\lambda
r(Z),\\\ \end{split}$ (9)

where $\Omega\subseteq[n]\times[L]$ is the index set that represents known
labels. Due to the non-convex rank constraint, this (9) becomes an NP-hard
problem. However, for convex loss functions, the standard alternating
minimization method can be used. For L2-loss, eq. (8) has a closed form
solution using SVD. This gives the closed form solution for CPLST.

#####

Most of the compressed sensing based methods and previous embedding based
methods assume that the label matrix is low rank and aims to hence predict in
a smaller dimensional embedding space rather than the original embedding
space. The paper Bhatia et al. (2015) claims that the low-rank assumption is
violated in most practical XML problems due to the presence of the tail labels
which act as outliers and are not spanned by the smaller embedding space.
Thus, this paper proposes a method called Sparse Local Embeddings for Extreme
Multi-label Classification (SLEEC) which utilizes the concept of ”distance
preserving embeddings” to predict both head and tail labels effectively.

The global low rank approximations performed by embedding based methods do not
take into account the presence of tail labels. It can be seen that a large
number of labels occur in a small number of documents. Hence, these labels
will not be captured in a global low dimensional projection.

In SLEEC embeddings $z_{i}$ are learnt which non-linearly capture label
correlations by preserving the pairwise distances between only the closest
label vectors, i.e. $d(z_{i},z_{j})=d(y_{i},y_{j})$ only if
$i\in\text{kNN}(j),$ where $d$ is a distance metric. Thus, if one of the label
vectors has a tail label, it will not be removed by approximation (which is
the case for low rank approximation). Regressors $V$ are trained to predict
$z_{i}=Vx_{i}.$ During prediction SLEEC uses kNN classifier in the embedding
space, as the nearest neighbours have been preserved during training. Thus,
for a new point $x$, the predicted label vector is obtained using
$y=\sum_{i:Vx_{i}\in\text{kNN}(Vx)}y_{i}.$ For speedup, SLEEC clusters the
training data into $C$ clusters, learns a separate embedding per cluster and
performs kNN only within the test point’s cluster. Since, clustering can be
unstable in large dimensions, SLEEC learns a small ensemble where each
individual learner is generated by a different random clustering.

Due to the presence of tail labels, the label matrix $Y$ cannot be well
approximated using a low-dimensional linear subspace. Thus it is modeled using
a low-dimensional non-linear manifold. That is, instead of preserving
distances of a given label vector to all the training points, SLEEC attempts
to preserve the distance to only a few nearest neighbors. That is, it finds a
$\hat{L}-$dimensional matrix
$Z=[z_{1},z_{2},\ldots,z_{n}]\in\mathbb{R}^{\hat{L}\times n}$ which minimizes
the following objective:

$\underset{Z\in\mathbb{R}^{\hat{L}\times
n}}{\min}||P_{\Omega}(Y^{T}Y)-P_{\Omega}(Z^{T}Z)||_{F}^{2},$ (10)

where the index set $\Omega$ denotes the set of neighbors that we wish to
preserve, i.e., $(i,j)\in\Omega$ iff $j\in N_{i}.$ $N_{i}$ denotes the set of
nearest neighbors of $i$. $P_{\Omega}:\mathbb{R}^{n\times
n}\rightarrow\mathbb{R}^{n\times n}$ is defined as :

$(P_{\Omega}(Y^{T}Y))_{ij}=\begin{cases}\langle y_{i},y_{j}\rangle,&\text{if
}(i,j)\in\Omega\\\ 0,&\text{otherwise}.\end{cases}$ (11)

The above equation, after simplification can be solved by using Singular Value
Projection (SVP) Jain et al. (2010) using the ADMM Sprechmann et al. (2013)
optimization method. The training algorithm is shown in Algorithm 6.

Algorithm 6 SLEEC: Training

Require :  $\mathcal{D}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\},$ embedding
dimensionality $\hat{L},$ number of neighbors $\bar{n},$ number of clusters
$C,$ regularization parameter $\lambda,\mu$, L1 smoothing parameter $\rho$

Partition $X$ into $Q^{1},\ldots,Q^{C}$ using $k$-means

for each partition $Q^{j}$

Form $\Omega$ using $\bar{n}$ nearest neighbors of each label vector $y_{i}\in
Q^{j}$

$[U\quad\Sigma]\leftarrow\text{SVP}(P_{\Omega}(Y^{jY^{j^{T}}}),\hat{L})$

$Z^{j}\leftarrow U\Sigma^{\frac{1}{2}}$

$V^{j}\leftarrow ADMM(X^{j},Z^{j},\lambda,\mu,\rho)$

$Z^{j}=V^{j}X^{j}$

end for

return $\\{(Q^{1},V^{1},Z^{1}),\ldots,(Q^{C},V^{C},Z^{C})\\}$

#####

The paper Mineiro and Karampatziakis (2014) proposes a method called
REMBRANDT, which utilizes a correspondence between rank constrained estimation
and low dimensional label embeddings to develop a fast label embedding
algorithm.

The assumption made by the paper is that with infinite data, the matrix being
decomposed is the expected outer product of the conditional label
probabilities. In particular, this indicates that two labels are similar when
their conditional probabilities are linearly dependent across the dataset.

The label embedding problem is modeled as a rank constrained estimation
problem, as described below. Given a data matrix $X$ and a label matrix $Y$,
let the weight matrix to be learned have a low-rank constraint. In matrix form

$W^{*}=\underset{\text{rank}(W)\leq k}{\text{argmin}}||Y-XW||^{2}_{F}.$ (12)

The solution to (12) is derived in Friedland and Torokhti (2006). The equation
is further simplified to obtain a low rank matrix approximation problem, which
is solved using a randomized algorithm proposed in Halko et al. (2011).

After the predictions are done in the embedding space, a decoding matrix is
used to project the predicted label matrix back to the $\mathbb{R}^{d\times
L}$ space.

#####

Yen et al. (2016) shows that for the extreme classification problem, a margin-
maximizing loss with $l_{1}$ penalty, yields a very sparse solution both in
primal and in dual space without affecting the predictor’s expressive power.
The proposed algorithm, PD-Sparse incorporates a Fully Corrective Block
Coordinate Frank Wolfe (FC-BCFW) Lacoste-Julien and Jaggi (2015) algorithm
that utilizes this sparsity to achieve a complexity sublinear to the number of
primal and dual variables. The main contribution of this method to the field
is the use of the separation ranking loss in XML which was further used in
several subsequent methods.

Instead of making structural assumption on the relation between labels, for
each instance, there are only a small number of correct labels and the feature
space can be used to distinguish between labels. Under this assumption, a
simple margin-maximizing loss can be shown to yield sparse dual solution in
the setting of extreme classification. When this loss is combined with $l_{1}$
penalty, it gives a sparse solution both in the primal as well as dual for any
$l_{1}$ parameter $\lambda$.

Let $P(y)=\\{l\in[L]|y_{l}=1\\}$ denote positive label indexes and
$N(y)=\\{l\in[L]|y_{l}=0\\}$ denote negative label indexes. In this paper, it
is assumed that $nnz(y)$ is small and does not grow linearly with $L$.

The objective of separation ranking loss is to compute the distance between
the output and the target. The loss penalizes the prediction on an input $x$
by the highest response $(z)$ from the set of negative labels minus the lowest
response from the set of positive labels.

$L(z,y)=\underset{k_{n}\in N(y),\,k_{p}\in
N(p)}{\max}(1+z_{k_{n}}-z_{k_{p}})_{+},$ (13)

where an instance has zero loss if all positive labels $k_{p}\in P_{i}$ have
higher positive responses that that of negative labels $k_{n}\in N_{i}$ plus a
margin. Here $(\,\cdot\,)_{+}=\max(0,.)$.

Figure 5: Support Labels in the context of an SVM.

In a binary classification scenario, the support labels are defined as

$(k_{n},k_{p})\in\underset{k_{n}\in N(y),\,k_{p}\in
P(y)}{\text{argmax}}(1+z_{k_{n}}-z_{k_{p}})_{+}.$ (14)

Here, the labels that maximize the loss in (13) form the set of support
labels. The basic inspiration for use of loss (13) is that for any given
instance, there are only a few labels with high responses and thus, the
prediction accuracy can be boosted by learning how to distinguish between
these labels. In the extreme classification setting, where $L$ is very high,
only a few of them are supposed to give high response. These labels are taken
as the support labels.

The problem now becomes to find a solution to the problem

$W^{*}=\underset{W}{\text{argmin}}\sum_{i=1}^{N}L(w^{T}x_{i},y_{i})+\lambda\sum_{k=1}^{K}||W_{k}||_{1}.$
(15)

It can be shown that the solutions in both the primal and dual space is sparse
in nature. Thus, sparsity assumptions on $W^{*}$ are not hindrances but
actually a property of the solution. The above formalized problem is solved by
separating blocks of variables and constraints to use the Block Coordinate
Frank Wolfe Algorithm Lacoste-Julien et al. (2013). The only bottleneck in the
entire process comes down to how to find the most violating label in each
step, for which an importance sampling based heuristic method is used.

#####

In this paper Xu et al. (2016), the idea of using low-rank structure for label
correlations is re-visited keeping in mind the tail labels. The claim made in
Bhatia et al. (2015) which says that low-rank decompositions are not
applicable in extreme classification is studied and a claim is made which says
that low-rank decomposition is applicable after removal of tail labels from
the data. Hence, in addition to low-rank decomposition of label matrix, the
authors add an additional sparse component to handle tail labels behaving as
outliers.

Assuming the label matrix as $Y\in\\{-1,+1\\}^{n\times L},$ it is decomposed
as

$Y=\hat{Y}_{L}+\hat{Y}_{S},$

where $\hat{Y}_{L}$ is low rank and depict label correlations and
$\hat{Y}_{S}$ is sparse, and captures the influence of tail labels. This can
be modeled as

$\begin{split}\underset{\underset{\underset{\text{card}(\hat{Y}_{S})\leq
s}{\text{rank}(\hat{Y}_{L})\leq
k,}}{\hat{Y}_{L},\hat{Y}_{S},}}{\min}\quad&||Y-\hat{Y}_{L}-\hat{Y}_{S}||^{2}_{F}.\\\
\end{split}$ (16)

Given $\hat{Y}_{L}$ and $\hat{Y}_{S}$, we wish to learn regression models such
that $\hat{Y}_{L}\equiv WX$ and $\hat{Y}_{S}\equiv HX,$ where
$W,H\in\mathbb{R}^{d\times L}$. Let $W=UV$ where $U\in\mathbb{R}^{d\times
k},V\in\mathbb{R}^{k\times L}.$ We impose the constraints by

$\begin{split}\underset{U,V,H}{\min}\quad||Y-XUV-
XH||_{F}^{2}+\lambda_{1}||H||_{F}^{2}+\lambda_{2}(||U||_{F}^{2}+||V||_{F}^{2})+\lambda_{3}||XH||_{1},\quad\lambda_{1},\lambda_{2},\lambda_{3}>0.\end{split}$
(17)

The objective (17) can be divided into three subproblems :

$\displaystyle V=\underset{V}{\text{argmin}}\>||Y-XUV-
XH||_{F}^{2}+\lambda_{2}||V||_{F}^{2}.$ (18) $\displaystyle
U=\underset{U}{\text{argmin}}\>||Y-XUV-XH||_{F}^{2}+\lambda_{2}||U||_{F}^{2}.$
(19) $\displaystyle H=\underset{H}{\text{argmin}}\>||Y-XUV-
XH||_{F}^{2}+\lambda_{1}||H||_{F}^{2}+\lambda_{3}||XH||_{1}.$ (20)

Each of these sub problems can be solved by equating the partial
differentiation to zero.

The sub problems (18),(19) and (20) can be efficiently solved in parallel and
their solutions can be combined to achieve the final solution. This is a
divide and conquer strategy.

For the divide step, given the label matrix $Y\in\mathbb{R}^{n\times L},$ it
is randomly partitioned into $t$ number of $m$-column sub matrices
$\\{(Y)_{i}\\}_{i=1}^{t},$ where we suppose $L=tm$ and each
$(Y_{i})\in\\{-1,1\\}^{n\times m}.$ Thus, the original problem is divided into
$t$ sub-problems regarding $\\{(Y)_{1},\cdots,(Y)_{t}\\}.$ The basic
optimization methods discussed in the previous section can now be adopted to
solve these sub-problems in parallel, which outputs the solutions as
$\\{((\hat{W})_{1},(\hat{H})_{1}),\cdots,((\hat{W})_{t},(\hat{H})_{t})\\}.$

The conquer step exploits column projection to integrate the solutions of sub-
problem solutions. The final approximation $W$ to problem (17) can be obtained
by projecting $[(\hat{W}_{1}),\cdots,(\hat{W}_{t})]$ onto the column space of
$(\hat{W}_{1}).$ After obtaining $\hat{W},$ the objective can be optimized
over each column of $\hat{H}$ in parallel to obtain the sparse component of
the resulting multi-label predictor.

Algorithm 7 REML

1:Input: $X,Y,t\geq 1$

2:for $i=1,\cdots,t$ do in parallel

3: Sample $(Y)_{i}\subseteq Y$

4: repeat

5: Solve $(\hat{V})_{i}$ from problem (18)

6: Solve $(\hat{U})_{i}$ from problem (19)

7: Solve $(\hat{H})_{i}$ from problem (20)

8: until Convergence

9: $(\hat{W})_{i}=(\hat{U})_{i}(\hat{V})_{i}$

10:end

11:ColumnProjection $([(\hat{W})_{1},\cdots,(\hat{W})_{t}],(\hat{W})_{1})$

#####

In Tagami (2017), the author highlights some major problems that the SLEEC
Bhatia et al. (2015) algorithm has. SLEEC uses only feature vectors for
$k$-means clustering. It does not access label information during clustering.
Thus data points having the same label vectors are not guaranteed to be
assigned to the same partition. As the number of partitions increase, the data
points having the same tail labels may be assigned to different partitions.
Further, in the prediction step, SLEEC predicts labels of the test point by
using the nearest training points in the embedding space. Hence, the order of
distance to the neighbors of the test point is considered, and not the values
themselves. This may cause an isolated point which may be far from a cluster
center to belong to that cluster.

The proposed method, AnnexML is able to solve these issues by learning a
multi-class classifier, which partitions the approximate $k$-Nearest Neighbor
Graph (KNNG) Dong et al. (2011) of the label vectors in order to preserve the
graph structure as much as possible. AnnexML also projects each divided sub-
graph into an individual embedding space by formulating this problem as a
ranking problem instead of a regression one. Thus the embedding matrix $V_{c}$
is not a regressor like in SLEEC.

There are mainly three steps to the training of the AnnexML algorithm.
Firstly, AnnexML learns to group the data points that have similar label
vectors to the same partition, which is done by utilizing the label
information. It forms a $k$-nearest neighbor graph (KNNG) of the label
vectors, and divides the graph into $K$ sub-graphs, while keeping the
structure as much as possible. After the KNNG has been computed and
partitioned, we learn the weight vector $w_{c}$ for each partition $c$ such
that the data points having the same tail labels are allocated in the same
partition while the data points are divided almost equally among partitions.
Thirdly, the learning objective of AnnexML is to reconstruct the KNNG of label
vectors in the embedding space. For this task, it employs a pairwise learning-
to-rank approach. That is, arranging the $k$ nearest neighbors of the $i$-th
sample is regarded as a ranking problem with the $i$-th point as the query and
other points as the items. The approach used is similar to DSSM Yih et al.
(2011).

The prediction of AnnexML mostly relies on the $k$-nearest neighbor search in
the embedding space. Thus, for faster prediction, we need to speed up this NN
search. An approximate $k$-nearest neighbor search method is applied, which
explores the learned KNNG in the embedding space by using an additional tree
structure and a pruning technique via the triangle inequality. This technique
gives AnnexML a much faster prediction than SLEEC.

#####

In the paper Jalan and Kar (2019), a new method for reducing the
dimensionality of the feature vectors is explored which is especially useful
when the feature vector is already sparse. This is not a specific XML method
but a add-on method for any XML algorithm which can be used to provide
speedups when the number of features is very high with minimal loss of
accuracy.

The reduction in dimensionality is performed by a method called feature
agglomeration, where clusters of features are created and then a sum is taken
to create new features. If $F$ is partition of the features $[d]$, then
corresponding to every cluster $F_{K}\in F$ we create a single feature by
summing up the features within cluster $F_{k}$. Thus, for a given vector
$z\in\mathbb{R}^{d},$ we create an agglomerated vector
$\tilde{z}\in\mathbb{R}^{K}$ with just $K$ features using the clustering $F$.
The $k-$th dimension of $\tilde{z}$ will be $\tilde{z}_{k}=\Sigma_{j\in
F_{k}}z_{j}$ for $k=1\ldots K.$

Figure 6:  An illustration of the feature agglomeration process.

The proposed method, DEFRAG, clusters the features into balanced clusters of
size not more than $d_{0}$. If this results in $K$ clusters, then we sum up
the features in these clusters to obtain $K$-dimensional features which are
subsequently used for training and testing using any XML method. It can be
theoretically proven that with a linear classification method, feature
agglomeration cannot give worse performance than the original method.

Algorithm 8 DEFRAG: Make Tree

1:If $|S|\leq d_{0}$ then

2: $n\leftarrow\text{Make-Leaf}(S)$

3:else

4: $n\leftarrow\text{Make-Internal-Node}()$

5: $\\{S_{+},S_{-}\\}\leftarrow\text{Balanced-Split}(S,\\{z^{i},i\in S\\})$ //
Balanced Spherical kmeans or nDCG split

6: $n_{+}\leftarrow\text{Make-Tree}(S_{+},\\{z^{i},i\in S_{+}\\},d_{0})$

7: $n_{-}\leftarrow\text{Make-Tree}(S_{-},\\{z^{i},i\in S_{-}\\},d_{0})$

8: $n.\text{left\\_child}\leftarrow n_{+}$

9: $n.\text{right\\_child}\leftarrow n_{-}$

10:return  Root node of the tree

DEFRAG first creates a representation vector for each feature $j\in[d]$ and
then performs hierarchical clustering on them. At each internal node of the
hierarchy, features at that node are split into two children nodes of equal
sizes by solving either a balanced spherical 2-means problem, or by minimizing
nDCG. This process is continued until we are left with less than $d_{0}$
features at a node, in which case the node is made a leaf. The representative
vectors can be either based on features only or labels and features together
which can perform different functions.

The use of DEFRAG for dimensionality reduction has several advantages over the
classical dimensionality reduction techniques such as PCA or random
projections for high-dimensional sparse data. Feature agglomeration in DEFRAG
involves summing up the coordinates of a vector belonging to the same cluster.
This is much less computationally expensive than performing PCA or random
projections. Also, the feature agglomeration done in DEFRAG does not densify
the vector. If the sparsity of a vector is $s$, then the $K$-dimensional
vector resulting from the agglomeration will have at most $s$ non-zeros
($s\leq K,s=K$ if one feature from each cluster has a non-zero). This is
unlike PCA or random projections which densify the vectors which in turn cause
algorithms such as SLEEC or LEML to use low dimensional embeddings. This
results in a loss of information. Thus, using DEFRAG preserves much of the
information of the original vectors and also offers speedup due to reduced
dimensionality.

##### Comparison between above stated methods

  1. 1.

Method LEML outperforms all of the compressed sensing based methods in terms
of performance and subsequent methods based on LEML hence outperform
compressed sensing based methods.

  2. 2.

Method SLEEC was the first to find the issue with low-rank decomposition based
methods proposed as compressed sensing based methods. Using a distance
preserving embedding, SLEEC achieved a large improvement over previous
methods. AnnexML improved on SLEEC further improving both performance and
prediction times.

  3. 3.

Method REML revisits the idea of low-rank embeddings by separating out the
tail labels and learning different predictors for head and tail labels.

Linear Algebra Based Methods
---
Algorithm |  Type of Method |  Summary
MLCSSP |  Subset Selection |  The maximum spanning subset of the label matrix is chosen i.e., a label subset is chosen which best represents the entire label space. Prediction is performed in this label space and the results are then extrapolated on the entire label set.
LEML |  Low rank decomposition |  The low-rank decomposition of the label matrix is assumed and a general ERM framework is proposed to solve it. Attempts to generalize compressed sensing based methods like CPLST and apply them for missing labels too.
SLEEC |  Distance preserving embeddings |  A method for generating embeddings which preserve the distance between labels in the generated embedding space. The prediction is done via KNN in the embedding space.
REMBRANDT |  Low rank decomposition |  Uses a randomized low-rank matrix factorization based technique to perform rank-constrained embedding. It can be shown to be equivalent to CPLST in the simplest case.
PD-SPARSE |  Separation Ranking Loss based Frank Wolfe |  Utilizes the dual and primal sparsity of a solution to the problem with separation ranking loss and $L1$ regularization. The problem is solved via a Fully Corrective Block Coordinate Frank Wolfe Algorithm.
REML |  Low rank decomposition |  Re-visits the Low rank decomposition technique and tries to resolve the issue tail labels create by separating head and tail labels. This makes the low-rank assumption valid once again and head and tail labels are predicted separately.
AnnexML |  Distance preserving embedding |  Distance preserving embeddings and improvement over the SLEEC algorithm by using a KNN graph for partitioning labels, using a ranking based loss and using an ANN based prediction technique.
DEFRAG |  Feature Agglomeration Supplement |  An algorithm for dealing with large feature spaces in extreme classification by performing feature agglomeration. Can also be used for feature imputation and label re-ranking.

###  4.3 Tree Based

Tree Based methods rely on the inherent hierarchy of the data to speed up the
multi-label learning and prediction. The main goal of these methods is to
repeatedly divide either the label or sample space in order to narrow down the
search space during prediction. The leaf nodes generally contain a one-versus-
all or a simple averaging based technique for final prediction.

Broadly, these techniques can be categorized into two types :

  1. 1.

Label Partitioning based. These methods rely on dividing the labels into
clusters at each level, thus forming a sort of meta-label structure. Each of
the levels is then equipped with a multi-label classifier to determine the
most relevant meta labels. The leaves contain a small number of labels which
can be dealt with by a one-vs-all classifier.

  2. 2.

Sample/Instance Partitioning Based. These methods group together the train
samples and cluster them into branches at each level. This forms a sort of
decision tree structure which can be used to group the incoming test point
into the correct branches and finally reach the leaf. The branch decisions are
made by a multi-class classifier and the final predictions on the leaf are
then made by combining the labels of the instances at that leaf.

Figure 7: Comparison of label and instance partitioning methods. Label
partitioning methods (top left) cluster labels to convert XML into a series of
multi-label classification problems. Instance partitioning methods cluster
samples and allow KNN-like approaches at the leaf.

Tree Based methods in general provide faster training and prediction than the
embedding and deep-learning based methods due to the reduction of training and
search space provided by the tree structure.

The paper Prabhu and Varma (2014) proposes a method called FastXML which
improves upon the state of the art tree based multi label classification
methods of the time, Multi-Label Random Forest Classifier (MLRF) Liu et al.
(2015) and Label Partitioning by Sub-linear Ranking (LPSR)Weston et al.
(2013). Both these methods learn a hierarchy of the labels to deal with the
large number of labels. The LPSR learns relaxed integer programs to partition
the sample into the clusters learnt by k-means like algorithm. MLRF on the
other hand learn an ensemble of randomized trees but uses a brute force
partitioning method based on Gini index or entropy. In contrast, FastXML
learns to partition samples or data points rather than labels.

Both methods MLRF and LPSR did not perform competitively on XML datasets when
compared with existing methods. Significantly higher accuracy is achieved by
FastXML by optimizing a nDCG loss along with learning the ranking of the
labels in each partition at the same time. An alternating minimization
algorithm for efficiently optimizing the problem formulation is also
developed.

FastXML proposes to learn the hierarchy by directly optimizing the ranking
loss function. This way of learning the hierarchy is better as nDCG is a
measure which is sensitive to both relevance and ranking ensuring that the
relevant positive labels are predicted with the highest possible ranks. This
is not guaranteed by rank insensitive measures such as Gini-index in MLRF or
clustering error in LPSR.

FastXML partitions the current node feature space by learning a linear
separator $w$ such that

$\displaystyle\min\,{||w||}_{1}+\sum_{i}C_{\delta}(\delta_{i})\log(1+e^{\delta_{i}w^{T}x_{i}})$
$\displaystyle-
C_{r}\sum_{i}\frac{1}{2}(1+\delta_{i})L_{\text{nDCG}_{@L}(r^{+},y_{i}}$
$\displaystyle-
C_{r}\sum_{i}\frac{1}{2}(1-\delta_{i})L_{\text{nDCG}_{@L}(r^{-},y_{i}}),$

where $w\in\mathcal{R}^{D},\delta\in\\{-1,+1\\}_{L},r^{+},r^{-}\in\Pi(1,L)$
where $i$ represents indices of all the training points present at the node
being partitioned. $\delta_{i}\in\\{-1,+1\\}$ is indicative of whether point
$i$ was assigned to the negative r positive partition . The positive and
negative partition are represented by variables $r^{+}$ and $r^{-}$
respectively. User defined parameters $C_{\delta}$ and $C_{r}$ are used to
determine the relative importance of the three terms.

There are three types of parameters in the equation, $w$, $\delta$ and
$r^{+},r^{-}$. Though the other two parameters can be obtained from $w$
itself, it is easier to optimize with separate parameters. The first term in
the loss is an $l_{1}$ term on $w$ which ensures sparsity. The second term is
the log loss of $\delta_{i}w^{T}x_{i}$. This term optimizes the parameters
$\delta$ and $w$ together, as the solution to be obtained is $\delta_{i}^{*}=$
sign$(w^{T}x_{i})$. This tries to make sure that a point which is assigned to
the positive (negative) partition, i.e points for which
$\delta_{i}=+1(\delta_{i}=-1),$ will have positive (negative) values of
$w^{T}x_{i}$. The third and fourth terms in the equation maximize the
$\text{nDCG}_{@L}$ of the rankings predicted for the positive and negative
partitions, $r^{+}$ and $r_{-}$ respectively. These terms relate $r^{+}$ to
$\delta$ and thus to $w$.

Maximizing nDCG makes it likely that the relevant positive labels for each
point are predicted as high as possible. As a result, points within the same
partition are more likely to have similar labels whereas points in different
partitions are more likely to have dissimilar labels.

The loss also allows a label to be assigned to both partitions if some of the
points which contain the label are assigned to the positive partition and some
to the negative. This makes the FastXML trees more robust as the error which
is propagated from the parents may be corrected by the children.

Once we have learned the hyperplane during the training phase, then we know
how to partition a test instance into a left or a right child. So, now we know
how to traverse the tree starting at the root and keep applying this procedure
recursively until we get to a leaf.

Given a new data point for prediction, $x\in\mathbb{R}^{D}$, FastXML’s top
ranked $k$ predictions are given by

$r(x)=\text{rank}_{k}\left(\frac{1}{T}\sum_{i=1}^{T}P_{t}^{\text{leaf}}(x)\right),$
(22)

where $T$ is the number of trees in the FastXML ensemble and
$P_{t}^{\text{leaf}}(x)$ is the distribution of points in the lead nodes
containing $x$ in tree $t$. It is found empirically, that the proposed nDCG
based objective function learns balanced which leads to fast and accurate
predictions in logarithmic time. The main reason behind the accurate
prediction is the novel node partitioning formulation which optimized an nDCG
based ranking loss over all the labels. Such a loss turns is more suitable for
XML than the Gini index used by MLRF or the clustering error used by LPSR and
efficiently scales to problems with more than millions of labels.

#####

In the paper Prabhu et al. (2018), a label tree partitioning based method,
Parabel, is proposed which aims to achieve the high prediction accuracy
achieved by one-vs-all methods such as DiSMEC Babbar and Schölkopf (2016) and
PPDSparse Yen et al. (2017) while having fast training and prediction times.
Parabel overcomes the problem of large label spaces by reducing the number of
training points in each one vs all classifier such that each label’s negative
training examples are those with most similar labels. This is performed using
the tree structure learnt.

In Parabel, labels are recursively partitioned into two groups to create a
balanced binary tree. After the partitioning, similar labels end up in a
group. Partitioning is stopped when the leaf node contains at-least $M$
labels. After the tree construction, two binary classifiers have to be trained
at each internal node. These two classifiers help in determining whether the
test point has to be sent to left or the right child or both. At the leaf node
One vs All classifiers are trained for each label associated with that leaf
node. At the time of prediction, a test sample is propagated through the tree
using classifiers at internal nodes, after reaching leaf nodes, ranking over
the labels is assigned using the one vs all classifiers present at the leaf.

The labels are represented by the normalized sum of training instances to in
which it appears. This label representation is used to cluster the labels
using a $2$-means objective along with an extra term to ensure that the label
splits are uniform. Further, the distance between labels is measured using the
cosine function, which basically leads to a spherical k-means objective with
$k=2$. This objective is solved using the well-known alternating minimization.

Using this splitting procedure recursively for each internal node of the tree
starting from the root, we can partition the labels to create a balanced
binary tree. Partitioning is stopped when there are less than $M$ number of
labels in a cluster and they become leaf nodes. In the final tree structure we
end up with, the internal nodes represent meta-labels, and the problem at each
node becomes a smaller multi-label classification problem.

After the tree structure is learnt, we need to train a classifier at each edge
for predicting the probability of the child being active given that the parent
is active. Let $z_{n}$ be a binary variable associated with each node $n$ for
each sample. For a given sample , if $z_{n}=1$ then the sub-tree rooted at
node $n$ has a leaf node which contains a relevant label of the given sample.
Thus we need to predict $P(z_{iCn}=1\mid z_{in}=1,x)$ at each internal node,
where $C_{n}$ represents a child of node $n$. This can be done by optimizing
the MAP estimate

$\underset{\Theta_{I_{n}}}{\min}\quad-\log
P(\Theta_{I_{n}})-\sum_{i:z_{in}}\log P\left(z_{iCn}\mid
z_{in}=1,x_{i},\Theta_{I_{n}},\right),$ (23)

which is parameterized by $\Theta_{I_{n}}$.

Similarly, at the leaf nodes one has to minimize the loss

$\underset{\Theta_{L_{n}}}{\min}\quad-\log
P(\Theta_{L_{n}})-\sum_{i:z_{in}}\log P\left(y_{in}\mid
z_{in}=1,x_{i},\Theta_{L_{n}}\right),$ (24)

which basically trains a one-vs-all classifier for each label present in that
leaf.

Highly parallel and distributed versions of Parabel are possible because all
the optimization problems are independent. The independence does not imply
that model does not recognize label to label dependency or correlation. In
fact, the model does take into account label-label correlation when clustering
the labels. At the time of clustering similar labels are grouped into a
cluster, thus model is not truly independent with respect to labels.

During prediction, the goal is to find the top $k$ labels with the highest
value of

$P(y_{l}\mid x)=P(y_{l}=1\mid z_{n}=1,x)\,\Pi_{n_{0}\in
A_{n}}P(z_{n_{0}}=1\mid z_{P_{n_{0}}}=1,x),$ (25)

where $P_{n}$ is the parent of node $n.$ This means that we have to find the
path to the leaf from the root with the maximum value of product of
probabilities on its nodes. We can use a beam search (greedy BFS traversal) to
find the top $k$ labels with the highest probabilities.

#####

The paper Siblini et al. (2018) proposes a random forest based algorithm with
a fast partitioning algorithm called CRAFTML (Clustering based RAndom Forest
of predictive Trees for extreme Multi-label Learning). The method proposed is
also an instance/sample partitioning based method like FastXML but it uses a
k-means based classification technique in comparison to nDCG optimization in
FastXML. Another major difference with FastXML is that it uses $k$-way
partition in the tree instead of 2-way partitions. CRAFTML also exploits a
random forest strategy which randomly reduces both the feature and the label
spaces using random projection matrices to obtain diversity.

CRAFTML computes a forest $F$ of $m_{F}$ $k$-ary instance trees which are
constructed by recursive partitioning. The base case of the recursive
partitioning is either of the three $(i)$ the number of instances in the node
is less than a given threshold $n_{\text{leaf}},(ii)$ all the instances have
the same features, or $(iii)$ all the instances have the same labels. After
the tree training is complete, each leaf stores the average label vector of
the samples present in the leaf.

The node training stage in CRAFTML is decomposed into three steps. First, a
random projection of the label and feature vectors into lower dimensional
spaces is performed. This is done using a projection matrix which is randomly
generated from either Standard Gaussian Distribution or sparse orthogonal
projection. Next, $k$-means is used for recursively partitioning the instances
into $k$ temporary subsets using their projected label vectors. We thus obtain
$k$ cluster centroids. The cluster centroids are initialized with the
$k$-means++ strategy which improves cluster stability and algorithm
performances against a random initialization. Finally, the cluster centroids
are re-calculated by taking the average of feature vectors assigned to the
temporary clusters. We now have a $k$-means classifier which is capable of
classification by finding the closest cluster to any instance. The instances
are partitioned into $k$ final subsets (child nodes) by the classifier.

The training algorithm is given below.

Algorithm 9 trainTree

Input: Training set with a feature matrix $X$ and a label matrix $Y.$

Initialize node $v.$

$v.$isLeaf $\leftarrow$ testStopCondition($X,Y$)

if $v.$isLeaf = false then

$v.$classif $\leftarrow$ trainNodeClassifier($X,Y$)

$(X_{child_{i}},Y_{child_{i}})_{i=0,\cdots,k-1}$ $\leftarrow$
split($v.$classif,$X,Y$)

for $i$ from $0$ to $k-1$ do

$v.child_{i}\leftarrow$ trainTree($X_{child_{i}},Y_{child_{i}}$)

end for

else

$v.\hat{y}\leftarrow$ computeMeanLabelVector($Y$)

end if

Output: node $v$

Algorithm 10 trainNodeClassifier

Input: feature matrix $(X_{v})$ and label matrix $(Y_{v})$ of the instance set
of the node $v.$

$X_{s},Y_{s}\leftarrow$ sampleRows($X_{v},Y_{v},n_{s}$) $\triangleright$
$n_{s}$ is the sample size

$X_{s}^{{}^{\prime}}\leftarrow X_{s}P_{x}$ $\triangleright$ random feature
projection

$Y_{s}^{{}^{\prime}}\leftarrow Y_{s}P_{y}$ $\triangleright$ Random label
projection

$c\leftarrow k$-means($Y_{s}^{{}^{\prime}},k$) $\triangleright$
$c\in\\{0,\cdots,k-1\\}^{\min(n_{v},n_{s})}$

$\triangleright$ $c$ is a vector where the $j^{th}$ component $c_{j}$ denotes
the cluster idx of the $j^{th}$ instance associated to
$(X_{s}^{{}^{\prime}})_{j,.}$ and $(Y_{s}^{{}^{\prime}})_{j,.}.$

for $i$ from $0$ to $k-1$ do

$(classif)_{i,.}\leftarrow$computeCentroid(${(X_{s}^{{}^{\prime}})_{j,.}|c_{j}=i}$)

end for

Output: Classifier $classif(\in\mathbb{R}^{k\times d_{x}^{{}^{\prime}}})$

During prediction, we traverse from the root to the leaves using the $k$-means
classifier decisions at each layer. Once a leaf is reached, prediction is
given by the average of the label vectors of instances present at that leaf.
Using the forest, we aggregate the predictions which largely helps increase
the accuracy.

#####

Khandagale et al. (2020) introduces a method Bonsai, which improves on Parabel
Prabhu et al. (2018). The authors make the observation that in Parabel, due to
its deep tree structure there is error propagation down the tree, which means
that the errors in the initial classifiers will accumulate and cause higher
classification error in leaf layers. Also, due to the balanced partitioning in
the tree layers, the tail labels are forced to be clustered with the head
labels, which causes the tail labels to be subsumed. Hence, in Bonsai, a
shallow tree structure with $\geq 2$ children for each node is proposed which
($i$) prevents ”cascading effect” of error in deep trees. ($ii$) allows more
diverse clusters preventing misclassification of tail labels.

Another contribution of the paper is to introduce different types of label
representations based on either the feature-label correlations , label-label
co-occurrence or a combination of both.

Let ${(x_{i},y_{i})_{i=1}^{N}}$ be the given training samples with $x_{i}\in
R^{D}$ and $y_{i}\in\\{0,1\\}^{L}$. $X_{N\times D}$, $Y_{N\times L}$ are data
and label matrices respectively. Let $v_{l}$ be the representation of label
$l.$

There are three ways to represent the labels before clustering.

In the input space representation, $v_{l}=\sum_{i=1}^{N}y_{il}x_{i}$, this can
be compactly written as $V=Y^{T}X$, where each row $V_{p:}$ corresponds to the
label representation of the label, i.e. $p^{th}$ row is the label
representation of label number $p$ ($V_{p:}=v_{p}$).

$\displaystyle\nu_{i}=Y^{T}X=\begin{bmatrix}v_{1}^{T}\\\ v_{2}^{T}\\\
\vdots\\\ v_{L}^{T}\\\ \end{bmatrix}_{L\times D},\quad\text{where}\quad
X=\begin{bmatrix}x_{1}^{T}\\\ x_{2}^{T}\\\ \vdots\\\ x_{N}^{T}\\\
\end{bmatrix}_{N\times D}Y=\begin{bmatrix}y_{1}^{T}\\\ y_{2}^{T}\\\ \vdots\\\
y_{L}^{T}\\\ \end{bmatrix}_{N\times L}.$ (26)

In the output space representation, the Label representation matrix $\nu_{o}$
is given by

$\displaystyle\nu_{o}=Y^{T}Y$ $\displaystyle=\begin{bmatrix}v_{1}^{T}\\\
v_{2}^{T}\\\ \vdots\\\ v_{L}^{T}\\\ \end{bmatrix}_{L\times
L},\quad\text{where}\quad Y=\begin{bmatrix}y_{1}^{T}\\\ y_{2}^{T}\\\ \vdots\\\
y_{L}^{T}\\\ \end{bmatrix}_{N\times L}.$ (27)

In the joint input-output representation, the Label representation matrix
$\nu_{io}$ is given by

$\displaystyle\nu_{io}=Y^{T}Z=\begin{bmatrix}v_{1}^{T}\\\ v_{2}^{T}\\\
\vdots\\\ v_{L}^{T}\\\ \end{bmatrix}_{L\times(D+L)},\quad\text{where}\quad
Z=\begin{bmatrix}z_{1}^{T}\\\ z_{2}^{T}\\\ \vdots\\\ z_{L}^{T}\\\
\end{bmatrix}_{N\times(D+L)}Y=\begin{bmatrix}y_{1}^{T}\\\ y_{2}^{T}\\\
\vdots\\\ y_{L}^{T}\\\ \end{bmatrix}_{N\times L}.$ (28)

Here the matrix $Z$ is obtained by concatenating the vector $X$ and vector
$Y,$ hence the dimension $N\times(D+L).$

The training and prediction algorithms for Bonsai remain the same as Parabel,
except that any of the label representations may be used, the tree is created
by dividing into $k$ clusters, and the balancing constraint is not enforced.

#####

Extreme Regression (XReg) Prabhu et al. (2020) is proposed as a new learning
paradigm for accurately predicting the numerical degree of relevance of an
extremely large number of labels to a data point. For example, predicting the
search query click probability for an ad. The paper introduces new regression
metrics for XReg and a new label-wise prediction algorithm useful for Dynamic
Search Advertising (DSA).

The extreme classification algorithms treat the labels as being fully relevant
or fully irrelevant to a data point but in XReg, the degree of relevance is
predicted. Also, the XML algorithms performs point-wise inference i.e. for a
given test point, recommend the most relevant labels. In this paper, an
algorithm is designed for label-wise inference, i.e., for a given label,
predict the most relevant test points. This improves the query coverage in
applications such as Dynamic Search Advertising.

XReg is a regression method which takes a probabilistic approach to estimating
the label relevance weights. All the relevant weights are normalized to lie
between 0 and 1 by dividing by its maximum value, so as to treat them as
probability values. These relevant weights are treated as marginal
probabilities of relevance of each label to a data point. Thus, XReg attempts
to minimize the KL Divergence between the true and predicted marginal
probabilities for each label w.r.t each data point. This is expensive using
the naive $1$-vs-All approach. So, XReg uses the trained label tree from
Parabel.

Each internal node contains two $1$-vs-All regressors which give the
probabilities that a data point traverses to each of its children. Each leaf
contains $M$ $1$-vs-All regressors which gives the conditional probability of
each label being relevant given the data point reaches its leaf.

For point-wise prediction, beam search is used as in Parabel. The top ranked
relevant labels are recommended based on a greedy $BFS$ traversal strategy.
For label-wise prediction, estimate what fraction of training points visit the
node of a tree, say $f.$ For some factor $F$, allot $f\times F$ test points to
respective nodes. This ensures all the non-zero relevance points for a label
end up reaching the labels’ leaf node. Finally, the topmost scoring test
points that reach a leaf are returned.

##### Comparison between above stated methods

  1. 1.

Most tree based methods do not outperform the baseline one-vs-all scores, but
however have lesser prediction and training times than compressed sensing,
linear algebra and deep learning methods. For example, CRAFTML is $20\times$
faster at training than SLEEC.

  2. 2.

Label partitioning based methods perform slightly better than the instance
partitioning methods in experimentation. Bonsai outperforms CRAFTML in most
datasets.

  3. 3.

Label partitioning is a more scalable approach due to the number of instances
possibly being arbitrarily large. Instance partitioning is however, faster
during prediction due to no need for traversal of multiple paths in the tree.

Tree Based Methods
---
Algorithm |  Type of Tree |  No of children |  Explicit Balancing |  Partitioning Method |  Classification Method in Leaf
FastXML |  Instance Tree / Sample Tree |  Binary Tree ($2$ children) |  No Balancing |  nDCG based loss optimization problem solved at each internal node to learn partitioning and label ranking at the same time |  Ranking function learnt at the leaves used for direct label prediction
Parabel |  Label Tree |  Binary Tree ($2$ children) |  Balancing done by partitioning into same sized clusters |  $2$-means based partitioning into balanced clusters |  Labels with highest probability predicted by a MAP estimate learnt during training
CRAFTML |  Instance Tree / Sample Tree |  $k$-ary Tree ($k$ children) |  No Balancing |  $k$-means clustering on projected label and feature vectors for each sample |  $k$-means classifier and label averaging for prediction
Bonsai |  Label Tree |  $k$-ary Tree ($k$ children) |  No Balancing |  $k$-means based partitioning into clusters |  Labels with highest probability predicted by a MAP estimate learnt during training
XReg |  Label Tree |  Binary Tree ($2$ children) |  Balancing done by partitioning into same sized clusters |  $2$-means based partitioning into balanced clusters |  Labels with highest probability predicted by a set of regressor on the path to the leaf node is given as final output.

###  4.4 Deep Learning Based

Deep Learning as a field has exploded in the recent past and has started to
become a dominating method in most machine learning problems, where there is a
large amount of available data. In extreme multi label classification, deep
learning did not make an advent until much later due to several possible
reasons. Firstly, the output space being extremely large implies the
requirement of very large models. Secondly, the very large tail-label
distribution implies that a large set of labels have very little training data
available, hindering the ability for deep learning models to learn enough to
predict these labels correctly. For example, in the Wiki-500K dataset Bhatia
et al. (2016), 98% of labels have less than 100 training instances. Thus,
efforts to use Deep Learning in the field were not as successful and linear
algebra and tree based methods dominated.

However, Deep Learning was very successful in extracting context dependent
information from the raw text due to the highly non-linear nature of learning.
With this ability to obtain highly representative embeddings from the text,
the usage of bag-of-word models in XML was contested by deep-learning based
methods.

#####

The paper Liu et al. (2017) was the first to try out application of Deep
Learning in XML, using a family of CNN’s. This followed the success of deep
learning in multi-class text classification problems by methods like FastText
Joulin et al. (2016), CNN-Kim Chen (2015) and Bow-CNN Liu et al. (2017). These
methods inspire this new method XML-CNN which applies similar concepts to
obtain an extreme multi-label classifier.

CNN-Kim Chen (2015) creates a document embedding from concatenation of word
embeddings. $t$ CNN filters are applied to obtain a $t$ dimensional vector
which is passed to a soft-max layer after max pooling. Bow-CNN Liu et al.
(2017) creates a $V$ dimensional vector for each region of the text, where $V$
is the vocabulary size, indicating whether each word is present in the region.
It also uses dynamic max pooling for better results. XML-CNN combines these
ideas and proposes the following architecture - various CNN filters similar to
CNN-Kim, dynamic max pooling similar to Bow-CNN, a bottleneck fully connected
layer, and binary cross entropy loss over a sigmoid output layer.

Let $e_{i}\in R^{k}$ be the word embedding of the $i-$th word of the document,
then $e_{i:j}\in R^{k(j-i+1)}$ is the concatenation of embeddings for a region
of the document. A convolution filter $v$ is applied to a region of $h$ words
to obtain $c_{i}=g_{c}(v^{T}e_{i:i+h-i})$ which is a new feature, where
$g_{c}$ is a non-linear activation. $t$ filters like this are used with
varying $h$ to obtain a a set of new features.

Dynamic Max pooling is then used on these newly obtained features $c$. The
usual max pooling basically takes the maximum over the entire feature vector
to obtain a single value. However, this value does not sufficiently represent
the entire document well. Thus, a max-over-time pooling function is used to
aggregate the vector into a smaller vector by taking max over smaller segments
of the initial vector. Thus, pooling function $P$ is given by

$\displaystyle
P(c)=\left[\max\left(c_{1:\frac{m}{p}}\right),\,\dots,\,\max\left(c_{m-\frac{m}{p}+1:m}\right)\right]\in\mathbb{R}^{p}.$

This pooling function can accumulate more information from different sections
of the document. These poolings from different filters are then concatenated
into a new vector.

The output of the pooling layer is now fed into a fully connected layer with
fewer number of neurons, also called a bottleneck layer. This bottleneck layer
has two advantages. Firstly, it reduces the number of parameters from
$pt\times L$ to $h\times(pt+L)$ where $L$ is the number of labels, $t$ is the
number of filters, $p$ is the pooling layer hyperparameter and $h$ is the
number of hidden layers in the bottleneck layer. This allows the model to fit
in memory as L is often large. Secondly, another non-linearity after the
bottleneck layer leads to a better model. Thirdly, this encourages the
learning of a more compact representation of the data.

Figure 8:  The XML-CNN model

Finally, the output of the bottleneck layer is passed through another fully
connected layer with output size $L$. The binary cross entropy loss is
observed to work the best used for this method.

The ablation studies performed in the paper show that BCE loss, bottleneck
layer, and dynamic max pooling each contribute to the improvement of the
model. Though XML-CNN was slower than the tree based methods, it clearly
outperformed them in terms of performance. It also performed better than
linear algebra based methods, showing the potential deep learning held for the
XML field.

#####

However, XML-CNN was unable to capture the most relevant parts of the input
text to each label, because the same text representation is given for all the
labels. Sequence to Sequence based methods like MLC2Seq Nam et al. (2017) were
also not suited for the task since the underlying assumption that labels are
predicted sequentially is not reasonable in extreme classification. You et al.
(2019) proposed AttentionXML, which used a BiLSTM (bidirectional long short-
term memory) to capture long-distance dependency among words and a multi-label
attention to capture the most relevant parts of texts for each label. Since
application of attention to train on each label with the full dataset is not
possible for large datasets, there must be a method for training on only the
most relevant samples for each label. For this, AttentionXML uses a shallow
and wide Probabilistic Label Tree (PLT) built on the labels.

The first step is to create the PLT, which is be done by hierarchical
clustering algorithm followed by a compression algorithm to reduce depth. This
step is similar to that of Parabel Prabhu et al. (2018) where we create a
label tree, but here the tree is constructed to be wide and shallow. In
effect, the label tree resembles that of Bonsai Khandagale et al. (2020). The
reason for creation of a wide tree instead of a deep one is to prevent error
propagation through the levels. The leaves correspond to an original label
while the internal nodes correspond to meta or pseudo labels. Each node
predicts $P(z_{n}|z_{Pa(n)}=1,x)$, ie the probability that label or pseudo-
label $n$ is present, given that parent of $n$ is present. Thus, the marginal
probability for each label being present is given by the product of
probabilities in its path in the PLT i.e.,

$\displaystyle P(z_{n}=1\mid x)=\Pi_{i\in\text{Path}(n)}P(z_{i}\mid
z_{Pa(i)}=1,x).$

The value of the marginal probabilities is predicted by the attention based
deep learning network. As depicted in 10, the architecture consists of a
bidirectional LSTM which finds embeddings for the words and then followed by a
2-layer fully connected neural network which finally predicts the probability
that the current label is active given the input. There is one block of such
network per layer of the PLT.

The input to the fully connected layers is given by using a attention based
mechanism which can find if a word embedding is relevant to the label.
Finally, the parameters of the fully connected layers are shared among the
different labels in each layer, as they perform the same function. This also
largely helps reduce model size. Further, to reduce training cost, the model
weights of each layer is initialized with the weights of the previous layer.

Figure 9:  An Illustration of Attention Aware Deep Model in AttentionXML

It is to be noted that even if this network is directly used, the training
time will be infeasible as each label would have to train on each sample.
However, we do not need to train on every sample for a particular label.
Hence, only the samples which contain the label and a few more negative
samples are used for training.

AttentionXML outperforms XML-CNN and most other methods in terms of P@1
scores. Further, the good PSP scores show that AttentionXML performs well on
tail labels as well. The utility of multi-head attention is proven in the
ablation study. However, AttentionXML is not easy to train as the training and
prediction times are much larger compared to other methods and hence does not
scale well to larger datasets.

#####

Despite the usage of attention by AttentionXML, a direct attempt at using the
pretrained transformers for XML was not yet made. The transfer learning of
pretrained transformers for this task could be the solution to the large
training times required by AttentionXML. Chang et al. (2020) made the first
attempt at using pretrained transformers for the XML task in the model
XTransformer. Transformers like BERT Devlin et al. (2018), RoBERTa Liu et al.
(2019), and XLNet Yang et al. (2019) are highly successful in the NLP domain
where they outperformed most other methods on tasks like question answering,
POS tagging, and sentence classification due to their ability to generate
contextual embeddings for words and sentences which are applicable to
downstream tasks. However, application of these models for the XML problem was
not so straightforward even though XML is primarily a text classification
problem.

The difficulty was because of the large number of labels and the output space
sparsity. Many of the labels do not have enough samples to be able to be able
to train large deep neural networks and hence direct application of pretrained
transformers led to bad results and memory issues. Xtransformer handles this
by reducing the larger problem into smaller subproblems, like in tree based
methods, and then training the transformers to predict in this smaller
problem. Each of the subproblems are eventually solved to get the final
predictions.

More concretely, the XTransformer model consists of three parts or modules.
The first module is called Semantic Label Indexing, which is responsible for
the division of the larger problem into smaller subproblems. For this, a
clustering of the labels is performed, creating $K$ clusters where $K\ll L$.
The clusters are created by finding a label to cluster assignment matrix
$C\in\\{0,1\\}^{L\times K}$ where $C_{lk}=1$ if label $l$ belongs to cluster
$k$. This matrix can be created by using hierarchical clustering algorithms
and the clusters are represented based on the mean of transformer embeddings
of the label text for the labels present in the cluster.

These clusters are then used as meta-labels for the problem of fine tuning the
transformer models in the second module called the Neural Matcher. Since the
number of meta-labels is much smaller, the label sparsity issue due to tail
labels is avoided. The transformers are trained to map from instances to the
relevant clusters. Embeddings $\phi(x)$ are thus trained for each instance
$x$.

In the third module after the matching step, a small subset of label clusters
is selected for each instance from which we are required to find a relevance
score of each label. For performing this final step which is crucial to
prediction, a one-vs-all classifier is trained for each label. The instances
on which each label trains must be limited in number to allow efficient
training. Techniques like picking teacher-forcing negatives (for each label
$l$, picking only the instances instances with label $l$ or with any of the
labels in the same cluster as label $l$) allow picking only a small subset of
“hard” instances.

Figure 10:  The XTransfomer method

During prediction, a subset of clusters are selected by the Matcher. All the
labels selected from each of the clusters are then passed the test instance to
which each one-vs-all classifier gives a relevance score to decide if the
label is relevant to the instance, based on which the label ranking is done.
XTransformer is successfully able to perform well on all datasets and was only
outperformed by AttentionXML on some datasets at the time.

Some other successful methods which attempt to fine tune transformers have
been recently proposed such as APLC-XLNet, Ye et al. (2020) which uses
transfer learning of the popular transformer model XLNet Yang et al. (2019).
As with previous methods, performing this directly is not possible, hence this
methods uses Adaptive Probabilistic Label Clusters, which attempts a
clustering based on separating the head and tail clusters, and then assigning
head cluster as the root of a tree and tail clusters as leaves.

Another method which uses transformers to perform extreme classification is
LightXML Jiang et al. (2021). This paper points out that methods like
AttentionXML and XTransformer suffer from static negative sampling, which
highly reduces the ability of the model. The main advantage of LightXML over
other methods using static negative sampling is that the model does not
overfit to specific negative samples. LightXML performs dynamic negative
sampling by using a generator-discriminator like method in which the label
recalling is performed by a module (generator) and the label ranking is done
by another module. This procedure allows each module to try and improve its
own objective while enhancing the other, thus leading to better performance
overall.

#####

A general trend can be observed from papers like AttentionXML and
XTransformer, where deep learning methods are not directly applied to the
problem due to scalability issues. Instead, the deep learning model is applied
to a smaller subproblem to obtain intermediate features which can be further
used in the problem. Also, negative sampling is generally used for training
the final model as training on all samples is not feasible. Dahiya et al.
(2021b) comes up with a general framework for applying deep learning methods
to XML called DeepXML. Consequently, they propose a new method called ASTEC
using the existing method which achieves a new state of the art for some
datasets in the domain.

The paper defines DeepXML to be a framework with four modules. Each module is
designed to be fairly of low complexity, allowing the entire method to scale
to large datasets easily. Not all the methods need to have each of the modules
depending on the utility, and the module algorithm can be switched to another
algorithm easily without affecting the entire method.

The first module of the framework is for training intermediate representations
for the features $Z^{0}$. Here, $Z^{0}$ should be as close as possible to the
final representation of the features $Z$ which would be the feature
representations if the entire problem was optimized directly. Since features
cannot be trained on the entire problem, a surrogate label selection procedure
is followed to ensure that the problem is tractable. Some examples of
surrogate label selection procedures could be label subset selection, label
clustering or or label projection into a smaller space.

The second module of DeepXML is the label shortlisting or the negative
sampling step, where for each sample, we select the most confusing of the
”hardest” labels. We select $N_{i}\subseteq[L]$ for each sample $i$ such that
$|N_{i}|=O(\log L)$ and these labels are most likely to be predicted as
positive labels for the samples. This negative sampling is done based on the
intermediate features learnt in the first module and any method can be used
for this procedure such as graphs, trees, clustering or hashing.

The third module is based on transfer learning to obtain the final feature
representations from the initial feature representations learnt in the first
module. The parameters can be re-trained from the first module, but it must be
ensured that the final feature representation $Z$ should not be too far from
the initial representation.

In the fourth module, the final classifier is learnt. This classifier uses the
feature representation from the third module and the negative samples from the
second module. Since the number of instances for each label is not excessive
due to the negative sampling, the model training time is limited. The third
and fourth modules can be combined as required.

Figure 11:  Overview of the DeepXML Framework

In the paper Dahiya et al. (2021b), the method ASTEC is proposed which uses
the DeepXML framework. For the first module, it uses a tree based clustering
method to obtain the surrogate labels for training intermediate features. For
the second module, an Approximate Nearest Neighbor Search (ANNS) data
structure is used for shortlisting. Modules 3 and 4 are trained together where
the transfer learning is done by a simple transfer matrix, while the final
classifiers are simple one-vs-all classifiers.

More methods using this framework have also been proposed and several existing
ones, such as XTransformer can can be formulated to fit into this framework.
Mittal et al. (2021a) proposes a method DECAF using this framework which
incorporates the label metadata. Mittal et al. (2021b) proposes ECLARE which
utilizes label to label correlation as well as label text to give a new method
following the DeepXML framework. GalaXC Saini et al. (2021) is another method
in this framework which uses graph neural networks on the combined document
label space.

Recent advances have been made in the field by using the label features in
addition to the instance features. Since in many of the XML datasets, the
labels are also entities with some text information. This allows using the
label text for learning better models. Different methods try to utilize the
label features in different ways. For example, DECAF Mittal et al. (2021a)
directly incorporates label text into the classification procedure by
embedding the instances and labels separately and then using a ranker to
predict which label embedding is most relevant to the instance.

On the other hand, GalaXC Saini et al. (2021) utilizes graph neural networks
to learn embeddings jointly over documents and labels. The method uses
convolutions of varying size to develop an attention mechanism for learning
several representations for each node, where each document and label is a
node. Multiple hops over the joint label and document graph allow collection
of information over related labels, other documents with these labels and so
on. This is used for shortlisting and then prediction is finally made by using
the label attention mechanism. ECLARE Mittal et al. (2021b) also uses a
similar method by accommodating for label metadata and label correlations.

SiameseXML Dahiya et al. (2021a) also uses label features, but it aims to
learn joint embeddings for the labels and features by using the concept of
Siamese Networks Chen et al. (2020), Schroff et al. (2015) where a triplet or
contrastive loss is used with a hard negative mining procedure. The main goal
is to learn common embeddings for instances and labels where instances are
close to the respective positive labels and far from the other negative
labels. This concept is adapted to the extreme classification scenario by
using the DeepXML framework.

The paper Dahiya et al. (2022) suggests another method NGAME which uses
Siamese Networks for extreme classification. A common method of using Siamese
Networks is using minibatches. The set of candidate labels contains all the
labels which appear in at least one of the other instances in the minibatch.
The minibatch size, if constructed independently, cannot be too large as the
set of labels would be to big. This leads to slower training. NGAME
strategically constructs the mini-batches such that the samples are close,
thus leading to informative negative samples as compared to random samples.
This leads to better convergence and faster training.

##### Comparison between methods

  * •

XML-CNN although the first of the deep learning methods in XML, is no longer a
competitive method in terms of performance. This is mainly because CNN’s are
not the best at capturing the information from text, and hence have been
outperformed by most other methods.

  * •

AttentionXML and XTransformer are both methods which require a lot of training
time. However, they still remain relevant due to the fact that they perform
significantly well on some datasets. In particular, AttentionXML performs well
on datasets with high average feature text length.

  * •

DeepXML based methods such as SiameseXML, ECLARE and NGAME are currently among
the best performing methods in XML.

Over the last five years, deep learning based methods have outperformed all
other methods in terms of performance. They have much higher accuracies than
tree based methods, but can be slower in terms of train and test complexities
and have higher model sizes.

Figure 12: Timeline of Discussed Methods in XML along with the categories

##  5 Applications of Extreme Classification

Extreme Classification has several applications, especially in cases where the
data is too large to be processed manually or semi-manually.

####  5.0.1 Document Tagging

XML is highly useful for tagging documents with labels which can be selected
multiple at a time. The features can be formulated as some representation of
the document, while labels are the possible tags.

For example, tagging of Wikipedia articles with relevant labels is a problem
which is suited for XML due to the fact that there are a very large number of
labels, some of which are very specific to the articles. This leads to a large
tail label distribution which is typical in XML problems.

####  5.0.2 Product Recommendation

Given a keyword or a “search phrase”, the problem of determining which
products to show given the product description and other information can also
be converted to an extreme classification problem. The “search phrase” or the
query can be treated as a feature while the different products act as labels.
Amazon has several product recommendation datasets such as Amazon-670K,
AmazonCat-13K and AmazonTitles-3M with large label spaces which serve as
benchmarking datasets in XML Medini et al. (2019).

####  5.0.3 Advertising

Finding the appropriate advertisements from the bid phrases given in an
advertisement using the user search phrase is also a popular application of
XML. Search engines such as Bing have adopted XML to highly improve their
click-through rates Dahiya et al. (2021b). Al alternate probelem in
advertizing, which is showing personalized ads using the search history of the
user can also be modelled as an XML problem, with the user search history
being included in the features and the advertisements as labels.

###  5.1 Multimodal Extreme Classification

Recently, there has been work in extending extreme classification methods to
non text domains. Mittal et al. (2022) has recently proposed a new product
recommendation dataset MM-AmazonTitles-300K created from Amazon listings of
products, each accompanied by an image and text. The paper also suggests a
modularized method called MUFIN, which aims to find recommendations based on
search query taking into account both images and text. The method creates
simultaneous data point and label embeddings (by combining the image and text
embeddings) and then uses DeepXML like modules to train the final model.

Figure 13: Practical Applications of XML

Acknowledgments

We would like to acknowledge support of MAPG grant, Qualcomm grant, etc.

## Appendix A.

## References

  * Babbar and Schölkopf (2016) Rohit Babbar and Bernhard Schölkopf.  Dismec: Distributed sparse machines for extreme multi-label classification.  In _WSDM ’17_ , 2016.
  * Balasubramanian and Lebanon (2012) Krishnakumar Balasubramanian and Guy Lebanon.  The landmark selection method for multiple output prediction.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , ICML’12, page 283–290, Madison, WI, USA, 2012. Omnipress.  ISBN 9781450312851.
  * Bhatia et al. (2016) K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma.  The extreme classification repository: Multi-label datasets and code, 2016\.  URL http://manikvarma.org/downloads/XC/XMLRepository.html.
  * Bhatia et al. (2015) Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma, and Prateek Jain.  Sparse local embeddings for extreme multi-label classification.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 730–738. Curran Associates, Inc., 2015.
  * Bi and Kwok (2013) Wei Bi and James T. Kwok.  Efficient multi-label classification with many labels.  In _Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28_ , ICML’13, page III–405–III–413. JMLR.org, 2013.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2008(10):P10008, oct 2008.  doi: 10.1088/1742-5468/2008/10/p10008.
  * Bloom (1970) Burton H. Bloom.  Space/time trade-offs in hash coding with allowable errors.  _Commun. ACM_ , 13(7):422–426, July 1970.  ISSN 0001-0782.  doi: 10.1145/362686.362692.
  * Boutsidis et al. (2009) Christos Boutsidis, Michael W. Mahoney, and Petros Drineas.  An improved approximation algorithm for the column subset selection problem.  In _Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’09, page 968–977, USA, 2009. Society for Industrial and Applied Mathematics.
  * Chang et al. (2020) Wei-Cheng Chang, Hsiang-Fu Yu, Kai Zhong, Yiming Yang, and Inderjit S Dhillon.  Taming pretrained transformers for extreme multi-label text classification.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 3163–3171, 2020.
  * Charikar et al. (2002) Moses Charikar, Kevin Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  In _Proceedings of the 29th International Colloquium on Automata, Languages and Programming_ , ICALP ’02, page 693–703, Berlin, Heidelberg, 2002. Springer-Verlag.  ISBN 3540438645.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pages 1597–1607. PMLR, 2020.
  * Chen (2015) Yahui Chen.  Convolutional neural network for sentence classification.  Master’s thesis, University of Waterloo, 2015.
  * Cissé et al. (2013) Moustapha Cissé, Nicolas Usunier, Thierry Artieres, and Patrick Gallinari.  Robust bloom filters for large multilabel classification tasks.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’13, page 1851–1859, Red Hook, NY, USA, 2013. Curran Associates Inc.
  * Dahiya et al. (2021a) Kunal Dahiya, Ananye Agarwal, Deepak Saini, K Gururaj, Jian Jiao, Amit Singh, Sumeet Agarwal, Purushottam Kar, and Manik Varma.  Siamesexml: Siamese networks meet extreme classifiers with 100m labels.  In _International Conference on Machine Learning_ , pages 2330–2340. PMLR, 2021a.
  * Dahiya et al. (2021b) Kunal Dahiya, Deepak Saini, Anshul Mittal, Ankush Shaw, Kushal Dave, Akshay Soni, Himanshu Jain, Sumeet Agarwal, and Manik Varma.  Deepxml: A deep extreme multi-label learning framework applied to short text documents.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , pages 31–39, 2021b.
  * Dahiya et al. (2022) Kunal Dahiya, Nilesh Gupta, Deepak Saini, Akshay Soni, Yajun Wang, Kushal Dave, Jian Jiao, Prasenjit Dey, Amit Singh, Deepesh Hada, et al.  Ngame: Negative mining-aware mini-batching for extreme classification.  _arXiv preprint arXiv:2207.04452_ , 2022.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dong et al. (2011) Wei Dong, Charikar Moses, and Kai Li.  Efficient k-nearest neighbor graph construction for generic similarity measures.  In _Proceedings of the 20th International Conference on World Wide Web_ , WWW ’11, page 577–586, New York, NY, USA, 2011. Association for Computing Machinery.  ISBN 9781450306324.  doi: 10.1145/1963405.1963487.
  * Evron et al. (2018) Itay Evron, Edward Moroshko, and Koby Crammer.  Efficient loss-based decoding on graphs for extreme classification.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Friedland and Torokhti (2006) Shmuel Friedland and Anatoli Torokhti.  Generalized rank-constrained matrix approximations, 2006.
  * Halko et al. (2011) N. Halko, P. G. Martinsson, and J. A. Tropp.  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  _SIAM Review_ , 53(2):217–288, 2011.  doi: 10.1137/090771806.
  * Hsu et al. (2009) Daniel J. Hsu, Sham M. Kakade, John Langford, and Tong Zhang.  Multi-label prediction via compressed sensing.  _CoRR_ , abs/0902.1284, 2009.
  * Jain et al. (2016) Himanshu Jain, Yashoteja Prabhu, and Manik Varma.  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_ , pages 935–944, 2016.
  * Jain et al. (2010) Prateek Jain, Raghu Meka, and Inderjit Dhillon.  Guaranteed rank minimization via singular value projection.  In _Proceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’10, pages 937–945, USA, 2010\. Curran Associates Inc.  URL http://dl.acm.org/citation.cfm?id=2997189.2997294.
  * Jalan and Kar (2019) Ankit Jalan and Purushottam Kar.  Accelerating extreme classification via adaptive feature agglomeration.  _CoRR_ , abs/1905.11769, 2019.
  * Jasinska and Karampatziakis (2016) Kalina Jasinska and Nikos Karampatziakis.  Log-time and log-space extreme classification.  _arXiv preprint arXiv:1611.01964_ , 2016.
  * Jiang et al. (2021) Ting Jiang, Deqing Wang, Leilei Sun, Huayi Yang, Zhengyang Zhao, and Fuzhen Zhuang.  Lightxml: Transformer with dynamic negative sampling for high-performance extreme multi-label text classification.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 7987–7994, 2021.
  * Joulin et al. (2016) Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov.  Bag of tricks for efficient text classification.  _arXiv preprint arXiv:1607.01759_ , 2016.
  * Khandagale et al. (2020) Sujay Khandagale, Han Xiao, and Rohit Babbar.  Bonsai: diverse and shallow trees for extreme multi-label classification.  _Machine Learning_ , 109(11):2099–2119, 2020\.
  * Lacoste-Julien and Jaggi (2015) Simon Lacoste-Julien and Martin Jaggi.  On the global linear convergence of frank-wolfe optimization variants.  _Advances in neural information processing systems_ , 28, 2015.
  * Lacoste-Julien et al. (2013) Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher.  Block-coordinate frank-wolfe optimization for structural svms.  In _International Conference on Machine Learning_ , pages 53–61. PMLR, 2013.
  * Liu et al. (2015) Feng Liu, Xiaofeng Zhang, Yunming Ye, Yahong Zhao, and Yan Li.  Mlrf: multi-label classification through random forest with label-set partition.  In _International conference on intelligent computing_ , pages 407–418. Springer, 2015.
  * Liu et al. (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_ , pages 115–124, 2017.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Loza Mencía and Fürnkranz (2008) Eneldo Loza Mencía and Johannes Fürnkranz.  Efficient pairwise multilabel classification for large-scale problems in the legal domain.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 50–65. Springer, 2008.
  * McAuley and Leskovec (2013) Julian McAuley and Jure Leskovec.  Hidden factors and hidden topics: understanding rating dimensions with review text.  In _Proceedings of the 7th ACM conference on Recommender systems_ , pages 165–172, 2013.
  * McAuley et al. (2015a) Julian McAuley, Rahul Pandey, and Jure Leskovec.  Inferring networks of substitutable and complementary products.  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 785–794, 2015a.