1
$\begingroup$

I am implementing the dual problem SVM in CVX with soft margin, and a polynomial Kernel. I have read through the theory and know that for data points crossing the margin, I should get alpha = C (1 in my case), and moreover, if I have a relatively separable data set, I should get most of the alphas = 0. However what i get is a vector of

1.0e-03 *

0.0012
0.0044
0.0016
0.0051
0.0059
0.0009
0.0025
0.0061
0.0031
0.0006
0.0011
0.0065
0.0062
0.0110
0.0169
0.0006
0.0209
0.0028
0.0080
0.0066
0.0024
0.0085

this. Basically, I cannot distinguish which alphas are 0 and which are not, and moreover, I cannot find any alphas that are equal to C (1 in my case), and I know for a fact that my data is not completely separable. If anyone has implemented the dual soft-margin SVM problem in CVX please help. Thank you so much!


Per the suggestion below, I have added my code.

% parameters
C = 100;
m = size(X,1);
n = size(Y,2);

% define Kernel matrix
Q = zeros(m,m);
for i = 1:size(Q,1)
     for j = 1:size(Q,2)
        % polynomial kernel degree 2
        Q(i,j) = Y(i).*Y(j).*(2 + 50.*(X(i,:)*X(j,:)').^2);
        % original kernel
        % Q(i,j) = Y(i).*Y(j).*(X(i,:)*X(j,:)'); 
    end
end

% train svm using cvx
cvx_begin
    variables alpha(m);
    minimize (0.5.*quad_form(alpha,Q) - ones(m,1)'*alpha);
    subject to 
        alpha >= 0;
        alpha <= C;
        Y'*alpha == 0; 
cvx_end
$\endgroup$
4
  • $\begingroup$ Without giving it much thought: Have you normalized your data? $\endgroup$
    – usεr11852
    Commented Jul 18, 2013 at 0:59
  • $\begingroup$ We will need to see your code ... $\endgroup$ Commented Jul 18, 2013 at 11:43
  • $\begingroup$ @user11852 yes, of course! $\endgroup$
    – user27525
    Commented Jul 18, 2013 at 18:32
  • $\begingroup$ @MarcClaesen I have edited my post. $\endgroup$
    – user27525
    Commented Jul 18, 2013 at 18:33

1 Answer 1

3
$\begingroup$

Define your kernel only in terms of $X_i$, that is $$Q(x_i,x_j;c,d)=(x_i^T x_j+c)^d $$

where $c,d$ are kernel parameters. Then, replace this line

minimize (0.5.*quad_form(alpha,Q) - ones(m,1)'*alpha);

with

minimize (0.5.*quad_form(Y.*alpha,Q) - ones(m,1)'*alpha);

Because the function you would like to minimize is $$L(\alpha)= \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y^{(i)} y^{(j)} x^{(i)T}x^{(j)} -\sum_{i=1}^n \alpha_i$$

$\endgroup$

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.