PaperlayerView exact revision on arXiv

Source-linked AI summary

Comprehensive Comparative Study of Multi-Label Classification Methods

Jasmin Bogatinovski, Ljupčo Todorovski, Sašo Džeroski, Dragi Kocev

arXiv:2102.07113v2cs.LGcs.AIcs.CC

TL;DR

Existing MLC comparisons cover relatively limited sets of methods and datasets. This paper conducts a broad empirical study across methods, datasets, evaluation measures, and application domains, identifying several strong-performing methods and recommended baselines. Its conclusions remain bounded by the included datasets and the computational and interpretive costs of large-scale evaluation.

  • Problem

    Prior MLC studies provide limited comparative coverage of the available methods and datasets, making broader landscape mapping desirable.

  • Method

    The study empirically evaluates 26 MLC methods across 42 datasets using predictive-performance and efficiency criteria.

  • Results

    RFPCT, RFDTBR, EBRJ48, AdaBoost.MH, and ECCJ48 perform best across the evaluation measures, while RFPCT and RFDTBR are also among the most efficient.

  • Takeaways & Limitations

    The study provides guidance for selecting MLC methods and baselines when proposing new methods or working with new datasets.

  • Takeaways & Limitations

    The conclusions apply within the meta-space defined by the included datasets, and large studies are computationally expensive and difficult to interpret.

Abstract

from arXiv · show

Multi-label classification (MLC) has recently received increasing interest from the machine learning community. Several studies provide reviews of methods and datasets for MLC and a few provide empirical comparisons of MLC methods. However, they are limited in the number of methods and datasets considered. This work provides a comprehensive empirical study of a wide range of MLC methods on a plethora of datasets from various domains. More specifically, our study evaluates 26 methods on 42 benchmark datasets using 20 evaluation measures. The adopted evaluation methodology adheres to the highest literature standards for designing and executing large scale, time-budgeted experimental studies. First, the methods are selected based on their usage by the community, assuring representation of methods across the MLC taxonomy of methods and different base learners. Second, the datasets cover a wide range of complexity and domains of application. The selected evaluation measures assess the predictive performance and the efficiency of the methods. The results of the analysis identify RFPCT, RFDTBR, ECCJ48, EBRJ48 and AdaBoostMH as best performing methods across the spectrum of performance measures. Whenever a new method is introduced, it should be compared to different subsets of MLC methods, determined on the basis of the different evaluation criteria.

1 INTRODUCTION

MLC addresses prediction problems in which each example may receive multiple labels, motivating broader empirical guidance as methods and applications proliferate. This study maps a larger landscape of methods and datasets to identify useful baselines and performance strengths.

  • MLC predicts multiple binary labels simultaneously for each sample, unlike multi-class classification, where each example belongs to only one class.
  • MLC applications span image annotation, gene-function prediction, drug effects, text, biology, and multimedia.
  • Prior studies were limited by their coverage of methods and datasets, despite providing theoretical discussion, reviews, or smaller empirical comparisons.
  • The study evaluates 26 MLC methods on 42 benchmark datasets using 18 performance measures to map the method landscape and identify suitable baselines.
  • RFPCT, RFDTBR, ECCJ48, EBRJ48, and AdaBoost are identified as best-performing baseline candidates, with RFPCT and RFDTBR also more computationally efficient than competitors.

2 THE TASK OF MULTI-LABEL CLASSIFICATION

The study characterizes 42 multi-label datasets across domains and meta-features, defines the MLC task formally, and distinguishes two broad method categories.

  • Benchmark datasets: Most datasets come from biology, text, and multimedia, with additional datasets from medicine and chemistry.These domains cover tasks including gene-function prediction, topic classification, disease prediction, and chemical-concentration prediction.
  • Dataset characteristics: 42 datasets vary widely in size, description richness, label count, label cardinality, and label density.The study uses five basic dataset meta-features to describe this variation.
  • Dataset characteristics: The number of training examples ranges from 174 to 17190, while the number of features ranges from 19 to 9844.Most datasets contain 300 to 2000 features, and features are usually exclusively numeric or exclusively nominal.
  • Dataset characteristics: The number of labels ranges from 4 to 374, and label cardinality measures the mean number of labels associated with each example.In many datasets, cardinality is below 1.5, indicating approximately one label per example on average.
  • MLC task definition: MLC assigns each example a subset of relevant labels and a complementary set of irrelevant labels.The formal task uses an example space X, label space L, example-label pairs E, and a quality criterion q.
  • MLC task definition: The objective is to find a function h: X →2L that maximizes predictive performance while minimizing complexity.The study follows a taxonomy separating problem transformation from algorithm adaptation methods.

3 METHODS FOR MULTI-LABEL CLASSIFICATION

The evaluation covers problem transformation methods, algorithm adaptation methods, and ensemble variants, emphasizing label dependencies and high-dimensional label spaces.

  • Method organization: The methods section first describes problem transformation methods, followed by algorithm adaptation methods and their ensemble variants.This organization reflects the study’s taxonomy of MLC methods.
  • Method comparison: The discussion compares methods according to their treatment of label dependencies and high-dimensional label spaces, including computational complexity.These properties are considered across the described method families and ensemble variants.

3.1 Problem transformation methods

Problem transformation methods convert multi-label classification into one or more simpler single-target problems, trading modeling simplicity against label-dependency preservation and generalization limits. The study organizes these methods into transformation families and ensemble extensions.

  • Transformation taxonomy: Problem transformation methods decompose multi-label classification into binary or multi-class problems solved with single-target learners.The taxonomy includes One-Vs-All-like and One-Vs-One-like transformations.
  • Binary relevance methods: Binary Relevance trains one binary classifier per label, generalizes beyond observed label-sets, but ignores label correlations and is unsuitable for many labels.Each transformed problem shares the original feature space.
  • Label Powerset methods: Label Powerset treats each unique label-set as a separate multi-class class, preserving label relationships but failing to generalize beyond label-sets seen during training.It learns a single multi-class model rather than multiple binary models.
  • Label Powerset methods: Pruned Sets reduces the number of unique label-set classes by removing infrequent sets, subsampling their subsets, and adding a threshold that can create new label combinations at prediction.Its main tuning choices include the pruning value, subset count, and base multi-class classifier.
  • Ensemble and structured methods: Ensemble extensions include Meta Binary Relevance, Ensembles of Classifier Chains, Ensembles of Binary Relevance, Random Subspace, HOMER, and label-embedding approaches.These methods vary in how they augment features, sample data, organize labels, or represent the label space.

3.2 Algorithm Adaptation Methods

Algorithm adaptation methods modify single-target training or prediction procedures to handle multiple labels simultaneously. The reviewed methods span adapted trees, neural networks, neural-fuzzy models, support vector machines, nearest neighbors, and ensembles.

  • Adaptation principles: Algorithm adaptation methods modify the training and prediction phases of single-target learners to handle multiple labels simultaneously.Trees can predict multiple labels and use impurity measures accounting for label membership and non-membership.
  • Trees: Predictive Clustering Trees compute impurity from the sum of label Gini indices and return per-label probability vectors.They train and predict quickly and can provide interpretable results, while single trees may have poor performance and high variance.
  • Neural methods: Back-propagation Neural Networks use standard multilayer perceptrons trained by back-propagation, with learning rate, epochs, and hidden units as hyperparameters.The passage describes neural networks as potentially effective when many training samples are available.
  • Neural methods: Restricted Boltzmann Machines and stacked Deep Belief Networks learn alternative data representations that can serve as inputs to multi-label classifiers.The representation may improve performance at the cost of increased training time and space complexity.
  • Neural-fuzzy methods: MLARAM uses two self-organizing maps to encode input prototypes and associate them with labels, with vigilance controlling prototype specificity.The method is an extension of adaptive resonance associative map neural-fuzzy networks.
  • SVM methods: MLTSVM fits multiple nonparallel hyperplanes to capture multi-label information and is reported to outperform other SVM-based methods on Hamming loss and ranking measures.Its fast quadratic-problem procedures support rapid training.
  • Nearest-neighbor methods: MLkNN adapts nearest-neighbor classification by estimating prior and conditional probabilities to obtain posterior probabilities for each label.The number of neighbors is its principal parameter, and model construction is fast.
  • Ensembles: RFPCT combines random-forest sampling of instances and features with Predictive Clustering Trees as base learners.Its stated advantages are fast operation and inherent handling of label correlation.

3.3 Addressing Specific Properties of MLC

MLC adds complexity through label dependencies and high-dimensional, sparse label spaces, shaping both method design and computational demands. Methods address dependencies differently, while complexity varies with labels, base learners, ensembles, and clustering.

  • MLC is harder than binary classification because it adds complexity along the target dimension, especially label dependencies and high-dimensional label spaces.
  • 3.3.1 Label dependencies: Label dependencies describe relationships among labels and can strongly influence predictive performance, motivating methods that explicitly model or exploit them.
  • 3.3.2 High-dimensional label space: High-dimensional label spaces increase prediction time and affect performance, while their sparsity creates imbalanced subproblems and can hinder model learning.
  • 3.3.2 High-dimensional label space: BR and CC scale linearly with the number of labels, CLR quadratically, and LP exponentially in the worst case, although practical LP complexity is bounded by training data.
  • 3.3.2 High-dimensional label space: Computational complexity depends on the base learner, ensemble size, and architecture-specific operations such as HOMER’s label clustering.

4 EXPERIMENTAL DESIGN

The study uses a unified, time-budgeted experimental protocol to tune and evaluate MLC methods under common conditions. It measures predictive performance and efficiency, applies statistical tests, and acknowledges computational and dataset-coverage constraints.

  • The experimental design comprises methodology, setup, parameter instantiation, evaluation measures, and statistical analysis for a comprehensive comparison.
  • 4.1 Experimental methodology: The protocol samples up to 1000 training examples using iterative stratification, then performs 3-fold cross-validation with a 12-hour hyperparameter-search budget.
  • 4.1 Experimental methodology: After tuning, each method is retrained on the complete training set with a 7-day model-learning budget; methods exceeding it are marked DNF.
  • 4.1 Experimental methodology: The test set is used only for final predictive assessment, and methods without a model receive the worst possible value for each evaluation measure.
  • 4.4 Evaluation Measures: The study evaluates 18 predictive-performance criteria and 2 efficiency criteria, covering score or bipartition predictions and example-based or label-based measures.
  • 4.4 Evaluation Measures: Training and testing times are measured for practical guidance and interpreted alongside computational complexity, while corrected Friedman and post-hoc Nemenyi tests assess significance.
  • Limitations: Large-scale studies are computationally expensive, and conclusions are constrained to the meta-space defined by the included datasets’ characteristics.

5 RESULTS AND DISCUSSION

Across the evaluated methods, tree-based approaches and selected ensembles generally dominate, but performance depends on the evaluation measure and method architecture. RFDTBR and RFPCT are especially strong overall, while other methods trade precision against recall or vary across averaging schemes.

  • Problem transformation methods: RFDTBR is best ranked on 12 evaluation measures, second best on 3 more, and most efficient in training and testing time among problem transformation methods.EBRJ48, AdaBoost.MH, ECC J48, TREMLC, and PSt are also often top ranked, whereas CDN, SM, and HOMER perform worst.
  • Problem transformation methods: J48-based ensembles generally outperform their SVM counterparts, with EBR J48 ranked best on 14 of 18 predictive performance measures.EBR and ECC with J48 also provide strong results without parameter tuning and are fast to build.
  • Problem transformation methods: LP-based architectures perform well on recall and F1 but underperform on precision, ranking, threshold-independent, and macro-averaged label-based measures.Preserving label-sets can reduce per-label diversity, while BR-based methods rank higher on ranking and threshold-independent measures.
  • Problem transformation methods: PSt generally outperforms its BR counterpart for example-based and micro-averaged label-based measures, indicating that infrequent label-sets hurt LP-based approaches.PSt prunes infrequent label-sets before training the LP method.
  • Algorithm adaptation methods: RFPCT is best ranked on 17 of 18 performance measures, followed closely by BPNN, whose differences from RFPCT are not statistically significant.CLEMS and MLkNN lead on micro-averaged precision and are more conservative in assigning relevant labels.
  • Selected method comparison: Across selected methods, tree-based models—especially random-forest ensembles—are identified as state-of-the-art, while RFPCT and RFDTBR dominate threshold-independent measures.ECC J48 is strongest on recall, AdaBoost.MH on precision, and RFPCT's performance differs between macro- and micro-averaged recall.

6 CONCLUSION

This study maps MLC methods through the field’s largest empirical comparison, evaluating diverse methods and datasets under standardized experimental procedures. It identifies strong-performing and efficient methods while showing that method choice depends on evaluation context.

  • Implications: The study provides practitioner guidance for choosing MLC methods, selecting baselines for new methods, and identifying initial methods to try on new datasets.Its comprehensive design also motivates further analysis of measure relationships, dataset properties, meta-learning, and thresholding techniques.
  • Experimental scope: 26 MLC methods are evaluated on 42 datasets using 18 predictive-performance measures and 2 efficiency criteria across multiple application domains.The datasets include text, medicine, multimedia, bioinformatics, biology, and chemistry.
  • Experimental design: The experimental design uses time-constrained hyperparameter optimization, literature-based parameter values, and Friedman and Nemenyi statistical tests.Results are presented using average-rank analyses.
  • Main findings: RFPCT, RFDTBR, EBRJ48, AdaBoost.MH, and ECCJ48 emerge as the best-performing methods across the evaluation measures.The study first selects eight strong methods within method groups before comparing them to obtain a more compact set.
  • Main findings: RFPCT and RFDTBR are top-ranked across most evaluation measures and are the most efficient methods within the selected best-performing group.ECCJ48 is strong on recall-based measures but weak on precision-based measures, with the reverse pattern for AdaBoost.MH.

METHODS

The figures compare average ranks among MLC methods using example-based, ranking-based, threshold-independent, and label-based evaluation measures.

  • Example-based measures: Average rank diagrams compare the best MLC methods using example-based measures.
  • Ranking-based measures: Average rank diagrams compare the best MLC methods using ranking-based measures.
  • Threshold-independent measures: Average rank diagrams compare the best MLC methods using threshold-independent measures.
  • Label-based measures: Average rank diagrams compare the best MLC methods using label-based measures.
Loading 2102.07113v2…