-1
$\begingroup$

In soft margin svm, we solve the following quadratic programming problem. $$ \text{maximize}\ \sum_{i=1}^N \alpha_i-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jX_i^tX_j,\\ \text{subject to}\ \sum_{i=1}^N \alpha_i Y_i=0,\\ 0\le \alpha_i\le C, 1\le i\le N. $$ $X_i$ is a vector predictor and $Y_i$ is a binary 1, -1 response. You can use the quadprog library in R to solve this. Once you have the solution, each predictor $X_i$ is projected on the real line by, $$ \sum_{j=1}^N \alpha_jY_j X_i^tX_j. $$ You want to find a suitable cutoff $b$, to assign a label, $$ \text{sign}\left[\sum_{j=1}^N \alpha_jY_j X_i^tX_j+b\right]. $$ Using this, we can assign a label to new predictor $\tilde{X}$ by, $$ \text{sign}\left[\sum_{j=1}^N \alpha_jY_j \tilde{X}^tX_j+b\right]. $$ You can obtain the cutoff by the fact that for $i$ such that $0\le\alpha_i\le C$, we have the equality, $$ Y_i\left(\sum_{j=1}^N \alpha_jY_j X_i^tX_j+b\right)=1. $$

But the iact value of solve.QP of quadprog returns that for all $i$, at least one of the inequalities $0\le \alpha_i$ and $\alpha_i\le C$ is an equality. This means there are no support vectors, which can't be. When I take a look at the $\alpha$'s, at least three of them is considerably far from 0 and C. But I get one cutoff value from two of these $\alpha$'s and another different cutoff value by using another $\alpha$. Even though they should be returning the same value. Help on why such odd things are happening would be much appreciated. The projection seems to be correct. And if the projections are correct, obtaining the cutoff is just one line from there.

Simulated Data

Above is the simulated data. Below is the projection and the cutoffs.

Cutoffs

The code that produced this is below.

library(quadprog)
set.seed(051517)

X=matrix(rnorm(200),100,2)
plot(X[,1],X[,2],pch='+')
vrbinom=Vectorize(rbinom)
Y=vrbinom(n=1,size=1,prob=exp(4*rowSums(X))/(exp(4*rowSums(X))+1))
Y=2*Y-1
Xp=X[Y==1,]
Xm=X[Y==-1,]
plot(Xp[,1],Xp[,2],pch='+',xlim=range(X[,1])+c(-0.1,0.1),
ylim=range(X[,2])+c(-0.1,0.1))
points(Xm[,1],Xm[,2],pch='-')
epsilon=1e-6
M=(X%*%t(X))
MAT=(Y%o%Y)*(X%*%t(X))+epsilon*diag(100)

lambda=100
A=rbind(Y,diag(100))
A=rbind(A,-diag(100))
A=t(A)
b=rep(0,101)
b=c(b,rep(-lambda,100))
sc=norm(2*MAT,"2")
sol=solve.QP(Dmat=2*MAT/sc,dvec=rep(1,100)/sc,Amat=A,bvec=b,meq=1)
alpha=sol$solution
index=which.min(abs(alpha-lambda/2))
indices=which(abs(alpha-lambda/2)<49)
cutoff=-1/Y[index]+sum(alpha*Y*M[,index])
for(i in indices){
    cat(-1/Y[i]+sum(alpha*Y*M[,i]),"\n")
}
abs(alpha-lambda/2)
projection=(X%*%t(X))%*%as.vector(alpha*Y)
sum(projection[Y==1]>cutoff)+sum(projection[Y==-1]<cutoff)
min(projection[Y==1])-max(projection[Y==-1])
plot(projection,Y,pch="+",xlab='projected Y',ylab='true Y')
abline(v=cutoff)
abline(v=0.5635418,lty=2)

setdiff(0:49,unique((sol$iact-1)[-which((sol$iact-1)==0)]%%50))
sort(unique((sol$iact-1)[-which((sol$iact-1)==0)]%%50))

The last two lines is where I check the iact values of solve.QP to find which of the inequalities were active. I also added a Tikhonov regularization to the matrix in the quadratic form, as without it, it was giving an error.

$\endgroup$
1
$\begingroup$

Basically, for $\alpha_i$ such that $0 < \alpha_i < C$ you should have that it is classified to be on the boundary (as you wrote). For numerical stability reasons, one generally takes an average in order to establish the value - see e.g., page 14 in the libSVM documentation

$\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.