Dx transformation in hard margin linear SVM

Dx transformation in hard margin linear SVM

Kobi (guest) 31 Jan 2015 18:17

Moed 2013A Question 7 solution doesn't include the column that describe the effect of a transformation of type Dx on the solution of Hard margin linear SVM.
(D being a diagonal matrix without zeros on the diagonal)

My guess is that it does change the solution. Although setting the "new" w^T* to w^TD^-1 will still fulfill all the constraints, I do not see why such a solution will necessarily minimize the norm of w*.
What is the right answer?

student (guest) 01 Feb 2015 12:45

I think the solution will change. In general, I think that if Dx and Ux don't change anything, Ax won't change anything (because of A SVD decomposition).
However, does someone have a clear example when the solution really changes?

On a similar topic, for the soft margin SVM it says a*x will not change the solution. I understand why this is true for hard margin svm, but I don't understand why the approach for hard margin svm works here:
in hard margin, we get w/a after the transformation, and so we minimize w's norm. But in soft margin, doing this will change the tradeoff between w's norm and the total hinge loss, so w/a is not necessarily the best solution for the original problem.
So, why doesn't a*x change the solution in soft margin svm?

Kobi (guest) 01 Feb 2015 18:34

1. I think you are write on the SVD decomposition :)

2. I also think you are write about the soft margin SVM. I ran the following R code:

library(e1071)

C <- 0.2
a <- 2

x1s <- c(.5,1,1,2,3,3.5,     1,3.5,4,5,5.5,6)
x2s <- c(3.5,1,2.5,2,1,1.2,  5.8,3,4,5,4,1)
ys <- c(rep(+1,6),          rep(-1,6))
my.data <- data.frame(x1=x1s, x2=x2s, type=as.factor(ys))
svm.model <- svm(type ~ ., data=my.data, type='C-classification', kernel='linear', cost=C, scale=FALSE)
# get parameters of hiperplane
w <- t(svm.model$coefs) %*% svm.model$SV

my.data$x1 <- my.data$x1 * a
my.data$x2 <- my.data$x2 * a
svm.model <- svm(type ~ ., data=my.data, type='C-classification', kernel='linear', cost=C, scale=FALSE)
# get parameters of hiperplane
w_new <- t(svm.model$coefs) %*% svm.model$SV

print(w)
print(w_new)

The results are:

> print(w)
             x1        x2
[1,] -0.6694118 -0.677647
> print(w_new)
             x1         x2
[1,] -0.4212334 -0.5267132

So w_new is not w / a.
However if I set the cost to 1e+10, w_new is almost exactly w / a, meaning that on hard margin there is no change of classification but in soft margin there is.

Bat-Sheva (guest) 02 Feb 2015 16:31

I think the soft margin sulotion will not change when multiplying by a, because samples are scaled in relation to w.

Re: Dx transformation in hard margin linear SVM

Regev Schweiger 01 Feb 2015 23:28

(Copy from another answer:) The question is not if you get an equivalent hyperplane, but does it have the same margin. If you change D, you may change the margin, and the identity of the best hyperplane may change also. Try to give an example.

lior wolfs heir (guest) 02 Feb 2015 11:36

what about the soft margin SVM? I agree with what "student" said