A Multiclass Nonparallel Parametric-Margin Support Vector Machine

Abstract

The twin parametric-margin support vector machine (TPMSVM) is an excellent kernel-based nonparallel classifier. However, TPMSVM was originally designed for binary classification, which is unsuitable for real-world multiclass applications. Therefore, this paper extends TPMSVM for multiclass classification and proposes a novel K multiclass nonparallel parametric-margin support vector machine (MNP-KSVC). Specifically, our MNP-KSVC enjoys the following characteristics. (1) Under the “one-versus-one-versus-rest” multiclass framework, MNP-KSVC encodes the complicated multiclass learning task into a series of subproblems with the ternary output $\{-1,0,+1\}$. In contrast to the “one-versus-one” or “one-versus-rest” strategy, each subproblem not only focuses on separating the two selected class instances but also considers the side information of the remaining class instances. (2) MNP-KSVC aims to find a pair of nonparallel parametric-margin hyperplanes for each subproblem. As a result, these hyperplanes are closer to their corresponding class and at least one distance away from the other class. At the same time, they attempt to bound the remaining class instances into an insensitive region. (3) MNP-KSVC utilizes a hybrid classification and regression loss joined with the regularization to formulate its optimization model. Then, the optimal solutions are derived from the corresponding dual problems. Finally, we conduct numerical experiments to compare the proposed method with four state-of-the-art multiclass models: Multi-SVM, MBSVM, MTPMSVM, and Twin-KSVC. Experimental results demonstrate the feasibility and effectiveness of MNP-KSVC in terms of multiclass accuracy and learning time.

1. Introduction

Data mining has become an essential tool for integrating information technology and industrialization due to the growing size of available databases [1]. One of the main applications in data mining is supervised classification. This aims to assign a label to an unseen instance that is as correct as possible from a given set of classes based on the learning model. Recently, support vector machine (SVM) [2,3] has been a preeminent maximum-margin learning paradigm for data classification. The basic idea of SVM is to find an optimal decision boundary via maximizing the margin between two parallel support hyperplanes. Compared with the neural network, SVM has the following attractive features [3]: (1) the structural risk minimization principle is implemented in SVM to control the upper bound of the generalization error, leading to an excellent generalization ability; (2) the global optimum can be achieved by optimizing a quadratic programming problem (QPP). Furthermore, kernel techniques enable SVM to handle complicated nonlinear learning tasks effectively. During recent decades, SVM has been successfully applied in a wide variety of fields ranging from scene classification [4], fault diagnosis [5,6], EEG classification [7,8], pathological diagnosis [9,10], and bioinformatics [8] to power applications [11].

One limitation in the classical SVM is the strictly parallel requirements for support vector hyperplanes. Namely, parallel hyperplanes are challenging to use to capture a data structure with a cross-plane distribution [12,13], such as “XOR” problems. To alleviate the above issue, the nonparallel SVM models have been proposed in the literature [13,14,15,16,17] during the past years. This approach relaxes the parallel requirement in SVM and seeks nonparallel hyperplanes for different classes. The pioneering work is the generalized eigenvalue proximal SVM (GEPSVM) proposed by Mangasarian and Wild [12], which attempts to find a pair of nonparallel hyperplanes via solving eigenvalue problems (EPs). Subsequently, Jayadeva et al. [13] proposed a novel QPP-type nonparallel model for classification, named TWSVM. The idea of TWSVM is to generate two nonparallel hyperplanes such that each hyperplane is closer to one of the two classes and is at least one apart from the other class. Compared with the classical SVM, the nonparallel SVM models (GEPSVM and TWSVM) have lower computational complexity and better generalization ability. Therefore, in the last few years, they have been studied extensively and developed rapidly, including a least squares version of TWSVM (LSTSVM) [16], structural risk minimization version of TWSVM (TBSVM) [17], $\nu$-PTSVM [18], nonparallel SVM (NPSVM) [19,20], nonparallel projection SVM (NPrSVM) [21], and so on [21,22,23,24,25,26,27,28].

The above nonparallel models were mainly proposed for binary classification problems. However, most real-world applications [29,30,31,32] are related to multiclass classifications such as disease diagnosis, fault detection, image recognition, and text categorization. Therefore, many researchers are interested in extending SVM models from binary to multiclass classification. Generally, the decomposition procedure has been considered to be an effective way to achieve multiclass extensions. Yang et al. [33] proposed a multiple birth SVM (MBSVM) for multiclass classification based on the “one-versus-rest” strategy, which is the first multiclass extension of the nonparallel SVM model. Angulo et al. [34] proposed an “one-versus-one-versus-rest” multiclass framework. In contrast to the “one-versus-one” strategy, it constructs $k(k-1)/2$ binary classifiers with all data points, which can avoid the risk of information loss and class distortion problems. Following this framework, Xu et al. [35] proposed a multiclass extension of TWSVM, termed Twin-KSVC. Results show that Twin-KSVC has a better generalization ability than MBSVM in most cases. Nasiri et al. [36] formulated Twin-KSVC in the least-squared sense to boost learning efficiency and further presented the LST-KSVC model. Lima et al. [32] proposed an improvement on LST-KSVC (ILST-KSVC) with regularization to implement the structural risk minimization principle.

As a successful extension of SVM, the twin parametric-margin support vector machine (TPMSVM) [15] was proposed to pursue a pair of parametric-margin nonparallel hyperplanes. Unlike GEPSVM and TWSVM, each hyperplane in TPMSVM aims to be closer to its class and far away from the other class. The parametric-margin mechanism enables TPMSVM to be suitable for many cases and results in better generalization performance. However, TPMSVM can only deal with binary classification learning tasks. The above motivates us to propose a novel K multiclass nonparallel parametric-margin support vector machine, termed MNP-KSVC. The proposed MNP-KSVC is endowed with the following attractive advantages:

• The proposed MNP-KSVC encodes the K multiclass learning task into a series of “one-versus-one-versus-rest” subproblems with all the training instances. Then, it encodes the outputs of subproblems with the ternary output $\{-1,0,+1\}$, which helps to deal with imbalanced cases.
• For each subproblem, MNP-KSVC aims to find a pair of nonparallel parametric-margin to separate the two selected classes together with the remaining classes. Unlike TMPSVM, each parametric-margin hyperplane is closer to its class and at least at a distance away from the other class, meanwhile mapping the remaining instances into a region.
• To implement the empirical risks, MNP-KSVC considers the hybrid classification and regression loss. The Hinge loss is utilized to penalize the errors of the focused two class instances and the $\epsilon$-intensive loss for the remaining class instances.
• Extensive numerical experiments are performed on several multiclass UCI benchmark datasets, and their results are compared with four models (Multi-SVM, MBSVM, MTPMSVM, and Twin-KSVC). The comparative results indicate the effectiveness and feasibility of the proposed MNP-KSVC for multiclass classification.

The remainder of this paper is organized as follows. Section 2 briefly introduces notations and related works. Section 3 proposes our MNP-KSVC. The model optimization is also discussed in Section 3. The nonlinear version of MNP-KSVC is extended in Section 4. Experimental results are described in Section 5 and Section 6 presents a discussion and future work.

2. Preliminaries

In this section, we first describe the notations used throughout the paper. Then, we briefly revisit the nonparallel classifier PTSVM and its variants.

2.1. Notations

In this paper, scalars are denoted by lowercase italic letters, vectors by lowercase bold face letters, and matrices by uppercase letters. All vectors are column vectors unless transformed to row vectors by a prime superscript ${(·)}^{\prime }$. A vector of zeros of arbitrary dimensions is represented by $\mathbf{0}$. In addition, we denote $\mathit{e}$ as a vector of ones and $\mathit{I}$ as an identity matrix of arbitrary dimensions. Moreover, let $\parallel ·\parallel$ stand for the $L_2$-norm.

2.2. TPMSVM

The TPMSVM [15] is originally proposed for binary classification with a heteroscedastic noise structure. It attempts to seek two nonparallel parametric-margin hyperplanes via the following QPPs:

$$\begin{array}{c}\hfill \begin{array}{cc}\underset{{\mathit{w}}_1,b_1}{min}& {\displaystyle \frac{1}{2}{\parallel {\mathit{w}}_1\parallel }^2+{\nu }_1\sum _{i\in {\mathcal{I}}_{+}}{\xi }_{1i}+c_1\sum _{j\in {\mathcal{I}}_{-}}{\eta }_{1j},}\hfill \\ \mathrm{s}.\mathrm{t}.& {\mathit{w}}_1^{\prime }{\mathit{x}}_i+b_1\ge -{\xi }_{1i},{\xi }_{1i}\ge 0,\hfill \\ & {\mathit{w}}_1^{\prime }{\mathit{x}}_j+b_1={\eta }_{1j},\hfill \end{array}\end{array}$$

(1)

and

$$\begin{array}{c}\hfill \begin{array}{cc}\underset{{\mathit{w}}_2,b_2}{min}& {\displaystyle \frac{1}{2}{\parallel {\mathit{w}}_2\parallel }^2+{\nu }_2\sum _{i\in {\mathcal{I}}_{-}}{\xi }_{2i}-c_2\sum _{j\in {\mathcal{I}}_{+}}{\eta }_{2j},}\hfill \\ \mathrm{s}.\mathrm{t}.& {\mathit{w}}_2^{\prime }{\mathit{x}}_i+b_2\le {\xi }_{1i},{\xi }_{2i}\ge 0,\hfill \\ & {\mathit{w}}_2^{\prime }{\mathit{x}}_j+b_2={\eta }_{2j},\hfill \end{array}\end{array}$$

(2)

where ${\nu }_1,{\nu }_2,c_1,c_2$ are positive parameters, and the decision hyperplane is half of the sum of the two hyperplanes. To obtain the solutions of problems (1) and (2), one needs to resort to the dual problems

$$\begin{array}{c}\hfill \begin{array}{cc}\underset{{\mathbf{\alpha }}_1}{min}& {\displaystyle \frac{1}{2}\sum _{i\in {\mathcal{I}}_{+}}\sum _{j\in {\mathcal{I}}_{+}}{\alpha }_{1i}^2{\mathit{x}}_i^{\prime }{\mathit{x}}_j-{\nu }_1\sum _{i\in {\mathcal{I}}_{+}}\sum _{j\in {\mathcal{I}}_{-}}{\alpha }_{1i}{\mathit{x}}_i^{\prime }{\mathit{x}}_j,}\hfill \\ \mathrm{s}.\mathrm{t}.& {\displaystyle \sum _{i\in {\mathcal{I}}_{+}}}{\alpha }_{1i}={\nu }_1,\hfill \\ & 0\le {\alpha }_{1i}\le c_1\hfill \end{array}\end{array}$$

(3)

and

$$\begin{array}{c}\hfill \begin{array}{cc}\underset{{\mathbf{\alpha }}_2}{min}& {\displaystyle \frac{1}{2}\sum _{i\in {\mathcal{I}}_{-}}\sum _{j\in {\mathcal{I}}_{-}}{\alpha }_{2i}^2{\mathit{x}}_i^{\prime }{\mathit{x}}_j-{\nu }_2\sum _{i\in {\mathcal{I}}_{-}}\sum _{j\in {\mathcal{I}}_{+}}{\alpha }_{2i}{\mathit{x}}_i^{\prime }{\mathit{x}}_j,}\hfill \\ \mathrm{s}.\mathrm{t}.& {\displaystyle \sum _{i\in {\mathcal{I}}_{-}}}{\alpha }_{2i}={\nu }_2,\hfill \\ & 0\le {\alpha }_{2i}\le c_2.\hfill \end{array}\end{array}$$

(4)

Then, the solutions $({\mathit{w}}_1,b_1)$ and $({\mathit{w}}_2,b_2)$ of dual problems (3) and (4) can be calculated according to the Karush–Kuhn–Tucker (KKT) conditions [3],

$$\begin{array}{c}\hfill {\mathit{w}}_1=\sum _{i\in {\mathcal{I}}_{+}}{\alpha }_{1i}{\mathit{x}}_i-{\nu }_1\sum _{j\in {\mathcal{I}}_{-}}{\mathit{x}}_j\mathrm{and}{\mathit{w}}_2=-\sum _{i\in {\mathcal{I}}_{-}}{\alpha }_{2i}{\mathit{x}}_i+{\nu }_2\sum _{j\in {\mathcal{I}}_{+}}{\mathit{x}}_j,\end{array}$$

(5)

$$\begin{array}{c}\hfill b_1=-\frac{1}{|{\mathcal{I}}_{S{V}_1}|}\sum _{i\in {\mathcal{I}}_{S{V}_1}}{\mathit{w}}_k^{\prime }{\mathit{x}}_i\mathrm{and}{b}_2=-\frac{1}{|{\mathcal{I}}_{S{V}_2}|}\sum _{i\in {\mathcal{I}}_{S{V}_2}}{\mathit{w}}_k^{\prime }{\mathit{x}}_i,\end{array}$$

(6)

where ${\mathcal{I}}_{S{V}_1}$ and ${\mathcal{I}}_{S{V}_2}$ are indices of the support vector set.

Note that TPMSVM can capture more complex heteroscedastic error structures via parametric-margin hyperplanes compared with TWSVM [13]. However, the variable b in TMPSVM is not strictly convex, leading to a lack of a unique solution. Moreover, the optimization problems (1) and (2) are only designed for binary classification tasks, and thus are unsuitable for many real-world multiclass learning applications.

3. The Proposed MNP-KSVC

3.1. Model Formulation

To address the above issues in TPMSVM, this subsection proposes a novel K multiclass nonparallel parametric-margin support vector machine, termed MNP-KSVC. Inspired by the “hybrid classification and regression” learning paradigm [35], MNP-KSVC decomposes the complicated K multiclass learning task into a series of “one-versus-one-versus-rest” subproblems. Each subproblem focuses on the separation of the two selected classes together with the remaining classes. Here, we utilize $\{-1,1\}$ to represent the label of the two selected classes and 0 to label the rest. Namely, the subproblem is encoded with the ternary output $\{-1,0,1\}$. The main idea of MNP-KSVC is to find a pair of nonparallel parametric-margin hyperplanes for each subproblem,

$$f_1\left(\mathit{x}\right)={\mathit{w}}_1^{\prime }\mathit{x}+b_1=0\mathrm{and}{f}_2\left(\mathit{x}\right)={\mathit{w}}_2^{\prime }\mathit{x}+b_2=0,$$

(7)

such that each one is approximate to the corresponding class while as far as possible from the other class on one side. Moreover, the remaining classes are restricted in a region between these hyperplanes.

Formally, we use ${\mathcal{I}}_k$ to express the set of indices for instances belonging to the k label in the subproblem, where k is in $\{-1,0,1\}$. Inspired by the TPMSVM [15], our MNP-KSVC considers the following two loss functions for the above ternary output learning problem:

$$\begin{array}{cc}{\mathcal{R}}_1^{emp}=\hfill & {\nu }_1\sum _{j\in {\mathcal{I}}_{-}}({\mathit{w}}_1^{\prime }{\mathit{x}}_j+b_1)+c_1\sum _{i\in {\mathcal{I}}_{+}}max(0,1-({\mathit{w}}_1^{\prime }{\mathit{x}}_i+b_1))\hfill \\ & +c_2\sum _{l\in {\mathcal{I}}_0}max(0,\epsilon -1+({\mathit{w}}_1^{\prime }{\mathit{x}}_l+b_1))\hfill \end{array}$$

(8)

and

$$\begin{array}{cc}{\mathcal{R}}_2^{emp}=\hfill & -{\nu }_2\sum _{i\in {\mathcal{I}}_{-}}({\mathit{w}}_2^{\prime }{\mathit{x}}_i+b_2)+c_3\sum _{j\in {\mathcal{I}}_{+}}max(0,1+({\mathit{w}}_2^{\prime }{\mathit{x}}_j+b_2))\hfill \\ & +c_4\sum _{l\in {\mathcal{I}}_0}max(0,\epsilon -1-({\mathit{w}}_2^{\prime }{\mathit{x}}_l+b_2)),\hfill \end{array}$$

(9)

where ${\nu }_1,{\nu }_2,c_1,c_2,c_3,c_4>0$ are penalty parameters and $\epsilon \in (0,1]$ is a margin parameter. Introducing the regularization term ${\parallel \mathit{w}\parallel }_2^2+b^2$ yields the primal problems of MNP-KSVC:

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \underset{{\mathit{w}}_1,{\mathbf{\xi }}_1,{\mathbf{\eta }}_1}{min}& \frac{1}{2}(\parallel {\mathit{w}}_1{\parallel }^2+b_1^2)+{\nu }_1\sum _{j\in {\mathcal{I}}_{-}}({\mathit{w}}_1^{\prime }{\mathit{x}}_j+b_1)+c_1\sum _{i\in {\mathcal{I}}_{+}}{\xi }_{1i}+c_3\sum _{l\in {\mathcal{I}}_0}{\eta }_{1l}\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& ({\mathit{w}}_1^{\prime }{\mathit{x}}_i+b_1)\ge 1-{\xi }_{1j},{\xi }_{1i}\ge 0,\hfill \\ & -({\mathit{w}}_1^{\prime }{\mathit{x}}_l+b_1)\ge \epsilon -1-{\eta }_{1l},{\eta }_{1l}\ge 0\hfill \end{array}\end{array}$$

(10)

and

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \underset{{\mathit{w}}_2,{\mathbf{\xi }}_2,{\mathbf{\eta }}_2}{min}& \frac{1}{2}(\parallel {\mathit{w}}_2{\parallel }^2+b_2^2)-{\nu }_2\sum _{i\in {\mathcal{I}}_{+}}({\mathit{w}}_2^{\prime }{\mathit{x}}_i+b_2)+c_2\sum _{j\in {\mathcal{I}}_{-}}{\xi }_{2i}+c_4\sum _{l\in {\mathcal{I}}_0}{\eta }_{2l}\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& -({\mathit{w}}_2^{\prime }{\mathit{x}}_j+b_2)\ge 1-{\xi }_{2j},{\xi }_{2j}\ge 0,\hfill \\ & ({\mathit{w}}_2^{\prime }{\mathit{x}}_l+b_2)\ge \epsilon -1-{\eta }_{2l},{\eta }_{2l}\ge 0,\hfill \end{array}\end{array}$$

(11)

where ${\mathbf{\xi }}_1,{\mathbf{\eta }}_1,{\mathbf{\xi }}_2,{\mathbf{\eta }}_2$ are non-negative slack vectors.

To deliver the mechanism of MNP-KSVC, we now give the following analysis and geometrical explanation for problem (10):

• The first term is the $L_2$-norm of ${\mathit{w}}_1$ and $b_1$. Minimizing this is done with the aim of regulating the model complexity of MNP-KSVC and avoiding over-fitting. Furthermore, this regularization term makes the QPPs strictly convex, leading to a unique solution.
• The second term is the sum of the projection value of the −1 labeled instances ${\mathit{x}}_{j\in {\mathcal{I}}_{-}}$ on $f_1\left({\mathit{x}}_j\right)$. Optimizing this term leads instances ${\mathit{x}}_{j\in {\mathcal{I}}_{-}}$ to be as far as possible from the +1 labeled parametric-margin hyperplane $f_1\left({\mathit{x}}_j\right)$.
• The third term with the first constraint requires the projection values of the +1 labeled instances ${\mathit{x}}_{i\in {\mathcal{I}}_{+}}$ on hyperplane $f_1\left({\mathit{x}}_j\right)$ to be not less than 1. Otherwise, a slack vector ${\xi }_{1i}$ is introduced to measure its error when the constraint is violated.
• The last term with the second constraint aims for the projection values of the remaining 0 labeled instances ${\mathit{x}}_{l\in {\mathcal{I}}_0}$ on hyperplane $f_1\left({\mathit{x}}_j\right)$ to be not more than $1-\epsilon$. Otherwise, a slack variable ${\eta }_{1l}$ is utilized to measure the corresponding error. Optimizing this is done with the aim of keeping instances ${\mathit{x}}_{l\in {\mathcal{I}}_0}$ at least $\epsilon$ distance from the +1 labeled instances. Moreover, $\epsilon$ controls the margin between “+” and “0” labeled instances.

The geometrical explanation for problem (11) is similar. Let ${\mathit{u}}_1=\left[{\mathit{w}}_1{b}_1\right]$, ${\mathit{u}}_2=\left[{\mathit{w}}_2{b}_2\right]$, $\tilde{\mathit{x}}=\left[\mathit{x}1\right]$. For the sake of simplicity, denote $\mathit{A}={\left\{\tilde{\mathit{x}}\right\}}_{i\in {\mathcal{I}}_{+}}$, $\mathit{B}={\left\{\tilde{\mathit{x}}\right\}}_{j\in {\mathcal{I}}_{-}}$ and $\mathit{C}={\left\{\tilde{\mathit{x}}\right\}}_{l\in {\mathcal{I}}_0}$ as the instances belonging to $+1$, $-1$, and 0 labels, respectively. Then, the matrix formulations of problems (10) and (11) can be expressed as

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \underset{{\mathit{u}}_1,{\mathbf{\xi }}_1,{\mathbf{\eta }}_1}{min}& \frac{1}{2}{\parallel {\mathit{u}}_1\parallel }^2+{\nu }_1{\mathit{e}}_{-}^{\prime }\mathit{B}{\mathit{u}}_1+c_1{\mathit{e}}_{+}^{\prime }{\mathbf{\xi }}_1+c_3{\mathit{e}}_0^{\prime }{\mathbf{\eta }}_1\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \mathit{A}{\mathit{u}}_1\ge {\mathit{e}}_{+}-{\mathbf{\xi }}_1,{\mathbf{\xi }}_1\ge \mathbf{0},\hfill \\ & -\mathit{C}{\mathit{u}}_1\ge (\epsilon -1){\mathit{e}}_0-{\mathbf{\eta }}_1,{\mathbf{\eta }}_1\ge \mathbf{0}\hfill \end{array}\end{array}$$

(12)

and

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \underset{{\mathit{u}}_2,{\mathbf{\xi }}_2,{\mathbf{\eta }}_2}{min}& \frac{1}{2}{\parallel {\mathit{u}}_2\parallel }^2-{\nu }_2{\mathit{e}}_{+}^{\prime }\mathit{A}{\mathit{u}}_2+c_2{\mathit{e}}_{-}^{\prime }{\mathbf{\xi }}_2+c_4{\mathit{e}}_0^{\prime }{\mathbf{\eta }}_2\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& -\mathit{B}{\mathit{u}}_2\ge {\mathit{e}}_{-}-{\mathbf{\xi }}_2,{\mathbf{\xi }}_2\ge \mathbf{0},\hfill \\ & \mathit{C}{\mathit{u}}_2\ge (\epsilon -1){\mathit{e}}_0-{\mathbf{\eta }}_2,{\mathbf{\eta }}_2\ge \mathbf{0}.\hfill \end{array}\end{array}$$

(13)

In what follows, we discuss the solutions of problems (12) and (13).

3.2. Model Optimization

To obtain solutions to problems (12) and (13), we first derive their dual problems by Theorem 1.

Theorem 1.

Optimization problems

$$\begin{array}{cc}\hfill \underset{{\mathbf{\alpha }}_1,{\mathbf{\beta }}_1}{min}& \frac{1}{2}\left[{\mathbf{\alpha }}_1^{\prime }{\mathbf{\beta }}_1^{\prime }\right]\left[\begin{array}{cc}\mathit{A}{\mathit{A}}^{\prime }& -\mathit{A}{\mathit{C}}^{\prime }\\ -\mathit{C}{\mathit{A}}^{\prime }& \mathit{C}{\mathit{C}}^{\prime }\end{array}\right]\left[\begin{array}{c}{\mathbf{\alpha }}_1\\ {\mathbf{\beta }}_1\end{array}\right]\hfill \\ & -\left({\nu }_1{\mathit{e}}_{-}^{\prime }[\mathit{B}{\mathit{A}}^{\prime }-\mathit{B}{\mathit{C}}^{\prime }]+\left[{\mathit{e}}_{+}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]\right)\left[\begin{array}{c}{\mathbf{\alpha }}_1\\ {\mathbf{\beta }}_1\end{array}\right]\hfill \\ \hfill s.t.& \mathbf{0}\le {\mathbf{\alpha }}_1\le c_1{\mathit{e}}_{+},\mathbf{0}\le {\mathbf{\beta }}_1\le c_3{\mathit{e}}_0\hfill \end{array}$$

(14)

and

$$\begin{array}{cc}\hfill \underset{{\mathbf{\alpha }}_2,{\mathbf{\beta }}_2}{min}& \frac{1}{2}\left[{\mathbf{\alpha }}_2^{\prime }{\mathbf{\beta }}_2^{\prime }\right]\left[\begin{array}{cc}\mathit{B}{\mathit{B}}^{\prime }& -\mathit{B}{\mathit{C}}^{\prime }\\ -\mathit{C}{\mathit{B}}^{\prime }& \mathit{C}{\mathit{C}}^{\prime }\end{array}\right]\left[\begin{array}{c}{\mathbf{\alpha }}_2\\ {\mathbf{\beta }}_2\end{array}\right]\hfill \\ & -\left({\nu }_2{\mathit{e}}_{+}^{\prime }[\mathit{A}{\mathit{B}}^{\prime }-\mathit{A}{\mathit{C}}^{\prime }]+\left[{\mathit{e}}_{-}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]\right)\left[\begin{array}{c}{\mathbf{\alpha }}_2\\ {\mathbf{\beta }}_2\end{array}\right]\hfill \\ \hfill s.t.& \mathbf{0}\le {\mathbf{\alpha }}_2\le c_3{\mathit{e}}_{-},\mathbf{0}\le {\mathbf{\beta }}_2\le c_4{\mathit{e}}_0\hfill \end{array}$$

(15)

are the dual problems of (12) and (13), respectively.

Proof of Theorem 1. 

Taking problem (12) as an example, firstly, we construct its Lagrangian function as

$$\begin{array}{cc}\mathcal{L}\left({\Xi }_1\right)=\hfill & \frac{1}{2}{\parallel {\mathit{u}}_1\parallel }^2+{\nu }_1{\mathit{e}}_{-}^{\prime }\mathit{B}{\mathit{u}}_1+c_1{\mathit{e}}_{+}^{\prime }{\mathbf{\xi }}_1+c_3{\mathit{e}}_0^{\prime }{\mathbf{\eta }}_1\hfill \\ & -{\mathbf{\alpha }}_1^{\prime }(\mathit{A}{\mathit{u}}_1+{\mathbf{\xi }}_1-{\mathit{e}}_{+})-{\mathbf{\beta }}_1^{\prime }(-\mathit{C}{\mathit{u}}_1+{\mathbf{\eta }}_1-(\epsilon -1){\mathit{e}}_0)\hfill \\ & -{\mathbf{\phi }}_1^{\prime }{\mathbf{\xi }}_1-{\gamma }_1{\mathbf{\eta }}_1,\hfill \end{array}$$

(16)

where ${\mathbf{\alpha }}_1,{\mathbf{\beta }}_1,{\mathbf{\phi }}_1,{\mathbf{\gamma }}_1$ are the non-negative Lagrange multipliers to constraints of problem (12), and ${\Xi }_1=\{{\mathit{u}}_1,{\mathbf{\xi }}_1,{\mathbf{\eta }}_1,{\mathbf{\alpha }}_1,{\mathbf{\beta }}_1,{\mathbf{\phi }}_1,{\mathbf{\gamma }}_1\}$. According to KKT conditions [3,37], the Lagrangian function (16) has to be maximized with its dual variables ${\mathbf{\alpha }}_1,{\mathbf{\beta }}_1,{\mathbf{\phi }}_1,{\mathbf{\gamma }}_1$ while being minimized with its primal variables ${\mathit{u}}_1,{\mathbf{\xi }}_1,{\mathbf{\eta }}_1$. Differentiate $\mathcal{L}\left({\Xi }_1\right)$ with respect to ${\mathit{u}}_1,{\mathbf{\eta }}_1,{\mathbf{\xi }}_1$; then, optimal conditions of problem (12) are obtained by

$$\begin{array}{c}\hfill \nabla {\mathcal{L}}_{{\mathit{u}}_1}={\mathit{u}}_1+{\nu }_1{\mathit{B}}^{\prime }{\mathit{e}}_{-}-{\mathit{A}}^{\prime }{\mathbf{\alpha }}_1+{\mathit{C}}^{\prime }{\mathbf{\beta }}_1=\mathbf{0},\end{array}$$

(17)

$$\begin{array}{c}\hfill \nabla {\mathcal{L}}_{{\mathbf{\xi }}_1}=c_1{\mathit{e}}_{+}-{\mathbf{\alpha }}_1-{\mathbf{\phi }}_1=\mathbf{0},\end{array}$$

(18)

$$\begin{array}{c}\hfill \nabla {\mathcal{L}}_{{\mathbf{\eta }}_1}=c_3{\mathit{e}}_0-{\mathbf{\beta }}_1-{\mathbf{\gamma }}_1=\mathbf{0},\end{array}$$

(19)

$$\begin{array}{c}\hfill {\mathbf{\alpha }}_1^{\prime }(\mathit{A}{\mathit{u}}_1+{\mathbf{\xi }}_1-{\mathit{e}}_{+})=0,\end{array}$$

(20)

$$\begin{array}{c}\hfill {\mathbf{\beta }}_1^{\prime }(-\mathit{C}{\mathit{u}}_1+{\mathbf{\eta }}_1-(\epsilon -1){\mathit{e}}_0)=0,\end{array}$$

(21)

$$\begin{array}{c}\hfill {\mathbf{\phi }}_1^{\prime }{\mathbf{\xi }}_1=0,\end{array}$$

(22)

$$\begin{array}{c}\hfill {\gamma }_1{\mathbf{\eta }}_1=0.\end{array}$$

(23)

From (17), we have

$$\begin{array}{c}\hfill {\mathit{u}}_1={\mathit{A}}^{\prime }{\mathbf{\alpha }}_1-{\mathit{C}}^{\prime }{\mathbf{\beta }}_1-{\nu }_1{\mathit{B}}^{\prime }{\mathit{e}}_{-}.\end{array}$$

(24)

Since ${\mathbf{\phi }}_1,{\mathbf{\gamma }}_1\ge \mathbf{0}$, from (18) and (19), we derive

$$\mathbf{0}\le {\mathbf{\alpha }}_1\le c_1{\mathit{e}}_{+}\mathrm{and}\mathbf{0}\le {\mathbf{\beta }}_1\le c_3{\mathit{e}}_0.$$

(25)

Finally, substituting (24) into the Lagrangian function (16) and using KKT conditions (17)–(23), the dual problem of (12) can be formulated as

$$\begin{array}{cc}\hfill \underset{{\mathbf{\alpha }}_1,{\mathbf{\beta }}_1}{min}& \frac{1}{2}\left[{\mathbf{\alpha }}_1^{\prime }{\mathbf{\beta }}_1^{\prime }\right]\left[\begin{array}{cc}\mathit{A}{\mathit{A}}^{\prime }& -\mathit{A}{\mathit{C}}^{\prime }\\ -\mathit{C}{\mathit{A}}^{\prime }& \mathit{C}{\mathit{C}}^{\prime }\end{array}\right]\left[\begin{array}{c}{\mathbf{\alpha }}_1\\ {\mathbf{\beta }}_1\end{array}\right]\hfill \\ & -\left({\nu }_1{\mathit{e}}_{-}^{\prime }[\mathit{B}{\mathit{A}}^{\prime }-\mathit{B}{\mathit{C}}^{\prime }]+\left[{\mathit{e}}_{+}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]\right)\left[\begin{array}{c}{\mathbf{\alpha }}_1\\ {\mathbf{\beta }}_1\end{array}\right]\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \mathbf{0}\le {\mathbf{\alpha }}_1\le c_1{\mathit{e}}_{+},\mathbf{0}\le {\mathbf{\beta }}_1\le c_3{\mathit{e}}_0.\hfill \end{array}$$

(26)

Similarly, we can derive the dual problem of (13) as problem (15). □

For ease of notation, define ${\mathit{q}}_1=[{\mathbf{\alpha }}_1;{\mathbf{\beta }}_1]$, ${\mathit{N}}_1=[\mathit{A};-\mathit{C}]$, ${\mathit{h}}_1=[{\mathit{e}}_{+};(\epsilon -1){\mathit{e}}_0]$, and ${\mathit{e}}_{q1}=[c_1{\mathit{e}}_{+};c_3{\mathit{e}}_0]$. Then, problem (14) can be succinctly reformulated as

$$\begin{array}{cc}\hfill \underset{{\mathit{q}}_1}{min}& \frac{1}{2}{\mathit{q}}_1^{\prime }{\mathit{H}}_1{\mathit{q}}_1-{\mathit{d}}_1{\mathit{q}}_1\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \mathbf{0}\le {\mathit{q}}_1\le {\mathit{e}}_{q1}\hfill \end{array}$$

(27)

where

$${\mathit{H}}_1={\mathit{N}}_1{\mathit{N}}_1^{\prime }=\left[\begin{array}{cc}\mathit{A}{\mathit{A}}^{\prime }& -\mathit{A}{\mathit{C}}^{\prime }\\ -\mathit{C}{\mathit{A}}^{\prime }& \mathit{C}{\mathit{C}}^{\prime }\end{array}\right]$$

(28)

and

$${\mathit{d}}_1={\nu }_1{\mathit{e}}_{-}^{\prime }\mathit{B}{\mathit{N}}_1^{\prime }+{\mathit{h}}_1^{\prime }={\nu }_1{\mathit{e}}_{-}^{\prime }[\mathit{B}{\mathit{A}}^{\prime }-\mathit{B}{\mathit{C}}^{\prime }]+\left[{\mathit{e}}_{+}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]$$

(29)

Similarly, define ${\mathit{q}}_2=[{\mathbf{\alpha }}_2;{\mathbf{\beta }}_2]$, ${\mathit{N}}_2=[-\mathit{B};\mathit{C}]$, ${\mathit{h}}_2=[{\mathit{e}}_{-};(\epsilon -1){\mathit{e}}_0]$, and ${\mathit{e}}_{q2}=[c_2{\mathit{e}}_{-};c_4{\mathit{e}}_0]$ for problem (15). Then, it can be reformulated as

$$\begin{array}{cc}\hfill \underset{{\mathit{q}}_2}{min}& \frac{1}{2}{\mathit{q}}_2^{\prime }{\mathit{H}}_2{\mathit{q}}_2-{\mathit{d}}_2{\mathit{q}}_2\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \mathbf{0}\le {\mathit{q}}_2\le {\mathit{e}}_{q2}\hfill \end{array}$$

(30)

where

$${\mathit{H}}_2={\mathit{N}}_2{\mathit{N}}_2^{\prime }=\left[\begin{array}{cc}\mathit{B}{\mathit{B}}^{\prime }& -\mathit{B}{\mathit{C}}^{\prime }\\ -\mathit{C}{\mathit{B}}^{\prime }& \mathit{C}{\mathit{C}}^{\prime }\end{array}\right]$$

(31)

and

$${\mathit{d}}_2={\nu }_2{\mathit{e}}_{+}^{\prime }\mathit{A}{\mathit{N}}_2^{\prime }+{\mathit{h}}_2^{\prime }={\nu }_2{\mathit{e}}_{+}^{\prime }[\mathit{A}{\mathit{B}}^{\prime }-\mathit{A}{\mathit{C}}^{\prime }]+\left[{\mathit{e}}_{-}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]$$

(32)

After solving dual problems (27) and (30) by the standard QPP solver, we can obtain the solutions to primal problems (12) and (13) by Proposition 1 according to KKT conditions without proof.

Proposition 1.

Suppose that ${\mathit{q}}_1=[{\mathbf{\alpha }}_1;{\mathbf{\beta }}_1]$ and ${\mathit{q}}_2=[{\mathbf{\alpha }}_2;{\mathbf{\beta }}_2]$ are solutions to dual problems (27) and (30), respectively. Then, solutions ${\mathit{u}}_1$ and ${\mathit{u}}_2$ to primal problems (12) and (13) can be formulated by

$$\begin{array}{c}\hfill {\mathit{u}}_1={\mathit{N}}_1^{\prime }{\mathit{q}}_1-{\nu }_1{\mathit{B}}^{\prime }{\mathit{e}}_{-}={\mathit{A}}^{\prime }{\mathbf{\alpha }}_1-{\mathit{C}}^{\prime }{\mathbf{\beta }}_1-{\nu }_1{\mathit{B}}^{\prime }{\mathit{e}}_{-}\end{array}$$

(33)

and

$$\begin{array}{c}\hfill {\mathit{u}}_2=-{\mathit{N}}_2^{\prime }{\mathit{q}}_2+{\nu }_2{\mathit{A}}^{\prime }{\mathit{e}}_{+}=-{\mathit{B}}^{\prime }{\mathbf{\alpha }}_2+{\mathit{C}}^{\prime }{\mathbf{\beta }}_2+{\nu }_2{\mathit{A}}^{\prime }{\mathit{e}}_{+}\end{array}$$

(34)

3.3. Decision Rule

As mentioned in Section 3.1, our MNP-KSVC decomposes the multiclass learning task into a series of subproblems with the “one-versus-one-versus-rest” strategy. Specifically, we construct $K(K-1)/2$ MNP-KSVC classifiers for K-class classification. For each $(k_1,k_2)$-pair classifier, we relabel the dataset with ternary outputs $\{-1,0,+1\}$ according to the two selected and the remaning class instances. Namely, we label “+1”, “−1”, and “0” to instances belonging to the $k_i$ class, $k_j$ class, and all the remaining classes, respectively. Then, we train it on the new relabeled dataset by solving problems (12) and (13).

As for the decision, we predict the label of an unseen instance $\mathit{x}$ on the voting strategy from the ensemble results of $K(K-1)/2$ MNP-KSVC classifiers. Namely, we determine the vote via each classifier according to the regions in which $\mathit{x}$ is located. Taking the $(k_1,k_2)$-pair classifier as an example, firstly, we reformulate the parametric-margin hyperplanes (7) w.r.t. $\mathit{u}=[\mathit{w};b]$ and $\tilde{\mathit{x}}=\left[\mathit{x}1\right]$ as

$$f_1\left(\mathit{x}\right)={\mathit{w}}_1^{\prime }\mathit{x}+b_1={\mathit{u}}_1^{\prime }\tilde{\mathit{x}}\mathrm{and}{f}_2\left(\mathit{x}\right)={\mathit{w}}_2^{\prime }\mathit{x}+b_2={\mathit{u}}_2^{\prime }\tilde{\mathit{x}},$$

(35)

If $\mathit{x}$ is located above the “+” hyperplane $f_1\left(\mathit{x}\right)>1-\epsilon$—i.e., satisfying the condition ${\mathit{u}}_1^{\prime }\tilde{\mathit{x}}>1-\epsilon$—we vote it to the $k_i$ class. On the other hand, if $\mathit{x}$ is located below the “−” hyperplane $f_2\left(\mathit{x}\right)<-1+\epsilon$, we vote it to the $k_j$ class. Otherwise, it belongs to the remaining classes. In summary, the decision function for the $(k_1,k_2)$-pair classifier can be expressed as

$$\begin{array}{c}\hfill g\left(\mathit{x}\right)=\left\{\begin{array}{cc}\hfill +1& f_1\left(\mathit{x}\right)>1-\epsilon ,\hfill \\ \hfill -1& f_2\left(\mathit{x}\right)<-1+\epsilon ,\hfill \\ \hfill 0& \mathrm{otherwise}.\hfill \end{array}\right.\end{array}$$

(36)

Finally, the given unseen instance $\mathit{x}$ is assigned to the class label that gets the most votes. In summary, the whole procedure of MNP-KSVC is established in Algorithm 1 with the Figure 1.

Algorithm 1 The procedure of MNP-KSVC

1: Input dataset $\mathcal{T}=\left\{({\mathit{x}}_i,y_i)\right|1\le i\le m\}$, where ${\mathit{x}}_i\in {\mathbb{R}}^n$ and $y_i=\{1,\cdots ,K\}$. 2: Choose parameters ${\nu }_1,{\nu }_2,c_1,c_2,c_3,c_4>0$ and $\epsilon \in (0,1]$. Training Procedure: 3: for$k_i$ in $\mathrm{range}(1,\cdots ,K)$ do 4:   for $k_j$ in $\mathrm{range}(k_i+1,\cdots ,K)$ do 5:    Relabel “+1”, “−1”, and “0” to instances belonging to $k_i$, $k_j$, and the rest classes. 6:    Construct $\mathit{A}$, $\mathit{B}$, and $\mathit{C}$ for problem (12) and (13) of $(k_1,k_2)$-pair classifier. 7:    Solve the corresponding dual problem (27) and (30) by QPP solver. Then, get    their solution ${\mathit{q}}_1=[{\mathbf{\alpha }}_1;{\mathbf{\beta }}_1]$ and ${\mathit{q}}_2=[{\mathbf{\alpha }}_2;{\mathbf{\beta }}_2]$. 8:    Build the auxiliary functions for classifier w.r.t. Proposition 1 $$k_1\text{-}\mathrm{class}:f_1\left(\mathit{x}\right)={\mathit{w}}_1^{\prime }\mathit{x}+b_1={\mathit{q}}_1^{\prime }{\mathit{N}}_1\mathit{x}-{\nu }_1{\mathit{e}}_{-}^{\prime }\mathit{B}\mathit{x}$$ (37)    and $$k_2\text{-}\mathrm{class}:f_2\left(\mathit{x}\right)={\mathit{w}}_2^{\prime }\mathit{x}+b_2=-{\mathit{q}}_2^{\prime }{\mathit{N}}_2\mathit{x}+{\nu }_2{\mathit{e}}_{+}^{\prime }\mathit{A}\mathit{x}$$ (38) 9:   end for 10: end for Predicting Procedure: 11: For an unseen instance $\mathit{x}$, assign it to class y via the following vote strategy. 12: Initialize the vote vector $\mathit{v}\mathit{o}\mathit{t}\mathit{e}=\mathbf{0}$ for K classes. 13: for$k_i$ in $\mathrm{range}(1,\cdots ,K)$ do 14:   for $k_j$ in $\mathrm{range}(k_i+1,\cdots ,K)$ do 15:    Compute the decision function $g\left(\mathit{x}\right)$ for the $(k_1,k_2)$-pair classifier w.r.t. (36). 16:    if $g\left(\mathit{x}\right)==1$ then 17:     Update $\mathit{v}\mathit{o}\mathit{t}\mathit{e}\left(k_i\right)+=1$ 18:    else if $g\left(\mathit{x}\right)==-1$ then 19:     Update $\mathbf{vote}\left(k_j\right)+=1$ 20:    end if 21:   end for 22: end for 23: Finally, assign the most votes of class to $\mathit{x}$ via $$\mathrm{label}\left(\mathit{x}\right)\leftarrow arg\underset{k=\{1,\cdots ,K\}}{max}\mathit{v}\mathit{o}\mathit{t}\mathit{e}\left(k\right)$$ (39)

4. Model Extension to the Nonlinear Case

In practice, the linear classifier is sometimes not suitable for many real-world nonlinear learning tasks [18,21,30]. One of the effective solutions is to map linearly non-separable instances into the feature space. Thus, in this section, we focus on the nonlinear extension of MNP-KSVC.

To construct our nonlinear MNP-KSVC, we consider the feature mapping ${\mathit{x}}^{\phi }=\phi \left(\mathit{x}\right):{\mathbb{R}}^n\to \mathcal{H}$ (RKHS, Reproducing Kernel Hilbert Space) with the kernel trick [3]. Define ${\mathit{A}}^{\varphi }={\left\{\varphi \left({\tilde{\mathit{x}}}_i\right)\right\}}_{i\in {\mathcal{I}}_{+}}$, ${\mathit{B}}^{\varphi }={\left\{\varphi \left({\tilde{\mathit{x}}}_j\right)\right\}}_{j\in {\mathcal{I}}_{-}}$, and ${\mathit{C}}^{\varphi }={\left\{\varphi \left({\tilde{\mathit{x}}}_l\right)\right\}}_{j\in {\mathcal{I}}_0}$. Then, the nonlinear MNP-KSVC model optimizes the following two primal QPPs:

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \underset{{\mathit{u}}_1,{\mathbf{\xi }}_1,{\mathbf{\eta }}_1}{min}& \frac{1}{2}{\parallel {\mathit{u}}_1\parallel }^2+{\nu }_1{\mathit{e}}_{-}^{\prime }{\mathit{B}}_{\varphi }{\mathit{u}}_1+c_1{\mathit{e}}_{+}^{\prime }{\mathbf{\xi }}_1+c_3{\mathit{e}}_0^{\prime }{\mathbf{\eta }}_1\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& {\mathit{A}}_{\varphi }{\mathit{u}}_1\ge {\mathit{e}}_{+}-{\mathbf{\xi }}_1,{\mathbf{\xi }}_1\ge \mathbf{0},\hfill \\ & -{\mathit{C}}_{\varphi }{\mathit{u}}_1\ge (\epsilon -1){\mathit{e}}_0-{\mathbf{\eta }}_1,{\mathbf{\eta }}_1\ge \mathbf{0}\hfill \end{array}\end{array}$$

(40)

and

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \underset{{\mathit{u}}_2,{\mathbf{\xi }}_2,{\mathbf{\eta }}_2}{min}& \frac{1}{2}{\parallel {\mathit{u}}_2\parallel }^2-{\nu }_2{\mathit{e}}_{+}^{\prime }{\mathit{A}}_{\varphi }{\mathit{u}}_2+c_2{\mathit{e}}_{-}^{\prime }{\mathbf{\xi }}_2+c_4{\mathit{e}}_0^{\prime }{\mathbf{\eta }}_2\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& -{\mathit{B}}_{\varphi }{\mathit{u}}_2\ge {\mathit{e}}_{-}-{\mathbf{\xi }}_2,{\mathbf{\xi }}_2\ge \mathbf{0},\hfill \\ & {\mathit{C}}_{\varphi }{\mathit{u}}_2\ge (\epsilon -1){\mathit{e}}_0-{\mathbf{\eta }}_2,{\mathbf{\eta }}_2\ge \mathbf{0}.\hfill \end{array}\end{array}$$

(41)

where ${\mathbf{\xi }}_1,{\mathbf{\eta }}_1,{\mathbf{\xi }}_2,{\mathbf{\eta }}_2$ are non-negative slack vectors. Because the formulations of nonlinear problems (40) and (41) are similar to the linear cases (12) and (13), we can obtain their solutions in a similar manner.

In what follows, we define the kernel operation for MNP-KSVC.

Definition 1.

Suppose that $\mathit{K}(·,·)$ is an appropriate kernel function; then, the kernel operation in matrix form is defined as

$$\mathit{K}(\mathit{A},\mathit{B})=〈{\mathit{A}}_{\varphi },{\mathit{B}}_{\varphi }〉,$$

(42)

whose $ij$-th element can be computed by

$$\mathit{K}{(\mathit{A},\mathit{B})}_{ij}=\varphi {\left({\mathit{x}}_i\right)}^{\prime }\varphi \left({\mathit{x}}_j\right)=\mathit{K}({\mathit{x}}_i,{\mathit{x}}_j).$$

(43)

Then, we can derive the dual problems of (40) and (41) by Theorem 2.

Theorem 2.

Optimization problems

$$\begin{array}{cc}\hfill \underset{{\mathbf{\alpha }}_1,{\mathbf{\beta }}_1}{min}& \frac{1}{2}\left[{\mathbf{\alpha }}_1^{\prime }{\mathbf{\beta }}_1^{\prime }\right]\left[\begin{array}{cc}\mathit{K}(\mathit{A},\mathit{A})& -\mathit{K}(\mathit{A},\mathit{C})\\ -\mathit{K}(\mathit{C},\mathit{A})& \mathit{K}(\mathit{C},\mathit{C})\end{array}\right]\left[\begin{array}{c}{\mathbf{\alpha }}_1\\ {\mathbf{\beta }}_1\end{array}\right]\hfill \\ & -\left({\nu }_1{\mathit{e}}_{-}^{\prime }[\mathit{K}(\mathit{B},\mathit{A})-\mathit{K}(\mathit{B},\mathit{C})]+\left[{\mathit{e}}_{+}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]\right)\left[\begin{array}{c}{\mathbf{\alpha }}_1\\ {\mathbf{\beta }}_1\end{array}\right]\hfill \\ \hfill s.t.& \mathbf{0}\le {\mathbf{\alpha }}_1\le c_1{\mathit{e}}_{+},\mathbf{0}\le {\mathbf{\beta }}_1\le c_3{\mathit{e}}_0\hfill \end{array}$$

(44)

and

$$\begin{array}{cc}\hfill \underset{{\mathbf{\alpha }}_2,{\mathbf{\beta }}_2}{min}& \frac{1}{2}\left[{\mathbf{\alpha }}_2^{\prime }{\mathbf{\beta }}_2^{\prime }\right]\left[\begin{array}{cc}\mathit{K}(\mathit{B},\mathit{B})& -\mathit{K}(\mathit{B},\mathit{C})\\ -\mathit{K}(\mathit{C},\mathit{B})& \mathit{K}(\mathit{C},\mathit{C})\end{array}\right]\left[\begin{array}{c}{\mathbf{\alpha }}_2\\ {\mathbf{\beta }}_2\end{array}\right]\hfill \\ & -\left({\nu }_2{\mathit{e}}_{+}^{\prime }[\mathit{K}(\mathit{A},\mathit{B})-\mathit{K}(\mathit{A},\mathit{C})]+\left[{\mathit{e}}_{-}^{\prime }(\epsilon -1){\mathit{e}}_0^{\prime }\right]\right)\left[\begin{array}{c}{\mathbf{\alpha }}_2\\ {\mathbf{\beta }}_2\end{array}\right]\hfill \\ \hfill s.t.& \mathbf{0}\le {\mathbf{\alpha }}_2\le c_3{\mathit{e}}_{-},\mathbf{0}\le {\mathbf{\beta }}_2\le c_4{\mathit{e}}_0\hfill \end{array}$$

(45)

are the dual problems of (40) and (41), respectively.

Proof of Theorem 2. 

By introducing non-negative Lagrange multipliers ${\mathbf{\alpha }}_1$, ${\mathbf{\beta }}_1$, ${\mathbf{\phi }}_1$, and ${\mathbf{\gamma }}_1$ to constraints of problem (40), its Lagrangian function is built as

$$\begin{array}{cc}\hfill \mathcal{L}\left({\Xi }_1\right)=& \frac{1}{2}{\parallel {\mathit{u}}_1\parallel }^2+{\nu }_1{\mathit{e}}_{-}^{\prime }{\mathit{B}}_{\varphi }{\mathit{u}}_1+c_1{\mathit{e}}_{+}^{\prime }{\mathbf{\xi }}_1+c_3{\mathit{e}}_0^{\prime }{\mathbf{\eta }}_1\hfill \\ & -{\mathbf{\alpha }}_1^{\prime }({\mathit{A}}_{\varphi }{\mathit{u}}_1+{\mathbf{\xi }}_1-{\mathit{e}}_{+})-{\mathbf{\beta }}_1^{\prime }(-{\mathit{C}}_{\varphi }{\mathit{u}}_1+{\mathbf{\eta }}_1-(\epsilon -1){\mathit{e}}_0)\hfill \\ & -{\mathbf{\phi }}_1^{\prime }{\mathbf{\xi }}_1-{\gamma }_1{\mathbf{\eta }}_1,\hfill \end{array}$$

(46)

where ${\Xi }_1=\{{\mathit{u}}_1,{\mathbf{\xi }}_1,{\mathbf{\eta }}_1,{\mathbf{\alpha }}_1,{\mathbf{\beta }}_1,{\mathbf{\phi }}_1,{\mathbf{\gamma }}_1\}$. Differentiate $\mathcal{L}\left({\Xi }_1\right)$ with respect to ${\mathit{u}}_1,{\mathbf{\eta }}_1,{\mathbf{\xi }}_1$; then, optimal conditions of problem (40) are obtained by

$$\begin{array}{c}\hfill \nabla {\mathcal{L}}_{{\mathit{u}}_1}={\mathit{u}}_1+{\nu }_1{\mathit{B}}_{\varphi }^{\prime }{\mathit{e}}_{-}-{\mathit{A}}_{\varphi }^{\prime }{\mathbf{\alpha }}_1+{\mathit{C}}_{\varphi }^{\prime }{\mathbf{\beta }}_1=\mathbf{0},\end{array}$$

(47)

$$\begin{array}{c}\hfill \nabla {\mathcal{L}}_{{\mathbf{\xi }}_1}=c_1{\mathit{e}}_{+}-{\mathbf{\alpha }}_1-{\mathbf{\phi }}_1=\mathbf{0},\end{array}$$

(48)

$$\begin{array}{c}\hfill \nabla {\mathcal{L}}_{{\mathbf{\eta }}_1}=c_3{\mathit{e}}_0-{\mathbf{\beta }}_1-{\mathbf{\gamma }}_1=\mathbf{0},\end{array}$$

(49)

$$\begin{array}{c}\hfill {\mathbf{\alpha }}_1^{\prime }({\mathit{A}}_{\varphi }{\mathit{u}}_1+{\mathbf{\xi }}_1-{\mathit{e}}_{+})=0,\end{array}$$

(50)

$$\begin{array}{c}\hfill {\mathbf{\beta }}_1^{\prime }(-{\mathit{C}}_{\varphi }{\mathit{u}}_1+{\mathbf{\eta }}_1-(\epsilon -1){\mathit{e}}_0)=0,\end{array}$$

(51)

$$\begin{array}{c}\hfill {\mathbf{\phi }}_1^{\prime }{\mathbf{\xi }}_1=0,\end{array}$$

(52)

$$\begin{array}{c}\hfill {\gamma }_1{\mathbf{\eta }}_1=0.\end{array}$$

(53)

From (47), we have

$$\begin{array}{c}\hfill {\mathit{u}}_1={\mathit{A}}_{\varphi }^{\prime }{\mathbf{\alpha }}_1-{\mathit{C}}_{\varphi }^{\prime }{\mathbf{\beta }}_1-{\nu }_1{\mathit{B}}_{\varphi }^{\prime }{\mathit{e}}_{-}.\end{array}$$

(54)

Since ${\mathbf{\phi }}_1,{\mathbf{\gamma }}_1\ge \mathbf{0}$, from (48) and (49), we derive

$$\mathbf{0}\le {\mathbf{\alpha }}_1\le c_1{\mathit{e}}_{+}\mathrm{and}\mathbf{0}\le {\mathbf{\beta }}_1\le c_3{\mathit{e}}_0.$$

(55)

Finally, substituting (54) into the Lagrangian function (16) and using KKT conditions (47)–(53), the dual problem of (40) can be formulated as (44). Similarly, we can derive the dual problem of (41) as problem (45). □

The procedure of the nonlinear MNP-KSVC is similar to that of the linear one, but with the following minor modifications in Algorithm 1:

• In contrast to some existing nonparallel SVMs, we do not need to consider the extra kernel-generated technique since only inner products appear in dual problems (14) and (15) of the linear MNP-KSVC. These dual formulations enable MNP-KSVC to behave consistently in linear and nonlinear cases. Thus, taking appropriate kernel functions instead of inner products in the Hessian matrix of dual problem (14) and (15), i.e.,

  $${\mathit{H}}_{\varphi 1}=\left[\begin{array}{cc}\mathit{K}(\mathit{A},\mathit{A})& -\mathit{K}(\mathit{A},\mathit{C})\\ -\mathit{K}(\mathit{C},\mathit{A})& \mathit{K}(\mathit{C},\mathit{C})\end{array}\right]\mathrm{and}{\mathit{H}}_{\varphi 2}=\left[\begin{array}{cc}\mathit{K}(\mathit{B},\mathit{B})& -\mathit{K}(\mathit{B},\mathit{C})\\ -\mathit{K}(\mathit{C},\mathit{B})& \mathit{K}(\mathit{C},\mathit{C})\end{array}\right],$$

  (56)

  we can obtain the dual formation of the nonlinear MNP-KSVC in (44) and (45).
• Once we obtain the solution ${\mathit{q}}_1=[{\mathbf{\alpha }}_1;{\mathbf{\beta }}_1]$ and ${\mathit{q}}_2=[{\mathbf{\alpha }}_2;{\mathbf{\beta }}_2]$ to problems (44) and (45) respectively, the corresponding primal solutions ${\mathit{u}}_1$ and ${\mathit{u}}_2$ in feature space can be formulated by

  $$\begin{array}{c}\hfill {\mathit{u}}_1={\mathit{A}}_{\varphi }^{\prime }{\mathbf{\alpha }}_1-{\mathit{C}}_{\varphi }^{\prime }{\mathbf{\beta }}_1-{\nu }_1{\mathit{B}}_{\varphi }^{\prime }{\mathit{e}}_{-}\end{array}$$

  (57)

  and

  $$\begin{array}{c}\hfill {\mathit{u}}_2=-{\mathit{B}}_{\varphi }^{\prime }{\mathbf{\alpha }}_2+{\mathit{C}}_{\varphi }^{\prime }{\mathbf{\beta }}_2+{\nu }_2{\mathit{A}}_{\varphi }^{\prime }{\mathit{e}}_{+}\end{array}$$

  (58)
• For an unseen instance $\mathit{x}$, construct the following decision functions for $(i,j)$-pair nonlinear MNP-KSVC classifier as

  $$\begin{array}{c}\hfill g_{\varphi }\left(\mathit{x}\right)=\left\{\begin{array}{cc}\hfill +1& f_{\varphi 1}\left(\tilde{\mathit{x}}\right)>1-\epsilon ,\hfill \\ \hfill -1& f_{\varphi 2}\left(\tilde{\mathit{x}}\right)<-1+\epsilon ,\hfill \\ \hfill 0& \mathrm{otherwise},\hfill \end{array}\right.\end{array}$$

  (59)

  where $\tilde{\mathit{x}}=\left[\mathit{x}1\right]$, the auxiliary functions $f_{\varphi 1}\left(\mathit{x}\right)$ and $f_{\varphi 2}\left(\mathit{x}\right)$ in feature space can be expressed as

  $$\begin{array}{c}\hfill f_{\varphi 1}\left(\tilde{\mathit{x}}\right))=\mathit{K}({\mathit{u}}_1,\tilde{\mathit{x}})={\mathbf{\alpha }}_1^{\prime }\mathit{K}(\mathit{A},\tilde{\mathit{x}})-{\mathbf{\beta }}_1^{\prime }\mathit{K}(\mathit{C},\tilde{\mathit{x}})-{\nu }_1{\mathit{e}}_{-}^{\prime }\mathit{K}(\mathit{B},\tilde{\mathit{x}})\end{array}$$

  (60)

  and

  $$\begin{array}{c}\hfill f_{\varphi 2}\left(\tilde{\mathit{x}}\right))=\mathit{K}({\mathit{u}}_2,\tilde{\mathit{x}})=-{\mathbf{\alpha }}_2^{\prime }\mathit{K}(\mathit{B},\tilde{\mathit{x}})+{\mathbf{\beta }}_2^{\prime }\mathit{K}(\mathit{C},\tilde{\mathit{x}})+{\nu }_2{\mathit{e}}_{+}^{\prime }\mathit{K}(\mathit{A},\tilde{\mathit{x}})\end{array}$$

  (61)

5. Numerical Experiments

5.1. Experimental Setting

To demonstrate the validity of MNP-KSVC, we perform extensive experiments on several benchmark datasets that are commonly used for testing machine learning algorithms. In experiments, we focus on comparing MNP-KSVC and four state-of-the-art multiclass models—Multi-SVM, MBSVM, MTPMSVM, and Twin-KSVC—detailed as follows:

• Multi-SVM [38]: The idea is similar to the “one-versus-all” SVM [3]. However, it generates K binary SVM classifiers by solving the one large dual QPP. That is, the k-th classifier is trained with the k-th class instances encoded with positive labels and the remaining class instances with negative labels. Then, the label of an unseen instance is assigned by the “voting” scheme. The penalty parameter for each classifier in Multi-SVM is c.
• MBSVM [33]: It is the multiclass extension of the binary TWSVM, which is based on the “one-versus-all” strategy. MBSVM aims to find K nonparallel hyperplanes by solving K QPPs simultaneously. Specifically, the k-th class instances are as far away as the k-th hyperplane while the remaining instances are proximal to the k-th hyperplane. An unseen instance is assigned to the label depending on to which of the K hyperplanes it lies farthest away. The penalty parameter for each classifier in MBSVM is c.
• MTPMSVM: Inspired by MBSVM [33], we use the “one-versus-all” strategy to implement the multiclass version of TPMSVM [15] as a baseline. In contrast to MBSVM, it aims to find K parametric-margin hyperplanes, such that each hyperplane is closer to its corresponding class instances and as far away from the remaining class instances. The penalty parameters for each classifier in MTPMSVM are $(\nu ,c)$.
• Twin-KSVC [35]: It is another novel multiclass extension of TWSVM. Twin-KSVC evaluates all the training instances in a “one-versus-one-versus-rest” structure with the ternary output $\{-1,0,+1\}$. It aims to find a pair of nonparallel hyperplanes for each of two kinds of samples selected from K classes. The remaining class instances are mapped into a region within these two nonparallel hyperplanes. The penalty parameters for each classifier in Twin-KSVC are $(c_1,c_2,c_3,c_4,\epsilon )$.

All methods are implemented by MATLAB on a PC with an i7 Intel Core processor with 32 GB RAM. The quadratic programming problems (QPPs) of all the classifiers are solved by the “quadprog” function in MATLAB. Now, we describe the setting of our experiments:

• Similar to [35,38], we use multiclass accuracy to measure each classifier, defined as

  $$\mathrm{accuracy}=\frac{1}{N}\sum _{k=1}^K\sum _{\mathit{x}\in {\mathcal{I}}_k}I\left(\widehat{g}\left(\mathit{x}\right)=k\right)$$

  (62)

  where N is the scalar of the dataset, K is the total classes, $\widehat{g}\left(x\right)$ is the prediction of the classifier, and $I(·)$ is an indicator function, which returns 1 if the class matches and 0 otherwise. Moreover, we adopt training time to represent the learning efficiency.
• To reduce the complexity of parameter selection for multiclass classifiers, we use the same parameter setting for each learning subproblem. Specifically, we set the same for all classifiers c in MBSVM and MBSVM, $\nu ,c$ in MTPSVM, $c_1=c_2,c_3=c_4$ in Twin-KSVC, and ${\nu }_1={\nu }_2,c_1=c_2,c_3=c_4$ in MNP-KSVC. For the nonlinear case, the RBF kernel $\mathit{K}({\mathit{x}}_i,{\mathit{x}}_j)=\exp \left(\frac{\parallel {\mathit{x}}_i-{\mathit{x}}_j{\parallel }^2}{\gamma }\right)$ is considered, where $\gamma >0$ is the kernel parameter.
• It is usually unknown beforehand which parameters are optimal for classifiers at hand. Thus, we employ the 10-fold cross-validation technique [3] for parameter selection. In detail, each dataset is randomly partitioned into 10 subsets with similar sizes and distributions. Then, the union of 9 subsets is used as the training set, while the remaining 1 is used as the testing set. Furthermore, we apply the grid-based approach [3] to obtain the optimal parameters of each classifier. Namely, the penalty parameters $c,c_1,c_2,\nu ,{\nu }_1$ and the kernel parameter $\gamma$ are selected from $\left\{2^i\right|i=-6,\dots ,6\}$, while the margin parameter $\epsilon$ is chosen from $\left\{i\right|i=0.1,0.2,\dots ,0.9\}$. Once selected, we return them to learn the final decision function.

5.2. Result Comparison and Discussion

For comparison, we consider 10 real-world multiclass datasets from the UCI machine learning repository (the UCI datasets are available at http://archive.ics.uci.edu/ml (accessed on 10 September 2021)), whose statistics are summarized in

Table 1. Statistics for benchmark datasets used in experiments. # denotes the corresponding quantity.

Datasets	#Instances	#Training	#Testing	#Attributes	#Class
Balance	625	438	187	4	3
Ecoli	327	229	98	7	5
Iris	150	105	45	4	3
Glass	214	150	64	13	6
Wine	178	125	53	13	3
Thyroid	215	150	65	5	3
Dermatology	358	251	107	34	6
Shuttle	2175	1522	653	9	5
Contraceptive	1473	1031	442	9	3
Pen Based	1100	770	330	16	10

. These datasets represent a wide range of domains (include phytology, bioinformatics, pathology, and so on), sizes (from 178 to 2175), features (from 4 to 34), and classes (from 3 to 10). All datasets are normalized before training such that features are transformed into $[-1,1]$. Moreover, we carry out experiments as follows. Firstly, each dataset is divided into 2 subsets: 70% for training and 30% for testing. Then, we train classifiers with 10-fold cross-validation executions. Finally, we predict the testing set with the fine-tuning classifiers. Each experiment is repeated 10 times.

Table 2. Performance comparison on benchmark datasets for linear classifiers, in terms of $\mathbf{mean}\pm \mathbf{std}$ of the testing multiclass accuracy (%). The Win/Loss (W/L) denotes the number of datasets for which MNP-KSVC is superior/inferior to the compared classifiers. Ave. Acc and rank denote each classifier’s average accuracy and rank over all datasets.

Datasets	Multi-SVM	MBSVM	MTPMSVM	Twin-KSVC	MNP-KSVC
Balance	79.91 ± 4.86	86.14 ± 4.63	87.43 ± 3.56	86.64 ± 1.92	88.33 ± 2.03
Ecoli	72.32 ± 7.03	73.62 ± 4.95	73.77 ± 4.33	74.62 ± 3.86	75.91 ± 2.52
Iris	93.24 ± 2.66	92.96 ± 2.24	93.21 ± 2.53	92.69 ± 3.24	94.13 ± 2.49
Glass	69.18 ± 9.85	72.89 ± 7.28	68.68 ± 6.79	71.65 ± 5.96	71.38 ± 5.38
Wine	93.24 ± 3.02	95.28 ± 1.46	98.19 ± 1.61	97.23 ± 1.12	97.14 ± 1.27
Thyroid	90.24 ± 2.53	93.74 ± 1.58	92.92 ± 1.43	96.97 ± 1.08	97.52 ± 1.54
Dermatology	81.82 ± 3.79	86.67 ± 1.69	84.46 ± 3.29	90.37 ± 2.32	89.06 ± 3.16
Shuttle	71.58 ± 4.78	84.04 ± 2.92	77.17 ± 3.3	78.76 ± 4.81	83.16 ± 1.92
Contraceptive	38.53 ± 3.76	43.95 ± 2.51	44.65 ± 2.93	42.25 ± 2.45	44.22 ± 2.03
Pen Based	79.59 ± 3.75	85.94 ± 1.26	81.94 ± 2.04	83.21 ± 2.77	86.78 ± 1.37
Ave. Acc	76.97	81.52	80.24	81.43	82.76
W/L	10/0	8/2	8/2	9/1	/
Ave. rank	4.6	2.9	3.1	2.67	1.7

and

Table 3. Performance comparison on benchmark datasets for nonlinear classifiers, in terms of the $\mathbf{mean}\pm \mathbf{std}$ of the testing multiclass accuracy (%). The Win/Loss (W/L) denotes the number of datasets for which MNP-KSVC is superior/inferior to the compared classifiers. Ave. Acc and rank denote each classifier’s average accuracy and rank over all datasets.

Datasets	Multi-SVM	MBSVM	MTPMSVM	Twin-KSVC	MNP-KSVC
Balance	79.94 ± 5.57	87.13 ± 4.57	89.92 ± 3.27	90.17 ± 4.08	91.41 ± 3.42
Ecoli	79.81 ± 5.19	80.82 ± 4.25	84.74 ± 3.49	80.12 ± 4.49	84.59 ± 3.83
Iris	90.26 ± 2.65	96.89 ± 1.83	97.39 ± 2.14	94.36 ± 2.03	98.04 ± 1.47
Glass	58.66 ± 4.76	52.64 ± 4.08	62.73 ± 3.95	56.01 ± 4.26	64.12 ± 2.98
Wine	94.36 ± 2.12	94.31 ± 1.87	98.38 ± 2.62	97.26 ± 1.61	98.04 ± 1.45
Thyroid	91.82 ± 1.75	93.27 ± 1.95	95.34 ± 0.89	94.14 ± 1.05	95.63 ± 0.84
Pen Based	86.53 ± 3.93	89.51 ± 3.29	85.06 ± 3.68	86.12 ± 2.47	88.78 ± 2.68
Dermatology	84.43 ± 4.29	83.82 ± 3.86	84.51 ± 2.64	83.33 ± 3.29	85.26 ± 3.12
Shuttle	74.36 ± 3.39	83.74 ± 2.73	87.06 ± 2.89	86.91 ± 2.38	89.37 ± 1.73
Contraceptive	42.09 ± 4.95	44.28 ± 4.02	45.93 ± 3.85	47.51 ± 3.57	47.47 ± 3.68
Ave. Acc	78.22	80.64	83.11	81.59	84.27
W/L	10/0	9/1	8/2	9/1	/
Ave. rank	4.3	3.69	2.3	3.3	1.4

contain a summary of learning results for the proposed MNP-KSVC model with other compared methods using linear and nonlinear kernels, respectively. The results on 10 benchmark datasets include the mean and standard of the testing multiclass accuracy (%), whose best performance is highlighted in bold. The comparison results reveal the following:

• MNP-KSVC yields better performance than other classifiers in terms of accuracy on almost all datasets. This confirms the efficacy of the proposed MNP-KSVC on the multiclass learning tasks.
• Nonparallel based models (MBSVM, MTPMSVM, Twin-KSVC, and MNP-KSVC) outperform the traditional SVM model. The reason is that SVM simply utilizes the parallel hyperplanes to learn the decision function, leading to less capability to capture the underlying multiclass distributions.
• MNP-KSVC has a better generalization ability than MBSVM and Twin-KSVC in most cases. For instance, MNP-KSVC obtains a higher accuracy (84.59%) than MBSVM (80.82%) and Twin-KSVC (80.12%) on the Ecoli dataset in the linear case. Similar results can be obtained from the other datasets. Since MBSVM and Twin-KSVC simply implement empirical risk minimization, they are easy to overfit. The regularization terms are considered in our MNP-KSVC, which regulates the model complexity to avoid overfitting.
• MTPMSVM is another multiclass extension, which is based on the “one-versus-rest” strategy. With the help of the “hybrid classification and regression” learning paradigm, our MNP-KSVC can learn more multiclass discriminate information.
• Furthermore, we count the number of Superior/Inferior (W/L) instances to the compared classifier on all datasets for both linear and nonlinear cases, listed at the bottom of Table 2 and Table 3. The results indicate that MNP-KSVC achieves the best results against others in terms of both W/L and average accuracy.

To provide more statistical evidence [39,40,41], we have further performed the non-parametric Friedman test to check whether there are significant differences between MNP-KSVC and other compared classifiers. The bottom lines of Table 2 and Table 3 list the average ranks of each classifier calculated by the Friedman test according to multiclass accuracy. Results show that MNP-KSVC has the first rank in linear and nonlinear cases, followed by NPSVM and RPTSVM successively. Now, we calculate the ${\mathcal{X}}_F^2$ value for the Friedman test as

$$\begin{array}{c}\hfill {\mathcal{X}}_F^2=\frac{12\times N}{k(k+1)}\left[\sum _{i=1}^k{r}_i^2-\frac{k{(k+1)}^2}{4}\right]\end{array}$$

(63)

where N is the number of datasets, k is the number of classifiers, and $r_i$ is the average rank on N datasets for the i-th model. For the linear case, we compute term ${\sum }_{i=1}^k{r}_i^2$ in Table 2 as

$$\begin{array}{c}\hfill \begin{array}{cc}{\displaystyle \sum _{i=1}^k{r}_i^2}\hfill & ={4.6}^2+{2.9}^2+{3.1}^2+{2.7}^2+{1.7}^2\hfill \\ & \approx 49.1989\hfill \end{array}\end{array}$$

(64)

Then, substituting $k=5$, $N=10$ and (64) into (63), we have

$$\begin{array}{c}\hfill \begin{array}{c}{\mathcal{X}}_F^2=\frac{12\times 10}{5(5+1)}\left[49.1989-\frac{5{(5+1)}^2}{4}\right]\approx 16.7956\hfill \end{array}\end{array}$$

(65)

Based on the above Friedman statistic ${\mathcal{X}}_F^2=16.7956$, we calculate the F-distribution statistic ${\mathcal{F}}_F$ with $(k-1,(k-1\left)\right(N-1\left)\right)=(4,36)$ degrees of freedom as

$$\begin{array}{c}\hfill {\mathcal{F}}_F=\frac{(N-1)\times {\mathcal{X}}_F^2}{N(k-1)-{\mathcal{X}}_F^2}=\frac{9\times 16.7956}{10\times 4-16.7956}\approx 6.5143\end{array}$$

(66)

Moreover, we compute the p-value, which rejects the null hypothesis at the level of significance $\alpha =0.05$. Similarly, we calculate the statistic for the nonlinear case, as summarized in

Table 4. Results of Friedman test on learning results.

	Statistic ${\mathcal{X}}_{\mathit{F}}^2$	p-Value	Hypothesis
Linear	6.5143	2.9503 × 10−4	reject
Nonlinear	10.2004	1.2267 × 10−5	reject

. The results reject the null hypothesis for both linear and nonlinear cases and reveal the existence of significant differences in the performances of classifiers.

Furthermore, we record the average learning time of each classifier for the above UCI datasets experiments, as shown in Figure 2 and Figure 3. The results show that our MNP-KSVC is faster than Multi-SVM and Twin-KSVC, while slightly slower than MBSVM and MTPMSVM for linear and nonlinear cases. Multi-SVM performs the slowest of all classifiers because Multi-SVM needs to solve larger problems than the nonparallel-based classifiers. Moreover, the Hessian matrix of dual QPPs in MNP-KSVC avoids the time-costly matrix inversion, leading to greater effectiveness than Twin-KSVC. Overall, the above results confirm the feasibility of Twin-KSVC.

6. Discussion and Future Work

This paper proposes a novel K multiclass nonparallel parametric-margin support vector machine, termed MNP-KSVC. Specifically, our MNP-KSVC has the following attractive merits:

• For the K-class learning task, our MNP-KSVC first transforms the complicated multiclass problem into $K(K-1)/2$ subproblems via a “one-versus-one-versus-rest” strategy. Each subproblem focuses on separating the two selected classes and the rest of the classes. That is, we utilize $\{-1,1\}$ to represent the label of the two selected classes and 0 to label the rest. Unlike the “one-versus-all” strategy used in Multi-SVM, MBSVM, and MTPMSVM, this encoding strategy can alleviate the imbalanced issues that sometimes occur in multiclass learning [32,35].
• For each subproblem, our MNP-KSVC aims to learn a pair of nonparallel parametric-margin hyperplanes (36) with the ternary encoding $\{-1,0,+1\}$. These parametric-margin hyperplanes are closer to their corresponding class and at least one distance from the other class. Meanwhile, they restrict the rest of the instances into an insensitive region. A hybrid classification and regression loss joined with the regularization is further utilized to formulate the optimization problems (10) and (11) of MNP-KSVC.
• Moreover, the nonlinear extension is also presented to deal with the nonlinear multiclass learning tasks. In contrast to MBSVM [33] and Twin-KSVC [35], the linear and nonlinear models in MNP-KSVC are consistent. Applying the linear kernel in the nonlinear problems (44) and (45) results in the same formulations as the original linear problems (14) and (15).
• Extensive experiments on various datasets demonstrate the effectiveness of the proposed MNP-KSVC compared with Multi-SVM, MBSVM, MTPMSVM, and Twin-KSVC.

There are several interesting directions to research in the future, such as extensions to semi-supervised learning [26,42], multi-label learning [22], and privilege-information learning [43].