Optimal Multi-Kernel Combination for Online Multi-Label Classification

Tingting Zhai; Wei Liu; Renjian Yu

cs.LGOct 19, 2026

Optimal Multi-Kernel Combination for Online Multi-Label Classification

Authors: Tingting Zhai, Wei Liu, Renjian Yu

Organizations: College of Information and Artificial Intelligence, Yangzhou University, Yangzhou, China, 225127

Abstract

Multi-label classification is particularly challenging in streaming scenarios, where data arrives sequentially. Online kernel methods offer a promising solution. However, prevailing methods rely on a single preselected kernel, making them prone to suboptimal choices since the global data distribution is unknown in advance in online settings. Although the recent method, Online Kernel Selection for Online Multi-label Classification (OKS-OMC), enables data-driven kernel selection, it fails to fully harness the complementary information from multiple kernels and encounters the curse of kernelization. To address these limitations, this paper introduces a novel online multi-kernel combination method for large-scale multi-label classification. First, an efficient and robust online single-kernel multi-label method is designed. Second, learning an optimal convex combination of multiple multi-label kernel classifiers is formalized as a structural risk minimization problem. An improved alternating optimization procedure is developed, in which the combination coefficients are updated by directly minimizing the objective function, while each kernel classifier is updated by minimizing a surrogate upper bound. This procedure decouples the learning of kernel classifiers from combination coefficients, allowing independent classifier updates via our single-kernel method and accelerating convergence to high-quality solutions. Our multi-kernel method is proven to asymptotically converge to the optimal fixed convex combination of the best fixed single-kernel models chosen in hindsight. Ablation studies confirm that our method's components outperform their counterparts in OKS-OMC. Comprehensive evaluations across 11 datasets and seven metrics demonstrate our method's overall superiority over existing online multi-label methods.

Figures & tables

Kernel name	$K(\bm{\delta})$	$p(\bm{u})$	distribution of $u_{i}$
Gaussian	$\exp\bigl(-\frac{\|\|\bm{\delta}\|\|^{2}}{2\sigma^{2}}\bigr)$	$\prod_{i=1}^{d}\frac{\sigma}{\sqrt{2\pi}}\exp\bigl(-\frac{\sigma^{2}u_{i}^{2}}{2}\bigr)$	Gaussian $\mathcal{N}(0,1/\sigma^{2})$
Laplacian	$\exp\bigl(-\frac{\|\|\bm{\delta}\|\|_{1}}{\sigma}\bigr)$	$\prod_{i=1}^{d}\frac{\sigma}{\pi(1+\sigma^{2}u_{i}^{2})}$	Cauchy $\mathcal{C}(0,1/\sigma)$
Cauchy	$\frac{1}{2^{d}}\prod_{i=1}^{d}\frac{2}{1+(\delta_{i}/\sigma)^{2}}$	$\prod_{i=1}^{d}\frac{\sigma}{2}\exp\bigl(-\sigma\|u_{i}\|\bigr)$	Laplace $\mathcal{L}(0,1/\sigma)$

Table 1: Shift-invariant kernels, their Fourier transforms and the corresponding distribution for

u_{i}

Datasets	domains	#instances ( $T$ )	#features ( $d$ )	#labels ( $L$ )	cardinality
Emotions	music	593	72	6	1.868
Medical	text	978	1449	45	1.245
PlantGO	biology	978	3,091	12	1.079
PlantPseAAC	biology	978	440	12	1.079
Enron	text	1,702	1,001	53	3.378
Image	image	2,000	294	5	1.236

Table 2: The characteristic of the datasets used in the experiments.

Panel of Figure 1 — Figure 1: The evolution of average cumulative loss $Avg(t)$ with the round number $t$ for both OMKC and OKS-OMC. On the HumanPseAAC dataset, the $Avg(t)$ values for the two GAM variants are substantially higher than those of OMKC and OKS-OMC. As a result, their curves fall outside the plotted range of [0.32, 0.42].

Dataset	Algorithm	Psn ( $\uparrow$ )	Rcal ( $\uparrow$ )	F1 ( $\uparrow$ )	MacroF1 ( $\uparrow$ )	MicroF1 ( $\uparrow$ )	Hl ( $\downarrow$ )	Rl ( $\downarrow$ )
Emotions ( $D=16d$ )	OSML-ELM	60.09 (1.57)	56.97 (1.65)	58.48 (1.50)	59.38 (1.69)	61.28 (1.35)	22.36 (0.69)	19.69 (0.78)
	ELM-OMLL	61.77 (0.76)	74.90 (1.20)	67.70 (0.76)	65.98 (0.71)	66.59 (0.71)	23.26 (0.48)	18.54 (0.45)
	ELM-O	31.89 (0.18)	81.61 (0.22)	45.86 (0.15)	43.82 (0.06)	46.22 (0.16)	61.96 (0.27)	53.28 (0.06)
	PAML-I	62.87 (0.86)	69.17 (1.14)	65.86 (0.83)	64.53 (0.55)	66.23 (0.50)	21.88 (0.42)	17.96 (0.48)
	FFLT	64.35 (0.77)	70.97 (0.81)	67.49 (0.61)	65.89 (0.59)	67.43 (0.58)	21.15 (0.41)	17.31 (0.43)
	OKS-OMC	64.45 (0.76)	69.68 (0.82)	66.96 (0.50)	65.35 (0.61)	67.03 (0.52)	21.11 (0.38)	17.09 (0.53)

Table 3: Online performance metrics [%] and standard derivation (in brackets) achieved by all compared algorithms on the first six datasets.

Dataset	Algorithm	Psn ( $\uparrow$ )	Rcal ( $\uparrow$ )	F1 ( $\uparrow$ )	MacroF1 ( $\uparrow$ )	MicroF1 ( $\uparrow$ )	Hl ( $\downarrow$ )	Rl ( $\downarrow$ )
Scene (D = 16d)	OSML-ELM	59.08 (0.55)	59.49 (0.64)	59.28 (0.57)	67.52 (0.52)	66.85 (0.50)	10.35 (0.14)	9.77 (0.25)
	ELM-OMLL	63.52 (0.53)	73.81 (0.79)	68.28 (0.60)	68.78 (0.45)	67.21 (0.44)	12.69 (0.18)	11.67 (0.30)
	ELM-O	18.10 (0.00)	91.93 (0.25)	30.24 (0.02)	30.06 (0.03)	30.21 (0.02)	76.17 (0.17)	49.96 (0.08)
	PAML-I	67.76 (0.49)	68.52 (0.55)	68.13 (0.51)	74.08 (0.41)	73.30 (0.41)	8.75 (0.13)	7.36 (0.17)
	FFLT	72.23 (0.46)	79.92 (0.40)	75.88 (0.40)	76.46 (0.37)	74.89 (0.36)	9.42 (0.14)	7.08 (0.17)
	OKS-OMC	71.60 (0.49)	79.74 (0.41)	75.45 (0.38)	76.08 (0.35)	74.51 (0.36)	9.59 (0.16)	6.92 (0.18)

Table 4: Online performance metrics [%] and standard derivation (in brackets) achieved by all compared algorithms on the last five datasets.

Statistics	Psn	Rcal	F1	MacroF1	MicroF1	Hl	Rl
$R^{+}$	36	65	64	65	62	32	17.5
$R^{-}$	30	1	2	1	4	34	48.5
min{ $R^{+},R^{-}$ }	30	1	2	1	4	32	17.5

Table 5: Rank statistics of Wilcoxon signed-rank tests on all evaluation metrics.

Algorithm	Psn	Rcal	F1	MacroF1	MicroF1	Hl	Rl	Rank
OSML-ELM	4.64	6.45	5.91	5.91	5.45	3.00	4.91	5.18
ELM-OMLL	5.27	3.27	3.91	3.45	4.91	5.73	5.73	4.61
ELM-O	6.73	4.27	6.73	7.00	6.73	7.00	6.73	6.45
PAML-I	4.36	5.27	5.00	4.09	4.91	3.32	4.18	4.45
FFLT	3.09	2.73	2.45	2.45	2.27	3.64	3.18	2.83
OKS-OMC	2.36	3.45	2.82	3.27	2.64	3.00	1.64	2.74

Table 6: Average ranks per metric and overall ranks over all metrics.

Algorithm	Psn	Rcal	F1	MacroF1	MicroF1	Hl	Rl
FFLT	2.636	1.818	2.182	1.909	2.273	2.455	2.818
OKS-OMC	2.091	2.545	2.636	2.727	2.636	2.091	1.545
OMKC	1.273	1.636	1.182	1.364	1.091	1.455	1.636
$F_{F}$ statistic	8.906	3.011	12.407	8.906	18.810	3.444	10.167

Table 7: The average ranks of FFLT, OKS-OMC and OMKC and the Friedman statistic

F_{F}

in terms of each metric.

Panel of Figure 2 — Figure 2: Statistical comparison of OMKC with two baseline methods using the Bonferroni–Dunn test.

Panel of Figure 3 — Figure 3: Evolution of online performance metrics of OMKC as the fixed threshold $\gamma$ varies within the interval $[-10,10]$ .

Multi-Label Classification

Multi-label classification assigns several potentially related tags to each example, from medical findings and topics to objects and user interests.

See all 137 papers

Oct 11, 2026

ProML: Progressive Multi-label Learning

Multi-label learning typically pursues model construction through the joint optimization of label fitting, correlation modeling, and structural regularization. While empirically effective, such a coupled paradigm imposes multiple learning objectives on a single predictive parameter matrix, forcing it to simultaneously fit observed labels and encode structural priors. This coupling may induce ill-conditioned optimization geometry, increase hyper-parameter sensitivity, and complicate capacity control. To address the these issues, this paper proposes a Progressive Multi-Label Learning (ProML) framework, which decouples direct label fitting from predictor learning via the introduction of an auxiliary predictive variable. This auxiliary variable admits a closed-form solution, yielding an equivalent profiled objective in which the supervised fitting term is scaled by a trade-off parameter. This result provides a unified view of ProML and conventional coupled learning, with the latter recovered as a limiting case. We theoretically analyze the optimization geometry of ProML and show that, under quadratic positive semidefinite structural regularization, ProML attenuates the dominant curvature of the fitting term, enlarges the stable learning rate range, and provides a controllable fidelity-regularization trade-off. Further, we instantiate the ProML for multi-label feature selection task by integrating global-local label priors and row-sparse regularization. Extensive experiments and controlled optimization analyses on 12 benchmark datasets empirically corroborate the theoretical analysis and demonstrate the robust and competitive performance of the proposed method.

Yi Kou, Jieting Wang, Yuhua Qian

Institute of Big Data Science and Industry, the School of Artificial Intelligence, and the Key Laboratory of Evolutionary Science Intelligence of Shanxi Province, Shanxi University, Taiyuan 030006, Shanxi, China

Multi-Label Classification

Ask PDF

May 27, 2026

Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

Many real-world classification tasks require predicting multiple labels per instance, necessitating the optimization of complex evaluation metrics such as the

F

-measure and Jaccard index. While the Empirical Utility Maximization (EUM) framework is natural for these population-level metrics, existing theoretical results are largely limited to asymptotic Bayes-consistency. In this paper, we develop principled learning algorithms for optimizing a broad class of generalized metrics within the EUM framework, grounded in the stronger notion of

H

-consistency. Our key contribution is the design of novel surrogate loss functions for multi-label learning that admit provable

H

-consistency bounds, enabling optimization with non-asymptotic guarantees tailored to the hypothesis class and finite samples. Crucially, we prove these combinatorially formulated surrogates decompose exactly, operating in strictly

O(l)

time without approximations. Building on this foundation, we introduce MMO (Multi-Label Metric Optimization), a new family of algorithms for optimizing generalized linear-fractional metrics. We validate our approach through extensive experiments, demonstrating robust scalability and superior performance over state-of-the-art continuous baselines on large-scale datasets (MS-COCO, Reuters-21578) in high-sparsity, deep learning regimes. Our results offer both theoretical rigor and practical effectiveness for general multi-label metric optimization.

Mehryar Mohri, Yutao Zhong

Google Research & CIMS · New York, NY 10011 · Google Research

Multi-Label Classification Statistical Learning Theory

Ask PDF

Aug 31, 2026

Knowing Beyond the Known: Reinforced Knowledge Specification for Multi-Label Class-Incremental Learning

Existing class-incremental learning methods struggle in multi-label scenarios (MLCIL) due to the inherent contradiction of learning objectives arising from co-occurring and incomplete labels. We argue that the core obstacle is the model's ambiguous boundary between known and unknown knowledge, which undermines historical knowledge retention, complicates current task learning, and limits adaptability to future concepts. To address this, we propose KBK (Knowing Beyond the Known), a reinforced knowledge specification framework that explicitly models what is known or not to unify historical, current, and prospective learning. Specifically, to clarify known knowledge, we develop a hierarchical feature purification module that disentangles fine-grained class-specific features from global features, where high-level semantic abstraction is reinforced with low-level visual features. Additionally, an uncertainty-aware recall enhancement strategy suppresses unreliable predictions based on distribution priors, improving the quality of historical recall. For probing the unknown, KBK leverages semantic correlations to synthesize informative unknown features under co-occurring, preserving embedding space for future learning. Furthermore, to mitigate heterogeneous forgetting, we design a category-balanced gradient compensation loss that dynamically reweights gradient backpropagation according to forgetting speeds. Experiments on multiple benchmarks validate the effectiveness and robustness of KBK, which surpasses prior best methods by 2.7% in Avg. Acc on MS-COCO B0-C10 setting even without any replay buffers.

Aoting Zhang, Dongbao Yang, Chang Liu +3

Institute of Information Engineering, Chinese Academy of2026 Sciences, Beijing, 100085, China · School of Cyber Security, University of Chinese Academy ofAug Sciences, Beijing, 101408, China · Nankai University, Tianjin, 300350, China +1

Class-Incremental Learning Multi-Label Classification Incremental Learning

Ask PDF

Abstract

Multi-Label Classification

Explore similar work

ProML: Progressive Multi-label Learning

Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

Knowing Beyond the Known: Reinforced Knowledge Specification for Multi-Label Class-Incremental Learning