Fast multi-label SVM training based on approximate extreme points

Abstract

Under the framework of multi-label classification, the excessive training time restricts the availability of non-linear kernel SVM (Support Vector Machine) classification algorithm on large-scale data sets. To solve this problem, this paper provides a fast multi-label SVM classification algorithm based on approximate extreme points (AEMLSVM). Firstly, it utilizes the approximate extreme point technique to obtain representative sets from the training data set. These representative sets not only retain almost all information of the training data set, but also its size is much smaller than that of training data set. After that, SVM is trained on the representative sets. Furthermore, the improved AEMLSVM algorithm (AEMLSVM-DEC) adopts DEC (Different Error Costs) technique to solve the label data imbalanced problem. We have conducted extensive experiments on four large-scale benchmark data sets. The results show that the proposed algorithms can effectively reduce training time, and their classification performance is similar to that of the traditional multi-label SVM algorithm. They outperform other scalable multi-label SVM algorithms in training time and classification performance. By adopting DEC method to solve the label data imbalanced problem, the AEMLSVM-DEC algorithm has a better classification performance than AEMLSVM algorithm.

Keywords

Support vector machine approximate extreme points multi-label classification label data imbalanced problem

1. Introduction

Multi-label classification is an important research hotspot in the field of machine learning and data mining, in which each instance can have one or more labels simultaneously associated [7]. Specifically speaking, in the multi-label classification framework, assume $\bm{X}\in\mathbb{R}^{d}$ represents a $d$ -dimensional input space, and $L=\{l_{1},\cdots,l_{k}\}$ represents the label space with $k$ possible labels. The task of multi-label classification is to learn a classifier $f:\bm{X}\rightarrow 2^{L}$ from the multi-label training data set $S=\{(\bm{x_{i}},Y_{i})\mid 1\leqslant i\leqslant N\}$ . For each multi-label training instance $(\bm{x_{i}},Y_{i})$ , $\bm{x_{i}}\in\bm{X}$ is a $d$ -dimensional feature vector and $Y_{i}\subseteq L$ is the label set of $\bm{x_{i}}$ . For any unseen testing instance $\bm{x}\in\bm{X}$ , the multi-label classifier $f(\cdot)$ predicts $f(\bm{x})\subseteq L$ as the proper label set for $\bm{x}$ . Until now, many algorithms have been proposed to deal with multi-label classification problem, for instance, algorithms based on SVM, K-nearest neighbor (KNN), neural network and decision tree [5]. These algorithms have been widely-used in music emotion categorization [14], bioinformatics prediction [13], automatic image and video annotation [18], text categorization [6], etc. But many existing multi-label classification algorithms are not suitable for large-scale data sets. The main reason is the overlong training time which is especially serious in algorithms based on SVM.

Traditional SVM [4] is a popular classification algorithm which can only deal with binary or multi-class classification problem. But improved algorithms like Rank-SVM algorithm [2] can deal with multi-label classification problem. Because most multi-label data sets are not linearly separable, multi-label classification algorithms based on SVM need non-linear kernel functions to achieve better classification performance, which further limits their availability on large-scale data sets. Moreover, it is accepted that most multi-label data sets are label imbalanced data sets [17], which has a negative impact on the classification performance.

In this paper, we utilize the advantages of BR (binary relevance) problem transformation strategy and binary SVM based on approximate extreme points (AESVM) [20] to construct a new fast multi-label SVM classification algorithm called AEMLSVM. AEMLSVM classification algorithm combined with non-linear kernel can be applied on large-scale data sets. The improved AEMLSVM (AEMLSVM-DEC) classification algorithm adopts DEC method [15] to solve the label data imbalanced problem. AEMLSVM and AEMLSVM-DEC classification algorithms utilize the approximate extreme point method to extract representative sets from the training data set. The size of representative sets is much smaller than that of the training data set, while it preserves almost all information of the training data set. After that, SVM classification algorithm is trained on the extracted representative sets. Experiment results on four large-scale benchmark data sets demonstrate that AEMLSVM and AEMLSVM-DEC classification algorithms have the fastest training speed compared with other multi-label classification methods, i.e., ML-BVM [9], ML-CVM [10] and ML-LIBSVM [3]. At the same time, their classification performance is similar to that of ML-LIBSVM method on the five evaluation metrics and better than that of ML-BVM and ML-CVM methods. By adopting DEC method to solve the label data imbalanced issue, the AEMLSVM-DEC classification algorithm has a better classification performance than AEMLSVM classification algorithm. We note that a short version of this work has been appeared in the BIGCOM- 2016 Workshop on the Best Paper Candidates topic [31].

The other parts of this paper are shown as follows. Some related works are introduced in Section 2; the AEMLSVM and AEMLSVM-DEC classification algorithms proposed in this paper are given in Section 3; the experiment results are analyzed in Section 4; Section 5 concludes this paper.

2. Related work

In recent years, many algorithms [1, 2, 12, 13, 19] have been put forward and used to solve the multi-label classification problem. Meanwhile, lots of algorithms [32, 33, 34] have also been proposed to overcome the label data imbalanced problem since label imbalanced data sets are very universal. SVM has been a popular algorithm in solving binary or multi-class classification problem. In this chapter, several existing multi-label classification algorithms are introduced firstly. Secondly, popular methods are introduced for dealing with label data imbalanced problem. Finally, the binary SVM is presented.

2.1 Multi-label classification algorithms

Currently, problem transformation strategy and algorithm adaptation strategy are two basic strategies for dealing with multi-label classification problem. The problem transformation strategy firstly transforms the multi-label problem into one or more single-label problems. After that, each single-label problem is solved with a single-label classification algorithm. Problem transformation strategy mainly includes BR (Binary Relevance) or OVR (One-Versus-Rest) [35], LP (Label Powerset) [21] and so on. Existing single-label classification algorithms include SVM [3], CVM [10], BVM [9], neural network, decision tree and K-nearest neighbor (KNN) [5], etc. The algorithm adaptation strategy extends a single-label classification algorithm in order to directly deal with multi-label data set. By using the algorithm adaptation strategy, many classical multi-label classification algorithms such as C4.5-type algorithm [1], BP-MLL algorithm [19], ML-KNN algorithm [13], Rank-SVM algorithm [2] and Rank-CVM algorithm [12] have been put forward and widely used in many filed.

2.2 Methods for solving label data imbalanced problem

It is a widely accepted that most multi-label data sets are label imbalanced data sets [17]. And label data imbalanced issue affects the performance of classification algorithms [8]. To overcome label data imbalanced problem, lots of algorithms have been put forward and they are classified into three types [36]. The first type of method acts on the data level and they are based on resampling the training data set to make the classifier receive the same proportion of instances each label [34]. Re-sampling method includes over-sampling and under-sampling methods. The second type of method acts on the algorithm level and they deal with the label data imbalanced problem by modifying the learning algorithm [32]. They can adjust the decision threshold and make it bias towards the minority label or assign larger costs to compensate for the minority. This is the basic principle of cost-sensitive learning. The third type of method is based on ensemble in which the basic ensemble method is modified to account for the underrepresentation of minority label in the training data set [33].

2.3 Binary SVM

Assume a binary data set includes $N$ data vectors, $\bm{X}=\{\bm{x}_{i}:\bm{x}_{i}\in R^{D},i=1,2,\ldots,N\}$ , and the target labels $\bm{Y}=\{y_{i}:y_{i}\in\{-1,1\},i=1,2,\ldots,N\}$ . The formula of unconstrained optimization problem of binary SVM is as follows [27]:

$\displaystyle\mathop{\text{min}}\limits_{\bm{w},b}F_{1}(\bm{w},b)=\frac{1}{2}% \|\bm{w}\|^{2}+\frac{C}{N}\sum^{N}_{i=1}l(\bm{w},b,\Phi(\bm{x}_{i})),$ (1)

where $l(\bm{w},b,\Phi(\bm{x}_{i}))=\textit{max}\{0,1-y_{i}(\bm{w}^{T}\Phi(\bm{x}_{i}% )+b)\},\forall\bm{x}_{i}\in\bm{X}$ and $\Phi:R^{D}\longrightarrow H,b\in R$ , and $\bm{w}\in H$ , $H$ a Hilbert space.

It is worth noting that $l(\bm{w},b,\Phi(\bm{x}_{i}))$ is the hinge loss function of training instance $\bm{x}_{i}$ , $\|\bm{w}\|^{2}$ represents the model’s complexity [4]. Parameter $C$ is used to make a balance between the model’s complexity and the total loss for the training data set, $C$ divided by $N$ is a widely-used punishment parameter [28]. The scaling of $C$ with $N$ can be analyzed on these formulas [29]. The time complexity of SVM algorithm using non-linear kernels is quadratic in the scale of the training data set [26]. Although SVM has good classification performance for binary or multi-class classification problem, its training time is overlong when it is applied on large-scale data sets.

It can be concluded from above that although many algorithms have been put forward and used for multi-label classification, they are still restricted from being used on large-scale data sets and this problem is especially serious for those based on SVM. The AEMLSVM and AEMLSVM-DEC classification algorithms can resolve this problem effectively. They can greatly shorten the training time while achieve a comparable classification performance to that of the ML-LIBSVM method. In addition, the AEMLSVM-DEC classification algorithm also overcomes the label data imbalanced problem effectively by using the DEC method.

3. Fast multi-label support vector machine classification algorithm based on approximate extreme points

Firstly, we will introduce the binary relevance strategy. Secondly, we will introduce binary support vector machine based on approximate extreme points (AESVM). Thirdly, we will introduce the improved AESVM. Then, we will implement fast multi-label SVM classification algorithm based on approximate extreme points (AEMLSVM). In addition, the improved AEMLSVM (AEMLSVM-DEC) classification algorithm uses the DEC method to solve the label data imbalanced problem and this further improves the performance of the AEMLSVM classification algorithm. At last, the complexity of the AEMLSVM and AEMLSVM-DEC algorithms are analyzed.

3.1 Binary relevance strategy

We adopt the famous BR strategy to realize multi-label classification in this paper. Firstly, the BR strategy transforms the multi-label data set $S=\{(\bm{x_{1}},Y_{1}),\cdots,(\bm{x_{N}},Y_{N})\}$ into k independent binary subsets $S_{l_{j}}=\{(\bm{x_{1}},y_{1}),(\bm{x_{2}},y_{2}),\cdots,(\bm{x_{N}},y_{N})\}$ , $l_{j}\in L$ , $y_{N}\in\{-1,+1\}$ and $j=\{1,\cdots,k\}$ . The binary subset $S_{l_{j}}$ includes positive instances which are labeled with the label $l_{j}$ and negative instances which are labeled with other labels. Then a corresponding binary classifier $f_{l_{j}}(\bm{x})$ is constructed for the label $l_{j}$ on the binary subset $S_{l_{j}}$ . At last, the BR strategy constructs a binary classifier set $H_{BR}$ which consists of $k$ binary classifiers. The equation is as follows.

$\displaystyle H_{BR}=\{f_{l_{j}}(\bm{x})\rightarrow l^{\prime}_{j}\in\{-1,+1\}% |l_{j}\in L,j=1,\ldots,k\},$ (2)

where $\bm{x}$ denotes the unknown testing instance, $l^{\prime}_{j}$ represents the $f_{l_{j}}(\bm{x})$ ’s prediction result for $\bm{x}$ , if $l^{\prime}_{j}=+1$ , then $\bm{x}$ has the label $l_{j}$ , else $\bm{x}$ doesn’t have the label $l_{j}$ . The following decision function is used and shown in the Eq. (3).

$\displaystyle Y=\{l_{j},s.t.f_{l_{j}}(\bm{x})\geqslant 0,l_{j}\in L,j=1,\ldots% ,k\}.$ (3)

To avoid getting a null relevant label set, the following rule is used [21].

$\displaystyle Y=\{l_{j},s.t.\max f_{l_{j}}(\bm{x}),f_{l_{j}}(\bm{x})<0,l_{j}% \in L,j=1,\ldots,k\},$ (4)

where, if all $f_{l_{j}}(\bm{x})<0$ , $\bm{x}$ has the label $l_{j}$ for $\max f_{l_{j}}(\bm{x})$ . With Eqs (3) and (4), $k$ binary classifiers are assembled into the multi-label classifier in the proposed AEMLSVM and AEMLSVM-DEC classification algorithms.

The main reason for adopting the BR strategy is that it has many obvious advantages. Firstly, it can use any existing binary classifier as base classifier to realize multi-label classification. Secondly, its complexity is linearly dependent on the amount of labels. Thirdly, it can be parallelized easily. Lastly, it can optimize multiple loss functions [23].

3.2 Binary SVM based on approximate extreme points

Before introduce the binary SVM based on approximate extreme points, the principle of extreme points will be introduced firstly. The convex hull of set $\bm{S}$ is the smallest convex set containing $\bm{S}$ [25] and can be obtained by taking all possible convex combinations of elements of $\bm{S}$ . When set $\bm{S}$ is a finite set, its convex hull is a polygon. $\textit{EP}(\bm{S})$ denotes the extreme points of set $\bm{S}$ which can be defined as the vertices of the convex polygon. The convex hull of set $\bm{S}$ forms the convex polygon. In set $\bm{S}$ , each vector $\bm{s}_{i}$ can be replaced by a convex combination vectors in $\textit{EP}(\bm{S})$ .

$\displaystyle\bm{s}_{i}=\sum_{\bm{s}_{t}\in EP(\bm{S})}\delta_{i,t}\bm{s}_{t},$

(5) $\displaystyle\textit{where}\;0\leqslant\delta_{i,t}\leqslant 1,\ \text{and}\ % \sum_{\bm{s}_{t}\in EP(\bm{S})}\delta_{i,t}=1$

We can get from the formula that by adopting only $\textit{EP}(\bm{S})$ and $\delta_{i,t}$ , any data vector $\bm{s}_{i}$ in $\bm{S}$ can be obtained. $\delta_{i,t}$ represents the convex combination weights. Using extreme points method, $\bm{S}$ can be represented by a subset of $\bm{S}$ . Thus the size of training data set can be reduced. After that, on the reduced training set, we can get similar performance and high speed compared with the whole training set. However, the extreme points method is not effective in all cases, considering some kernels functions, in which every data vector is an extreme point. For instance, the Gaussian kernel, $K(\bm{x}_{i},\bm{x}_{i})=\phi(\bm{x}_{i})^{T}\phi(\bm{x}_{i})=1$ . This Gaussian kernel shows that each data vector appears on the surface of the unit ball, thus they are all extreme points.

Therefore, Nandan et al. [20] introduce the concept of approximate extreme points. Meanwhile, he proposes a binary SVM based on approximate extreme points (AESVM). It can reduce the training time effectively while guaranteeing the accuracy of classification. The formula of unconstrained optimization problem of binary AESVM is as follows [31]:

$\displaystyle\mathop{\text{min}}\limits_{\bm{w},b}F_{2}(\bm{w},b)=\frac{1}{2}% \|\bm{w}\|^{2}+\frac{C}{N}\sum^{M}_{t=1}\beta_{t}l(\bm{w},b,\Phi(\bm{x}_{t})),$ (6)

where $l(\bm{w},b,\Phi(\bm{x}_{t}))=\textit{max}\{0,1-y_{t}(\bm{w}^{T}\Phi(\bm{x}_{t}% )+b)\},\forall\bm{x}_{t}\in\bm{X}^{}$ and $\Phi:R^{D}\rightarrow H,b\in R$ and $\bm{w}\in H$ , $H$ a Hilbert space.

$M$ denotes the scale of $\bm{X}^{}$ , $\bm{X}^{*}$ is an optimal representative set of $\bm{X}$ . $\beta_{t}$ is associated with the approximate extreme point technique. It can be suggested reasonably that when the value of $\varepsilon$ is small, the solution of AESVM is similar to that of SVM. Meanwhile, based on the principle of approximate extreme points, Nandan et. al proposes the DeriveRS algorithm to extract the representative set effectively. Its time complexity is linear [20]. Consequently, we implement a fast multi-label SVM classification algorithm (AEMLSVM) by combining the BR strategy with binary SVM based on approximate extreme points. AEMLSVM classification algorithm using non-linear kernel can be used on large-scale data sets which will be introduced in 3.4.
3.3 Improvement of binary svm based on approximate extreme points

When the BR problem transformation strategy is used on large-scale data sets, it can result in severe label data imbalanced problem and this problem deteriorates with the increase of labels [30]. Figure 1 shows the ratio of the 20 commonest labels in each multi-label data set. The attributes of these multi-label data sets are presented in Table 1. Many labels are represented by less than 20% of the total instances and some of those not shown in Fig. 1. It is a fact that most of these multi-label data sets have more than 20 labels. In a word, label data imbalanced problem occurs more often in large-scale data sets. Meanwhile, Although binary AESVM classification algorithm has good classification performance, it cannot perform well when the data set is imbalanced. Hence, we will combine the DEC method with binary AESVM to solve this problem. The DEC method is introduced firstly.

Figure 1.

Ratio of the 20 commonest labels in each data set.

Binary SVM classification algorithm is sensitive to label data imbalanced problem because same misclassification cost are assigned to the positive and negative label misclassification problems in the penalty term of the soft margin objective function given in Eq. (1). This makes the separating hyperplane slope towards the minority label and leads to a suboptimal model. DEC method is proposed in [15] and it is a cost-sensitive learning technique to deal with the above problems in SVM. In the training of SVM, the soft margin objective function of SVM is modified by assigning different misclassification costs and shown in the following equation.

$\displaystyle\mathop{\text{min}}\limits_{\bm{w},b}F_{3}(\bm{w},b)=\frac{1}{2}% \|\bm{w}\|^{2}+\frac{C}{N}\left[C^{+}\sum^{N}_{i|y_{i}=+1}l(\bm{w},b,\Phi(\bm{% x}_{i}))+C^{-}\sum^{N}_{i|y_{i}=-1}l(\bm{w},b,\Phi(\bm{x}_{i}))\right],$ (7)

In Eq. (7), $C^{+}$ represents the misclassification cost for the positive instances and $C^{-}$ for the negative instances. It can be seen that when the misclassification cost assigned to the minority label instances is higher than that to the majority label instances, the negative influence of label data imbalanced issue is weakened and thus the classification performance of the improved SVM algorithm is enhanced. Although the binary SVM combined with DEC method can solve the label data imbalanced problem, it is severely restricted by the excessive training time when used on large-scale data sets.

To summarize, the advantages of DEC method and binary AESVM are fully used to reduce the training time effectively while guaranteeing the accuracy of classification. The following equation gives the optimization problem of the improved binary SVM based on approximate extreme points.

$\displaystyle\mathop{\text{min}}\limits_{\bm{w},b}F_{4}(\bm{w},b)=\frac{1}{2}% \|\bm{w}\|^{2}+\frac{C}{N}\left[C^{+}\sum^{M}_{t|y_{t}=+1}\beta_{t}l(\bm{w},b,% \Phi(\bm{x}_{t}))+C^{-}\sum^{M}_{t|y_{t}=-1}\beta_{t}l(\bm{w},b,\Phi(\bm{x}_{t% }))\right],$ (8)

In order to simplify the Eq. (8) and facilitate the implementation of the following algorithms, we convert the Eq. (8) as follows.

$\displaystyle\mathop{\text{min}}\limits_{\bm{w},b}F_{5}(\bm{w},b)=\frac{1}{2}% \|\bm{w}\|^{2}+\frac{C}{N}\sum^{M}_{t=1}\beta_{t}\tau_{t}l(\bm{w},b,\Phi(\bm{x% }_{t})),$ (9)

Parameter $\tau_{t}$ is the scaling coefficient to solve the label data imbalanced problem.

$\displaystyle\tau_{t}=\frac{1+y_{t}}{2}R+\frac{1-y_{t}}{2}$ (10)

We will use the following strategy to obtain different penalty factors for the misclassification of instances with the majority and minority label.

$\displaystyle C^{-}/C^{+}=R=\frac{n}{p\alpha}$ (11)

Parameter $C^{-}/C^{+}$ is the imbalance level of data set. Parameter $n$ denotes the number of negative instances and parameter $p$ denotes the number of positive instances in the training data set. Parameter $\alpha$ is a positive real constant in the range of $(0,\frac{n}{p})$ .

Therefore, we also realize a fast multi-label SVM classification algorithm by combining the BR problem transformation strategy with the improved binary SVM based on approximate extreme points [20]. These also will be introduced in 3.4. It is worth noting that improper value of $C^{-}/C^{+}$ will have negative impact on classification performance.

3.4 AEMLSVM and AEMLSVM-DEC classification algorithms

The proposed AEMLSVM and AEMLSVM-DEC classification algorithms firstly utilize the BR strategy to decompose a multi-label data set into $k$ binary data sets where $k$ is equal to the quantity of labels. Secondly, the DeriveRS algorithm [20] is improved and the ImpDeriveRS algorithm is proposed to extract the representative set from each binary data set. The improvement of the ImpDeriveRS algorithm is to simplify the processing of data sets. It is based on the theory of the DeriveRS algorithm which is introduced in [20]. Thirdly, we use improved LIBSVM algorithm [3], a widely-used binary classification algorithm to process the representative sets. Then using Eqs (3) and (4), $k$ binary classifiers are integrated into a multi-label classifier to realize fast multi-label classification. In addition, the AEMLSVM-DEC classification algorithm adopts the DEC method to deal with label data imbalanced problem. It can be concluded from the theoretical analysis that AEMLSVM and AEMLSVM-DEC classification algorithms can not only reduce the training time effectively, but also ensure that their classification performance is almost not reduced.

Algorithms 1 and 2 give the pseudocode of AEMLSVM algorithm and AEMLSVM-DEC algorithm respectively. In Algorithms 1 and 2, $S^{*}_{l_{i}}$ denotes the representative set extracted from the training subset $S_{l_{i}}$ . $\beta_{l_{i}}$ is a constant related to the approximate extreme points technique. $f_{l_{i}}$ is the prediction model trained on the representative set $S^{*}_{l_{i}}$ for the label $l_{i}$ . $f_{l_{i}}(\bm{x})$ is the testing instance $\bm{x}$ ’s predicted value for the label $l_{i}$ . $C^{-}_{l_{i}}/C^{+}_{l_{i}}$ denotes the imbalance level of the representative set $S^{*}_{l_{i}}$ .

[!t] Input: $S$ Multi-label training data set $\{(\bm{x}_{1},Y_{1}),(\bm{x}_{2},Y_{2}),\cdots,(\bm{x}_{N},Y_{N})\}$ . $L$ Total label set $\{l_{1},\cdots,l_{k}\}$ . $\bm{x}$ Testing instance $\bm{x}\in R^{D}$ . $P$ Maximum scale of training data subset after separation of first level. $V$ Maximum scale of training data subset after separation of second level. $k$ The number of labels.Output: $Y$ Predicted label set of $\bm{x}(Y\subseteq L)$ .beginTransform the multi-label training data set $S=\{(\bm{x}_{1},Y_{1}),(\bm{x}_{2},Y_{2}),\cdots,(\bm{x}_{N},Y_{N})\}$ into $k$ independent binary training subsets using binary relevance method. i.e., $S_{l_{1}},S_{l_{2}},\cdots,S_{l_{k}}$ .each binary training subset $S_{l_{i}}(l_{i}\in L,i=1,\cdots,k)$ Extract the representative set using: $[S^{*}_{l_{i}},\beta_{l_{i}}]=ImpDeriveRS(S_{l_{i}},P,V)$ ;Train an LIBSVM classifier using: $f_{l_{i}}=SVMTrain(S^{*}_{l_{i}},\beta_{l_{i}})$ , adopting non-linear kernel, based on the Eq. (6); Acquire the predicted label set for the testing instance $\bm{x}$ ,all $f_{l_{i}}(\bm{x})<0$ $Y=\{l_{i},s.t.\max f_{l_{i}}(\bm{x}),l_{i}\in L,i=1,\cdots,k\}$ ,using the Eq. (4); $Y=\{l_{i},s.t.f_{l_{i}}(\bm{x})\geqslant 0,l_{i}\in L,i=1,\cdots,k\}$ ,using the Eq. (3);return $Y$ ;

AEMLSVM[!t] Input: $S$ Multi-label training data set $\{(\bm{x}_{1},Y_{1}),(\bm{x}_{2},Y_{2}),\cdots,(\bm{x}_{N},Y_{N})\}$ . $L$ Total label set $\{l_{1},\cdots,l_{k}\}$ . $\bm{x}$ Testing instance $\bm{x}\in R^{D}$ . $P$ Maximum scale of training data subset after separation of first level. $V$ Maximum scale of training data subset after separation of second level. $k$ The number of labels. $\alpha$ The constants of positive real.Output: $Y$ Predicted label set of $\bm{x}(Y\subseteq L)$ .beginTransform the multi-label training data set $S=\{(\bm{x}_{1},Y_{1}),(\bm{x}_{2},Y_{2}),\cdots,(\bm{x}_{N},Y_{N})\}$ into $k$ independent binary training subsets using binary relevance method. i.e., $S_{l_{1}},S_{l_{2}},\cdots,S_{l_{k}}$ .each binary training subset $S_{l_{i}}(l_{i}\in L,i=1,\cdots,k)$ Extract the representative set using: $[S^{*}_{l_{i}},\beta_{l_{i}}]=ImpDeriveRS(S_{l_{i}},P,V)$ ;Obtain the imbalance level of $S^{*}_{l_{i}}$ data set using : $a)$ The number of negative instances $n_{l_{i}}$ ; $b)$ The number of positive instances $p_{l_{i}}$ ; $c)$ Obtain $C^{-}_{l_{i}}/C^{+}_{l_{i}}=\frac{n_{l_{i}}}{p_{l_{i}}\alpha}$ based no the Eq. (11);Train an improved LIBSVM classifier using: $f_{l_{i}}=SVMTrain(S^{*}_{l_{i}},\beta_{l_{i}},C^{-}_{l_{i}}/C^{+}_{l_{i}})$ , adopting non-linear kernel, based on the Eq. (9); Acquire the predicted label set for the testing instance $\bm{x}$ ,all $f_{l_{i}}(x)<0$ $Y=\{l_{i},s.t.\max f_{l_{i}}(\bm{x}),l_{i}\in L,i=1,\cdots,k\}$ ,using the Eq. (4); $Y=\{l_{i},s.t.f_{l_{i}}(\bm{x})\geqslant 0,l_{i}\in L,i=1,\cdots,k\}$ ,using the Eq. (3);return $Y$ ; AEMLSVM-DEC

3.5 Complexity analysis of AEMLSVM and AEMLSVM-DEC classification algorithms

The time and space complexity of standard SVM training are $O(N^{3})$ and $O(N^{2})$ , where $N$ denotes the size of training data set [10, 11]. The time complexity of AEMLSVM and AEMLSVM-DEC in computing the representative set is $O(kN)$ . The training time complexity of AEMLSVM and AEMLSVM-DEC varies between $O(kM)$ and $O(kM^{2.3})$ [37]. The space complexity of AEMLSVM and AEMLSVM-DEC is $O(kM)$ , where $k$ denotes the number of labels and $M$ denotes the size of representative set. we can conclude that AEMLSVM and AEMLSVM-DEC classification algorithms implements fast training mainly by reducing the size of training data set.

4. Experiments

In this section, the AEMLSVM and AEMLSVM-DEC algorithms are compared with three popular multi-label methods, ML-BVM, ML-CVM and ML-LIBSVM experimentally. Before the experimental results are presented, we firstly introduce the three popular multi-label methods, four benchmark data sets and five evaluation metrics.

4.1 Three popular multi-label methods

In the experiments, we choose three popular multi-label classification methods, ML-BVM, ML-CVM and ML-LIBSVM to compare with AEMLSVM and AEMLSVM-DEC. The reason to choose these three methods is that they also use the BR strategy to decompose the multi-label data set into many binary data subsets. The main difference among these methods is that they use different binary classification algorithms to deal with each binary data subset. ML-BVM method employs BVM [1] algorithm to process binary data subsets, ML-CVM method employs CVM [21] algorithm to process binary data subsets, and ML-LIBSVM method employs LIBSVM [10] algorithm to process binary data subsets. Then the classification results of the binary data subsets are integrated as the final multi-label classification result.

Table 1
The characteristics of data sets

Data set	Training instances	Testing instances	Features	Labels
Mediamill (exp1)	30993	12914	120	101
Siam-competition2007	21519	7077	30438	22
Rcvlv2 (topics; full sets)	23149	12000	47236	103
EukaryoteGO	4658	3108	12688	22

Figure 2.

The five evaluation metrics on data set mediamill with the RBF kernel.

4.2 Four large-scale benchmark data sets

The four large-scale benchmark data sets downloaded from LIBSVM’s website [16] are used in the experiment. The characteristics of these data sets are shown in Table 1[31].

4.3 Evaluation metrics

Because each instance can be linked to multiple labels simultaneously, the evaluation metrics of multi-label classification algorithm are more complex than binary or multi-class classification algorithm. Hence, lots of specific evaluation metrics are developed to deal with this problem [13, 5, 24]. Five popular evaluation metrics are chosen in this paper and they are Hamming loss, One-error, Coverage, Ranking loss and Average-precision [5, 24] respectively.

Table 2
The parameter setting with the RBF kernel

data set	$\varepsilon$	P	V	e
Mediamill (exp1)	0.065	500	300	1.95e-5
Siam-competition2007	0.835	100	80	9.5e-5
Rcvlv2 (topics; full sets)	1.540	120	82	2.65e-4
EukaryoteGO	1.0834	150	100	1.95e-5

Figure 3.

Training and classifying time on data set mediamill with the RBF kernel.

Figure 4.

The five evaluation metrics on data set siam with the RBF kernel.

Figure 5.

Training and classifying time on data set siam with the RBF kernel.

Hamming loss: used to evaluate how many average times an instance-label pair is misclassified.

One-error: used to evaluate how many times the top-ranked label is not in the relevant label set.

Coverage: used to evaluate how many average steps are required to move along the ranked label list so as to cover all the relevant labels of an instance.

Figure 6.

The five evaluation metrics on data set rcv1v2 with the RBF kernel.

Figure 7.

Training and classifying time on data set rcv1v2 with the RBF kernel.

Ranking loss: used to evaluate the average label pairs that are misordered for an instance.

Average-precision: used to evaluate the average fraction that relevant labels are ranked higher than a particular label.

Briefly, the greater the value of average-precision, the better the multi-label classifier’s performance. The smaller the value of the other four metrics, the better the multi-label classifier’s performance.

Figure 8.

The five evaluation metrics on data set eukaryoteGO with the RBF kernel.

Figure 9.

Training and classifying time on data set eukaryoteGO with the RBF kernel.

4.4 Experimental setting and result analysis

In our experiment, we need to set parameters $\varepsilon$ , $P$ and $V$ for AEMLSVM and AEMLSVM-DEC algorithms to acquire the optimal representation set. Parameters $\varepsilon$ , $P$ and $V$ need to be set by empirical studies for different data sets. Meanwhile, we set $e$ as the allowable termination criterion and $C^{*}(C^{*}=C/N)$ as the punishment parameter for the five multi-label classification methods. We use cross validation to obtain parameters $e$ and $C^{*}$ for different data sets. For the experimental results’ fairness and rationality, the parameters are set the same for the same data set. The hardware platform of the experiments is a regular Lenovo desktop with I5-4690 processor, 4 GB memory, 3.5 GHz frequency.

4.4.1 Analysis of experimental results with the RBF kernel

In the experiment, we adopt the RBF (Radial Basis Function) kernel $K(x,y)=\textit{exp}(-\gamma\|x-y\|^{2}_{2})$ to conduct experiment for AEMLSVM, AEMLSVM-DEC, ML-BVM, ML-CVM and ML-LIBSVM. Here, $\gamma$ represents kernel scale factor and $\|\cdot\|_{2}$ represents euclidean distance. We set $\gamma=1/16$ for RBF kernel. The parameters are set as shown in Table 2 for the data set mediamill (exp1), siam-competition2007, rcv1v2 and eukaryoteGO respectively. In addition, the parameter $C^{*}$ is set for the five multi-label methods as $1,2,4,6,8$ . Figures 2 and 3 demonstrate the experiment results of the five multi-label methods on the data set mediamill (exp1). Figures 4 and 5 demonstrate the experiment results of the five multi-label methods on the data set siam-competition2007. Figures 6 and 7 demonstrate the experiment results of the five multi-label methods on the data set rcv1v2. Figures 8 and 9 demonstrate the experiment results of the five multi-label methods on the data set eukaryoteGO.

It can be seen from Figs 2, 4, 6 and 8 that the classification results of AEMLSVM and AEMLSVM-DEC classification algorithms are comparable to that of the ML-LIBSVM method on the five evaluation metrics and superior to those of ML-BVM and ML-CVM methods. It can be concluded from Figs 3, 5, 7 and 9 that the training time of AEMLSVM algorithm is the shortest and it is only 1/24, 1/4, 1/6 and 1/4 of that of ML-LIBSVM method respectively. It can be seen that our algorithms can shorten the training time greatly while ensuring the classification performance is almost not reduced. This is mainly because our algorithm uses approximate extreme point technique to obtain representative sets, the size of which is far less than that of the training data sets. So the training time on the representative set is far less than that on the training data set. And, the representative set also keeps almost all information of the training data set, so the classification performance of the AEMLSVM and AEMLSVM-DEC algorithms are also comparable to that of ML-LIBSVM method. In addition, the classification results of AEMLSVM-DEC classification algorithm are all superior to that of AEMLSVM classification algorithm on the five evaluation metrics. This proves that by using the DEC method to solve the label data imbalanced problem, we can enhance the classification performance. And AEMLSVM-DEC classification algorithm spends 2%, 10%, 4.8% and 4.2% more training time than the AEMLSVM algorithm respectively. This means the improved classification performance is at the expense of training speed, but it is within acceptable limits. In addition, AEMLSVM and AEMLSVM-DEC classification algorithm have less testing time.

Table 3
The parameter setting with the polynomial kernel

Data set	$\varepsilon$	P	V	e
Siam-competition2007	1.08	100	80	9.5e-5
Rcvlv2 (topics; full sets)	1.54	82	82	2.65e-4
EukaryoteGO	500	150	80	1.95e-5

Figure 10.

The five evaluation metrics on data set siam with the Polynomial kernel.

Figure 11.

Training and classifying time on data set siam with the Polynomial kernel.

Figure 12.

The five evaluation metrics on data set rcv1v2 with the Polynomial kernel.

Figure 13.

Training and classifying time on data set rcv1v2 with the Polynomial kernel.

4.4.2 Analysis of experimental results with the polynomial kernel

To validate our proposal of AEMLSVM and AEMLSVM-DEC as a fast candidate to multi-label SVM classification for each non-linear kernel, we also adopt the polynomial kernel $K(x_{i},x_{j})=(\gamma x_{i}^{T}x_{j}+r)^{d}$ to conduct experiment for ML-CVM, ML-LIBSVM, AEMLSVM and AEMLSVM-DEC. Here, $\gamma$ , $d$ and $r$ represent the kernel scale factor, highest power of the polynomial and the kernel coefficient respectively. We set $\gamma=1/16$ , $d=3$ , and $r=0$ for the polynomial kernel. The parameters are set as shown in Table 3 for the data set siam-competition2007, rcv1v2 and eukaryoteGO respectively. In addition, the parameter setting for the four multi-label methods is $C^{*}=1,2,4,6,8$ . Figures 10 and 11 demonstrate the experiment results of the four multi-label methods on the data set siam-competition2007. Figures 12 and 13 demonstrate the experiment results of the four multi-label methods on the data set rcv1v2. Figures 14 and 15 demonstrate the experiment results of the four multi-label methods on the data set eukaryoteGO.

Figure 14.

The five evaluation metrics on data set eukaryoteGO with the Polynomial kernel.

Figure 15.

Training and classifying time on data set eukaryoteGO with the Polynomial kernel.

It can be seen from Figs 10, 12 and 14 that the classification results of AEMLSVM and AEMLSVM-DEC algorithms are comparable to that of the ML-LIBSVM method on the five evaluation metrics and superior to that of ML-CVM method. It can be concluded from Figs 11, 13 and 15 that the training time of AEMLSVM algorithm is the shortest and it is only 1/8, 1/10 and 1/4 of that of ML-LIBSVM method respectively. It shows that our algorithms can shorten the training time substantially and ensure the classification performance is almost not lowered. This is mainly because our algorithm adopts approximate extreme point technique to obtain representative sets. The size of the representative sets is far less than that of the training data sets. So the training time on the representative set is far less than that on the training data set. And, the representative set also keeps almost all information of the training data set, so the classification performance of the AEMLSVM and AEMLSVM-DEC algorithms is also comparable to that of ML-LIBSVM method. In addition, the classification results of AEMLSVM-DEC classification algorithm are all superior to that of AEMLSVM algorithm on the five evaluation metrics. This proves that by using the DEC method to solve the label data imbalanced problem, we can enhance the classification performance. And, AEMLSVM-DEC classification algorithm spends 4.3%, 9.8% and 20.5% more training time than AEMLSVM algorithm respectively. This means the improved classification performance is at the expense of training speed, but it is within acceptable limits. In addition, AEMLSVM and AEMLSVM-DEC classification algorithm have less testing time.

In a word, the experiment results demonstrate that the results of AEMLSVM and AEMLSVM-DEC algorithms are comparable to that of ML-LIBSVM method, and better than to that of other classification method with respect to the five evaluation metrics. Meanwhile, AEMLSVM classification algorithm not only has advantages in classification performance, but also shortens the training and classifying time. The AEMLSVM-DEC classification algorithm has obtained better classification results by using the DEC method to solve the label data imbalanced issue. In addition, the proposed AEMLSVM and AEMLSVM-DEC classification algorithms can be applied to all non-linear kernels. These will greatly improve the applicability of AEMLSVM and AEMLSVM-DEC classification algorithm on large-scale multi-label data sets.

5. Conclusions

To solve the overlong training time problem which restricts the multi-label SVM algorithm using non-linear kernel from being used on large-scale data sets, novel algorithms named AEMLSVM and AEMLSVM-DEC are proposed. In addition, the AEMLSVM-DEC classification algorithm adopts the DEC method to overcome label data imbalanced problem. These have greatly extended the application of these algorithms on large-scale data sets. Experiment results demonstrate that AEMLSVM and AEMLSVM-DEC classification algorithms can speed up the training and classification speed obviously while ensuring a comparable classification performance to that of ML-LIBSVM method and better performance than that of ML-BVM and ML-CVM method. In the future, we will further research on the label data imbalanced problem, which could get better classification performance.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (NSFC) under the grant number 61170258, 61103196, 61379127 and 61379128, by the National Key R&D Program of China under the grant number 2016YFC1401900.

References

Clare

and King

R.D.

, Knowledge discovery in Multi-label phenotype data, in: Principles of data mining and knowledge discovery, European Conference, Pkdd 2001, Freiburg, Germany, 2001, pp 42–53.

Elisseeff

A.E.

and Weston

, A kernel method for Multi-labelled classification, in: Advances in neural information processing systems, 2001, pp. 681–687.

Chang

C.C.

and Lin

C.J.

, LIBSVM: a library for support vector machines, ACM Transactions on Intelligent Systems and Technology 2(3) (2011), 27.

Cortes

and Vapnik

, Support-vector networks, Machine Learning 20(3) (1995), 273–297.

Gibaja

and Ventura

, A Tutorial on Multi-label Learning, ACM Computing Surveys 47(3) (2015), 1–38.

Brucker

Benites

and Sapozhnikova

, Multi-label classification and extracting predicted class hierarchies, Pattern Recognition 44(3) (2011), 724–738.

Tsoumakas

Katakis

and Vlahavas

, Mining Multi-label data, Data mining and knowledge discovery handbook, Springer US, 2009.

and Garcia

E.A.

, Learning from imbalanced data, IEEE Transactions on Knowledge and Data Engineering 21(9) (2009), 1263–1284.

Tsang

I.W.

Kocsor

and Kwok

J.T.

, Simpler core vector machines with enclosing balls, in: Proceedings of the 24th International Conference on Machine Learning, ACM, 2007, pp. 911–918.

10.

Tsang

I.W.

Kwok

J.T.

and Cheung

P.M.

, Core vector machines: Fast SVM training on very large data sets, Journal of Machine Learning Research 6(1) (2005), 363–392.

11.

Platt

J.C.

, fast training of support vector machines using sequential minimal optimization, in: Advances in kernel methods, 1999, pp. 185–208.

12.

, Fast Multi-label core vector machine, Pattern Recognition 46(3) (2013), 885–898.

13.

Chou

K.C.

and Shen

H.B.

, Cell-PLoc 2.0: an improved package of Web-Servers for predicting subcellular localization of proteins in various organisms, Natural Science 2(10) (2010), 1090–1103.

14.

Trohidis

Tsoumakas

Kalliris

et al., Multi-label Classification of Music into Emotions, In: ISMIR, 2008, pp. 325–330.

15.

Veropoulos

Campbell

Cristianini

et al., Controlling the sensitivity of support vector machines, in: Proceedings of the International Joint Conference on AI, 1999, pp. 55–60.

16.

LIBSVM datasets. Available: https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/andhttp://computer.njnu.edu.cn/Lab/LABIC/LABIC-Software.html.

17.

Tahir

M.A.

Kittler

and Bouridane

, Multi-label classification using heterogeneous ensemble of Multi-label classifiers, Pattern Recognition Letters 33(5) (2012), 513–523.

18.

Zhang

M.L.

and Zhou

Z.H.

, ML-KNN: A lazy learning approach to Multi-label learning, Pattern Recognition 40(7) (2007), 2038–2048.

19.

Zhang

M.L.

and Zhou

Z.H.

, Multi-label neural networks with applications to functional genomics and text categorization, IEEE Transactions on Knowledge and Data Engineering 18(10) (2006), 1338–1351.

20.

Nandan

Khargonekar

P.P.

and Talathi

S.S.

, Fast SVM training using approximate extreme points, The Journal of Machine Learning Research 15(1) (2014), 59–98.

21.

Boutell

M.R.

Luo

and Shen

et al., Learning Multi-label scene classification, Pattern Recognition 37(9) (2004), 1757–1771.

22.

García-Pedrajas

Pérez-Rodrguez

Garca-Pedrajas

Ortiz-Boyer

and Fyfe

, Class imbalance methods for translation initiation site recognition in DNA sequences, Knowledge-Based Systems 25(1) (2012), 22–34.

23.

Luaces

Díez

Barranquero

del Coz

J.J.

and Bahamonde

, Binary relevance efficacy for multilabel classification, Progress in Artificial Intelligence 1(4) (2012), 303–313.

24.

Schapire

R.E.

and Singer

, BoosTexter: A Boosting-based system for text categorization, Machine Learning 39(2) (2000), 135–168.

25.

Rockafellar

R.T.

, Convex analysis, Princeton university press, 2015.

26.

Shalev-Shwartz

and Srebro

, SVM optimization: inverse dependence on training set size, in: Proceedings of the 25th International Conference on Machine Learning, ACM, 2008, pp. 928–935.

27.

Shalev-Shwartz

Singer

and Srebro

, et al., Pegasos: Primal estimated Sub-gradient solver for SVM, Mathematical Programming 127(1) (2011), 3–30.

28.

Joachims

and Yu

C.N.J.

, Sparse kernel SVMs via Cutting-Plane training, Machine Learning 76(2) (2009), 179–193.

29.

Joachims

, Training linear SVMs in linear time, in: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2006, pp. 217–226.

30.

Zhou

Z.H.

Zhang

M.L.

Huang

S.J.

et al., Multi-instance Multi-label learning, Artificial Intelligence176(1) (2012), 2291–2320.

31.

Sun

Guo

Jiang

Wang

, and Liu

, Research and Application of Fast Multi-label SVM Classification Algorithm Using Approximate Extreme Points, in: Proceedings of the 2nd International Conference on Big Data Computing and Communication, Big Data Computing and Communications, 2016.

32.

Hong

and Liu

, Imbalanced multi-modal multi-label learning for subcellular localization prediction of human proteins with both single and multiple sites, Plos One 7(6) (2012), e37155.

33.

Tahir

M.A.

Kittler

and Yan

, Inverse random under sampling for class imbalance problem and its application to multi-label classification, Pattern Recognition 45(10) (2012), 3738–3750.

34.

Charte

Rivera

A.J.

Jesus

M.J.D.

and Herrera

, Addressing imbalance in multilabel classification: measures and random resampling algorithms, Neurocomputing 163 (2015), 3–16.

35.

Godbole

and Sarawagi

, Discriminative methods for multi-labeled classification, in: Advances in Knowl, Discovery and Data, 2004, pp. 22–30.

36.

Charte

Rivera

A.J.

Jesus

M.J.D.

and Herrera

, Mlsmote: approaching imbalanced multilabel learning through synthetic instance generation, Knowledge-Based Systems 89 (2015), 385–397.

37.

Platt

J.C.

, Fast training of support vector machines using sequential minimal optimization, in: Advances in kernel methods, MIT Press, 1999, pp. 185–208.

Fast multi-label SVM training based on approximate extreme points

Abstract

Keywords

1. Introduction

2. Related work

2.1 Multi-label classification algorithms

2.2 Methods for solving label data imbalanced problem

2.3 Binary SVM

3.1 Binary relevance strategy

3.5 Complexity analysis of AEMLSVM and AEMLSVM-DEC classification algorithms

4. Experiments

4.1 Three popular multi-label methods

Table 1 The characteristics of data sets

4.3 Evaluation metrics

Table 2 The parameter setting with the RBF kernel

4.4.1 Analysis of experimental results with the RBF kernel

Table 3 The parameter setting with the polynomial kernel

Footnotes

Acknowledgments

References

Table 1
The characteristics of data sets

Table 2
The parameter setting with the RBF kernel

Table 3
The parameter setting with the polynomial kernel