Classifier chains for multi-label classification

J. ReadBernhard PfahringerG. HolmesE. Frank

article2009ECML PKDD2,740 citationsTest of Time Award

Proposes classifier chains and ensemble extensions that model label correlations in multi-label classification while retaining the computational efficiency and linear scalability of binary relevance across large datasets.

Listen

Multi-label classification assigns multiple labels to each instance and arises in text categorization, scene analysis, and bioinformatics. The binary relevance method treats each label independently and scales linearly with the number of labels, yet it is widely dismissed because it ignores correlations among labels. More elaborate methods that attempt to capture those correlations incur quadratic or exponential costs and often become intractable once the number of labels or training examples grows large.

The article introduces classifier chains, a problem-transformation technique that retains the linear complexity of binary relevance while propagating label information along an ordered sequence of binary classifiers. Each classifier receives the original features plus the 0/1 predictions of all preceding classifiers in the chain, thereby modeling label dependence at modest extra cost. An ensemble of such chains, each with a random label order and trained on bootstrap samples, further improves robustness; a lightweight variant that randomly subsamples both attributes and instances makes the ensemble practical for very large data.

Extensive experiments on fifteen datasets ranging from a few hundred to more than one hundred thousand examples and up to nearly one thousand labels show that the single-chain method already surpasses binary relevance and related stacking approaches on most accuracy-oriented measures. The full ensemble matches or exceeds the predictive performance of far more complex state-of-the-art algorithms while finishing training and testing in a fraction of the time; on the largest collections only the binary-relevance family completes within reasonable resource limits. Subsampling reduces running time dramatically with negligible loss in accuracy.

These results indicate that carefully designed binary-relevance methods can deliver high accuracy at low cost and therefore deserve renewed consideration for production-scale multi-label tasks. Practitioners facing large label sets or streaming data should therefore prototype an ensemble of classifier chains, optionally with attribute and instance subsampling, before investing in more elaborate correlation-modeling schemes. Further work is warranted on adaptive chain ordering and on threshold calibration when label cardinality differs markedly between training and test distributions.

Universidad Carlos III de Madrid University of Waikato multi-label classification svm classification models Classifier Chain Binary Relevance Ensemble of Classifier Chain

Read et al (2009).pdf

Paper: In Defense of One-Vs-All Classification, Ryan Rifkin et al. (2004). This paper provides foundational empirical justification for one-vs-all binary decomposition, which serves as the core baseline and structural building block that classifier chains directly adapt and extend.
Paper: BoosTexter: A Boosting-based System for Text Categorization, ROBERT E. SCHAPIRE et al. (2000). BoosTexter establishes the formal formulation and benchmark evaluation standards for multi-label text categorization problems addressed by classifier chains.
Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). This work introduces structured output learning to model interdependencies among outputs, providing the theoretical context for modeling label correlations that classifier chains solve with lower computational complexity.
Paper: The Random Subspace Method for Constructing Decision Forests, Tin Kam Ho (1998). Tin Kam Ho introduces feature-subspace randomization in ensemble learning, which directly underlies the random attribute and instance subsampling strategies used in ensembles of classifier chains.
Paper: Random Forests, Leo Breiman (2001). Breiman's bagging and feature-subspace ensemble principles form the methodological foundation for constructing robust ensembles of classifier chains.
Paper: On Combining Classifiers, Josef Kittler et al. (1998). This paper establishes formal Bayesian fusion and voting rules for combining outputs from multiple diverse classifiers, which ensembles of classifier chains leverage during inference.
Paper: Solving Multiclass Learning Problems via Error-Correcting Output Codes, Thomas G. Dietterich et al. (1994). Dietterich and Bakiri present output coding transformations that decompose multi-output problems into binary learners, serving as an important conceptual precursor to chain transformations.

Paper: A Review on Multi-Label Learning Algorithms, Min-Ling Zhang et al. (2014). This comprehensive review places classifier chains within the broader taxonomy of high-order problem-transformation methods and evaluates their algorithmic complexity against subsequent multi-label learning paradigms.

Cover for Classifier chains for multi-label classification

Abstract

The widely known binary relevance method for multi-label classification, which considers each label as an independent binary problem, has often been overlooked in the literature due to the perceived inadequacy of not directly modelling label correlations. Most current methods invest considerable complexity to model interdependencies between labels. This paper shows that binary relevance-based methods have much to offer, and that high predictive performance can be obtained without impeding scalability to large datasets. We exemplify this with a novel classifier chains method that can model label correlations while maintaining acceptable computational complexity. We extend this approach further in an ensemble framework. An extensive empirical evaluation covers a broad range of multi-label datasets with a variety of evaluation metrics. The results illustrate the competitiveness of the chaining method against related and state-of-the-art methods, both in terms of predictive performance and time complexity.

Topics

multi-label classification svm classification models ensemble classifiers

Keywords

Classifier Chain Binary Relevance Ensemble of Classifier Chain Multi‑label Classification Label Correlation Computational Complexity Evaluation Measure Random k‑Labelset Probabilistic Classifier Chain Threshold Selection

1 Introduction
2 Preliminaries
3 In defence of the binary relevance method
4 The classifier chains model ( CC )
5 Ensembles of classifier chains ( ECC )
6 Related work
6.1 Related methods
6.2 Alternative methods
7 Scaling up ECC
8 Experiments
8.1 Datasets
8.2 Methods
8.3 Evaluation measures
8.4 Threshold selection
8.5 Setup and method
8.6 Results
9 Discussion
9.1 The value of classifier chains
9.2 The value of ensembles of classifier chains
9.3 ECC as compared with other methods
9.4 Scaling up to large datasets
9.5 Time complexity
10 Conclusions
References

Knowls

Knowl 1 — Classifier Chains (CC) Algorithm for Multi-Label Classification
algorithm
The Classifier Chains (CC) method is a problem transformation approach that converts a multi-label classification problem with an input space $\mathcal{X}^d \subseteq \mathbb{R}^d$ and label space $\mathcal{L} = \{1, \dots, L\}$ into a chain of $L$ binary classification problems. Unlike independent Binary Relevance (BR), CC models label interdependencies by extending the attribute space of each binary model with the $0/1$ ground-truth or predicted relevance values of all preceding labels in the chain.

During training, given an ordered sequence of labels $(1, \dots, L)$ , the $j$ -th classifier $h_j$ is trained on instances whose feature vectors are augmented by the true binary values of prior labels: $\mathbf{x}'_j = [x_1, \dots, x_d, y_1, \dots, y_{j-1}] \in \mathcal{X}^d \times \{0, 1\}^{j-1}$ . During inference, classification propagates sequentially from $h_1$ to $h_L$ : each classifier $h_j$ predicts binary relevance $\hat{y}_j \in \{0, 1\}$ given the original features augmented by the predictions of all preceding classifiers in the chain $\hat{\mathbf{x}}'_j = [x_1, \dots, x_d, \hat{y}_1, \dots, \hat{y}_{j-1}]$ .
Algorithm: Classifier Chains Training
Input: Training dataset $D = \{(\mathbf{x}^i, \mathbf{y}^i)\}_{i=1}^N$ where $\mathbf{x}^i \in \mathcal{X}^d$ and $\mathbf{y}^i = [y_1^i, \dots, y_L^i] \in \{0, 1\}^L$ , label sequence $(1, \dots, L)$
Output: Chain of $L$ binary classifiers $\mathbf{h} = (h_1, \dots, h_L)$
1. for $j = 1$ to $L$ do
2. $D'_j \leftarrow \emptyset$
3. for each $(\mathbf{x}^i, \mathbf{y}^i) \in D$ do
4. ${\mathbf{x}'}^i \leftarrow [x_1^i, \dots, x_d^i, y_1^i, \dots, y_{j-1}^i]$
5. $D'_j \leftarrow D'_j \cup \{({\mathbf{x}'}^i, y_j^i)\}$
6. end for
7. Train binary classifier $h_j: \mathcal{X}^d \times \{0, 1\}^{j-1} \rightarrow \{0, 1\}$ on $D'_j$
8. end for
9. return $\mathbf{h} = (h_1, \dots, h_L)
Algorithm: Classifier Chains Prediction
Input: Test instance $\mathbf{x} = [x_1, \dots, x_d] \in \mathcal{X}^d$ , chain of binary classifiers $\mathbf{h} = (h_1, \dots, h_L)$
Output: Predicted binary label vector $\hat{\mathbf{y}} = [\hat{y}_1, \dots, \hat{y}_L] \in \{0, 1\}^L$
1. for $j = 1$ to $L$ do
2. $\mathbf{x}' \leftarrow [x_1, \dots, x_d, \hat{y}_1, \dots, \hat{y}_{j-1}]$
3. $\hat{y}_j \leftarrow h_j(\mathbf{x}')$
4. end for
5. return $\hat{\mathbf{y}} = [\hat{y}_1, \dots, \hat{y}_L]
Knowl 2 — Ensembles of Classifier Chains (ECC)
algorithm
Ensembles of Classifier Chains (ECC) mitigates the sensitivity of a standalone Classifier Chains (CC) model to label ordering and prevents error propagation along the chain by combining $m$ diverse CC models.

In training, ECC fits $m$ individual CC models $\mathbf{h}^{(1)}, \dots, \mathbf{h}^{(m)}$ . For each ensemble iteration $k \in \{1, \dots, m\}$ :
1. A random permutation of the label ordering $(1, \dots, L)$ is selected.
2. A bootstrap training sample $D^{(k)}$ of size $N$ is drawn uniformly with replacement from the original training set $D$ .
3. A CC model $\mathbf{h}^{(k)}$ is trained on $D^{(k)}$ along the chosen random permutation.
Algorithm: ECC Prediction and Voting
Input: Test instance $\mathbf{x} \in \mathcal{X}^d$ , ensemble of $m$ trained CC models $\{\mathbf{h}^{(1)}, \dots, \mathbf{h}^{(m)}\}$ , threshold $t \in [0, 1]$
Output: Binary prediction vector $\hat{\mathbf{y}} = [\hat{y}_1, \dots, \hat{y}_L] \in \{0, 1\}^L$
1. for $k = 1$ to $m$ do
2. $\hat{\mathbf{y}}^{(k)} \leftarrow \text{CC-CLASSIFY}(\mathbf{x}, \mathbf{h}^{(k)})$
3. end for
4. for $j = 1$ to $L$ do
5. $\hat{w}_j \leftarrow \frac{1}{m} \sum_{k=1}^m \hat{y}_{j,k}$
6. if $\hat{w}_j \ge t$ then
7. $\hat{y}_j \leftarrow 1$
8. else
9. $\hat{y}_j \leftarrow 0$
10. end if
11. end for
12. return $\hat{\mathbf{y}} = [\hat{y}_1, \dots, \hat{y}_L]
The continuous ensemble confidence for each label is $\hat{w}_j = \frac{1}{m} \sum_{k=1}^m \hat{y}_{j,k}$ . Bipartitions are generated via thresholding: $\hat{y}_j = 1$ if $\hat{w}_j \ge t$ and $0$ otherwise.
Knowl 3 — Cardinality-Calibrated Threshold Selection for Multi-Label Ensembles
equation
When a multi-label ensemble produces a vector of continuous confidence values $\hat{\mathbf{w}} = [\hat{w}_1, \dots, \hat{w}_L] \in [0, 1]^L$ for test instances $i = 1, \dots, N_{\text{test}}$ , a single global threshold $t \in [0, 1]$ is selected by minimizing the difference between the average label cardinality observed on the training dataset $D$ and the predicted average label cardinality on the evaluation set:

$t = \arg\min_t \left| \text{LCARD}(D) - \frac{1}{N_{\text{test}}} \sum_{i=1}^{N_{\text{test}}} \sum_{j=1}^L \mathbf{1}_{\hat{w}_j^i \ge t} \right|$

where the training Label Cardinality (LCARD) for $N$ training examples with binary label matrix $\mathbf{y} \in \{0, 1\}^{N \times L}$ is defined as:

$\text{LCARD}(D) = \frac{1}{N} \sum_{i=1}^N \sum_{j=1}^L y_j^i$

This calibration strategy aligns the density of positive predictions with the empirical label density of the dataset, providing robust thresholding across varied domains without requiring per-label threshold optimization.
Knowl 4 — Bounded Multi-Label Log-Loss Evaluation Metric
equation
The multi-label Log-Loss evaluates predicted label confidence scores $\hat{\mathbf{w}}^i = [\hat{w}_1^i, \dots, \hat{w}_L^i] \in [0, 1]^L$ against ground-truth binary label vectors $\mathbf{y}^i = [y_1^i, \dots, y_L^i] \in \{0, 1\}^L$ across $N$ instances and $L$ labels by penalizing over-confident errors logarithmically:

$\text{LOG-LOSS} = \frac{1}{NL} \sum_{i=1}^N \sum_{j=1}^L \min\left( \text{loss}(\hat{w}_j^i, y_j^i), \, \ln(N) \right)$

where the point-wise binary cross-entropy is:

$\text{loss}(\hat{w}, y) = - \left( y \ln(\hat{w}) + (1 - y) \ln(1 - \hat{w}) \right)$

The dataset-dependent cap $\ln(N)$ truncates the maximum error contribution of any single label prediction, smoothing the metric and preventing isolated, severely over-confident mistakes (such as predicting $\hat{w} \approx 0$ when $y = 1$ ) from distorting the overall evaluation score.
Knowl 5 — Computational Complexity Comparison of Problem Transformation Methods
theoretical result
For a dataset with $N$ instances, $d$ attributes, and $L$ binary labels, problem transformation methods exhibit distinct worst-case computational and architectural scaling:
- Binary Relevance (BR): Trains $L$ independent binary models with 2 classes each on $N$ instances and $d$ features. Total complexity is $O(L \cdot f(d, N))$ , where $f(d, N)$ represents the base learner training complexity.
- Classifier Chains (CC): Trains $L$ binary models with 2 classes each on $N$ instances. The $j$ -th classifier trains on $d + j - 1$ features, yielding a total complexity of $O(L \cdot f(d + L, N))$ . For base learners linear in the feature count ( $f(d, N) = d \cdot f(1, N)$ ), the complexity is $O(L \cdot d \cdot f(1, N) + L^2 \cdot f(1, N))$ . When $L < d$ (standard in multi-label classification), the first term dominates, giving an effective complexity of $O(L \cdot d \cdot f(1, N))$ , identical to BR.
- Pairwise Classification (PW / CLR): Trains $\frac{L(L-1)}{2}$ binary models with 2 classes each on $\le N$ examples, scaling quadratically $O(L^2)$ in the number of classifiers.
- Label Combination / Label Powerset (LC): Trains 1 multi-class model with up to $\min(N, 2^L - 1)$ distinct atomic classes on $N$ examples, scaling exponentially with $L$ .
Unlike Label Powerset or Stacking / Meta-BR (MBR) methods, CC trains in a single iteration without internal validation and allows model serialization and parallelization during training.
Knowl 6 — Probabilistic Interpretation of Classifier Chains as Greedy Joint Mode Approximation
theoretical result
According to the probability product rule, the joint conditional probability distribution of the multi-label vector $\mathbf{y} = [y_1, \dots, y_L] \in \{0, 1\}^L$ given input features $\mathbf{x} \in \mathcal{X}^d$ factorizes as:

$P(\mathbf{y} \mid \mathbf{x}) = P(y_1 \mid \mathbf{x}) \prod_{j=2}^L P(y_j \mid \mathbf{x}, y_1, \dots, y_{j-1})$

When probabilistic base classifiers $h_j(\mathbf{x}, y_1, \dots, y_{j-1}) = P(y_j = 1 \mid \mathbf{x}, y_1, \dots, y_{j-1})$ are employed:

$P(\mathbf{y} \mid \mathbf{x}) = h_1(\mathbf{x}) \prod_{j=2}^L h_j(\mathbf{x}, y_1, \dots, y_{j-1})$

Probabilistic Classifier Chains (PCC) finds the Bayes-optimal label combination by searching over all $2^L$ possible binary vectors $\mathbf{y}$ , rendering exact inference computationally intractable for $L > 10\text{--}15$ .

Standard Classifier Chains (CC) passes deterministic binary predictions $\hat{y}_j \in \{0, 1\}$ greedily along the chain. This serves as a greedy mode-seeking approximation of $P(\mathbf{y} \mid \mathbf{x})$ in $O(L)$ time. When labels are conditionally independent, CC behaves like Binary Relevance; when correlations are present, it approximates the mode of the joint distribution, mimicking Label Powerset.
Knowl 7 — Subsampled Scalable Ensembles of Classifier Chains
model/method
To reduce time and memory complexity on large multi-label datasets while maintaining predictive accuracy, Ensembles of Classifier Chains (ECC) can be configured with learning-space subsampling:
1. Instance Subsampling: Each ensemble chain is trained on a random subset (sampled without replacement) of the training instances (e.g., 75% of $N$ ).
2. Attribute Subsampling: Each binary classifier within a chain is trained on a random subset of the original feature space (e.g., 50% of the $d$ attributes) in addition to preceding chained label features.
3. Reduced Ensemble Size: The number of ensemble iterations is reduced from $m = 50$ to $m = 10$ .
This configuration reduces training time substantially compared to standard bagging on the full dataset while suffering negligible degradation in multi-label accuracy.
Knowl 8 — Label Set Diversity Statistics: PUNIQ and PMAX
definition
To characterize the distribution, uniformity, and regularity of label combinations in a multi-label dataset $D = \{(\mathbf{x}^i, \mathbf{y}^i)\}_{i=1}^N$ with label space $\mathcal{L} = \{1, \dots, L\}$ , two statistics complement Label Cardinality:
1. Proportion of Unique Label Combinations (PUNIQ): The fraction of instances in $D$ whose specific label combination occurs exactly once:
$\text{PUNIQ} = \frac{\left| \{\mathbf{y} \mid \exists ! \, \mathbf{x} \text{ s.t. } (\mathbf{x}, \mathbf{y}) \in D\} \right|}{N}$
1. Proportion of Label Sets with Maximum Frequency (PMAX): The proportion of instances associated with the single most frequent label combination in $D$ :
$\text{PMAX} = \frac{\max_{\mathbf{y}} \text{COUNT}(\mathbf{y}, D)}{N}$

where $\text{COUNT}(\mathbf{y}, D) = \sum_{i=1}^N \mathbf{1}_{\mathbf{y}^i = \mathbf{y}}$ .

A high PMAX combined with low PUNIQ indicates a skewed distribution concentrated on a few standard label sets, whereas a high PUNIQ (such as 0.981 in Delicious) indicates severe combinatorial label sparsity where nearly all instances possess distinct label sets.

Knowl 9 — Empirical Comparison of Standalone CC against BR, MBR, and SMBR

data/table

Standalone Classifier Chains (CC) was compared against Binary Relevance (BR), Meta-BR (MBR, which stacks BR predictions into a second training stage), and Subset-Mapped BR (SMBR, which maps BR output vectors to the nearest observed training label combination via Hamming distance) using $5 \times 2$ -fold cross-validation with a linear Support Vector Machine (SMO base classifier) across 9 benchmark multi-label datasets.

Dataset	0/1 Loss $\downarrow$				Accuracy $\uparrow$
	BR	CC	MBR	SMBR	BR	CC	MBR	SMBR
Music	0.736	0.713	0.714	0.728	0.506	0.525	0.529	0.530
Scene	0.489	0.361	0.446	0.434	0.587	0.685	0.614	0.622
Yeast	0.856	0.788	0.854	0.836	0.496	0.527	0.497	0.491
Genbase	0.031	0.031	0.031	0.032	0.983	0.983	0.983	0.981
Medical	0.358	0.328	0.357	0.344	0.730	0.752	0.730	0.730
Slashdot	0.660	0.622	0.660	0.642	0.435	0.464	0.437	0.447
Enron	0.899	0.885	0.898	0.889	0.387	0.393	0.388	0.390
LangLog	0.784	0.781	0.784	0.781	0.106	0.108	0.106	0.106
Reuters	0.732	0.670	0.727	0.725	0.319	0.387	0.324	0.324
Avg. Rank	3.889	1.333	2.778	2.222	3.222	1.333	2.333	2.778

Nemenyi statistical significance tests show that CC achieves the best average rank (1.333) and is significantly superior to MBR and BR on 0/1 Loss ( $\text{CC} \succ \{\text{MBR}, \text{BR}\}$ ), and significantly superior to SMBR and BR on Accuracy ( $\text{CC} \succ \{\text{SMBR}, \text{BR}\}$ ). On macro F-Measure, CC and MBR both significantly outperform SMBR. In training runtime, CC is nearly identical to BR, whereas MBR requires more than twice the running time.

Knowl 10 — Empirical Benchmark of ECC against State-of-the-Art Multi-Label Methods

data/table

Ensembles of Classifier Chains (ECC, $m=50$ ) was evaluated against Ensembles of Binary Relevance (EBR, $m=50$ ), Ensembles of Pruned Sets (EPS, $m=50$ ), Instance-Based Logistic Regression (IBLR, $k=10$ ), Calibrated Label Ranking (CLR), RAkEL(1) ( $m=10, k=L/2$ ), and RAkEL(2) ( $m=2L, k=3$ ) across 9 standard datasets using $5 \times 2$ -fold cross-validation with a linear SVM base classifier.

Metric	CLR	EBR	ECC	EPS	IBLR	RAkEL(1)	RAkEL(2)
0/1 Loss $\downarrow$	6.000 (7)	4.667 (5)	3.111 (3)	1.889 (1)	4.889 (6)	2.389 (2)	3.944 (4)
Hamming Loss $\downarrow$	6.250 (7)	4.167 (5)	2.611 (1)	3.778 (4)	4.667 (6)	3.333 (3)	2.778 (2)
Accuracy $\uparrow$	5.750 (7)	4.556 (5)	2.667 (3)	2.556 (2)	5.000 (6)	2.333 (1)	4.444 (4)
Log-Loss $\downarrow$	5.000 (6)	2.889 (2)	1.556 (1)	3.333 (3)	3.667 (4)	4.889 (5)	5.556 (7)
F-Measure $\uparrow$	4.500 (6)	4.000 (3)	2.333 (1)	4.000 (3)	5.000 (7)	2.667 (2)	4.111 (5)

ECC achieves the overall best average rank on Log-Loss (1.556), Hamming Loss (2.611), and F-Measure (2.333). Nemenyi tests indicate that ECC is statistically significantly better than RAkEL(2), RAkEL(1), and CLR on Log-Loss ( $\text{ECC} \succ \{\text{RAkEL}(2), \text{RAkEL}(1), \text{CLR}\}$ ), significantly better than CLR on Hamming Loss and 0/1 Loss, and significantly better than IBLR on F-Measure.

Knowl 11 — Scalability Limits and Performance of Multi-Label Methods on Large Datasets
empirical result
Empirical testing on six large multi-label datasets (TMC2007: $N=28,596, L=22$ ; Ohsumed: $N=13,929, L=23$ ; MediaMill: $N=43,907, L=101$ ; Bibtex: $N=7,395, L=159$ ; IMDB: $N=120,919, L=28$ ; Delicious: $N=16,105, L=983$ ) using a 60/40 train/test split demonstrated severe scalability constraints for non-binary methods:
1. Pairwise (CLR) fails on datasets with large label counts ( $L > 64$ ), timing out or exhausting memory on Bibtex ( $L=159$ ), MediaMill ( $L=101$ ), and Delicious ( $L=983$ ) due to its $O(L^2)$ scaling (requiring 16,256 models at $L=128$ ).
2. Label Powerset and RAkEL fail to complete on large datasets (such as IMDB and Delicious) due to memory exhaustion caused by exponential distinct label set growth ( $\{\min(N, 2^L - 1)\}$ class combinations).
3. Instance-based IBLR fails when instance counts grow large ( $N > 200,000$ ), failing on IMDB due to $k$ -nearest neighbor computation overhead.
4. Binary Relevance methods (BR, EBR, and Subsampled ECC) successfully completed on all large datasets within 2 GB memory and one-week time limits. Subsampled ECC ( $m=10$ , 75% instance subset, 50% attribute subset) ranked first or second in F-Measure (avg rank 2.167) and Accuracy (avg rank 2.667) across large datasets, including Delicious ( $L=983$ ). When training instances $N$ are very large, baseline BR and EBR perform competitively with or better than complex correlation-modeling methods.

Coverage note — None was omitted; all primary models, algorithms, theoretical complexity and probabilistic analyses, threshold calibration methods, and benchmark experimental results are included.

References

1.Boutell, M. R., Luo, J., Shen, X., & Brown, C. M. (2004). Learning multi-label scene classification. Pattern Recognition, 37(9), 1757–1771.
2.Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123–140.
3.Cheng, W., & Hüllermeier, E. (2009). Combining instance-based learning and logistic regression for multilabel classification. Machine Learning, 76(2–3), 211–225. doi:10.1007/s10994-009-5127-5.
4.Cheng, W., Dembczyński, K., & Hüllermeier, E. (2010). Bayes optimal multilabel classification via probabilistic classifier chains. In ICML ’10: 27th international conference on machine learning. Haifa: Omnipress.
5.Clare, A., & King, R. D. (2001). Lecture notes in computer science: Vol. 2168. Knowledge discovery in multi-label phenotype data.
6.Dembczyński, K., Waegeman, W., Cheng, W., & Hüllermeier, E. (2010). On label dependence in multi-label classification. In Workshop proceedings of learning from multi-label data (pp. 5–12). Haifa, Israel.
7.Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7, 1–30.
8.Dimou, A., Tsoumakas, G., Mezaris, V., Kompatsiaris, I., & Vlahavas, I. (2009). An empirical study of multi-label learning methods for video annotation. In Proceedings of the 7th international workshop on content-based multimedia indexing. New York: IEEE.
9.Elisseeff, A., & Weston, J. (2001). A kernel method for multi-labelled classification. In Advances in neural information processing systems (Vol. 14, pp. 681–687). Cambridge: MIT Press.
10.Fan, R. E., & Lin, C. J. (2007). A study on threshold selection for multi-label classification (Tech. rep.). National Taiwan University. http://www.csie.ntu.edu.tw/cjlin/papers/threshold.pdf.
11.Freund, Y., & Schapire, R. E. (1999). A short introduction to boosting. Jinkō Chinō Gakkaishi, 14(5), 771–780.
12.Fürnkranz, J. (2002). Round robin classification. Machine Learning, 2, 721–747.
13.Fürnkranz, J., Hüllermeier, E., Loza Mencía, E., & Brinker, K. (2008). Multilabel classification via calibrated label ranking. Machine Learning, 73(2), 133–153. doi:10.1007/s10994-008-5064-8.
14.Godbole, S., & Sarawagi, S. (2004). Discriminative methods for multi-labeled classification. In PAKDD ’04: eighth Pacific-Asia conference on knowledge discovery and data mining (pp. 22–30). Berlin: Springer.
15.Hall, M., Frank, E., Holmes, G., Pfahringer, B., Peter, R., & Witten, I. H. (2009). The weka data mining software: An update. SIGKDD Explorations, 11(1).
16.Hsu, D., Kakade, S. M., Langford, J., & Zhang, T. (2009). Multi-label prediction via compressed sensing. In NIPS ’09: neural information processing systems 2009.
17.Ji, S., Tang, L., Yu, S., & Ye, J. (2008). Extracting shared subspace for multi-label classification. In KDD ’08: 14th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 381–389). New York: ACM. doi:10.1145/1401890.1401939.
18.Kiritchenko, S. (2005). Hierarchical text categorization and its application to bioinformatics. Ph.D. thesis, Queen’s University, Kingston, Canada.
19.Loza Mencía, E., & Fürnkranz, J. (2008). Efficient pairwise multilabel classification for large-scale problems in the legal domain. In ECML-PKDD ’08: European conference on machine learning and knowledge discovery in databases (pp. 50–65). Berlin: Springer. doi:10.1007/978-3-540-87481-2_4.
20.McCallum, A. K. (1999). Multi-label text classification with a mixture model trained by EM. In Association for the advancement of artificial intelligence workshop on text learning.
21.Petrovskiy, M. (2006). Paired comparisons method for solving multi-label learning problem. In HIS ’06: sixth international conference on hybrid intelligent systems. New York: IEEE. doi:10.1109/HIS.2006.264925.
22.Platt, J. C. (1999). Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in large margin classifiers (pp. 61–74). Cambridge: MIT Press.
23.Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106.
24.Ráez, A. M., López, L. A. U., & Steinberger, R. (2004). Adaptive selection of base classifiers in one-against-all learning for large multi-labeled collections. In EsTAL: 4th international conference on advances in natural language processing (pp. 1–12).
25.Read, J., Pfahringer, B., & Holmes, G. (2008). Multi-label classification using ensembles of pruned sets. In ICDM’08: eighth IEEE international conference on data mining (pp. 995–1000). New York: IEEE.
26.Read, J., Pfahringer, B., & Holmes, G. (2009a). Generating synthetic multi-label data streams. In MLD ’09: 1st ECML/PKDD 2009 workshop on learning from multi-label data.
27.Read, J., Pfahringer, B., Holmes, G., & Frank, E. (2009b). Classifier chains for multi-label classification. In ECML ’09: 20th European conference on machine learning (pp. 254–269). Berlin: Springer.
28.Schapire, R. E., & Singer, Y. (1999). Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3), 297–336.
29.Schapire, R. E., & Singer, Y. (2000). Boostexter: a boosting-based system for text categorization. Machine Learning, 39(2/3), 135–168.
30.Spyromitros, E., Tsoumakas, G., & Vlahavas, I. (2008). An empirical study of lazy multilabel classification algorithms. In SETN ’08: fifth Hellenic conference on artificial intelligence (pp. 401–406). Berlin: Springer.
31.Sun, L., Ji, S., & Ye, J. (2008). Hypergraph spectral learning for multi-label classification. In KDD ’08: 14th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 668–676). New York: ACM. doi:10.1145/1401890.1401971.
32.Tai, F., & Lin, H. T. (2010). Multi-label classification with principle label space transformation. In Workshop proceedings of learning from multi-label data, Haifa, Israel.
33.Tsoumakas, G., & Katakis, I. (2007). Multi label classification: an overview. International Journal of Data Warehousing and Mining, 3(3), 1–13.
34.Tsoumakas, G., & Vlahavas, I. P. (2007). Random k-labelsets: an ensemble method for multilabel classification. In ECML ’07: 18th European conference on machine learning (pp. 406–417). Berlin: Springer.
35.Vens, C., Struyf, J., Schietgat, L., Džeroski, S., & Blockeel, H. (2008). Decision trees for hierarchical multi-label classification. Machine Learning, 2(73), 185–214. doi:10.1007/s10994-008-5077-3.
36.Yan, R., Tesic, J., & Smith, J. R. (2007). Model-shared subspace boosting for multi-label classification. In KDD ’07: 13th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 834–843). New York: ACM. doi:10.1145/1281192.1281281.
37.Yang, Y. (2001). A study on thresholding strategies for text categorization. In Proceedings of SIGIR-01, 24th ACM international conference on research and development in information retrieval (pp. 137–145). New York: ACM Press.
38.Zhang, M. L., & Zhou, Z. H. (2005). A k-nearest neighbor based algorithm for multi-label classification. In GnC ’05: IEEE international conference on granular computing (pp. 718–721). New York: IEEE.
39.Zhang, M. L., & Zhou, Z. H. (2007). ML-KNN: a lazy learning approach to multi-label learning. Pattern Recognition, 40(7), 2038–2048.

Citation

MLA

Read, J., et al. “Classifier Chains for Multi-label Classification”. Machine Learning, vol. 85, no. 3, 2011, pp. 333–59, https://doi.org/10.1007/s10994-011-5256-5.

APA

Read, J., Pfahringer, B., Holmes, G., & Frank, E. (2011). Classifier chains for multi-label classification. Machine Learning, 85(3), 333–359. https://doi.org/10.1007/s10994-011-5256-5

Chicago

Read, J., B. Pfahringer, G. Holmes, and E. Frank. 2011. “Classifier Chains for Multi-label Classification”. Machine Learning 85 (3): 333–59. https://doi.org/10.1007/s10994-011-5256-5.

Harvard

Read, J. et al. (2011) “Classifier chains for multi-label classification”, Machine Learning, 85(3), pp. 333–359. Available at: https://doi.org/10.1007/s10994-011-5256-5.

Vancouver

1. Read J, Pfahringer B, Holmes G, Frank E (2011) Classifier chains for multi-label classification. Machine Learning 85:333–359

BibTeX

@article{Read_2011, title={Classifier chains for multi-label classification}, volume={85}, ISSN={1573-0565}, url={http://dx.doi.org/10.1007/s10994-011-5256-5}, DOI={10.1007/s10994-011-5256-5}, number={3}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Read, Jesse and Pfahringer, Bernhard and Holmes, Geoff and Frank, Eibe}, year={2011}, month=June, pages={333–359} }

Metadata:Crossref

Access the Paper

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

Open PDF

Classifier chains for multi-label classification

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Classifier Chains (CC) Algorithm for Multi-Label Classification

Knowl 2 — Ensembles of Classifier Chains (ECC)

Knowl 3 — Cardinality-Calibrated Threshold Selection for Multi-Label Ensembles

Knowl 4 — Bounded Multi-Label Log-Loss Evaluation Metric

Knowl 5 — Computational Complexity Comparison of Problem Transformation Methods

Knowl 6 — Probabilistic Interpretation of Classifier Chains as Greedy Joint Mode Approximation

Knowl 7 — Subsampled Scalable Ensembles of Classifier Chains

Knowl 8 — Label Set Diversity Statistics: PUNIQ and PMAX