7
$\begingroup$

The linear SVM in textbook takes form of maximizing

$L_D = \sum_i{a_i} - \frac{1}{2}\sum_{i,j}{a_ia_jy_iy_jx_i^Tx_j}$

over $a_i$ where $a_i \geq 0$ and $\sum_i{a_iy_i} = 0$

Since $w = \sum_i{a_iy_ix_i}$, the classifier will take the form $\text{Sgn}(wx - b)$.

Thus, it seems to solve linear SVM, I need to figure out $a_i$ with some gradient based methods. However, recently, I came across a paper which states that they try to minimize the following form:

$L_P = \frac{1}{2}||w||^2+C\sum_i{\text{max}(0, 1-y_if_w(x_i))}$

and they claim $C$ is a constant. It seems to me that this form is quite different from primal form of $L_P$ in linear SVM because of the missing $a_i$. As far as the paper goes, it seems to me that they optimized on $w$ directly. I am puzzled here as if I missed something. Can you optimize $w$ directly on linear SVM? Why is that possible?

$\endgroup$
2
  • 2
    $\begingroup$ The title of your question is asking a totally different question from what you really ask­. I, for one, was curious about the real differences between the Linear SVM (let's take the hard margin SVM) and other linear discriminants. $\endgroup$ – levesque Feb 24 '11 at 15:19
  • 1
    $\begingroup$ I guess the main difference is the objective function they optimize. SVM tries to maximize the margin. Other linear classifiers do other things (e.g. perceptron optimizes the reconstruction error). These different objectives have different properties (e.g. maximizing the margin improves the generalization error). They also give you different problems to solve (some of which may be easier or more efficient, others can be solved online, etc.). $\endgroup$ – SheldonCooper Feb 24 '11 at 20:54
8
$\begingroup$

There are two things going on here.

  1. Difference between primal and dual problem. The "original" objective function of SVM is to minimize $1/2 ||w||^2$. This is called "primal form". Turns out that the objective function you wrote (the one involving $L_D$) is the dual form of this problem. So the two lead to equivalent solutions and can be used interchangeably.

  2. The second formulation you describe is called "soft margin SVM". It is obtained by taking the primal form of (1) above and replacing the constraint $y_i f_w(x_i) \geq 1$ by the penalty term $C \cdot \max(0, 1 - y_i f_w(x_i))$. The effect is that you allow violations of the constraint. This is useful e.g. if your data is not linearly separable. You can obtain a dual formulation of this (similar to your expression with $L_D$) as well.

$\endgroup$

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.