Online kernel selection for online multi-label classification.

Abstract

Online kernel methods have proven effective in addressing large-scale nonlinear classification tasks. However, numerous existing approaches are designed for single-label tasks. Compared to single-label classification, multi-label classification presents distinct challenges and assumptions and is vital for a variety of applications. Currently, only a few online kernel methods are available for multi-label classification and they typically rely on an offline kernel selection process to determine a suitable kernel. Given that the global data structure is unknown in advance in an online setting, this selection process may lead to suboptimal kernel choices, ultimately reducing online performance. This paper introduces a novel online multi-label classification approach that seamlessly integrates kernel selection and model learning within a unified online framework. Initially, a joint optimization problem involving multi-label kernel classifiers and their combination coefficients is formulated. To address the computational challenges posed by the non-convexity of this problem, a reasonable approximation of the original problem is proposed. This approximation enables us to decompose the problem into two sub-problems that can be efficiently solved incrementally, while allowing to derive a meaningful regret bound. On average, this method matches the performance of the best fixed single-kernel multi-label model, chosen after observing all examples and evaluating each kernel in the predefined set. Extensive experiments on 11 datasets demonstrate that our method outperforms existing state-of-the-art methods in terms of overall online performance. The source code of our method can be found at https://github.com/LUCKY-ting/OKS-OMC.