© Wuhan University 2023

0 Introduction

The multi-label classification problem is an emerging machine learning paradigm ^[1]. A single sample could be related to several classes simultaneously, and the class labels are no longer mutually exclusive. Nowadays, there are lots of real-world applications, such as text categorization, automatic scene classification, gene function prediction, and music emotions annotation ^[2]. In recent years, with in-depth research on multi-label classification problems, many multi-label classification methods have been proposed. Most authors agree with the taxonomy that differentiates between two main approaches in solving multi-label classification problems: problem transformation methods and algorithm adaptation methods ^[2]. Despite being studied extensively, most existing studies of multi-label classification are restricted to batch learning, which requires that the whole training dataset is read into memory and processed for the decision model at once. However, these batch learning methods, especially for classifying large-scale datasets, will consume a significant amount of time and space resources.

Online learning algorithms represent a family of quick and simple machine learning techniques, which generally make few statistical assumptions about the datasets and are often used for classification problems. As discussed in this thesis, it is to update the model on each round without retraining. In general, online learning aims to incrementally learn some prediction models to make correct predictions on a stream of examples that arrive sequentially. Online learning is advantageous for its high efficiency and scalability for large-scale applications. It has been applied to solve online classification tasks in various real-world data mining applications. In the machine learning community, online learning has been actively studied, and various online learning algorithms have been proposed, including first-order and second-order online learning algorithms ^[3]. For example, the classical and popular first-order algorithms include perceptron ^[4] and passive-aggressive (PA) ^[5]. Examples of second-order online learning algorithms include adaptive regularization of weights (AROW) ^[6] and soft confidence-weighted (SCW) ^[7]. These methods can be explored to guide and enhance algorithm classification performance. Most aforementioned online algorithms, however, are online single-label algorithms. Aiming at these issues, we use online learning for large-scale learning tasks in multi-label classification problems.

In traditional online learning classification, a learner is trained sequentially to predict the class labels of a sequence of samples as precisely as possible ^[8-10]. In this paper, we propose a multi-label online learning algorithm by maximizing the margin between the relevant and irrelevant labels in multi-label samples: learning label correlations for multi-label online passive-aggressive classification algorithm (MLRPA), which builds a sorted error set by predicting the pairs of labels and then updates its classifier model according to the size of error set. The experiment compares the MLRPA algorithm with four other algorithms on four multi-label datasets, according to four popular and indicative performance measures. The experimental results show that the MLRPA algorithm has good performance.

1 Related Work

1.1 Online Learning

Online learning reduces computation costs by incrementally updating classifiers in which new training samples are taken into account instead of training the classifier again from the beginning on the combined training samples. Online learning has been actively studied in the machine learning community, in which various online learning algorithms have been presented, including several first-order and second-order algorithms. One of the most well-known first-order online approaches is the perceptron algorithm, which updates the learning function by adding the misclassified example with a previous weight to update the current weight vectors. Recently, a number of online learning algorithms have been developed based on the criterion of maximum margin. One representative example is the PA algorithm. It updates the classification function when a new sample is misclassified, or its classification score does not exceed the predefined margin. Empirical studies showed that the maximum margin-based online learning algorithms are generally more effective than the perceptron algorithm. Recent years have seen a surge of studies on second-order online learning algorithms, which have shown that parameter confidence information can be explored to guide and improve online learning performance ^[3].

Multi-label classification problem has always been an emerging machine learning paradigm. Because of many real-world applications, a few online multi-label classification methods have recently been studied ^[11]. For example, Ref.[12] proposed an extreme learning machine-based online universal classifier that is independent of classification type and can perform all three types of classification. Moreover, cost-sensitive dynamic principal projection (CS-DPP) ^[13] resolves three important real-world issues: online updating, label space dimension reduction (LSDR), and cost sensitivity. Based on binary relevance, Refs.[14,15] presented online multi-label algorithms in which the dataset is divided into many single-label datasets to solve the multi-label classification problem. The online multi-label semi-supervised (OMLSS) ^[16] introduced non-local labeling functions taking into account the topology of the network in the prediction of a label and improving the influence of the labeling strategy on the topology of the network in the multi-label case, using the labels to improve the synaptic links.

1.2 Label Correlations

To cope with the challenge of exponential-sized output space, it is essential to facilitate the learning process by exploiting correlations among labels ^[17]. Therefore, effectively exploiting the label correlation information is deemed crucial for the success of multi-label learning techniques ^[18]. According to the different ways and degrees of label correlation, the existing multi-label classification methods can be roughly divided into three categories. First-order strategy: the task of multi-label learning is tackled in a label-by-label style, thus ignoring the co-existence of the other labels. The prominent merit of the first-order approach lies in its conceptual simplicity and high efficiency. Typical first-order strategy algorithms include Binary Relevance (BR) ^[19] and multi-label k-nearest neighbor (ML-KNN) ^[20]. However, the effectiveness of the resulting approaches has low generalization performance due to the ignorance of label correlations. Second-order strategy: the task of multi-label learning is tackled by considering pairwise relations between labels. As label correlations are exploited to some extent by the second-order approach, the resulting methods can obtain good generalization performance. The most representative algorithm is RankSVM( Rank Support Vector Machine) ^[21]. High-order strategy: the task of multi-label learning is tackled by considering high-order relations among labels, such as imposing all other label's influences on each label ^[22]. However, dealing with large-scale learning problems is difficult because of the high computational complexity ^[23]. Traditional multi-label online methods often need to request all class labels of each incoming sample. The correlations among labels are not considered in the multi-label online classification problem. We propose a multi-label online classification algorithm based on label correlations to compensate for this shortcoming.

2 Proposed Method

In the multi-label classification problem, a single instance could be related to several classes simultaneously, and the class labels are no longer mutually exclusive. For concreteness, we assume that there are q different possible labels and denote the set of all possible labels by Q={1,2,…,q}. At each step t, the set of relevant labels Y_t of instance ${\mathit{x}}_t$ is therefore a subset of Y. We can say that label y is relevant to the sample ${\mathit{x}}_t$, if $y\in Y_t$. Otherwise, the set of irrelevant labels ${\overline{Y}}_t$ is a subset of Y. This setting is often discussed in text categorization applications. As we all know, the learning paradigm and the analysis that we use in this paper belong to the mistake-bound model for online learning. The interval between sample labels in multi-label sorting is defined as follows:

$\underset{r\in y}{\mathrm{m}\mathrm{i}\mathrm{n}}\{{\mathit{w}}_r\cdot \mathit{x}\}-\underset{s\notin y}{\mathrm{m}\mathrm{a}\mathrm{x}}\{{\mathit{w}}_s\cdot \mathit{x}\}$(1)

On round t, an online learning algorithm receives an instance ${\mathit{x}}_t$. Given the instance ${\mathit{x}}_t$, the learning algorithm outputs a ranking $R_t=\left(\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left({\mathit{x}}_t,\mathrm{1}\right),\cdots ,\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left({\mathit{x}}_t,q\right)\right)$, where $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left({\mathit{x}}_t,\mathrm{1}\right)$ is induced by ${\mathit{w}}_{\mathrm{1}}·{\mathit{x}}_t$. The algorithm then receives the (correct) set of relevant labels $y_t$. Given the feedback $y_t$ and the predicted topic ranking $R_t$, the algorithm computes the associated loss ${\mathcal{l}}_t=\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left(y_t,R_t\right)$. If ${\mathcal{l}}_t$ is zero, the algorithm does not modify the model. Otherwise, it updates its label-ranking rule by modifying the set of weights ${\mathit{w}}_{\mathrm{1}},\cdots ,{\mathit{w}}_q$. The goal of the online label-ranking algorithm is to suffer a cumulative loss ${\mathcal{l}}_t$ that is competitive with a zero cumulative loss. The MLRPA algorithm we describe employs a refined notion of a mistake by examining all pairs of labels. The goal of this method is that the margin of an instance is positive, which means that all the sets of relevant labels are ranked higher than the non-relevant labels. Therefore, we define the multi-label loss function:

$\mathcal{l}\left(\mathit{w};\left({\mathit{x}}_t,y_t\right)\right)=\{\begin{array}{l}\mathrm{0},\\ \mathrm{1}-〈{\mathit{w}}_r-{\mathit{w}}_s,{\mathit{x}}_t〉,\end{array}\begin{array}{c}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\\ 〈{\mathit{w}}_r-{\mathit{w}}_s,{\mathit{x}}_t〉\le \mathrm{1}\end{array}$(2)

where w represents the weight vector of the instance. r and s denote the number of prediction errors in the relevant and irrelevant labels of instance x, respectively. $〈\cdot 〉$ represents the interval function between all relevant and irrelevant labels. It can be seen from the above loss that the sum of each pair of labels is calculated for the case where the ranking of irrelevant labels in the sample is higher than the relevant label. The classification performance of the algorithm model can be improved by fully considering the correlation among the labels.

To improve the classification performance of the algorithm, we add slack variables to the objective function. The MLRPA algorithm optimization model is as follows:

$\begin{array}{l}{\mathit{w}}_{t+\mathrm{1}}=\underset{\mathit{w},j=\mathrm{1},\cdots ,q}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}{\displaystyle \sum _{j=\mathrm{1}}^q}{\Vert \mathit{w}-{\mathit{w}}_t\Vert }^{\mathrm{2}}+C{\displaystyle \sum _{i=\mathrm{1}}^N}\frac{\mathrm{1}}{\left|Y_i\right|\left|\overline{Y_i}\right|}\sum _{(r,s)\in Y_i\times {\overline{Y}}_i}{\xi }_{irs}\\ \mathrm{s}.\mathrm{t}.\mathrm{1}-〈{\mathit{w}}_r-{\mathit{w}}_s\cdot {\mathit{x}}_t〉\ge {\xi }_{irs}\mathrm{a}\mathrm{n}\mathrm{d}{\xi }_{irs}\ge \mathrm{0}\end{array}$(3)

where ${\xi }_{irs}$ is the slack variables and C > 0,$\mathrm{1}\le i\le N$. When the loss of function ${\mathcal{l}}_t=\mathrm{0}$, the algorithm does not update the weight value. When ${\mathcal{l}}_t>\mathrm{0}$, similar to the multi-class PA algorithm, the above optimization model is divided into two parts to meet the Lagrange function:

$\begin{array}{l}L({\mathit{w}}^r,\tau ,\xi ,\lambda )=\frac{\mathrm{1}}{\mathrm{2}}{\Vert {\mathit{w}}^r-{\mathit{w}}_t^r\Vert }^{\mathrm{2}}+C{\displaystyle \sum _{i=\mathrm{1}}^N}\frac{\mathrm{1}}{\left|Y_i\right|\left|\overline{Y_i}\right|}\sum _{(r,s)\in Y_i\times {\overline{Y}}_i}{\xi }_{ir}\\ +({\displaystyle \sum _{i=\mathrm{1}}^N}\sum _{(r,s)\in Y_i\times \overline{Y}}{\tau }_{irs}({\mathit{w}}_t^r\cdot {\mathit{x}}_t-{\mathit{w}}_t^s\cdot {\mathit{x}}_t)-\mathrm{1}+{\xi }_{ir})\end{array}$

$+{\displaystyle \sum _{i=\mathrm{1}}^N}\sum _{(r,s)\in Y_i\times {\overline{Y}}_i}{\lambda }_{irs}\left({\xi }_{irs}-{\eta }_{irs}\right)$(4)

and

$\begin{array}{l}L({\mathit{w}}^s,\tau ,\xi ,\lambda )=\frac{\mathrm{1}}{\mathrm{2}}{\Vert {\mathit{w}}^s-{\mathit{w}}_t^s\Vert }^{\mathrm{2}}+C{\displaystyle \sum _{i=\mathrm{1}}^N}\frac{\mathrm{1}}{\left|Y_i\right|\left|\overline{Y_i}\right|}\sum _{(r,s)\in Y_i\times {\overline{Y}}_i}{\xi }_{rs}\\ +({\displaystyle \sum _{i=\mathrm{1}}^N}\sum _{(r,s)\in Y_i\times \overline{Y}}{\tau }_{irs}({\mathit{w}}_t^r\cdot {\mathit{x}}_t-{\mathit{w}}_t^s\cdot {\mathit{x}}_t)-\mathrm{1}+{\xi }_{irs})\\ +{\displaystyle \sum _{i=\mathrm{1}}^N}\sum _{(r,s)\in Y_i\times {\overline{Y}}_i}{\lambda }_{irs}\left({\xi }_{irs}-{\eta }_{irs}\right)\end{array}$(5)

where $\lambda \ge \mathrm{0}$ and $\tau$ ≥ 0 are Lagrange multipliers. $\eta \left(\eta \ge \mathrm{0}\right)$ is slack variables. At time t, taking the derivative of the above formula (4) and (5) concerning ${\mathit{w}}^r$ and ${\mathit{w}}^s$, we get

$\frac{\partial L}{\partial {\mathit{w}}^r}=\mathrm{0}\Rightarrow {\mathit{w}}_{t+\mathrm{1}}^r={\mathit{w}}_t^r+m_{t,r}{\tau }_t^{irs}{\mathit{x}}_t$(6)

and

$\frac{\partial L}{\partial {\mathit{w}}^s}=\mathrm{0}\Rightarrow {\mathit{w}}_{t+\mathrm{1}}^s={\mathit{w}}_t^s+m_{t,r}{\tau }_t^{irs}{\mathit{x}}_t$(7)

where $m_{t,r}\ge \mathrm{0}$ indicates the sum of squares of the number of pairs of labels predicted to be unordered.

$m_{t,r}{\tau }_t^{irs}={\displaystyle \sum _{i=\mathrm{1}}^N}\sum _{(r,s)\in Y_i\times {\overline{Y}}_i}{\tau }_t^{irs}$(8)

Taking the derivative of L (·) with respect to ξ and setting it to zero, we get

$\frac{\partial L}{\partial {\xi }_{rs}}=\mathrm{0}\Rightarrow \frac{C}{\left|Y_i\right|\left|\overline{Y_i}\right|}-{\tau }_t^{irs}-{\lambda }_t^{irs}=\mathrm{0}\Rightarrow \frac{C}{\left|Y_i\right|\left|\overline{Y_i}\right|}={\tau }_t^{irs}+{\lambda }_t^{irs}$(9)

the Karush-Kuhn-Tucker (KKT) conditions confine λ to be non-negative, so we conclude that

$\{\begin{array}{l}\frac{C}{\left|Y_i\right|\left|\overline{Y_i}\right|}={\tau }_t^{rs}+{\lambda }_t^{rs}\\ \lambda \ge \mathrm{0}\end{array}\Rightarrow \frac{C}{\left|Y_i\right|\left|\overline{Y_i}\right|}\ge {\tau }_t^{rs}$(10)

Finally, taking the derivative of L(·) with respect to $\tau$ and setting it to zero, we get

$\frac{\partial L}{\partial {\tau }_t^{irs}}=\mathrm{0}$(11)

Plugging the Eq. (9) back into Eq.(4).

$\{\begin{array}{l}{\tau }_t^{irs}\le \frac{C}{\left|Y_i\right|\left|\overline{Y_i}\right|}\\ \frac{\mathrm{1}}{\mathrm{2}}({\tau }_t^{irs}{)}^{\mathrm{2}}{m}_{t,r}{\Vert \mathit{x}\Vert }^{\mathrm{2}}+{\displaystyle \sum _{r\in y_t}^{}}{\displaystyle \sum _{s\notin y_t}^{}}{\tau }_t^{irs}(({\mathit{w}}_t^r\cdot {\mathit{x}}_t-{\mathit{w}}_t^s\cdot {\mathit{x}}_t)-\mathrm{1})=\mathrm{0}\end{array}$(12)

Simplifying the above formula, we get

${\tau }_t^{irs}=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\frac{C}{\left|Y_i\right|\left|{\overline{Y}}_i\right|},\frac{{\mathcal{l}}_t}{m_{t,r}{\Vert {\mathit{x}}_t\Vert }^{\mathrm{2}}}\right\}$(13)

Finally, we summarize the proposed method in the following Algorithm 1. In Algorithm 1, the classifier weights matrix and parameters are initialized. At time t, the classifier accepts a sample and then predicts the relevant and irrelevant labels of the sample. Then, the MLRPA algorithm calculates the loss function based on the obtained real and predicted labels. Finally, the MLRPA algorithm updates the weight of the classifier according to whether the loss function is greater than zero.

Algorithm 1 MLRPA learning algorithm

Input: Set the key parameters: C = 1. 1: Initialize weight matrix W. 2: fort = 1,…, Tdo 3:   Receives an incoming sample ${\mathit{x}}_t$ 4:   Calculate the learner Wt ·${\mathit{x}}_t$ 5:   Get the real relevant labels $y_t$ and irrelevant labels ${\widehat{y}}_t$ 6:    The loss ${\mathcal{l}}_t$ is calculated according to Eq. (2) 7:   if${\mathcal{l}}_t$ > 0 then 8:    for$k=1,\cdots ,q$do 9:        According to Eq. (6) and Eq. (7), update weight          vector 10:    end for 12:   end if 13: end for

3 Experiments

3.1 Four Datasets and Four Existing Methods

We use four benchmark datasets: Corel5K(image), Corel16k001(image), Delicious(text), and Tmc2007(text) to validate our proposed method. Some valuable statistics of these datasets are provided in Table 1. In this study, we select three different multi-label online classification algorithms: perceptron algorithm based on multi class and multi label feedback (MMP) ^[24], BR-PA, and BR-perceptron (BR-PE), and a multi-label offline classification algorithm: ML-KNN. The MMP algorithm is based on a perceptron-based multi-label online classification algorithm, which considers label correlations. The BR-PA algorithm and BR-PE algorithm are based on the problem decomposition strategy of the multi-label online classification algorithm. The BR-PA algorithm transforms the multi-label classification problem into two types of online PA algorithm, and the BR-PE algorithm is similar to the BR-PA algorithm, which transforms the multi-label classification problem into a binary online perceptron algorithm. The ML-KNN is derived from the traditional k-Nearest Neighbor (KNN) algorithm. For each unseen instance, its k nearest neighbors in the training set are first identified. After that, based on statistical information gained from the label sets of these neighboring instances.

In BR-PA and our MLRPA, two parameters are set as C = 1. For the ML-KNN algorithm, the smoothing factor s = 1 and the nearest neighbor k = 10. In order to ensure that the datasets are realistic, we randomize the dataset. In the experiment, we use online learning in the training dataset and offline in the test dataset. All the experiments were executed with about 10 runs of different random permutations for each dataset. All the results were reported by averaging over these 10 runs.

3.2 Performance Comparison

First, we have selected four large-scale multi-label datasets on four online algorithms in training datasets, where Fig. 1 and Fig. 2 show the average precision and one error values. Figure 1 shows the average precision of the four different algorithms for multi-label online learning. We observe that with the increase of the training sample set, the average precision of the four different online classification algorithms also increases. The MLRPA algorithm proposed in this paper has an average precision value better than other algorithms. In addition, on the image datasets (Corel16k001), the performance of the online algorithm considering label correlation is better than the algorithm based on the decomposition strategy. Figure 2 summarizes the one error performance of the four diverse algorithms. With the increase of the training sample set, the proposed MLRPA algorithm has fewer errors than other algorithms. The performance is more prominent, especially in the image dataset (Corel16k001). Experimental results show that the MLRPA algorithm based on label correlation significantly outperforms the online algorithm based on problem decomposition when dealing with multi-label online classification. MLRPA algorithm is also more suitable for dealing with large-scale dataset classification problems.

Fig. 1 The average precision analysis of four algorithms on four datasets

Fig. 2 The one error analysis of four algorithms on four datasets

To further evaluate the online MLRPA algorithm, we compare the MLRPA algorithm with online and offline algorithms for classification performance in test datasets. Tables 2-5 show detailed metrics of four different algorithms for multi-label online learning on four testing datasets in an offline learning way. The experiment results are listed in Tables 2-5 according to four criteria mentioned in this paper, where the optimal value of each dataset among four methods is highlighted in boldface. To compare these methods, we sort four methods on a single metric with 1-5 and calculate the average rank of each method over all four datasets, as listed in the last rows of Tables 2-5.

The results in Table 2 to Table 5 show that our proposed MLRPA algorithm achieves good classification performance for all datasets under four different evaluation criteria. Table 2 shows one error value on four datasets. The MLRPA works the best on four datasets. From the ranking loss in Table 3, the MLRPA performs the best on four datasets and achieves the first rank. In Table 4 for average precision, the four best values are from our MLRPA. At the same time, the MLRPA obtains the best rank. According to Table 5, the MLRPA works the best on all datasets and receives the best rank. In addition, we observe that our MLRPA outperforms the ML-KNN and MMP on all datasets. The experimental results also show that the MLRPA algorithm based on label correlation is more suitable for large-scale multi-label classification problems.

4 Conclusion

This paper investigated multi-label online learning techniques for machine learning and mining data streams. By maximizing the margin between the relevant and irrelevant labels in multi-label samples, we proposed a new algorithm for multi-label classification, which considers the label correlations. The experimental results on four datasets illustrate that our proposed method works better than three existing methods, including a simple MMP ranking algorithm and two multi-label online approaches, according to four widely-used evaluation metrics. For further work, we will validate the effectiveness of our method on more datasets and take online second-order algorithms into account in multi-label classification problems..

References

All Tables

All Figures

	Fig. 1 The average precision analysis of four algorithms on four datasets
In the text

	Fig. 2 The one error analysis of four algorithms on four datasets
In the text