ginisvm.cpp

一种新的SVM算法

	                     (a11 - a11old) + 2*rdist/C[currptr->dataind]*(a11 - a11old)+
	      	             k12*
		             (a21 - a21old);
             }

             if ( currptr->dataind == i2 )
             {
                 currptr->E += k12*
	                     (a11 - a11old) + 2*rdist/C[currptr->dataind]*(a21 - a21old)+
	      	             k22*
		             (a21 - a21old);
             }

             if (( currptr->dataind != i2 ) && ( currptr->dataind != i1))
             {
                 currptr->E += kernel->Value(traindata,currptr->dataind,i1,dimension)*
	                     (a11 - a11old) + 
	      	             kernel->Value(traindata,currptr->dataind,i2,dimension)*
		             (a21 - a21old);
             }

	     if ( (otherptr = svmap[currptr->dataind][c2]) != (GINI_Set*) GINI_NULL )
             {
                otherptr->E = -(currptr->E + 2*rdist*(Y[currptr->dataind][c1] - currptr->alpha/C[currptr->dataind])) +
			       -2*rdist*(Y[currptr->dataind][c2] - otherptr->alpha/C[currptr->dataind]);
             }
	     //else
             //{
             //   printf("Binary Case: Two sv lists unsynchronized\n");
             //}
       
            // Update the maximum and min E for purposes of second heuristic
            // Use the true gradient information in update.
            if ( currptr->E  > maxE[c1]->E )
            {
               maxE[c1] = currptr;
            }

            if ( currptr->E  < minE[c1]->E )
            {
               minE[c1] = currptr;
            }
         }
         currptr = currptr->next;
      }

      currptr = svset[c2];
      minE[c2] = currptr;
      maxE[c2] = currptr;
      while ( currptr != (GINI_Set*) GINI_NULL )
      {
         if ( currptr->shrinklevel == 0 )
         {
            if ( currptr->E > maxE[c2]->E )
            {
               maxE[c2] = currptr;
            }

            if ( currptr->E < minE[c2]->E )
            {
               minE[c2] = currptr;
            }
         }
         currptr = currptr->next;
      }
   }
   else
   {

      // 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*
	                     (a11 - a11old) + 2*rdist/C[currptr->dataind]*(a11 - a11old)+
	         	          k12*
		             (a21 - a21old);
             }

             if ( currptr->dataind == i2 )
             {
                 currptr->E += k12*
	                     (a11 - a11old) + 2*rdist/C[currptr->dataind]*(a21 - a21old)+
	         	          k22*
		             (a21 - a21old);
             }

             if (( currptr->dataind != i2 ) && ( currptr->dataind != i1))
             {
                 currptr->E += kernel->Value(traindata,currptr->dataind,i1,dimension)*
	                     (a11 - a11old) + 
	      	             kernel->Value(traindata,currptr->dataind,i2,dimension)*
		             (a21 - a21old);
             }

            // Update the maximum and min E for purposes of second heuristic
            // Use the true gradient information in update.
            if ( currptr->E  > maxE[c1]->E )
            {
               maxE[c1] = currptr;
            }

            if ( currptr->E  < minE[c1]->E )
            {
               minE[c1] = currptr;
            }
         }
         currptr = currptr->next;
      }

      currptr = svset[c2];
      minE[c2] = currptr;
      maxE[c2] = currptr;
      while ( currptr != (GINI_Set*) GINI_NULL )
      {
         if ( currptr->shrinklevel == 0 )
         {
            if ( currptr->dataind == i1 )
            {
               currptr->E += k11*
	                     (a12 - a12old) + 2*rdist/C[currptr->dataind]*(a12 - a12old)+
	      	             k12*
		             (a22 - a22old);
            }

            if ( currptr->dataind == i2 )
            {
               currptr->E += k12*
	                     (a12 - a12old) + 2*rdist/C[currptr->dataind]*(a22 - a22old)+
	   	             k22*
		             (a22 - a22old);
            }

            if (( currptr->dataind != i2 ) && ( currptr->dataind != i1 ))
            {
               currptr->E += kernel->Value(traindata,currptr->dataind,i1,dimension)*
	                        (a12 - a12old) + 
	   	             kernel->Value(traindata,currptr->dataind,i2,dimension)*
		             (a22 - a22old);
            }

            if ( currptr->E > maxE[c2]->E )
            {
               maxE[c2] = currptr;
            }

            if ( currptr->E < minE[c2]->E )
            {
               minE[c2] = currptr;
            }
         }
         currptr = currptr->next;
      }
   }

   // Now estimate the biases
   //_biasestimate();
   // If one of a11 and a12 are at bounds and one of a21 and a22 is also
   // at bounds then estimate the bias by averaging. Otherwise one can obtain
   // an immediate estimate of the bias.

   if ((( svmap[i1][c1] == (GINI_Set*) GINI_NULL )  ||
        ( svmap[i1][c2] == (GINI_Set*) GINI_NULL )) && 
       (( svmap[i2][c1] == (GINI_Set*) GINI_NULL )  || 
        ( svmap[i2][c2] == (GINI_Set*) GINI_NULL ))
   )
   {
      _biasestimate();
   }
   else
   {
      if ((( svmap[i1][c1] != (GINI_Set*) GINI_NULL )  &&
           ( svmap[i1][c2] != (GINI_Set*) GINI_NULL ))
      )
      {
         if ( c1 > c2 )
         {
            bias[c2] = bias[c1] + svmap[i1][c1]->E - svmap[i1][c2]->E; 
         }
	 else
         {
            bias[c1] = bias[c2] - svmap[i1][c1]->E + svmap[i1][c2]->E;
         }
      }
      else
      {
         if ( c1 > c2 )
         {
            bias[c2] = bias[c1] + svmap[i2][c1]->E - svmap[i2][c2]->E; 
         }
	 else
         {
            bias[c1] = bias[c2] - svmap[i2][c1]->E + svmap[i2][c2]->E;
         }
       }
    }

   timer8 += currtimeval(&tv);

   //iterations++;

   #ifdef _HMMSVM_DEBUGON_
   //printf("%6d: %2d %2d %2d %2d %3.7f %3.7f %3.7f %3.7f %3.7f\n",iterations,i1,i2,c1,c2,a11,a11old,eta,bias[0],CostFunction());
   //printf("%2d\n%2d\n%2d\n%2d\n",i1,i2,c1,c2);
   //printf("%6d: %2d %2d %2d %2d %3.7f %3.7f %3.7f \n",iterations,i1,i2,c1,c2,a11,a11old,eta);
   #endif
   return 1;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_u32 GINI_SVMBlock::_minmaxopt( )
{
   GINI_u32 i1,i2,c2,i,c1,count,totalchanged;
   GINI_Set *currptr;
   GINI_bool found;
   GINI_double evalue;

   struct timeval tv;
   struct timezone tz;
   (void) gettimeofday(&tv,&tz);

   count = 1;
   totalchanged = 0;

   while ( count > 0 )
   {
      count = 0;
      for ( c1 = 0; c1 < classes; c1++ )
      {
         if ( setsize[c1] > 0 )
         {
            i1 = minE[c1]->dataind;
            if ( _getdirection(i1,c1) == GINI_UP_DOWN )
            {
               i2 = maxE[c1]->dataind;

               // maximum g12 maximum g21 and a11 and a22 can go up
               c2 = 0;
               evalue = 9999999;
               found = GINI_FALSE;
               for ( i = 0; i < classes; i++ )
               {
                  if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
                      ( i != c1 ) &&
	              (_getdirection(i2,i) == GINI_UP_DOWN ))
                  {
                     if ( currptr->shrinklevel == 0 )
                     {
                        if ( evalue > currptr->E )
                        {
                           evalue = currptr->E;
		           c2 = i;
	                   found = GINI_TRUE;
                        }
                      }
                   }
               }

               // Once the second class is found choose the
               // data point in that set corresponding to the
               // maximum gradient.
               if ( found == GINI_TRUE )
               {
                  if ( setsize[c1] > 0 )
                  {
                     if ( _takestep(i1,c1,i2,c2,&(minE[c1]->E),&evalue,&(maxE[c1]->E), (GINI_double*)GINI_NULL ))
                     {
                        phase1++;
      	   	        count++;
                     }
                  }
               }
            }
         }
      }
      totalchanged += count;
   }

   timer3 += currtimeval(&tv);
   return totalchanged;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_u32 GINI_SVMBlock::_examineExample( GINI_u32 i1 )
{
   GINI_u32 i2,c2,i,c1,count;
   GINI_Set *currptr, *startptr;
   GINI_bool found;
   GINI_double g11,evalue;
   GINI_status dir;

   struct timeval tv;
   struct timezone tz;
   (void) gettimeofday(&tv,&tz);

   // First evaluate the KKT condition for this data point
   // and choose the corresponding class for which its violated.
   if ( _kktcondition(i1,&c1,&g11,&dir) == GINI_FALSE )
   {
      timer1 += currtimeval(&tv);
      return 0;
   }
   timer1 += currtimeval(&tv);

   // We would want to select other three set of data points
   // such that there is a maximum decrease in the cost function.
   // The valid combinations are 
   // (GINI_DOWN, GINI_UP_DOWN, GINI_UP_DOWN, *)
   // (GINI_UP_DOWN, * , * , * )
   
   // Strategy 1
   // First search along the same data point but different
   // class, if there exist an sv and if there is one choose
   // the one with the maximum or minimum gradient depending
   // on the sign of g11 and dir.
   //
   if ( setsize[c1] > 0 )
   {
      if ( dir == GINI_DOWN )
      {
         // minimum g21 minimum g22 and a12 and a21 can go up
         c2 = 0;
         evalue = 9999999;
         found = GINI_FALSE;
         for ( i = 0; i < classes; i++ )
         {
            if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
                ( i != c1 ))
	    {  
	        if (((_getdirection(i1,i) == GINI_UP_DOWN ) &&
	            (_getdirection(minE[c1]->dataind,c1) == GINI_UP_DOWN))||
	            (_getdirection(minE[c1]->dataind,i) == GINI_UP_DOWN ))
                {
                     if ( currptr->shrinklevel == 0 )
                     {
                        if ( evalue > currptr->E )
                        {
                           evalue = currptr->E;
		           c2 = i;
	                   found = GINI_TRUE;
                        }
                     }
                }
             }
         }

         // Once the second class is found choose the
         // data point in that set corresponding to the
         // maximum gradient.
         if ( found == GINI_TRUE )
         {
            if ( _takestep(i1,c1,minE[c1]->dataind,c2,&g11,&evalue,&(minE[c1]->E), (GINI_double*)GINI_NULL ))
            {
               phase1++;
               return 1;
            }
         }
      }
      else
      {
          // If there is no specific choice of current data point
          // then try either direction.
          // Check which directional gradient is bigger g11-min(g21)
         if ( fabs(g11-minE[c1]->E) > fabs(g11-maxE[c1]->E))
         {
            // First min g12 and max g22
            c2 = 0;
            evalue = 9999999;
            found = GINI_FALSE;
            for ( i = 0; i < classes; i++ )
            {
               if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
                ( i != c1 ) &&
	        (_getdirection(i1,i) == GINI_UP_DOWN)) 
               {
                   if ( currptr->shrinklevel == 0 )
                   {
                        if ( evalue > currptr->E )
                        {
                           evalue = currptr->E;
		           c2 = i;
	                   found = GINI_TRUE;
                        }
                     }
                 }
             }

            // Once the second class is found choose the
            // data point in that set corresponding to the
            // maximum gradient.
            if ( found == GINI_TRUE )
            {
               if ( _getdirection(minE[c1]->dataind,c1) == GINI_UP_DOWN )
               {
                  if ( _takestep(i1,c1,minE[c1]->dataind,c2,&g11,&evalue,&(minE[c1]->E),(GINI_double*)GINI_NULL ))
                  {
                     phase1++;
                     return 1;
                  }
               }
            }
         }
         else
         {
            // If the previous step was unsuccesful try
            // the other direction now
            // max g12 and min g22
            c2 = 0;
            evalue = -9999999;
            found = GINI_FALSE;
            for ( i = 0; i < classes; i++ )
            {
               if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
                ( i != c1 ) &&
	        ( _getdirection(maxE[c1]->dataind,i) == GINI_UP_DOWN) &&
	        (_getdirection(maxE[c1]->dataind,i) == GINI_UP_DOWN ))
               {
                  if ( currptr->shrinklevel == 0 )
                   {
                        if ( evalue < currptr->E )
                        {
                           evalue = currptr->E;
		           c2 = i;
	                   found = GINI_TRUE;
                        }
                     }
                 }
             }

            // Once the second class is found choose the
            // data point in that set corresponding to the
            // maximum gradient.
            if ( found == GINI_TRUE )
            {
               if ( _takestep(i1,c1,maxE[c1]->dataind,c2,&g11,&evalue,&(maxE[c1]->E),(GINI_double*)GINI_NULL ))