A kernel method for multi-labelled classification

A. ElisseeffJ. Weston

article2001NeurIPS1,527 citations

Presents a large-margin kernel ranking framework for multi-label classification that directly minimizes ranking loss while capturing correlations between labels better than standard binary decomposition methods.

Listen

Many modern analytical problems in domains like bioinformatics and text mining require multi-label classification, where a single data instance can belong to several categories simultaneously (such as a gene participating in multiple biological functions). Common approaches typically break these problems down into separate, independent binary decisions. However, this independent decomposition fails to capture correlations among labels and often leads to weak predictive power, while existing multi-label boosting algorithms frequently suffer from overfitting when training datasets are small.

The article develops and evaluates a direct multi-label classification framework based on a large-margin ranking system, termed Ranking Support Vector Machine (Rank-SVM). The objective is to effectively rank potential labels and accurately predict the appropriate set size for each instance while controlling model complexity through regularization and kernel methods.

The researchers formulated a quadratic optimization problem that directly minimizes ranking errors while maximizing classification margins, extending Support Vector Machine principles to multi-label problems. To complete the classification process, they integrated a learned threshold mechanism to predict how many top-ranked labels should be assigned to an instance. They validated the method using synthetic data to demonstrate theoretical advantages over binary models, followed by rigorous benchmarking on a real-world Yeast gene functional classification dataset comprising 1,500 training genes, 917 test genes, and 14 potential functional categories across polynomial kernels of varying complexity.

The empirical evaluation demonstrated four primary findings. First, Rank-SVM consistently achieved higher precision and lower error rates across almost all evaluated metrics compared to traditional binary decomposition methods. Second, Rank-SVM substantially reduced ranking loss relative to the binary approach, confirming its capability to correctly order relevant labels before irrelevant ones. Third, both SVM-based approaches markedly outperformed the established boosting baseline (Boostexter), which yielded poor precision (0.70) and higher error rates on the gene dataset. Fourth, the performance advantage of Rank-SVM over binary methods was most pronounced with lower-degree polynomial kernels, gradually converging as kernel complexity increased.

These results indicate that directly incorporating label rankings and margin regularization yields superior predictive performance without requiring extensive separate tuning for each class. For organizations deploying predictive models on complex biological or textual data, adopting Rank-SVM reduces the risk of misclassification driven by unmodeled label dependencies. Furthermore, the framework's compatibility with kernel methods allows domain-specific knowledge to be embedded directly into the learning process.

Decision-makers and practitioners working with multi-label data should consider transitioning from disconnected binary models or decision-stump boosting frameworks to large-margin ranking architectures like Rank-SVM. Moving forward, the article suggests extending this system to incorporate feature selection algorithms on ranking problems, which will enhance interpretability by identifying small, discriminative subsets of features for specific applications, such as identifying key genes in complex medical disorders.

While the findings are strong, the study represents initial experimental validation on a single real-world biological dataset and a stylized synthetic test. Computational efficiency also requires specialized optimization techniques, as standard implementations can be memory-intensive. Additional testing across broader industrial datasets and higher-dimensional label hierarchies is recommended before broad operational rollout.

BIOwulf Technologies kernel method multi-label classification support vector multi-labelled classification kernel method support vector machines

Elisseeff et al (2001).pdf

Paper: BoosTexter: A Boosting-based System for Text Categorization, ROBERT E. SCHAPIRE et al. (2000). It introduces the multi-label boosting benchmark BoosTexter that the source directly compares against and builds upon.
Paper: An Efficient Boosting Algorithm for Combining Preferences, Yoav Freund et al. (1998). It formalizes the pairwise preference ranking formulation that underpins the ranking loss minimized by Rank-SVM.
Paper: Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers, Erin L. Allwein et al. (2000). It analyzes margin-based reductions of multiclass problems to binary subproblems, providing the theoretical context for overcoming binary decomposition in multi-label settings.
Paper: Support-vector networks, Corinna Cortes et al. (1995). It introduces soft-margin Support Vector Machines and decomposition algorithms, which serve as the foundational learning framework extended by the source.
Paper: A training algorithm for optimal margin classifiers, Bernhard E. Boser et al. (1992). It establishes the core quadratic optimization framework for large-margin classifiers with kernel functions utilized throughout the source.

Paper: A Review on Multi-Label Learning Algorithms, Min-Ling Zhang et al. (2014). It provides a comprehensive review of multi-label learning algorithms, explicitly categorizing and contextualizing Rank-SVM within second-order ranking and algorithm-adaptation paradigms.
Paper: Classifier chains for multi-label classification, Jesse Read et al. (2009). It develops classifier chains to model higher-order label correlations efficiently as an alternative to ranking and pairwise margin formulations.
Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). It generalizes large-margin optimization from label ranking to arbitrary complex, interdependent, and structured output variables using cutting-plane methods.
Paper: Optimizing search engines using clickthrough data, Thorsten Joachims (2002). It adapts pairwise Ranking SVM architectures to information retrieval and search engine optimization using implicit clickthrough data.
Paper: An Introduction to Variable and Feature Selection, Isabelle M Guyon et al. (2003). Co-authored by one of the source's authors, it synthesizes variable and feature selection techniques, addressing the explicit future direction suggested in the source.
Paper: Training linear SVMs in linear time, Thorsten Joachims (2006). It develops linear-time cutting-plane algorithms for linear SVMs and ordinal ranking, addressing the computational bottlenecks noted in the source.
Paper: Regularized multi--task learning, T. Evgeniou et al. (2004). It extends regularized kernel methods to multi-task learning by explicitly capturing relations between tasks in a unified margin formulation.

Cover for A kernel method for multi-labelled classification

Abstract

This article presents a Support Vector Machine (SVM) like learning system to handle multi-label problems. Such problems are usually decomposed into many two-class problems but the expressive power of such a system can be weak [5, 7]. We explore a new direct approach. It is based on a large margin ranking system that shares a lot of common properties with SVMs. We tested it on a Yeast gene functional classification problem with positive results.

Topics

kernel method multi-label classification support vector svm classification models adaptive boosting

Keywords

multi-labelled classification kernel method support vector machines polynomial kernels text categorization phylogenetic profiles loss functions large margin

1 Introduction
2 Cost functions
3 Ranking based system
4 Set size prediction
5 Toy problem
6 Experiments on real data
7 Discussion and conclusion
References

Knowls

Knowl 1 — Rank-SVM Quadratic Optimization Formulation
model/method
Rank-SVM is a multi-label ranking algorithm that learns a linear scoring function $r_k(x) = \langle w_k, x \rangle + b_k$ for each label $k \in \{1, \dots, Q\}$ from a training dataset $S = \{(x_1, Y_1), \dots, (x_m, Y_m)\} \subset (\mathbb{R}^d \times \mathcal{P}(\{1, \dots, Q\}))^m$ , where $Y_i$ is the set of relevant labels for sample $x_i$ and $\bar{Y}_i = \{1, \dots, Q\} \setminus Y_i$ is its complement.

The parameters $w_1, \dots, w_Q \in \mathbb{R}^d$ , $b_1, \dots, b_Q \in \mathbb{R}$ , and ranking slack variables $\xi_{ikl} \ge 0$ are obtained by solving the quadratic optimization problem:

$\min_{w_1, \dots, w_Q, b_1, \dots, b_Q, \xi} \sum_{k=1}^Q \|w_k\|^2 + C \sum_{i=1}^m \frac{1}{|Y_i| |\bar{Y}_i|} \sum_{(k,l) \in Y_i \times \bar{Y}_i} \xi_{ikl}$

subject to the constraints:

$\langle w_k - w_l, x_i \rangle + b_k - b_l \ge 1 - \xi_{ikl}, \quad \forall i \in \{1, \dots, m\}, \; \forall (k,l) \in Y_i \times \bar{Y}_i$ $\xi_{ikl} \ge 0, \quad \forall i \in \{1, \dots, m\}, \; \forall (k,l) \in Y_i \times \bar{Y}_i$

where $C > 0$ is a regularization hyperparameter balancing model complexity with ranking violations. When $|Y_i| = 1$ for all $i$ , this formulation reduces to multi-class Support Vector Machines. The formulation supports kernelization through its dual representation.
Knowl 2 — Multi-Label Geometric Margin Formulation
theoretical result
For a multi-label linear ranking system with scoring functions $r_k(x) = \langle w_k, x \rangle + b_k$ ( $k \in \{1, \dots, Q\}$ ), the decision boundary separating relevant labels $k \in Y$ from irrelevant labels $l \in \bar{Y} = \{1, \dots, Q\} \setminus Y$ for input $x \in \mathbb{R}^d$ consists of the hyperplanes $\langle w_k - w_l, x \rangle + b_k - b_l = 0$ .

The geometric $L_2$ margin of an example $(x, Y)$ to the decision boundary is:

$\min_{k \in Y, l \in \bar{Y}} \frac{\langle w_k - w_l, x \rangle + b_k - b_l}{\|w_k - w_l\|}$

Under the condition that the training examples are correctly ranked, parameters can be scaled such that $\langle w_k - w_l, x_i \rangle + b_k - b_l \ge 1$ for all $(k,l) \in Y_i \times \bar{Y}_i$ . Maximizing the margin over the training set corresponds to solving:

$\max_{w_j, b_j} \min_{(x, Y) \in S} \min_{k \in Y, l \in \bar{Y}} \frac{1}{\|w_k - w_l\|^2} \quad \text{subject to} \quad \langle w_k - w_l, x_i \rangle + b_k - b_l \ge 1, \; (k,l) \in Y_i \times \bar{Y}_i$

When no two labels always co-occur, approximating the max-min objective by the sum of squared norms yields the regularizer $\sum_{k=1}^Q \|w_k\|^2$ .
Knowl 3 — Threshold-Based Multi-Label Set Size Prediction
model/method
To transform a ranking model with scoring functions $(r_1(x), \dots, r_Q(x))$ into a multi-label classification system that predicts a discrete label set $\hat{Y}(x) = \{k \in \{1, \dots, Q\} \mid r_k(x) > t(x)\}$ , a threshold function $t(x)$ is learned:
1. For each training sample $(x_i, Y_i)$ with complement $\bar{Y}_i$ , compute the optimal threshold $t(x_i)$ that minimizes label assignment errors: $t(x_i) = \arg\min_t \left( |\{k \in Y_i \mid r_k(x_i) \le t\}| + |\{k \in \bar{Y}_i \mid r_k(x_i) \ge t\}| \right)$ When the set of minimizers forms a closed segment, $t(x_i)$ is chosen as the midpoint of that segment.
2. Fit a regression model (e.g., linear least squares) mapping the score vector $(r_1(x_i), \dots, r_Q(x_i))$ to the target threshold $t(x_i)$ .
3. For an unseen input $x$ , evaluate the ranking functions to obtain $(r_1(x), \dots, r_Q(x))$ , compute the predicted threshold $t(x)$ , and assign all labels satisfying $r_k(x) > t(x)$ . Learning the threshold over ranking outputs enables the predictor to adapt to ranking errors, whereas direct regression of set size $|Y_i|$ on input $x_i$ cannot compensate for ranking imperfections.
Knowl 4 — Multi-Label Classification and Ranking Performance Metrics
definition
Let $x \in \mathbb{R}^d$ be an input, $Y \subseteq \{1, \dots, Q\}$ be the true set of relevant labels, and $\bar{Y} = \{1, \dots, Q\} \setminus Y$ be its complement. For a model with scoring functions $r_k(x)$ and predicted label set $f(x) \subseteq \{1, \dots, Q\}$ , standard evaluation metrics are defined as:
- Hamming Loss: The fraction of label misclassifications based on the symmetric difference $\Delta$ : $HL(f, x, Y) = \frac{1}{Q} |f(x) \Delta Y|$ When $|Y|=1$ , $HL(f, x, Y)$ equals $2/Q$ times the standard multi-class error.
- Ranking Loss: The average fraction of pairs of labels that are incorrectly ordered by the real-valued scoring functions: $RL(r, x, Y) = \frac{1}{|Y||\bar{Y}|} \left| \{ (k, l) \in Y \times \bar{Y} \mid r_k(x) \le r_l(x) \} \right|$
- Precision: The average fraction of relevant labels ranked above each relevant label: $\text{precision}(r, x, Y) = \frac{1}{|Y|} \sum_{k \in Y} \frac{|\{l \in Y \mid r_l(x) \ge r_k(x)\}|}{|\{l \in \{1, \dots, Q\} \mid r_l(x) \ge r_k(x)\}|}$
- One-Error: Indicates whether the top-ranked label is incorrect: $\text{1-err}(r, x, Y) = \begin{cases} 0 & \text{if } \arg\max_{k \in \{1,\dots,Q\}} r_k(x) \in Y \\ 1 & \text{otherwise} \end{cases}$
Knowl 5 — Computational Complexity and Optimization of Rank-SVM
theoretical result
Solving the constrained quadratic programming problem of Rank-SVM with general QP solvers requires $O(m^2)$ memory and $O(m^3)$ computational steps, where $m$ is the training set size.

Applying a linearization method coupled with a predictor-corrector logarithmic barrier procedure reduces the complexity to:
- Memory cost: $O(m Q Q_{\max})$ , where $Q$ is the total number of labels and $Q_{\max} = \max_{i=1,\dots,m} |Y_i|$ is the maximum number of positive labels associated with any training instance.
- Per-iteration time cost: $O(m^2 Q)$ .
In typical applications where $Q_{\max} \ll Q \ll m$ , this optimization avoids quadratic scaling in memory relative to the number of constraint pairs.
Knowl 6 — Expressive Power Advantage of Ranking Over Binary Decomposition on Correlated Labels
empirical result
Independent binary classification models can fail to represent simple decision boundaries when label correlations exist across classes.

On a 2D synthetic problem on $[0,1]^2$ with $Q=3$ labels where:
- Label 1 is present on all examples in the dataset (i.e., regions are labelled with $\{1\}$ , $\{1,2\}$ , or $\{1,3\}$ ),
- The region labelled $\{1\}$ is separated by a linear boundary from $\{1,2\} \cup \{1,3\}$ , and
- A linear boundary separates region $\{1,2\}$ from region $\{1,3\}$ ,
the binary decomposition fails because label 1 provides zero training signal to separate points of label $\{1,2\}$ from $\{1,3\}$ , resulting in an empirical Hamming Loss of $0.08$ on 50 uniformly sampled points with $C = \infty$ .

In contrast, Rank-SVM with scoring parameters $w_1 = 0, b_1 = \infty$ , $(w_2, b_2)$ separating class 2 from class 3, $(w_3, b_3) = -(w_2, b_2)$ , and a set size predictor $s(x) = \langle w, x \rangle + b$ with $w = (-1, 1)$ and $b = 0$ achieves a Hamming Loss of $0.00$ , separating all regions perfectly.

Knowl 7 — Yeast Gene Functional Classification Benchmark Results

data/table

Performance comparison on the Yeast gene functional classification dataset (1500 training genes, 917 test genes, 103 input features from microarray expression and phylogenetic profiles, $Q=14$ top-level functional classes, average $4.2 \pm 1.6$ labels per gene) between Rank-SVM and Binary-SVM across polynomial kernel degrees 2 to 9, and Boostexter (1000 iterations with decision stumps). Differences smaller than $0.01$ are not statistically significant.

	Rank-SVM				Binary-SVM
Metric	Deg 2	Deg 3	Deg 4	Deg 5	Deg 2	Deg 3	Deg 4	Deg 5
Precision	0.703	0.740	0.746	0.762	0.692	0.721	0.714	0.753
Ranking Loss	0.227	0.191	0.190	0.175	0.241	0.212	0.196	0.184
Hamming Loss	0.238	0.217	0.209	0.201	0.247	0.224	0.211	0.207
One-Error	0.334	0.262	0.255	0.232	0.341	0.306	0.267	0.250
	Rank-SVM				Binary-SVM
Metric	Deg 6	Deg 7	Deg 8	Deg 9	Deg 6	Deg 7	Deg 8	Deg 9
Precision	0.765	0.770	0.773	0.769	0.760	0.765	0.770	0.769
Ranking Loss	0.170	0.166	0.163	0.163	0.176	0.170	0.165	0.164
Hamming Loss	0.199	0.198	0.196	0.197	0.200	0.199	0.195	0.195
One-Error	0.232	0.223	0.217	0.225	0.232	0.227	0.218	0.226

Boostexter (1000 iterations) yielded Precision = 0.717, Ranking Loss = 0.298, Hamming Loss = 0.237, and One-Error = 0.302.

Rank-SVM consistently achieves superior precision and ranking loss compared to Binary-SVM at lower polynomial degrees (2–5). As polynomial kernel degree increases (6–9), the performance gap between Rank-SVM and Binary-SVM narrows. Both SVM formulations outperform Boostexter across all measured metrics.

Coverage note — None was omitted; all contributed models, margin formulations, set size prediction techniques, computational complexity results, and empirical evaluations are represented.

References

1.B. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifi ers. In Fifth Annual Workshop on Computational Learning Theory, pages 144–152, Pittsburgh, 1992. ACM.
2.N. Cristianini and J. Shawe-Taylor. Introduction to Support Vector Machines. Cambridge University Press, 2000.
3.André Elisseeff and Jason Weston. Kernel methods for multi-labelled classifi cation and categorical regression problems. Technical report, BIOwulf Technologies, 2001. http://www.bht-labs.com/public/.
4.T. Joachims. Text categorization with support vector machines: learning with many relevant features. In Claire Nédellec and Céline Rouveirol, editors, Proceedings of ECML-98, 10th European Conference on Machine Learning, number 1398, pages 137–142, Chemnitz, DE, 1998. Springer Verlag, Heidelberg, DE.
5.A. McCallum. Multi-label text classifi cation with a mixture model trained by em. AAAI’99 Workshop on Text Learning., 1999.
6.P. Pavlidis, J. Weston, J. Cai, and W.N. Grundy. Combining microarray expression data and phylogenetic profi les to learn functional categories using support vector machines. In RECOMB, pages 242–248, 2001.
7.R.E. Schapire and Y. Singer. Boostexter: A boosting-based system for text categorization. Machine Learning, 39(2/3):135–168, 2000.
8.J. Weston and C. Watkins. Multi-class support vector machines. Technical Report 98-04, Royal Holloway, University of London, 1998.

Citation

MLA

Elisseeff, A., and J. Weston. “A Kernel Method for Multi-labelled Classification”. Advances in Neural Information Processing Systems, vol. 14, 2001, https://proceedings.neurips.cc/paper_files/paper/2001/file/39dcaf7a053dc372fbc391d4e6b5d693-Paper.pdf.

APA

Elisseeff, A., & Weston, J. (2001). A kernel method for multi-labelled classification. Advances in Neural Information Processing Systems, 14. https://proceedings.neurips.cc/paper_files/paper/2001/file/39dcaf7a053dc372fbc391d4e6b5d693-Paper.pdf

Chicago

Elisseeff, A., and J. Weston. 2001. “A Kernel Method for Multi-labelled Classification”. Advances in Neural Information Processing Systems 14. https://proceedings.neurips.cc/paper_files/paper/2001/file/39dcaf7a053dc372fbc391d4e6b5d693-Paper.pdf.

Harvard

Elisseeff, A. and Weston, J. (2001) “A kernel method for multi-labelled classification”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2001/file/39dcaf7a053dc372fbc391d4e6b5d693-Paper.pdf.

Vancouver

1. Elisseeff A, Weston J (2001) A kernel method for multi-labelled classification. Advances in Neural Information Processing Systems 14:

BibTeX

@inproceedings{elisseeff2001kernel,
  title = {A kernel method for multi-labelled classification},
  author = {Elisseeff, André and Weston, Jason},
  year = {2001},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {14},
  url = {https://proceedings.neurips.cc/paper_files/paper/2001/file/39dcaf7a053dc372fbc391d4e6b5d693-Paper.pdf}
}

Metadata:DOI registry

Access the Paper

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

Open PDF

License: Authors

A kernel method for multi-labelled classification

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Rank-SVM Quadratic Optimization Formulation

Knowl 2 — Multi-Label Geometric Margin Formulation

Knowl 3 — Threshold-Based Multi-Label Set Size Prediction

Knowl 4 — Multi-Label Classification and Ranking Performance Metrics

Knowl 5 — Computational Complexity and Optimization of Rank-SVM

Knowl 6 — Expressive Power Advantage of Ranking Over Binary Decomposition on Correlated Labels

Knowl 7 — Yeast Gene Functional Classification Benchmark Results

References

Citation

BibTeX

Access the Paper