ginisvm.cpp

一种新的SVM算法

	 previouscost = currentcost;
	 if ( verbose == GINI_TRUE)
         {
            printf("Iteration = %d,Number changed = %d,Cost = %f\n",iterations+1,numchanged,currentcost);
            fflush(stdout);
         }
      }
      else
      {
	 if ( verbose == GINI_TRUE)
         {
            printf("Iteration = %d,Number changed = %d\n",iterations+1,numchanged);
            fflush(stdout);
         }
      }


      // If all the data points were being examined   
      if ( examineAll == 1 )
      {
         if ( numchanged != 0 )
         {
            examineAll = 0;
         }
	 else
         {
               break;
         }
      }
      else
      {
         if ( numchanged == 0 )
         {
            examineAll = 1;
         }
      }
      iterations++;
   }
   timer4 += currtimeval(&tv1);


   printf("..Done !!\n");
   printtimers();
   printf("Final Cost = %f\n",CostFunction());
   fflush(stdout);
   return GINI_TRUE;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_u32 GINI_SVMBlock::_takestep( GINI_u32 i1,
                                   GINI_u32 c1,
                                   GINI_u32 i2,
                                   GINI_u32 c2,
				   GINI_double *e11,
				   GINI_double *e12,
				   GINI_double *e21,
				   GINI_double *e22
)
{
   GINI_double a11,a12,a21,a22;
   GINI_Set *currptr, *otherptr;

   struct timeval tv;
   struct timezone tz;

   //printf("Optimizing (%d,%d) and (%d,%d)\n",i1,c1,i2,c2);
   if (( i1 == i2 ) || (c1 == c2))
   {
      return 0;
   }

   // Update the kernel cache hits for these two data points
   // If the total number of hits for these points are 
   // greater than threshold hit value then replace i1 or i2
   // with the lowest activity cache.
   //kernel->UpdateCache(i1,i2);

   // First get the alpha values
   GINI_double a11old, E11;
   GINI_double a21old, E21;
   GINI_double a12old, E12;
   GINI_double a22old, E22;

   // compute a11
   if ((currptr = svmap[i1][c1]) != (GINI_Set*) GINI_NULL)
   {
      a11old = currptr->alpha;
   }
   else
   {
      a11old = 0;
   }

   // compute a12
   if ((currptr = svmap[i1][c2]) != (GINI_Set*) GINI_NULL)
   {
      a12old = currptr->alpha;
   }
   else
   {
      a12old = 0;
   }

   // compute a21
   if ((currptr = svmap[i2][c1]) != (GINI_Set*) GINI_NULL)
   {
      a21old = currptr->alpha;
   }
   else
   {
      a21old = 0;
   }

   // compute a22
   if ((currptr = svmap[i2][c2]) != (GINI_Set*) GINI_NULL)
   {
      a22old = currptr->alpha;
   }
   else
   {
      a22old = 0;
   }

   GINI_double y11 = Y[i1][c1];
   GINI_double y12 = Y[i1][c2];
   GINI_double y21 = Y[i2][c1];
   GINI_double y22 = Y[i2][c2];

   GINI_double C1 = C[i1];
   GINI_double C2 = C[i2];

   GINI_double k11,k12,k22,eta;

   GINI_double gamma1 = a11old + a21old;
   GINI_double gamma2 = a12old + a22old;
   GINI_double beta1 = a11old + a12old;

   GINI_double Low = GINI_MAX(gamma1 - C2*y21, beta1 - C1*y12);
   GINI_double High = GINI_MIN(C1*y11,C2*y22+beta1 - gamma2);

   if ( Low >= High )
   {
      return 0;
   }


   (void) gettimeofday(&tv,&tz);
   // compute a11
   if ( e11 == ( GINI_double*) GINI_NULL )
   {
      if ((currptr = svmap[i1][c1]) != (GINI_Set*) GINI_NULL)
      {
         E11 = currptr->E;
      }
      else
      {
         E11 = evaluateCache(i1,c1);
      }
   }
   else
   {
      E11 = *e11;
   }

   // compute a12
   if ( e12 == ( GINI_double*) GINI_NULL )
   {
      if ((currptr = svmap[i1][c2]) != (GINI_Set*) GINI_NULL)
      {
         E12 = currptr->E;
      }
      else
      {
         E12 = evaluateCache(i1,c2);
      }
   }
   else
   {
      E12 = *e12;
   }

   // compute a21
   if ( e21 == ( GINI_double*) GINI_NULL )
   {
      if ((currptr = svmap[i2][c1]) != (GINI_Set*) GINI_NULL)
      {
         E21 = currptr->E;
      }
      else
      {
         E21 = evaluateCache(i2,c1);
      }
   }
   else
   {
      E21 = *e21;
   }

   // compute a22
   if ( e22 == ( GINI_double*) GINI_NULL )
   {
      if ((currptr = svmap[i2][c2]) != (GINI_Set*) GINI_NULL)
      {
         E22 = currptr->E;
      }
      else
      {
         E22 = evaluateCache(i2,c2);
      }
   }
   else
   {
      E22 = *e22;
   }
   timer6 += currtimeval(&tv);


   // This step needs to be improved in the 
   // incremental approach because one wont 
   // need to compute one of the alpha values
   k11 = kernel->Value(
                        traindata,
                        i1,
                        i1,
                        dimension
         );
   k12 = kernel->Value(
                        traindata,
                        i1,
                        i2,
                        dimension
         );
   k22 = kernel->Value(
                        traindata,
                        i2,
                        i2,
                        dimension
         );

   // Check the second derivative of the cost function
   // if its negetive means we are in business and 
   // there fore means that there exist a maxima in the
   // region of interest.
   eta = 2*(k11 + k22 -2*k12) + 4*rdist/C1 + 4*rdist/C2;

   if ( eta > 0)
   {
      
      // Compute the RHS of the newton raphson iterate
      a11 = a11old - (E11 + E22 - E12 - E21 )/eta;

      if (a11 >= High)
      {
         a11 = High;
      }
      else
      {
         if (a11 <= Low)
         {
            a11 = Low;
         }
      }


      if (fabs(a11-a11old) <= alphaeps)
      {
         return 0;
      }

      a12 = beta1 - a11;
      a21 = gamma1 - a11;
      a22 = gamma2 - beta1 + a11;
   }
   else
   {
      // If the kernel matrix is not pd
      return 0;
   }

   (void) gettimeofday(&tv,&tz);
   // Now check to see if any housekeeping has to be done
   //
   //  a11
   if ( (currptr = svmap[i1][c1]) != (GINI_Set*) GINI_NULL )
   {
      // i1,c1 was an sv and not an sv now then remove it
      // from the svset.
      if (( a11 < alphaeps ) && ( a11 > -alphaeps))
      {
         _removeelement(c1,currptr);
	 svmap[i1][c1] = (GINI_Set*) GINI_NULL;
        cachefull = kernel->ResetActivity(i1);
	 setsize[c1]--;
      }
      else
      {
         currptr->alpha = a11;
	 if ( currptr->cachehits > numofhits )
         {
            cachefull = kernel->InsertCache(i1);
            currptr->cachehits = 0;
         }
	 else
         {
             currptr->cachehits++;
         }
      }
   }
   else
   {
      // i1,c1 was not an sv but now becomes an sv.
      if (( a11 >= alphaeps ) || ( a11 <= -alphaeps))
      {
         svmap[i1][c1] = _addelement(i1,c1,E11,a11);
	 //cachefull = kernel->InsertCache(i1);
	 setsize[c1]++;
      }
   }

   // a12
   if ( (currptr = svmap[i1][c2]) != (GINI_Set*) GINI_NULL )
   {
      // i1,c2 was an sv and not an sv now then remove it
      // from the svset and make the activity counter for
      // its cache = 0 if it exists.
      if (( a12 < alphaeps ) && ( a12 > -alphaeps))
      {
         _removeelement(c2,currptr);
	 svmap[i1][c2] = (GINI_Set*) GINI_NULL;
         cachefull = kernel->ResetActivity(i1);
	 setsize[c2]--;
      }
      else
      {
         currptr->alpha = a12;
	 if ( currptr->cachehits > numofhits )
         {
            cachefull = kernel->InsertCache(i1);
            currptr->cachehits = 0;
         }
	 else
         {
             currptr->cachehits++;
         }
      }
   }
   else
   {
      // i1,c2 was not an sv but now becomes an sv.
      if (( a12 >= alphaeps ) || ( a12 <= -alphaeps))
      {
         svmap[i1][c2] = _addelement(i1,c2,E12,a12);
	 //cachefull = kernel->InsertCache(i1);
	 setsize[c2]++;
      }
   }

   // a21
   if ( (currptr = svmap[i2][c1]) != (GINI_Set*) GINI_NULL )
   {
      // i2,c1 was an sv and not an sv now then remove it
      // from the svset.
      if (( a21 < alphaeps ) && ( a21 > -alphaeps))
      {
         _removeelement(c1,currptr);
	 svmap[i2][c1] = (GINI_Set*) GINI_NULL;
         cachefull = kernel->ResetActivity(i2);
	 setsize[c1]--;
      }
      else
      {
         currptr->alpha = a21;
	 if ( currptr->cachehits > numofhits )
         {
            cachefull = kernel->InsertCache(i2);
            currptr->cachehits = 0;
         }
	 else
         {
             currptr->cachehits++;
         }
      }
   }
   else
   {
      // i2,c1 was not an sv but now becomes an sv.
      if (( a21 >= alphaeps ) || ( a21 <= -alphaeps))
      {
         svmap[i2][c1] = _addelement(i2,c1,E21,a21);
	 //cachefull = kernel->InsertCache(i2);
	 setsize[c1]++;
      }
   }

   // a22
   if ( (currptr = svmap[i2][c2]) != (GINI_Set*) GINI_NULL )
   {
      // i2,c2 was an sv and not an sv now then remove it
      // from the svset.
      if (( a22 < alphaeps ) && ( a22 > -alphaeps))
      {
         _removeelement(c2,currptr);
	 svmap[i2][c2] = (GINI_Set*) GINI_NULL;
         cachefull = kernel->ResetActivity(i2);
	 setsize[c2]--;
      }
      else
      {
         currptr->alpha = a22;
	 if ( currptr->cachehits > numofhits )
         {
            cachefull = kernel->InsertCache(i2);
            currptr->cachehits = 0;
         }
	 else
         {
             currptr->cachehits++;
         }
      }
   }
   else
   {
      // i2,c2 was not an sv but now becomes an sv.
      if (( a22 >= alphaeps ) || ( a22 <= -alphaeps))
      {
         svmap[i2][c2] = _addelement(i2,c2,E22,a22);
	 //cachefull = kernel->InsertCache(i2);
	 setsize[c2]++;
      }
   }
   timer7 += currtimeval(&tv);

   (void) gettimeofday(&tv,&tz);

   // A Special update procedure for two class problems
   // where each ecache is -ve of the other .


   if ( classes == 0 )
   {
      // Update the Ecache for all the unbounded vectors.
      currptr = svset[c1];
      minE[c1] = currptr;
      maxE[c1] = currptr;
      while ( currptr != (GINI_Set*) GINI_NULL )
      {
         if ( currptr->shrinklevel == 0 )
         {

             if ( currptr->dataind == i1 )
             {
                 currptr->E += k11*