ã THE NAIVE SVM SOLUTION: GRADIENT ASCENT

ã Loading input/output script

_load '/home/sasha/Work/IO.+'

ã Loading script to plot

_load '/home/sasha/Work/Plot.+'


ã Linear kernel
ã ap-arbitrary parameter

Linear {A;B;ap} : {A+.«B}

ã Polynomial kernel of degree n

Poly {A;B;n} : {
                (1+A+.«B)*n
               }

ã Gaussian kernel (Radial Basis Function)
ã p - nested vector of two valid forms:('sigma';sigma value)or('mju';mju value)

RBF {A;B;p} : {
                if ('sigma'½0Øp) mjuûß(1Øp)*2 else mjuû1Øp;
                *-mju«+/@1(A -@1 1 0 ôB)*2
              }


ã Auxiliary functions for stopping criteria

ã Monitoring the growth of the dual objective function 
ã Output - criterion value and cond=0 if it meet the condition 

ObjGrowth {crit;alpha;y;KM} : {
                     tolû1e-9;  
                     critûcrit,(+/alpha)-0.5«(alpha«y)+.«KM+.«,@0 alpha«y;
                     condûtol<+/¢1 1«¢2Ùcrit;
                     (crit;cond)
                              }

ã Monitoring the KKT conditions for the primal problem
ã Output: crit-number of points violeting KKT conditions
 
KKT {crit;alpha;y;C;KM;Type} : {
                     tolû1e-2;
                     â(Type=`soft_2)/'(0 0ôKM)û(0 0ôKM)-ßC';
                     yfû¢1+y«(alpha«y)+.«KM;
                     case (Type)
                      {
                       `soft_1;critûcrit,+/((yf<-tol)^alpha<C)©(yf>tol)^alpha>0;
                       `soft_2; critûcrit,+/((yf<-tol)^alpha=0)©((yf>tol-alphaßC)^alpha>0)©(yf<-tol+alphaßC)^alpha>0;
                        critûcrit,+/(yf<-tol)©(yf>tol)^alpha>0
                      };
                     condû0¨¢1Ùcrit;
                     (crit;cond)
                               }

ã Monitoring the feasibility gap between the primal & dual objective functions
ã Output - criterion value and cond=0 if it meet the condition 

FeasGap {crit;alpha;y;C;KM;Type} : {
                     tolû1e-3;
                     ksiû0Ó1-y«(alpha«y)+.«KM;
                     Wû(+/alpha)-0.5«(alpha«y)+.«KM+.«,@0 alpha«y;
                     â(Type¨`soft_1)/'Cû1+Ó/alpha';
                     numrtrû((+/alpha)-2«W)+C«+/ksi;
                     critûcrit,numrtrßnumrtr+W+1;
                     condûtol<¢1Ùcrit;
                     (crit;cond) 
                                   }



ã GRADIENT ASCENT ALGORITHM
ã Algorithm for training SVM
ã
ã Input:
ã Mode-nested vector of symbol (`hard,`soft_1 or `soft_2) to select SVM type &
ã number (1,2 or 3) to choice the stopping criteria
ã By default other entries is replaced by `hard and (or) 1-st criterion 
ã Ker is a kernel function
ã S is the data matrix (in rows) and class labels (last column)
ã kp is a kernel's parameter
ã C is the parameter of the SVM algorithm
ã
ã Output: alpha1,y1-Lagrange multipliers & class labels for SV  
ã sv-support vectors (in rows)
ã b-bias (not geometrical)
ã crit-criterion value
ã ind-indices of SV
ã iter-number of iterations
ã margin-geometrical margin
ã Classification rule for X is '«b+(alpha1«y1)+.«Ker {sv;ôX;kp}' 

 
(Ker Ascent Mode) P : {
                   (S;kp;C)ûP;
                   alphaû(#S)Ò0.0; 
                   critûÉ0;condû1;iterû0;marginûÉ0;
                   xû¢1Õ@1 S;
                   yû,¢1Ù@1 S;
                   RûÓ/+/@1 x*2; 
                   KMûR+Ker {x;ôx;kp};
                   â(`soft_2=0ØMode)/'(0 0ôKM)û(0 0ôKM)+ßC';
                   etaûß0 0ôKM;
                   case (1ØMode) 
                    {
                     2;StCritû'KKT {crit;alpha;y;C;KM;0ØMode}';
                     3;StCritû'FeasGap {crit;alpha;y;C;KM;0ØMode}';
                     StCritû'ObjGrowth {crit;alpha;y;KM}'
                    }; 
                   while (cond)
                    {
                     iû0;iterûiter+1;
                     while (i<#S)
                      {
                       alpha[i]ûalpha[i]+eta[i]«1-y[i]«(alpha«y)+.«KM[i;];
                       case (0ØMode)
                        {
                         `soft_1;alpha[i]û0ÓCÄalpha[i];
                          alpha[i]û0Óalpha[i]
                        };
                       iûi+1 
                      };
                     â(`soft_2=0ØMode)/'(0 0ôKM)û(0 0ôKM)-ßC';
                     marginûmargin,((alpha«y)+.«(KM-R)+.«,@0 alpha«y)*¢0.5;
                     â(`soft_2=0ØMode)/'(0 0ôKM)û(0 0ôKM)+ßC';
                     (crit;cond)ûâStCrit;
                    };
                   (alpha1;y1;sv;ind)û(<alpha¨0)/¡(alpha;y;x;É#x);
                   bûR«y1+.«alpha1;
                   (alpha1;y1;sv;b;crit;ind;iter;margin) 
                      }