PaperlayerView exact revision on arXiv

Source-linked AI summary

The Emerging Trends of Multi-Label Learning

Weiwei Liu, Haobo Wang, Xiaobo Shen, Ivor W. Tsang

arXiv:2011.11197v3cs.LG

TL;DR

Multi-label learning must address large label spaces, limited supervision, streaming data, and the challenge of capturing label dependencies. This paper comprehensively reviews emerging topics and representative methods, emphasizing challenges and future directions. The survey identifies promising research extensions and applications while noting limitations in current approaches.

  • Problem

    Traditional multi-label methods do not adequately address big and complex data, including extreme label spaces, limited supervision, and streaming settings.

  • Method

    The paper provides a comprehensive review of extreme, limited-supervision, deep, online, statistical, and application-oriented multi-label learning.

  • Results

    The survey synthesizes representative works, emerging challenges, future research directions, and promising extensions across multi-label learning topics.

  • Takeaways & Limitations

    The reviewed topics and applications identify research directions and extensions worthy of further study.

  • Takeaways & Limitations

    Existing deep embedding research may not effectively capture label correlation in textual domains.

Abstract

from arXiv · show

Exabytes of data are generated daily by humans, leading to the growing need for new efforts in dealing with the grand challenges for multi-label learning brought by big data. For example, extreme multi-label classification is an active and rapidly growing research area that deals with classification tasks with an extremely large number of classes or labels; utilizing massive data with limited supervision to build a multi-label classification model becomes valuable for practical applications, etc. Besides these, there are tremendous efforts on how to harvest the strong learning capability of deep learning to better capture the label dependencies in multi-label learning, which is the key for deep learning to address real-world classification tasks. However, it is noted that there has been a lack of systemic studies that focus explicitly on analyzing the emerging trends and new challenges of multi-label learning in the era of big data. It is imperative to call for a comprehensive survey to fulfill this mission and delineate future research directions and new applications.

1 INTRODUCTION

Multi-label learning is increasingly challenged by big, complex, and streaming data, while emerging settings require scalable methods, limited supervision, and stronger modeling of label dependencies. This paper surveys these trends, applications, and future research directions.

  • Multi-label classification assigns multiple labels to each instance and supports applications in protein functions, documents, and images.
  • Traditional multi-label methods struggle with the increasing scale and complexity of contemporary data.
  • Extreme multi-label classification addresses problems with millions or billions of labels, where existing techniques face prohibitive computational costs.
  • Limited-supervision settings reduce the need for expensive full annotation by using missing, semi-supervised, or ambiguous labels.
  • Deep learning has expanded multi-label classification research, including methods for extreme, partial, weakly supervised, and unseen-label problems.
  • Streaming data motivates online multi-label learning because offline methods require all data in memory and are difficult to adapt to sequential inputs.

2 EXTREME MULTI-LABEL LEARNING

Extreme multi-label learning addresses classification with extremely large label spaces, where conventional methods face prohibitive computational costs. The survey reviews embedding, tree-based, and one-vs-all strategies, along with their efficiency gains and remaining limitations.

  • Extreme multi-label classification: Extreme multi-label classification targets automatically selecting the most relevant subset from millions or even billions of labels.Applications include language modeling, document classification, image or video annotation, web page categorization, and gene function prediction.
  • Embedding Methods: Embedding methods project high-dimensional label vectors into a lower-dimensional space, learn regressors there, and decode predictions back into labels.SLEEC preserves pairwise distances among nearby label vectors, learns regressors in the embedding space, and uses kNN for prediction.
  • Embedding Methods: Embedding approaches can improve XMLC scalability, but existing embeddings may ignore input-output correlations and incur high training or testing costs.Feature-only clustering in SLEEC can place similarly labeled instances in different regions, affecting embedding quality; Bloom filters may also yield false positives.
  • Tree-based Methods: Tree-based methods hierarchically partition instances or labels into smaller subproblems, yielding sub-linear or logarithmic prediction costs when trees are balanced.FastXML optimizes nDCG for rank-sensitive label ordering, while Parabel reduces one-vs-all training complexity from O(ndL) to O((nd log L)/L).
  • Tree-based Methods: Tree-based systems achieve strong efficiency and accuracy gains, but their complex non-convex node optimization and possible error propagation remain open problems.SwiftXML is reported as 14% more accurate than leading extreme classifiers, whereas Parabel can be inaccurate on low-dimensional data because tree errors propagate.
  • One-vs-all Methods: One-vs-all methods independently train a binary classifier for each label, creating computation and memory challenges and failing to model label correlations.Reviewed methods reduce computation, but exploiting label correlations within one-vs-all learning remains an identified future research problem.

3 MULTI-LABEL LEARNING WITH LIMITED SUPER-

Limited-supervision multi-label learning addresses the cost and difficulty of obtaining complete annotations in large output spaces. The survey distinguishes missing-label, semi-supervised, and partial-label settings, while evaluation uses fully supervised test data.

  • Limited supervision is needed because precise annotation is costly when multi-label tasks contain many ground-truth labels and very large output spaces.
  • MLML provides only a subset of labels, SS-MLC adds a large unlabeled set, and PML supplies a candidate superset of labels.
  • These settings train with imperfect supervision but are evaluated on perfectly supervised test data to quantify predictive performance.

3.1 Multi-Label Learning With Missing Labels

MLML covers settings where labels are missing implicitly or explicitly, and its methods primarily exploit low-rank structure, embeddings, graphs, and related regularization. The survey also identifies tailored deep architectures and Bayesian deep learning as promising directions.

  • Problem settings: MLML has two main settings: only a subset of relevant labels is observed, or missing labels are explicitly identified.The first setting treats unobserved labels as negative in a positive-unlabeled formulation.
  • Low-Rank and Embedding Methods: Low-rank methods complement missing entries by exploiting label correlations and can decompose classifiers into lower-dimensional factors for efficient optimization.Some methods treat tail labels as sparse outliers when they may violate the low-rank assumption.
  • Low-Rank and Embedding Methods: Embedding approaches project features and labels into latent spaces, including neural models that jointly embed, decode, and predict labels.
  • Graph-based Methods: Graph-based methods use instance and label graphs to impose sample-level and label-level smoothness while completing incomplete supervision.The standard framework adds manifold regularization to empirical risk minimization; some methods interactively learn two similarity graphs.
  • Other Techniques for Missing Labels: Future MLML work could develop more tailored architectures and apply Bayesian deep learning to high-dimensional data and complex uncertainty.

3.2 Semi-Supervised Multi-Label Classification

SS-MLC combines fully labeled and unlabeled data and can be viewed as MLML where some instances have no labels. Existing approaches use graph, low-rank, probabilistic, and label-enhancement techniques, while deep semi-supervised methods remain underused.

  • Setting: SS-MLC contains fully labeled and unlabeled data and is a special case of MLML in which some instances have completely missing labels.
  • Graph-based Methods: Graph-based SS-MLC methods differ mainly in how they use label correlations, with examples enforcing low-rank classifiers, dynamic graphs, or curriculum similarity.
  • Weakly-Supervised MLC: Weakly-supervised MLC may simultaneously include fully labeled, incompletely labeled, and unlabeled data, and its meaning can differ from MLML with weak labels.
  • Weakly-Supervised MLC: Approaches include weighted ranking, graph regularization, dual similarity regularization, label enhancement, and probabilistic models that integrate unlabeled-data distributions.
  • Open Directions: The survey notes that abundant unlabeled data can restrict SS-MLC representation ability, while few studies apply modern deep semi-supervised techniques.It recommends consistency regularization and self-supervised pretraining for utilizing unlabeled data.

3.3 Partial Multi-Label Learning

PML preserves candidate labels when relevance is ambiguous and focuses on identifying ground-truth labels rather than completing missing ones. Methods use two-stage, end-to-end, label-enhancement, and low-rank strategies, but assumptions and benchmarks remain important concerns.

  • Problem setting: PML assigns each instance a candidate label set containing true relevant labels and false-positive distractor labels.Unlike MLML, PML preserves potentially correct labels when relevance is difficult to determine.
  • Problem setting: PML identifies ground-truth labels from candidates, whereas MLML primarily addresses completion of missing labels.
  • Two-stage Learning Methods: Two-stage methods learn real-valued label confidences, transform the problem into supervised learning, and then induce an MLC classifier.PARTICLE uses label propagation and thresholding, but trimming confidences loses information and limits correlation modeling to second order.
  • Two-stage Learning Methods: PML-LD uses feature-manifold, sample-level, and local label-level smoothness to disambiguate candidates before softmax normalization and supervised learning.
  • End-to-end Learning Methods: Two-stage PML methods retain confidence information for multi-output learning, while end-to-end methods jointly optimize classification and confidence estimation.
  • Open Directions: The survey recommends revisiting the assumption that all candidate labels are equally plausible, adding partial ranks, and establishing a dedicated PML benchmark.

3.4 Other Settings

Multi-label learning increasingly addresses imperfect, ambiguous, dynamic, and actively acquired labels. These settings include noisy, unseen, partially supervised, distributed, and multi-instance labels, while further challenges such as out-of-distribution detection and domain shift remain open.

  • Noisy-MLC models noise affecting both relevant and irrelevant labels, extending settings that consider only one-sided label noise.
  • MLC with unseen labels handles label spaces that expand during or after training, including streaming labels and multi-label zero-shot prediction.
  • Multi-label active learning selects informative instances for annotation to train better models with less labeling effort.
  • Label distribution learning assigns normalized real-valued description degrees to labels, while label enhancement recovers distributions from logical labels.
  • Multi-label multiple-instance learning represents each example with multiple instances and binary labels, but primarily addresses instance-level rather than label ambiguity.
  • The survey identifies out-of-distribution detection, domain shift, and other complicated real-world settings as directions deserving further attention.

4 DEEP LEARNING FOR MULTI-LABEL LEARNING

Deep learning for multi-label learning develops representations and objectives that capture label dependencies, while extending to extreme, partial, weakly supervised, and unseen-label settings. The survey highlights both practical advances and unresolved challenges in modeling correlations across domains and changing feature spaces.

  • 4 DEEP LEARNING FOR MULTI-LABEL LEARNING: Deep neural networks learn a new feature space and place a multi-label classifier on top, with label dependency modeling as a central objective.
  • 4.1 Deep Embedding Methods for MLC: BP-MLL uses pairwise losses that penalize insufficient separation between positive and negative label outputs, encouraging larger positive and smaller negative scores.
  • 4.1 Deep Embedding Methods for MLC: BP-MLL underperformed on textual datasets, while replacing its ranking loss with cross-entropy and using ReLUs, Dropout, and AdaGrad achieved state-of-the-art large-scale text classification performance.
  • 4.1 Deep Embedding Methods for MLC: C2AE jointly embeds instances and labels in a deep latent space through canonical correlation analysis and an autoencoder that preserves label dependencies.
  • 4.3 Advanced Deep Learning for MLC: Existing deep embedding objectives may be ineffective in textual domains, motivating graph convolutional and recurrent architectures for improved label-correlation modeling.
  • 4.2 Deep Learning for Challenging MLC: Deep learning methods address extreme label spaces with bottleneck representations and label-focused attention, including XML-CNN and AttentionXML for text.
  • 4.2 Deep Learning for Challenging MLC: Representative approaches also target partial, weakly supervised, and unseen-label MLC through label proportions, generative modeling, streaming mappings, feature distillation, and student networks.
  • 4.2 Deep Learning for Challenging MLC: Existing work emphasizes label-space challenges, while feature disappearance, feature augmentation, and distribution change remain challenges for real-world MLC.

5 ONLINE MULTI-LABEL LEARNING

Online multi-label learning targets sequential, large-scale data that cannot be handled efficiently by offline methods requiring all examples in memory. Existing approaches use neural, ranking, embedding, and semi-supervised strategies, but theoretical and empirical support remains limited.

  • 5 ONLINE MULTI-LABEL LEARNING: Online multi-label learning supports large-scale applications such as tagging social-media streams, feeds, and advertisements.
  • 5 ONLINE MULTI-LABEL LEARNING: Offline multi-label methods are impractical for large datasets because they require all data in memory and are difficult to adapt to sequential data.
  • 5.1 Online MLC Methods: OUC uses vectorized target labels and a deep model for online training across binary, multi-class, and multi-label classification.
  • 5.1 Online MLC Methods: OSML-ELM applies a single-hidden-layer network with sigmoid activation and incrementally learned output weights to streaming multi-label data.
  • 5.1 Online MLC Methods: OLANSGD reduces per-iteration updates to single-label gradient information, while using Nesterov’s smoothing to optimize a ranking-based objective.
  • 5.1 Online MLC Methods: CS-DPP projects features and labels into a shared embedding space, analyzes cumulative-loss bounds, and experimentally outperforms the cited baselines.
  • 5.2 Online SS-MLC: Online semi-supervised methods incorporate unlabeled examples through dynamic graphs, label embeddings, and local smoothness regularization.
  • 5 ONLINE MULTI-LABEL LEARNING: Model, algorithmic, experimental, and theoretical results for online multi-label learning remain very limited.

6 STATISTICAL MULTI-LABEL LEARNING

Statistical multi-label learning studies generalization, consistency, regularization, and dependency modeling. The survey points to stronger penalties and dependency theory as opportunities, while noting dimensional limitations for copula-based analysis.

  • 6 STATISTICAL MULTI-LABEL LEARNING: Generalization analyses study low-rank linear models, trace-norm regularization, and consistency of learned classifiers under expected loss.
  • 6 STATISTICAL MULTI-LABEL LEARNING: XMLC methods using ℓ1 regularization face estimator bias and lack the oracle property, motivating unified frameworks with nonconvex penalties.
  • 6 STATISTICAL MULTI-LABEL LEARNING: Under suitable conditions, nonconvex-penalty analyses provide convergence rates involving sample size and true-support cardinality.
  • 6 STATISTICAL MULTI-LABEL LEARNING: Statistical properties of label-feature dependency models remain underexplored, despite existing approaches such as classifier chains, CCA, and CPLST.
  • 6 STATISTICAL MULTI-LABEL LEARNING: Copula-based dependency modeling offers unbiased and consistent estimation with asymptotic and mean-squared-error analysis, but cannot handle high-dimensional issues.

7 NEW APPLICATIONS

Multi-label learning is being applied to emerging problems across computer vision, including video annotation, facial action unit recognition, and neonatal brain white matter segmentation.

  • Computer Vision: Multi-label classification supports video indexing by assigning multiple semantic concepts to videos in large online corpora.TRECVID videos are annotated with more than one label from 39 concepts.
  • Computer Vision: Facial action unit recognition models multiple facial muscle movements to describe expressions and support mental state analysis.Action unit occurrences are strongly correlated and their sample distribution is unbalanced.
  • Computer Vision: Multi-label segmentation assigns one or multiple anatomical white matter bundle labels to each neonatal brain-imaging voxel.The formulation reflects cases where multiple fiber bundles pass through a single voxel.

7.2 Natural Language Processing

The section presents natural-language and user-centered applications of multi-label learning, spanning mobile recommendation, legal text mining, advertising, product queries, and user profiling.

  • Legal Text Mining: Legal text mining uses multiple orthogonal EUROVOC concepts to categorize European Union legal documents.The EUR-Lex dataset contains treaties, legislation, case-law, and legislative proposals.
  • Recommendation and User Modeling: Recommendation systems can be formulated as multi-label tasks because they recommend multiple items or preferences to users.Applications include recommending bid phrases from an advertisement landing page and relevant queries for products.
  • Recommendation and User Modeling: Extreme multi-label recommendation has been studied for advertising and item-to-item product recommendation.These applications use product, query, and customer purchase information alongside product metadata.
  • Recommendation and User Modeling: User profiling can be treated as multi-label learning to infer multiple user characteristics and personal interests from generated data.Correlations between profiles can support personalization in social-media and e-commerce services.

8 CONCLUSION

The paper surveys emerging multi-label learning topics, representative work, challenges, future directions, and new applications. It emphasizes extreme classification, limited supervision, deep, online, and statistical learning.

  • Conclusion: The survey covers six emerging topics: extreme classification, limited supervision, deep learning, online learning, statistical learning, and new applications.It provides an overview of representative works referenced throughout the paper.
  • Conclusion: The paper highlights challenges, future research directions, and promising extensions across these emerging multi-label learning topics.These directions are presented as opportunities for further study.

APPENDIX A EVALUATION METRICS AND NOTATIONS AND NEW APPLICATIONS

The appendix defines the multi-label classification setting, introduces evaluation metrics, and summarizes notation and application-specific metric usage.

  • Notation and Problem Definition: MLC learns a classifier from feature vectors and binary label vectors to predict labels for testing instances.n, d, and L denote the numbers of training data, feature dimensions, and labels.
  • Evaluation Metrics: Hamming loss measures label-wise prediction disagreement, while ranking loss evaluates reversely ordered label pairs.Ranking loss uses the complementary label set in the label space.
  • Evaluation Metrics: F-measure aggregates true and false positives and negatives across labels into an overall F-1 score.The metric summarizes label-level classification outcomes.
  • Evaluation Metrics: Precision@k and Recall@k measure top-k precision and recall and are standard metrics for extreme multi-label classification.F-measure and ranking loss are commonly used in recommender systems.
  • Appendix Resources: The appendix points readers to tables summarizing important notation and new multi-label learning applications.The application summary is presented in Table 3.
Loading 2011.11197v3…