The Emerging Trends of Multi-Label Learning
多标签学习的新兴趋势

To deal with many labels, [49] assume that label vectors have a little support. In other words, each label vector can be projected into a lower dimensional compressed label space, which can be deemed as encoding. A regression is then learned for each compressed label. Lastly, the compressed sensing technique is used to decode the labels from the regression outputs of each testing instance. Many embedding based works have recently been developed in this learning paradigm. These works mainly differ in compression and decompression methods such as canonical correlation analysis (CCA) [47] and bloom filters [50]. Amongst them, SLEEC [1] is one of the seminal embedding methods in XMLC due to its simplicity and promising experimental results [1].
为了处理许多标签，[49] 假设标签向量有一点支持。换句话说，每个标签向量都可以投影到一个低维的压缩标签空间中，这可以被认为是编码。然后，为每个压缩标签学习回归。最后，使用压缩传感技术从每个测试实例的回归输出中解码标签。在这种学习范式中，最近开发了许多基于嵌入的作品。这些工作主要在压缩和解压缩方法上有所不同，例如典型相关分析 （CCA） [47] 和布隆滤波器 [50]。其中，SLEEC [1] 是 XMLC 中开创性的嵌入方法之一，因为它简单且实验结果有前途 [1]。

SLEEC learns low dimensional embeddings which non-linearly capture label correlations by preserving the pairwise distances between only the closest (rather than all) label vectors. Regressors are then trained in the embedding space. SLEEC uses a $k$-nearest neighbor ($k$NN) classifier in the embedding space for prediction.
SLEEC 学习低维嵌入，通过保持成对距离来非线性地捕获标签相关性 仅在最近的（而不是所有）标签向量之间。然后在嵌入空间中训练回归器。SLEEC 在嵌入空间中使用 $k$ 最近邻 （ $k$ NN） 分类器进行预测。

Assume $x_{i}\in\mathbb{R}^{d\times 1}$ is a real vector representing an input or instance (feature), $y_{i}\in\{0,1\}^{L\times 1}$ is the corresponding output or label vector $(i\in\{1,\ldots,n\})$. $n$ denotes the number of training data. The input matrix is $X=[x_{1},\ldots,x_{n}]\in\mathbb{R}^{d\times n}$ and the output matrix is $Y=[y_{1},\ldots,y_{n}]\in\{0,1\}^{L\times n}$. SLEEC maps the label vector $y_{i}$ to $\varpi$-dimensional vector $z_{i}\in\mathbb{R}^{\varpi\times 1}$ ($\varpi<L$ is a small constant) and learns a set of regressors $V\in\mathbb{R}^{\varpi\times d}$ s.t. $z_{i}\approx Vx_{i},\forall i\in\{1,\ldots,n\}$. During the prediction, for a testing instance $x$, SLEEC first computes its embedding $Vx$ and then perform $k$NN over the set $[Vx_{1},\ldots,Vx_{n}]$. We denote the transpose of the vector/matrix by the superscript ^T and the logarithms to base 2 by $\log$. Let $||\cdot||_{F}$ and $||\cdot||_{1}$ represent the Frobenius norm and $\ell_{1}$ norm of a matrix.
假设 $x_{i}\in\mathbb{R}^{d\times 1}$ 是表示输入或实例（特征）的实向量， $y_{i}\in\{0,1\}^{L\times 1}$ 是相应的输出或标签向量 $(i\in\{1,\ldots,n\})$ 。 $n$ 表示训练数据的数量。输入矩阵为 $X=[x_{1},\ldots,x_{n}]\in\mathbb{R}^{d\times n}$ ，输出矩阵为 $Y=[y_{1},\ldots,y_{n}]\in\{0,1\}^{L\times n}$ 。SLEEC 将标签向量 $y_{i}$ 映射到 $\varpi$ -维向量 $z_{i}\in\mathbb{R}^{\varpi\times 1}$ （ $\varpi<L$ 是一个小常数）并学习一组回归器 $V\in\mathbb{R}^{\varpi\times d}$ s.t. $z_{i}\approx Vx_{i},\forall i\in\{1,\ldots,n\}$ .在预测期间，对于测试实例 $x$ ，SLEEC 首先计算其嵌入 $Vx$ ，然后对 set $[Vx_{1},\ldots,Vx_{n}]$ 执行 $k$ NN 。我们用上标 ^T 表示向量/矩阵的转置，用 表示对数到以 2 为底的对数。 $\log$ 设 $||\cdot||_{F}$ 和 $||\cdot||_{1}$ 表示矩阵的 Frobenius 范数和 $\ell_{1}$ 范数。

SLEEC aims to learn a embedding matrix $Z=[z_{1},\ldots,z_{n}]\in\mathbb{R}^{\varpi\times n}$ through the following formula:
SLEEC 旨在通过以下公式学习嵌入矩阵 $Z=[z_{1},\ldots,z_{n}]\in\mathbb{R}^{\varpi\times n}$ ：

where the index set $\Omega$ denotes the set of neighbors: $(i,j)\in\Omega$ iff $j\in\mathcal{N}_{i}$. $\mathcal{N}_{i}$ denotes a set of nearest neighbors of $i$. $P_{\Omega}(\cdot)$ is defined as:
其中 index set $\Omega$ 表示邻居集： $(i,j)\in\Omega$ iff $j\in\mathcal{N}_{i}$ 。 $\mathcal{N}_{i}$ 表示 的 $i$ 一组最近邻。 $P_{\Omega}(\cdot)$ 定义为：

Based on embedding matrix $Z$, SLEEC minimizes the following objective with $\ell_{1}$ and $\ell_{2}$ regularization to find regressors $V$, which is able to reduce the prediction time and the model size, and avoid overfitting.
基于嵌入矩阵 $Z$ ，SLEEC 最小化以下目标 $\ell_{1}$ 和 $\ell_{2}$ 正则化 以查找回归器 $V$ ，这能够减少预测时间和模型大小，并避免过拟合。

where $\mu>0$ and $\lambda>0$ are the regularization parameters.
其中 $\mu>0$ 和 $\lambda>0$ 是正则化参数。

To scale to large-scale data sets, SLEEC clusters the training set into smaller local region just based on features and does not consider label information. Therefore, the instances that have similar labels are not guaranteed to be split into the same region. This partitioning may affect the quality of embeddings learned in SLEEC.
为了扩展到大规模数据集，SLEEC 仅根据特征将训练集聚类到较小的局部区域，而不考虑标签信息。因此，不保证将标签相似的实例拆分到同一区域。这种分区可能会影响在 SLEEC 中学习的嵌入的质量。

Many methods have been developed to address this issue. For example, AnnexML [12] shows a novel graph embedding method based on the k-nearest neighbor graph (KNNG). AnnexML aims to construct the KNNG of label vectors in the embedding space to improve both the prediction accuracy and speed of the k-nearest neighbor classifier. DEFRAG [51] represents each feature $j\in[d]$ as an $L$-dimensional vector $q^{j}=\sum_{i=1}^{n}x_{i}^{j}y_{i}$, which is a weighted aggregate of the label vectors of data points where the feature $j$ is non-zero. After creating these representative vectors, DEFRAG performs hierarchical clustering on them to obtain feature clusters, and then performs agglomeration by summing up the coordinates of the feature vectors within a cluster. [51] shows that DEFRAG offers faster and better performance.
已经开发了许多方法来解决这个问题。例如，AnnexML [12] 展示了一种基于 k 最近邻图 （KNNG） 的新型图嵌入方法。AnnexML 旨在构建嵌入空间中标签向量的 KNNG，以提高 k 最近邻分类器的预测准确性和速度。DEFRAG [51] 将每个特征 $j\in[d]$ 表示为一个 $L$ -dimensional vector $q^{j}=\sum_{i=1}^{n}x_{i}^{j}y_{i}$ ，它是特征为非零的数据点 $j$ 标签向量的加权聚合。创建这些代表性向量后，DEFRAG 对它们进行分层聚类以获得特征簇，然后通过汇总簇内特征向量的坐标来进行集聚。[51] 表明 DEFRAG 提供了更快、更好的性能。

Word embeddings have been successfully used for learning non-linear representations of text data for natural language processing (NLP) tasks, such as understanding word and document semantics and classifying documents. Recently, [52] first proposes to use word embedding techniques to learn the label embedding of instances. [52] treats each instance as a “word”, and define the “context” as k-nearest neighbors of a given instance in the space formed by the training label vectors $y_{i}$. Based on Skip Gram Negative Sampling (SGNS) technique, [52] learns embeddings $z_{1},\ldots,z_{n}$ through the following formula:
单词嵌入已成功用于学习自然语言处理 （NLP） 任务的文本数据的非线性表示，例如理解单词和文档语义以及对文档进行分类。最近，[52] 首次提出使用词嵌入技术来学习实例的标签嵌入。[52] 将每个实例视为一个“单词”，并将“上下文”定义为由训练标签向量 $y_{i}$ 形成的空间中给定实例的 k 个最近邻。基于跳跃革兰氏负采样 （SGNS） 技术，[52] $z_{1},\ldots,z_{n}$ 通过以下公式学习嵌入：

where $j^{\prime}\in\{1,\ldots,n\}$, $\sigma(\cdot)$ is a sigmoid function, $\langle\cdot,\cdot\rangle$ denotes the inner product and $C$ is a constant. After learning label embeddings $z_{1},\ldots,z_{n}$, [52] follows the learning algorithm of SLEEC to learn $V$ and make the prediction. [52] shows competitive prediction accuracies compared to state-of-the-art embedding methods, and provides the new insight for XMLC from the popular word2vec in NLP, which may open a new line of research.
其中 $j^{\prime}\in\{1,\ldots,n\}$ ，是 $\sigma(\cdot)$ sigmoid 函数， $\langle\cdot,\cdot\rangle$ 表示内积， $C$ 并且是一个常数。在学习标签嵌入后 $z_{1},\ldots,z_{n}$ ，[52] 遵循 SLEEC 的学习算法来学习和 $V$ 做出预测。[52] 显示了与最先进的嵌入方法相比具有竞争力的预测准确性，并从 NLP 中流行的 word2vec 为 XMLC 提供了新的见解，这可能会开辟一条新的研究路线。

The embedding matrix $Z=[z_{1},\ldots,z_{n}]\in\mathbb{R}^{\varpi\times n}$ of existing embedding methods is in real space. Hence we need to use regressors for training and may involve solving expensive optimization problems. To break this limitation, many references leverage coding technique for efficiently training the model. For example, based on Bloom filters [53], a well-known space-efficient randomized data structure designed for approximate membership testing, [50] designs a simple scheme to select the $k$ representative bits for labels for training and proposes a robust decoding algorithm for prediction. However, Bloom filters may yield many false positives.
现有嵌入方法的嵌入矩阵 $Z=[z_{1},\ldots,z_{n}]\in\mathbb{R}^{\varpi\times n}$ 位于真实空间中。因此，我们需要使用回归器进行训练，并且可能涉及解决昂贵的优化问题。为了打破这一限制，许多参考文献利用编码技术来有效地训练模型。例如，基于 Bloom filters [53]（一种著名的用于近似隶属度测试的节省空间的随机数据结构）[50]，设计了一个简单的方案来选择用于训练的标签的 $k$ 代表性位，并提出了一种用于预测的稳健解码算法。但是，Bloom 筛选器可能会产生许多误报。

To address this issue, [54] transforms MLC to a popular group testing problem. In the group testing problem, one wish to identify a small number $k$ of defective elements in a population of large size $L$. The idea is to test the items in groups with the premise that most tests will return negative results. Only few $\varpi<L$ tests are needed to detect the $k$ defective elements. [54] trains $\varpi$ binary classifiers on $z_{i}$ and learn to test whether the data belongs to a group (of labels) or not, and then uses a simple inexpensive decoding scheme to recover the label vector from the predictions of the classifiers. Recently, [55] develops a novel sparse coding tree framework for XMLC based on Huffman coding and Shannon-Fano coding. [50, 54, 55] introduce the coding theory into MLC which is very novel and worth further research and exploration in this direction.
为了解决这个问题，[54] 将 MLC 转换为一个流行的群测试问题。在组测试问题中，人们希望在大规模 $L$ 的总体中识别少量有缺陷 $k$ 的元素。这个想法是分组测试项目，前提是大多数测试将返回阴性结果。只需进行少量 $\varpi<L$ 测试即可检测出有缺陷的 $k$ 元件。[54] 训练 $\varpi$ $z_{i}$ 二元分类器并学习测试数据是否属于一组（标签），然后使用一种简单廉价的解码方案从分类器的预测中恢复标签向量。最近，[55] 基于 Huffman 编码和 Shannon-Fano 编码为 XMLC 开发了一种新的稀疏编码树框架。[50， 54， 55] 将编码理论引入 MLC 中，这是非常新颖的，值得在这个方向上进一步研究和探索。

Remark. Embedding methods are the most popular strategies for addressing XMLC. SLEEC is a seminal work among them and recommended for the beginners to try. The major limitation of existing embedding methods is that the correlations between the input and output are ignored, such that their learned embeddings are not well aligned, which leads to degradation in prediction performance. How to build an embedding space that can preserve the relations between the input and output is an important research topic in the future. For example, [30, 56, 57] explore the correlations between the input and output. They propose to jointly learn a semantic common subspace and view-specific mappings within one framework. The semantic similarity structure among the embeddings is further preserved, ensuring that close embeddings share similar labels. Another limitation of existing embedding methods is that both the training and testing time complexity are too high (See Table I). Some techniques, such as random projection, hashing and parallelization, may be able to accelerate the training and testing process. Tree-based methods are able to obtain fast testing speed, which is discussed in the following paragraph.
备注。嵌入方法是解决 XMLC 的最常用策略。SLEEC 是其中的开创性作品，建议初学者尝试。现有嵌入方法的主要局限性是忽略了输入和输出之间的相关性，因此它们学习的嵌入不能很好地对齐，从而导致预测性能下降。如何构建一个能够保持输入和输出之间关系的嵌入空间是未来重要的研究课题。例如，[30， 56， 57] 探索输入和输出之间的相关性。他们提议在一个框架中共同学习语义公共子空间和特定于视图的映射。嵌入之间的语义相似性结构被进一步保留，确保紧密的嵌入共享相似的标签。现有嵌入方法的另一个限制是训练和测试时间的复杂度都太高（见表 I）。一些技术（例如随机投影、哈希和并行化）可能能够加速训练和测试过程。基于树的方法能够获得快速的测试速度，这将在下一段中讨论。

For tree-based methods, the original large-scale problem is divided into a sequence of small-scale subproblems by hierarchically partitioning the instance set or the label set. The root node is initialized to contain the entire set. A partitioning formulation is then optimized to partition a set in a node into a fixed number $k$ of subsets which are linked to $k$ child nodes. Nodes are recursively decomposed until a stopping condition is checked on the subsets. Each node involves two optimization problems: optimizing the partition criterion, and defining a condition or building a classifier on the feature space to decide which child node an instance belongs to. In the prediction phase, an instance is passed down the tree until it reaches a leaf (instance tree) or several leaves (label tree). For a label tree, the reached leaves contain the predicted labels. For an instance tree, the prediction is made by a classifier trained on the instances in the leaf node. Thus, the main advantage of tree-based methods is that the prediction costs are sub-linear or even logarithmic if the tree is balanced.
对于基于树的方法，通过对实例集或标签集进行分层分区，将原始的大规模问题划分为一系列小规模的子问题。根节点初始化为包含整个集。然后优化分区公式，将节点中的集分区为固定数量的 $k$ 子集，这些子集链接到 $k$ 子节点。节点将递归分解，直到在子集上检查停止条件。每个节点都涉及两个优化问题：优化分区标准，以及定义条件或在特征空间上构建分类器来决定实例属于哪个子节点。在预测阶段，实例沿树向下传递，直到到达一个叶子（实例树）或多个叶子（标签树）。对于标签树，到达的叶子包含预测的标签。对于实例树，预测是由在叶节点中的实例上训练的分类器进行的。因此，基于树的方法的主要优点是，如果树是平衡的，预测成本是亚线性的，甚至是对数的。

FastXML [6] presents to learn the hierarchy by optimizing the ranking loss function, normalized Discounted Cumulative Gain (nDCG). nDCG brings two main benefits to XMLC. Firstly, nDCG is a measurement which is sensitive to ranking and relevance and therefore ensures that the relevant positive labels are predicted with ranks that are as high as possible. This cannot be guaranteed by rank insensitive measures such as the Gini index or the clustering error. Second, by being rank sensitive, nDCG can be optimized across all $L$ labels at the current node thereby ensuring that the local optimization is not myopic. The experiments show that nDCG is more suitable for extreme multi-label learning.
FastXML [6] 通过优化排名损失函数、标准化折扣累积增益 （nDCG） 来学习层次结构。nDCG 为 XMLC 带来了两个主要好处。首先，nDCG 是一种对排名和相关性敏感的测量方法，因此可以确保以尽可能高的排名预测相关的正面标签。这不能通过不区分排名的度量值（如 Gini 指数或聚集误差）来保证。其次，通过对秩敏感，nDCG 可以在当前节点的所有 $L$ 标签上进行优化，从而确保局部优化不是短视的。实验表明，nDCG 更适合于极端的多标签学习。

Based on FastXML, PfastreXML [7] studies how to improve the prediction accuracy of tail labels. The labels in XMLC follow a power law distribution. Infrequently occurring labels usually convey more information, but have little training data and are harder to predict than frequently occurring ones. PfastXML improves FastXML by replacing the nDCG loss with its unbiased propensity scored variant, and assigns higher rewards for predicting accurate tail labels. Moreover, PfastreXML re-ranks PfastXML’s predictions using tail label classifiers. [7] shows that PfastreXML achieves promising performance in predicting tail labels and successfully applies to tagging, recommendation and ranking problems. SwiftXML [9] maintains all the scaling properties of PfastreXML, but improves the prediction accuracy of PfastreXML by considering more information about revealed item preferences and item features. SwiftXML proposes a novel node partitioning function by optimizing two separating hyperplanes in the user and item feature spaces respectively. Experiments on tagging on Wikipedia and item-to-item recommendation on Amazon reveal that SwiftXML is more accurate than leading extreme classifiers by 14%.
基于 FastXML，PfastreXML [7] 研究如何提高尾部标签的预测准确性。XMLC 中的标签遵循幂律分布。不经常出现的标签通常传达更多信息，但训练数据很少，并且比频繁出现的标签更难预测。PfastXML 通过将 nDCG 损失替换为其无偏倾向评分变体来改进 FastXML，并为预测准确的尾部标签分配更高的奖励。此外，PfastreXML 使用尾部标签分类器对 PfastXML 的预测进行重新排序。[7] 表明 PfastreXML 在预测尾部标签方面取得了有希望的性能，并成功地应用于标记、推荐和排名问题。SwiftXML [9] 保留了 PfastreXML 的所有缩放属性，但通过考虑有关显示的项目首选项和项目功能的更多信息，提高了 PfastreXML 的预测准确性。SwiftXML 通过在 user 和 item 特征空间中分别优化两个分离超平面，提出了一种新的节点分区函数。Wikipedia 上的标记实验和 Amazon 上的项目到项目推荐表明，SwiftXML 比领先的极端分类器准确 14%。

FastXML, PfastreXML and SwiftXML have studied the ranking-based measures such as nDCG and its variants. Recently, [8] focuses on F-measure, which is a commonly used performance measure in multi-label classification as well as other fields, such as information retrieval and natural language processing. [8] proposes a novel sparse probability estimates (SPEs) to reduce the complexity of threshold tuning in XMLC. Then, they develop three algorithms for maximizing the F-measure in the Empirical Utility Maximization (EUM) framework by using SPEs. Moreover, Probabilistic label trees (PLTs) and FastXML are discussed for computing SPEs. Recently, the theory in [10] shows that the pick-one-label is inconsistent with respect to the Precision@$k$, and PLTs model can get zero regret (i.e., it is consistent) in terms of marginal probability estimation and Precision@$k$ in the multi-label setting. Inspired by [10], [61] further studies the consistency of other reduction strategies based on a different Recall@$k$ metric.
FastXML、PfastreXML 和 SwiftXML 研究了基于排名的衡量标准，例如 nDCG 及其变体。最近，[8] 专注于 F-measure，这是多标签分类以及其他领域（如信息检索和自然语言处理）中常用的性能度量。[8] 提出了一种新的稀疏概率估计 （SPE） 来降低 XMLC 中阈值调整的复杂性。然后，他们开发了三种算法，用于使用 SPE 在经验效用最大化 （EUM） 框架中最大化 F 度量。此外，还讨论了用于计算 SPE 的概率标签树 （PLT） 和 FastXML。最近，[10] 中的理论表明，选择单标签相对于 Precision@ 不一致 $k$ ，PLTs 模型在边际概率估计和多标签设置 $k$ 中的Precision@方面可以获得零遗憾（即它是一致的）。受 [10] 的启发，[61] 进一步研究了基于不同 Recall@ $k$ 度量的其他还原策略的一致性。

Remark. Tree-based methods are the efficient strategy for addressing XMLC with the logarithmic dependence to the number of labels (See Table I). FastXML is a popular method and recommended for the practitioners. However, one of the major problems for tree-based methods, such as FastXML, PfastreXML and SwiftXML, is that they involve complex non-convex optimization problem at each node. How to obtain cheap and scalable tree structure is an important research topic in the future. For example, GBDT-SPARSE [58] studies the gradient boosted decision trees (GBDT) for XMLC. In each node, the feature is firstly projected into a low-dimensional space and then a simple inexact search strategy is used to find a good split. They significantly reduce the training and prediction time and model size of GBDT to make it suitable for XMLC. CRAFTML [62] tries to use fast partitioning strategies and exploit random forest algorithm. CRAFTML first randomly projects the feature and label into lower dimensional spaces. A $k$-means algorithm is then used in the projected labels to partition the instances into $k$ temporary subsets. Moreover, GBDT-SPARSE and CRAFTML also open the way to parallelization, which are able to motivate further research.
备注。基于树的方法是一种有效的策略，用于对标签数量的对数依赖性 XMLC（请参阅表 I）。FastXML 是一种流行的方法，推荐给从业者。然而，基于树的方法（如 FastXML、PfastreXML 和 SwiftXML）的主要问题之一是它们在每个节点都涉及复杂的非凸优化问题。如何获得廉价且可扩展的树结构是未来重要的研究课题。例如，GBDT-SPARSE [58] 研究了 XMLC 的梯度提升决策树 （GBDT）。在每个节点中，首先将特征投影到低维空间中，然后使用简单的不精确搜索策略来找到一个好的分割。它们显著减少了 GBDT 的训练和预测时间以及模型大小，使其适用于 XMLC。CRAFTML [62] 尝试使用快速分区策略并利用随机森林算法。CRAFTML 首先将特征和标签随机投影到低维空间中。然后， $k$ 在投影的标签中使用 -means 算法将实例划分为 $k$ 临时子集。此外，GBDT-SPARSE 和 CRAFTML 也为并行化开辟了道路，这能够激励进一步的研究。

One-vs-all (OVA) methods are one of the most popular strategies for multi-label classification which independently trains a binary classifier for each label. However, this technique suffers two major limitations for XMLC: 1) Training one-vs-all classifiers for XMLC problems using off-the-shelf solvers such as Liblinear can be infeasible for computation and memory. 2) The model size for XMLC data set can be extremely large, which leads to slow prediction. Recently, many works have been developed to address the above issues of the one-vs-all methods in XMLC.
一对多 （OVA） 方法是最流行的多标签分类策略之一，它为每个标签独立训练一个二进制分类器。但是，该技术对 XMLC 有两个主要限制：1） 使用现成的求解器（如 Liblinear）为 XMLC 问题训练一对多分类器对于计算和内存来说可能不可行。2） XMLC 数据集的模型大小可能非常大，这会导致预测速度变慢。最近，已经开发了许多工作来解决 XMLC 中 one-vo-all 方法的上述问题。

By exploiting the sparsity of the data, some sub-linear algorithms are proposed to adapt one-vs-all methods in the extreme classification setting. For example, PD-Sparse [59] proposes to minimize the separation ranking loss and $\ell_{1}$ penalty in an Empirical Risk Minimization (ERM) framework for XMLC. The separation ranking loss penalizes the prediction on an instance by the highest response from the set of negative labels minus the lowest response from the set of positive labels. PD-Sparse obtains an extremely sparse solution both in primal and in dual with the sub-linear time cost, while yields higher accuracy than SLEEC, FastXML and some other XMLC methods. By introducing separable loss functions, PPDSparse [3] parallelizes PD-Sparse with sub-linear algorithms to scale out the training. PPDSparse can also reduce the memory cost of PDSparse by orders of magnitude due to the separation of training for each label. DiSMEC [2] also presents a sparse model with a parameter thresholding strategy, and employs a double layer of parallelization to scale one-vs-all methods for problems involving hundreds of thousand labels. ProXML [63] proposes to use $\ell_{1}$-regularized Hamming loss to address the tail label issues, and reveals that minimizing one-vs-all method based on Hamming loss works well for tail-label prediction in XMLC based on the graph theory.
通过利用数据的稀疏性，提出了一些亚线性算法来适应极端分类设置中的一对多方法。例如，PD-Sparse [59] 提议在 XMLC 的经验风险最小化 （ERM） 框架中最小化分离排序损失和 $\ell_{1}$ 惩罚。分离排名损失根据负标签集的最高响应减去正标签集的最低响应来惩罚对实例的预测。PD-Sparse 在初数和对偶中都获得了极稀疏的解，具有次线性时间成本，同时比 SLEEC、FastXML 和其他一些 XMLC 方法产生更高的精度。通过引入可分离损失函数， PPDSparse [3] 使用次线性算法并行化 PD-Sparse 以扩展训练。由于每个标签的训练分离，PPDSparse 还可以将 PDSparse 的内存成本降低几个数量级。DiSMEC [2] 还提出了一个具有参数阈值策略的稀疏模型，并采用双层并行化来扩展涉及数十万个标签的问题的一对多方法。ProXML [63] 建议使用 $\ell_{1}$ 正则化汉明损失来解决尾部标签问题，并揭示了基于汉明损失的最小化一对多方法对于基于图论的 XMLC 中的尾部标签预测非常有效。

PD-Sparse, PPDSparse, DiSMEC and ProXML have obtained high prediction accuracies and low model sizes. However, they still train a separate linear classifier for each label and linear scan every single label to decide whether it is relevant or not. Thus the training and testing cost of these methods grow linearly with the number of labels. Some advanced methods are presented to address this issue. For example, to reduce the linear prediction cost of one-vs-all methods, [60] proposes to predict on a small set of labels, which is generated by projecting a test instance on a filtering line, and retaining only the labels that have training instances in the vicinity of this projection. The candidate label set should keep most of the true labels of the testing instances, and be as small as possible. They train the label filters by optimizing these two principles as a mixed integer problem. The label filters can reduce the testing time of existing XMLC classifiers by orders of magnitude, while yields comparable prediction accuracy. [60] shows an interesting technique to find a small number of potentially relevant labels, instead of going through a very long list of labels. How to use label filters to speed up the training time is left as an open problem.
PD-Sparse 、 PPDSparse 、 DiSMEC 和 ProXML 获得了高预测精度和低模型大小。但是，他们仍然为每个标签训练一个单独的线性分类器，并线性扫描每个标签以确定它是否相关。因此，这些方法的训练和测试成本随着标签数量的增加而线性增长。提出了一些高级方法来解决此问题。例如，为了降低一对多方法的线性预测成本，[60] 建议对一小部分标签进行预测，这是通过将测试实例投影到过滤线上生成的，并且只保留在此投影附近具有训练实例的标签。候选标签集应保留测试实例的大部分真实标签，并尽可能小。他们通过将这两个原则优化为混合整数问题来训练标签过滤器。标签过滤器可以将现有 XMLC 分类器的测试时间减少几个数量级，同时产生相当的预测准确性。[60] 展示了一种有趣的技术，可以查找少量可能相关的标签，而不是遍历很长的标签列表。如何使用标签过滤器来加快训练时间是一个悬而未决的问题。

Parabel [4] reduces training time of one-vs-all methods from $O(ndL)$ to $O((nd\log L)/L)$ by learning balanced binary label trees based on an efficient and informative label representation. They also present a probabilistic hierarchical multi-label model for generalizing hierarchical softmax to the multi-label setting. The logarithmic prediction algorithm is also proposed for dealing with XMLC. Experiments show that Parabel could be orders of magnitude faster at training and prediction compared to the state-of-the-art one-vs-all extreme classifiers. However, Parabel is not accurate in low-dimension data set, because Parabel can not guarantee that similar labels are divided into the same group, and the error will be propagated in the deep trees. To reduce the error propagation, Bonsai [64] shows a shallow $k$-ary label tree structure with generalized label representation. A novel negative sampling technique is also presented in Slice [5] to improve the prediction accuracy for low-dimensional dense feature representations. Slice is able to cut down the training time cost of one-vs-all methods from linear to $O(nd\log L)$ by training classifier on only $O(n/L\log L)$ of the most confusing negative examples rather than on all $n$ training set. Slice employs generative model to estimate $O(n/L\log L)$ negative examples for each label based on approximate nearest neighbor search (ANNS) in time $O((n+L)d\log L)$, and conduct the prediction on $O(\log L)$ of the most probable labels for each testing data. Slice is up to 15% more accurate than Parabel, and able to scale to 100 million labels and 240 million training points. The experiments in [5] show that negative sampling is a powerful tool in XMLC, and the performance gain of some advanced negative sampling technique may be explored for future research.
Parabel [4] $O((nd\log L)/L)$ 通过基于高效和信息丰富的标签表示来学习平衡的二进制标签树，从而减少了一对多方法 $O(ndL)$ 的训练时间。他们还提出了一个概率分层多标签模型，用于将分层 softmax 推广到多标签设置。还提出了对数预测算法来处理 XMLC。实验表明，与最先进的一对多极端分类器相比，Parabel 在训练和预测方面可以快几个数量级。但是，Parabel 在低维数据集中并不准确，因为 Parabel 无法保证相似的标签被划分到同一组，误差会在深树中传播。为了减少错误传播， Bonsai [64] 显示了具有广义标签表示形式的浅层 $k$ -ary 标签树结构。Slice [5] 中还提出了一种新的负采样技术，以提高低维密集特征表示的预测精度。Slice 能够将一对多方法的训练时间成本从线性降低到 $O(nd\log L)$ 仅在 $O(n/L\log L)$ 最令人困惑的负面样本上训练分类器，而不是在所有 $n$ 训练集上训练分类器。Slice 采用生成模型，根据近似最近邻搜索 （ANNS） 在时间 $O((n+L)d\log L)$ 上估计 $O(n/L\log L)$ 每个标签的负样本，并对 $O(\log L)$ 每个测试数据最可能的标签进行预测。Slice 的准确率比 Parabel 高 15%，并且能够扩展到 1 亿个标签和 2.4 亿个训练点。 [5] 中的实验表明，负采样是 XMLC 中的强大工具，一些高级负采样技术的性能提升可以用于未来的研究。

Remark. One-vs-all methods are the simple strategies for dealing with XMLC, and PD-Sparse is the first choice for the beginners to try. As mentioned before, one-vs-all methods independently train a binary classifier for each label, so computation and memory cost pose an intractable issue for XMLC, and one-vs-all methods do not consider the correlations between labels. Although the reviewed methods in this subsection are able to ease the computation issue, how to use the correlations between labels to boost the performance of one-vs-all methods could pose a serious problem in the future. One possible way is to design some one-vs-all learning models which consider various label correlations.
备注。一对多方法是处理 XMLC 的简单策略，PD-Sparse 是初学者尝试的首选。如前所述，一对多方法为每个标签独立训练一个二进制分类器，因此计算和内存成本对 XMLC 来说是一个棘手的问题，并且一对多方法不考虑标签之间的相关性。尽管本小节中回顾的方法能够缓解计算问题，但如何使用标签之间的相关性来提高 one-vs-all 方法的性能，将来可能会带来一个严重的问题。一种可能的方法是设计一些考虑各种标签相关性的 one-vs-all 学习模型。

In real-world scenarios, it is intractable for the annotators to figure out all the ground-truth labels, due to the complicated structure or the high volume of the output space. Instead, a subset of labels can be obtained, which is called multi-label learning with missing labels (MLML). There are two main settings in MLML. The first setting [15] only obtains a subset of relevant labels. It views the MLML problem as a positive-unlabeled learning task such that the remaining labels are all regarded as negative labels. The other setting [65] explicitly indicates which labels are missing. Formally, given a feature vector $x_{i}$, we denote the label vector of these two settings by $\hat{y}_{i}\in\{-1,+1\}^{L\times 1}$ ($-1$ can be missing or negative labels) and $\tilde{y}_{i}\in\{-1,0,+1\}^{L\times 1}$ ($0$ represents missing labels) respectively. We distinguish these two settings in Figure 2. Moreover, two different learning targets may be considered. One is transductive that only learns to complete the missing entries. The other is inductive where a classifier is trained for unseen data. For simplicity, we do not explicitly distinguish these differences.
在实际场景中，由于结构复杂或输出空间的大容量，注释者很难弄清楚所有真实标签。相反，可以获取标签的子集，称为缺失标签的多标签学习 （MLML）。MLML 中有两个主要设置。第一个设置 [15] 仅获得相关标签的子集。它将 MLML 问题视为一个正 - 未标记的学习任务，因此剩余的标签都被视为负标签。另一个设置 [65] 明确指示缺少哪些标签。形式上，给定一个特征向量 $x_{i}$ ，我们分别用 $\hat{y}_{i}\in\{-1,+1\}^{L\times 1}$ （ $-1$ 可以是缺失或负标签） 和 $\tilde{y}_{i}\in\{-1,0,+1\}^{L\times 1}$ （ $0$ 表示缺失标签） 来表示这两个设置的标签向量。我们在图 2 中区分了这两种设置。此外，可以考虑两个不同的学习目标。一种是 transductive，只学习完成缺失的条目。另一种是归纳法，其中分类器针对看不见的数据进行训练。为简单起见，我们没有明确区分这些差异。

Next, we will review state-of-the-art MLML methods which are mainly based on low-rank and graph assumptions.
接下来，我们将回顾主要基于低秩和图假设的最先进的 MLML 方法。

In semi-supervised MLC (SS-MLC) [92], the data set is comprised of two sets: fully labeled data and unlabeled data. Though SS-MLC has a far longer history than MLML, we can regard it as a special case of MLML, i.e. the labels of some instances are totally missing. In fact, similar to MLML, a plenty of SS-MLC algorithms are also based on graph models [93, 94], and low-rank assumptions [79, 95]. In what follows, we first review some state-of-the-art SS-MLC algorithms and then, discuss a novel learning setting called weakly-supervised MLC.
在半监督MLC（SS-MLC）[92]中，数据集由两组组成：完全标记数据和未标记数据。虽然 SS-MLC 的历史比 MLML 要长得多，但我们可以将其视为 MLML 的一个特例，即一些实例的标签完全缺失。事实上，与 MLML 类似，许多 SS-MLC 算法也基于图模型 [93， 94] 和低秩假设 [79， 95]。在下文中，我们首先回顾了一些最先进的 SS-MLC 算法，然后讨论了一种称为弱监督 MLC 的新型学习设置。

In practice, the complicated structure of the label space usually makes it hard to decide some hard labels are relevant or not. For example, it is usually hard to decide whether a dog is a malamute or a husky. One might naively drop these labels and regard the original problem as an MLML task. However, missing labels provides no information to the user at all. Hence, partial multi-label learning (PML) [17] is proposed to address this issue, which preserves all the potentially correct labels. Formally speaking, each instance $x$ is equipped with a set of candidate labels $S$, only some of which are the true relevant labels. The remaining labels are called false positive labels or distractor labels. Technically, PML can be regarded as a dual problem of MLML and solved by existing MLML techniques. However, it is worth noting that this strategy may be less practical owing to the sparsity of the label space. Moreover, PML also provides a safe way to protect data privacy since no label can be determined as the ground-truth, as opposite to MLML data.
在实践中，标签空间的复杂结构通常使得很难确定某些硬标签是否相关。例如，通常很难确定一只狗是雪橇犬还是哈士奇。人们可能会天真地丢弃这些标签，并将原始问题视为 MLML 任务。但是，缺少标签根本不会向用户提供任何信息。因此，提出了部分多标签学习 （PML） [17] 来解决这个问题，它保留了所有可能正确的标签。从形式上讲，每个实例 $x$ 都配备了一组 candidate labels $S$ ，其中只有一部分是真正的相关标签。其余标签称为误报标签或干扰标签。从技术上讲，PML 可以看作是 MLML 的一个对偶问题，可以通过现有的 MLML 技术来解决。但是，值得注意的是，由于标签空间的稀疏性，这种策略可能不太实用。此外，PML 还提供了一种保护数据隐私的安全方法，因为与 MLML 数据相反，没有标签可以确定为真实数据。

The complexity of the label space has expedited various kinds of improperly-supervised MLC settings. In what follows, we briefly review some more state-of-the-art settings in the literature.
标签空间的复杂性加速了各种监督不当的 MLC 设置。在下文中，我们将简要回顾文献中一些更先进的设置。

MLC with Noisy Labels (Noisy-MLC). While MLML and PML consider single-side noise, Noisy-MLC assumes that noisy labels occur in both relevant and irrelevant labels. Many effective Noisy-MLC algorithms have been proposed to address this problem, including graph based methods [120], probability models [121], teacher-student model [122]. In [106], the WS-MLC framework is extended and noisy labels are assumed to be contained in the data set. Some works [123, 24] maintain a small set of clean data to reduce the noise in the large data set. Since learning from label noise have been a hot topic in the community, Noisy-MLC deserve more attention.
具有噪声标签的 MLC （Noisy-MLC）。MLML 和 PML 考虑单侧噪声，而 Noisy-MLC 假设噪声标签同时出现在相关和不相关的标签中。已经提出了许多有效的 Noisy-MLC 算法来解决这个问题，包括基于图的方法 [120]、概率模型 [121]、教师-学生模型 [122]。在 [106] 中，扩展了 WS-MLC 框架，并假设数据集中包含嘈杂的标签。一些工作 [123， 24] 维护了一小群干净的数据，以减少大数据集中的噪声。由于从标签噪声中学习一直是社区中的热门话题，因此 Noisy-MLC 值得更多关注。

MLC with Unseen Labels. In the aforementioned settings, the label spaces is fixed during training and testing. However, in practice, the label space may be dynamically expanded. For instance, [124] studies an online MLC setting that an arriving data instance may be associated with unknown labels. In [35], knowledge distillation method is used to handle streaming labels. Multi-label zero-shot learning (ML-ZSL) [36] requires the prediction of unknown labels which are not defined during training. To make ML-ZSL feasible, external semantic information is usually involved, such as word vectors [125] and knowledge graphs [36]. In [126], few-shot labels is also considered, which relates to only few instances in the data set, i.e. nearly unseen.
具有 Unseen Labels 的 MLC。在上述设置中，标签空间在训练和测试期间是固定的。但是，在实践中，标签空间可能会动态扩展。例如，[124] 研究了在线 MLC 设置，即到达的数据实例可能与未知标签相关联。在 [35] 中，知识蒸馏方法用于处理流式标签。多标签零样本学习（ML-ZSL）[36]需要预测训练过程中未定义的未知标签。为了使 ML-ZSL 可行，通常涉及外部语义信息，例如词向量 [125] 和知识图谱 [36]。在 [126] 中，还考虑了小镜头标签，它仅与数据集中的少数实例有关，即几乎看不见。

Multi-Label Active Learning (MLAL). Active learning is a notable way to alleviate the difficulty of multi-label tagging. The idea is to carefully select the most informative data instances for labeling such that better models can be trained with less labeling effort. A variety of works have studied MLAL problems. For example, [127] adopts maximum loss reduction with maximal confidence as the sampling criterion for MLAL. [26] solves MLAL problems via a probability model. Moreover, MLAL is also considered in crowdsourcing [128] and novel queries [129] tasks.
多标签主动学习 （MLAL）。主动学习是缓解多标签标记难度的一种显着方法。这个想法是仔细选择信息量最大的数据实例进行标记，以便以更少的标记工作训练更好的模型。各种工作都研究了 MLAL 问题。例如，[127] 采用最大置信度的最大损失减少作为 MLAL 的采样标准。[26] 通过概率模型解决 MLAL 问题。此外，MLAL 也被考虑用于众包 [128] 和新颖查询 [129] 任务。

Label Distribution Learning (LDL). LDL [107] is a general framework that assigns $L$ normalized real values to label description degree. It aims to tackle inherent ambiguity in data annotation, e.g. a facial expression usually conveys a complex mixture of basic emotions. Since it is difficult to obtain the label distribution directly, many works [108, 130, 131] focus on recovering label distributions from logical labels, which is also known as label enhancement (LE). LE is an effective learning strategy to deal with label ambiguity. LE is also applied in WS-MLC [106] and PML [109] to handle imperfect supervision signals.
标签分布学习 （LDL）。LDL [107] 是一个通用框架，它将标准化的实值分配给 $L$ 标签描述程度。它旨在解决数据注释中固有的歧义，例如，面部表情通常传达基本情绪的复杂混合。由于很难直接获得标签分布，许多工作 [108， 130， 131] 专注于从逻辑标签中恢复标签分布，这也称为标签增强 （LE）。LE 是处理标签歧义的有效学习策略。LE 也应用于 WS-MLC [106] 和 PML [109] 中，以处理不完美的监控信号。

MLC with Multiple Instances (MIML). MIML [119] is a popular setting which assumes each example is described by multiple instances as well as associated with multiple binary labels. Recent studies in MIML [132, 133] have developed many deep learning models such that noisy instances can be effectively figured out. Nevertheless, MIML mainly focuses on the instance-level ambiguity instead of the labels. Hence, we do not further discuss it.
具有多个实例的 MLC （MIML）。MIML [119] 是一种流行的设置，它假设每个示例都由多个实例描述，并与多个二进制标签相关联。MIML [132， 133] 的最新研究开发了许多深度学习模型，可以有效地找出嘈杂的实例。尽管如此，MIML 主要关注实例级的歧义性，而不是标签。因此，我们不再进一步讨论它。

Remark. Intelligent systems are enrolled in increasingly difficult and complicated tasks, and thus new settings like PML and LDL deserve more attention. Moreover, there remain more challenging and complicated settings in real-world applications to be explored. For instance, there might be out-of-distribution detection [134], domain shift [135] and other problems arise in MLC problems.
备注。智能系统承担的任务越来越困难和复杂，因此 PML 和 LDL 等新设置值得更多关注。此外，在实际应用中仍有更具挑战性和更复杂的设置有待探索。例如，MLC 问题中可能会出现分布外检测 [134]、域偏移 [135] 和其他问题。

Different from conventional multi-label methods, deep neural networks (Deep NNs) often seek a new feature space and employ a multi-label classifier on the top. To our knowledge, BP-MLL [29] is the first method to utilize NN architecture for multi-label learning problem. To explicitly exploit the dependencies among labels, given the neural network $F$, BP-MLL introduces a pairwise loss function for each instance $x_{i}$:
与传统的多标签方法不同，深度神经网络 （Deep NN） 通常会寻找新的特征空间，并在顶部使用多标签分类器。 据我们所知，BP-MLL [29] 是第一种利用 NN 架构解决多标签学习问题的方法。为了显式利用标签之间的依赖关系，给定神经网络 $F$ ，BP-MLL 为每个实例 $x_{i}$ 引入了一个成对损失函数：

where $y_{i}^{1}$ and $y_{i}^{0}$ denote the sets of positive and negative labels for the $i$-the instance $x_{i}$ respectively, $(F(x_{i}))^{p}$ denotes the $p$-th entry of $F(x_{i})$. $F(x_{i}))^{p}-(F(x_{i}))^{q}$ measures the difference between the outputs of the network on the positive and negative labels, and the exponential function is used to severely penalize the difference. Thus the minimization of (9) leads to output larger values for positive labels, and smaller values for the negative labels. [29] further shows that (9) is closely related to ranking loss.
其中 $y_{i}^{1}$ 和 $y_{i}^{0}$ 分别表示 $i$ -the 实例的 $x_{i}$ 正标签集和负标签集， $(F(x_{i}))^{p}$ 表示 $p$ 的第 -个条目 $F(x_{i})$ 。 $F(x_{i}))^{p}-(F(x_{i}))^{q}$ 测量正标签和负标签上网络输出之间的差异，并使用指数函数对差异进行严重惩罚。因此，（9） 的最小化会导致正标签的输出值较大，而负标签的输出值较小。[29] 进一步表明 （9） 与排名损失密切相关。

Later, [136] finds that BP-MLL does not perform as expected on data sets in textual domain. To address the issue, based on BP-MLL, [136] proposes to use a comparably simple NN approach that can achieve the state-of-the-art performance in large-scale multi-label text classification. They show that the ranking loss in BP-MLL can be efficiently and effectively replaced by the commonly used cross-entropy function, and several NN tricks, i.e., rectified linear units (ReLUs), Dropout, and AdaGrad can be effectively employed in this setting.
后来，[136] 发现 BP-MLL 在文本域中的数据集上没有按预期执行。为了解决这个问题，基于 BP-MLL，[136] 建议使用一种相对简单的 NN 方法，该方法可以在大规模多标签文本分类中实现最先进的性能。他们表明，BP-MLL 中的排名损失可以有效地被常用的交叉熵函数所取代，并且几种 NN 技巧，即整流线性单元 （ReLUs）、Dropout 和 AdaGrad 可以有效地用于此设置。

Embedding methods have been effective to capture the label dependency and reduce the computation costs. However, existing embedding methods are shallow models, which may not be powerful to discover high order dependency among labels. To fulfill this gap, [30] proposes Canonical Correlated AutoEncoder (C2AE), which is the first DNN-based embedding method for MLC to our knowledge. The basic idea of C2AE is to seek a deep latent space to jointly embed the instances and labels. C2AE performs feature-aware label embedding and label-correlation aware prediction. The former is realized by joint learning of deep canonical correlation analysis (DCCA) and the encoding stage of autoencoder, while the latter is achieved by the introduced loss function for the decoding outputs.
嵌入方法可以有效地捕获标签依赖关系并降低计算成本。然而，现有的嵌入方法是浅层模型，对于发现标签之间的高阶依赖关系可能并不强大。为了填补这一差距，[30] 提出了 Canonical Correlated AutoEncoder （C2AE），据我们所知，这是第一个基于 DNN 的 MLC 嵌入方法。C2AE 的基本思想是寻找一个深的潜在空间来共同嵌入实例和标签。C2AE 执行特征感知标签嵌入和标签相关性感知预测。前者是通过深度典型相关分析 （DCCA） 和自动编码器编码阶段的联合学习实现的，而后者是通过引入解码输出的损失函数来实现的。

C2AE consists of two DNN modules, i.e., DCCA and autoencoder, and seeks three mapping functions, i.e., feature mapping $F_{x}$, encoding function $F_{e}$, and decoding function $F_{d}$. For training, C2AE receives instance $X$ and labels $Y$, associates them in the latent space $L$, and enforces the recover of $Y$ using autoencoder. The objective function of C2AE is defined as follows:
C2AE 由两个 DNN 模块组成，即 DCCA 和自动编码器，寻求三种映射功能，即特征映射 $F_{x}$ 、编码函数 $F_{e}$ 和解码函数 $F_{d}$ 。对于训练，C2AE 接收实例 $X$ 和标签 $Y$ ，将它们关联到潜在空间中 $L$ ，并使用自动编码器强制执行恢复 $Y$ 。C2AE 的目标函数定义如下：

where $\Phi(F_{x},F_{e})$ and $\Gamma(F_{e},F_{d})$ denote the losses in the latent and output spaces respectively, $\alpha$ is used to balance the two terms. Inspired by the CCA, C2AE learns the deep latent space by maximizing the correlation between instances and labels. Thus $\Phi(F_{x},F_{e})$ can be defined as:
其中 $\Phi(F_{x},F_{e})$ 和 $\Gamma(F_{e},F_{d})$ 分别表示 latent 和 output 空间中的损失， $\alpha$ 用于平衡这两个项。受 CCA 的启发，C2AE 通过最大化实例和标签之间的相关性来学习深层潜在空间。因此 $\Phi(F_{x},F_{e})$ 可以定义为：

In addition, C2AE recovers the labels using autoencoder with aim of preserving label dependency. Inspired by [29], $\Gamma(F_{e},F_{d})$ is defined as follows:
此外，C2AE 使用自动编码器恢复标签，目的是保留标签依赖性。 受 [29] 启发， $\Gamma(F_{e},F_{d})$ 定义如下：

where $N$ is the number of the instances, $F_{d}(F_{e}(x_{i}))$ is the recovered label of $x_{i}$ using the autoencoder. For prediction, given a test instance $\hat{x}$, C2AE performs prediction as $\hat{y}=F_{d}(F_{x}(\hat{x}))$.
其中 $N$ 是实例数， $F_{d}(F_{e}(x_{i}))$ 是使用 autoencoder 的 $x_{i}$ recovered 标签。对于预测，给定一个测试实例 $\hat{x}$ ，C2AE 将执行预测。 $\hat{y}=F_{d}(F_{x}(\hat{x}))$

Later, inspired by C2AE, [137] presents a two-stage label embedding model based on neural factorization machine model. It first exploits second-order label correlation via a factorization layer and then learns high-order correlation by additional fully-connected layers. [57] proposes another deep embedding method, i.e., Deep Correlation Structure Preserved Label Space Embedding (DCSPE). In addition to DCCA, DCSPE further develops deep multidimensional scaling (DMDS) to preserve the intrinsic structure of the latent space. Finally, DCSPE transforms test instance into the latent space, searches its nearest neighbor, and finally regards label of this neighbor as prediction. However, as the $k$NN search is time-consuming, the $k$NN embedding methods are computationally expensive in the large-scale setting. To solve the above issue, [138] proposes a novel deep binary prototype compression (DBPC) for fast multi-label prediction. DBPC compresses the database into a small set of short binary prototypes, and uses the prototypes for prediction.
后来，受 C2AE 的启发，[137] 提出了一种基于神经因子分解机模型的两阶段标签嵌入模型。它首先通过因式分解层利用二阶标签相关性，然后通过其他全连接层学习高阶相关性。[57] 提出了另一种深度嵌入方法，即深度相关结构保留标签空间嵌入 （DCSPE）。除了 DCCA，DCSPE 还进一步开发了深度多维缩放 （DMDS） 以保留潜在空间的内在结构。最后，DCSPE 将测试实例转换为潜在空间，搜索其最近的邻居，最后将该邻居的标签视为预测。然而，由于 $k$ NN 搜索非常耗时，因此 $k$ NN 嵌入方法在大规模设置中的计算成本很高。为了解决上述问题，[138] 提出了一种新的深度二进制原型压缩 （DBPC） 用于快速多标签预测。DBPC 将数据库压缩为一小组简短的二进制原型，并使用这些原型进行预测。

For multi-label emotion classification, [139] recently proposes latent emotion memory (LEM) to learn latent emotion distribution without external knowledge. LEM includes latent emotion and memory modules to learn emotion distribution and emotional features respectively, and the concatenation of the two is fed into Bi-directional Gated Recurrent Unit (BiGRU) for prediction. For multi-label image classification, [140] proposes a unified deep neural network that exploits both semantic and spatial relations between labels with only image-level supervision. Specifically, the authors propose Spatial Regularization Network (SRN) that generates attention maps for all labels and captures the underlying relations between them via learnable convolutions. [141] finds the consistency of attention regions of CNN classifiers under many transforms are not preserved. To address the issue, the authors propose a two-branch network with original and transformed images as inputs and introduce a new attention consistency loss that measures the attention heatmap consistency between two branches. Later [142] proposes Adjacency-based Similarity Graph Embedding (ASGE) and Cross-modality Attention (CMA) to capture the dependencies between labels and discover locations of discriminative features respectively. Specifically, ASGE learns semantic label embedding that can explicitly exploit label correlations, and CMA generates the meaningful attention maps by leveraging more prior semantic information. Instead of requiring laborious object-level annotations, [143] proposes to distill knowledge from weakly-supervised detection (WSD) task to boost MLC performance. The authors construct an end-to-end MLC framework augmented by a knowledge distillation module that guides the classification model by the WSD model for object RoIs. WSD and MLC are the teacher and student models respectively.
对于多标签情绪分类，[139] 最近提出了潜在情绪记忆 （LEM） 在没有外部知识的情况下学习潜在情绪分布。LEM 包括潜在情绪和记忆模块，分别学习情绪分布和情绪特征，两者的串联被馈送到双向门控循环单元 （BiGRU） 进行预测。对于多标签图像分类，[140] 提出了一个统一的深度神经网络，该网络利用标签之间的语义和空间关系，仅需要图像级监督。具体来说，作者提出了空间正则化网络 （SRN），它为所有标签生成注意力图，并通过可学习的卷积捕捉它们之间的潜在关系。[141] 发现在许多转换下 CNN 分类器的注意力区域的一致性没有被保留。为了解决这个问题，作者提出了一个以原始图像和转换后的图像作为输入的双分支网络，并引入了一种新的注意力一致性损失，用于测量两个分支之间的注意力热图一致性。后来 [142] 提出了基于邻接的相似图嵌入 （ASGE） 和跨模态注意力 （CMA），以分别捕获标签之间的依赖关系并发现判别特征的位置。具体来说，ASGE 学习可以显式利用标签相关性的语义标签嵌入，而 CMA 通过利用更多先验语义信息来生成有意义的注意力图。[143] 建议从弱监督检测 （WSD） 任务中提取知识，以提高 MLC 性能，而不是费力的对象级注释。 作者构建了一个端到端的 MLC 框架，该框架由知识蒸馏模块增强，该模块通过对象 RoI 的 WSD 模型指导分类模型。WSD 和 MLC 分别是教师和学生模式。

Remark. Deep embedding methods are the most widely-used deep methods for MLC. Among them, C2AE is pioneer deep embedding work for MLC and has been applied in many real-world applications including multi-label emotion classification, which deserves exploration for the beginners to understand basic mechanism. As we know, label correlation is key for MLC, and some objectives, e.g., (12) have been used to model label correlation in deep embedding methods for MLC. However, existing research shows that (12) may not be effective for textual domain. In the future, how to effectively capture label correlation is an important research topic of deep embedding methods for MLC. Some advanced techniques, e.g., graph convolutional network (GCN), recurrent neural network (RNN) open doors to better capture label correlation, and can motivate further research of deep embedding methods for MLC.
备注。深度嵌入方法是 MLC 中使用最广泛的深度方法。其中，C2AE 是 MLC 的先驱深度嵌入工作，并已应用于包括多标签情感分类在内的许多实际应用中，值得初学者探索以了解基本机制。众所周知，标签相关性是 MLC 的关键，一些目标，例如 （12） 已被用于模拟 MLC 深度嵌入方法中的标签相关性。然而，现有的研究表明 （12） 可能对文本域无效。未来，如何有效地捕获标签相关性是 MLC 深度嵌入方法的重要研究课题。一些先进的技术，例如图卷积网络 （GCN）、递归神经网络 （RNN） 为更好地捕获标签相关性打开了大门，并且可以激励 MLC 深度嵌入方法的进一步研究。

In real world applications, multi-label learning is often challenging due to the complex setting of labels. For instance, the number of labels is very large known as XMLC; the labels are often partially or weakly given; labels emerge continuously or are even unseen before. This section reviews the recent advances of deep learning to address these challenging MLC problems.
在实际应用中，由于标签设置复杂，多标签学习通常具有挑战性。例如，标签的数量非常大，称为 XMLC;标签通常是部分或微弱的;标签不断出现，甚至以前从未见过。本节回顾了深度学习解决这些具有挑战性的 MLC 问题的最新进展。

DL for Extreme MLC. To our knowledge, [31] is the first attempt at applying deep learning to XMLC. XML-CNN [31] applies convolutional neural network (CNN) and dynamic pooling to learn the text representation, and a hidden bottleneck layer much smaller than the output layer is used to achieve computational efficiency. However, XML-CNN still suffers from effectiveness of capturing the important subtext for each label. To address this issue, AttentionXML [32] is proposed with two unique features: 1) a multi-label attention mechanism with raw text as input, which allows to capture the most relevant part of text to each label, 2) a shallow and wide probabilistic label tree (PLT), which allows to handle millions of labels, especially for "tail labels". Meanwhile, based on C2AE, a new deep embedding method, i.e., Ranking-based Auto-Encoder (Rank-AE) [33] is proposed for XMLC. Rank-AE first uses an efficient attention mechanism to learn rich representations from any type of input features, learns a latent space for instance and labels, and finally develops a margin-based ranking loss that is more effective for XMLC and noisy labels. [144] empirically demonstrates that overfitting leads to the poor performance of the DNN based embedding methods for XMLC. Based on this finding, [144] further proposes a new regularizer, i.e., GLaS for embedding-based neural network approaches. [145] finetunes a pretrained deep transformer for better feature representation. They propose a novel label clustering model for XMLC and the transformer serves as a neural matcher. With the proposed techniques, the state-of-the-art performance is achieved on several widely-used extreme data sets. Very recently [146] develops DeepXML framework that can generate a family of algorithms by including four sub-tasks, i.e., intermediate representation, negative sampling, transfer learning, and classifier learning. It yields Accelerated Short Text Extreme Classifier (Astec) that is more accurate and faster than state-of-the-art deepXMLs on public short text data sets. DECAF [147] considers label metadata, e.g., textual descriptions of labels, which is informative but usually ignored by existing methods. DECAF jointly learns model enriched by label metadata and feature representation, and predicts accurately with millions of labels. ECLARE [148] incorporates label text and label correlations, and develops frugal architecture and scalable techniques to train model with label correlation graph with millions of labels. Similarly, GalaXC [149] collaboratively learns over joint document-label graphs that can incorporate various sources, e.g., label metedata. GalaXC further introduces label-wise attention to obtain high-capacity extreme classifiers. [149] shows that GalaXC is up to 18% more accurate than state-of-the-arts while it trains 2-50 times faster and predicts 10 times faster on benchmark data sets.
DL 代表 Extreme MLC。据我们所知，[31] 是将深度学习应用于 XMLC 的第一次尝试。XML-CNN [31] 应用卷积神经网络 （CNN） 和动态池化来学习文本表示，并使用比输出层小得多的隐藏瓶颈层来实现计算效率。但是，XML-CNN 仍然无法有效地捕获每个标签的重要潜台词。为了解决这个问题，AttentionXML [32] 提出了两个独特的功能：1） 以原始文本为输入的多标签注意力机制，允许捕获与每个标签最相关的文本部分，2） 浅而宽的概率标签树 （PLT），允许处理数百万个标签，特别是 “尾部标签”。同时，在 C2AE 的基础上，提出了一种新的深度嵌入方法，即基于排名的自动编码器 （Rank-AE） [33] 用于 XMLC。Rank-AE 首先使用一种高效的注意力机制从任何类型的输入特征中学习丰富的表示，学习潜在空间（例如和标签），最后开发一种基于边距的排名损失，这对 XMLC 和嘈杂的标签更有效。[144] 经验证明，过拟合会导致基于 DNN 的 XMLC 嵌入方法性能不佳。基于这一发现，[144] 进一步提出了一种新的正则化器，即 GLaS，用于基于嵌入的神经网络方法。[145] 微调预训练的深度 transformer 以获得更好的特征表示。他们为 XMLC 提出了一种新的标签聚类模型，该转换器用作神经匹配器。 通过提出的技术，在几个广泛使用的极端数据集上实现了最先进的性能。最近 [146] 开发了 DeepXML 框架，该框架可以通过包括四个子任务来生成一系列算法，即中间表示、负采样、迁移学习和分类器学习。它生成的加速短文本极端分类器 （Astec） 在公共短文本数据集上比最先进的 deepXML 更准确、更快速。DECAF [147] 考虑了标签元数据，例如标签的文本描述，这是信息丰富的，但通常被现有方法所忽略。DECAF 联合学习通过标签元数据和特征表示丰富的模型，并使用数百万个标签进行准确预测。ECLARE [148] 整合了标签文本和标签相关性，并开发了节俭架构和可扩展技术，以使用具有数百万个标签的标签关联图来训练模型。同样，GalaXC [149] 通过联合文档标签图进行协作学习，这些图可以包含各种来源，例如标签元数据。GalaXC 进一步引入了标签关注以获得高容量的极端分类器。[149] 表明，GalaXC 的准确率比最先进的高 18%，同时它在基准数据集上的训练速度提高了 2-50 倍，预测速度提高了 10 倍。

DL for partial and weakly-supervised MLC. Several efforts [150, 34, 19, 151] have been made towards MLC with partial labels. [34] empirically shows that partially annotating all images is better than fully annotating a small subset. Thus [34] generalizes the standard binary cross-entropy loss by exploiting label proportion information, and develops an approach based on Graph Neural Networks (GNNs) to explicitly model the correlation between categories. Later, [19] regularizes the cross-entropy loss with a cost function that measures the smoothness of labels and features of images on data manifold, and develops an efficient interactive learning framework where similarity learning and CNN training interact and improve each another. [23] is the first deep generative model to tackle weakly-supervised MLC (WS-MLC). [23] proposes a probabilistic framework that integrates sequential prediction and generation processes to exploit information from unlabeled or partially labeled data.
DL 用于部分和弱监督 MLC。已经对带有部分标签的 MLC 做出了一些努力 [150， 34， 19， 151]。[34] 实证表明，部分注释所有图像比完全注释一小部分图像要好。因此 [34] 通过利用标签比例信息概括了标准的二进制交叉熵损失，并开发了一种基于图神经网络 （GNN） 的方法来显式建模类别之间的相关性。后来，[19] 用一个成本函数来规范交叉熵损失，该函数测量数据流形上图像的标签和特征的平滑度，并开发了一个高效的交互式学习框架，其中相似性和 CNN 训练相互作用并相互改进。[23] 是第一个处理弱监督 MLC （WS-MLC） 的深度生成模型。[23] 提出了一个概率框架，该框架集成了顺序预测和生成过程，以利用来自未标记或部分标记数据的信息。

DL for MLC with unseen labels. In conventional MLC, all the labels are assumed to be fixed and static; however, it is ignored that labels emerge continuously in changing environments. To fulfill this gap, a novel DNN-based method, i.e., Deep Streaming Label Learning (DSLL) [35] is proposed to deal with MLC with newly emerged labels effectively. DSLL uses streaming label mapping, streaming feature distillation, and senior student network to explore the knowledge from past labels and historical models to understand new labels. In addition, [35] further theoretically proves that DSLL admits tight generalization error bounds for new labels in the DNN framework. Different from DSLL, [36] incorporates the additional knowledge graphs for multi-label zero-shot learning (ML-ZSL). [36] advances label propagation mechanism in the semantic space, enabling the reasoning of the learned model for predicting unseen labels.
DL 表示具有不可见标签的 MLC。在传统的 MLC 中，所有标签都被假定为固定和静态的;然而，人们忽略了标签在不断变化的环境中不断出现。为了填补这一差距，提出了一种基于 DNN 的新方法，即深度流标签学习 （DSLL） [35] 来有效处理新出现标签的 MLC。DSLL 使用流式标签映射、流式特征蒸馏和高年级学生网络来探索过去标签和历史模型中的知识，从而了解新标签。此外，[35] 进一步从理论上证明，DSLL 承认 DNN 框架中新标签的严格泛化误差边界。与 DSLL 不同，[36] 结合了用于多标签零样本学习 （ML-ZSL） 的附加知识图谱。[36] 在语义空间中推进了标签传播机制，使学习模型的推理能够预测看不见的标签。

Remark. MLC problem is challenging due to the high complexity of labels. [149], [34], [23], and [35] are representative deep works for beginners to address extreme MLC, partial MLC, weakly-supervised MLC, and MLC with unseen labels, respectively. The above attempts only focus on challenges of label space in MLC problem. However, in real-world MLC problems, there are some challenges in feature space, e.g., some features may be vanished or augmented, the distribution may change. How to simultaneously address challenges in label and feature spaces is more challenging and can be regarded as future research of challenging MLC problem.
备注。由于标签的高度复杂性，MLC 问题具有挑战性。[149]、[34]、[23] 和 [35] 是初学者的代表性深度工作，分别解决了极端 MLC、部分 MLC、弱监督 MLC 和具有看不见标签的 MLC。以上尝试仅关注 MLC 问题中标签空间的挑战。然而，在现实世界的 MLC 问题中，特征空间存在一些挑战，例如，某些特征可能会消失或增强，分布可能会发生变化。如何同时应对标签和特征空间的挑战更具挑战性，可以被视为未来具有挑战性的 MLC 问题的研究。

Recently some advanced deep learning architectures have been developed for MLC problems.
最近，针对 MLC 问题开发了一些高级深度学习架构。