A Unified Framework for Multiclass and Multilabel Support Vector Machines

Multilabel classification is a generalization of the well known multiclass problem in supervised learning and is consequently more challenging. Some of the challenges in the multilabel setting include, but are not limited to, exponential growth of cardinality of possible label sets, correlation among labels, structured label spaces and severely unbalanced datasets. Multilabel classification has already seen many real-world applications such as scene labeling [4], functional genomics analysis [61, 33] and text categorization [25, 38, 27, 43].

The rising number of applications has led to the development of multilabel learning as a new supervised learning paradigm [16]. Many approaches have been proposed in the literature to tackle multilabel classification problems within the support vector machine (SVM) framework. Despite the plethora of approaches and algorithms, we assert that no straightforward (natural) extension of the SVM has hitherto been proposed for multilabel classification. The SVM was first introduced as a two-class, single label (binary) classifier based on maximum margin geometry (and regularized error minimization) [3, 8, 58]. Since then, the binary SVM has been studied extensively and applied successfully in many different domains. However, its extension to multiclass and multilabel cases is still an ongoing research problem since there is neither consensus nor a majoritarian approach.

In this work, we first attempt to justify the need to revisit the two-class (binary) SVM framework. Subsequently, we investigate the multilabel problem from a unified large margin perspective. We propose a novel formulation based on a geometric reinterpretation of the binary SVM which has a natural extension resulting in a unified multiclass and multilabel classification framework. Our proposed method is also capable of dealing with the aforementioned class imbalance problem in classification tasks.

Multilabel classification approaches mainly fall into the two categories of problem transformation and algorithm adaptation. An intuitive way to handle multilabel classification tasks is to transform them into a series of binary classification problems and then use—as a method of solution—one of the existing binary classifiers (including binary SVM) to solve them. Algorithm adaptation approaches, on the other hand, solve the problem directly by extending binary classification methods in such a way that all classes are considered at once. Our method falls into the category of algorithm adaptation for multilabel (and multiclass) classification—within the SVM framework. In this paper, we therefore focus mainly on SVM-based approaches to multiclass and multilabel problems and mention other approaches (available in the literature) only as required.

Below, we describe the basic idea behind our multilabel SVM formulation. A more formal description is elaborated in Section 3. The main reason for presenting a précis is to quickly get to the (simple) idea behind the formulation.

If the dataset is assumed to be linearly separable, then there are infinitely many hyperplanes which can separate the patterns into two classes. The main idea of the binary SVM is to choose a hyperplane which is optimal in the sense of maximizing the margin between the two sets of patterns while being somewhat robust to outliers. Given the finite set of patterns

subset $C_{1}\left(y=1\right)$ is linearly separable from subset $C_{2}\left(y=-1\right)$ by hyperplane $v^{T}x=c$ if there exist both a unit vector $v$ and constant c such that for all training instances, $y_{i}(v^{T}x_{i})>c$. Vapnik [58] shows that the optimal solution $\left(v^{*}\right)$ to the following optimization problem is a unit normal vector of the hyperplane with maximum margin:

where the assumption is that the patterns of these two classes are linearly separable, i.e., $y_{i}\left(v^{T}x_{i}\right)>c,i\in\left\{1,2,\ldots,N\right\}$ for some vector $v$ and constant $c$. The optimal unit vector $\left(v^{*}\right)$ along with constant

determine the maximum margin hyperplane. It is also proved that the maximum margin (optimal) hyperplane is unique [58]. Furthermore, the optimization problem in (1) can be equivalently formulated as finding a pair—vector $w$ and bias (threshold) $b$–such that $w$ has the smallest $\ell_{2}$ norm and constraints $y_{i}\left(w^{T}x_{i}\right)+b\geq 1$ are satisfied for all training patterns [58]:

Patterns for which the inequality constraints in (2) become active (equality constraints) are of particular importance. These points locate the optimal hyperplane and are known as support vectors and hence the name support vector machine. Cortes and Vapnik [8] extended this problem to the case where the two classes are not linearly separable by relaxing the hard margin constraints in (2) and letting some patterns violate the margin:

The optimization problem in (3) is known as the soft margin SVM. Solving for $\{\xi_{i}\}$ in terms of the other variables, we get the following hinge loss in objective function which is an upper bound convex approximation to the zero-one misclassification loss function:

The essential idea behind our multilabel (and multiclass) formulation was inspired by the optimization problem in (1) which can be reformulated as

and furthermore, equivalently written as

We have introduced an origin $x_{0}$ and wish to point out that reconfiguring the training set with respect to this origin does not change the optimal solution to the problem in (1). In fact, Vapnik’s original formulation in (1) is relative. Therefore, adding $\left(v^{T}x_{0}\right)$ to both terms in the optimization problem in (1) does not change the optimal solution. In Vapnik’s equivalent formulation (2), the origin is implicitly introduced via a bias term $b$ by transitioning from the relative formulation in (1). Furthermore, we are effectively considering a separate hyperplane for each class which results in the two hyperplanes becoming parallel in this formulation with the addition of a sum-to-zero constraint on the normal vectors $(v+(-v)=O)$. As we will see in Section 3, there is no necessity to have a sum-to-zero constraint on the normal vectors (of hyperplanes). When this is relaxed, it yields nonparallel separating hyperplanes in two-class problems. While it may seem odd to have twin, nonparallel hyperplanes in a two-class problem, as we later show, it becomes a useful construct in the multilabel setting.

Having presented the basic idea—nonparallel hyperplanes—we turn to a quick description of related work in order to forestall impressionistic notions of similarity to previous work. The twin SVM (TWSVM) also departs from parallel hyperplanes for the two-class problem [24]. However, it is neither a maximum margin formulation nor an all-in-one machine since it solves two separate optimization problems for binary classification. Mangasarian and Wild [37] proposed a generalized eigenvalue proximal SVM (GEPSVM) which deviates from a previous proximal SVM (PSVM) [15] with parallel hyperplanes. This approach also solves two separate optimization problems for obtaining the separating hyperplane of each class in binary classification. The normal vector of each of the two nonparallel proximal hyperplanes is the eigenvector corresponding to the smallest eigenvalue of a generalized eigenvalue problem.

Our approach is also different from the one-class SVM which is an unsupervised algorithm for outlier (novelty) detection [46, 54]. In the one-class SVM, training data is available for only one class and the goal is to decide whether a new pattern belongs to this class. The one-class SVM introduced in [46] is a natural extension of SVM to the case of unsupervised learning and all the patterns are separated from the origin of the feature space by a hyperplane with maximum margin. Depending on which side of the hyperplane a point falls, it is classified either as a member (of that class) or as an outlier. Whether or not this problem could be formulated for a two-class problem with outliers without the oppositional framework has not been investigated. This approach does not consider the multilabel problem (or even multiclass for that matter). Our model simultaneously addresses multiclass and multilabel problems with the origin implicitly determined by the support vectors of all classes in feature space. In particular, our problem formulation is based on a unique and novel geometry for simultaneously maximizing the margins of all classes in the multiclass and multilabel settings. In order to better demonstrate the advantages of our approach, we mainly focus on large margin formulations in the literature.

The outline of paper is as follows. In Section 2 we review previous work focused on multiclass and multilabel problems mostly within the SVM framework. In Section 3, the new formulation is presented and a quadratic majorizer for the hinge loss is used to solve the optimization problem in the primal. In Section 4, the nonlinear transformation of the input space to infinite dimensional spaces via reproducing kernel Hilbert spaces (RKHS) is discussed and the majorization algorithm extended to solve the primal kernel formulation. In Section 5, we present illustrative experiments and the results of our formulation on multiclass and multilabel datasets. We also discuss a scenario which widely used approaches are not able to handle but is easily handled in our formulation. Section 6 presents the conclusions and speculates on future possibilities and extensions.

In Section 1, we motivated the unified framework by jettisoning the parallel hyperplane constraint which is standard in almost all binary (two-class) SVMs. Furthermore, we introduced an origin variable $x_{0}$ and set up the margin constraints using this new variable. The picture that emerges from this description is of individual class-specific weight vectors $(\left\{w_{k}\right\})$ which seek to satisfy margin constraints for the patterns belonging to that class. This is repeated for all classes. However, this alone does not ensure competition between classes which is enshrined using parallel hyperplanes in the standard SVM. In our formulation, we introduce competition by minimizing the inner product between all pairs of weight vectors. Note that the minimum inner product between two unit weight vectors $w_{k}$ and $w_{l}$ is attained when the two vectors are anti-parallel (as in the standard SVM). Later, in Section 3.5, we show that suitable constraints on a pair of weight vectors $w_{1}$ and $w_{2}$ in a two-class problem, make our formulation completely equivalent to the standard binary SVM.

In common with virtually all previous soft margin approaches, the objective function includes regularization and outlier rejection terms [8]. As mentioned above, in addition to the margin term for each weight vector $w_{k}$, we have the sum of all pairwise inner products between weight vectors $w_{k}$ and $w_{l}$ which endeavor to make the weight vectors anti-parallel. Thus far, we have not discussed the bias term in this set up. When we introduced the origin $x_{0}$ as a variable in (4), we ended up with two terms that canceled each other out: $v^{T}x_{0}$ and $-v^{T}x_{0}$ which assumes anti-parallel hyperplanes. In a two-class multilabel SVM, these become $b_{1}\equiv-w_{1}^{T}x_{0}$ and $b_{2}\equiv-w_{2}^{T}x_{0}$. We then have the option of enforcing a hard constraint $b_{1}+b_{2}=0$ or a soft constraint term $\left(b_{1}+b_{2}\right)^{2}$ to be mimimized as part of objective function. For problem formulation with more than two classes, the former option is selected in this work since it was practically demonstrating better performance in both linear and kernel cases and is fully demonstrated in appendices. The other case can be similarly worked out. From a conceptual perspective, a hard constraint on the biases is an extension of the anti-parallel hyperplanes constraint, whereas the soft constraint on the biases is a relaxation of the same. A candidate multilabel (and multiclass) optimization problem is

where the first constraint is the hard constraint on biases and the second set of constraints are margin violation constraints obtained by introducing outlier (slack) variables [8]. The first term in the objective function relates to margin maximization, the second term implicitly models pairwise label correlations and the last term penalizes deviation of patterns from their corresponding class margin. The regularization parameters, $\alpha$,$\;\beta>0$, have standard objective function semantics. We reformulate the optimization problem in (5) by eliminating all the outlier variables via hinge losses and introducing the bias variables $b_{k}\equiv-w_{k}^{T}x_{0}$:

where we define $W=\left\{w_{1},w_{2},...,w_{K}\right\}$ as the set comprising all the normal vectors to the hyperplanes and $b=\left\{b_{1},b_{2},...,b_{K}\right\}$ as the set of biases. The hard constraint on biases is incorporated into the objective function of (6) by the method of Lagrange multipliers and results in the following Lagrangian (where $\lambda$ is a Lagrange multiplier):

This is by no means the only available integrated formulation. In Section 3.4, we examine all four possibilities: the cross product space of soft and hard constraints on the hyperplanes and soft and hard constraints on the biases. We also have considered the margins as in the conventional SVM. However, it is possible to incorporate margin-related variables in the formulation by setting up the problem similar to the $\nu$-SVC [45].

After solving the optimization problem and obtaining the classifiers, a test instance is projected to each weight vector. We employ a simple decision criterion wherein each test instance gets assigned all class labels with projection greater than $1$, i.e., if $S_{t}$ denotes the set of labels for test instance $x_{t}$, then

From a geometric point of view, we have an ambiguous region which is inhabited by patterns whose projections are all less than 1. Therefore the decisions on label assignment could include this information. In the present work however, we eschew careful examination of pattern and label test set geometry and relegate this to future work. Instead, when this situation occurs, we revert to a multiclass strategy and pick the label corresponding to the maximum projection as explained below.

In the multiclass (single label) setting, a winner-take-all strategy (as mentioned above) is applied and the test pattern is assigned to the class with maximum projection value

Most of the existing literature on SVM optimization is focused on formulating the primal problem from which the dual formulation is extracted followed by a solution in dual space. However, primal problems can also be efficiently solved. In fact, solving the primal may have advantages for large scale optimization since—at least in the linear SVM—the objective function is linear in the training set patterns (and not quadratic). Furthermore, often in large scale optimization, an approximate solution is sought which results in a large number of support vectors. In this case, the dual may result in a solution which is not meaningful [6].

One of the most simple and effective algorithms for solving the primal is majorization-minimization (MM). The main advantage of iterative majorization for the SVM is that it results in simple linear system updates (achieved without the need for line-search parameter tuning). A secondary advantage of MM is that the objective function value is guaranteed to be non-increasing and is generally decreasing in each iteration. If the function to be optimized is strictly convex which is the case with the SVM loss function, MM converges to the global minimum. In contrast, other methods which solve the dual must often completely converge in order to obtain a meaningful and reasonable solution. Variants of MM have also been proposed which deal with large-scale optimization problems.

Consider the standard, linear, binary SVM in the primal. It comprises a margin term and the hinge loss on the patterns. An alternative to majorization is to smooth the hinge loss (resulting in a differentiable approximation like the Huber loss). However, in this case, we are minimizing a different function which is an approximation to the original function. Furthermore, the smoothed hinge loss does not result in simple update equations (achieved without having to estimate a step-size parameter). Even if we approximate the hinge loss with the generalized logistic loss $g_{\beta}(x)=\frac{1}{\beta}\text{log}(1+\text{exp}\{\beta(1-x)\})$ (which approaches $[1-x]_{+}$ as $\beta\rightarrow\infty$), we would still need to use nonlinear optimization on this logistic regression variant in order to obtain good solutions. Finally, the non-differentiability of the hinge loss forces us to adopt subgradient optimization which is also complex (from a line search perspective). For these reasons, we introduce a simple MM approach to minimize the SVM objective in our unified framework. Clearly, alternatives are available (including minimization in the dual) but we have relegated these to future work.

Majorization leads to a particular kind of iterative optimization algorithm. The basic idea behind majorization is to construct an auxiliary objective function which lies above the original objective function and is easier to minimize. The auxiliary objective function usually has the property of touching the original objective at the current time (iteration) instant. By descending on the auxiliary objective, we guarantee that we also descend on the original objective by virtue of the fact that the auxiliary objective is strictly greater than or equal to the original [31]. For the task at hand, note that MM can specifically deal with nondifferentiable convex objective functions (like the hinge loss) by constructing a sequence of smooth convex functions which majorize the original nonsmooth objective function. A brief formal description of MM follows. A function $g(x,x_{k})$ majorizes $f\left(x\right)$ at $x_{k}$ if

which means that $g(x,x_{k})$ lies above $f\left(x\right)$ everywhere and touches $f(x)$ at least at $x_{k}$ where $x_{k}$ is a point in the domain of $f(x)$ at the current iteration. Now we minimize the surrogate function $g\left(x,x_{k}\right)$ instead of $f\left(x\right)$ in the minimization version of the MM algorithm. If $x_{k+1}$ is the minimum of $g\left(x,x_{m}\right)$, then the descent property follows from (8). From the descent property, we see that it is possible to merely descend on $g$ instead of finding its global minimum:

There exist previous approaches which solve the SVM in the primal using MM [18, 19, 39, 57]. For example, [18] have a majorization approach which considers different loss functions (hinge, quadratic, Huber). We follow [10] in our approach. [18] and [10] show that the hinge loss $[1-u]_{+}:=\textup{$\min$}(0,1-u)$ is majorized by the following quadratic (in $u$):

where $z>0$. It is shown that $g$ is the best quadratic majorizer for $\left[1-u\right]_{+}$ [10]. Theoretically, it is possible to get arbitrarily as close as possible to the hinge loss through the above quadratic majorizer. In practice however, we choose a very small positive threshold value $\epsilon$ for $z$, i.e., $z\geq\epsilon$ for the sake of numerical stability. Here $z$ is an auxiliary variable. Assuming (for the sake of convenience) that $z$ is unconstrained (instead of requiring a positivity constraint), the derivative of $g(u,z)$ w.r.t. $z$ is

Setting this to zero yields $z^{2}=(1-u)^{2}$ from which we obtain $z=\left|1-u\right|$ which is non-negative and is equal to zero when $u=1$. It can easily be shown that setting $z=\epsilon$ when $|1-u|<\epsilon$ is the global minimum for $z$ (when $z$ is constrained to be greater than or equal to $\epsilon$). We can therefore use the above majorization trick to obtain a quadratic objective w.r.t. $u$. Note that $g(u,z)$ will be replaced by a suitable function of $w_{k}$ and $b_{k}$ in the formulation. The majorized multiclass/multilabel SVM optimization problem can be written as

where $Z$ denotes the set of all strictly positive auxiliary variables $\left\{z_{ki}\right\}$. In order to simplify the notation in the optimization problem in (9), we concatenate $w_{k}$ and $b_{k}$ into one vector and define the following matrices:

where $M$ is the number of features. With these changes and defining the set of augmented weight vectors $\widetilde{W}=\left\{\widetilde{w}_{1},\ldots,\widetilde{w}_{K}\right\}$, we may rewrite the optimization problem as

and again by including the hard constraint on biases into the objective function via the method of Lagrange multipliers, the Lagrangian can be written as

Rather than solving for $\widetilde{W}$, we concatenate all the augmented weight vectors $\widetilde{w}_{k}$ into one vector $\widetilde{w}=\left[\widetilde{w}_{1}^{T},\widetilde{w}_{2}^{T},\ldots,\widetilde{w}_{K}^{T}\right]^{T}$ and alternate between least-squares solutions for $\widetilde{w}$ and closed-form solutions for $Z$. The solution for $Z$ follows the approach outlined above:

The solution for the concatenated weight vector $\widetilde{w}$ merely requires some turgid algebra and is relegated to Appendix A. The pseudo code of the algorithm is presented in Algorithm 1. We briefly mention here that the regularization coefficients for soft constraints on weight vectors $\left(\alpha\right)$ and hinge loss terms $\left(\beta\right)$ should be chosen in such a way that the Hessian obtained after concatenating the weight vectors is positive definite (as shown in Appendix A).

The formulation in the previous section imposed a soft constraint on the hyperplane normal vectors, wherein the inner product of every pair of vectors was minimized. Furthermore, a hard constraint on the biases $b_{k}$ was used to make their sum equal to zero. However, depending on the problem and dataset, we could also consider hard constraints on both the normal vectors $\left(\sum_{k=1}^{K}w_{k}=0\right)$ and the biases $\left(\sum_{k=1}^{K}b_{k}=0\right)$. Table 1 provides the four different possibilities for incorporating the constraints into the formulation. For the sake of simplicity, we omit the margin terms and hinge loss terms which are common to all cases. In all these models, hyperparameters should be chosen in such a way that the Hessian of the objective function remains positive definite, ensuring that the optimization problem remains bounded from below. The details of the formulation specific to the Hessian for the case of soft $w$-hard $b$ are relegated to Appendix A.

The original two-class soft margin SVM problem is equivalent to the minimization of the following objective function:

Note that we have used $w^{T}w$ instead of $\frac{1}{2}w^{T}w$ since the equivalence will be shown using two hyperplanes. From (14), we see that the existence of two hyperplanes with equal norms and anti-parallel normal vectors is implicit within the standard soft margin binary SVM formulation. The original binary SVM is equivalent to our formulation by imposing hard constraints on $w$ and $b$:

Incorporating these constraints into the objective function, we get

which is identical to (14). We have shown that when hard constraints are imposed on two weight vectors (making them anti-parallel but with equal norm) and on the two biases (making them sum to zero), we recover the original soft margin SVM. Furthermore, our soft $w$-hard $b$ model (shown in Table 1)—while providing a degree of flexibility to the weight vectors’ orientations and norms—is still capable of producing parallel hyperplanes (anti-parallel weight vectors) when the optimal solution dictates this to be the case. Consider the following example which is designed in such a way that the optimal solution must be two parallel hyperplanes. As shown in Figure 1, for any $\alpha\in\left[1,2\right]$, we get parallel hyperplanes and the solution coincides with the binary SVM.

Kernels were introduced as a tool to map a nonlinearly separable dataset into an implicit higher (or infinite) dimensional reproducing kernel Hilbert space (RKHS) $\mathcal{H}$ where linear separability can be achieved without the need to explicitly compute the features in the transformed space [59]. In order to adapt our formulation to an RKHS, two problems have to be dealt with before we can proceed. As we will show, the origin of the RKHS needs to be properly treated and correctly interpreted in an infinite dimensional Hilbert space. Furthermore, the inclusion of a hard constraint on the weight vectors is not as straightforward as in the linearly separable case. We first briefly summarize how RKHS kernels are used in the SVM context.

Deploying a kernel function $\kappa:X\times X\rightarrow\mathbb{R}$, the inner product of feature mappings in a high dimensional RKHS is performed by function evaluation in the original space. If $\phi:X\rightarrow\mathbb{\mathcal{H}}$ is a mapping from the original space to a feature space, i.e., $X\ni x\mapsto\phi(x):=\kappa(\cdot,x)\in\mathbb{\mathcal{H}}$, then

By the representer theorem [28], each weight vector $w_{k}$ can be written as a linear combination of all projected patterns $\phi(x_{i}):=\kappa(\cdot,x_{i})$ in RKHS,

If we define $S_{W}$ as the subspace spanned by $W=\left\{w_{1},w_{2},\cdots,w_{K}\right\}$, i.e.,

we can write $x_{0}$ (the origin in the infinite dimensional feature space) as a summation of elements in $S_{W}$ and an element in the orthogonal complement of $S_{W}$, i.e., $S_{W}^{\perp}$

However, in calculating $\left\langle w_{k},x_{0}\right\rangle$, the inner product of all elements in $S_{W}^{\perp}$ taken with $w_{k}$ vanishes. Therefore, we consider only the $S_{W}$ component of $x_{0}$. Replacing $w_{k}$ in $x_{0}$ with (15), we get

In our application of RKHS principles, we need to compute the following inner products with respect to some kernel in RKHS:

where $G$ is the Gram matrix formed by the set of pairwise RKHS inner products of patterns. Also, we have

where $g_{i}$ is the $i^{\textup{th}}$ column of the Gram matrix $G$.

We now extend our formulation to an RKHS. The RKHS objective function directly follows (7) with the main difference being the use of RKHS inner products:

Again, after majorizing the hinge loss followed by a change of variables $b_{k}\equiv-\left\langle w_{k},x_{0}\right\rangle$, we have

Rewriting the Lagrangian using a matrix formulation of RKHS inner products, we get

where $\mathcal{A}=\left\{\alpha_{1},\alpha_{2},...,\alpha_{K}\right\}$. Again by concatenating $\alpha_{k}$ and $b_{k}$ into a vector $\widetilde{\alpha}_{k}$ and defining the following matrices

the Lagrangian is rewritten as

where $\widetilde{\mathcal{A}}=\left\{\widetilde{\alpha}_{1},\widetilde{\alpha}_{2},...,\widetilde{\alpha}_{K}\right\}$.

In a manner similar to the linear setting in Section 3.4, we can also incorporate any combination of soft and hard constraints on the normal vectors and biases into the formulation in the kernel setting. As mentioned above, using the representer theorem we can write each $w_{k}$ in an RKHS as a linear combination of mapped patterns. Note that we cannot directly incorporate a hard constraint on the weight vectors into the formulation as we did in the linear case since $0_{H}$ here is the origin of an infinite dimensional Hilbert space and is therefore not computable. One way to set the sum of the $w_{k}$ equal to $0_{H}$ in RKHS, i.e., $\sum_{k=1}^{K}w_{k}=0_{H}$, is by adding the following constraints to the problem:

These constraints are derived from the fact that each $w_{k}$ is a linear combination of mapped patterns

and therefore setting the sum to $0_{H}$ via

is equivalent to (16). Here, we only present the formulation for the hard constraints on both weight vectors and biases. The detailed formulation for the case of soft $w$-hard $b$ is also presented in Appendix B. The other two cases can be obtained in similar fashion. The optimization problem is

Similarly, by concatenating $b_{k}$ to $\alpha_{k}$, we get the simplified optimization problem

We then concatenate all $\widetilde{\alpha}_{k}$ into one vector, $\widetilde{\alpha}$, and solve for it using KKT optimality conditions. The four cases for the kernel formulation with different settings of constraints are summarized in Table 2. Similar to the linear case in Section 3, regularization terms and hinge loss terms are left out since they are common to all cases.

One of the drawbacks of the BR approach for multilabel problems is that we might not have data only belonging to one class in order to train its classifier. For illustration, consider the following scenario shown in Figure 2. In this two-class example, the training set patterns belong either to class 1 (label $\left[1,0\right]$) or to both classes (label $\left[1,1\right]$). Therefore there is no pattern which only belongs to class 2. Obviously, the OvR approach can not train a classifier for class 1 versus class 2 as there is no pattern belonging solely to the latter. Hence we need an approach for determining the hyperplanes of each class without requiring data belonging to opposing classes. In other words, we need each class to determine its classifier based on available information of its members without the need for direct opposition from other classes. This is the core idea of our approach and hence the monicker one versus none (OvN).

Scikit-learn handles this situation by just assigning the label $1$ to any test set pattern and therefore only produces label set $\left[1,0\right]$ or $\left[1,1\right]$ for each training or test pattern. The cross training approach of [4] is also not able to cope with this situation. They implemented the OvR approach to train separate classifiers. If a pattern belongs to both class 1 and class 2, it is considered a class 1 (class 2) pattern while training the class 1 (class 2) classifier. However, even this strategy is not able to mitigate the situation. With the OvN approach, we are capable of producing new label sets which have not occurred during training. Figure 2 demonstrates this scenario. As we can see from Figure 2, it does not make sense to assign label set $\left[1,1\right]$ to patterns $\left(-4,3\right)$, $\left(-5,2\right)$ and $\left(-3,3\right)$ since they are far away from the points which have both labels. Our linear soft $w$-hard $b$ model, assigns label set $\left[0,1\right]$ to these points.