Source-linked AI summary
Deep Extreme Multi-label Learning
Wenjie Zhang, Junchi Yan, Xiangfeng Wang, Hongyuan Zha
TL;DR
Extreme multi-label learning must choose relevant labels from enormous label spaces, yet existing embedding approaches may ignore label structure. This paper combines deep nonlinear embedding with an explicit label graph, and reports competitive or better performance than SLEEC without an ensemble on public benchmarks.
Problem
XML must predict relevant subsets from very large label sets while handling massive feature and label dimensions, and embedding methods may ignore label structure.
Source: §1 · pp. 1–2Method
The method uses deep networks for nonlinear embedding in feature and label spaces while modeling label-graph structure.
Source: §1 · p. 2Results
Without an ensemble, the method performs competitively with or outperforms state-of-the-art ensemble method SLEEC on public benchmarks.
Source: §1 · p. 2Takeaways & Limitations
The authors conclude that experiments corroborate the efficacy of using a label graph to model large-scale label space alongside deep neural networks for label-space exploration and feature embedding.
Source: §5 · p. 6The authors leave more advanced training mechanisms for an end-to-end deep-learning paradigm for XML classification to future work.
Source: §5 · p. 7
Abstract
from arXiv · showhide
Extreme multi-label learning (XML) or classification has been a practical and important problem since the boom of big data. The main challenge lies in the exponential label space which involves $2^L$ possible label sets especially when the label dimension $L$ is huge, e.g., in millions for Wikipedia labels. This paper is motivated to better explore the label space by originally establishing an explicit label graph. In the meanwhile, deep learning has been widely studied and used in various classification problems including multi-label classification, however it has not been properly introduced to XML, where the label space can be as large as in millions. In this paper, we propose a practical deep embedding method for extreme multi-label classification, which harvests the ideas of non-linear embedding and graph priors-based label space modeling simultaneously. Extensive experiments on public datasets for XML show that our method performs competitive against state-of-the-art result.
1 INTRODUCTION
Extreme multi-label learning must predict relevant subsets from enormous label sets while handling high-dimensional features and labels. The paper combines nonlinear deep embedding with explicit label-graph structure and reports competitive or better benchmark performance than SLEEC without an ensemble.
1 INTRODUCTION
- XML must select relevant subsets from huge label sets while managing massive label, feature, and training-sample dimensions.The passage contrasts multi-label prediction, where labels may co-exist, with multi-class classification, which predicts one mutually exclusive label.Source: §1 · p. 1
- Existing XML methods use trees or embeddings, but embedding approaches assume low-rank label structure that is violated in many real-world applications.The introduction also notes that one-against-all classifiers are computationally impractical at million-label scale and may fail to leverage label dependencies.Source: §1 · p. 1
- The proposed approach jointly models feature-space nonlinearity and label-graph structure through deep embedding.The label graph differs from a tree-based label hierarchy; its edges connect labels that co-occur in at least one sample.Source: §1 · p. 2, Figure 1 · p. 2
- Without an ensemble, the method performs competitively with or outperforms state-of-the-art ensemble method SLEEC on public benchmarks.The authors describe this as an outcome of extensive experiments on various public benchmark datasets.Source: §1 · p. 2
2 RELATED WORK
XML methods seek tractable prediction across huge label spaces, principally through tree-based or embedding-based approaches. The paper reviews their trade-offs and notes that deep embedding frameworks from cross-modal retrieval do not directly fit XML’s feature dimensions.
2.1 Classification Methods for XML
- Tree-based XML methods learn label or feature hierarchies for prediction, but hierarchy learning can add substantial training cost.LPSR reduces prediction time by building a hierarchy over a benchmark classifier, while MLRF also incurs extremely high training cost; FastXML builds its hierarchy over feature space.Source: §2.1 · p. 2
- Embedding methods reduce effective label count under a low-rank assumption, map labels to a low-dimensional space, and lift predictions back to the original label space.The paper describes compression and decompression as key differences among embedding methods and cites SLEEC as adding nonlinear neighborhood constraints and k-NN prediction.Source: §2.1 · p. 3
- The proposed method extends embedding-based XML by using neural networks for both label-space structure and feature-space embedding.This distinction is presented after describing SLEEC and its local embedding and k-NN approach.Source: §2.1 · p. 3
2.2 Traditional Multi-label Classification
- Traditional multi-label methods can become computationally unaffordable as label counts grow, while XML involves millions of labels.Tree-based models may become too large to train, and a scalable one-against-all generalization is described as lacking algorithmic scalability for XML.Source: §2.2 · p. 3
- Deep embedding frameworks for cross-modal retrieval are not directly applicable to XML because their input feature vectors are usually low-dimensional.Source: §2.2 · p. 3
3 DEEP LEARNING FOR XML
DXML maps feature and label vectors into a shared embedding space, combining nonlinear feature mapping with label-graph structure. It then uses k-nearest neighbors in that space to predict labels.
3 DEEP LEARNING FOR XML
- DXML embeds high-dimensional feature and label vectors in a common space, then uses a k-NN classifier there to predict labels.The method has training and prediction stages.Source: §3 · p. 3
3.1 Preliminaries
- The setup defines each training example by a feature vector and a binary label vector, and denotes the learned low-dimensional label representation matrix by V.The classifier predicts a subset of the L labels for an unseen input.Source: §3.1 · p. 3
3.2 Deep Label Graph Embedding
- Labels that co-occur in training samples form a graph, whose node-context information DeepWalk uses to learn low-dimensional label representations.If a prior label hierarchy is guaranteed, the method incorporates it instead of building the graph.Source: §3.2 · p. 3
3.3 Deep Non-linear Embedding
- The feature branch learns a nonlinear mapping into the embedding space, using smooth-ℓ1 loss to align feature and label representations.The authors choose smooth-ℓ1 instead of contrastive or triplet losses, which require sampling tuples or triplets.Source: §3.3 · pp. 3–4
3.4 Cluster Embedding Space
- Clustering training examples in the low-dimensional embedding space is described as more computationally efficient and stable than clustering them in the high-dimensional feature space.The authors contrast this with SLEEC's high-dimensional clustering and ensemble of models.Source: §3.4 · p. 4
3.5 Algorithm Framework
- For prediction, DXML embeds a test example, assigns it to a cluster, searches for k nearest training examples there, and averages or sums their labels.Training builds a co-occurrence label graph, applies DeepWalk, projects labels, and trains a neural network to map features into the embedding space.Source: §3.5 · pp. 4–5
4 EXPERIMENTS
Experiments on six public XML benchmarks found that DXML was often more accurate than SLEEC and remained competitive without an ensemble. Results covered small and large datasets, testing time, and an ablation of nonlinear embedding.
4.1 Protocol
- The experiments compared embedding- and tree-based methods on public XML benchmarks, using P@k and nDCG@k to evaluate predictions.The benchmarks included both small- and large-scale datasets.Source: §4.1 · p. 5, §4 · p. 5
4.2 Results and Ablation Analysis
- DXML had test-time complexity comparable to SLEEC, and the ablation found that DXML with nonlinearities outperformed its linear variant.DXML ran on GPU during training and CPU during testing; SLEEC ran on CPU for both stages.Source: §4.2 · p. 5
- On small datasets, DXML was mostly ranked in the top two; it beat SLEEC by nearly 1% on Delicious but slightly underperformed FastXML there.Results were averaged over 10 train-test splits for each dataset.Source: §4.2 · p. 5, Table 2 · p. 6
- On large datasets, DXML was more accurate than the other baselines except on Delicious-200K, where it ranked second.On Amazon-670K, it outperformed LFML and LPSR-NB by around 28% and 9%, respectively, for {P,nDCG} @ {1, 3, 5}.Source: §4.2 · p. 5, Table 3 · p. 6
- Across six XML benchmarks, DXML often achieved higher prediction accuracy than SLEEC and was competitive without an ensemble.The reported comparison includes both large and smaller datasets.Source: §4.2 · pp. 5–6
5 CONCLUSION
The paper models the large-scale XML label space with a label graph and uses deep neural networks to explore that space and learn feature-space embeddings. Its experiments include nDCG evaluations on small- and large-scale datasets, timing comparisons, and a precision@k ablation.
5 CONCLUSION
- The approach models XML label structure with a graph and uses deep neural networks to explore the label space and learn feature-space embeddings.The conclusion presents this as the paper’s approach to XML classification.Source: §5 · p. 6
- Table 4 reports nDCG@k on small-scale datasets.Source: Table 4 · p. 7
- Table 5 reports nDCG@k on large-scale datasets.Source: Table 5 · p. 7
- Table 6 compares training and test times, in seconds, for different methods.Source: Table 6 · p. 7
- Figure 2 compares precision@k for deep nonlinear and deep linear embeddings on Delicious-200K.Source: Figure 2 · p. 7
- The paper leaves more advanced training mechanisms for end-to-end deep learning in XML classification as future work.Source: §5 · p. 7