A novel multi-class SVM model using second-order cone constraints

Abstract

In this work we present a novel maximum-margin approach for multi-class Support Vector Machines based on second-order cone programming. The proposed method consists of a single optimization model to construct all classification functions, in which the number of second-order cone constraints corresponds to the number of classes. This is a key difference from traditional SVM, where the number of constraints is usually related to the number of training instances. This formulation is extended further to kernel-based classification, while the duality theory provides an interesting geometric interpretation: the method finds an equidistant point between a set of ellipsoids. Experiments on benchmark datasets demonstrate the virtues of our method in terms of predictive performance compared with various other multicategory SVM approaches.

Appendix : A: Dual formulation for multi-class SOCP-SVM

1.1 A.1 Proof of Theorem 1

Proof

The Lagrangian function associated with Problem (P _θ ) is given by:

$$\begin{array}{@{}rcl@{}} L(\tilde{\textbf{w}},\textbf{b},\alpha_{i},\beta) &=& \frac{1}{2}\|\textbf{Q}^{1/2}(\theta )\tilde{\textbf{w}}\|^{2} + \sum\limits_{i=1}^{K} \alpha_{i}(\kappa_{i}\|S_{i}^{\top} H^{i}\tilde{\textbf{w}}\| \\&&- (H^{i}\tilde{\textbf{w}})^{\top} {\boldsymbol\mu}_{i}-(\textbf{d}^{i})^{\top} \textbf{b})\\ &&+\sum\limits_{i=1}^{K} \alpha_{i}+\beta(\textbf{e}^{\top} \textbf{b}). \end{array} $$

Since the relationship ∥v∥= max∥u∥≤1v ^⊤ u holds for any v ∈ ℜⁿ, we can rewrite the Lagrangian as follows

$$\begin{array}{@{}rcl@{}} L(\tilde{\textbf{w}},\textbf{b},\alpha_{i},\beta)&=&\max\limits_{\textbf{u}^{i}}\{L_{1}(\tilde{\textbf{w}},\textbf{b}, \alpha_{i},\beta,\textbf{u}^{i}):\|\textbf{u}^{i}\|\\ &&\qquad\le 1, i=1,\ldots,K\}, \end{array} $$

where L ₁ is given by

$$\begin{array}{@{}rcl@{}} &&L_{1}(\tilde{\textbf{w}},\textbf{b},\alpha_{i},\beta,\textbf{u}^{i})\\&=& \frac{1}{2}\|\textbf{Q}^{1/2}(\theta )\tilde{\textbf{w}}\|^{2}\\ && + \sum\limits_{i=1}^{K} \alpha_{i}\left( \kappa_{i}(S_{i}^{\top} H^{i}\tilde{\textbf{w}})^{\top} \textbf{u}^{i}- (H^{i}\tilde{\textbf{w}})^{\top} {\boldsymbol\mu}_{i}\right)\\ &&+\sum\limits_{i=1}^{K} \alpha_{i}(1-(\textbf{d}^{i})^{\top} \textbf{b})+\beta(\textbf{e}^{\top} \textbf{b}). \end{array} $$

(34)

Thus, Problem (P _θ ) can be written equivalently as

$$\min\limits_{\tilde{\textbf{w}},\textbf{b}} \max\limits_{\alpha_{i},\beta,\textbf{u}^{i}}\!\{L_{1}\!(\tilde{\textbf{w}},\textbf{b}, \alpha_{i},\beta,\textbf{u}^{i})\!\!:\!\!\|\textbf{u}^{i}\|\!\le\!1,\!\ \alpha_{i}\!\ge\!0,\! i\,=\,1,\ldots,\!K\}. $$

Hence, the dual problem (see e.g. [7, 24, 28]) of (P _θ ) is given by

$$\begin{array}{@{}rcl@{}} &&\max\limits_{\alpha_{i},\beta,\textbf{u}^{i}}\min\limits_{\tilde{\textbf{w}},\textbf{b}} \{L_{1}(\tilde{\textbf{w}},\textbf{b},\alpha_{i},\beta,\textbf{u}^{i}):\|\textbf{u}^{i}\|\le1,\ \alpha_{i}\\ &&\ge0,\ i=1,\ldots,K\}. \end{array} $$

(35)

The expression (35) now enables us to eliminate the primal variables to give the dual. Computing the first order optimization condition of the internal minimum problem (35) yields

$$\begin{array}{@{}rcl@{}} \nabla_{\tilde{\textbf{w}}} L_{1}&=&\textbf{Q}(\theta )\tilde{\textbf{w}} + \sum\limits_{i=1}^{K} \alpha_{i}\left( \kappa_{i}{H^{i}}^{\top} S_{i} \textbf{u}^{i}- {H^{i}}^{\top} {\boldsymbol\mu}_{i}\right)\\&=&0, \end{array} $$

(36)

$$\begin{array}{@{}rcl@{}} \nabla_{\textbf{b}} L_{1} &=& -\sum\limits_{i=1}^{K} \alpha_{i}\textbf{d}^{i}+\beta\textbf{e}=0. \end{array} $$

(37)

It follows from the previous (37) that α _i = β for all i = 1,…,K, and therefore, replacing in (34) we get

$$\begin{array}{@{}rcl@{}} L_{1}(\tilde{\textbf{w}},\textbf{b},\alpha_{i},\beta,\textbf{u}^{i})&=& \frac{1}{2}\|\textbf{Q}^{1/2}(\theta) \tilde{\textbf{w}}\|^{2} \\ &&+ \beta\sum\limits_{i=1}^{K} \tilde{\textbf{w}}^{\top} {H^{i\top}} (\kappa_{i}S_{i}^{\top} \textbf{u}^{i}- {\boldsymbol\mu}_{i})\\ &&+K\beta. \end{array} $$

(38)

Additionally, from (36) we get

$$ \textbf{Q}(\theta)\tilde{\textbf{w}}=\beta{\sum}_{i=1}^{K} {H^{i}}^{\top}({\boldsymbol\mu}_{i}-\kappa_{i}S_{i} \textbf{u}^{i}). $$

(39)

Replacing (39) in (38) we obtain the reduced form

$$ L_{1}(\tilde{\textbf{w}},\textbf{b},\alpha_{i},\beta,\textbf{u}^{i})=-\frac{1}{2} \|\textbf{Q}^{1/2}(\theta)\tilde{\textbf{w}}\|^{2}+K\beta. $$

(40)

In order to use (39) to compute $\textbf {Q}^{1/2}(\theta )\tilde {\textbf {w}}$, and then to obtain the dual problem, we distinguish two main cases: θ>0, in which we have strong convexity of the objective function and we obtain good mathematical properties as uniqueness of the optimal solution; and the case θ = 0, in which most of this mathematical structure is lost but we can still derive a dual problem for this alternative by using some properties of the matrix Q(0).

Case

θ>0: In this case we note first that (see [35, Proposition 3.4] for details)

$$\textbf{Q}^{-1/2}(\theta)=\frac{1}{\sqrt{K+\theta}}I_{nK}+\frac{\sqrt{K+\theta}-\sqrt{\theta}}{K\sqrt{\theta} \sqrt{K+\theta}}{\mathcal J}, $$

then

$$ {\textbf{Q}^{-1/2}}(\theta){H^{i}}^{\top}=\frac{1}{\sqrt{K+\theta}}{H^{i}}^{\top}. $$

(41)

Therefore, multiplying (39) by Q ^−1/2(θ) we obtain

$$\textbf{Q}^{1/2}(\theta)\tilde{\textbf{w}}=\frac{\beta}{\sqrt{K+\theta}}\sum\limits_{i=1}^{K} {H^{i}}^{\top} \textbf{z}_{i},\text{ where }\ \textbf{z}_{i}={\boldsymbol\mu}_{i}-\kappa_{i}S_{i} \textbf{u}^{i}. $$

Replacing this expression in the reduced Lagrangian function (40), we get

$$L_{1}= K \beta-\frac{\beta^{2}}{2(K+\theta)}\|\sum\limits_{i=1}^{K} {H^{i}}^{\top}\textbf{z}_{i}\|^{2}, $$

and therefore we obtain the following dual formulation

$$ \begin{array}{rl} \max\limits_{\textbf{u}^{i}, \beta}&\ K \beta- \frac{\beta^{2}}{2(K+\theta)}\|\sum\limits_{i=1}^{K} {H^{i}}^{\top}\textbf{z}_{i}\|^{2}\\ \text{s.t.}&\ \textbf{z}_{i}={\boldsymbol\mu}_{i}-\kappa_{i}S_{i} \textbf{u}^{i},\\ & \|\textbf{u}^{i}\|\le1,\ i=1,\ldots,K,\\ &\ \beta\ge0. \end{array} $$

(42)

Note that, after some algebraic manipulation, we have

$$ \|\sum\limits_{i=1}^{K} {H^{i\top}}\textbf{z}_{i}\|^{2}=\sum\limits_{i=1}^{K}\|\textbf{z}_{i}-\textbf{p}\|^{2}, \quad\text{ with }\quad \textbf{p}=\frac{1}{K}\sum\limits_{i=1}^{K}\textbf{z}_{i}. $$

(43)

In consequence, Problem (42) can be written as

$$ \begin{array}{rl} \max\limits_{\textbf{z}_{i},\textbf{u}^{i},\beta}&\ K \beta- \frac{\beta^{2}}{2(K+\theta)}\sum\limits_{i=1}^{K}\|\textbf{z}_{i}-\textbf{p}\|^{2}\\ \text{s.t.}&\ \textbf{z}_{i}={\boldsymbol\mu}_{i}-\kappa_{i}S_{i} \textbf{u}^{i},\\ &\ \|\textbf{u}^{i}\|\le1,\ i=1,\ldots,K,\\ & \ \textbf{p}=\frac{1}{K}\sum\limits_{i=1}^{K}\textbf{z}_{i},\\ &\ \beta\ge0. \end{array} $$

(44)

Case

θ = 0: We note the following property $\textbf {Q}(0)=\sqrt {K}\textbf {Q}^{1/2}(0)$. Replacing this in (39) one has

$$\textbf{Q}^{1/2}(0)\tilde{\textbf{w}}=\frac{\beta}{\sqrt{K}}\sum\limits_{i=1}^{K} {H^{i}}^{\top} ({\boldsymbol\mu}_{i}-\kappa_{i}S_{i} \textbf{u}^{i}). $$

Using this in (40) and proceeding in a similar way to the case θ>0, we obtain the same formulation in (44) with θ = 0.

1.2 A.2 Proof of Proposition 1

Proof

It is suffices to prove that the formulation (1) is equivalent to (17). We note that, given θ≥0, the objective function of the dual problem (17) is concave with respect to β therefore attains its maximum value at

$$ \beta=\frac{K(K+\theta)}{{\sum}_{i=1}^{K}\|\textbf{z}_{i}-\textbf{p}\|^{2}}, $$

(45)

also its optimal value is given by

$$\frac{K^{2}(K+\theta)}{2{\sum}_{i=1}^{K}\|\textbf{z}_{i}-\textbf{p}\|^{2}}. $$

Hence, replacing this in (17) and using the definition of E(μ,S,κ) we get that (17) is equivalent to problem:

$$ \begin{array}{rl} \max\limits_{\textbf{z}_{i},\textbf{u}^{i}} & \ \frac{K^{2}(K+\theta)}{2{\sum}_{i=1}^{K}\|\textbf{z}_{i}-\textbf{p}\|^{2}}\\ \text{s.t.}&\ \ \textbf{z}_{i}\in \textbf{E}({\boldsymbol\mu}_{i},S_{i},\kappa_{i}),\quad i=1,\ldots,K,\\ & \ \ \textbf{p}=\frac{1}{K}\sum\limits_{i=1}^{K}\textbf{z}_{i}, \ \end{array} $$

(46)

turn the max term to min we obtain the result. □

1.3 A.3 Proof of Proposition 2

Proof

It is not difficult to see that

$$ \sum\limits_{i=1}^{K} {H^{i}}^{\top}\textbf{z}_{i}=\frac{1}{K}\textbf{Q}(0)\tilde{\textbf{z}}, $$

(47)

where we denote $\widetilde {\textbf {z}}=[\textbf {z}_{1}^{\top },\textbf {z}_{2}^{\top },\ldots ,\textbf {z}_{K}^{\top }]^{\top }\in \Re ^{nK}.$ Therefore, from (39) the relation between w _i and z _i can be written equivalently as

$$\textbf{Q}(\theta)\tilde{\textbf{w}}=\frac{\beta}{K}\textbf{Q}(0)\tilde{\textbf{z}}. $$

Since Q(θ) is invertible, when θ>0, we have

$$\tilde{\textbf{w}}=\frac{\beta}{K} \textbf{Q}(\theta)^{-1}\textbf{Q}(0)\tilde{\textbf{z}}=\frac{\beta}{K(K+\theta)} \textbf{Q}(0) \tilde{\textbf{z}}. $$

where the last inequality follows from (41) and (47). Then, we conclude that w _i can be written in terms of z _i and p as

$$\textbf{w}_{i}=\frac{\beta}{(K+\theta)}(\textbf{z}_{i}-\textbf{p})=\frac{K}{{\sum}_{i=1}^{K} \|\textbf{z}_{i}-\textbf{p}\|^{2}}(\textbf{z}_{i}-\textbf{p}), $$

$$i=1,\ldots,K. $$

□

We note that in the case θ = 0,$\tilde {\textbf {w}}$ and $\tilde {\textbf {z}}$, are related by

$$\textbf{Q}(0)\tilde{\textbf{w}}=\frac{\beta}{K} \textbf{Q}(0)\tilde{\textbf{z}}, $$

but the uniqueness of solution is lost, because the matrix Q(0) is symmetric positive semi-definite.

1.4 A.4 Proof of Proposition 3

Proof

The KKT conditions of the dual formulation (1) can be summarized as follows

$$\begin{array}{@{}rcl@{}} -\frac{4\kappa_{i}}{K^{2}(K+\theta)}\, S_{i}^{\top}(\textbf{z}_{i} - \textbf{p})+\gamma_{i}\textbf{u}_{i}&=&0,\\ \gamma_{i}(\|\textbf{u}_{i}\|-1)&=&0, \end{array} $$

(48)

$$\begin{array}{@{}rcl@{}} {\sum}_{i}(\textbf{z}_{i} - \textbf{p}) &=&0,\\ \|\textbf{u}_{i}\|\le1,\ \gamma_{i}&\ge&0. \end{array} $$

(49)

Since Σ _i are symmetric positive definite matrices, and z _i ≠p for all i = 1,…,K, we have that z _i −p does not belong to the null space of $S_{i}^{\top }$. Consequently, the Lagrangian multipliers γ _i are strictly positive. This implies that ∥u _i ∥=1 holds. In such situation, z _i = μ _i −κ _i S _i u _i belong to the boundary of the Ellipsoid E(μ _i ,S _i ,κ _i ).

Furthermore, by (37) and (45) we have that α _i = β>0 for i = 1,…,K. This implies that the constraints in (P _θ ) are active. Then, since $\bar {\textbf {w}}=0$ (cf. Remark 3) and ∥u _i ∥=1, we get from (10) that

$$\kappa_{i}\|u_{i}\|\|S_{i}^{\top}\textbf{w}_{i}\|= \textbf{w}_{i}^{\top} {\boldsymbol\mu}_{i}+{b}_{i}-1 \quad i=1,\ldots,K. $$

We note at optimality $S_{i}^{\top }(\textbf {z}_{i} - \textbf {p})$ is parallel to u _i , for i = 1,…,K, thus, we have that $\|\textbf {u}_{i}\|\|S_{i}^{\top }\textbf {w}_{i}\|=\textbf {u}_{i}^{\top } S_{i}^{\top } \textbf {w}_{i},$ obtaining from the above expression that

$$0=\textbf{w}_{i}^{\top} ({\boldsymbol\mu}_{i}-\kappa_{i}S_{i}\textbf{u}_{i})+{b}_{i}-1 \quad i=1,\ldots,K. $$

Then, we get the following conditions:

$$\textbf{w}_{i}^{\top} \textbf{z}_{i}+b_{i}=1,\quad \text{ for \(i=1,\ldots,K\)}. $$

This geometrically means that the hyperplanes $\textbf {w}_{i}^{\top } \textbf {x}+b_{i}=1$ are tangents to the ellipsoids E(μ _i ,S _i ,κ _i ), for i = 1,…,K. Using the above relation and (45), one can compute the value of b _i obtaining the result in (22).

Finally, as decision functions are given by $f^{i}(\textbf {x}):=\textbf {w}_{i}^{\top }\textbf {x}+b_{i},$ the result in (23) is obtained by replacing the values of b _i from (22) and w _i from Proposition 2. □