How to solve SVM Soft Margin Primal formula in MATLAB quadprog

Question

I am trying to solve the SVM Primal formula in MATLAB using the Quadprog function. When the two classes are linearly separated, the problem of minimizing the SVM to obtain the weight vector w becomes 1/2 (|| W || 2)

subject to the constraint yi (wxi-b)> = 1

http://en.wikipedia.org/wiki/Support_vector_machine#Primal_form

Matlab's quadrupole function solves the following equation

x = quadprog (H, f, A, b) minimizes 1/2 * x '* H * x + f' * x subject to the constraints A * x ≤ b. A is the twin matrix, b is the twin vector.

So, the primary form can easily be mapped onto a quadruple function in order to easily obtain the weight vector w. H becomes the identity matrix. f 'becomes a matrix of zeros. A - the left side of the constraint from previously b is -1, since the original constraint has> = 1, it becomes <= -1 when we multiply with -1 on both sides.

When I do this, the weight vector is great.

Now I am trying to solve the case with the soft SVM field here

http://en.wikipedia.org/wiki/Support_vector_machine#Soft_margin

Minimization equation here

min ((1/2) || w || 2 + C (summation epsilon (i)) w, b

subject to the constraint yi (wxi-b)> = 1 - eplison (i)> = 0.

How to solve this optimization problem using the Quadprog MATLAB function. It is unclear how the equation should be matched with the parameters of the quadprog function. I split my head about how unlucky.

It has been a long time since I learned SVM, but due to vague memory, I remember that Primal Form in the Soft Margin is an NP problem, so we convert it to Wolfe's double representation to solve it, but I'm not sure .

I converted it to double form and I can get the values ​​of the Lagrange variable in double form, however I want to confirm that the primary form cannot be solved on its own.

Does anyone know how this can be solved using the matlab quadprog function? Or if it is an NP problem?

Answer 1

I do not see how this can be a problem. Let z be our vector of variables (2n + 1) :

 z = (w, eps, b) 

Then H becomes a diagonal matrix with the first n values ​​on the diagonal equal to 1 , and the last n + 1 set equal to zero:

 H = diag([ones(1, n), zeros(1, n + 1)]) 

Vector f can be expressed as:

 f = [zeros(1, n), C * ones(1, n), 0]' 

The first set of restrictions:

 Aineq = [A1, eye(n), zeros(n, 1)] bineq = ones(n, 1) 

where A1 is the same matrix as in the primary form.

The second set of constraints becomes lower bounds:

 lb = (inf(n, 1), zeros(n, 1), inf(n, 1)) 

Then you can call MATLAB:

 z = quadprog(H, f, Aineq, bineq, [], [], lb); 

PS I may be mistaken in some small details, but the general idea is correct.

Answer 2

If z = (w; w0; eps) T is a long vector with n + 1 + m elements (m is the number of points) Then,

 H= diag([ones(1,n),zeros(1,m+1)]). f = [zeros(1; n + 1); ones(1;m)] 

Limitations of inequality can be indicated as:

 A = -diag(y)[X; ones(m; 1); zeroes(m;m)] -[zeros(m,n+1),eye(m)], 

where X is the input matrix nxm in primary form. Of the two parts for A, the first part is for w0, and the second part is for eps.

 b = ones(m,1) 

Limitations of Equality:

 Aeq = zeros(1,n+1 +m) beq = 0 

Bounds:

 lb = [-inf*ones(n+1,1); zeros(m,1)] ub = [inf*ones(n+1+m,1)] 

Now z=quadprog(H,f,A,b,Aeq,beq,lb,ub)

Answer 3

Complete the code. The idea is the same as above.

 n = size(X,1); m = size(X,2); H = diag([ones(1, m), zeros(1, n + 1)]); f = [zeros(1,m+1) c*ones(1,n)]'; p = diag(Y) * X; A = -[p Y eye(n)]; B = -ones(n,1); lb = [-inf * ones(m+1,1) ;zeros(n,1)]; z = quadprog(H,f,A,B,[],[],lb); w = z(1:m,:); b = z(m+1:m+1,:); eps = z(m+2:m+n+1,:);