A Review on Multi-Label Learning Algorithms

article2014TKDE3,289 citations

Presents a unified taxonomy and rigorous mathematical analysis of twelve representative multi-label learning algorithms across problem transformation and algorithm adaptation paradigms to guide the selection of appropriate methods and evaluation metrics.

Listen

Multi-label learning addresses the practical challenge that many real-world objects carry several semantic labels at once, such as news articles on multiple topics, videos depicting several scenes, or genes linked to multiple biological functions. Traditional single-label classification cannot capture this multiplicity, and the number of possible label combinations grows exponentially with the label space, making direct enumeration infeasible. Effective techniques therefore depend on exploiting statistical dependencies among labels while remaining computationally tractable.

The review systematically defines the multi-label setting, introduces example-based and label-based evaluation metrics, examines twelve representative algorithms in detail, surveys several extended research directions, and identifies open problems together with publicly available resources. The algorithms are grouped into problem-transformation methods, which recast the task as one or more single-label problems, and algorithm-adaptation methods, which modify existing learners to accept multi-label training data directly. Each algorithm is presented under uniform notation, with its order of label-correlation modeling, training and test complexity, and the surrogate loss it optimizes.

The analysis shows that first-order methods are simple and parallelizable but ignore label dependence; second-order methods capture pairwise interactions at moderate extra cost; and high-order methods model richer dependencies yet scale less well. Empirical and theoretical results indicate that optimizing subset accuracy and Hamming loss lead to different classifiers, that consistent surrogate losses exist for certain ranking-based metrics, and that ensemble constructions such as classifier chains or random k-labelsets often improve robustness. Extended topics include handling noisy or missing labels, leveraging unlabeled data via active or semi-supervised learning, performing dimensionality reduction, scaling to very large label spaces, and connections to related paradigms such as multi-instance or ordinal classification.

These findings matter because multi-label data now dominate text, image, audio, video, and bioinformatics applications; choosing an algorithm whose correlation-modeling order and complexity match the data scale directly affects accuracy, training time, and deployment feasibility. Practitioners should therefore match the chosen method to the size of the label space and the strength of observed dependencies rather than defaulting to the simplest baseline.

Future work should focus on principled characterizations of asymmetric or instance-specific label correlations, large-scale experimental comparisons across many metrics, and algorithms that remain effective when both the number of instances and the number of labels are very large. The main limitations of the review are its deliberate selection of twelve influential rather than exhaustive algorithms and the fact that reported complexities assume worst-case behavior; readers should verify performance on their own data distributions before committing to a production system.

MOE Key Laboratory of Computer Network and Information Integration Nanjing University School of Computer Science and Engineering Southeast University machine learning multi-label classification online learning Multi‑Label Learning Binary Relevance Classifier Chain

Zhang et al (2014).pdf

Paper: Multitask Learning, RICH CARUANA (1997). Reading Caruana's foundational multitask learning framework first is essential because multi-label learning algorithms often model label correlations by treating each label as a related task.
Paper: Machine learning in automated text categorization, Fabrizio Sebastiani (2001). Sebastiani's survey on automated text categorization provides the essential classification background and evaluation methodologies assumed by multi-label learning literature.

Paper: An Overview of Multi-Task Learning in Deep Neural Networks, Sebastian Ruder (2017). Ruder's overview of multi-task learning in deep neural networks naturally extends the survey's coverage of traditional multi-label algorithms into modern deep architectures.
Paper: Modeling Task Relationships in Multi-task Learning with Multi-gate Mixture-of-Experts, Jiaqi Ma et al. (2018). This paper applies multi-task learning principles to large-scale recommendation systems using Mixture-of-Experts, continuing the algorithmic themes reviewed in the source.

Cover for A Review on Multi-Label Learning Algorithms

Abstract

Multi-label learning studies the problem where each example is represented by a single instance while associated with a set of labels simultaneously. During the past decade, significant amount of progresses have been made towards this emerging machine learning paradigm. This paper aims to provide a timely review on this area, with emphasis on state-of-the-art multi-label learning algorithms. Firstly, fundamentals on multi-label learning including formal definition and evaluation metrics are given. Secondly and primarily, twelve representative multi-label learning algorithms are scrutinized under common notations, with corresponding analyses and discussions. Thirdly, several extended topics on multi-label learning are briefly summarized. As a conclusion, online resources and open research problems on multi-label learning are outlined for reference purposes.

Topics

machine learning multi-label classification online learning modeling languages

Keywords

Multi‑Label Learning Binary Relevance Classifier Chain Random k‑Labelset Calibrated Label Ranking Rank‑SVM ML‑kNN Evaluate Metric Exploit Label Correlation Transform Problem

A Review on Multi-Label Learning Algorithms
Index Terms
I. INTRODUCTION
II. THE PARADIGM
A. Formal Definition
B. Evaluation Metrics
III. LEARNING ALGORITHMS
A. Simple Categorization
B. Problem Transformation Methods
C. Algorithm Adaptation Methods
D. Summary
IV. EXTENDED TOPICS
A. Noisy/Weak Labels
B. Unlabeled Data
C. Dimensionality Reduction
D. Large-Scale Data
E. Related Learning Settings
V. CONCLUSION
REFERENCES

Knowls

Knowl 1 — Multi-Label Learning Problem Formulation and Data Multi-Labeledness Indicators
definition
Let $\mathcal{X} = \mathbb{R}^d$ (or $\mathbb{Z}^d$ ) denote the $d$ -dimensional instance space and $\mathcal{Y} = \{y_1, y_2, \dots, y_q\}$ denote the label space consisting of $q$ distinct binary class labels. Given a multi-label training set $D = \{(x_i, Y_i) \mid 1 \le i \le m\}$ , where $x_i = (x_{i1}, x_{i2}, \dots, x_{id})^\top \in \mathcal{X}$ is a feature vector and $Y_i \subseteq \mathcal{Y}$ is the subset of labels associated with $x_i$ , the goal of multi-label learning is to induce a classifier $h: \mathcal{X} \to 2^\mathcal{Y}$ that assigns a subset of proper labels to an unseen instance $x \in \mathcal{X}$ . Alternatively, learning systems often induce a real-valued scoring function $f: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ , where $f(x, y)$ reflects the confidence of label $y$ being relevant to $x$ , from which $h(x)$ is obtained via threshold calibration.

To quantitatively measure the structural properties and degree of multi-labeledness in a dataset $D$ , four statistical indicators are defined:
1. Label Cardinality ( $\text{LCard}$ ): The average number of relevant labels per training instance: $\text{LCard}(D) = \frac{1}{m} \sum_{i=1}^m |Y_i|$
2. Label Density ( $\text{LDen}$ ): The label cardinality normalized by the total number of possible labels in the label space: $\text{LDen}(D) = \frac{1}{q} \text{LCard}(D) = \frac{1}{m q} \sum_{i=1}^m |Y_i|$
3. Label Diversity ( $\text{LDiv}$ ): The number of distinct label subsets appearing in the dataset: $\text{LDiv}(D) = |\{Y \subseteq \mathcal{Y} \mid \exists x : (x, Y) \in D\}|$
4. Proportional Label Diversity ( $\text{PLDiv}$ ): The proportion of distinct label subsets relative to the total number of training examples: $\text{PLDiv}(D) = \frac{1}{|D|} \text{LDiv}(D) = \frac{1}{m} \text{LDiv}(D)$
Knowl 2 — Taxonomy of Label Correlation Exploitation Orders
model/method
The fundamental challenge of multi-label learning is the exponential size of the output space ( $2^q$ possible label combinations for $q$ class labels). To make learning tractable and achieve strong generalization, multi-label learning algorithms exploit label correlation information. Algorithmic strategies are categorized into three families based on the order of label correlations they model:
1. First-order strategy: Tackles the multi-label learning problem in a label-by-label fashion by decomposing the task into $q$ independent binary classification or estimation tasks, ignoring any co-existence among labels. This strategy offers maximum conceptual simplicity and computational scalability (enabling parallel processing), but can lead to suboptimal generalization performance due to neglecting label dependencies.
2. Second-order strategy: Models pairwise relationships between labels, such as the ranking order between relevant and irrelevant labels for a given instance or the pairwise interaction between any two labels. This strategy strikes a favorable balance between correlation-modeling capacity and computational feasibility, though it assumes that higher-order relationships can be decomposed into pairwise interactions.
3. High-order strategy: Models high-order correlations by accounting for the collective influence of all other labels on each target label, considering relationships within arbitrary random subsets of labels, or mapping all labels simultaneously to a shared lower-dimensional latent subspace. This family possesses the highest correlation-modeling expressiveness, but typically incurs substantial computational costs and scalability bottlenecks when $q$ is large.
Knowl 3 — Example-Based Multi-Label Evaluation Metrics
equation
Given a test dataset $S = \{(x_i, Y_i) \mid 1 \le i \le p\}$ with $p$ multi-label examples, a multi-label classifier $h: \mathcal{X} \to 2^\mathcal{Y}$ , and a real-valued ranking/confidence function $f: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ where $\text{rank}_f(x, y)$ denotes the descending rank of label $y$ according to $f(x, \cdot)$ , example-based metrics evaluate performance on each test example individually and then average the results across $S$ .

Classification Metrics (derived from $h$ ):
1. Subset Accuracy: Measures the exact match between the predicted and true label subsets: $\text{subsetacc}(h) = \frac{1}{p} \sum_{i=1}^p \llbracket h(x_i) = Y_i \rrbracket$ where $\llbracket \cdot \rrbracket$ evaluates to $1$ if the predicate holds and $0$ otherwise. The optimal value is $1$ .
2. Hamming Loss: Measures the fraction of misclassified instance-label pairs: $\text{hloss}(h) = \frac{1}{p} \sum_{i=1}^p \frac{1}{q} |h(x_i) \Delta Y_i|$ where $\Delta$ denotes the symmetric difference between two sets. The optimal value is $0$ .
3. Example-Based Accuracy, Precision, Recall, and $F_\beta$ : $\text{Accuracy}_{\text{exam}}(h) = \frac{1}{p} \sum_{i=1}^p \frac{|Y_i \cap h(x_i)|}{|Y_i \cup h(x_i)|}, \quad \text{Precision}_{\text{exam}}(h) = \frac{1}{p} \sum_{i=1}^p \frac{|Y_i \cap h(x_i)|}{|h(x_i)|}$ $\text{Recall}_{\text{exam}}(h) = \frac{1}{p} \sum_{i=1}^p \frac{|Y_i \cap h(x_i)|}{|Y_i|}, \quad F^\beta_{\text{exam}}(h) = \frac{(1 + \beta^2) \cdot \text{Precision}_{\text{exam}}(h) \cdot \text{Recall}_{\text{exam}}(h)}{\beta^2 \cdot \text{Precision}_{\text{exam}}(h) + \text{Recall}_{\text{exam}}(h)}$ with $\beta > 0$ (commonly $\beta = 1$ ).
Ranking Metrics (derived from $f$ ):
1. One-error: Fraction of examples whose top-ranked label is irrelevant (optimal value $0$ ): $\text{one-error}(f) = \frac{1}{p} \sum_{i=1}^p \llbracket [\arg\max_{y \in \mathcal{Y}} f(x_i, y)] \notin Y_i \rrbracket$
2. Coverage: Average number of steps required to descend down the ranked label list to cover all relevant labels (optimal value $\frac{1}{p}\sum_{i=1}^p |Y_i| - 1$ ): $\text{coverage}(f) = \frac{1}{p} \sum_{i=1}^p \max_{y \in Y_i} \text{rank}_f(x_i, y) - 1$
3. Ranking Loss: Fraction of label pairs where an irrelevant label is ranked above a relevant label (optimal value $0$ ): $\text{rloss}(f) = \frac{1}{p} \sum_{i=1}^p \frac{1}{|Y_i||\bar{Y}_i|} |\{(y', y'') \in Y_i \times \bar{Y}_i \mid f(x_i, y') \le f(x_i, y'')\}|$ where $\bar{Y}_i = \mathcal{Y} \setminus Y_i$ .
4. Average Precision: Average proportion of relevant labels ranked higher than each specific relevant label (optimal value $1$ ): $\text{avgprec}(f) = \frac{1}{p} \sum_{i=1}^p \frac{1}{|Y_i|} \sum_{y \in Y_i} \frac{|\{y' \in Y_i \mid \text{rank}_f(x_i, y') \le \text{rank}_f(x_i, y)\}|}{\text{rank}_f(x_i, y)}$
Knowl 4 — Label-Based Multi-Label Evaluation Metrics
equation
Given a test set $S = \{(x_i, Y_i) \mid 1 \le i \le p\}$ , a classifier $h: \mathcal{X} \to 2^\mathcal{Y}$ , and a scoring function $f: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ , label-based metrics evaluate the performance on each class label $y_j \in \mathcal{Y}$ ( $1 \le j \le q$ ) separately and then aggregate across all $q$ labels using macro-averaging (equal weight per label) or micro-averaging (equal weight per test instance).

For each label $y_j$ , the basic binary quantities are: $TP_j = |\{x_i \mid y_j \in Y_i \land y_j \in h(x_i)\}|, \quad FP_j = |\{x_i \mid y_j \notin Y_i \land y_j \in h(x_i)\}|$ $TN_j = |\{x_i \mid y_j \notin Y_i \land y_j \notin h(x_i)\}|, \quad FN_j = |\{x_i \mid y_j \in Y_i \land y_j \notin h(x_i)\}|$ where $TP_j + FP_j + TN_j + FN_j = p$ .

For any binary classification metric $B(TP_j, FP_j, TN_j, FN_j) \in \{\text{Accuracy}, \text{Precision}, \text{Recall}, F^\beta\}$ :
- Macro-averaging: $B_{\text{macro}}(h) = \frac{1}{q} \sum_{j=1}^q B(TP_j, FP_j, TN_j, FN_j)$
- Micro-averaging: $B_{\text{micro}}(h) = B\left(\sum_{j=1}^q TP_j, \sum_{j=1}^q FP_j, \sum_{j=1}^q TN_j, \sum_{j=1}^q FN_j\right)$
For ranking evaluation with scoring function $f$ , let $Z_j = \{x_i \mid y_j \in Y_i\}$ and $\bar{Z}_j = \{x_i \mid y_j \notin Y_i\}$ . Macro-averaged AUC is given by: $\text{AUC}_{\text{macro}} = \frac{1}{q} \sum_{j=1}^q \frac{|\{(x', x'') \in Z_j \times \bar{Z}_j \mid f(x', y_j) \ge f(x'', y_j)\}|}{|Z_j||\bar{Z}_j|}$

Similarly, letting $S^+ = \{(x_i, y) \mid y \in Y_i\}$ and $S^- = \{(x_i, y) \mid y \notin Y_i\}$ , micro-averaged AUC is: $\text{AUC}_{\text{micro}} = \frac{|\{((x', y'), (x'', y'')) \in S^+ \times S^- \mid f(x', y') \ge f(x'', y'')\}|}{|S^+||S^-|}$
Knowl 5 — Theoretical Consistency and Incompatibility of Multi-Label Loss Functions
theoretical result
Theoretical analysis of multi-label evaluation metrics reveals metric incompatibility and establishes necessary and sufficient conditions for asymptotic consistency when minimizing surrogate loss functions:
1. Metric Incompatibility: Multi-label classifiers optimized specifically to maximize subset accuracy (subset zero-one loss) exhibit provably poor performance when evaluated under Hamming loss, and vice versa. No single model can simultaneously optimize both metrics unless label dependencies are trivial.
2. Consistency of Surrogate Losses: A multi-label learning algorithm minimizing a surrogate loss function is statistically consistent if the expected surrogate risk minimizer converges to the true Bayes-optimal multi-label risk minimizer as the training set size $m \to \infty$ . For a fixed joint distribution over $\mathcal{X} \times 2^\mathcal{Y}$ , consistency holds if and only if the set of classifiers yielding optimal surrogate loss is a subset of the classifiers yielding optimal original multi-label loss.
3. Ranking Loss Inconsistency and Consistency Conditions:
  - Negative Result: No pairwise convex surrogate loss defined over pairs of labels ( $(y_j, y_k) \in Y_i \times \bar{Y}_i$ ) is consistent with ranking loss, even under deterministic multi-label settings (where $P(Y \mid x) > 0.5$ for some $Y$ ).
  - Positive Result: By reducing multi-label ranking to the bipartite ranking framework, simple univariate convex surrogate losses (such as exponential or logistic losses) defined on individual labels are statistically consistent with ranking loss, admitting explicit regret bounds and convergence rates.
Knowl 6 — Threshold Calibration via Stacking Linear Models
model/method
When a multi-label learning algorithm outputs a real-valued confidence vector $f^*(x) = (f(x, y_1), f(x, y_2), \dots, f(x, y_q))^\top \in \mathbb{R}^q$ for an instance $x \in \mathcal{X}$ , a thresholding function $t: \mathcal{X} \to \mathbb{R}$ is required to discretize scores into a predicted label subset $h(x) = \{y_j \in \mathcal{Y} \mid f(x, y_j) > t(x)\}$ .

In the stacking-based threshold calibration strategy, $t(x)$ is parameterized as a linear model over the score vector: $t(x) = \langle w^*, f^*(x) \rangle + b^*$ where $w^* \in \mathbb{R}^q$ is a weight vector and $b^* \in \mathbb{R}$ is a bias parameter. To determine $(w^*, b^*)$ , a target threshold $s(x_i)$ is computed for each training example $(x_i, Y_i) \in D$ as the scalar that minimizes the classification errors between relevant ( $Y_i$ ) and irrelevant ( $\bar{Y}_i$ ) labels: $s(x_i) = \arg\min_{a \in \mathbb{R}} \left( |\{y_j \in Y_i \mid f(x_i, y_j) \le a\}| + |\{y_k \in \bar{Y}_i \mid f(x_i, y_k) \ge a\}| \right)$

The parameters $(w^*, b^*)$ are then learned by solving the following linear least squares regression problem: $\min_{\{w^*, b^*\}} \sum_{i=1}^m \left( \langle w^*, f^*(x_i) \rangle + b^* - s(x_i) \right)^2$
Knowl 7 — Binary Relevance and AdaBoost.MH Transformation Methods
model/method
Binary Relevance (BR) and AdaBoost.MH transform multi-label learning into binary classification tasks:
1. Binary Relevance (BR):
  - Transformation: Decomposes the multi-label dataset $D = \{(x_i, Y_i)\}_{i=1}^m$ into $q$ independent binary datasets $D_j = \{(x_i, \phi(Y_i, y_j)) \mid 1 \le i \le m\}$ for $1 \le j \le q$ , where $\phi(Y_i, y_j) = +1$ if $y_j \in Y_i$ and $-1$ otherwise.
  - Learning & Inference: A binary learning algorithm $B$ trains $q$ classifiers $g_j \leftarrow B(D_j)$ . Predictions are formed as $Y = \{y_j \mid g_j(x) > 0\}$ . If $Y = \emptyset$ , the T-Criterion selects $y_{j^*}$ where $j^* = \arg\max_{1 \le j \le q} g_j(x)$ .
  - Properties: First-order method with training time complexity $O(q \cdot \mathcal{F}_B(m, d))$ and testing complexity $O(q \cdot \mathcal{F}'_B(d))$ . It optimizes Hamming loss but ignores label correlations and is sensitive to class imbalance.
2. AdaBoost.MH:
  - Transformation: Constructs a single consolidated binary dataset $D^* = \{([x_i, y_j], \phi(Y_i, y_j)) \mid 1 \le i \le m, 1 \le j \le q\}$ of size $m q$ in a $(d+1)$ -dimensional space by concatenating the instance feature vector with a label identifier.
  - Learning & Inference: A base learner $B$ (specifically AdaBoost) induces a single classifier $g^* \leftarrow B(D^*)$ , and the predicted set is $Y = \{y_j \mid g^*(x, y_j) > 0\}$ .
  - Properties: High-order method with training complexity $O(\mathcal{F}_B(m q, d+1))$ and per-instance testing complexity $O(q \cdot \mathcal{F}'_B(d+1))$ . It directly minimizes Hamming loss while modeling dependencies through shared instance representations.
Knowl 8 — Classifier Chains (CC) and Ensemble of Classifier Chains (ECC)
algorithm
Classifier Chains (CC) is a high-order problem transformation algorithm that links $q$ binary classifiers along a specified label ordering $\tau: \{1, \dots, q\} \to \{1, \dots, q\}$ , such that each classifier uses the predictions of all preceding classifiers as augmented features.
Algorithm ClassifierChains(D, B, \tau, x)
  Input: Training set $D = \{(x_i, Y_i)\}_{i=1}^m$ , binary learning algorithm $B$ , label permutation $\tau$ , query instance $x$
  Output: Predicted label set $Y \subseteq \mathcal{Y}$
  for $j = 1$ to $q$ do
    Construct chained dataset $D_{\tau(j)} = \{([x_i, \text{pre}_{\tau(j)}^i], \phi(Y_i, y_{\tau(j)})) \mid 1 \le i \le m\}$ , where $\text{pre}_{\tau(j)}^i = (\phi(Y_i, y_{\tau(1)}), \dots, \phi(Y_i, y_{\tau(j-1)}))^\top$
    Induce binary classifier $g_{\tau(j)} \leftarrow B(D_{\tau(j)})$
  end for
   $\lambda_{\tau(1)}^x = \text{sign}[g_{\tau(1)}(x)]$
  for $j = 2$ to $q$ do
     $\lambda_{\tau(j)}^x = \text{sign}[g_{\tau(j)}([x, \lambda_{\tau(1)}^x, \dots, \lambda_{\tau(j-1)}^x])]$
  end for
   $Y = \{y_{\tau(j)} \mid \lambda_{\tau(j)}^x = +1, 1 \le j \le q\}$
  return $Y$
To mitigate sensitivity to label ordering $\tau$ , an Ensemble of Classifier Chains (ECC) trains $n$ separate classifier chains $\{\tau^{(1)}, \dots, \tau^{(n)}\}$ on bootstrap or sub-sampled replicas of $D$ ( $|D^{(r)}| = 0.67|D|$ without replacement or $|D^{(r)}| = |D|$ with replacement). Predictions across chains are aggregated via thresholded voting.

The training complexity of a single chain is $O(q \cdot \mathcal{F}_B(m, d+q))$ and the per-instance testing complexity is $O(q \cdot \mathcal{F}'_B(d+q))$ .
Knowl 9 — Calibrated Label Ranking (CLR)
algorithm
Calibrated Label Ranking (CLR) transforms multi-label learning into a pairwise label ranking task calibrated with an artificial virtual label $y_V$ that acts as a natural boundary separating relevant and irrelevant labels.
Algorithm CalibratedLabelRanking(D, B, x)
  Input: Training set $D = \{(x_i, Y_i)\}_{i=1}^m$ , binary learner $B$ , query instance $x$
  Output: Predicted label set $Y \subseteq \mathcal{Y}$
  for $j = 1$ to $q - 1$ do
    for $k = j + 1$ to $q$ do
      Construct $D_{jk} = \{(x_i, \psi(Y_i, y_j, y_k)) \mid \phi(Y_i, y_j) \ne \phi(Y_i, y_k), 1 \le i \le m\}$ , where $\psi(Y_i, y_j, y_k) = +1$ if $y_j \in Y_i, y_k \notin Y_i$ and $-1$ otherwise
      Induce binary classifier $g_{jk} \leftarrow B(D_{jk})$
    end for
  end for
  for $j = 1$ to $q$ do
    Construct $D_{jV} = \{(x_i, \phi(Y_i, y_j)) \mid 1 \le i \le m\}$ , where $\phi(Y_i, y_j) = +1$ if $y_j \in Y_i$ and $-1$ otherwise
    Induce virtual boundary classifier $g_{jV} \leftarrow B(D_{jV})$
  end for
  for $j = 1$ to $q$ do
     $\zeta^*(x, y_j) = \sum_{k=1}^{j-1} \llbracket g_{kj}(x) \le 0 \rrbracket + \sum_{k=j+1}^q \llbracket g_{jk}(x) > 0 \rrbracket + \llbracket g_{jV}(x) > 0 \rrbracket$
  end for
   $\zeta^*(x, y_V) = \sum_{j=1}^q \llbracket g_{jV}(x) \le 0 \rrbracket$
   $Y = \{y_j \mid \zeta^*(x, y_j) > \zeta^*(x, y_V), 1 \le j \le q\}$
  return $Y$
CLR trains $\frac{q(q-1)}{2}$ pairwise classifiers plus $q$ calibration classifiers (total $\frac{q(q+1)}{2}$ binary classifiers). It is a second-order method that mitigates class imbalance through pairwise decomposition. Its training complexity is $O(q^2 \cdot \mathcal{F}_B(m, d))$ and testing complexity is $O(q^2 \cdot \mathcal{F}'_B(d))$ .
Knowl 10 — Random k-Labelsets (RAkEL)
algorithm
Random k-Labelsets (RAkEL) transforms multi-label learning into an ensemble of multi-class classification problems, using the Label Powerset (LP) transformation on randomly selected small subsets of labels ( $k$ -labelsets) to balance computational efficiency, predictive completeness, and high-order correlation modeling.
Algorithm RandomKLabelsets(D, M, k, n, x)
  Input: Training set $D = \{(x_i, Y_i)\}_{i=1}^m$ , multi-class learner $M$ , labelset size $k$ , ensemble size $n$ , query instance $x$
  Output: Predicted label set $Y \subseteq \mathcal{Y}$
  for $r = 1$ to $n$ do
    Randomly select a subset $Y^k(l_r) \subseteq \mathcal{Y}$ such that $|Y^k(l_r)| = k$
    Construct multi-class dataset $D^\dagger_{Y^k(l_r)} = \{(x_i, \sigma(Y_i \cap Y^k(l_r))) \mid 1 \le i \le m\}$ , where $\sigma: 2^{Y^k(l_r)} \to \mathbb{N}$ maps each distinct label combination to a unique class index
    Induce multi-class classifier $g^\dagger_{Y^k(l_r)} \leftarrow M(D^\dagger_{Y^k(l_r)})$
  end for
  for $j = 1$ to $q$ do
     $\tau(x, y_j) = \sum_{r=1}^n \llbracket y_j \in Y^k(l_r) \rrbracket$
     $\mu(x, y_j) = \sum_{r=1}^n \llbracket y_j \in \sigma^{-1}(g^\dagger_{Y^k(l_r)}(x)) \rrbracket$
  end for
   $Y = \{y_j \mid \mu(x, y_j) / \tau(x, y_j) > 0.5, 1 \le j \le q\}$
  return $Y$
Typical default hyperparameter settings are $k = 3$ and $n = 2q$ . The computational complexity is $O(n \cdot \mathcal{F}_M(m, d, 2^k))$ for training and $O(n \cdot \mathcal{F}'_M(d, 2^k))$ for testing, where $\mathcal{F}_M(m, d, K)$ is the complexity of inducing a $K$ -class classifier on $m$ examples of dimension $d$ .
Knowl 11 — Multi-Label k-Nearest Neighbor (ML-kNN)
algorithm
Multi-Label $k$ -Nearest Neighbor (ML-kNN) is a first-order algorithm adaptation method that extends the nearest neighbor paradigm by applying Maximum A Posteriori (MAP) Bayesian reasoning over the label counts in the neighborhood of an instance.
Algorithm ML-kNN(D, k, s, x)
  Input: Training set $D = \{(x_i, Y_i)\}_{i=1}^m$ , number of neighbors $k$ , Laplace smoothing parameter $s$ (default $s=1$ ), query instance $x$
  Output: Predicted label set $Y \subseteq \mathcal{Y}$
  for $i = 1$ to $m$ do
    Identify the $k$ nearest neighbors $\mathcal{N}(x_i)$ of $x_i$ in $D \setminus \{(x_i, Y_i)\}$ (using Euclidean distance)
  end for
  for $j = 1$ to $q$ do
     $P(H_j) = \frac{s + \sum_{i=1}^m \llbracket y_j \in Y_i \rrbracket}{2s + m}, \quad P(\neg H_j) = 1 - P(H_j)$
    Initialize frequency arrays $\kappa_j[r] = 0$ and $\tilde{\kappa}_j[r] = 0$ for $r \in \{0, 1, \dots, k\}$
    for $i = 1$ to $m$ do
       $\delta_j(x_i) = \sum_{(x^*, Y^*) \in \mathcal{N}(x_i)} \llbracket y_j \in Y^* \rrbracket$
      if $y_j \in Y_i$ then
         $\kappa_j[\delta_j(x_i)] = \kappa_j[\delta_j(x_i)] + 1$
      else
         $\tilde{\kappa}_j[\delta_j(x_i)] = \tilde{\kappa}_j[\delta_j(x_i)] + 1$
      end if
    end for
  end for
  Identify the $k$ nearest neighbors $\mathcal{N}(x)$ of query instance $x$ in $D$
   $Y = \emptyset$
  for $j = 1$ to $q$ do
     $C_j = \sum_{(x^*, Y^*) \in \mathcal{N}(x)} \llbracket y_j \in Y^* \rrbracket$
     $P(C_j \mid H_j) = \frac{s + \kappa_j[C_j]}{s(k + 1) + \sum_{r=0}^k \kappa_j[r]}$
     $P(C_j \mid \neg H_j) = \frac{s + \tilde{\kappa}_j[C_j]}{s(k + 1) + \sum_{r=0}^k \tilde{\kappa}_j[r]}$
    if $P(H_j) \cdot P(C_j \mid H_j) > P(\neg H_j) \cdot P(C_j \mid \neg H_j)$ then
       $Y = Y \cup \{y_j\}$
    end if
  end for
  return $Y$
The computational complexity of ML-kNN is $O(m^2 d + q m k)$ for training (offline neighbor search and frequency table compilation) and $O(m d + q k)$ for per-instance testing.
Knowl 12 — Multi-Label Decision Tree (ML-DT) with Decomposable Multi-Label Entropy
algorithm
Multi-Label Decision Tree (ML-DT) adapts decision tree induction to multi-label learning by computing an information gain criterion based on a decomposable multi-label entropy under the assumption of label independence.

For any dataset partition $T = \{(x_i, Y_i)\}_{i=1}^n$ , multi-label entropy is computed as: $\text{MLEnt}(T) = \sum_{j=1}^q \left( -p_j \log_2 p_j - (1 - p_j) \log_2(1 - p_j) \right)$ where $p_j = \frac{1}{|T|} \sum_{(x_i, Y_i) \in T} \llbracket y_j \in Y_i \rrbracket$ is the proportion of examples possessing label $y_j$ .
Algorithm ML-DT(D, C, x)
  Input: Training set $D = \{(x_i, Y_i)\}_{i=1}^m$ , stopping criterion $C$ , query instance $x$
  Output: Predicted label set $Y \subseteq \mathcal{Y}$
  Function BuildTree(T):
    if stopping criterion $C$ is met on subset $T$ then
      return LeafNode(T)
    else
      Find feature $l$ and threshold $\vartheta$ maximizing information gain:
       $IG(T, l, \vartheta) = \text{MLEnt}(T) - \frac{|T^-|}{|T|}\text{MLEnt}(T^-) - \frac{|T^+|}{|T|}\text{MLEnt}(T^+)$
      where $T^- = \{(x_i, Y_i) \in T \mid x_{il} \le \vartheta\}$ and $T^+ = \{(x_i, Y_i) \in T \mid x_{il} > \vartheta\}$
      return InternalNode(l, \vartheta, \text{BuildTree}(T^-), \text{BuildTree}(T^+))
    end if
  Tree = BuildTree(D)
  Traverse $x$ through Tree to reach leaf node containing subset $T_\text{leaf} \subseteq D$
   $Y = \{y_j \mid p_j > 0.5, 1 \le j \le q\}$ , where $p_j = \frac{1}{|T_\text{leaf}|} \sum_{(x_i, Y_i) \in T_\text{leaf}} \llbracket y_j \in Y_i \rrbracket$
  return $Y$
ML-DT is a first-order method with training complexity $O(m d q)$ and testing complexity $O(m q)$ .
Knowl 13 — Ranking Support Vector Machine (Rank-SVM)
model/method
Ranking Support Vector Machine (Rank-SVM) adapts the maximum margin principle to multi-label learning by jointly learning $q$ linear classifiers $\mathcal{W} = \{(w_j, b_j) \mid w_j \in \mathbb{R}^d, b_j \in \mathbb{R}\}_{j=1}^q$ to minimize surrogate ranking loss over relevant-irrelevant label pairs.

For each training instance $(x_i, Y_i)$ , the signed $L_2$ -margin over all relevant-irrelevant label pairs $(y_j, y_k) \in Y_i \times \bar{Y}_i$ is maximized. Rank-SVM solves the following convex Quadratic Program (QP): $\min_{\{\mathcal{W}, \Xi\}} \sum_{j=1}^q \|w_j\|^2 + C \sum_{i=1}^m \frac{1}{|Y_i||\bar{Y}_i|} \sum_{(y_j, y_k) \in Y_i \times \bar{Y}_i} \xi_{ijk}$ $\text{subject to } \langle w_j - w_k, x_i \rangle + b_j - b_k \ge 1 - \xi_{ijk}, \quad \xi_{ijk} \ge 0 \quad (1 \le i \le m, (y_j, y_k) \in Y_i \times \bar{Y}_i)$ where $C > 0$ balances margin maximization and hinge ranking loss violation, and $\Xi = \{\xi_{ijk}\}$ are slack variables.

Nonlinear decision surfaces are accommodated by solving the dual formulation via kernel tricks. Predictions for query instance $x$ are produced using a stacking threshold model: $Y = \{y_j \mid \langle w_j, x \rangle + b_j > \langle w^*, f^*(x) \rangle + b^*, 1 \le j \le q\}$ where $f^*(x) = (\langle w_1, x\rangle + b_1, \dots, \langle w_q, x\rangle + b_q)^\top$ .

Let $\mathcal{F}_{\text{QP}}(a, b)$ denote the complexity of solving a QP with $a$ variables and $b$ constraints. Rank-SVM has training complexity $O(\mathcal{F}_{\text{QP}}(d q + m q^2, m q^2) + q^2(q + m))$ and testing complexity $O(d q)$ .
Knowl 14 — Backpropagation for Multi-Label Learning (BP-MLL)
model/method
BP-MLL adapts feed-forward neural networks to multi-label learning by optimizing an exponential surrogate ranking loss defined over relevant and irrelevant label pairs.

The network architecture consists of $d$ input units, $s$ hidden units with weight matrix $V \in \mathbb{R}^{d \times s}$ and bias vector $\gamma \in \mathbb{R}^s$ , and $q$ output units with weight matrix $W \in \mathbb{R}^{s \times q}$ and bias vector $\theta \in \mathbb{R}^q$ , using the activation function $\eta(a) = \tanh(a) = \frac{e^a - e^{-a}}{e^a + e^{-a}}$ .

The global network loss function is defined as: $E = \sum_{i=1}^m \frac{1}{|Y_i||\bar{Y}_i|} \sum_{(y_j, y_k) \in Y_i \times \bar{Y}_i} \exp\left( - (c_j^i - c_k^i) \right)$ where $c_j^i$ is the network's output on instance $x_i$ for label $y_j$ .

For each example $(x_i, Y_i)$ with hidden activations $b_u = \eta(\sum_{l=1}^d x_{il} v_{lu} + \gamma_u)$ and outputs $c_j^i = \eta(\sum_{u=1}^s w_{uj} b_u + \theta_j)$ , parameters are updated via gradient descent with learning rate $\alpha \in [0, 1]$ : $\Delta w_{uj} = \alpha d_j b_u, \quad \Delta \theta_j = \alpha d_j, \quad \Delta v_{lu} = \alpha e_u x_{il}, \quad \Delta \gamma_u = \alpha e_u$ where the error terms are: $d_j = \begin{cases} \left( \frac{1}{|Y_i||\bar{Y}_i|} \sum_{y_k \in \bar{Y}_i} \exp(-(c_j^i - c_k^i)) \right) (1 + c_j^i)(1 - c_j^i) & \text{if } y_j \in Y_i \\ -\left( \frac{1}{|Y_i||\bar{Y}_i|} \sum_{y_k \in Y_i} \exp(-(c_k^i - c_j^i)) \right) (1 + c_j^i)(1 - c_j^i) & \text{if } y_j \in \bar{Y}_i \end{cases}$ $e_u = \left( \sum_{j=1}^q d_j w_{uj} \right) (1 + b_u)(1 - b_u)$

Predicted labels are obtained via stacking threshold calibration $Y = \{y_j \mid c_j > \langle w^*, c \rangle + b^*\}$ . BP-MLL has training complexity $O(s(d + q)m N + q^2(q + m))$ for $N$ epochs and testing complexity $O(s(d + q))$ .
Knowl 15 — Collective Multi-Label (CML) Classification via Maximum Entropy
model/method
Collective Multi-Label Classifier (CML) adapts the Maximum Entropy / Conditional Random Field (CRF) framework to multi-label learning, modeling the joint conditional label distribution $p(y \mid x)$ subject to empirical feature-label and pairwise label-label constraints.

Representing labels as a binary vector $y = (y_1, \dots, y_q)^\top \in \{-1, +1\}^q$ , the conditional distribution is parameterised as a Gibbs distribution: $p(y \mid x) = \frac{1}{Z_\Lambda(x)} \exp\left( \sum_{k \in \mathcal{K}} \lambda_k f_k(x, y) \right)$ where $Z_\Lambda(x) = \sum_{y \in \{-1, +1\}^q} \exp\left( \sum_{k \in \mathcal{K}} \lambda_k f_k(x, y) \right)$ is the partition function, and constraints $\mathcal{K} = \mathcal{K}_1 \cup \mathcal{K}_2$ consist of:
1. $d \cdot q$ feature-label constraints: $f_k(x, y) = x_l \cdot \llbracket y_j = +1 \rrbracket$ for $(l, j) \in \mathcal{K}_1$ .
2. $4 \binom{q}{2}$ pairwise label correlation constraints: $f_k(x, y) = \llbracket y_{j_1} = b_1 \rrbracket \cdot \llbracket y_{j_2} = b_2 \rrbracket$ for $(j_1, j_2, b_1, b_2) \in \mathcal{K}_2$ where $b_1, b_2 \in \{-1, +1\}$ .
Assuming a zero-mean Gaussian prior $\lambda_k \sim \mathcal{N}(0, \varepsilon^2)$ , parameters $\Lambda = \{\lambda_k\}$ are determined by maximizing the convex penalized log-posterior: $l(\Lambda \mid D) = \sum_{(x, y) \in D} \left( \sum_{k \in \mathcal{K}} \lambda_k f_k(x, y) - \log Z_\Lambda(x) \right) - \sum_{k \in \mathcal{K}} \frac{\lambda_k^2}{2\varepsilon^2}$ via unconstrained optimization methods (e.g., BFGS) using gradients: $\frac{\partial l(\Lambda \mid D)}{\partial \lambda_k} = \sum_{(x, y) \in D} \left( f_k(x, y) - \sum_{y'} f_k(x, y') p(y' \mid x) \right) - \frac{\lambda_k}{\varepsilon^2}$

Predictions are obtained via MAP inference $Y = \arg\max_{y \in \{-1, +1\}^q} p(y \mid x)$ , with pruning applied when $q$ is large. CML has training complexity $O(\mathcal{F}_{\text{UNC}}(d q + q^2, m))$ and testing complexity $O((d q + q^2) \cdot 2^q)$ .
Knowl 16 — Multi-Label Least Squares (MLLS) via Shared Subspace Learning
model/method
Multi-Label Least Squares (MLLS) models high-order label correlations by assuming that $q$ linear scoring functions share a common $r$ -dimensional latent subspace ( $r \ll d$ ) parameterized by an orthonormal matrix $\Theta \in \mathbb{R}^{r \times d}$ (satisfying $\Theta \Theta^\top = I$ ).

The prediction scoring function is: $f(x, y_j) = (w_j + \Theta^\top v_j)^\top x$ where $W = [w_1, \dots, w_q] \in \mathbb{R}^{d \times q}$ and $V = [v_1, \dots, v_q] \in \mathbb{R}^{r \times q}$ . Setting $U = W + \Theta^\top V \in \mathbb{R}^{d \times q}$ , instance matrix $X \in \mathbb{R}^{m \times d}$ , and target label matrix $Y \in \{-1, +1\}^{m \times q}$ , MLLS minimizes the regularized squared loss: $\min_{\{\Theta, U, V\}} \frac{1}{m} \|X U - Y\|_F^2 + \alpha \|U - \Theta^\top V\|_F^2 + \beta \|U\|_F^2 \quad \text{subject to } \Theta \Theta^\top = I$ where $\alpha > 0$ controls the degree of subspace sharing and $\beta > 0$ regularizes model complexity.

The optimal solution is derived in closed form:
1. $V = \Theta U$
2. $U = \frac{1}{m} (M - \alpha \Theta^\top \Theta)^{-1} X^\top Y$ , where $M = \frac{1}{m} X^\top X + (\alpha + \beta) I$
3. Optimal $\Theta$ maximizes $\text{trace}\left( (\Theta S_1 \Theta^\top)^{-1} (\Theta S_2 \Theta^\top) \right)$ subject to $\Theta \Theta^\top = I$ , where $S_1 = I - \alpha M^{-1}$ and $S_2 = M^{-1} X^\top Y Y^\top X M^{-1}$ . It is computed by finding the top $r$ eigenvectors $Z \in \mathbb{R}^{d \times r}$ of the generalized eigenvalue problem $S_1 z = \lambda S_2 z$ and setting $\Theta = Z_Q^\top$ via reduced QR factorization $Z = Z_Q Z_R$ .
Inference predicts $Y = \{y_j \mid (w_j + \Theta^\top v_j)^\top x > 0\}$ . The training complexity is $O(d m^2 + r q^2 + d r^2)$ and testing complexity is $O(d q)$ .

Knowl 17 — Comparative Summary of Representative Multi-Label Learning Algorithms

data/table

The twelve representative multi-label learning algorithms differ fundamentally across design strategy (problem transformation vs. algorithm adaptation), correlation order, computational scalability, and the specific surrogate loss metric they optimize.

Algorithm	Category / Basic Idea	Correlation Order	Training Complexity	Testing Complexity	Optimized Metric
Binary Relevance (BR)	Transformation to $q$ binary classifiers	First-order	$\mathcal{O}(q \cdot \mathcal{F}_B(m, d))$	$\mathcal{O}(q \cdot \mathcal{F}'_B(d))$	Hamming loss
AdaBoost.MH	Transformation to 1 binary classifier	High-order	$\mathcal{O}(\mathcal{F}_B(m q, d+1))$	$\mathcal{O}(q \cdot \mathcal{F}'_B(d+1))$	Hamming loss
Stacked Aggregation	Transformation to stacked binary classifiers	High-order	$\mathcal{O}(q \cdot \mathcal{F}_B(m, d+q))$	$\mathcal{O}(q \cdot \mathcal{F}'_B(d+q))$	Hamming loss
Classifier Chains (CC)	Transformation to a chain of binary classifiers	High-order	$\mathcal{O}(q \cdot \mathcal{F}_B(m, d+q))$	$\mathcal{O}(q \cdot \mathcal{F}'_B(d+q))$	Hamming loss
Calibrated Label Ranking	Transformation to $q(q+1)/2$ pairwise classifiers	Second-order	$\mathcal{O}(q^2 \cdot \mathcal{F}_B(m, d))$	$\mathcal{O}(q^2 \cdot \mathcal{F}'_B(d))$	Ranking loss
Random $k$ -Labelsets	Transformation to $n$ multi-class classifiers	High-order	$\mathcal{O}(n \cdot \mathcal{F}_M(m, d, 2^k))$	$\mathcal{O}(n \cdot \mathcal{F}'_M(d, 2^k))$	Subset accuracy
ML- $k$ NN	Adaptation of $k$ -nearest neighbors via MAP	First-order	$\mathcal{O}(m^2 d + q m k)$	$\mathcal{O}(m d + q k)$	Hamming loss
ML-DT	Adaptation of decision trees via multi-label IG	First-order	$\mathcal{O}(m d q)$	$\mathcal{O}(m q)$	Hamming loss
Rank-SVM	Adaptation of SVM / max-margin to label pairs	Second-order	$\mathcal{O}(\mathcal{F}_{\text{QP}}(d q + m q^2, m q^2))$	$\mathcal{O}(d q)$	Ranking loss
BP-MLL	Adaptation of neural networks via ranking error	Second-order	$\mathcal{O}(s(d+q)m N + q^2(q+m))$	$\mathcal{O}(s(d+q))$	Ranking loss
CML	Adaptation of conditional random fields (CRF)	Second-order	$\mathcal{O}(\mathcal{F}_{\text{UNC}}(d q + q^2, m))$	$\mathcal{O}((d q + q^2) 2^q)$	Subset accuracy
MLLS	Adaptation of spectral / shared subspace learning	High-order	$\mathcal{O}(d m^2 + r q^2 + d r^2)$	$\mathcal{O}(d q)$	Hamming loss

Key observations:

First-order methods scale linearly with $q$ but do not exploit label dependencies.
Second-order methods specifically optimize ranking loss or pairwise constraints, but scale quadratically with $q$ .
High-order methods achieve strong predictive completeness and capture arbitrary dependencies, but have higher training or inference overhead (e.g., CML has exponential inference cost in $q$ unless pruned, whereas RAkEL controls complexity via fixed labelset size $k$ ).
Appending predicted labels as features (Stacked Aggregation, Classifier Chains) provides substantial benefits when $q$ is large relative to $d$ , but diminishes in efficacy when $d \gg q$ .

Coverage note — Extended topics surveyed qualitatively in Section IV (including weak/noisy labels, semi-supervised multi-label learning, active learning, and feature selection/dimensionality reduction) were omitted as they summarize auxiliary literature without introducing self-contained algorithmic or theoretical contributions beyond the 12 core algorithms detailed above.

References

1.B.-K. Bao, B. Ni, Y. Mu, and S. Yan, —Efficient region-aware large graph construction towards scalable multi-label propagation,— Pattern Recognition, vol. 44, no. 3, pp. 598–606, 2011.
2.Z. Barutcuoglu, R. E. Schapire, and O. G. Troyanskaya, —Hierarchical multi-label prediction of gene function,— Bioinformatics, vol. 22, no. 7, pp. 830–836, 2006.
3.A. L. Berger, V. J. Della Pietra, and S. A. Della Pietra, —A maximum entropy approach to natural language processing,— Computational Linguistics, vol. 22, no. 1, pp. 39–71, 1996.
4.W. Bi and J. T. Kwok, —Multi-label classification on tree- and DAG-structured hierarchies,— in Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, 2011, pp. 17–24.
5.C. Bielza, G. Li, and P. Larraqaga, —Multi-dimensional classification with Bayesian networks,— International Journal of Approximate Reasoning, vol. 52, no. 6, pp. 705–727, 2011.
6.H. Borchani, C. Bielza, C. Toro, and P. Larraqaga, —Predicting human immunodeficiency virus type 1 inhibitors using multi-dimensional Bayesian network classifiers,— Artificial Intelligence in Medicine, in press.
7.M. R. Boutell, J. Luo, X. Shen, and C. M. Brown, —Learning multi-label scene classification,— Pattern Recognition, vol. 37, no. 9, pp. 1757–1771, 2004.
8.K. Brinker, —On active learning in multi-label classification,— in Proceedings of the 29th Annual Conference of the German Classification Society, Magdeburg, Germany, 2005, pp. 206–213.
9.K. Brinker, J. F urnkranz, and E. Hullermeier, —A unified model for multilabel classification and ranking,— in Proceedings of the 17th European Conference on Artificial Intelligence, Riva del Garda, Italy, 2006, pp. 489–493.
10.K. Brinker and E. Hullermeier, —Case-based multilabel ranking,— in Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007, pp. 702–707.
11.S. S. Bucak, R. Jin, and A. K. Jain, —Multi-label multiple kernel learning by stochastic approximation: Application to visual object recognition,— in Advances in Neural Information Processing Systems 23, J. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, Eds. Cambridge, MA: MIT Press, 2010, pp. 325–333.
12.R. H. Byrd, J. Nocedal, and R. B. Schnabel, —Representations of quasi-newton matrices and their use in limited memory methods,— Mathematical Programming, vol. 63, no. 1-3, pp. 129–156, 1994.
13.R. S. Cabral, F. De la Torre, J. P. Costeira, and A. Bernardino, —Matrix completion for multi-label image classification,— in Advances in Neural Information Processing Systems 24, J. Shawe-Taylor, R. S. Zemel, P. Bartlett, F. C. N. Pereira, and K. Q. Weinberger, Eds. Cambridge, MA: MIT Press, 2011, pp. 190–198.
14.L. Cai and T. Hofmann, —Hierarchical document categorization with support vector machines,— in Proceedings of the 13th ACM International Conference on Information and Knowledge Management, Washington, D.C., 2004, pp. 78–87.
15.R. Caruana, —Multitask learning,— Machine Learning, vol. 28, no. 1, pp. 41–75, 1997.
16.R. Caruana, A. Niculescu-Mizil, G. Crew, and A. Ksikes, —Ensemble selection from libraries of models,— in Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004.
17.N. Cesa-Bianchi, M. Re, and G. Valentini, —Synergy of multi-label hierarchical ensembles, data fusion, and cost-sensitive methods for gene functional inference,— Machine Learning, vol. 88, no. 1-2, pp. 209–241, 2012.
18.C.-C. Chang and C.-J. Lin, —LIBSVM: A library for support vector machines,— ACM Transactions on Intelligent Systems and Technology, vol. 2, no. 3, 2011, Article 27, Software available at http://www.csie.ntu.edu.tw/ʘcjlin/libsvm.
19.F. Chang and C.-C. Liu, —Solving large-scale multi-label svm problems with a tree decomposition approach,— in Poster Session of the 3rd Asian Conference on Machine Learning, Taoyuan, Taiwan, 2011.
20.G. Chen, Y. Song, F. Wang, and C. Zhang, —Semi-supervised multi-label learning by solving a Sylvester equation,— in Proceedings of the 8th SIAM International Conference on Data Mining, Atlanta, GA, 2008, pp. 410–419.
21.W. Cheng, K. Dembczynski, and E. Hullermeier, —Graded multilabel classification: The ordinal case,— in Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010, pp. 223–230.
22.W. Cheng and E. Hullermeier, —Combining instance-based learning and logistic regression for multilabel classification,— Machine Learning, vol. 76, no. 2-3, pp. 211–225, 2009.
23.——, —A simple instance-based approach to multilabel classification using the Mallows model,— in Working Notes of the First International Workshop on Learning from Multi-Label Data, Bled, Slovenia, 2009, pp. 28–38.
24.T.-H. Chiang, H.-Y. Lo, and S.-D. Lin, —A ranking-based KNN approach for multi-label classification,— in Proceedings of the 4th Asian Conference on Machine Learning, Singapore, 2012, pp. 81–96.
25.A. Clare and R. D. King, —Knowledge discovery in multi-label phenotype data,— in Lecture Notes in Computer Science 2168, L. De Raedt and A. Siebes, Eds. Berlin: Springer, 2001, pp. 42–53.
26.D. Cohn, L. Atlas, and R. Ladner, —Improved generalization with active learning,— Machine Learning, vol. 15, no. 2, pp. 201–221, 1994.
27.F. D. Comite, R. Gilleron, and M. Tommasi, —Learning multi-label altenating decision tree from texts and data,— in Lecture Notes in Computer Science 2734, P. Perner and A. Rosenfeld, Eds. Berlin: Springer, 2003, pp. 35–49.
28.T. Cour, B. Sapp, and B. Taskar, —Learning from partial labels,— Journal of Machine Learning Research, vol. 12, no. May, pp. 1501–1536, 2011.
29.A. de Carvalho and A. A. Freitas, —A tutorial on multi-label classification techniques,— in Studies in Computational Intelligence 205, A. Abraham, A. E. Hassanien, and V. Snasel, Eds. Berlin: Springer, 2009, pp. 177–195.
30.A. F. De Souza, F. Pedroni, E. Oliveira, P. M. Ciarelli, W. F. Henrique, L. Veronese, and C. Badue, —Automated multilabel text categorization with VG-RAM weightless neural networks,— Neurocomputing, vol. 72, no. 10-12, pp. 2209–2217, 2009.
31.P. R. de Waal and L. C. van der Gaag, —Inference and learning in multi-dimensional Bayesian network classifiers,— in Lecture Notes in Artificial Intelligence 4724, K. Mellouli, Ed. Berlin: Springer, 2007, pp. 501–511.
32.O. Dekel and O. Shamir, —Multiclass-multilabel classification with more classes than examples,— in Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, Sardinia, Italy, 2010, pp. 137–144.
33.V. Delcroix, M.-A. Maalej, and S. Piechowiak, —Bayesian networks versus other probabilistic models for the multiple diagnosis of large devices,— International Journal on Artificial Intelligence Tools, vol. 16, no. 3, pp. 417–433, 2007.
34.K. Dembczynski, W. Cheng, and E. Hullermeier, —Bayes optimal multilabel classification via probabilistic classifier chains,— in Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010, pp. 279–286.
35.K. Dembczynski, W. Kotłowski, and E. Hullermeier, —Consistent multilabel ranking through univariate loss minization,— in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, UK, 2012, pp. 1319–1326.
36.K. Dembczynski, W. Waegeman, W. Cheng, and E. Hullermeier, —Regret analysis for performance metrics in multi-label classification: The case of hamming loss and subset zero-one loss,— in Lecture Notes in Artificial Intelligence 6321, J. Balcazar, F. Bonchi, A. Gionis, and M. Sebag, Eds. Berlin: Springer, 2010, pp. 280–295.
37.——, —On label dependence and loss minimization in multi-label classification,— Machine Learning, vol. 88, no. 1-2, pp. 5–45, 2012.
38.T. G. Dietterich, —Ensemble methods in machine learning,— in Proceedings of the 1st International Workshop on Multiple Classifier Systems, Cagliari, Italy, 2000, pp. 1–15.
39.T. G. Dietterich, R. H. Lathrop, and T. Lozano-Perez, —Solving the multiple-instance problem with axis-parallel rectangles,— Artificial Intelligence, vol. 89, no. 1-2, pp. 31–71, 1997.
40.G. Doquire and M. Verleysen, —Feature selection for multi-label classification problems,— in Lecture Notes in Computer Science 6691, J. Cabestany, I. Rojas, and G. Joya, Eds. Berlin: Springer, 2011, pp. 9–16.
41.A. Elisseeff and J. Weston, —Kernel methods for multi-labelled classification and categorical regression problems,— BIOwulf Technologies, Tech. Rep., 2001.
42.——, —A kernel method for multi-labelled classification,— in Advances in Neural Information Processing Systems 14, T. G. Dietterich, S. Becker, and Z. Ghahramani, Eds. Cambridge, MA: MIT Press, 2002, pp. 681–687.
43.C. Elkan and K. Noto, —Learning classifiers from only positive and unlabeled data,— in Proceedings of the 14th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Las Vegas, NV, 2008, pp. 213–220.
44.A. Esuli and F. Sebastiani, —Active learning strategies for multi-label text categorization,— in Lecture Notes in Computer Science 5478, M. Boughanem, C. Berrut, J. Mothe, and C. Soule-Dupuy, Eds. Berlin: Springer, 2009, pp. 102–113.
45.R.-E. Fan and C.-J. Lin, —A study on threshold selection for multi-label classification,— National Taiwan University, Tech. Rep., 2007.
46.C. S. Ferng and H. T. Lin, —Multi-label classification with error-correcting codes,— in Proceedings of the 3rd Asian Conference on Machine Learning, Taoyuan, Taiwan, 2011, pp. 281–295.
47.E. Frank and M. Hall, —A simple approach to ordinal classification,— in Lecture Notes in Computer Science 2167, L. De Raedt and P. Flach, Eds. Berlin: Springer, 2001, pp. 145–156.
48.Y. Freund and R. E. Schapire, —A decision-theoretic generalization of on-line learning and an application to boosting,— Journal of Computer and System Sciences, vol. 55, no. 1, pp. 119–139, 1997.
49.J. F urnkranz, E. Hullermeier, E. Loza Mencıa, and K. Brinker, —Multilabel classification via calibrated label ranking,— Machine Learning, vol. 73, no. 2, pp. 133–153, 2008.
50.M. M. Gaber, A. Zaslavsky, and S. Krishnaswamy, —A survey of classification methods in data streams,— in Data Streams: Models and Algorithms, C. C. Aggarwal, Ed. Berlin: Springer, 2007, pp. 39–59.
51.S. Gao, W. Wu, C.-H. Lee, and T.-S. Chua, —A MFoM learning approach to robust multiclass multi-label text categorization,— in Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004.
52.W. Gao and Z.-H. Zhou, —On the consistency of multi-label learning,— in Proceedings of the 24th Annual Conference on Learning Theory, Budapest, Hungary, 2011, pp. 341–358.
53.N. Ghamrawi and A. McCallum, —Collective multi-label classification,— in Proceedings of the 14th ACM International Conference on Information and Knowledge Management, Bremen, Germany, 2005, pp. 195–200.
54.D. Gjorgjevikj and G. Madjarov, —Two stage classifier chain architecture for efficient pair-wise multi-label learning,— in Proceedings of the 21st IEEE International Workshop on Machine Learning for Signal Processing, Beijing, China, 2011, pp. 1–6.
55.S. Godbole and S. Sarawagi, —Discriminative methods for multi-labeled classification,— in Lecture Notes in Artificial Intelligence 3056, H. Dai, R. Srikant, and C. Zhang, Eds. Berlin: Springer, 2004, pp. 22–30.
56.K. Gold and A. Petrosino, —Using information gain to build meaningful decision forests for multilabel classification,— in Proceedings of the 9th IEEE International Conference on Development and Learning, Ann Arbor, MI, 2010, pp. 58–63.
57.G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed. Baltimore, MD: Johns Hopkins University Press, 1996.
58.S. Gopal and Y. Yang, —Multilabel classification with meta-level features,— in Proceedings of the 33rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Geneva, Switzerland, 2010, pp. 315–322.
59.R. Grodzicki, J. Mandziuk, and L. Wang, —Improved multilabel classification with neural networks,— in Lecture Notes in Computer Science 5199, G. Rudolph, T. Jansen, S. Lucas, C. Poloni, and N. Beume, Eds. Berlin: Springer, 2008, pp. 409–416.
60.Q. Gu, Z. Li, and J. Han, —Correlated multi-label feature selection,— in Proceedings of the 20th ACM Conference on Information and Knowledge Management, Glasgow, UK, 2011, pp. 1087–1096.
61.Y. Guo and S. Gu, —Multi-label classification using conditional dependency networks,— in Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, 2011, pp. 1300–1305.
62.Y. Guo and D. Schuurmans, —Adaptive large margin training for multilabel classification,— in Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, CA, 2011, pp. 374–379.
63.M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten, —The WEKA data mining software: An update,— SIGKDD Explorations, vol. 11, no. 1, pp. 10–18, 2009.
64.J. A. Hanley and B. J. McNeil, —The meaning and use of the area under a receiver operating characteristic (ROC) curve,— Radiology, vol. 143, no. 1, pp. 29–36, 1982.
65.B. Hariharan, S. V. N. Vishwanathan, and M. Varma, —Efficient max-margin multi-label classification with applications to zero-shot learning,— Machine Learning, vol. 88, no. 1-2, pp. 127–155, 2012.
66.B. Hariharan, L. Zelnik-Manor, S. V. N. Vishwanathan, and M. Varma, —Large scale max-margin multi-label classification with priors,— in Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010, pp. 423–430.
67.S. Haykin, Neural Networks: A Comprehensive Foundation, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1999.
68.J. He, H. Gu, and Z. Wang, —Bayesian multi-instance multi-label learning using Gaussian process prior,— Machine Learning, vol. 88, no. 1-2, pp. 273–295, 2012.
69.D. Hsu, S. Kakade, J. Langford, and T. Zhang, —Multi-label prediction via compressed sensing,— in Advances in Neural Information Processing Systems 22, Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, Eds. Cambridge, MA: MIT Press, 2009, pp. 772–780.
70.K.-W. Huang and Z. Li, —A multilabel text classification algorithm for labeling risk factors in SEC form 10-K,— ACM Transactions on Management Information Systems, vol. 2, no. 3, 2011, Article 18.
71.S.-J. Huang, Y. Yu, and Z.-H. Zhou, —Multi-label hypothesis reuse,— in Proceedings of the 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Beijing, China, 2012, pp. 525–533.
72.S.-J. Huang and Z.-H. Zhou, —Multi-label learning by exploiting label correlations locally,— in Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto, Canada, 2012, pp. 949–955.
73.C.-W. Hung and H.-T. Lin, —Multi-label active learning with auxiliary learner,— in Proceedings of the 3rd Asian Conference on Machine Learning, Taoyuan, Taiwan, 2011, pp. 315–330.
74.M. Ioannou, G. Sakkas, G. Tsoumakas, and I. Vlahavas, —Obtaining bipartition from score vectors for multi-label classification,— in Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, Arras, France, 2010, pp. 409–416.
75.E. T. Jaynes, —Information theory and statistical mechanics,— Physical Review, vol. 106, no. 4, pp. 620–630, 1957.
76.S. Ji, L. Sun, R. Jin, and J. Ye, —Multi-label multiple kernel learning,— in Advances in Neural Information Processing Systems 21, D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, Eds. Cambridge, MA: MIT Press, 2009, pp. 777–784.
77.S. Ji, L. Tang, S. Yu, and J. Ye, —Extracting shared subspace for multi-label classification,— in Proceedings of the 14th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Las Vegas, NV, 2008, pp. 381–389.
78.——, —A shared-subspace learning framework for multi-label classification,— ACM Transactions on Knowledge Discovery from Data, vol. 4, no. 2, 2010, Article 8.
79.S. Ji and J. Ye, —Linear dimensionality reduction for multi-label classification,— in Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, TX, 2009, pp. 1077–1082.
80.A. Jiang, C. Wang, and Y. Zhu, —Calibrated rank-svm for multi-label image categorization,— in Proceedings of the International Joint Conference on Neural Networks, Hong Kong, 2008, pp. 1450–1455.
81.R. Jin and Z. Ghahramani, —Learning with multiple labels,— in Advances in Neural Information Processing Systems 15, S. Becker, S. Thrun, and K. Obermayer, Eds. Cambridge, MA: MIT Press, 2003, pp. 897–904.
82.F. Kang, R. Jin, and R. Sukthankar, —Correlated label propagation with application to multi-label learning,— in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, NY, 2006, pp. 1719–1726.
83.I. Katakis, G. Tsoumakas, and I. Vlahavas, —Multilabel text classification for automated tag suggestion,— in Proceedings of the ECML PKDD 2008 Discovery Challenge, Antwerp, Belgium, 2008, pp. 75–83.
84.H. Kazawa, T. Izumitani, H. Taira, and E. Maeda, —Maximal margin labeling for multi-topic text categorization,— in Advances in Neural Information Processing Systems 17, L. K. Saul, Y. Weiss, and L. Bottou, Eds. Cambridge, MA: MIT Press, 2005, pp. 649–656.
85.D. Kocev, C. Vens, J. Struyf, and S. Dɖzeroski, —Ensembles of multi-objective decision trees,— in Proceedings of the 18th European Conference on Machine Learning, Warsaw, Poland, 2007, pp. 624–631.
86.X. Kong, M. Ng, and Z.-H. Zhou, —Transductive multi-label learning via label set propagation,— IEEE Transactions on Knowledge and Data Engineering, 2012 (in press).
87.X. Kong and P. S. Yu, —Multi-label feature selection for graph classification,— in Proceedings of the 10th IEEE International Conference on Data Mining, Sydney, Australia, 2010, pp. 274–283.
88.——, —An ensemble-based approach to fast classification of multi-label data streams,— in Proceedings of the 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing, Orlando, FL, 2011, pp. 95–104.
89.——, —gMLC: A multi-label feature selection framework for graph classification,— Knowledge and Information Systems, vol. 31, no. 2, pp. 281–305, 2012.
90.W. Kotłowski, K. Dembczynski, and E. Hullermeier, —Bipartite ranking through minimization of univariate loss,— in Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, 2011, pp. 1113–1120.
91.G. Lastra, O. Luaces, J. R. Quevedo, and A. Bahamonde, —Graphical feature selection for multilabel classification tasks,— in Lecture Notes in Computer Science 7014, J. Gama, E. Bradley, and J. Hollmen, Eds. Berlin: Springer, 2011, pp. 246–257.
92.M. Lee and C. H. Park, —On applying dimension reduction for multi-labeled problems,— in Lecture Notes in Artificial Intelligence 4571, P. Perner, Ed. Berlin: Springer, 2007, pp. 131–143.
93.T. Li, S. Yan, T. Mei, X.-S. Hua, and I.-S. Kweon, —Image decomposition with multilabel context: Algorithms and applications,— IEEE Transactions on Image Processing, vol. 8, no. 20, pp. 2301–2314, 2011.
94.X. Li, L. Wang, and E. Sung, —Multi-label svm active learning for image classification,— in Proceedings of the 2004 International Conference on Image Processing, Singapore, 2004, pp. 2207–2210.
95.Y. Liu, R. Jin, and L. Yang, —Semi-supervised multi-label learning by constrained non-negative matrix factorization,— in Proceedings of the 21st AAAI Conference on Artificial Intelligence, Boston, MA, 2006, pp. 421–426.
96.H.-Y. Lo, J.-C. Wang, H.-M. Wang, and S.-D. Lin, —Cost-sensitive multi-label learning for audio tag annotation and retrieval,— IEEE Transactions on Multimedia, vol. 13, no. 3, pp. 518–529, 2011.
97.E. Loza Mencıa, —Multilabel classification in parallel tasks,— in Working Notes of the Second International Workshop on Learning from Multi-Label Data, Haifa, Israel, 2010, pp. 20–36.
98.E. Loza Mencıa and J. F urnkranz, —Efficient pairwise multilabel classification for large-scale problems in the legal domain,— in Lecture Notes in Artificial Intelligence 5212, W. Daelemans, B. Goethals, and K. Morik, Eds. Berlin: Springer, 2008, pp. 50–65.
99.——, —Pairwise learning of multilabel classifications with perceptrons,— in Proceedings of the International Joint Conference on Neural Networks, Hong Kong, 2008, pp. 2899–2906.
100.E. Loza Mencıa, S.-H. Park, and J. F urnkranz, —Efficient voting prediction for pairwise multilabel classification,— Neurocomputing, vol. 73, no. 7-9, pp. 1164–1176, 2010.
101.G. Madjarov, D. Gjorgjevikj, and T. Delev, —Efficient two stage voting architecture for pairwise multi-label classification,— in Lecture Notes in Computer Science 6464, J. Li, Ed. Berlin: Springer, 2011, pp. 164–173.
102.G. Madjarov, D. Gjorgjevikj, and S. Dɖzeroski, —Two stage architecture for multi-label learning,— Pattern Recognition, vol. 45, no. 3, pp. 1019–1034, 2012.
103.G. Madjarov, D. Kocev, D. Gjorgjevikj, and S. Dɖzeroski, —An extensive experimental comparison of methods for multilabel learning,— Pattern Recognition, vol. 45, no. 9, pp. 3084–3104, 2012.
104.A. McCallum, —Multi-label text classification with a mixture model trained by EM,— in Working Notes of the AAAI’99 Workshop on Text Learning, Orlando, FL, 1999.
105.E. Montaqes, J. R. Quevedo, and J. J. del Coz, —Aggregating independent and dependent models to learn multi-label classifiers,— in Lecture Notes in Artificial Intelligence 6912, D. Gunopulos, T. Hofmann, D. Malerba, and M. Vazirgiannis, Eds. Berlin: Springer, 2011, pp. 484–500.
106.K. Nigam, J. Lafferty, and A. McCallum, —Using maximum entropy for text classification,— in Working Notes of the IJCAI’99 Workshop on Machine Learning for Information Filtering, Stockholm, Sweden, 1999, pp. 61–67.
107.K. Ozonat and D. Young, —Towards a universal marketplace over the web: Statistical multi-label classification of service provider forms with simulated annealing,— in Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 1295–1303.
108.F. Pachet and P. Roy, —Improving multilabel analysis of music titles: A large-scale validation of the correction approach,— IEEE Transactions on Audio, Speech, and Language Processing, vol. 17, no. 2, pp. 335–343, 2009.
109.C. H. Park and M. Lee, —On applying linear discriminant analysis for multi-labeled problems,— Pattern Recognition Letters, vol. 29, no. 7, pp. 878–887, 2008.
110.J. Petterson and T. Caetano, —Reverse multi-label learning,— in Advances in Neural Information Processing Systems 23, J. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, Eds. Cambridge, MA: MIT Press, 2010, pp. 1912–1920.
111.——, —Submodular multi-label learning,— in Advances in Neural Information Processing Systems 24, J. Shawe-Taylor, R. S. Zemel, P. Bartlett, F. C. N. Pereira, and K. Q. Weinberger, Eds. Cambridge, MA: MIT Press, 2011, pp. 1512–1520.
112.G.-J. Qi, X.-S. Hua, Y. Rui, J. Tang, T. Mei, and H.-J. Zhang, —Correlative multi-label video annotation,— in Proceedings of the 15th ACM International Conference on Multimedia, Augsburg, Germany, 2007, pp. 17–26.
113.G.-J. Qi, X.-S. Hua, Y. Rui, J. Tang, and H.-J. Zhang, —Two-dimensional multilabel active learning with an efficient online adaptation model for image classification,— IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 10, pp. 1880–1897, 2009.
114.B. Qian and I. Davidson, —Semi-supervised dimension reduction for multi-label classification,— in Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, GA, 2010, pp. 569–574.
115.W. Qu, Y. Zhang, J. Zhu, and Q. Qiu, —Mining multi-label concept-drifting data streams using dynamic classifier ensemble,— in Lecture Notes in Artificial Intelligence 5828, Z.-H. Zhou and T. Washio, Eds. Berlin: Springer, 2009, pp. 308–321.
116.J. R. Quevedo, O. Luaces, and A. Bahamonde, —Multilabel classifiers with a probabilistic thresholding strategy,— Pattern Recognition, vol. 45, no. 2, pp. 876–883, 2012.
117.J. R. Quinlan, C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann, 1993.
118.R. Rak, L. Kurgan, and M. Reformat, —Multi-label associative classification of medical documents from medline,— in Proceedings of the 4th International Conference on Machine Learning and Applications, Los Angeles, CA, 2005, pp. 177–186.
119.J. Read, —A pruned problem transformation method for multi-label classification,— in Proceedings of the 2008 New Zealand Computer Science Research Student Conference, Christchurch, New Zealand, 2008, pp. 143–150.
120.J. Read, A. Bifet, G. Holmes, and B. Pfahringer, —Scalable and efficient multi-label classification for evolving data streams,— Machine Learning, vol. 88, no. 1-2, pp. 243–272, 2012.
121.J. Read, B. Pfahringer, and G. Holmes, —Multi-label classification using ensembles of pruned sets,— in Proceeding of the 8th IEEE International Conference on Data Mining, Pisa, Italy, 2008, pp. 995–1000.
122.J. Read, B. Pfahringer, G. Holmes, and E. Frank, —Classifier chains for multi-label classification,— in Lecture Notes in Artificial Intelligence 5782, W. Buntine, M. Grobelnik, and J. Shawe-Taylor, Eds. Berlin: Springer, 2009, pp. 254–269.
123.——, —Classifier chains for multi-label classification,— Machine Learning, vol. 85, no. 3, pp. 333–359, 2011.
124.J. Rousu, C. Saunders, S. Szedmak, and J. Shawe-Taylor, —Learning hierarchical multi-category text classifcation models,— in Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany, 2005, pp. 774–751.
125.——, —Kernel-based learning of hierarchical multilabel classification models,— Journal of Machine Learning Research, vol. 7, no. Jul, pp. 1601–1626, 2006.
126.T. N. Rubin, A. Chambers, P. Smyth, and M. Steyvers, —Statistical topic models for multi-label document classification,— Machine Learning, vol. 88, no. 1-2, pp. 157–208, 2012.
127.C. Sanden and J. Z. Zhang, —Enhancing multi-label music genre classification through ensemble techniques,— in Proceedings of the 34th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Beijing, China, 2011, pp. 705–714.
128.E. P. Sapozhnikova, —ART-based neural networks for multi-label classification,— in Lecture Notes in Computer Science 5772, N. Adams, C. Robardet, and A. Siebes, Eds. Berlin: Springer, 2009, pp. 167–177.
129.R. E. Schapire and Y. Singer, —Boostexter: a boosting-based system for text categorization,— Machine Learning, vol. 39, no. 2/3, pp. 135–168, 2000.
130.K. Sechidis, G. Tsoumakas, and I. Vlahavas, —On the stratification of multi-label data,— in Lecture Notes in Artificial Intelligence 6913, D. Gunopulos, T. Hofmann, D. Malerba, and M. Vazirgiannis, Eds. Berlin: Springer, 2011, pp. 145–158.
131.C. Shi, X. Kong, P. S. Yu, and B. Wang, —Multi-label ensemble learning,— in Lecture Notes in Artificial Intelligence 6913, D. Gunopulos, T. Hofmann, D. Malerba, and M. Vazirgiannis, Eds. Berlin: Springer, 2011, pp. 223–239.
132.C. N. Silla and A. A. Freitas, —A survey of hierarchical classification across different application domains,— Data Mining and Knowledge Discovery, vol. 22, no. 1-2, pp. 31–72, 2011.
133.C. G. M. Snoek, M. Worring, J. C. van Gemert, J.-M. Geusebroek, and A. W. M. Smeulders, —The challenge problem for automated detection of 101 semantic concepts in multimedia,— in Proceedings of the 14th Annual ACM International Conference on Multimedia, Santa Barbara, CA, USA, 2006, pp. 421–430.
134.Y. Song, L. Zhang, and L. C. Giles, —A sparse gaussian processes classification framework for fast tag suggestions,— in Proceeding of the 17th ACM Conference on Information and Knowledge Management, Napa Valley, CA, 2008, pp. 93–102.
135.E. Spyromitros-Xioufis, M. Spiliopoulou, G. Tsoumakas, and I. Vlahavas, —Dealing with concept drift and class imbalance in multi-label stream classification,— in Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, 2011, pp. 1583–1588.
136.E. Spyromitros-Xioufis, G. Tsoumakas, and I. Vlahavas, —An empirical study of lazy multilabel classification algorithms,— in Proceedings of the 5th Hellenic Conference on Artificial Intelligence, Syros, Greece, 2008, pp. 401–406.
137.——, —Multi-label learning approaches for music instrument recognition,— in Lecture Notes in Artificial Intelligence 6804, M. Kryszkiewicz, H. Rybinski, A. Skowron, and Z. W. Ras, Eds. Berlin: Springer, 2011, pp. 734–743.
138.A. P. Streich and J. M. Buhmann, —Classification of multi-labeled data: A generative approach,— in Lecture Notes in Artificial Intelligence 5212, W. Daelemans, B. Goethals, and K. Morik, Eds. Berlin: Springer, 2008, pp. 390–405.
139.L. Sun, S. Ji, and J. Ye, —Hypergraph spectral learning for multi-label classification,— in Proceedings of the 14th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Las Vegas, NV, 2008, pp. 668–676.
140.——, —Canonical correlation analysis for multilabel classification: A least-squares formulation, extensions, and analysis,— IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, pp. 194–200, 2011.
141.Y.-Y. Sun, Y. Zhang, and Z.-H. Zhou, —Multi-label learning with weak label,— in Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, GA, 2010, pp. 593–598.
142.M. A. Tahir, J. Kittler, K. Mikolajczyk, and F. Yan, —Improving multilabel classification performance by using ensemble of multi-label classifiers,— in Lecture Notes in Computer Science 5997, N. El Gayar, J. Kittler, and F. Roli, Eds. Berlin: Springer, 2010, pp. 11–21.
143.L. Tang, J. Chen, and J. Ye, —On multiple kernel learning with multiple labels,— in Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, TX, 2009, pp. 1255–1266.
144.L. Tang, S. Rajan, and V. K. Narayanan, —Large scale multi-label classification via metalabeler,— in Proceedings of the 19th International Conference on World Wide Web, Madrid, Spain, 2009, pp. 211–220.
145.L. Tenenboim-Chekina, L. Rokach, and B. Shapira, —Identification of label dependencies for multi-label classification,— in Working Notes of the Second International Workshop on Learning from Multi-Label Data, Haifa, Israel, 2010, pp. 53–60.
146.F. A. Thabtah, P. Cowling, and Y. Peng, —MMAC: A new multi-class, multi-label associative classification approach,— in Proceedings of the 4th IEEE International Conference on Data Mining, Brighton, UK, 2004, pp. 217–224.
147.K. M. Ting and I. H. Witten, —Issues in stacked generalization,— Journal of Artificial Intelligence Research, vol. 10, pp. 271–289, 1999.
148.K. Trohidis, G. Tsoumakas, G. Kalliris, and I. Vlahavas, —Multilabel classification of music into emotions,— in Proceedings of the 9th International Conference on Music Information Retrieval, Philadephia, PA, 2008, pp. 325–330.
149.I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun, —Support vector machine learning for interdependent and structured output spaces,— in Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004.
150.——, —Large margin methods for structured and interdependent output variables,— Journal of Machine Learning Research, vol. 6, no. Sep, pp. 1453–1484, 2005.
151.G. Tsoumakas, A. Dimou, E. Spyromitros, V. Mezaris, I. Kompatsiaris, and I. Vlahavas, —Correlation-based pruning of stacked binary relevance models for multi-label learning,— in Working Notes of the First International Workshop on Learning from Multi-Label Data, Bled, Slovenia, 2009, pp. 101–116.
152.G. Tsoumakas and I. Katakis, —Multi-label classification: An overview,— International Journal of Data Warehousing and Mining, vol. 3, no. 3, pp. 1–13, 2007.
153.——, —Effective and efficient multilabel classification in domains with large number of labels,— in Working Notes of the ECML PKDD’08 Workshop on Mining Multidimensional Data, Antwerp, Belgium, 2008.
154.G. Tsoumakas, I. Katakis, and I. Vlahavas, —Mining multi-label data,— in Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach, Eds. Berlin: Springer, 2010, pp. 667–686.
155.——, —Random k-labelsets for multi-label classification,— IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 7, pp. 1079–1089, 2011.
156.G. Tsoumakas, E. Spyromitros-Xioufis, J. Vilcek, and I. Vlahavas, —MULAN: A java library for multi-label learning,— Journal of Machine Learning Research, vol. 12, no. Jul, pp. 2411–2414, 2011.
157.G. Tsoumakas and I. Vlahavas, —Random k-labelsets: an ensemble method for multilabel classification,— in Lecture Notes in Artificial Intelligence 4701, J. N. Kok, J. Koronacki, R. L. de Mantaras, S. Matwin, D. Mladeniɖc, and A. Skowron, Eds. Berlin: Springer, 2007, pp. 406–417.
158.G. Tsoumakas, M.-L. Zhang, and Z.-H. Zhou, —Tutorial on learning from multi-label data,— in European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Bled, Slovenia, 2009 [http://www.ecml pkdd2009.net/wp-content/uploads/2009/08/learning-from-multi-label-data.pdf].
159.N. Ueda and K. Saito, —Parametric mixture models for multi-label text,— in Advances in Neural Information Processing Systems 15, S. Becker, S. Thrun, and K. Obermayer, Eds. Cambridge, MA: MIT Press, 2003, pp. 721–728.
160.L. C. van der Gaag and P. R. de Waal, —Multi-dimensional Bayesian network classifiers,— in Proceedings of the 3rd European Workshop in Probabilistic Graphical Models, Prague, Czech Republic, 2006, pp. 107–114.
161.A. Veloso, W. Meira Jr., M. Goncalves, and M. Zaki, —Multi-label lazy associative classification,— in Lecture Notes in Artificial Intelligence 4702, J. N. Kok, J. Koronacki, R. L. de Mantaras, S. Matwin, D. Mladeniɖc, and A. Skowron, Eds. Berlin: Springer, 2007, pp. 605–612.
162.C. Vens, J. Struyf, L. Schietgat, S. Dɖzeroski, and H. Blockeel, —Decision trees for hierarchical multi-label classification,— Machine Learning, vol. 73, no. 2, pp. 185–214, 2008.
163.H. Wang, C. Ding, and H. Huang, —Multi-label classification: Inconsistency and class balanced k-nearest neighbor,— in Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, GA, 2010, pp. 1264–1266.
164.——, —Multi-label linear discriminant analysis,— in Lecture Notes in Computer Science 6316, K. Daniilidis, P. Maragos, and N. Paragios, Eds. Berlin: Springer, 2010, pp. 126–139.
165.H. Wang, H. Huang, and C. Ding, —Image annotation using multi-label correlated Green’s function,— in Proceedings of the 12th International Conference on Computer Vision, Kyoto, Japan, 2009, pp. 2029–2034.
166.——, —Multi-label feature transform for image classifications,— in Lecture Notes in Computer Science 6314, K. Daniilidis, P. Maragos, and N. Paragios, Eds. Berlin: Springer, 2010, pp. 793–806.
167.H. Wang, M. Huang, and X. Zhu, —A generative probabilistic model for multi-label classification,— in Proceedings of the 8th IEEE International Conference on Data Mining, Pisa, Italy, 2008, pp. 628–637.
168.J. Wang, Y. Zhao, X. Wu, and X.-S. Hua, —Transductive multi-label learning for video concept detection,— in Proceedings of the ACM International Conference on Multimedia Information Retrieval, Vancouver, Canada, 2008, pp. 298–304.
169.——, —A transductive multi-label learning approach for video concept detection,— Pattern Recognition, vol. 44, no. 10-11, pp. 2274–2286, 2011.
170.M. Wang, X. Zhou, and T.-S. Chua, —Automatic image annotation via local multi-label classification,— in Proceedings of the 7th ACM International Conference on Image and Video Retrieval, Niagara Falls, Canada, 2008, pp. 17–26.
171.Z. Wang, Y. Hu, and L.-T. Chia, —Multi-label learning by image-to-class distance for scene classification and image annotation,— in Proceedings of the ACM International Conference on Image and Video Retrieval, Xi’an, China, 2010, pp. 105–112.
172.A. Wieczorkowska, P. Synak, and Z. W. Ras, —Multi-label classification of emotions in music,— in Advances in Soft Computing 35, M. A. Klopotek, S. T. Wierzchon, and K. Trojanowski, Eds. Berlin: Springer, 2006, pp. 307–315.
173.D. H. Wolpert, —Stacked generalization,— Neural Networks, vol. 5, no. 2, pp. 241–259, 1992.
174.F. Wu, Y. Han, Q. Tian, and Y. Zhuang, —Multi-label boosting for image annotation by structural grouping sparsity,— in Proceedings of the 18th ACM International Conference on Multimedia, Firenze, Italy, 2010, pp. 15–24.
175.S. Xiang, S. Chen, and L. Qiao, —Sparse representation: Extract adaptive neighborhood for multilabel classification,— in Lecture Notes in Artificial Intelligence 6230, B.-T. Zhang and M.-A. Orgun, Eds. Berlin: Springer, 2010, pp. 304–314.
176.R. Yan, J. Teɖsic, and J. R. Smith, —Model-shared subspace boosting for multi-label classification,— in Proceedings of the 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, San Jose, CA, 2007, pp. 834–843.
177.B. Yang, J.-T. Sun, T. Wang, and Z. Chen, —Effective multi-label active learning for text categorization,— in Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 917–925.
178.Y. Yang and S. Gopal, —Multilabel classification with meta-level features in a learning-to-rank framework,— Machine Learning, vol. 88, no. 1-2, pp. 47–68, 2012.
179.J. Ye, —Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems,— Journal of Machine Learning Research, vol. 6, no. Apr, pp. 483–502, 2005.
180.Z. Younes, F. Abdallah, and T. Denoeux, —An evidence-theoretic k-nearest neighbor rule for multi-label classification,— in Lecture Notes in Artificial Intelligence 5785, L. Godo and A. Pugliese, Eds. Berlin: Springer, 2009, pp. 297–308.
181.Z. Younes, F. Abdallah, T. Denoeux, and H. Snoussi, —A dependent multilabel classification method derived from the k-nearest neighbor rule,— EURASIP Journal on Advances in Signal Processing, 2011, Article 645964.
182.K. Yu, S. Yu, and V. Tresp, —Multi-label informed latent semantic indexing,— in Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Salvador, Brazil, 2005, pp. 258–265.
183.J. H. Zaragoza, L. E. Sucar, E. F. Morales, C. Bielza, and P. Larraqaga, —Bayesian chain classifiers for multidimensional classification,— in Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, 2011, pp. 2192–2197.
184.Z.-J. Zha, T. Mei, J. Wang, Z. Wang, and X.-S. Hua, —Graph-based semi-supervised learning with multi-label,— in Proceedings of the 2008 IEEE International Conference on Multimedia & Expo, Hannover, Germany, 2008, pp. 1321–1324.
185.——, —Graph-based semi-supervised learning with multiple labels,— Journal of Visual Communication and Image Representation, vol. 20, no. 2, pp. 97–103, 2009.
186.M.-L. Zhang, —ML-RBF: RBF neural networks for multi-label learning,— Neural Processing Letters, vol. 29, no. 2, pp. 61–74, 2009.
187.M.-L. Zhang, J. M. Peqa, and V. Robles, —Feature selection for multi-label naive bayes classification,— Information Sciences, vol. 179, no. 19, pp. 3218–3229, 2009.
188.M.-L. Zhang and K. Zhang, —Multi-label learning by exploiting label dependency,— in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington D. C., 2010, pp. 999–1007.
189.M.-L. Zhang and Z.-H. Zhou, —A k-nearest neighbor based algorithm for multi-label classification,— in Proceedings of the 1st IEEE International Conference on Granular Computing, Beijing, China, 2005, pp. 718–721.
190.——, —Multilabel neural networks with applications to functional genomics and text categorization,— IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 10, pp. 1338–1351, 2006.
191.——, —ML-kNN: A lazy learning approach to multi-label learning,— Pattern Recognition, vol. 40, no. 7, pp. 2038–2048, 2007.
192.——, —Multi-label learning by instance differentiation,— in Proceedings of the 22nd AAAI Conference on Artificial Intelligence, Vancouver, Canada, 2007, pp. 669–674.
193.X. Zhang, Q. Yuan, S. Zhao, W. Fan, W. Zheng, and Z. Wang, —Multi-label classification without the multi-label cost,— in Proceedings of the 10th SIAM International Conference on Data Mining, Columbus, OH, 2010, pp. 778–789.
194.Y. Zhang and J. Schneider, —Multi-label output codes using canonical correlation analysis,— in Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, FL, 2011, pp. 873–882.
195.——, —Maximum margin output coding,— in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, UK, 2012, pp. 1575–1582.
196.Y. Zhang and Z.-H. Zhou, —Multi-label dimensionality reduction via dependency maximization,— in Proceedings of the 23rd AAAI Conference on Artificial Intelligence, Chicago, IL, 2008, pp. 1503–1505.
197.——, —Multi-label dimensionality reduction via dependency maximization,— ACM Transactions on Knowledge Discovery from Data, vol. 4, no. 3, 2010, Article 14.
198.T. Zhou and D. Tao, —Multi-label subspace ensemble,— in Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, Canary Islands, Spain, 2012, pp. 1444–1452.
199.T. Zhou, D. Tao, and X. Wu, —Compressed labeling on distilled labelsets for multi-label learning,— Machine Learning, vol. 88, no. 1-2, pp. 69–126, 2012.
200.Z.-H. Zhou, Ensemble Methods: Foundations and Algorithms. Boca Raton, FL: Chapman & Hall/CRC, 2012.
201.Z.-H. Zhou and M.-L. Zhang, —Multi-instance multi-label learning with application to scene classification,— in Advances in Neural Information Processing Systems 19, B. Scholkopf, J. Platt, and T. Hoffman, Eds. Cambridge, MA: MIT Press, 2007, pp. 1609–1616.
202.Z.-H. Zhou, M.-L. Zhang, S.-J. Huang, and Y.-F. Li, —Multi-instance multi-label learning,— Artificial Intelligence, vol. 176, no. 1, pp. 2291–2320, 2012.
203.S. Zhu, X. Ji, W. Xu, and Y. Gong, —Multi-labelled classification using maximum entropy method,— in Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Salvador, Brazil, 2005, pp. 274–281.
204.X. Zhu and A. B. Goldberg, —Introduction to semi-supervised learning,— in Synthesis Lectures to Artificial Intelligence and Machine Learning, R. J. Brachman and T. G. Dietterich, Eds. San Francisco, CA: Morgan & Claypool Publishers, 2009, pp. 1–130.

Citation

MLA

Zhang, M.-L., and Z.-H. Zhou. “A Review on Multi-Label Learning Algorithms”. IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 8, 2014, pp. 1819–37, https://doi.org/10.1109/TKDE.2013.39.

APA

Zhang, M.-L., & Zhou, Z.-H. (2014). A Review on Multi-Label Learning Algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8), 1819–1837. https://doi.org/10.1109/TKDE.2013.39

Chicago

Zhang, M.-L., and Z.-H. Zhou. 2014. “A Review on Multi-Label Learning Algorithms”. IEEE Transactions on Knowledge and Data Engineering 26 (8): 1819–37. https://doi.org/10.1109/TKDE.2013.39.

Harvard

Zhang, M.-L. and Zhou, Z.-H. (2014) “A Review on Multi-Label Learning Algorithms”, IEEE Transactions on Knowledge and Data Engineering, 26(8), pp. 1819–1837. Available at: https://doi.org/10.1109/TKDE.2013.39.

Vancouver

1. Zhang M-L, Zhou Z-H (2014) A Review on Multi-Label Learning Algorithms. IEEE Transactions on Knowledge and Data Engineering 26:1819–1837

BibTeX

@article{Zhang_2014, title={A Review on Multi-Label Learning Algorithms}, volume={26}, ISSN={1041-4347}, url={http://dx.doi.org/10.1109/TKDE.2013.39}, DOI={10.1109/tkde.2013.39}, number={8}, journal={IEEE Transactions on Knowledge and Data Engineering}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Zhang, Min-Ling and Zhou, Zhi-Hua}, year={2014}, month=Aug, pages={1819–1837} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

A Review on Multi-Label Learning Algorithms

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Multi-Label Learning Problem Formulation and Data Multi-Labeledness Indicators

Knowl 2 — Taxonomy of Label Correlation Exploitation Orders

Knowl 3 — Example-Based Multi-Label Evaluation Metrics

Knowl 4 — Label-Based Multi-Label Evaluation Metrics

Knowl 5 — Theoretical Consistency and Incompatibility of Multi-Label Loss Functions

Knowl 6 — Threshold Calibration via Stacking Linear Models

Knowl 7 — Binary Relevance and AdaBoost.MH Transformation Methods

Knowl 8 — Classifier Chains (CC) and Ensemble of Classifier Chains (ECC)

Knowl 9 — Calibrated Label Ranking (CLR)

Knowl 10 — Random k-Labelsets (RAkEL)

Knowl 11 — Multi-Label k-Nearest Neighbor (ML-kNN)

Knowl 12 — Multi-Label Decision Tree (ML-DT) with Decomposable Multi-Label Entropy

Knowl 13 — Ranking Support Vector Machine (Rank-SVM)

Knowl 14 — Backpropagation for Multi-Label Learning (BP-MLL)

Knowl 15 — Collective Multi-Label (CML) Classification via Maximum Entropy

Knowl 16 — Multi-Label Least Squares (MLLS) via Shared Subspace Learning

Knowl 17 — Comparative Summary of Representative Multi-Label Learning Algorithms

References

Citation

BibTeX

Access the Paper