Label Embedding via Low-Coherence Matrices

Besides label embedding, existing methods for extreme multiclass classification can be grouped into three main categories: label hierarchy, one-vs-all methods, and other methods.

Label Embedding. A natural approach involves representing each label as a vector in a low-dimensional space. LEML (Yu et al.,, 2014) leverages a low-rank assumption on linear models and effectively constrains the output space of models to a low-dimensional space. SLICE (Jain et al.,, 2019) is designed to train on low-dimensional dense features, with each label represented by the mean of all feature vectors associated with that label. SLEEC (Bhatia et al.,, 2015) is a local embedding framework that preserves the distance between label vectors. Guo et al., (2019) point out that low-dimensional embedding-based models could suffer from significant overfitting. Their theoretical insights inspire a novel regularization technique to alleviate overfitting in embedding-based models. WLSTS (Evron et al.,, 2018) is an extreme multiclass classification framework based on error correcting output coding, which embeds labels with codes induced by graphs. Hsu et al., (2009) use column vectors from a matrix with the restricted isometry property (RIP) to represent labels. Their analysis is primarily tailored to multilabel classification.They deduce bounds for the conditional $\ell_{2}$-error, which measures the squared $2$-norm difference between the prediction and the label vector — a metric that is not a standard measure of classification error. In contrast, our work analyzes the standard classification error.

Label Hierarchy. Numerous methods such as Parabel (Prabhu et al.,, 2018), Bonsai (Khandagale et al.,, 2020), AttentionXML (You et al.,, 2019), lightXML (Jiang et al.,, 2021), XR-Transformer (Zhang et al.,, 2021), X-Transformer (Wei et al.,, 2019), XR-Linear (Yu et al.,, 2022), and ELIAS (Gupta et al.,, 2022) partition the label spaces into clusters. This is typically achieved by performing $k$-means clustering on the feature space. The training process involves training a cluster-level model to assign a cluster to a feature vector, followed by training a label-level model to assign labels within the cluster.

One-vs-all methods. One-vs-all (OVA) algorithms address extreme classification problems with $C$ labels by modeling them as $C$ independent binary classification problems. For each label, a classifier is trained to predict its presence. DiSMEC (Babbar and Schölkopf,, 2017) introduces a large-scale distributed framework to train linear OVA models, albeit at an expensive computational cost. ProXML (Babbar and Schölkopf,, 2019) mitigates the impact of data scarcity with adversarial perturbations. PD-Sparse (Yen et al.,, 2016) and PPD-Sparse (Yen et al., 2017a, ) propose optimization algorithms to exploit a sparsity assumption on labels and feature vectors.

Other methods. Beyond the above categories, DeepXML (Dahiya et al.,, 2021) uses a negative sampling procedure that shortlists $O(\log C)$ relevant labels during training and prediction. VM (Choromanska and Langford,, 2015) constructs trees with $\mathcal{O}(\log C)$ depth that have leaves with low label entropy. Based on the standard random forest training algorithm, FastXML (Prabhu and Varma,, 2014) proposes to directly optimize the Discounted Cumulative Gain to reduce the training cost. AnnexML (Tagami,, 2017) constructs $k$-nearest neighbor graph of the label vectors and attempts to reproduce the graph structure in a lower-dimension feature space.

Our theoretical contributions are expressed as excess risk bounds, which quantify how the excess risk associated to a surrogate loss relates to the excess risk for the 01 loss. Excess risk bounds for classification were developed by Zhang, (2004); Bartlett et al., (2006); Steinwart, (2007) and subsequently developed and extended by several authors. Ramaswamy and Agarwal, (2012) shows that one needs to minimize a convex surrogate loss defined on at least a $C-1$ dimension space to achieve consistency for the standard $C$-class classification problem, $i.e.$, any convex surrogate loss function operating on a dimension less than $C-1$ inevitably suffers an irreducible error. We draw insights from (Steinwart,, 2007) to establish a novel excess risk bound for the label embedding framework, quantifying this irreducible error.

From a different perspective, Ramaswamy et al., (2018) put forth a novel surrogate loss function for multiclass classification with an abstain option. This abstain option enables the classifier to opt-out from making predictions at a certain cost. Remarkably, their proposed methods not only demonstrate consistency but also effectively reduce the multiclass problems to $\lceil\log C\rceil$ binary classification problems by encoding the classes with their binary representations. In particular, the region in $\mathcal{X}$ that causes the irreducible error in our excess risk bound is abstained in Ramaswamy et al., (2018) to achieve lossless dimension reduction in the abstention setting.

We first introduce the notations. Let $\mathcal{X}$ denote the feature space and $\mathcal{Y}=\left\{1,\dots,C\right\}$ denote the label space where $C\in\mathbb{N}$. Let $(X,Y)$ be random variables in $\mathcal{X}\times\mathcal{Y}$, and let $P$ be the probability measure that governs $(X,Y)$. We use $P_{\mathcal{X}}$ to denote the marginal distribution of $P$ on $\mathcal{X}$.

To define the standard classification setting, denote the 0-1 loss $L_{01}:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}$ by $L_{01}\left(\hat{y},y\right)=\begin{cases}1,&\text{ if }y\neq\hat{y}\\ 0,&o.w.\end{cases}$. The risk of a classifier $h$ is $\mathbb{E}\left[L_{01}(h(X),Y)\right]$, and the goal of classification is to learn a classifier from training data whose risk is as close as possible to the Bayes risk $\min_{h\in\mathcal{H}}\mathbb{E}\left[L_{01}(h(X),Y)\right]$, where $\mathcal{H}=\left\{\text{measurable }h:\mathcal{X}\rightarrow\mathcal{Y}\right\}$ is the set of all measurable functions $\mathcal{X}$ to $\mathcal{Y}$.

We now describe an approach to classification based on label embedding, which represents labels as vectors in $n$ dimensional $\mathbb{C}^{n}$. In particular, let $G$ be an $n\times C$ matrix with unit norm columns, called the embedding matrix, having coherence $\lambda^{G}<1$. The columns of $G$ are denoted by $g_{1},g_{2},\dots,g_{C}$, and the column $g_{i}$ is used to embed the $i$-th label.

Given an embedding matrix $G$, the original $C$-class classification problem may be reduced to a multi-output regression problem, where the classification instance $(x,y)$ translates to the regression instance $(x,g_{y})$. Given training data $\{(x_{i},y_{i})\}$ for classification, we create training data $\{(x_{i},g_{y_{i}})\}$ for regression, and apply any algorithm for multi-output regression to learn a regression function $f:\mathcal{X}\to\mathbb{C}^{n}$.

At test time, given a test point $x$, a label $y$ is obtained by taking the nearest neighbor to $f(x)$ among the columns of $G$. In particular, define the decoding function $\beta^{G}:\mathbb{C}^{n}\rightarrow\mathcal{Y}$, $\beta^{G}(p)=\min\left\{\operatorname*{arg\,min}_{i\in\mathcal{Y}}\left\lVert p-g_{i}\right\rVert_{2}\right\}$, where $p$ is the output of a regression model. Then the label assigned to $x$ is $\beta^{G}(f(x))$. In the rare case where multiple nearest neighbors exist for $p$, this ambiguity is resolved by taking the label with smallest index.

Thus, label embedding searches over classifiers of the form $\beta^{G}\circ f$, where $f\in\mathcal{F}=\left\{\text{all measurable }f:\mathcal{X}\rightarrow\mathbb{C}^{n}\right\}$. Fortunately, according to the following result, no expressiveness is lost by considering classifiers of this form.

It follows that $\min_{f\in\mathcal{F}}\mathbb{E}_{P}\left[L_{01}(\beta^{G}(f(X)),Y)\right]$ is the Bayes risk for classification as defined earlier. This allows us to focus our attention on learning $f:\mathcal{X}\to\mathbb{C}^{n}$. Toward that end, we now formalize notions of loss and risk for the task of learning a multi-output function $f$ for multiclass classification via label embedding.

Using this notation, the target loss for learning is the loss function $L^{G}:\mathbb{C}^{n}\times\mathcal{Y}$ associated with embedding matrix $G$ defined by $L^{G}(p,y):=L_{01}(\beta^{G}(p),y)$. By Prop. 2, the $L^{G}$-risk of $f$ is the usual classification risk of the associated classifier $h=\beta^{G}\circ f$. Given $G$, we’d like to find an $f$ that minimizes $\mathcal{R}_{L^{G},P}(f)$, or in other words, an $f$ that makes the excess risk $\mathcal{R}_{L^{G},P}-\mathcal{R}_{L^{G},P}^{*}$ as small as possible.

While the target loss $L^{G}$ defines our learning goal, it is not practical as a training objective because of its discrete nature. Therefore, for learning purposes, Hsu et al., (2009); Akata et al., (2013); Yu et al., (2014) suggest a surrogate loss, namely, the squared distance between $f(x)$ and $g_{y}$. More precisely, for a given embedding matrix $G$, define $\ell^{G}:\mathbb{C}^{n}\times\mathcal{Y}\rightarrow\mathbb{R}$ as $\ell^{G}(p,y):=\frac{1}{2}\left\lVert p-g_{y}\right\rVert^{2}_{2}$. This surrogate allows us to learn $f$ by applying existing multi-output regression algorithms as we describe next. Thus, the label embedding learning problem is to learn $f$ with small surrogate excess risk. Our subsequent analysis will connect $\mathcal{R}_{L^{G},P}-\mathcal{R}_{L^{G},P}^{*}$ to $\mathcal{R}_{\ell^{G},P}-\mathcal{R}_{\ell^{G},P}^{*}$.

The theory presented below motivates the use of a $G$ with low coherence, and an $f$ with small surrogate risk $\mathcal{R}_{\ell^{G},P}$. In light of this theory, the problem statement just introduced leads to a natural meta-algorithm for label embedding. This meta-algorithm should not be considered novel as its essential ingredients have been previously introduced Akata et al., (2013); Rodríguez et al., (2018). Our contribution is the theory below, and the experimental assessment of the meta-alogrithm with low-coherence matrices for extreme multiclass classification.

Let the training dataset $\left\{\left(x_{i},y_{i}\right)\right\}_{i=1}^{N}$ be realizations of $\left(X,Y\right)$. Given an embedding matrix $G=\left[g_{1},g_{2},\dots,g_{C}\right]$, replace each label $y_{i}$ with its embedding vector $g_{y_{i}}$ to form the regression dataset $\left\{\left(x_{i},g_{y_{i}}\right)\right\}_{i=1}^{N}$. Next, train a regression model $f$ on the regression dataset. For example, this may be achieved by solving $\min_{f\in\mathcal{F}_{0}}\frac{1}{N}\sum_{i=1}^{N}\ell^{G}(f(x_{i}),y_{i}),$ where $\mathcal{F}_{0}\subset\mathcal{F}$ is some model class, such as a multilayer perceptron with $n$ nodes in the output layer.

$G$ can either be fixed or trained jointly with $f$. Our analysis is independent of model training, and thus applies to either case. Given a new data point $x$, to assign a label we search for the nearest embedding vector $g_{y}$ of $f(x)$ and annotate $x$ with the label $y$. The full meta-algorithm is presented in Alg. 1.

We present an excess risk bound, which relates the excess surrogate risk to the excess target risk. This bound justifies the use of the squared error surrogate, and also reveals a trade-off between the reduction in dimensionality (as reflected by $\lambda^{G}$) and the potential penalty in accuracy.

To state the bound, define the class posterior $\eta(x)=\left(\eta_{1}(x),\dots,\eta_{C}(x)\right)$ where $\eta_{i}(x)=P_{Y\mid X=x}(i)$. Define $d(x)=\max_{i}\eta_{i}(x)-\max_{i\notin\operatorname*{arg\,max}_{j}\eta_{j}(x)}\eta_{i}(x)$, which is a measure of “noise” at $x$. We discuss this quantity further after the main result, which we now state.

We begin by sketching the proof, and after the sketch offer a discussion of the bound. Full proofs and associated lemmas are provided in the Appendix. Before delving into the proof sketch, the concept of conditional risk is needed.

The conditional risk represents the expected value of a loss given the model output $p$ and a feature vector $x$. Note that $\mathcal{R}_{\mathcal{L},P}(f)=\mathbb{E}_{X\sim P_{\mathcal{X}}}C_{\mathcal{L},X}(f(X))$. For brevity, we introduce the notation $C_{1,x}(p)=C_{L^{G},x}(p)-C^{*}_{L^{G},x},C_{2,x}(p)=C_{\ell^{G},x}(p)-C^{*}_{\ell^{G},x}$.

As mentioned earlier, the goal of learning is to minimize the excess target risk $\mathcal{R}_{L^{G},P}(f)-\mathcal{R}^{*}_{L^{G},P}$. The theorem shows that this goal can be achieved up to the first (irreducible) term by minimizing the excess surrogate risk $\mathcal{R}_{\ell^{G},P}(f)-\mathcal{R}^{*}_{\ell^{G},P}$. The excess surrogate risk can be driven to zero by any consistent algorithm for multi-output regression with squared error loss.

The quantity $d(x)$ can be viewed as a measure of noise (inherent in the joint distribution of $(X,Y)$) at a point $x$. While $\max_{i}\eta_{i}(x)$ represents the probability of the most likely label occurring, $\max_{i\notin\operatorname*{arg\,max}_{j}\eta_{j}(x)}\eta_{i}(x)$ represents the probability of the second most likely label occurring, A large $d(x)$ implies that $\operatorname*{arg\,max}_{i}\eta_{i}(x)$ is, with high confidence, the correct prediction at $x$. In contrast, if $d(x)$ is small, our confidence in predicting $\operatorname*{arg\,max}_{i}\eta_{i}(x)$ is reduced, as the second most likely label has a similar probability of being correct.

As pointed out by Ramaswamy and Agarwal, (2012), any convex surrogate loss function operating on a dimension less than $C-1$ inevitably suffers an irreducible error, which is measured by the coherence of the embedding matrix $G,\lambda^{G}$, in the label embedding framework. From the proof outline, we can see that the model $f^{*}$ minimizing the $\ell^{G}$-risk $\mathcal{R}_{\ell^{G},P}(f)$ may potentially make a suboptimal prediction at point $x$ when $d(x)<\frac{2\lambda^{G}}{1+\lambda^{G}}$. Conversely, when $d(x)>\frac{2\lambda^{G}}{1+\lambda^{G}}$, $f^{*}$ will always make the optimal prediction at point $x$. Given a classification problem with $C$ classes, a larger embedding dimension $n$ will lead to a smaller coherence $\lambda^{G}$, making $d(x)>\frac{2\lambda^{G}}{1+\lambda^{G}}$ on a larger region in $\mathcal{X}$ at the cost of increasing computational complexity. On the other hand, by choosing a smaller $n$, $d(x)<\frac{2\lambda^{G}}{1+\lambda^{G}}$ on a larger region in $\mathcal{X}$, increasing the first term in Theorem 4. This interpretation highlights the balance between the benefits of dimensionality reduction and the potential impact on prediction accuracy, as a function of the coherence of the embedding matrix, $\lambda^{G}$, and the noisiness measure, $d(x)$.

While Theorem 4 holds universally (for all distributions $P$), by considering a specific subset of distributions, we can derive a more conventional form of the excess risk bound. As a direct consequence of Theorem 4, under the multiclass extension of the Massart noise condition (Massart and Nédélec,, 2006), which requires $d(X)>c$ with probability 1 for some $c$, the first and second terms in Theorem 4 vanish. In this case, we recover a conventional excess risk bound, where $\mathcal{R}_{L^{G},P}(f)-\mathcal{R}^{*}_{L^{G},P}$ tends to $0$ with $\mathcal{R}_{\ell^{G},P}(f)-\mathcal{R}^{*}_{\ell^{G},P}$. We now formalize this.

We conduct experiments on three large-scale datasets, DMOZ, LSHTC1, and ODP, which are extensively used for benchmarking extreme classification algorithms. The details of these datasets are provided in Table 1, with DMOZ and LSHTC1 available from (Yen et al.,, 2016), and ODP from (Medini et al.,, 2019). We adapt our method to fully connected neural networks, which are implemented using Pytorch, with a 2-layer fully connected neural network used for the LSHTC1 and DMOZ datasets and a 4-layer fully connected neural network for the ODP dataset. We tune the hyperparameters for all models on a held-out dataset. For our embedding matrix, we employ the Rademacher matrix, the Gaussian matrix, the complex Gaussian matrix, and the matrix proposed by (Nelson and Temlyakov,, 2011), which has demonstrated superior empirical performance in our tests. For the competing methods, we use the hyperparameters as suggested in their respective papers or accompanying code.

We compare our method against the following state-of-the-art methods:

• •

  PD-Sparse (Yen et al.,, 2016): an efficient solver designed to exploit the sparsity in extreme classification.

• •

  PPD-Sparse (Yen et al., 2017a, ): a multi-process extension of PD-Sparse (Yen et al.,, 2016).

• •

  Parabel (Prabhu et al.,, 2018): a tree-based method which builds a label-hierarchy.

• •

  AnnexML (Tagami,, 2017): a method which constructs a $k$-nearest neighbor graph of the label vectors and attempts to reproduce the graph structure from a lower-dimension feature space.

• •

  MLP (CE Loss): Standard multilayer perceptron classifier with cross-entropy loss.

• •

  MLP (SE Loss): Standard multilayer perceptron classifier with squared error loss.

We experiment with the following types of embedding matrices:

• •

  Rademacher: entries are sampled $i.i.d.$ from a uniform distribution on $\left[\frac{1}{\sqrt{n}},-\frac{1}{\sqrt{n}}\right]$.

• •

  Gaussian: entries are sampled $i.i.d.$ from $\mathcal{N}(0,\frac{1}{n})$. We normalize each column to have unit norm.

• •

  Complex Gaussian: the real and imaginary parts of each entry are sampled $i.i.d.$ from $\mathcal{N}(0,\frac{1}{2n})$. We normalize each column to have unit norm.

• •

  Nelson (Nelson and Temlyakov,, 2011): a deterministic construction of low-coherence complex matrices. If $r$ is an integer, $n>r$ is a prime number, and $n^{r}\geq C$, then the coherence of the constructed matrix is at most $\frac{r-1}{\sqrt{n}}$. We choose $r=2$ in experiments.

While our theoretical framework is adaptable to any form of embedding, whether trained, fixed, or derived from auxiliary information, we focus on fixed embeddings in our empirical studies. This choice stems from the absence of a standardized approach to train or construct embeddings with auxiliary data. By centering on fixed embeddings, we ensure a controlled evaluation, minimizing confounding factors and emphasizing the role of coherence of the embeddings.

All neural network training is performed on a single NVIDIA A40 GPU with 48GB of memory. For our neural networks models, we explore different embedding dimensions and provide figures showing the relationship between the coherence of the embedding matrix and the accuracy. The full details of the experiments are presented in the appendix.

The experimental results presented in Tables 2, 3, and 4 highlight the superior performance of our proposed method across various datasets. In Tables 2, 3, and 4, the first column is the name of the method or embedding type, the second column is the embedding dimension for label embedding methods, and the third column is the mean and standard deviation of accuracy in 5 randomized repetitions. We highlight the best-performing method for each dataset.

We plot the accuracies as the coherence of the embedding matrix decreases in Figures 1, 2, and 3 for the LSHTC1, DMOZ, and ODP datasets, respectively. Figures 1, 2, and 3 demonstrate a negative correlation between the coherence of the embedding matrix and the accuracy, confirming our theoretical analysis.

PD-Sparse (Yen et al.,, 2016) and PPD-Sparse (Yen et al., 2017b, ) are among the most computationally efficient methods for training for extreme classification, to the best of our knowledge. PD-Sparse and PPD-Sparse both solve an elastic net efficiently leveraging the sparsity in extreme classification. To allow for a fair comparison, we also use the Rademacher embedding with an elastic net, which is a linear model regularized by both $\ell_{1}$ and $\ell_{2}$ penalties. To compare the computational efficiency, we consistently set the embedding dimension to $n=360$. In our distributed implementation, each node independently solves a subset of elastic nets with real-value output, effectively spreading out the computation. As shown in the table, the Rademacher embedding not only trains faster but also achieves higher accuracy. We train the PD-Sparse method and the Single-Node Rademacher embedding on Intel Xeon Gold 6154 processors, equipped with 36 cores and 180GB of memory. Our distributed approach and the PPD-Sparse method — also implemented in a distributed fashion — are trained across 10 CPU nodes, harnessing 360 cores and 1.8TB of memory in total. In Table 5, we compare Rademacher embedding with PD-sparse and PPD-sparse. The Rademacher embedding clearly outperforms PD-sparse and PPD-sparse in both runtime and accuracy.