7
$\begingroup$

Consider the dual with no offset and not slack.

In the dual we have that for data points that are support vectors:

$$\alpha_t > 0$$

and that the constraint is satisfied with equality (since a support vector!):

$$y^{(t)}\sum^n_{t'=1} \alpha_{t'}y^{(t')}x^{(t')} \cdot x^{(t)} = 1$$

However, just because $\alpha_t > 0$ its not obvious to me if all the support vector have the same value of $\alpha_t$. Do all of the support vectors have the same value of $\alpha_t$? I was kind of looking for a mathematical justification or intuition for my question. My guess is that they would have the same $\alpha_t$ value in the absence of slack. My other guess was that, $\alpha_i$ intuitively, says the important of that point, right? (maybe thats wrong) If thats true then, not all support vector have the same value of $\alpha_i$ because not all support vectors are essential support vectors. What I mean is, that some support vectors will lie on the margin boundary but removing them will not necessarily change the margin (for example, consider the case where you have 3 SVs in a line, you can remove the middle one and keep the same boundary). So do essential support vectors get larger value of $\alpha_t$?

Also, I was wondering, what would happen in the case of slack and offset to the value of $\alpha_t$. I was guessing that closer points to the decision boundary, get larger value of $\alpha$? However, are points inside the margin even consider support vectors?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ @user603 in the case of no offset, for support vectors we have $y^{(i)} \theta \cdot x^{(i)} = 1$ (I said no slack and then later asked whats going on with slack). If $\theta = \sum^n_{i=1} \alpha_i y^{i} x^{(i)}$ then the constrain becomes: $y^{(i)} \sum^n_{i=1} \alpha_i y^{i} x^{(i)} \cdot x^{(i)} = 1$. Which is what I wrote. For support vectors we can change the inequality to an equality because its a support vector. There is nothing wrong about what I wrote. $\endgroup$
    – Charlie Parker
    Commented Mar 20, 2014 at 19:36
  • $\begingroup$ thanks for the clarification. I see now: I had read the equations a bit too fast and clearly not paid attention to the surrounding text. $\endgroup$
    – user603
    Commented Mar 20, 2014 at 19:39
  • $\begingroup$ Don't worry, I think I also wrote the question a little weirdly, let me write it clearer, I agree its not the best wording I could have chosen. You should try look for a clarification before writing an angry comment and down voting though :P I was so sad for a second hehe But I understand the misunderstanding. I'll improve my question. $\endgroup$
    – Charlie Parker
    Commented Mar 20, 2014 at 19:41

1 Answer 1

Reset to default
3
$\begingroup$

The cost function of SVM is: $$\min_{\alpha,\xi,b} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^n \xi_i$$

where $\xi$ are the slack variables (0 for hard margin) and $$ ||\mathbf{w}||^2 =\mathbf{w}^T\mathbf{w} = \sum_{i\in \mathcal{S}}\sum_{j\in \mathcal{S}} \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j) $$

A couple of important properties can be derived from the Langrangian (here with slack variables):

$$L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(<\mathbf{w},\varphi(\mathbf{x}_i)>+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$

By setting the partial derivative to $\xi$ (the slack variables) to zero, we obtain the following equation in $\alpha$: $$\frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad \alpha_i=C-\mu_i, \quad \forall i$$ In the presence of slack variables, all support values ($\alpha$'s) are bound by $0$ and $C$. They are not all equal.

In the absence of slack variables (hard margin SVM), $\alpha$ values are not equal because $\alpha$ is a direct part of the objective function as shown in the first two equations. In hard margin SVM, the cost function is a weighted quadratic function in $\alpha$ where the kernel evaluations between corresponding points determine the weights. Since not all weights are equal, the $\alpha$ values aren't either.

This is more apparant in least-squares SVM (LS-SVM), where all training points become support vectors due to the problem formulation. One of the original methods proposed to obtain sparsity in LS-SVM involved pruning support vectors with small $\alpha$ values.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In your Lagrangian, what is $\mu_i$? $\endgroup$
    – Charlie Parker
    Commented Mar 20, 2014 at 19:58
  • 1
    $\begingroup$ @Pinocchio $\mu$ is the vector of dual variables (Langrange multipliers) associated with the slack variables $\xi$. $\endgroup$
    – Marc Claesen
    Commented Mar 20, 2014 at 20:00
  • $\begingroup$ Aahhh I see. We have two lagrange multipler variables, one for the two sets of constraints. One for the slack constraints and the other for the "normal" margin one. Thanks now it makes sense. I was put me off because $\mu$ is usually reserved for denoting the mean, so I was very confused. I would have used $\beta_i$, since we are using $\alpha$ to denote the first set of constraints. :p But its not that important. $\endgroup$
    – Charlie Parker
    Commented Mar 20, 2014 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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