CIS 515 Project Instructions
Project 4: Hard Margin Support Vector Machine
The purpose of this project is to implement the hard margin support vector machine (version h2).
Recall that we would like to solve the following optimization problem:
Hard margin SVM (SVMh2):
minimize 1 ∥w∥2
w⊤ui −b≥1 −w⊤vj +b≥1
2 subject to
where {u1,…,up} is a set of p blue points and {v1,…,vq} is a set of q red points in Rn (here, n = 2). We assume that these two sets of points are separable.
The problem is to find a separating hyperplane Hw,b of equation w⊤x − b = 0 which maximizes the smallest distance δ from these data points, called the margin.
The margin is δ = 1/∥w∥. The margin hyperplanes are the hyperplanes Hw,b+1 (the blue hyperplane) of equation w⊤x − b − 1 = 0 and Hw,b−1 (the red hyperplane) of equation w⊤x − b + 1 = 0. In order to solve the above problem, we solve the dual program. The dual program is the following program:
Dual of the Hard margin SVM (SVMh2):
1( ) (λ)( )
minimize 2λ⊤ μ⊤ X⊤X μ −λ⊤ μ⊤ 1p+q subject to
i=1,…,p j=1,…,q,
∑p i=1
λi −
∑q j=1
μj = 0
λ≥0, μ≥0, where X is the n×(p+q) matrix given by
X=(−u ··· −u v ··· v), 1p1q
1
CIS 515 | Property of Penn Engineering
a matrix whose columns are the ui and the vj. Then w is determined as follows:
(λ)∑p ∑q
w = −X μ = λiui − μjvj.
i=1 j=1
To solve the dual using ADMM we need to determine the matrices P,q A and c. We
have
and since the only constraint is
P=X⊤X, q=−1p+q,
i=1 the matrix A is the 1×(p+q) row vector
and the right-hand side c is the scalar Obviously the matrix A has rank 1.
∑p
λi −
∑q
μj = 0,
j=1
A = (1⊤ −1⊤), pq
c = 0.
We obtain b using any i0 such that λi0 > 0 and any j0 such that μj0 > 0. Since the
corresponding constraints are active, we have
w⊤ui0 −b = 1, −w⊤vj0 +b = 1, b=w⊤(ui0 +vj0)/2.
so we obtain
For improved numerical stability, we can average over the sets of indices defined as Iλ>0 =
{i∈{1,…,p}|λi >0}andIμ>0 ={j∈{1,…,q}|μj >0}. Weobtain
(∑) (∑)
b = w⊤ ui /|Iλ>0| + vj /|Iμ>0| /2.
i∈Iλ>0 j ∈Iμ>0
(50 points) The following Matlab programs implements the above method but we have
left out some code to determine b that you need to fill in.
function [lamb,mu,w] = SVMhard2(rho,u,v)
%
% Runs hard margin SVM version 2
%
% p green vectors u_1, …, u_p in n x p array u
2
CIS 515 | Property of Penn Engineering
% qred vectorsv_1,…,v_qinnxqarrayv %
% First builds the matrices for the dual program
%
p = size(u,2); q = size(v,2); n = size(u,1);
[A,c,X,Pa,qa] = buildhardSVM2(u,v);
%
% Runs quadratic solver
%
tolr = 10^(-10); tols = 10^(-10); iternum = 180000;
[lam,U,nr,ns,kk] = qsolve1(Pa, qa, A, c, rho, tolr, tols, iternum);
fprintf(‘nr = %d ‘,nr)
fprintf(‘ ns = %d \n’,ns)
fprintf(‘kk = %d \n’,kk)
if kk > iternum
fprintf(‘** qsolve did not converge. Problem not solvable ** \n’)
end
w = -X*lam;
nw = sqrt(w’*w); % norm of w
fprintf(‘nw = %.15f \n’,nw)
delta = 1/nw;
fprintf(‘delta = %.15f \n’,delta)
if delta < 10^(-9)
fprintf('** Warning, delta too small, program does not converge ** \n')
end
%
lamb = lam(1:p,1);
mu = lam(p+1:p+q,1);
b = 0;
tols = 10^(-10);
%
% You need to supply code for finding
% the nonzero lambda_i (those for which
% tols < lambda_i) and the
% nonzero mu_j (those for which tols < mu_j),
% and how many of them there are (numsvl1, numsvm1)
%
% Then compute b using the averaging method
%
if n == 2
CIS 515 | Property of Penn Engineering
3
[ll,mm] = showdata(u,v);
if numsvl1 > 0 && numsvm1 > 0
showSVMs2(w,b,1,ll,mm,nw)
end
end end
The functions buildhardSVM2, qsolve1, showdata, showSVMs2 and makeline (which is needed for solveSVM2) are given in the file folder Matlabcode4.
The parameter ρ is used by the function qsolve1 that solve the optimization program using ADMM. We suggest using ρ = 10.
A difficulty that arises is to tune the tolerance parameters needed to deal with floating- point arithmetric. We suggested some tolerance parameters for you, but you are welcome to experiment.
Run your program on the following sets of data points:
v1 = [1 2 3 1 1 3 -1 -3;-1 0 -2 -0.5 -4 -3 -3 -3];
u1 = [-1 -1 0 1 -3 -4 0.5 3 0.5;0 1 2 3 0 -2 2 2.5 2.5];
u2 = 10.1*randn(2,20)+15;
v2 = -10.1*randn(2,20)-15;
u3 = 10.1*randn(2,20)+10;
v3 = -10.1*randn(2,20)-10;
u4 = 10.1*randn(2,50)+18;
v4 = -10.1*randn(2,50)-18;
If you want to suppress printing lamb and mu, call the function using [~, ~, w] = SVMhard2(rho,u,v)
What do you observe when you run hard SVM on the data set (u3, v3)?
CIS 515 | Property of Penn Engineering
4