3
$\begingroup$

I'm using SVMs with linear kernel for sentence classification (binary). My dataset contains many duplicate instances i.e. many sentences in the training set have identical feature vectors. In the trained model, I see a lot of duplicate support vectors, each with a different Lagrange Multiplier (alpha*y) term. For example:

-0.064019597363882741 5660:1 # fcda5cf6-e00b-11e2-ddad-001517e11bd0
-0.00028270965981203044 5660:1 # 67d4d4d2-855c-11e3-f88e-001517e11900
-0.00084391434273911603 5660:1 # 38d53d84-e435-11e2-ddad-001517e11bd0
-0.031641060077848393 5660:1 # 069c2c6e-e8be-11e2-edb1-001517e116e4
-0.0028105012661461251 5660:1 # 623c52e4-e038-11e2-edb1-001517e116e4
-0.00098570725949942428 5660:1 # f67aae78-e020-11e2-5884-001517e11900

For those who are unfamiliar with SVMLight model format, each of the above lines represents a support vector, where:

  • 1st term is alpha*y
  • key-value pairs ('5660:1') are feature_number:feature_value. So, all the above training instances contain just one feature with value 1.
  • Stuff following '#' are comments (instance ids in my case)

Why do the above support vectors have different alpha*y values, even when they have identical feature vectors? Also, why does the model contain multiple SVs with same feature vectors in the first place? I had expected all SVs to have unique feature vectors, although the ones which were duplicated would've had larger alpha value. I agree that training instance duplication might shift the margin if duplicate instances fall within the (soft) margin, but I'm unable to understand why would each duplicate support vector have a different alpha*y value?

$\endgroup$
1
$\begingroup$

Just to expand on Justin's answer, In this case, the Lagrange multipliers are not unique - there are an infinite number of combinations of Lagrange multipliers which are optimal, and produce the exact same performance of the SVM. Because the constraints are linear, the Kuhn-Tucker-Kasrush conditions apply, whether or not any of the constraints are redundant (i.e., not full rank). If you used a different optimization solver, you could get other, still optimal, values of the Lagrange multipliers.

$\endgroup$
0
$\begingroup$

The formula for the decision boundary is given by:

$\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i.$

If you have multiple ones with different alpha you can combine them to make $\bar\alpha_1 = \sum_i \alpha_i$ and $\bar\alpha_i = 0.0$ for $i \neq 1$ where $i$ ranges over each group of identical features.

With the $\bar\alpha_i$'s you will have the same decision boundary as before but only one support vector per unique feature. In other words, it doesn't matter if you have one non-zero alpha or if you spread the alpha among all the identical features.

$\endgroup$
  • $\begingroup$ Thanks Aaron. I get it that alpha values for identical SVs can be added to get one alpha-value for each unique-SV. What's puzzling me are the different alphas values for each identical SVs. I'm trying to understand what would make one SV have a greater/smaller alpha value than another SV with an identical feature vector. Is this a SVMLight training artifact or does it make sense mathematically? $\endgroup$ – user2588219 Jul 23 '14 at 14:23
  • $\begingroup$ You're still confused I think. All that matters is the decision boundary. If you can vary the alpha values without changing the decision boundary then you are free to do so. If you want all of the SV with the same feature to have the same alpha for some reason then just redistribute the alpha among all of those SV's so that they are all equal. $\endgroup$ – Aaron Jul 23 '14 at 14:41

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.