%%%%%%%%%%%% Simple SVM Stepest Desecnt %%%%%%%%%%%%%%%%%%%%
clear;
close all;
%%%%%%%%%%%% Constants %%%%%%%%%%%%%%%%%%%%
NNN=30; %%% Sample number %%% 10 20 30
NOISEL=0.0; %%% NOISE LEVEL in Training Samples %%% 0.0 0.1 0.2 0.3
CCC=20000; %%% PARAMETR for soft margin %%%
SUPPORT=0.1; %%% Judgement of support vector %%% 0.1 1 10 100
CYCLE=20000; %%% Cycle of optimization process
DISPLAY=20; %%% Diplay Number
INTERVAL=(CYCLE/DISPLAY); %%% Drawing cycle
ETA=0.05; %%% Optimization coefficient
LLL=100; %%% Parameter for Condition, dot(YYY,Alpha)=0
%%%%%%%%%%%%%%%%%%%%%%%%%%Ture parameter %%%%%%%%%%%%%%%%%%%%
A10=1;
A20=1;
B00=-1;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Make Inputs and Outputs %%%%%%%%%%%%%%%%%%%%%%%%%%%
W00=[A10,A20];
XXX=rand(2,NNN); %%% (2,NNN) Inputs of samples
HHH=W00*XXX+B00+NOISEL*(1-2*rand(1,NNN));
YYY=sign(HHH); %%% (1,NNN) Outputs of samples
ZZZ=(YYY+1)/2;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
subplot(2,2,1);
for i=1:1:NNN
plot(XXX(1,i),XXX(2,i),'+','Color',[ZZZ(i) 0 1-ZZZ(i)]); hold on;
end
title('Blue -1 : Red : +1'); hold off
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Kernel%%%%%%%%%%%%%%%%%%%%%%%%%%
KXX=XXX'*XXX; %%% (NNN,NNN) (x,x)
KYY=YYY'*YYY; %%% (NNN,NNN) yy
KYYXX=KYY.*KXX; %%% (NNN,NNN) yy(x,x)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Initialize Optimization%%%%%%%%%%%%%%%%%%%%%%%%%%%%
CCCS=CCC*ones(1,NNN);
MATYX=KYYXX+eye(NNN)+LLL*YYY'*YYY;
AT=MATYX\ones(NNN,1);
Alpha=AT';
AA=zeros(1,NNN);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Optimization%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Dual Parameters are optimized by steepest descent %%%%%%%%%%%%%%
III=zeros(1,DISPLAY);
EEE=zeros(1,DISPLAY);
COND=zeros(1,DISPLAY);
for i=1:1:CYCLE
ETA2=ETA*(1-i/CYCLE);
TTT=dot(YYY,Alpha);
AB=Alpha+ETA2*(1-Alpha*KYYXX'-LLL*TTT*YYY); %%% Steepest Descent
AB=AB-dot(YYY,AB)*YYY/NNN; %%%
AB=(AB+abs(AB))/2; %%% make ( AB >= 0 )
AB=(AB+CCCS-abs(AB-CCCS))/2; %%% make (AB <= CCCS )
Alpha=AB; %%% Update Alpha
if(mod(i,INTERVAL)==0)
III(i/INTERVAL)=i;
EEE(i/INTERVAL)=dot(Alpha,ones(1,NNN))-0.5*Alpha*KYYXX*Alpha';
COND(i/INTERVAL)=0.5*LLL*TTT*TTT;
end
end
subplot(2,2,2);
plot(III,EEE,'r-');
title('Horizontal: cycle, Red: Dual Loss');
hold off
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%WWW and BBB are calculated%%%%%%%%%%%%%%%%%%%%
fprintf('Optimization Completed \n');
TTT=dot(YYY,Alpha);
CONDITION=TTT*TTT;
fprintf('CONDITION=%e sufficiently small. \n',CONDITION); %%%%% dot(YYY,Alpha)=0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%
ALY=Alpha.*YYY;
WWW=ALY*XXX';
COUNTER=0;
BBB=0.0;
for i=1:1:NNN
if(Alpha(i)>SUPPORT)
%%% Alpha(1,i) %%% SUPPORT VECTOR
subplot(2,2,3); plot(XXX(1,i),XXX(2,i),'o','Color',[0 0 0]); hold on
BBB=BBB+YYY(1,i)-WWW*XXX(:,i);
COUNTER=COUNTER+1;
end
end
BBB=BBB/COUNTER;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Display Results%%%%%%%%%%%%%%
for i=1:1:NNN
subplot(2,2,3);
plot(XXX(1,i),XXX(2,i),'+','Color',[ZZZ(i) 0 1-ZZZ(i)]); hold on
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[X00, Y00]=ndgrid(0:0.05:1,0:0.05:1);
Z00=A10*X00+A20*Y00+B00;
ZZ=WWW(1)*X00+WWW(2)*Y00+BBB;
contour(X00,Y00,ZZ,[0 0],'g'); hold on
contour(X00,Y00,Z00,[0 0],'r');
title('Red: True, Green: Estimated, o: Support Vectors');
subplot(2,2,4);
bar(Alpha);
title('Optimized Values of Dual Variables');
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Generalization Error
NTEST=1000;
Xtest=rand(1,NTEST);
Ytest=rand(1,NTEST);
Ztesttrue=A10*Xtest+A20*Ytest+B00;
Ztest=WWW(1)*Xtest+WWW(2)*Ytest+BBB;
SUM = sum( (1+sign(Ztesttrue.*Ztest))/2 );
fprintf('Generalization: Recognition Rate =%.3f. \n',SUM/NTEST);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%