  Existing online multi-label classification works cannot well handle the
online label thresholding problem and lack the regret analysis for their online
algorithms. This paper proposes a novel framework of adaptive label
thresholding algorithms for online multi-label classification, with the aim to
overcome the drawbacks of existing methods. The key feature of our framework is
that both scoring and thresholding models are included as important components
of the online multi-label classifier and are incorporated into one online
optimization problem. Further, in order to establish the relationship between
scoring and thresholding models, a novel multi-label classification loss
function is derived, which measures to what an extent the multi-label
classifier can distinguish between relevant labels and irrelevant ones for an
incoming instance. Based on this new framework and loss function, we present a
first-order linear algorithm and a second-order one, which both enjoy closed
form update, but rely on different techniques for updating the multi-label
classifier. Both algorithms are proved to achieve a sub-linear regret. Using
Mercer kernels, our first-order algorithm has been extended to deal with
nonlinear multi-label prediction tasks. Experiments show the advantage of our
linear and nonlinear algorithms, in terms of various multi-label performance
metrics.
