5
$\begingroup$

In Support Vector Machine, why is it a quadratic programming problem instead of a linear programming problem to obtain the optimal separating hyperplane. I only find, in book references, that the author choose the quadratic, my question is why????

$\endgroup$
7
$\begingroup$

Because the optimal separating hyperplane between classes of data

\begin{equation} D(\mathbf{x})=\mathbf{w}^T\mathbf{x} + b = c \quad \quad -1 < c < 1, \end{equation}

is found by minimizing the objective function

\begin{equation} \begin{split} Q(\mathbf{w})&=\frac{1}{2} ||\mathbf{w}||^2\\ \mathrm{w.r.t } & \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1,\\ \end{split} \end{equation}

which is linear in the inequality contraint but is a quadratic objective function due to the squared term. The square of the Euclidean norm $||\mathbf{w}||$ makes the optimization problem "quadratic programming." The quadratic objective function with inequality constraints results in a function value that is unique, but the solutions are nonunique.

There's also a definition in optimization theory:

Definition: An optimization problem for which the objective function, inequality, and equality constraints are linear is said to be a linear program. However, if the objective function is quadratic while the constraints are all linear, then the optimization problem is called a quadratic program.

$\endgroup$
5
$\begingroup$

In order to find an optimal separating hyperplane, the norm of the weight vector $||\overline{w}||$ should be minimized, subject to constraints $y_i(\overline{w} \cdot \varphi(x_i) + b) ≥ 1 − \xi_i$, $\xi_i \geqslant 0, i=1,\dots, l$ (see here).

While it's technically possible to minimize $\mathcal{l}^1$-norm $||\overline{w}|| = \sum_i^n |w_i|$ (i.e. to solve linear programming problem) instead of $\mathcal{l}^2$ norm (quadratic problem), the $l^1$-approach has a number of disadvantages over the $l^2$:

(a) the solutions for $l^1$-norm minimization problem lack stability,

(b) the solution isn't unique,

(c) it's harder to provide computationally efficient method for $l^1$-minimization, as compared to $l^2$-minimization.

On the other hand, while the solution of $l^1$-minimization problem is more robust to outliers than of the corresponding $l^2$ problem, this doesn't play a great role specifically for SVMs, since there's a very small chance for an outlier to become a support vector.

$\endgroup$
  • 3
    $\begingroup$ Another point of interest: since the L1 norm is not invariant under rotation, this SVM would have the weird property of changing when you rotated your data set; i.e. the separating slab would not rotate along with the data points. $\endgroup$ – Matthew Drury Jul 22 '17 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.