text:
\section{Introduction}
Extreme multi-label text classification (XMTC) is the task of tagging documents with relevant labels in a very large and often skewed candidate space. It has a wide range of applications, such as assigning subject topics to news or Wikipedia articles, tagging keywords for online shopping items, classifying industrial products for tax purposes, and so on.

\begin{figure}[th!]
     \centering
     \includegraphics[width=\linewidth]{img/lin_res.pdf}
     \caption{The classification performance of X-Transformer and DEPL (ours) on the Wiki10-31K dataset. The curves show the macro-averaged $F1@19$ scores of each system over the label bins (with 100 labels per bin).}
     \label{fig:data_dist}
\end{figure}

The most difficult part in solving the XMTC problem is to train classification models effectively for the rare labels in the long tail of highly skewed distributions, which suffers severely from the lack of sufficient training instances.
Efforts addressing this challenge by the text classification community include hierarchical regularization methods for large margin classifiers \cite{gopal2013recursive}, Bayesian modeling of graphical or hierarchical dependencies among labels \cite{gopal2010multilabel, gopal2012bayesian}, clustering-based divide-and-conquer  strategies in resent neural classifiers \cite{chang2020taming, khandagale2019bonsai, prabhu2018parabel}, and so on. Despite the remarkable progresses made so far, and the problem is still very far from being well solved.
\Figref{fig:data_dist} shows the performance of X-Transformer \cite{chang2020taming}, one of the
state-of-the-art (SOTA) XMTC models with the best published result so far on the  Wiki10-31k benchmark dataset (with over 30,000 unique labels). The horizontal axis in this figure is the ranks of the labels sorted from rare to common, and the vertical axis is the text classification performance measured in macro-averaged $F1@19$ (higher the better) for binned labels (100 labels per bin).  The blue curve is the result of X-Transformer, which has the scores close to $0$ (worst possible score) for nearly half of the total labels.
In other words, SOTA methods in XMTC still perform poorly in tail label prediction. We should point out that such poor performance of XMTC classifiers on tail labels has been largely overlooked in the recent literature, because benchmark evaluations of SOTA methods have typically used the metrics that are dominated by the system's performance on common labels, such as the micro-averaged precision at top-k (P@k).
As a proper choice for evaluation of tail label prediction in \figref{fig:data_dist},  macro-averaged $F1@k$ is used, which gives the performance on each label an equal weight in the average. The red curve in the figure is the result of our new approach, being introduced the next.

In this paper, we seek solutions for tail label prediction from a new angle: we introduce a novel framework, namely the Dual Encoder with Pseudo Label (\textsc{DEPL}). It treats each input document as a query and uses a neural network model to retrieve relevant labels from the candidate space based on the textual descriptions of the labels.  The underlying assumption is, if the label descriptions are highly informative for text-based matching, then the retrieval system should be able to find relevant labels for input documents. Such a system would be particularly helpful for tail label prediction as the retrieval effectiveness does not necessarily rely on the availability of a large number of training instances, which what the tail labels are lacking.

Now the key question is, how can we get a highly informative description for each label without human annotation?  In reality, class names are often available but they are typically one or two words, which cannot be sufficient for retrieval-based label prediction. Our answer is to use a relatively simple trained classifier, e.g., a linear support vector machine (SVM), to automatically generate an informative description for each label, which we call the pseudo description of the label.   The reason for us to choose a traditional classifier like linear SVM instead of a more modern neural model for label descriptions generation is that we want to better leverage the unsupervised statistics about word usage such as TF (term frequency within a document) and IDF (the inverse document frequencies within a document collection). Such unsupervised word features would be particularly helpful to alleviate the difficulty in classifier training under extreme data scarce conditions, and are easy and natural for traditional classifiers like SVM to leverage. The result of our approach (\textsc{DEPL}) is shown as the red curve in Figure 1, which significantly outperforms the blue curve of X-Transformer not only in the tail-label region but also in all other regions.  We also observed similar improvements by \textsc{DEPL } over strong baselines on other benchmark datasets (see \secref{sec:evaluation}).

Our main contributions can be summarized as the following:
\begin{enumerate}
\item We formulate the XMTC task as a neural retrieval problem, which enables us to alleviate the difficulty in tail label prediction by matching documents against label descriptions with advanced neural retrieval techniques.
\item We enhance the retrieval system with pseudo label descriptions generated by a BoW classifier, which is proven to be highly effective for improving tail label prediction under severe data scarce conditions.
\item Our proposed method significantly and consistently outperforms strong baselines on multiple challenging benchmark datasets. Ablation tests provide in-depth analysis on different settings in our framework.
A theoretical analysis for relating the BoW and neural models w.r.t. performance lower bound is also provided.
\end{enumerate}

\section{Introduction}
Extreme multi-label text classification (XMTC) is the task of tagging each document with the relevant category labels in a very large predefined label space, in which the number of categories can be from a few thousands to more than a million. It has a wide range of potential applications, such as assigning subject topics to articles, tagging keywords for online shopping recommendation, classifying products for tax purposes, and so on.

\begin{figure}[th!]
     \centering
     \includegraphics[width=\linewidth]{img/data_dist.png}
     \caption{In the skewed distribution of XMTC, tail labels with less than $10$ training instances cover a large portion, if not the majority, of the label space, but their training instances cover a only small percentage of the training set.}
     \label{fig:data_dist}
\end{figure}

The label frequencies in XMTC often follow a power law. That is, a small portion of the labels have a dominating number of training instances (namely head labels), whereas the majority of the labels have very few training instances (namely as tail labels), as illustrated in \figref{fig:data_dist}. The severe data sparse issue with the tail labels poses a harder optimization problem for XMTC than the  classification tasks where the number of categories are much smaller and the label distributions are not as skewed.

Traditional classifiers typically use a bag-of-words (BoW) vector to represent each document, whose dimension is the the entire document vocabulary.  Each word in the document is treated as an one-hot vector weighted by the tf-idf~\cite{kuang2010improvement} value. Summing over the one-hot vectors of the within-document words yields the BoW representation of the document. Since the BoW vectors of documents are typically high-dimensional and very sparse, we call the classification models based on such representation as BoW classifiers or \textit{sparse classifiers}.
Models like DiSMEC~\cite{babbar2017dismec}, ProXML~\cite{babbar2019proxml} and PPDSparse~\cite{yen2017ppdsparse} are recent examples of this kind.
BoW classifiers enjoy their simplicity and effectiveness in utilizing local and global frequencies of words in unlabeled data, such as TF (the within-document frequency of each word) and IDF (the within-corpus inverted document frequency of each word), which is arguably a strength in addressing the severe data sparse issue in tail label prediction (see the rest of this paper for deeper insights).  As for their weaknesses or limitations, the word independence assumption in the BoW presentations is clearly unjustified, as word location, ordering and semantic dependencies in context are ignored.

In contrast, recent neural classifiers use
neural networks to extract latent features with learnable parameters, and obtain a lower dimensional dense vector as document embedding. Typically, neural classifiers learn the latent label embeddings jointly with the document embeddings in an end-to-end training process. Since the learned document and label representations are both dense vectors, we call such models \textit{dense classifiers} in this paper.
Recently, large pre-trained Transformer-based models such as BERT~\cite{devlin2018bert} and XLNet~\cite{yang2019xlnet} have been adapted to XMTC problems to extract expressive contextualized features. Examples include  X-Transformer~\cite{chang2020taming}, APLC-XLNet~\cite{ye2020pretrained} and LightXML~\cite{jiang2021lightxml}, which achieved state-of-the-art (SOTA) performance on several benchmark datasets for XMTC evaluation. Despite the desirable expressiveness of such dense classifiers, how much does their successes depend on the availability of a large quantity of labeled training data, and how much does their performance suffers under severe data sparse conditions?  These questions have not investigated in sufficient depth so far. Furthermore, the dense classifiers do not make explicit use of the unsupervised statistics like tf-idf term weights, which maybe a potential weakness.

This paper aims to improve the prediction power of XMTC classifiers especially with respect to tail label prediction. Specifically, we propose a framework that combines the strengths of both BoW sparse classifiers and neural dense classifiers. The key idea is 1) using a trained BoW model to select keywords for each label, which yields the pseudo label description, and 2) training a neural model based on the training pairs of input documents and the pseudo descriptions.  Step 1 leverages the strength of Bow models in using unsupervised TF-IDF statistics, which would be particularly important under severe data sparse conditions (see \secref{sec:rethinking} for details) , and Step 2 takes advantage of a neural encoder in learning expressive representations (embeddings) of documents and labels. Our experiments show significant improvements of the proposed approach over other strong baseline methods on benchmark datasets, especially on tail label prediction. A theoretical analysis is also provided for relating BoW and neural models w.r.t. performance lower bound.

\section{Conclusion}
In this paper, we propose a novel neural retrieval framework (DEPL) for the open challenge of tail-label prediction in XMTC.  By formulating the problem as to  capture the semantic mapping between input documents and system-enhanced label descriptions, DEPL combines the strengths of neural embedding based retrieval and the effectiveness of a large-marge BoW classifier in generating informative label descriptions under severe data sparse conditions.
Our extensive experiments on very large benchmark datasets show significant performance improvements by DEPL over strong baseline methods, especially in tail label description.

\section{Appendix}
We include the assumptions and proofs of Theorem \ref{th:main}.
\label{sec:proof}

\paragraph{Assumptions}
Similar to \citet{luan2020sparse}, we treat neural embedding as fixed dense vector ${\bm{E}} \in \mathbb{R}^{d\times v}$ with each entry sampled from a random Gaussian $N(0, d^{-1/2})$. $\phi_n({\bm{x}}) = {\bm{E}}\phi_t({\bm{x}})$ is weighted average of word embeddings by the sparse vector representation of text. According to the \textit{Johnson-Lindenstrauss (JL) Lemma}~\citep{johnson1984extensions, ben2002limitations}, even if the entries of ${\bm{E}}$ are sampled from a random normal distribution, with large probability, $\langle \phi_t({\bm{x}}), {\bm{v}} \rangle$ and $\langle {\bm{E}}\phi_t({\bm{x}}), {\bm{E}}{\bm{v}} \rangle$ are close.

\begin{lemma}
\label{lemma:keyword}
Let ${\bm{v}}$ be the $\delta$-bounded keyword-selected label embedding of ${\bm{w}}$. For two labels $p, n$, the error margins satisfy:
$$
   | \mu( \phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n )
   - \mu( \phi_t({\bm{x}}), {\bm{v}}_p, {\bm{v}}_n ) | \le \delta
$$
\end{lemma}
\begin{proof}
By the definition of $\delta$-bounded keywords,
\begin{align}
    & \langle \phi_t({\bm{x}}), {\bm{w}}_p \rangle - \delta \le \langle \phi_t({\bm{x}}), {\bm{v}}_p \rangle \le \langle \phi_t({\bm{x}}), {\bm{w}}_p \rangle \label{eq:l1_1} \\
    & - \langle \phi_t({\bm{x}}), {\bm{w}}_n \rangle \le -\langle \phi_t({\bm{x}}), {\bm{v}}_n \rangle \le - \langle \phi_t({\bm{x}}), {\bm{w}}_n \rangle + \delta \label{eq:l1_2}
\end{align}
Adding \eqref{eq:l1_1} and \eqref{eq:l1_2} finishes the proof:
\begin{equation}
   \langle \phi_t({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle - \delta
   \le \langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_n \rangle
   \le  \langle \phi_t({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle + \delta
\end{equation}
\end{proof}

\begin{lemma}
\label{lemma:main}
Let $\phi_t({\bm{x}})$ and $\phi_n({\bm{x}})$ be the sparse and dense (dimension $d$) document feature, ${\bm{w}}_l$ be the label embedding and  ${\bm{z}}_l$ be the $\delta$-bounded keywords. Let $p$ be a positive label and $n$ be a negative label ranked below $p$ be the sparse classifier. The error margin is $\epsilon=\mu(\phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n)$. An error ${\mathcal{E}}$ of neural classification occurs when $\mu(\phi_n({\bm{x}}), \phi_n({\bm{z}}_p), \phi_n({\bm{z}}_n) ) \le 0$. The probability $P({\mathcal{E}}) \le 4 \exp (-\frac{(\epsilon - \delta)^2d}{50})$.
\end{lemma}

\begin{proof}
By the JL Lemma \citep{ ben2002limitations}:
For any two vectors ${\bm{a}}, {\bm{b}} \in {\mathbb{R}}^{v}$, let ${\bm{E}} \in {\mathbb{R}}^{d \times v}$ be a random matrix such that the entries are sampled from a random Gaussian. Then for every constant $\gamma > 0$:
\begin{equation}
 P\left(|\langle {\bm{E}} {\bm{a}}, {\bm{E}} {\bm{b}} \rangle - \langle {\bm{a}}, {\bm{b}} \rangle| \geq \frac{\gamma}{2}\left(\| {\bm{a}} \|^{2}+\|{\bm{b}}\|^{2}\right)\right)
\leq  4 \exp \left(-\frac{\gamma^2d}{8}\right)
\end{equation}
Let $\gamma = \frac{2}{5}(\epsilon - \delta)$, ${\bm{a}} = \phi_t({\bm{x}})$ and ${\bm{b}} = {\bm{v}}_p - {\bm{v}}_n$. Since $\| {\bm{a}} \|_2 = 1 $ and $\| {\bm{b}} \|_2 \le (\|{\bm{v}}_p \|_2 + \|{\bm{v}}_n \|_2)^2 \le 4$, the JL Lemma gives
\begin{align}
    &P\left(
    |\langle {\bm{E}} \phi_t({\bm{x}}), {\bm{E}} ({\bm{v}}_p - {\bm{v}}_n) \rangle - \langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_n \rangle| \geq \epsilon - \delta  \right) \label{eq:jl} \\
    &\le 4 \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{align}
To complete the proof, we need to show $P({\mathcal{E}}) \le Eq. \ref{eq:jl}$:
\begin{alignat}{3}
{\mathcal{E}}
&\implies \quad    & | \langle {\bm{E}} \phi_t({\bm{x}}), {\bm{E}} ({\bm{v}}_p - {\bm{v}}_n) \rangle - \langle \phi_t({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle | &\ge \epsilon \\
&\implies \quad    &| \langle {\bm{E}} \phi_t({\bm{x}}), {\bm{E}} ({\bm{v}}_p - {\bm{v}}_n) \rangle - \langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_n \rangle | &\ge \epsilon - \delta \label{eq:l2_2}
\end{alignat}
where the \eqref{eq:l2_2} is derived by Lemma \ref{lemma:keyword}:
\begin{align}
&| \langle {\bm{E}} \phi_t({\bm{x}}), {\bm{E}} ({\bm{v}}_p - {\bm{v}}_n) \rangle - \langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_n \rangle | \\
\ge &| \langle {\bm{E}} \phi_t({\bm{x}}), {\bm{E}} ({\bm{v}}_p - {\bm{v}}_n) \rangle
- \langle \phi_t({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle |
- \\
&|\langle \phi_t({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle
- \langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_n \rangle | \\
\ge &\epsilon - \delta
\end{align}
Therefore $P({\mathcal{E}}) \le Eq. \ref{eq:jl}$, which completes the proof.
\end{proof}

\noindent Proof of \textbf{Theorem} \ref{th:main}

\begin{proof}
The Lemma 2 shows that
\begin{equation}
    P({\mathcal{E}}_i ) \le 4 \exp (-\frac{(\epsilon_i - \delta)^2d}{50}) \le 4 \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{equation}
By an union bound on the error events $\{ {\mathcal{E}}_1, {\mathcal{E}}_2, \ldots, {\mathcal{E}}_{M_p} \}$,
\begin{align}
     P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p}) &\le \sum_{i=1}^{M_p} 4\exp(-\frac{(\epsilon_i - \delta)^2d}{50}) \\
     &= 4 {M_p} \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{align}
\end{proof}
When $(\epsilon - \delta)^2 \ge 10 \sqrt{\frac{\log {M_p}}{d}}$, we have $\exp (-\frac{(\epsilon - \delta)^2d}{50}) \le \frac{1}{4{M_p}^2}$ and therefore $P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p}) \le \frac{1}{{M_p}}$.

\section{Background}

\subsection{Preliminary}

Let $\mathcal{D}=\{\left(\mathbf{x}_i, \mathbf{y}_i\right)_{i=1}^{N_{\text{train}}} \}$ be the training data where $\mathbf{x}_i$ is the input text and $\mathbf{y}_i\in\{-1, +1\}^L$ is the ground truth label list.
The XMTC method can be formulated as learning a scoring function $f(\mathbf{x}, l) \in {\mathbb{R}}$ defined on an input and candidate label pair $({\bm{x}}, l)$. The score should be higher for relevant labels than irrelevant labels.
The objective function of a classification model is defined as:
\begin{equation*}
        \min_{f} \quad \frac{1}{N_{\text{train}} L} \sum_{i=1}^{N_{\text{train}}} \sum_{l=1}^{L} \mathcal{L}(y_{i l}, f(\mathbf{x}_i, l))
\end{equation*}
where $\mathcal{L}(\cdot, \cdot)$ is an instance-wise loss, such as a hinge loss in a Linear SVM or a sigmoid loss in the final layer of a neural network.

In the evaluation, since multi-labels can be relevant for an input document $\mathbf{x}$, a typical way is to measure the quality of a top-k ranked list of the predicted label: \begin{equation}
    \operatorname{Top-k}([f({\bm{x}}, 1), \ldots, f({\bm{x}}, L)])
\end{equation}

\subsection{Tf-idf+SVM vs. Dense Neural Model}
\noindent \textbf{Tf-idf+SVM} The one-vs-all linear SVM model is a simple realization of $f(\mathbf{x}, l)$:
\begin{equation*}
    f({\bm{x}}, l) = \langle \phi_t({\bm{x}}), {\bm{w}}_l \rangle
\end{equation*}
where $\phi_{\text{t}}({\bm{x}}) \in {\mathbb{R}}^{v}$ converts each text input into the tf-idf feature with vocabulary size of $v$, and ${\bm{w}}_l \in \mathbb{R}^v$ is the learned parameter of linear classifier for label $l$. The tf-idf feature uses the human defined heuristics to reflect the distributed importance of each word in the training corpus.

The document-vector representation-based methods (\textit{doc-vec}) encodes the raw text into a dense vector representation with neural networks as $\phi_n({\bm{x}})$.
\begin{equation}
    f({\bm{x}}, l) = \langle \phi_n({\bm{x}}), {\bm{u}}_l \rangle
\end{equation}
where $\phi_n({\bm{x}}) \in {\mathbb{R}}^{d}$ is a $d$ dimensional dense feature usually obtained by the deep transformer models such as BERT~\citep{devlin2018bert} or XLNet~\citep{yang2019xlnet}.
${\bm{u}}_l$ represents the learned parameter of a linear classifier for label $l$, which is typically optimized by the logistic regression objective $\mathcal{L}_{\mathrm{logistic}}$. We use ${\bm{u}}_l$ to distinguish from ${\bm{w}}_l$ because ${\bm{u}}_l \in {\mathbb{R}}^d$ is a compressed dense vector while ${\bm{w}}_l \in {\mathbb{R}}^v$ is sparse ($d \ll v$).

The most representative deep Transformer-based models tailored for the XMTC task are  X-transformer~\cite{chang2020taming}, APLC-XLNet~\cite{ye2020pretrained} and LightXML~\cite{jiang2021lightxml}, which are discussed in Appendix~\ref{sec:append_experiment}.

\section{Experiments}
\label{sec:experiment}

\begin{table*}[t!]
    \small
    \centering
    \begin{tabular}{l|cccccccc}
    \toprule
    Dataset & $N_{train}$ & $N_{test}$ & $F$ & $\bar{L}_d$ & $L$ & $p_{\text{tail}}^l$ & $p_{\text{tail}}^d$ \\
    \midrule
    EURLex-4K & 15,539 &  3,809 & 34,932 & 5.30 & 3,956 & 63.48\% & 9.50\% \\
    Wiki10-31K & 14,146 & 6,616 & 189,795 & 18.64 &  30,938 & 88.65\% & 27.06\%  \\
    AmazonCat-13K & 1,186,239 & 306,782 & 200,000 & 5.04 & 13,330 & 29.53\% & 0.27\% \\
    \bottomrule
    \end{tabular}
    \caption{$N_{\text{train}}$ and $N_{\text{test}}$ are the number of training and testing instances respectively. $F$ is the tf-idf feature size. $\bar{L}_d$ is the average number of labels per document. $L$ is the number of labels. For tail labels with $1\sim 9$ training instances, $p_{\text{tail}}^l$ is percentage of tail labels and $p_{\text{tail}}^d$ is the percentage of training instances covered by the tail labels. \label{tab:dataset}}
\end{table*}

\begin{table*}[ht!]
    \centering
    \begin{tabular}{c|ccc|ccc|ccc}
    \toprule
    \multicolumn{1}{c}{} & \multicolumn{3}{c}{EUR-Lex} &  \multicolumn{3}{c}{Wiki10-31K} & \multicolumn{3}{c}{AmazonCat-13K} \\
    \midrule
    Methods & P@1 & P@3 & P@5 & P@1 & P@3 & P@5 & P@1 & P@3 & P@5\\
    \midrule
    DisMEC  &  83.21 & 70.39 & 58.73 & 84.13 & 74.72 & 65.94 & 93.81 & 79.08 & 64.06 \\
    PfastreXML & 73.14 & 60.16 & 50.54 &  83.57 & 68.61 & 59.10 & 91.75 & 77.97 & 63.68 \\
    Parabel & 82.12 & 68.91 & 57.89 & 84.19 & 72.46 & 63.37 & 93.02 & 79.14 & 64.51 \\
    Bonsai & 82.30 & 69.55 & 58.35 &  84.52 & 73.76 & 64.69 &  92.98 & 79.13 & 64.46 \\
    \midrule
    AttentionXML & 85.12 & 72.80 & 61.01  & 86.46 & 77.22 & 67.98  & 95.53 & 82.03 & 67.00 \\
    X-Transformer & 85.46 & 72.87 & 60.79 & 87.12 & 76.51 & 66.69 & 95.75 & 82.46 & 67.22 \\
    BERT-APLC & 85.54 & 72.68 & 60.59 & 88.54 & 77.21 & 67.43 & 94.49 & 79.74 & 64.46\\
    XLNet-APLC & 86.83 & 74.34 & 61.94 & 88.99 & 78.79 & 69.79 & 94.56 & 79.78 & 64.59\\
    LightXML & 86.12 & 73.87 & 61.67 & 87.39 & 77.02 & 68.21 & 94.61 & 79.83 & 64.45\\
    \midrule
    tf-idf+SVM (ours)  & 83.44 & 70.62 & 59.08 & 84.61 & 74.64 & 65.89 & 93.20 & 78.89 & 64.14 \\
    BERT (ours) & 84.72 & 71.66 & 59.12 & 87.60 & 76.74 & 67.03 & 94.26 & 79.63 & 64.39 \\
KDE & 86.13 & 73.82 & 62.22 & 88.52 & 78.13 & 68.98 &  96.13 & \bf 82.70 & \bf 67.52 \\
KDE+SVM & \bf 87.98 & \bf 75.81 & \bf 63.62  & \bf 89.10 & \bf 80.24 & \bf 70.49 & \bf 96.25 & 81.90 & 65.20 \\
    \bottomrule
    \end{tabular}
    \caption{Comparisons between \textsc{DEPL } and the SOTA sparse and dense classifiers. The results are evaluated with the micro-averaging P@5 metrics, with highest values in bold. We report our baseline sparse (tf-idf+SVM) and dense (BERT) classifiers with KDE and KDE+SVM (average of KDE and SVM predicted score).}
    \label{tab:micro_all}
\end{table*}

\subsection{Experimental Setting}
\paragraph{Datasets}
We conduct our experiments on $3$ benchmark datasets: EURLex-4K~\citep{10.1007/978-3-540-87481-2_4}, Wiki10-31K~\citep{zubiaga2012enhancing} and AmazonCat-13K~\citep{10.1145/2507157.2507163}.
The statistics of the datasets are shown in Table~\ref{tab:dataset}.
For the tail label evaluation, we consider the labels with $1 \sim 9$ training instances, because we assume the absolute number of training instance reflects the difficulty of optimization across datasets. The tail labels covers $63.48\%$, $88.65\%$ and $30\%$ of training labels for the $3$ datasets respectively.
We obtain the datasets from the Extreme classification Repository\footnote{\url{http://manikvarma.org/downloads/XC/XMLRepository.html}} and a unstemmed version of EURLex-4K from the APLC-XLNet github\footnote{\url{https://github.com/huiyegit/APLC_XLNet.git}}.

\paragraph{Implementation Details} For the sparse model, since the public available BoW feature doesn't have a vocabulary dictionary, we generate the tf-idf feature by ourselves. We tokenize and lemmatize the raw text with the Spacy~\cite{spacy2} library and extract the tf-idf feature with the Sklearn~\cite{scikit-learn} library, with unigram whose idf is $>= 2$ and $<= 70\%$. For the dense model, we fine-tune a $12$ layer BERT-base model with different learning rates for the BERT encoder, BERT pooler and the classifier. The learning rates are $(1e-5$, $1e-4$, $1e-3)$ for Wiki10-31K and $(5e-5$, $1e-4$, $2e-3)$ for the rest datasets. We used learning rate $1e-5$ for fine-tuning the \textsc{DEPL } model. For the pseudo label descriptions, we concatenate the provided label description with the generated the top $20$ keywords. The final length is truncated up to $32$ after BERT tokenization.

\paragraph{Evaluation Metrics}
We use the micro-averaging $P@k$ metric to evaluate the overall system performance and the macro-averaging $F1@k$ metric to evaluate the tail label prediction, because both precision and recall are important for tail label predictions (and $F1@k$ is a harmonic average of both).

\noindent \textbf{micro-averaging P@k:}
The micro-averaging P@k metric is widely used to evaluate a ranked list of predicted labels:
\begin{equation}
    P@k = \frac{1}{k} \sum_{i=1}^{k} \mathbbm{1}_{{\bm{y}}_i^+}(p_i)
\end{equation}
where  $p_i$ is the $i$-th label in the predicted ranked list ${\bm{p}}$ and $\mathbbm{1}_{{\bm{y}}_i^+}$ is the indicator function. The metric score is averaged over all the test instances.

\noindent \textbf{macro-averaging F1@k:}
The $F1$ metric is a harmonic average of prediction (P) and recall (R):
\begin{equation}
    \operatorname{F1} = 2 \frac{P \cdot R }{P + R }
\end{equation}
The precision and recall for a predicted ranked list ${\bm{p}}$ are computed by $\mathrm{P}= \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}}, \mathrm{R}=\frac{ \mathrm{TP}}{ \mathrm{TP} + \mathrm{FN}}$ according to the confusion matrix in \tblref{tab:confusion_matrix}.
\begin{table}[h!]
    \centering
    \setlength{\tabcolsep}{4pt}
    \small
    \begin{tabular}{c|cc}
    & $l$ in ${\bm{y}}_i$ & $l$ not in ${\bm{y}}_i$ \\
    \hline
    $l$ in ${\bm{p}}_i$ & True Positive($\mathrm{TP}_l^i$) & False Positive($\mathrm{FP}_l^i$) \\
    $l$ not in ${\bm{p}}_i$ & False Negative($\mathrm{FN}_l^i$) & True Negative($\mathrm{TN}_l^i$) \\
    \end{tabular}
    \caption{Confusion Matrix for instance $i$ and label $l$ given the ranked list ${\bm{p}}_i$.}
    \vspace{-1.0em}
    \label{tab:confusion_matrix}
\end{table}

Given $N_{\text{test}}$ instances and $L$ labels, the macro-average computes the scores on individual category first ($\mathrm{F1}_l$), and then take an average over all the categories ($\mathrm{F1} = \frac{1}{|{\mathbb{L}}|}\sum_{i \in {\mathbb{L}}} \mathrm{F1}_l$), which reflects label level performance of the methods.

For micro-averaging P@k, we choose $k=1,3,5$ the same as in other works. For macro-averaging F1@k, we choose $k=19$ for Wiki10-31K because it has an average of $18.64$ labels and $k=5$ for the rest datasets.

\paragraph{Baselines}
Our method is compared with the state-of-the-art baselines including both the sparse and dense classifiers. Specifically, DisMEC~\cite{babbar2017dismec}, PfastreXML~\cite{jain2016extreme}, Parabel~\cite{prabhu2018parabel}, Bonsai~\cite{khandagale2019bonsai} belong to the sparse classifiers, and X-Transformer~\cite{chang2020taming}, APLC-XLNet~\cite{ye2020pretrained} and LightXML~\cite{jiang2021lightxml}, AttentionXML~\cite{you2018attentionxml} belong to the dense classifier. X-Transformer, LightXML, and APLC-XLNet employ pre-trained Transformers to encode a document into a fixed embedding. We report the single model performance (chosen from their papers) with BERT-large for X-Transformer, BERT-base for LightXML and XLNet-base for APLC-XLNet. The AttentionXML utitizes label-word attention to generate label-aware word embedding instead of a fix document representation. We provide an additional linear SVM model with our extracted tf-idf features as a sparse baseline, and BERT-base classifier as a dense baseline.

\subsection{Experimental Results and Discussions}
The performance of model evaluated on the micro-averaging P@5 metric is reported in \tblref{tab:micro_all}.

\noindent \textbf{Sparse and dense classifiers:} The sparse classifiers (first panel) generally underperform the dense models (second panel) under the micro-averaging evaluation metric. Our implementation of Linear SVM model and BERT model achieve comparable result with the sparse and dense classifiers respectively, except that the AttentionXML and X-Transformer achieve better result in Amazoncat-13K. The reason could be that the Amazoncat-13K product categorization relies more on the lexicon matching features, which gives the two methods performance gains.

\noindent \textbf{\textsc{DEPL}:} Our KDE model is fine-tuned on top of the BERT model with the pseudo label descriptions generated from the SVM model. As shown in the result, \textsc{DEPL } has additional gains on both of the classifiers, indicating \textsc{DEPL } can: 1) leverage the keyword semantic from sparse model for better generalization, 2) alleviate the difficult of optimization of neural model with scarce data by providing label side information. The KDE model outperforms the baseline models on the Amazoncat-13K dataset, and the KDE+SVM (average of KDE and sparse classifier scores) performs the best on the other two datasets.

\begin{figure}[th!]
     \centering
     \includegraphics[width=\linewidth]{img/tail_label.png}
     \caption{The evaluation of tail label prediction for a dense classifier base (BERT) and our proposed \textsc{DEPL } with different settings. The metric is  macro-averaging F1@k, where $k=19$ for Wiki10-31K and $k=5$ for the other datasets. The figure shows the relative improvement to the SVM baseline with $*$ indicating the significance for $p<0.01$.}
     \label{fig:macro_tail}
\end{figure}
\subsection{Tail Label Evaluation}
Previously, we observe that the pre-trained Transformer-based models underperform the sparse classifier (Linear SVM baseline) on tail label prediction. In this section, we want to test the ability of \textsc{DEPL } to generalize over the sparse classifier with the generated pseudo label description for tail label prediction. The experimental results are shown in \figref{fig:macro_tail}, where we report the relative performance of the models under investigation with respect to the sparse classifier. Specifically, we include the dense classifier (BERT) without any label side information as a baseline, which underperforms the SVM on all of the datasets.

\noindent \textbf{Only Provided Label Text} We fine-tune \textsc{DEPL } with only the provided label text, denoted as \textsc{DEPL }+label. The model outperforms the sparse classifier on the EURLex-4K and Amazoncat-13K dataset, with the latter one being significant. This is probably because these two datasets has higher quality label text compared with Wiki10-31K, where the label space is both large and noisy.

\noindent \textbf{Pseudo Label Description} We fine-tune \textsc{DEPL } with pseudo label descriptions, denoted as \textsc{DEPL }+label+key$k$, where $k$ is the length of the pseudo label description after BERT tokenization. We observe that with keyword length $16$, the model performs the best, which achieves significant improvement on the tail label prediction for all datasets. With larger $k=32$ in the default setting, the model includes additional "less important" keywords, which may introduce noises and thus lower the performance.

\begin{comment}

\section{Experiments}
\label{sec:experiment}
In our experiments, we probe which Transformer architecture can benefit tail label prediction, which is evaluated by proposed binned macro-based F1.
Also, we analyze the performance of the document representation-based method versus the label attention-based method.

\subsection{Datasets}
\label{sec:dataset}
We use three benchmark datasets: EUR-Lex (4K), Wiki10-31K and AmazonCat-13K.

\subsection{Shallow vs. Deep Transformers}
In the Transformer models, each word interacts with each other using self-attention, gradually forming more abstract representations from layer to layer.
Hence, the embeddings of the last layer encodes the richest semantic meaning of the entire document, which are usually used as the document representation.
In XMTC, recent works extract document representation by pooling over the last layer's embedding~\cite{chang2020taming,ye2020pretrained}, or concatenating the [CLS] embeddings from the last few layers to collect more semantic information\cite{jiang2021lightxml}.

As mentioned in the previous section, less abstract level features are potentially suitable for tail label prediction.
Intuitively, deeper Transformer layers encode the high-level semantic information~\cite{tenney-etal-2019-bert}.
Hence, the first architecture design that we want to explore is the depth of the Transformer model.
For different model depths, we control the number of layers for BERT by $[1, 2, 4, 6, 12]$ layers.

As shown in Fig \ref{fig:attn_cls}, we observe that using shallow layers of BERT benefits label attention-based method, while deep Transformer benefits the document representation-based method.
This can be expected because the Transformer model gradually refines the latent embedding of each word by incorporating more context information via the self-attention mechanism over the layers.
Compared with the upper layers, the word identity will be overwritten by the contextualized information.
Therefore, word level retrieval-based method will perform worse on the upper layers. To the contrary, as more contextualized information is injected into the [CLS] embedding in the upper layers, the global information helps document embedding to encode useful feature for the label classification.

From Table \ref{tab:results}, the performance of the retrieval-based method and the representation-based method are similar, with the retrieval-based method slightly better on P@1 and the representation-based method better on P@5. However, the two models are based on really different feature and underlying mechanism, so we will compare the difference in the next part.

\subsection{Comparison with Baselines}

In this Section, we compare our proposed AttentionXL+BERT with other baselines.

\subsection{Retrieval-based Method vs. Representation-based Method}
Although the two models give similar performance on the micro P@k metric, they are based on very different feature and classification algorithms which is not reflected by the metric. In order to show the difference, we use the F1@5 metric evaluated over different bins of labels according to their frequency in the training data.

The results are shown in Fig. \ref{fig:binned_evaluation}. The horizontal axis represents the label bins according to the number of training instances and the groups are $\{1\sim9, 10\sim 99, \ldots \}$. The vertical axis represents the relative improvement compared with the flat svm baseline. From the figure, we observe that retrieval-based method benefits the lower-frequency (tail) bins, and the representation-based method benefits the high-frequency (head) bins. As most of the training instances concentrate in the head bins, the micro precision metric will be largely impacted by the prediction in those groups. Therefore, the advantage of the retrieval method in the tail bins is shadowed by the micro P@k metric. Especially in the Wiki10-31K dataset, although retrieval based method performs worse on the precision metric, it has a huge advantage on the prediction of tail labels.

\end{comment}

\section{Theoretical Analyses on the Lower Bound Performance}
Intuitively, our model combines feature from two complementary sources: the corpus specific word importance statistics and neural embedding with word semantics.
In the theoretical analyses, we demonstrate that our model achieves a lower bound performance as the sparse classifier, given the selected keywords are important and the sparse classifier can separate the positive from the negative instances with non-trivial margin.

Let $\phi_t({\bm{x}})$ be the normalized tf-idf feature vector of text with $\| \phi_t({\bm{x}}) \|_2 = 1$. The label embeddings $\{ {\bm{w}}_1, \ldots, {\bm{w}}_L \}$ satisfies $\| {\bm{w}}_i \|_2 \le 1$. In fact, label embeddings can be transformed to satisfy the condition without changing the prediction rank.

\begin{theorem}[informal]
Let ${\bm{x}}$ be a text document with tf-idf feature $\phi_t({\bm{x}})$, and $p$ be a positive label and ${\mathbb{N}}_p = \{n_1, \ldots, n_{M_p} \}$ be a set of negative labels ranked lower than $p$. Let $\epsilon_i=\mu(\phi_t({\bm{x}}), {\bm{v}}_p, {\bm{v}}_{n_i})$ and $\epsilon = \min(\{ \epsilon_1, \ldots, \epsilon_{M_p} \})$. An error event ${\mathcal{E}}_i$ occurs when $\mu({\bm{E}}\phi_t({\bm{x}}), {\bm{E}} {\bm{v}}_p, {\bm{E}}{\bm{v}}_{n_i}) \le 0$.
The probability of any such error happening satisfies
\begin{equation}
    P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p}) \le 4 {M_p} \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{equation}
When $(\epsilon - \delta) \ge 10 \sqrt{\frac{\log M_p}{d}}$,  $P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p})
    \le \frac{1}{M_p}$
\end{theorem}

For each label $l$, the keywords are selected according to importance ${w}_{li}$ of the learned label embedding ${\bm{w}}_{l}$. Assume a set of keywords ${\mathbb{K}}_{w_l}$ is selected, we denote the keyword-selected label embedding as ${\bm{v}}_l$ where ${v}_{li} = {w}_{li}$ if $i \in {\mathbb{K}}_{w_l}$ and $0$ otherwise.

Since both the tf-idf score and the word embedding entries are positive, it is always true that $\langle \phi_t ({\bm{x}}), {\bm{v}}_l \rangle \le \langle \phi_t({\bm{x}}), {\bm{w}}_l  \rangle$, with smaller difference when more keywords are selected, especially when all the keywords are kept, $\delta = 0$. We formally define difference between the label embedding ${\bm{w}}_l$ and the keyword-selected label embedding ${\bm{v}}_l$.

 \begin{definition}
  For label $l$ and $\delta>0$, the keyword-selected label embedding is $\delta$-bounded if  $\langle \phi_t ({\bm{x}}), {\bm{v}}_l \rangle \ge \langle \phi_t({\bm{x}}), {\bm{w}}_l  \rangle - \delta $, the corresponding set of keywords is ${\mathbb{K}}_{v_l}^\delta$.
 \end{definition}

We define an error margin of prediction between two labels:

 \begin{definition}
 For two labels $p$ and $n$, with text feature $\phi({\bm{x}})$ and the label embeddings ${\bm{w}}_p, {\bm{w}}_n$, the error margin is the difference of the predicted score $\mu(\phi ({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n) = \langle \phi ({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle$.
 \end{definition}

\begin{lemma}
Following the notation above, let ${\bm{v}}$ is the $\delta$-bounded keyword-selected label embedding of ${\bm{w}}$, then
$
   | \mu( \phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n )
   - \mu( \phi_t({\bm{x}}), {\bm{v}}_p, {\bm{v}}_n ) | \le \delta
$
\end{lemma}

Lemma 1 shows that the error margin between the label embedding and the $\delta$-bounded keyword-selected embedding is bounded. All the lemmas and theorems are proved in appendix \ref{appendix:A}.

Our goal is to compare the performance between \textsc{DEPL } and the SVM model. The \textsc{DEPL } model learns dense representations for both the text $\phi_n({\bm{x}}) \in \mathbb{R}^d$ and the keywords $\phi_n({\bm{z}}_l)$ where $z_{li} \in {\mathbb{K}}_{v_l}^\delta$.
Following \citet{luan2020sparse}, we treat $\phi_n({\bm{a}}) = {\bm{E}}{\bm{a}}$ as weighted average of word embeddings aggregated by the weights of a sparse vector ${\bm{a}}$, where ${\bm{E}} \in \mathbb{R}^{d\times v}$ is the word embedding matrix. According to the famous the \textbf{Johnson-Lindenstrauss Lemma}~\citep{johnson1984extensions, ben2002limitations}, even if the entries of ${\bm{E}}$ are sampled from a random normal distribution $N(0, d^{-1/2})$, with large probability, $\langle \phi_t({\bm{x}}), {\bm{v}} \rangle$ and $\langle {\bm{E}}\phi_t({\bm{x}}), {\bm{E}}{\bm{v}} \rangle$ are close.

We formally define an error event when SVM make the correct prediction but the neural model doesn't. If the neural model avoids all such errors, the performance should be at least as good as the SVM model.

\begin{definition}
Let $p$ be a positive label and ${\mathbb{N}}_p = \{n_1, \ldots, n_{M_p} \}$ be the set of negative labels that are ranked below $p$ by SVM. For any negative $n \in {\mathbb{N}}_p$, it follows $\mu(\phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n) > 0$. An error event ${\mathcal{E}}$ occurs when $\mu ({\bm{E}} \phi_t({\bm{x}}), {\bm{E}}{\bm{v}}_p, {\bm{E}}{\bm{v}}_n) \le 0$.
\end{definition}

The following lemma shows a bound for an error event for a positive label $l$ and a negative label $n \in {\mathbb{N}}_l$.

\begin{lemma}
Let ${\bm{x}}$ be a text document with tf-idf feature $\phi_t({\bm{x}})$, and $p$ be a positive label and $n\in {\mathbb{N}}_p$. Let ${\bm{v}}_p$ and ${\bm{v}}_n$ be the $\delta$ bounded keyword label embedding. Assume $\langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_{n} \rangle = \epsilon$.
The probability of an error event ${\mathcal{E}}$ satisfies $P({\mathcal{E}}) \le 4 \exp (-\frac{(\epsilon - \delta)^2d}{50})$.
\end{lemma}

Lemma 2 models the probability of one error event for label $l$. Using the Union Bound with Lemma 2, we show a bound of probability of all the error events.

\textbf{Discussion:} Theorem 1 shows that the probability of \textsc{DEPL } performing worse than the SVM is bounded, especially when $(\epsilon - \delta)$ is larger, the probability is smaller. Intuitively, when $\delta$ is small, it means that the extracted keywords are more meaningful for the SVM model, and thus more informative for our neural encoder. The term $\epsilon$ is taking the mean of error margins $\epsilon_1, \ldots, \epsilon_{M_p}$, which means the model is prone to mistake if the negative labels are indistinguishable from the positive label.

\textbf{Theoretical analysis vs. the empirical experiments:} We acknowledge the differences between our theoretical analysis and the empirical experiments. First, the bound in the theoretical analysis is very loose as it assumed the word embeddings are random samples from Gaussian distribution. It is shown that the pre-trained language models can produce more meaningful semantic word embeddings based on the context and gain more generalization power. Second, for efficient batch encoding of label keywords, we selected top $k$ keywords for every label, whereas the ${\mathbb{K}}_{v_l}^\delta$ is just used for theoretical analysis. The $k$ is a hyper-parameter selected empirically. Lastly, the dual encoder is an additional module on top of the base neural classifier, because encoding the label keywords are beneficially for tail labels, but the head labels can be modeled with the base neural classifier.
\section{Keyword-selected Dual Encoder}
\label{sec:model}
In this section, we proposed a dual encoder framework that leverages the pairs of input document with the pseudo label descriptions extracted from a sparse classifier. We call it the Keyword-selected Dual Encoder (\textsc{DEPL}).

\noindent \textbf{Sparse classifier:}
We train a linear SVM model with tf-idf feature $\phi_t({\bm{x}})$ as the sparse classifier:
    $$ f_{\text{sparse}}({\bm{x}}, l) = \sigma(\langle \phi_t({\bm{x}}), {\bm{w}}_l \rangle)  $$
The learned word embedding ${w}_{li}$ denotes the importance of the word $i$ for label $l$. The top $k$ important keywords selected for label $l$ is denoted as ${\bm{z}}_l$, where $k$ is a hyperparameter.

\noindent \textbf{KDE:}
We first train a base neural classifier with feature extract $\phi_n({\bm{x}})$ (initialized by BERT) and the label embeddings ${\bm{u}}_l$ (randomly initialized):
\begin{equation}
    f_{\text{dense}}({\bm{x}}, l) = \sigma(\langle \phi_n({\bm{x}}),  {\bm{u}}_l \rangle)
\end{equation}
Then we fine-tune the model on pseudo label descriptions by sharing the encoder $\phi_n(.)$ for both the text (${\bm{x}}$) and keywords (${\bm{z}}_l$):
\begin{equation}
    f_{\text{KDE}}({\bm{x}}, l) = \frac{\sigma(\langle \phi_n({\bm{x}}), \phi_n({\bm{z}}_l)\rangle) +  f_{\text{dense}}({\bm{x}}, l)}{2}
\end{equation}
The predicted probability is an average of two terms, where $\sigma(\langle \phi_n({\bm{x}}), \phi_n({\bm{z}}_l)\rangle)$ leverages the document and label semantic matching that benefits the tail label prediction, and $f_{\text{dense}}({\bm{x}}, l)$ is a dense classifier that is better optimized for head labels with sufficient training data.

\noindent \textbf{Inference}: we can directly use $f_{\text{KDE}}$ or a weighted sum of sparse and KDE classifiers:
$$ f_{\text{final}}({\bm{x}}, l) = (1-\lambda)f_{\text{sparse}}({\bm{x}}, l) + \lambda f_{\text{KDE}} ({\bm{x}}, l)$$
We set $\lambda = \frac{1}{2}$ as a simple design choice.

\noindent \textbf{Learning:} $f_{\text{dense}}$ and $f_{\text{sparse}}$ are optimized with the BCE loss. For $f_{\text{KDE}}({\bm{x}}, l)$, calculating $\phi_n({\bm{z}}_l)$ for all labels both expensive and prohibitive by memory limit, so we use negative sampling for in-batch optimization. Specifically, the label representations are calculated over a subset of labels ${\mathbb{S}}_b = {\mathbb{P}}_b \cup {\mathbb{N}}_b$, where ${\mathbb{P}}_b$ contains all the positive labels for the instances in the batch and ${\mathbb{N}}_b$ are the negative labels with hard negatives and uniform random sampling. For each instance, the hard negative labels are the false positive predictions by the SVM model. The objective for dual encoder is:
\begin{equation}
\begin{split}
    \min \frac{1}{N}\sum_{i=1}^N \Bigg( \Bigg.
    \sum_{p \in {\bm{y}}_{i}^+} \log f_{\text{KDE}}({\bm{x}}, p) \\
    + \sum_{n \in {\mathbb{S}}_b \backslash {\bm{y}}_{i}^+} \log(1 - f_{\text{KDE}}({\bm{x}}, n)) \Bigg. \Bigg)
\end{split}
\end{equation}
where ${\bm{y}}_i^+$ is the set of positive labels for instance $i$.

\section{Analysis of Current XMTC Systems}
\section{Rethinking Sparse and Dense XMTC}
\label{sec:rethinking}
Let $\mathcal{D}=\{\left(\mathbf{x}_i, \mathbf{y}_i\right)_{i=1}^{N_{\text{train}}} \}$ be the training data where $\mathbf{x}_i$ is the input text and $\mathbf{y}_i\in\{0, 1\}^L$ are the binary ground truth labels.
Given an instance ${\bm{x}}$ and a label $l$, a neural classification system jointly learns the feature embedding $\phi_n({\bm{x}}; \theta)$ (parameterized by $\theta$) and the label embedding ${\bm{w}}_l$. The system calculates a relevance score (logits) $s_l = \langle \phi_n({\bm{x}}), {\bm{w}}_l \rangle$, which is then normalized by the sigmoid function to produce $p_l = \sigma(s_l)$, indicating the probability of the label being true.
The probability is optimized by the binary cross entropy (BCE) loss:
\begin{equation*}
    \mathcal{L}_{\text{BCE}} = -\sum_{l=1}^L y_l\log p_l + (1-y_l)\log (1-p_l)
\end{equation*}
The derivative of $\mathcal{L}_{\text{BCE}}$ w.r.t the logits is:
\begin{equation*}
    \frac{\partial \mathcal{L}_{\text{BCE}}}{\partial s_l} =
    \begin{cases}
        p_{l} - 1 & \text{if } y_{l}=1 \\
        p_{l} & \text{otherwise} \\
    \end{cases}
\end{equation*}
We analyze the difficulty of both the document and label embedding optimization in the skewed label distribution from the gradient perspective, and show that: 1) the learned document feature lacks for the representation of tail label. 2) the tail label embedding is hard to encode meaningful information by supervised signals alone. We then provide empirical observations together to shed light on our proposed framework.

\subsection{Analysis of Document Feature Learning}
In multi-label classification, the document feature needs to reflect all the representations of relevant labels. In fact, the gradient describes the relation between feature $\phi_n({\bm{x}})$ and label embedding ${\bm{w}}_l$. By the chain rule, the gradient of $\mathcal{L}_{\text{BCE}}$ w.r.t the document feature is:
\begin{equation*}
    \frac{\partial \mathcal{L}_{\text{BCE}}(y_{l}, p_{l})}{\partial \phi_n({\bm{x}})} =
    \begin{cases}
        (p_{l} - 1){\bm{w}}_l & \text{if } y_{l}=1 \\
        p_{l}{\bm{w}}_l & \text{otherwise} \\
    \end{cases}
\end{equation*}
By optimizing parameters $\theta$ of feature extractor,
the document feature is encourage to remove the information of a negative label, that is:
$$\phi_n({\bm{x}}; \theta^\prime) \leftarrow \phi_n({\bm{x}}; \theta) - \eta p_l {\bm{w}}_l$$
where $\eta$ is the learning rate.
Since a tail label has an overwhelming number of negative instances and  $\theta$ is shared for all the data, the feature extractor is inclined to remove the tail label information, which will be missing in the document representation. In comparison, the sparse feature like tf-idf is unsupervised from corpus statics, which does not suffer from this problem. The feature may still maintain the representation power to separate the tail labels.

\subsection{Analysis of Label Feature Learning}
When the labels are treated as indices in a classification system, they are randomly initialized and learned from supervised signals. The gradients of $\mathcal{L}_{\text{BCE}}$ w.r.t the label feature is:
\begin{equation*}
    \frac{\partial \mathcal{L}_{\text{BCE}}(y_{l}, p_{l})}{\partial {\bm{w}}_l} =
    \begin{cases}
        (p_{l} - 1) \phi_n({\bm{x}}) & \text{if } y_{l}=1 \\
        p_{l} \phi_n({\bm{x}}) & \text{otherwise} \\
    \end{cases}
\end{equation*}
The label embedding is updated by:
\begin{align*}
    {\bm{w}}_l^\prime &= {\bm{w}}_l + \frac{\eta}{N_{\text{train}}}\sum_{i: y_{il} = 1} (1 - p_{il}) \phi_n({\bm{x}}_i) \\
    & -\frac{\eta}{N_{\text{train}}} \sum_{i: y_{il}=0} p_{il}\phi_n({\bm{x}}_i)
\end{align*}
After the optimization, the label embedding tends to include features from positive instances and exclude features from negative instances.
As most of the instances are negative for a tail label, the update is inundated with the aggregation of negative features, making it hard to encode distinctive feature reflecting its identity.
Therefore, learning the tail label embedding from supervised signals alone can be very distracting. Although previous works leverage negative sampling to alleviate the problem~\cite{jiang2021lightxml, chang2020taming},
we argue that it is important to initialize the label embedding with the label side information.

\begin{figure}[th!]
     \centering
     \includegraphics[width=\linewidth]{img/tail_label_example2.png}
     \caption{The evaluation of tail label prediction for SOTA Transformer-based models with macro-averaging F1@k, where $k=19$ for Wiki10-31K and $k=5$ for the other datasets. The figure shows the relative improvement to the SVM baseline with $*$ indicating the significance for $p<0.01$.}
     \label{fig:tail_eval}
\end{figure}

\subsection{Observations and Proposed Idea}

\noindent \textbf{Obs. 1: sparse classifier has an advantage on tail label prediction.}
We evaluate the classification performance of tail labels with less than $10$ training instances by the macro-averaging F1 metric described in \secref{sec:experiment}. In \figref{fig:tail_eval}, the dense models are compared with a linear SVM baseline trained from tf-idf feature, and the relative improvement is reported. The $3$ deep Transformer models except for AttentionXML underperform the sparse classifier on all datasets, with $*$ indicating the significance~\cite{yang1999re} for $p<0.01$. AttentionXML performs the best in two datasets, but it utilizes the more expensive label-word attention that doesn't encode the document into a fixed representation, which we don't seek to improve it in this paper.

\begin{table*}[th!]
    \small
    \centering
    \begin{tabular}{lc|c}
    \toprule
    \bf Dataset & \bf Label Text & \bf Top Keywords \\
    \midrule
    & child care (1) & \makecell{\high{care child parent upbringing family} responsabilitie occupational affordable reconciliation \\ leave reconcile responsibility arise enable need \high{service} effective talent ambition charter} \\
    EURLex-4K & scientific profession (3) & \makecell{\high{science confidential} 452 access society \high{scientific} purposes whose \high{researchers} \\ bodies bank 831 issues may central list recalling \high{data} recognises 412} \\
    & mining extraction(5) & \makecell{ \high{extractive industries extracting drilling} contract soda awarded \high{mineral mining ash} \\ 531 corporation through dialogue tailings communicate tenneco 1600 webb value} \\
    \hline\\
     & phase4 (1) & \makecell{\high{trials} \high{clinical} protection personal directive processed data trial \high{drug} phase eu \\ processing \high{patients} sponsor \high{controller} legislation regulation art investigator \high{study} } \\
   Wiki10-31K & eco-construction (3) & \makecell{\high{solar building cob} passive glazing \high{cordwood thermal timber sewage natural} \\ autonomous \high{roof} \high{clay window insulation} cistern septic shade bale reduce} \\
    & bookmaking (5) & \makecell{ \high{tex book artist} spine \high{binding bind bookbinding bookbinder} nickname scroll \high{signature} \\ someone raise \high{glue sew} texas fold cloth endpaper typeset }\\
    \hline \\
    & booklet envelopes (1) & \makecell{ \high{cabinetmaking booklet} upcoming excerpts building centers \high{cabinet book} joinery \\ kreg mark basics develop provided content \high{produce} allow entire customer \high{covers} } \\
    Amazoncat-13K & sweater dresses (3) & \makecell{favorable \high{slung} impress \high{dye sweater worn} multi \high{dress} pair space \\ super sure palette knit jean low favorite jacket brown \high{soft} }\\
    & farming (5) & \makecell{ \high{crops acres farmers sustainable} hobby \high{grit profitable livestock farms} discusses \\ small issue national gardening \high{soil} readers designed magazine traditional \high{homegrown} } \\
    \bottomrule
    \end{tabular}
    \caption{Example of provided label descriptions with training frequency in parenthesis for the benchmark datasets, and the top $20$ extracted label keywords from the sparse classifier. For illustration purpose, we manually highlight keywords that can enrich the original label text. \label{tab:description} }
\end{table*}
\noindent \textbf{Obs. 2: provided label descriptions are noisy.}
The provided label descriptions are shown in the left of \tblref{tab:description}, which are usually very short, noisy and insufficient to be related to the document with lexical matching. As an example in Wiki10-31K, the label text \textit{phase4} (with only $1$ training instance) is hard even for human to understand the meaning without more context or definitions specific to the document. With generated pseudo label description (explained in the next part), we can understand it is about medical testing phases with keywords \textit{trial, clinical, drug ...} extracted. Although not all the keywords can provide rich semantics to complement the original label text, they may serve as a context for the label to make it more distinguishable, i.e. \textit{responsibility, reconciliation} for label \textit{child care}.

\noindent \textbf{Proposed Idea}
From the analysis of document feature learning and observation 1, the sparse classifier has a strength in tail label prediction. Additionally, the learned label embeddings from a sparse classifier can be interpreted as importance of words in the corpus vocabulary for the label. In this way, we can extract the top k keywords from the label embedding as the pseudo label description. From the analysis of label feature learning, it is important to provide additional label side information for label embedding. In observation 2, the neural model may benefit from the extracted keywords that leverage the knowledge from the sparse classifier and generalize better with neural embeddings of the keywords.

In \secref{sec:model}, we will explain the proposed framework that leverages the pseudo label description; in \secref{sec:theory}, we provide theoretical analysis to relate the performance of our model with respect to the sparse classifier; in \secref{sec:experiment}, we demonstrate the generalization power of our model by experiments on benchmark datasets.

\section{Related Work}
\paragraph{BoW (or Sparse) Classifier}
Traditional BoW classifiers rely on the bag-of-words features such as one-hot vector with tf-idf weights, which capture the word importance in a document. Since the feature is high dimenstional and sparse, we call the BoW classifiers the \textit{sparse classifiers}. Early examples include the one-vs-all SVM models such as DiSMEC \cite{babbar2017dismec}, ProXML \cite{babbar2019proxml} and PPDSparse \cite{yen2017ppdsparse}.
Later methods leverage the tree structure of the label space for more effective or scalable learning, such as Parabel \cite{prabhu2018parabel} and Bonsai \cite{khandagale2019bonsai}. Since tf-idf features rely on surface-level word matching, sparse classifiers tend to miss the semantic matching among lexical variants or related concepts in different wording.

\paragraph{Neural (or Dense) Classifier}
Neural models learn to capture the high level semantics of documents with dense feature embeddings. For this reason, we call them the \textit{dense classifiers}. The XML-CNN \cite{liu2017deep} and SLICE \cite{jain2019slice} employ the convolutional neural network on word embeddings for document representation. More recently, X-Transformer \cite{chang2020taming}, LightXML \cite{jiang2021lightxml} and APLC-XLNet \cite{ye2020pretrained} tames large pre-trained Transformer models to encode the input document into a fixed vector. AttentionXML \cite{you2018attentionxml} applies a label-word attention mechanism to calculate label-aware document embeddings, but it requires more computational cost proportional to the document length. In the above neural models, the feature extractor and the label embedding (randomly initialized) are jointly optimized via supervised signals. As we will show later, the document and the label embedding can be insufficiently optimized for the tail labels whose supervision signals are mostly negative.

\paragraph{Hybrid Approach:}
X-Transformer \citep{chang2020taming} complements neural model with sparse feature by concatenating tf-idf with the learned cluster-level neural embedding, which is an ensemble of the sparse and dense classifiers. Recent works in retrieval design unified systems to combine the sparse and dense features for better performance. SPARC~\cite{lee2019sparc} learns contextualized sparse feature indirectly via Transformer attention.
COIL~\cite{gao2021coil} leverages lexical matching of contextualized BERT embeddings, and CLEAR~\cite{gao2004complementing} designs a residual-based loss function for the neural model to learn hard examples from a sparse retrieval model.
While we also combine the sparse feature with neural model, the classification setting does not assume predefined label description as in the retrieval setting.

\paragraph{Label Description:}
When both the document text and label descriptions are available, the ranked-based multi-label classification is similar to the retrieval setting, where the dual encoder models~\cite{gao2021unsupervised, xiong2020approximate, luan2020sparse, karpukhin2020dense} have achieved SOTA performance in information retrieval on large benchmark datasets with millions of passages. The Siamese network \cite{dahiya2021siamesexml} for classification encodes both input documents and label descriptions under the assumption that high quality label descriptions are available. \citet{chai2020description} tries a generative model with reinforcement learning to produce extended label description with predefined label descriptions for initialization and uses cross attentions between input text document and output labels.  Although their ideas of utilizing label descriptions are attractive, the performance of those systems crucially depends on availability of predefined high-quality label descriptions, which is often difficult to obtain in real-world applications.  Instead, the realistic label descriptions are often short, noisy and insufficient for lexicon-matching based label prediction for input documents.  How to generate informative label descriptions without human efforts is thus an important problem, for which we offer an algorithmic solution in this paper.

\section{Theoretical Analysis on Performance}
\label{sec:theory}
In the theoretical analysis, we demonstrate that \textsc{DEPL } achieves a lower bound performance as the sparse classifier, given the selected keywords are important and the sparse classifier can separate the positive from the negative instances with non-trivial margin.

Let $\phi_t({\bm{x}})$ be the normalized tf-idf feature vector of text with $\| \phi_t({\bm{x}}) \|_2 = 1$. The sparse label embeddings $\{ {\bm{w}}_1, \ldots, {\bm{w}}_L \}$ satisfies $\| {\bm{w}}_l \|_2 \le 1, w_{li} > 0$. In fact, label embeddings can be transformed to satisfy the condition without changing the prediction rank.
Let ${\bm{z}}_l$ be the selected keywords and ${\bm{v}}_l$ be the sparse keyword embedding with ${v}_{li} = {w}_{li}$ if $i$ is keyword and $0$ otherwise.
We define the keyword importance and error margin which are major terms affecting the performance bound.

 \begin{definition}
  For label $l$ and $\delta \ge 0$, the sparse keyword embedding is $\delta$-bounded if  $\langle \phi_t ({\bm{x}}), {\bm{v}}_l \rangle \ge \langle \phi_t({\bm{x}}), {\bm{w}}_l  \rangle - \delta $.
 \end{definition}

\begin{definition}
 For two labels $p$ and $n$, the error margin is the difference between the predicted scores $\mu(\phi ({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n) = \langle \phi ({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle$.
\end{definition}

We state the theorem below with additional assumptions and proofs in appendix \ref{appendix:A}.

\begin{theorem}
\label{th:main}
Let $\phi_t({\bm{x}})$ and $\phi_n({\bm{x}})$ be the sparse and dense (dimension $d$) feature, ${\bm{w}}_l$ be the label embedding and  ${\bm{z}}_l$ be the $\delta$-bounded keywords. For a positive label $p$, let ${\mathbb{N}}_p = \{n_1, \ldots, n_{M_p} \}$ be a set of negative labels ranked lower than $p$.
The error margin $\epsilon_i=\mu(\phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_{n_i})$ and $\epsilon = \min(\{ \epsilon_1, \ldots, \epsilon_{M_p} \})$. An error event ${\mathcal{E}}_i$ occurs when $\mu(\phi_n({\bm{x}}), \phi_n({\bm{z}}_p), \phi_n({\bm{z}}_{n_i}) ) \le 0$.
The probability of any such error happening satisfies
\begin{equation*}
    P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p}) \le 4 {M_p} \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{equation*}
When $(\epsilon - \delta) \ge 10 \sqrt{\frac{\log M_p}{d}}$, the probability is bounded by $\frac{1}{M_p}$.
\end{theorem}

\noindent \textbf{Discussion:}
An error event occurs when the sparse model makes a correct prediction but the neural model doesn't. If the neural model avoids all such errors, the performance should be at least as good as the SVM model, and Theorem \ref{th:main} gives a bound of that probability.

The term $\delta$ measures the importance of selected keywords (smaller the more important), the term $\epsilon$ term measures the error margin of the correctly predicted positive and negative pairs by the sparse model. The theorem states that the model achieves a lower bound performance as sparse classifier if the keywords are informative and error margin is non-trivial.

\noindent \textbf{Theoretical analysis vs. empirical experiments:}
1) the bound in the theoretical analysis is very loose as the proof doesn't consider contextualized semantic embedding of Transformer models, which could produce more meaningful features based on the context and generalize better. 2) we select top $k$ keywords for every label as a hyper-parameter for efficient batch encoding of label keywords instead of the $\delta$-bounded keywords. 3) by mining hard negatives as inputs to \textsc{DEPL }, the neural model may generalize better to avoid the mistakes by sparse classifier.

\section{Theoretical Analyses on the Lower Bound Performance}
Intuitively, our model combines feature from two complementary sources: the corpus specific word importance and neural embedding with word semantics. In the theoretical analyses, we demonstrate that our model achieves a lower bound performance as the sparse classifier, given the selected keywords are important and the sparse classifier can separate the positive from the negative instances with non-trivial margin.

\textbf{Notations:} Let $\phi_t({\bm{x}})$ be the normalized tf-idf feature vector of text, s.t. $\| \phi_t({\bm{x}}) \|_2 = 1$. We assume that the label embeddings $\{ {\bm{w}}_1, \ldots, {\bm{w}}_L \}$ satisfies $\| {\bm{w}}_i \|_2 \le 1$ and $ {w}_{ij} \ge 0, i\in\{1, \ldots, L\}, j\in \{1, \ldots, V\}$. In fact, since we use a ranking metric, we can always normalize the label embeddings by
$\frac{{\bm{w}}_l - \min( \{{w}_{ij}\} )}{\max  (\{ \| {\bm{w}}_i - \min( \{{w}_{ij}\} ) \|_2 \}) }$,
without changing the prediction rank.

For each label $l$, the keywords are selected according to importance ${w}_{li}$ of the learned label embedding ${\bm{w}}_{l}$. Assume a set of keywords ${\mathbb{K}}_{w_l}$ is selected, we denote the keyword-selected label embedding as ${\bm{v}}_l$ where ${v}_{li} = {w}_{li}$ if $i \in {\mathbb{K}}_{w_l}$ and $0$ otherwise.

Since both the tf-idf score and the word embedding entries are positive, it is always true that $\langle \phi_t ({\bm{x}}), {\bm{v}}_l \rangle \le \langle \phi_t({\bm{x}}), {\bm{w}}_l  \rangle$, with smaller difference when more keywords are selected, especially when all the keywords are kept, $\delta = 0$. We formally define difference between the label embedding ${\bm{w}}_l$ and the keyword-selected label embedding ${\bm{v}}_l$.

 \begin{definition}
  For label $l$ and $\delta>0$, the keyword-selected label embedding is $\delta$-bounded if  $\langle \phi_t ({\bm{x}}), {\bm{v}}_l \rangle \ge \langle \phi_t({\bm{x}}), {\bm{w}}_l  \rangle - \delta $, the corresponding set of keywords is ${\mathbb{K}}_{v_l}^\delta$.
 \end{definition}

We define an error margin of prediction between two labels:

 \begin{definition}
 For two labels $p$ and $n$, with text feature $\phi({\bm{x}})$ and the label embeddings ${\bm{w}}_p, {\bm{w}}_n$, the error margin is the difference of the predicted score $\mu(\phi ({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n) = \langle \phi ({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle$.
 \end{definition}

\begin{lemma}
Following the notation above, let ${\bm{v}}$ is the $\delta$-bounded keyword-selected label embedding of ${\bm{w}}$, then
$
   | \mu( \phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n )
   - \mu( \phi_t({\bm{x}}), {\bm{v}}_p, {\bm{v}}_n ) | \le \delta
$
\end{lemma}

Lemma 1 shows that the error margin between the label embedding and the $\delta$-bounded keyword-selected embedding is bounded. All the lemmas and theorems are proved in appendix \ref{appendix:A}.

Our goal is to compare the performance between \textsc{DEPL } and the SVM model. The \textsc{DEPL } model learns dense representations for both the text $\phi_n({\bm{x}}) \in \mathbb{R}^d$ and the keywords $\phi_n({\bm{z}}_l)$ where $z_{li} \in {\mathbb{K}}_{v_l}^\delta$.
Following \citet{luan2020sparse}, we treat $\phi_n({\bm{a}}) = {\bm{E}}{\bm{a}}$ as weighted average of word embeddings aggregated by the weights of a sparse vector ${\bm{a}}$, where ${\bm{E}} \in \mathbb{R}^{d\times v}$ is the word embedding matrix. According to the famous the \textbf{Johnson-Lindenstrauss Lemma}~\citep{johnson1984extensions, ben2002limitations}, even if the entries of ${\bm{E}}$ are sampled from a random normal distribution $N(0, d^{-1/2})$, with large probability, $\langle \phi_t({\bm{x}}), {\bm{v}} \rangle$ and $\langle {\bm{E}}\phi_t({\bm{x}}), {\bm{E}}{\bm{v}} \rangle$ are close.

We formally define an error event when SVM make the correct prediction but the neural model doesn't. If the neural model avoids all such errors, the performance should be at least as good as the SVM model.

\begin{definition}
Let $p$ be a positive label and ${\mathbb{N}}_p = \{n_1, \ldots, n_{M_p} \}$ be the set of negative labels that are ranked below $p$ by SVM. For any negative $n \in {\mathbb{N}}_p$, it follows $\mu(\phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n) > 0$. An error event ${\mathcal{E}}$ occurs when $\mu ({\bm{E}} \phi_t({\bm{x}}), {\bm{E}}{\bm{v}}_p, {\bm{E}}{\bm{v}}_n) \le 0$.
\end{definition}

The following lemma shows a bound for an error event for a positive label $l$ and a negative label $n \in {\mathbb{N}}_l$.

\begin{lemma}
Let ${\bm{x}}$ be a text document with tf-idf feature $\phi_t({\bm{x}})$, and $p$ be a positive label and $n\in {\mathbb{N}}_p$. Let ${\bm{v}}_p$ and ${\bm{v}}_n$ be the $\delta$ bounded keyword label embedding. Assume $\langle \phi_t({\bm{x}}), {\bm{v}}_p - {\bm{v}}_{n} \rangle = \epsilon$.
The probability of an error event ${\mathcal{E}}$ satisfies $P({\mathcal{E}}) \le 4 \exp (-\frac{(\epsilon - \delta)^2d}{50})$.
\end{lemma}

Lemma 2 models the probability of one error event for label $l$. Using the Union Bound with Lemma 2, we show a bound of probability of all the error events.

\begin{theorem}
Let ${\bm{x}}$ be a text document with tf-idf feature $\phi_t({\bm{x}})$, and $p$ be a positive label and ${\mathbb{N}}_p = \{n_1, \ldots, n_{M_p} \}$ be a set of negative labels ranked lower than $p$. Let $\epsilon_i=\mu(\phi_t({\bm{x}}), {\bm{v}}_p, {\bm{v}}_{n_i})$ and $\epsilon = \min(\{ \epsilon_1, \ldots, \epsilon_{M_p} \})$. An error event ${\mathcal{E}}_i$ occurs when $\mu({\bm{E}}\phi_t({\bm{x}}), {\bm{E}} {\bm{v}}_p, {\bm{E}}{\bm{v}}_{n_i}) \le 0$.
The probability of any such error happening satisfies
\begin{equation}
    P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p}) \le 4 {M_p} \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{equation}
When $(\epsilon - \delta) \ge 10 \sqrt{\frac{\log M_p}{d}}$,  $P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p})
    \le \frac{1}{M_p}$
\end{theorem}

\textbf{Discussion:} Theorem 1 shows that the probability of \textsc{DEPL } performing worse than the SVM is bounded, especially when $(\epsilon - \delta)$ is larger, the probability is smaller. Intuitively, when $\delta$ is small, it means that the extracted keywords are more meaningful for the SVM model, and thus more informative for our neural encoder. The term $\epsilon$ is taking the mean of error margins $\epsilon_1, \ldots, \epsilon_{M_p}$, which means the model is prone to mistake if the negative labels are indistinguishable from the positive label.

\textbf{Theoretical analysis vs. the empirical experiments:} We acknowledge the differences between our theoretical analysis and the empirical experiments. First, the bound in the theoretical analysis is very loose as it assumed the word embeddings are random samples from Gaussian distribution. It is shown that the pre-trained language models can produce more meaningful semantic word embeddings based on the context and gain more generalization power. Second, for efficient batch encoding of label keywords, we selected top $k$ keywords for every label, whereas the ${\mathbb{K}}_{v_l}^\delta$ is just used for theoretical analysis. The $k$ is a hyper-parameter selected empirically. Lastly, the dual encoder is an additional module on top of the base neural classifier, because encoding the label keywords are beneficially for tail labels, but the head labels can be modeled with the base neural classifier.
\subsection{Preliminary}

Let $\mathcal{D}=\{\left(\mathbf{x}_i, \mathbf{y}_i\right)_{i=1}^{N_{\text{train}}} \}$ be the training data where $\mathbf{x}_i$ is the input text and $\mathbf{y}_i\in\{-1, +1\}^L$ is the ground truth label list.
The XMTC method can be formulated as learning a scoring function $f(\mathbf{x}, l) \in {\mathbb{R}}$ defined on an input and candidate label pair $({\bm{x}}, l)$. The score should be higher for relevant labels than irrelevant labels.
The objective function of a classification model is defined as:
\begin{equation*}
        \min_{f} \quad \frac{1}{N_{\text{train}} L} \sum_{i=1}^{N_{\text{train}}} \sum_{l=1}^{L} \mathcal{L}(y_{i l}, f(\mathbf{x}_i, l))
\end{equation*}
where $\mathcal{L}(\cdot, \cdot)$ is an instance-wise loss, such as a hinge loss in a Linear SVM or a sigmoid loss in the final layer of a neural network.

In the evaluation, since multi-labels can be relevant for an input document $\mathbf{x}$, a typical way is to measure the quality of a top-k ranked list of the predicted label: \begin{equation}
    \operatorname{Top-k}([f({\bm{x}}, 1), \ldots, f({\bm{x}}, L)])
\end{equation}

\subsection{Motivation 1. Sparse vs. Dense Classifier}
We compare the models with two types of features that are frequently used in the classification systems: the tf-idf feature and dense embedding feature.
\noindent \textbf{Tf-idf+SVM} The one-vs-all linear SVM model is a simple realization of $f(\mathbf{x}, l)$:
\begin{equation*}
    f({\bm{x}}, l) = \langle \phi_t({\bm{x}}), {\bm{w}}_l \rangle
\end{equation*}
where $\phi_{\text{t}}({\bm{x}}) \in {\mathbb{R}}^{v}$ converts each text input into the tf-idf feature with vocabulary size of $v$, and ${\bm{w}}_l \in \mathbb{R}^v$ is the learned parameter of linear classifier for label $l$. The tf-idf feature uses the human defined heuristics to reflect the distributed importance of each word in the training corpus.

The document-vector representation-based methods (\textit{doc-vec}) encodes the raw text into a dense vector representation with neural networks as $\phi_n({\bm{x}})$.
\begin{equation}
    f({\bm{x}}, l) = \langle \phi_n({\bm{x}}), {\bm{u}}_l \rangle
\end{equation}
where $\phi_n({\bm{x}}) \in {\mathbb{R}}^{d}$ is a $d$ dimensional dense feature usually obtained by the deep transformer models such as BERT~\citep{devlin2018bert} or XLNet~\citep{yang2019xlnet}.
${\bm{u}}_l$ represents the learned parameter of a linear classifier for label $l$, which is typically optimized by the logistic regression objective $\mathcal{L}_{\mathrm{logistic}}$. We use ${\bm{u}}_l$ to distinguish from ${\bm{w}}_l$ because ${\bm{u}}_l \in {\mathbb{R}}^d$ is a compressed dense vector while ${\bm{w}}_l \in {\mathbb{R}}^v$ is sparse ($d \ll v$).

We highlight the key differences between the two types of features: 1) tf-idf is corpus dependent and the neural embedding reflects the general language understanding. 2) tf-idf is unsupervised but the neural embedding is supervised. 3) the tf-idf is a sparse vector but the dense embedding is not.

. Dense vectors are effective for
encoding local syntactic and semantic cues leveraging recent advances in contextualized text encoding (Devlin et al., 2019), while sparse vectors
are superior at encoding precise lexical information.

\section{Evaluation Methodology}
\label{sec:background_metric}
A typical way to evaluate XMTC is to measure the quality of the label ranked list produced by the model.
The micro-based metrics takes average over all the test instances:
\begin{equation}
    \operatorname{Micro@k}  = \frac{1}{N_{\text{test}}} \sum_{i=1}^{N_{\text{test}}} \operatorname{Metric}(\mathbf{p}_i^k,\mathbf{y}_i)
\end{equation}
where $N_{\text{test}}$ is the number of test instances and $\mathbf{p}^k_i, \mathbf{y}_i$ are the predicted top $k$ ranked list and the ground truth labels respectively.
$\operatorname{Metric}$ is a function to score the quality of the ranked list such as P@k (Precision at k)~\cite{liu2017deep, you2018attentionxml, parabel, khandagale2019bonsai, ye2020pretrained, chang2020taming, jiang2021lightxml}, R@k (Recall at k), N@k (Normalized Discounted Cumulative Gain at k)~\cite{fastxml} , or PSP@k (Propensity-scored Performance at k)~\cite{PSP}, which are discussed in Section \ref{sec:append_micro_eval}.

In this paper, we report the micro F1@k as the evaluation metric, which is calculated by:
\begin{equation}
    \operatorname{F1@k} = 2 \frac{P@k \cdot R@k }{P@k + R@k }
\end{equation}

\paragraph{Macro-averaging Metrics}
For better evaluation on the label level, we proposed to apply the \textit{macro-averaging F1} metric, where the performance score on each label is given an equal weight when calculating the average.
Moreover, the macro-averaging F1 metric can be applied to groups of labels according to their training frequency to clearly reflect the performance on head labels and tail labels. We call this metric the \textit{binned macro-averaging F1} metric.
Let $L_b$ be a group of labels, then the macro-based F1 on $L_b$ is calculated by:
\begin{equation}
    \operatorname{Macro@k} = \frac{1}{|L_b|} \sum_{l \in L_b} \operatorname{F1}_l^k
\end{equation}
where $L_b$ is the label set for bin $b$ and $\operatorname{F1}_l^k$ is the $\operatorname{F1}$ metric for label $l$ evaluated on top $k$ ranked list $\mathbf{p}^k$.

Specifically, the F1@k for label $l$ over predicted ranked list $\mathbf{p}^k$ is calculated according to the confusion matrix at Table \ref{tab:confusion_matrix}:
\begin{equation*}
    \mathrm{P}^k_{l}= \frac{\mathrm{TP}_l^k}{\mathrm{TP}_l^k + \mathrm{FP}_l^k} ,\quad \mathrm{R}^k_{l}=\frac{\mathrm{TP}_l^k}{\mathrm{TP}_l^k + \mathrm{FN}_l^k} ,\quad
    \mathrm{F1}^k_l=  2\frac{\mathrm{P}^k_l \cdot \mathrm{R}^k_l}{\mathrm{P}^k_l+ \mathrm{R}^k_l}
\end{equation*}

where $\mathrm{P}^k_l, \mathrm{R}^k_{l}, \mathrm{F1}^k_l$ are the precision, recall, F1 at $k$ for label $l$. As a designed choice, we set $\mathrm{F1}^k_l = 0$ if a label $l$ is never predicted.

\begin{table}[h!]
    \centering
    \small
    \caption{Confusion Matrix for label $l$ and top $k$ ranked list $\mathbf{p}^k$.}
    \begin{tabular}{c|cc}
    & $l$ in $\mathbf{y}$ & $l$ not in $\mathbf{y}$ \\
    \hline
    $l$ in $\mathbf{p}^k$ & True Positive($\mathrm{TP}_l^k$) & False Positive($\mathrm{FP}_l^k$) \\
    $l$ not in $\mathbf{p}^k$ & False Negative($\mathrm{FN}_l^k$) & True Negative($\mathrm{TN}_l^k$) \\
    \end{tabular}
    \vspace{-1.0em}
    \label{tab:confusion_matrix}
\end{table}

\section{Proposed Method}
\label{sec:model}
In this section,we first provide the preliminaries on multi-label text classification system. Then we discuss the generation of pseudo label description obtained from a sparse classifier, the design of \textsc{DEPL } from the retrieval perspective, and the enhanced classification system with the retrieval module.

\subsection{Preliminaries}
Let $\mathcal{D}=\{\left(\mathbf{x}_i, \mathbf{y}_i\right)_{i=1}^{N_{\text{train}}} \}$ be the training data where $\mathbf{x}_i$ is the input text and $\mathbf{y}_i\in\{0, 1\}^L$ are the binary ground truth labels of size $L$.
Given an instance ${\bm{x}}$ and a label $l$, a classification system produces a matching score of the text and label:
\begin{equation*}
    f({\bm{x}}, l) = \langle \phi({\bm{x}}), {\bm{w}}_l \rangle
\end{equation*}
where $\phi({\bm{x}})$ represent the document feature vector and ${\bm{w}}_l$ represents the label embedding of $l$. The dot product $\langle \cdot, \cdot \rangle$ is used as the similarity function.

Typically, the label embedding ${\bm{w}}_l$ is randomly initialized and trained from the supervised signal. While learning the embedding as free parameters is expressive when data is abundant, it could be difficult to be optimized under the data scarce situation.
\paragraph{Sketch of Method} To tackle the long-tailed XMTC problem, we propose \textsc{DEPL}, a neural retrieval framework with generated pseudo label descriptions, as shown in \figref{fig:model}. Instead of learning the label embedding from scratch, the retrieval module directly leverages the semantic matching between the document and label text, providing a strong inductive bias on tail label prediction.

Furthermore, we will show in later sections that a BoW classifier with the statistical feature gives better performance in data scarce situation. The pseudo labels generated from a BoW classifier exploit such data heuristics, and the neural model complements the statistical information with semantic meaning for further improvement. Next, we introduce the components of our system in details.

\subsection{Pseudo Label Description}
Short label names are usually given in the benchmark dataset, such as the category name of an Amazon product or the could tag of a Wikipedia article.
However, the provided label name is usually noisy and ambiguous, of which the precise meaning need to be inferred from the document text (refer to \secref{sec:evaluation} for more detailed discussions). Therefore, we enhance the quality of label names by an augmentation with keywords generated from a sparse classifier.
While there are multiple choices of the sparse classifier, we pick the linear SVM model with tf-idf feature $\phi_t({\bm{x}})$ for a balance between efficiency and performance:
    $$ f_{\text{sparse}}({\bm{x}}, l) = \langle \phi_t({\bm{x}}), {\bm{w}}^{\text{svm}}_l \rangle  $$
The label embedding weight ${\bm{w}}^{\text{svm}}_l$ is optimized with the hinge loss:
\begin{equation*}
    \mathcal{L}_{\text{hinge}} = \frac{1}{LB}\sum_{i=1}^B\sum_{l=1}^L \max (0, 1- \tilde{y}_l \cdot f_{\text{sparse}}({\bm{x}}_i, l))
\end{equation*}
where $\tilde{y}_{l}=2 y_{l}-1 \in\{-1,1\}$ and $B$ is the batch size.

For a train SVM model, ${\bm{w}}^{\text{svm}}_l$ has the dimension equal to the vocabulary size and each value ${w}^{\text{svm}}_{li}$ of the label embedding denotes the importance of the token $i$ w.r.t label $l$. We select the top $k$ most important tokens (ranked according to the importance score) as keywords, which are appended to the original label name to form the pseudo label description:
\begin{equation*}
    \operatorname{pseudo\_label}(l) = \operatorname{label\_name}(l) \oplus \operatorname{keywords}(l)
\end{equation*}
where $\oplus$ is the append operation. The token importance learned in ${\bm{w}}^{\text{svm}}_l$ is purely based on the statistics of word frequency. After we extract the tokens as keywords, we can additionally leverage the semantic meaning of them with the powerful neural network representations, which will be introduced in the next section.

\subsection{Retrieval Model with Label Text}
In the long-tailed XMTC problem, the training instances of document and label pair for tail labels are limited, and thus it is difficult to optimize for neural model with a large number of parameters. Instead, we use a dual encoder model \cite{gao2021unsupervised, xiong2020approximate, luan2020sparse, karpukhin2020dense} to leverage the semantic matching of document and label text. We use the BERT \cite{devlin2018bert} model as our design choice as the contextualized function, which is shared for both the document and label text encoding. The similarity between them is measured by the dot product:
\begin{equation*}
    f_{\text{dual}}({\bm{x}}, l) = \langle \phi_{\text{doc}}({\bm{x}}), \phi_{\text{label}}(\operatorname{text}(l)) \rangle
\end{equation*}
where $\operatorname{text}(l)$ is the textual information of the label $l$. When the textual information only includes the label name given in the dataset, we call the model \textbf{DE-ret}. Otherwise, when the textual information is the pseudo label, we call the model \textbf{DEPL}.

The document embedding $\phi_{\text{doc}}({\bm{x}})$ is obtained from the CLS embedding of the BERT model followed by a linear pooling layer:
\begin{equation*}
    \phi_{\text{doc}}({\bm{x}}) = {\bm{W}}_{doc} \cdot \operatorname{BERT}({\bm{x}}, \text{CLS}) + {\bm{b}}_{doc}
\end{equation*}
where $\operatorname{BERT}(\operatorname{text}(l), \text{CLS})$ represents the contextualized embedding of the special CLS token. ${\bm{W}}_{doc}$ and ${\bm{b}}_{doc}$ are the weights and biases for the document pooler layer.

For the label embedding $\phi_{\text{label}}(\operatorname{text}(l))$, we take an average of the last hidden layer of BERT followed by a linear pooler layer:
\begingroup
\small
\begin{align}
    &\phi_{\text{label}} (\operatorname{text}(l)) = {\bm{W}}_{label} \cdot \psi_{bert}(\operatorname{text}(l)) + {\bm{b}}_{label} \\
    &\psi_{bert}(\operatorname{text}(l)) = \frac{1}{|\operatorname{text}(l)|}\sum_{j=1}^{|\operatorname{text}(l)|} \operatorname{BERT}(\operatorname{text}(l), j) \label{eq:avg_bert}
\end{align}
\endgroup
where $\operatorname{BERT}(\operatorname{text}(l), j)$ represents the contextualized embedding of the $j$-th token in $\operatorname{text}(l)$ obtained from the last hidden layer of the BERT model. ${\bm{W}}_{label}$ and ${\bm{b}}_{label}$ are the weights and biases for the label pooler layer. In the \eqref{eq:avg_bert}, the average embedding of label tokens yields better performance empirically than the CLS embedding for two potential reasons: 1) the keywords ranked by importance are not natural language and the CLS embedding may not effectively aggregate such type of information, and 2) the CLS embedding captures the global semantic of longer context while the average of token preserves more of the shorter label text meaning.

\paragraph{Learning with Negative Sampling}
In order to optimize $f_{\text{dual}}({\bm{x}}, l)$, we need to calculate the label embedding $\phi_{\text{label}}(\operatorname{text}(l))$. Since calculating all the label embeddings for each batch is both expensive and prohibitive by the memory limit, we resort to negative sampling strategies for in-batch optimization. Specifically, we sample a fix-sized subset of labels for each batch containing: 1) all the positive labels of the instances in the batch, 2) the top negative predictions by the sparse classifier as the hard negatives, and 3) the rest of the batch is filled with uniformly random sampled negatives labels.

Let ${\mathbb{S}}_b$ be the subset of labels sampled for a batch. The objective for the dual encoder is:
\begin{equation*}
\begin{split}
    \mathcal{L}_{\text{dual}} = -\frac{1}{B |{\mathbb{S}}_b|}\sum_{i=1}^B \Bigg( \Bigg.
    \sum_{p \in {\bm{y}}_i^{+}} \log \sigma(f_{\text{dual}}({\bm{x}}_i, p)) \\
    + \sum_{n \in {\mathbb{S}}_b \backslash {\bm{y}}_i^+} \log \sigma((1 - f_{\text{dual}}({\bm{x}}_i, n))) \Bigg. \Bigg)
\end{split}
\end{equation*}
where $B$ is the batch size, ${\bm{y}}_i^+$ is the postive labels for instance $i$, and $\sigma$ is the sigmoid function.

\subsection{Enhance Classification with Retrieval}
In the neural classification system, the label embedding is treated as free parameters to be learned from supervised data, which is more expressive for medium and head labels with abundant training instances. The dense classifier learns the function:
\begin{equation}
    f_{\text{dense}}({\bm{x}}, l) = \langle \phi_{\text{doc}}({\bm{x}}), {\bm{w}}_l^{\text{neural}}\rangle
\end{equation}
We propose to enhance the classification model with the retrieval mechanism by jointly fine-tuning:
\begin{equation}
    f_{\text{cls-dual}}({\bm{x}}, l) = \frac{\sigma(f_\text{dual}({\bm{x}}, l)) +  \sigma(f_{\text{dense}}({\bm{x}}, l))}{2}
\end{equation}
The classification and retrieval modules share the same BERT encoder. We refer to the system as \textbf{DEPL+c}. The object function $\mathcal{L}_{\text{cls-dual}}$ is similar to $\mathcal{L}_{\text{dual}}$ except for replacing $f_{\text{dual}}$ with $f_{\text{\text{cls-dual}}}$.

The \textbf{DEPL+c} model looks like an ensemble of the two systems at the first sight, but there are two major differences: 1) As the BERT encoder is shared between the classification and retrieval modules, it doesn't significantly increase the number of parameters as in \cite{chang2020taming, jiang2021lightxml}; and 2) when the two modules are optimized together, the system can take advantages of both units according to the situation of head or tail label predictions.

\section{Analysis of Current XMTC Systems}
\section{Theoretical Analyses of \textsc{DEPL }}
\label{sec:analysis}
In this section, we first
discuss the relation between dense and sparse classifier and then we derive a lower bound performance of \textsc{DEPL } over the sparse classifier.

\subsection{Rethinking Dense and Sparse XMTC}
We analyze the document and label embedding optimization in the skewed label distribution from the gradient perspective. Specifically, recall the predicted probability optimized by the binary cross entropy (BCE) loss:
\begin{equation*}
    \mathcal{L}_{\text{BCE}} = -\sum_{l=1}^L y_l\log p_l + (1-y_l)\log (1-p_l)
\end{equation*}
The derivative of $\mathcal{L}_{\text{BCE}}$ w.r.t the logits is:
\begin{equation*}
    \frac{\partial \mathcal{L}_{\text{BCE}}}{\partial s_l} =
    \begin{cases}
        p_{l} - 1 & \text{if } y_{l}=1 \\
        p_{l} & \text{otherwise} \\
    \end{cases}
\end{equation*}

\paragraph{Document Feature Learning} In multi-label classification, the document feature needs to reflect all the representations of relevant labels. In fact, the gradient describes the relation between feature $\phi_n({\bm{x}})$ and label embedding ${\bm{w}}_l$. By the chain rule, the gradient of $\mathcal{L}_{\text{BCE}}$ w.r.t the document feature is:
\begin{equation*}
    \frac{\partial \mathcal{L}_{\text{BCE}}(y_{l}, p_{l})}{\partial \phi_n({\bm{x}})} =
    \begin{cases}
        (p_{l} - 1){\bm{w}}_l & \text{if } y_{l}=1 \\
        p_{l}{\bm{w}}_l & \text{otherwise} \\
    \end{cases}
\end{equation*}
By optimizing parameters $\theta$ of feature extractor,
the document representation is encourage to move away from the negative label representation, that is:
$$\phi_n({\bm{x}}; \theta^\prime) \leftarrow \phi_n({\bm{x}}; \theta) - \eta p_l {\bm{w}}_l$$
where $\eta$ is the learning rate.
Since a tail label appears more often as negative labels and $\theta$ is shared for all the data, the feature extractor is unlikely to encode tail label information, making tail labels more difficult to be predicted. In comparison, the sparse feature like tf-idf is unsupervised from corpus statics, which does not suffer from this problem. The feature may still maintain the representation power to separate the tail labels.

\paragraph{Label Feature Learning}
When the labels are treated as indices in a classification system, they are randomly initialized and learned from supervised signals. The gradients of $\mathcal{L}_{\text{BCE}}$ w.r.t the label feature is:
\begin{equation*}
    \frac{\partial \mathcal{L}_{\text{BCE}}(y_{l}, p_{l})}{\partial {\bm{w}}_l} =
    \begin{cases}
        (p_{l} - 1) \phi_n({\bm{x}}) & \text{if } y_{l}=1 \\
        p_{l} \phi_n({\bm{x}}) & \text{otherwise} \\
    \end{cases}
\end{equation*}
The label embedding is updated by:
\begin{align*}
    {\bm{w}}_l^\prime &= {\bm{w}}_l + \frac{\eta}{N_{\text{train}}}\sum_{i: y_{il} = 1} (1 - p_{il}) \phi_n({\bm{x}}_i) \\
    & -\frac{\eta}{N_{\text{train}}} \sum_{i: y_{il}=0} p_{il}\phi_n({\bm{x}}_i)
\end{align*}
As most of the instances are negative for a tail label, the update of tail label embedding is inundated with the aggregation of negative features, making it hard to encode distinctive feature reflecting its identity.
Therefore, learning the tail label embedding from supervised signals alone can be very distracting. Although previous works leverage negative sampling to alleviate the problem~\cite{jiang2021lightxml, chang2020taming},
we argue that it is important to initialize the label embedding with the label side information.

\subsection{Analysis on Performance Lower Bound}
\label{sec:theory}
We will show that \textsc{DEPL } achieves a lower bound performance as the sparse classifier, given the selected keywords are important and the sparse classifier can separate the positive from the negative instances with non-trivial margin.

Let $\phi_t({\bm{x}})$ be the normalized tf-idf feature vector of text with $\| \phi_t({\bm{x}}) \|_2 = 1$. The sparse label embeddings $\{ {\bm{w}}_1, \ldots, {\bm{w}}_L \}$ satisfies $\| {\bm{w}}_l \|_2 \le 1, w_{li} > 0$. In fact, label embeddings can be transformed to satisfy the condition without affecting the prediction rank.
Let ${\bm{z}}_l$ be the top selected keywords from the sparse classifier, which is treated as the pseudo label. Define the sparse keyword embedding ${\bm{v}}_l$ with ${v}_{li} = {w}_{li}$ if $i$ is an index of selected keywords and $0$ otherwise.

In the following, we define the keyword importance and the classification error margin.
 \begin{definition}
  For label $l$ and $\delta \ge 0$, the sparse keyword embedding ${\bm{v}}_l$ is $\delta$-bounded if  $\langle \phi_t ({\bm{x}}), {\bm{v}}_l \rangle \ge \langle \phi_t({\bm{x}}), {\bm{w}}_l  \rangle - \delta $.
 \end{definition}

\begin{definition}
 For two labels $p$ and $n$, the error margin $\mu$ is the difference between the predicted scores $\mu(\phi ({\bm{x}}), {\bm{w}}_p, {\bm{w}}_n) = \langle \phi ({\bm{x}}), {\bm{w}}_p - {\bm{w}}_n \rangle$.
\end{definition}

We state the main theorem below:
\begin{theorem}
\label{th:main}
Let $\phi_t({\bm{x}})$ and $\phi_n({\bm{x}})$ be the sparse and dense (dimension $d$) document feature, ${\bm{w}}_l$ be the label embedding and  ${\bm{z}}_l$ be the $\delta$-bounded keywords. For a positive label $p$, let ${\mathbb{N}}_p = \{n_1, \ldots, n_{M_p} \}$ be a set of negative labels ranked lower than $p$.
The error margin $\epsilon_i=\mu(\phi_t({\bm{x}}), {\bm{w}}_p, {\bm{w}}_{n_i})$ and $\epsilon = \min(\{ \epsilon_1, \ldots, \epsilon_{M_p} \})$. An error ${\mathcal{E}}_i$ of the neural classifier occurs when
\begin{equation}
    \mu(\phi_n({\bm{x}}), \phi_n({\bm{z}}_p), \phi_n({\bm{z}}_{n_i}) ) \le 0
\end{equation}
The probability of any such error happening satisfies
\begin{equation*}
    P({\mathcal{E}}_1 \cup \ldots \cup {\mathcal{E}}_{M_p}) \le 4 {M_p} \exp (-\frac{(\epsilon - \delta)^2d}{50})
\end{equation*}
When $(\epsilon - \delta) \ge 10 \sqrt{\frac{\log M_p}{d}}$, the probability is bounded by $\frac{1}{M_p}$.
\end{theorem}

\noindent \textbf{Discussion:}
An error event occurs when the sparse model makes a correct prediction but the neural model doesn't. If the neural model avoids all such errors, the performance should be at least as good as the sparse model, and Theorem \ref{th:main} gives a bound of that probability.

The term $\delta$ measures the importance of selected keywords (smaller the more important), the error margin $\epsilon$ measures the difficulty the correctly predicted positive and negative pairs by the sparse model. The theorem states that the model achieves a lower bound performance as sparse classifier if the keywords are informative and error margin is non-trivial. Proofs and assumptions are in \secref{sec:proof} for interested readers.

\section{Evaluation Design}
\label{sec:experiment}

\subsection{Datasets}

The benchmark datasets for our experiments are
EURLex-4K~\citep{10.1007/978-3-540-87481-2_4}, Wiki10-31K~\citep{zubiaga2012enhancing} and AmazonCat-13K~\citep{10.1145/2507157.2507163}. The Wiki10-31K and AmazonCat-13K were obtained from the Extreme Classification Repository\footnote{\url{http://manikvarma.org/downloads/XC/XMLRepository.html}}. As for EURLex-4K, we obtained an unstemmed version from the APLC-XLNet github\footnote{\url{https://github.com/huiyegit/APLC_XLNet.git}}. Table~\ref{tab:dataset} summarizes the corpus statistics.

\begin{table}[th!]
    \centering
    \small
    \caption{Corpus Statistics: $N_{\text{train}}$ and $N_{\text{test}}$ are the number of training and testing instances respectively; $\bar{L}_d$ is the average number of labels per document, and $L$ is the number of unique labels in total;  $|{\mathbb{L}}_{\text{tail}}|$ is the number of tail labels with $1\sim 9$ positive training instances. \label{tab:dataset}}
    \begin{adjustbox}{width=\columnwidth,center}
    \begin{tabular}{l|cccccc}
    \toprule
    Dataset & $N_{train}$ & $N_{test}$  & $\bar{L}_d$ & $L$ & $|{\mathbb{L}}_{\text{tail}}|$ \\
    \midrule
    EURLex-4K & 15,539 &  3,809  & 5.30 & 3,956 & 2,413 \\
    Wiki10-31K & 14,146 & 6,616  & 18.64 &  30,938 & 26,545 \\
    AmazonCat-13K & 1,186,239 & 306,782  & 5.04 & 13,330 & 3,936 \\
    \bottomrule
    \end{tabular}
    \end{adjustbox}
\end{table}

For comparative evaluation of methods in tail label prediction, from each of the three corpora we extracted the subset of labels with $1 \sim 9$ positive training instances.  Those tail-label subsets include
$63.48\%$, $88.65\%$ and $29.53\%$ of the total labels in the three corpora, respectively.  These numbers indicate that the label distributions are indeed highly skewed, with a heavy long tail in each corpus.

\subsection{Evaluation Metrics}
We use three metrics which are commonly used in XMTC evaluations,  namely, the micro-averaged $P@k)$, the PSP@k \cite{PSP, wei2021towards}, and the macro-averaged $F1@k$.

Given a ranked list of the predicted labels for each test document, the precision of the top-k labels is defined as:
\begin{equation}
    P@k = \frac{1}{k} \sum_{i=1}^{k} \mathbbm{1}_{{\bm{y}}_i^+}(p_i)
\end{equation}
where  $p_i$ is the $i$-th label in the list ${\bm{p}}$ and $\mathbbm{1}_{{\bm{y}}_i^+}$ is the indicator function. The average of the $P@k$ values across all the test-set documents is called \textbf{micro-averaged P@k}, which has been the most commonly used in XMTC evaluations. Since this metric gives an equal weight to the per-instance scores, the resulted average is dominated by the system's performance on the common (head) labels but not the tail labels.
In other words, the performance comparison in this metric cannot provide enough insights to the effectiveness of methods in tail label prediction.

As an alternative metric, \textbf{PSP@k} ~\cite{PSP}  re-weights the precision on each instance as: \begin{align*}
    PSP @ k=\frac{1}{k} \sum_{l=1}^{k} \frac{\mathbbm{1}_{\mathbf{y}}(\mathbf{p}_l)}{\operatorname{prop}(\mathbf{p}_l)}
\end{align*}
where  the propensity score $\operatorname{prop}(\mathbf{p}_l)$ in the denominator gives higher weights to tail labels.

\textbf{Macro-averaged F1@k} \cite{yang1999re} is a metric that gives an equal weight to all the labels, including tail labels, head labels and any labels in the middle range. It is defined as the average of the label-specific $F1@k$ values, calculated based on a contingency table for each label, as shown in \tblref{tab:confusion_matrix}.  Specifically, the precision, recall and $F1$ for a predicted ranked list of length $k$ are computed as $\mathrm{P}= \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}}, \mathrm{R}=\frac{ \mathrm{TP}}{ \mathrm{TP} + \mathrm{FN}}$, and $\operatorname{F1} = 2 \frac{P \cdot R }{P + R }$.
\begin{table}[ht]
    \centering
    \setlength{\tabcolsep}{4pt}
    \caption{Contingency table for label $l$.}
    \begin{adjustbox}{width=\columnwidth,center}
    \begin{tabular}{c|cc}
    & $l$ is true label & $l$ is not true label \\
    \hline
    $l$ is predicted & True Positive ($\mathrm{TP}_l$) & False Positive ($\mathrm{FP}_l$) \\
    $l$ is not predicted & False Negative ($\mathrm{FN}_l$) & True Negative ($\mathrm{TN}_l$) \\
    \end{tabular}
    \end{adjustbox}
    \label{tab:confusion_matrix}
\end{table}

For micro-averaged P@k and PSP@k, we choose $k=1,3,5$ as in previous works. For macro-averaged F1@k, we choose $k=19$ for Wiki10-31K because it has an average of $18.64$ labels and $k=5$ for the rest datasets.

\subsection{Baselines}
For the tail label evaluation, our method is compared with the SOTA deep learning models including X-Transformer~\cite{chang2020taming}, XLNet-APLC~\cite{ye2020pretrained}, LightXML~\cite{jiang2021lightxml}, and AttentionXML~\cite{you2018attentionxml}. X-Transformer, LightXML, and XLNet-APLC employ pre-trained Transformers for document representation. We reproduced the results of single model (given in their implementation) predictions with BERT as the base model for LightXML, BERT-large for X-Transformer, XLNet for XLNet-APLC, and LSTM for AttentionXML. The AttentionXML utilizes label-word attention to generate label-aware document embeddings, while the other models generate fixed document embedding.

For the overall prediction of all labels, we also include the baselines of sparse classifiers: DisMEC~\cite{babbar2017dismec}, PfastreXML~\cite{jain2016extreme}, Parabel~\cite{prabhu2018parabel}, Bonsai~\cite{khandagale2019bonsai}, and we use the published results for comparison. We provide an implementation of linear SVM model with our extracted tf-idf features as another sparse baseline, and a BERT-base classifier as another dense classifier (used to initialize \textsc{DEPL}).

\subsection{Implementation Details}
For the sparse model, since the public available BoW feature doesn't have a vocabulary dictionary, we generate the tf-idf feature by ourselves. We tokenize and lemmatize the raw text with the Spacy~\cite{spacy2} library and extract the tf-idf feature with the Sklearn~\cite{scikit-learn} library, with unigram whose df is $>= 2$ and $<= 70\%$ of the total documents. We use the BERT model as the contextualize function for our retrieval model, which is initialized with a pretrained dense classifier. Specifically, we fine-tune a $12$ layer BERT-base model with different learning rates for the BERT encoder, BERT pooler and the classifier. The learning rates are $(1e-5$, $1e-4$, $1e-3)$ for Wiki10-31K and $(5e-5$, $1e-4$, $2e-3)$ for the rest datasets. For the negative sampling, we sample batch of 500 instances for Wiki10-31K, and $300$ for EURLex-4K and AmazonCat-13K. We include $10$ hard negatives predicted by the SVM model for each instances. We used learning rate $1e-5$ for fine-tuning the BERT of our retrieval model and $1e-4$ for the pooler and label embeddings. For the pseudo label descriptions, we concatenate the provided label description with the generated the top $20$ keywords. The final length is truncated up to $32$ after BERT tokenization. We use length $16$ of pseudo label description as the default setting for \textsc{DEPL}.

\begin{comment}

\section{Experiments}
\label{sec:experiment}
In our experiments, we probe which Transformer architecture can benefit tail label prediction, which is evaluated by proposed binned macro-based F1.
Also, we analyze the performance of the document representation-based method versus the label attention-based method.

\subsection{Datasets}
\label{sec:dataset}
We use three benchmark datasets: EUR-Lex (4K), Wiki10-31K and AmazonCat-13K.

\subsection{Shallow vs. Deep Transformers}
In the Transformer models, each word interacts with each other using self-attention, gradually forming more abstract representations from layer to layer.
Hence, the embeddings of the last layer encodes the richest semantic meaning of the entire document, which are usually used as the document representation.
In XMTC, recent works extract document representation by pooling over the last layer's embedding~\cite{chang2020taming,ye2020pretrained}, or concatenating the [CLS] embeddings from the last few layers to collect more semantic information\cite{jiang2021lightxml}.

As mentioned in the previous section, less abstract level features are potentially suitable for tail label prediction.
Intuitively, deeper Transformer layers encode the high-level semantic information~\cite{tenney-etal-2019-bert}.
Hence, the first architecture design that we want to explore is the depth of the Transformer model.
For different model depths, we control the number of layers for BERT by $[1, 2, 4, 6, 12]$ layers.

As shown in Fig \ref{fig:attn_cls}, we observe that using shallow layers of BERT benefits label attention-based method, while deep Transformer benefits the document representation-based method.
This can be expected because the Transformer model gradually refines the latent embedding of each word by incorporating more context information via the self-attention mechanism over the layers.
Compared with the upper layers, the word identity will be overwritten by the contextualized information.
Therefore, word level retrieval-based method will perform worse on the upper layers. To the contrary, as more contextualized information is injected into the [CLS] embedding in the upper layers, the global information helps document embedding to encode useful feature for the label classification.

From Table \ref{tab:results}, the performance of the retrieval-based method and the representation-based method are similar, with the retrieval-based method slightly better on P@1 and the representation-based method better on P@5. However, the two models are based on really different feature and underlying mechanism, so we will compare the difference in the next part.

\subsection{Comparison with Baselines}

In this Section, we compare our proposed AttentionXL+BERT with other baselines.

\subsection{Retrieval-based Method vs. Representation-based Method}
Although the two models give similar performance on the micro P@k metric, they are based on very different feature and classification algorithms which is not reflected by the metric. In order to show the difference, we use the F1@5 metric evaluated over different bins of labels according to their frequency in the training data.

The results are shown in Fig. \ref{fig:binned_evaluation}. The horizontal axis represents the label bins according to the number of training instances and the groups are $\{1\sim9, 10\sim 99, \ldots \}$. The vertical axis represents the relative improvement compared with the flat svm baseline. From the figure, we observe that retrieval-based method benefits the lower-frequency (tail) bins, and the representation-based method benefits the high-frequency (head) bins. As most of the training instances concentrate in the head bins, the micro precision metric will be largely impacted by the prediction in those groups. Therefore, the advantage of the retrieval method in the tail bins is shadowed by the micro P@k metric. Especially in the Wiki10-31K dataset, although retrieval based method performs worse on the precision metric, it has a huge advantage on the prediction of tail labels.

\end{comment}

\section{Results}
\label{sec:evaluation}
Our experiments investigate the effectiveness of our model on the tail label prediction as well as its performance on the overall prediction.

\subsection{Results in Tail Label Prediction}
\paragraph{PSP Metric} The evaluation with the PSP metric is shown in \tblref{tab:psp}. We compare our model with the SOTA deep learning methods. Our proposed models \textsc{DEPL } and \textsc{DEPL}+c perform the best on the three benchmark datasets.

Since the Wiki10-31K dataset has more labels and the distribution is more skewed, the observation on the results is very interesting. On the one hand, the most frequent label covers more than $85\%$ of the training instances, so it is easier to predict that label than other lower frequencies labels. However, ranking the high frequency labels at the top doesn't give much gain on the PSP metric.
On the other hand, each instance has an average of $19$ positive labels and ranking the subset of tail labels at the top could boost the PSP score. Since \textsc{DEPL } relies on the semantic matching between the document and label text, it is less affected by the dominating training pairs, and thus the PSP@1, PSP@3 beats the SOTA models by a larger margin. The \textsc{DEPL}+c achieves worse performance on this dataset, because the classification counterpart of the model would benefit more on the head label predictions and tend to rank the head labels at the top.

For the EURLex-4K and AmazonCat-13K, we don't observe to much difference in \textsc{DEPL } and \textsc{DEPL }+c performance, and even \textsc{DEPL }+c can perform better on the EURLex-4K dataset. This maybe due to the improvement of head label predictions which can also boost the overall score in the micro-based metric.

\paragraph{Macro-F1 Metric} Although the PSP metric gives higher weight to the tail labels, it is a micro-averaged metric over the scores of each instance, which can still be affected by the high frequency labels that cover most of the instances. In comparison, the Macro-averaged F1 metric gives each label an equal weight and reflects more of the label level performance. We compare the Macro F1 metric averaged on the tail labels and the results are shown in \figref{fig:tail_eval}.

An interesting observation is that the SVM baseline achieves competitive results on the tail label predictions. We observe that SVM model can outperform all the pre-trained Transformer-based models on the tail label prediction, and outperform the AttentionXML on the Wiki10-31K dataset. We guess the reason is that the SVM utilizes the unsupervised statistical feature as document representation, which potentially suffers less from the data scarcity issue. The empirical result also serves as an evidence that the joint optimization of feature extractor and label embedding is difficult when data is limited. Among the deep learning baselines, the AttentionXML method performs the best on the tail label predictions, beating the SVM on $2$ out of the $3$ benchmark datasets. The reason could be that it utilizes the label to document word attention which is a local feature matching that benefits the tail label prediction.

Our proposed models perform the best on the Macro F1 metric with the \textsc{DEPL } model showing the best performance on all the $3$ benchmark datasets. We attribute the success of model to the retrieval module that focuses on the semantic matching between the document and label text. While the results evaluated in the Macro-averaged F1 metric show similar trend to that in the PSP metric, we do get some different conclusions with different metrics, i.e. the SVM model doesn't stand out under the PSP metric. Since the F1 metric is calculated specifically on the set of tail labels, it provides a more fine-grained result of tail label prediction. In comparison, the PSP metric also reflects the performance on the more common categories.

\begin{table*}[ht!]
    \centering
    \caption{The all-label prediction results of representative classification systems evaluated in the micro-avg P@k metric. The bold phase and underscore highlight the best and second best model performance. }
    \begin{tabular}{cc|ccc|ccc|ccc}
    \toprule
    \multicolumn{2}{c}{} & \multicolumn{3}{c}{EURLex-4K} &  \multicolumn{3}{c}{Wiki10-31K} & \multicolumn{3}{c}{AmazonCat-13K} \\
    \midrule
    & Methods & P@1 & P@3 & P@5 & P@1 & P@3 & P@5 & P@1 & P@3 & P@5\\
    \midrule
    \multirow{4}{*}{published results} & DisMEC  &  83.21 & 70.39 & 58.73 & 84.13 & 74.72 & 65.94 & 93.81 & 79.08 & 64.06 \\
    & PfastreXML & 73.14 & 60.16 & 50.54 &  83.57 & 68.61 & 59.10 & 91.75 & 77.97 & 63.68 \\
    & Parabel & 82.12 & 68.91 & 57.89 & 84.19 & 72.46 & 63.37 & 93.02 & 79.14 & 64.51 \\
    & Bonsai & 82.30 & 69.55 & 58.35 &  84.52 & 73.76 & 64.69 &  92.98 & 79.13 & 64.46 \\
    \midrule
     \multirow{6}{*}{replicated results} & AttentionXML & 85.12 & 72.80 & 61.01  & 86.46 & \underline{77.22} & 67.98  & 95.53 & 82.03 & 67.00 \\
    & X-Transformer & 85.46 & 72.87 & 60.79 & 87.12 & 76.51 & 66.69 & \underline{95.75} & \bf 82.46 & \underline{67.22} \\
    & XLNet-APLC & \bf 86.83 & \bf 74.34 & \underline{61.94} & \bf 88.99 & \bf 78.79 & \bf 69.79 & 94.56 & 79.78 & 64.59\\

    & LightXML & 86.12 & \underline{73.87} & 61.67 & 87.39 & 77.02 & \underline{68.21} & 94.61 & 79.83 & 64.45\\

    & SVM  & 83.44 & 70.62 & 59.08 & 84.61 & 74.64 & 65.89 & 93.20 & 78.89 & 64.14 \\
    & BERT   & 84.72 & 71.66 & 59.12 & 87.60 & 76.74 & 67.03 & 94.26 & 79.63 & 64.39 \\
    \midrule

     \multirow{2}{*}{our model results} & DEPL & 85.38 &  71.86 & 59.91 & 84.54 & 73.44 & 64.75 & 94.86 & 80.85 & 64.55 \\
    & DEPL+c & \underline{86.43} & 73.77 & \bf 62.19 & 87.32 & 77.05 & 67.39 & \bf 96.16 & \underline{82.23} & \bf 67.65 \\
    \bottomrule
    \end{tabular}
    \label{tab:micro_all}
\end{table*}

\begin{table*}[th!]
    \small
    \centering
    \caption{Examples of SVM generated keywords for tail labels from Wiki10-31K. The classifier is trained with only one positive training instance per label. For each label, we show the top $20$ extracted keywords. We manually highlights the meaningful keywords in red. \label{tab:description}}
    \begin{tabular}{cc|c}
    \toprule
    \bf Label Text & \bf \#training instance & \bf Top Keywords \\
    \midrule
    phase4  & 1 & \makecell{\high{trials} \high{clinical} protection personal directive processed data trial \high{drug} phase eu \\ processing \high{patients} sponsor \high{controller} legislation regulation art investigator \high{study} } \\
    \hline
    ensemble & 1 &\makecell{ \high{boosting} kurtz ferrell weak \high{algorithms} \high{learners} \high{misclassified learner} kearns \high{ensemble} \\ charges bioterrorism indictment doj indict cae correlated 2004 \high{reweighted} boost } \\
    \hline
    kakuro & 1 & \makecell{ \high{nikoli} kakuro \high{puzzles crossword clues entries entry values sums cells} \\ cross \high{digits} dell \high{solvers} racehorse guineas aa3aa digit clue kaji } \\
    \bottomrule
    \end{tabular}
\end{table*}

\subsection{Results in All-label Prediction}
The performance of model evaluated on the micro-averaged P@k metric is reported in \tblref{tab:micro_all}. Our model is compared against the SOTA sparse and dense classifiers. The results on the EURLex-4K and AmazonCat-13K shows that \textsc{DEPL}+c achieves the best or second best performance compared to the all the SOTA models. On the Wiki10-31K dataset, our model performs worse than the other neural baseline, because the retrieval-based models have lower score evaluated on the P@k metric.

By comparing the overall performance with the tail label performance, we uncover a trade-off between the head label and tail label prediction. While our retrieval-based models achieve the best performance on the tail label evaluation on the Wiki10-31K dataset, it is worse under the micro-averaged P@5 metric, which could be dominated by the head labels. We want to emphasis that over $26,545$ ($88.65\%$) labels in the Wiki10-31K dataset belong to the tail labels with less than $10$ training instances, constituting a majority of the label space. The overall classification precision (P@k) only reflects a part of the success of a classification system, and the tail label evaluation is yet another part.

From the evaluation, we observe that the \textsc{DEPL}+c outperforms the retrieval-based counterpart \textsc{DEPL } and the BERT model as the baseline classifier. This shows that enhancing the classification system with the retrieval model improves the overall performance. The reason is that the dense classifier learns better representation when the training instances are abundant, while the retrieval system is better at matching the semantic of document and label text. Each of the modules captures a certain aspect of the data heuristic for text classification and a combination of them by sharing the BERT encoder yields better performance.

The sparse classifiers generally underperform the neural models and are comparable to our implement of SVM. We observe that \textsc{DEPL } can outperform the sparse models, even if the pseudo labels are extracted from the SVM classifier. The reason is that neural retrieval model can additionally leverage the keyword semantic information and correlation of them, which is ignored in the SVM classifier.

\begin{figure}[th!]
     \centering
     \includegraphics[width=\linewidth]{img/ablation_label.pdf}
     \caption{The ablation-test results of \textsc{DEPL } in Macro-averaged F1@k metric with varying length of pseudo label descriptions. }
     \label{fig:tail_ablation}
\end{figure}

\begin{table}[ht!]
    \centering
    \small
    \setlength{\tabcolsep}{3.5pt}
    \caption{Ablation-test results of \textsc{DEPL } under different training conditions.\label{tab:ablation}}
    \begin{adjustbox}{width=\columnwidth,center}
    \begin{tabular}{l|ccc|ccc}
    \toprule
    Methods & P@1 & P@3 & P@5 & PSP@1 & PSP@3 & PSP@5 \\
    \midrule
    \multicolumn{7}{c}{EUR-Lex}   \\
    \midrule
    DE-ret & -1.34 & -1.18 & -1.16 & -3.2 & -2.11 &  +0.18 \\
    w/o pre-train & -6.81 & -6.72 & -6.16 & -6.87 & -7.09 & -5.87  \\
    w/o neg & -2.52 & -2.63 & -2.2 & -3.59 & -3.66 & -1.9 \\
    5 hard negative &  -1.55 & -1.19 & -1.12 & -3.57 & -2.98 & -1.32  \\
    \midrule
    \multicolumn{7}{c}{Wiki10-31K}   \\
    \midrule
    DE-ret & -3.31 &  -7.35 & -10.74 & -5.43 & -4.43 & -4.55 \\
    w/o pre-train & -4.72 &  -8.3 & -10.9  & -1.56 & -1.36 & -1.27 \\
    w/o hard negative & -1.91 &  -5.54 & -3.73 & -0.25 & -0.53 & -0.72 \\
    5 hard negative  &  -0.71 & -2.77 & -2.96 & -0.32 & -0.35 & -0.27  \\
    \bottomrule
    \end{tabular}
    \end{adjustbox}
\end{table}

\subsection{Ablation Study}
\paragraph{Pseudo Label Description}
In \figref{fig:tail_ablation}, we conduct an ablation test on the length of the pseudo label and the performance is measured by Macro-avg F1@k. The BERT classifier is included as a baseline with no label text information (length equals $0$). As we observe that the longer description of length $16$ performs the better, but when length is $32$, the performance doesn't increase as the text may become noisy with more unrelated keywords.

The DE-ret model is a pure retrieval baseline (avg length $3$) with only the label name. While it achieves good performance on the EURLex-4K and AmazonCat-13K datasets, it still performs poorly on the Wiki10-31K dataset. Another evidence is shown in \tblref{tab:ablation}, where the performance of DE-ret drops more significantly on the Wiki10-31K dataset. That shows that generating the keywords from the sparse classifier can enhance the text quality. Furthermore, the generated text allows \textsc{DEPL } to use the semantic information of the label keywords, which is ignored in the SVM model. This could be another reason why our model performs better than the SVM baseline on the Wiki10-31K dataset.

In \tblref{tab:description}, we pick the illustrative examples of the SVM generated keywords trained on the Wiki10-31K dataset for labels with only $1$ training example. We manually highlight the meaningful terms related to the label meaning. For example, the label name \textit{phase4} is ambiguous, whose meaning needs to be inferred from the corresponding document. From the keywords \textit{trial, clinical, drug ...}, we can understand it is about medical testing phase and the keywords can enhance the label semantic. In another example, \textit{kakuro} is a Japanese logic puzzle known as a mathematical crossword and the game play involves in adding number in the cells. Generating a description for \textit{kakuro} requires the background knowledge, but the keywords automatically learned from the sparse classifier provide the key concepts. Although not all the keywords can provide rich semantics to complement the original label name, they may serve as a context for the label to make it more distinguishable from others.

\paragraph{Model Pre-training} We fine-tune our retrieval model on a pre-trained neural classifier (BERT) and \tblref{tab:ablation} shows that without using the pre-trained model, there is a significant drop in the precision and PSP metrics.
\paragraph{Negative Sampling}
We used the top negative predictions by the SVM model as the choice of hard negative labels. By default, we use $10$ hard negatives for each instance in the batch. In \tblref{tab:ablation}, we observe a performance drop when no hard negatives or only $5$ hard negatives are used for training.

redpajama_set_name: RedPajamaArXiv