regsmoimproved.java

Weka

      m_bUp = Double.MAX_VALUE; 
      m_bLow = -Double.MAX_VALUE; 
      for (int j = m_I0.getNext(-1); j != -1; j = m_I0.getNext(j)) {
	updateBoundaries(j, m_error[j]);
      }
      if (!m_I0.contains(i1)) {
	updateBoundaries(i1, m_error[i1]);
      }
      if (!m_I0.contains(i2)) {
	updateBoundaries(i2, m_error[i2]);
      }
      
      return 1;
    } 
    else {
      return 0;
    }
  }
  
  /**
   * updates the index sets I0a, IOb, I1, I2 and I3 for vector i
   * 
   * @param i index of vector
   * @param C capacity for vector i
   * @throws Exception
   */
  protected void updateIndexSetFor(int i, double C) throws Exception {
    /*
     m_I0a.delete(i);
     m_I0b.delete(i);
     m_I1.delete(i);
     m_I2.delete(i);
     m_I3.delete(i);
     */
    if (m_alpha[i] == 0 && m_alphaStar[i] == 0) {
      //m_I1.insert(i);
      m_iSet[i] = I1;
      m_I0.delete(i);
    } else if (m_alpha[i] > 0) {
      if (m_alpha[i] < C) {
	if ((m_iSet[i] & I0) == 0) {
	  //m_error[i] = -SVMOutput(i) - m_b + m_target[i];
	  m_I0.insert(i);
	}
	//m_I0a.insert(i);
	m_iSet[i] = I0a;
      } else { // m_alpha[i] == C
	//m_I3.insert(i);
	m_iSet[i] = I3;
	m_I0.delete(i);
      }
    } else {// m_alphaStar[i] > 0 
      if (m_alphaStar[i] < C) {
	if ((m_iSet[i] & I0) == 0) {
	  //m_error[i] = -SVMOutput(i) - m_b + m_target[i];
	  m_I0.insert(i);
	}
	//m_I0b.insert(i);
	m_iSet[i] = I0b;
      } else { // m_alpha[i] == C
	//m_I2.insert(i);
	m_iSet[i] = I2;
	m_I0.delete(i);
      }
    }
  }
  
  /**
   * updates boundaries bLow and bHi and corresponding indexes
   * 
   * @param i2 index of vector
   * @param F2 error of vector i2
   */
  protected void updateBoundaries(int i2, double F2) {		
    int iSet = m_iSet[i2];
    
    double FLow = m_bLow;
    if ((iSet & (I2 | I0b)) > 0) {
      FLow = F2 + m_epsilon;
    } else if ((iSet & (I1 | I0a)) > 0) {
      FLow = F2 - m_epsilon;
    }
    if (m_bLow < FLow) {
      m_bLow = FLow;
      m_iLow = i2;
    }
    double FUp = m_bUp;
    if ((iSet & (I3 | I0a)) > 0) {
      FUp = F2 - m_epsilon;
    } else if ((iSet & (I1 | I0b)) > 0) {
      FUp = F2 + m_epsilon;
    }
    if (m_bUp > FUp) {
      m_bUp = FUp;
      m_iUp = i2;
    }
  }
  
  /** 
   * parameters correspond to pseudocode from paper.
   * 
   * @param i2 index of  candidate
   * @return
   * @throws Exception
   */
  protected int examineExample(int i2) throws Exception {
    //procedure examineExample(i2)
    //
    //  alpha2, alpha2' = Lagrange multipliers for i2 
    double alpha2 = m_alpha[i2];
    double alpha2Star = m_alphaStar[i2];
    
    //  if (i2 is in I.0)
    //    F2 = f-cache[i2] 
    //  else
    //    compute F2 = F.i2 and set f-cache[i2] = F2 
    //    % Update (b.low, i.low) or (b.up, i.up) using (F2, i2)... 
    //    if (i2 is in I.1)
    //      if (F2+epsilon < b.up)
    //        b.up = F2+epsilon, 
    //        i.up = i2 
    //      elseif (F2-epsilon > b.low)
    //        b.low = F2-epsilon, 
    //        i.low = i2 
    //      end if 
    //    elseif ( (i2 is in I.2) && (F2+epsilon > b.low) )
    //      b.low = F2+epsilon, 
    //      i.low = i2 
    //    elseif ( (i2 is in I.3) && (F2-epsilon < b.up) )
    //      b.up = F2-epsilon, 
    //      i.up = i2 
    //    endif 
    //  endif 
    
    int iSet = m_iSet[i2];
    double F2 = m_error[i2];
    if (!m_I0.contains(i2)) {
      F2 = -SVMOutput(i2) - m_b + m_target[i2];
      m_error[i2] = F2;
      if (iSet == I1) {
	if (F2 + m_epsilon < m_bUp) {
	  m_bUp = F2 + m_epsilon;
	  m_iUp = i2;
	} else if (F2 - m_epsilon > m_bLow) {
	  m_bLow = F2 - m_epsilon;
	  m_iLow = i2;
	} 
      } else if ((iSet == I2) && (F2 + m_epsilon > m_bLow)) {
	m_bLow = F2 + m_epsilon;
	m_iLow = i2;
      } else if ((iSet == I3) && (F2 - m_epsilon < m_bUp)) {
	m_bUp = F2 - m_epsilon;
	m_iUp = i2;
      }
    }
    
    //  % Check optimality using current b.low and b.up and, if 
    //  % violated, find an index i1 to do joint optimization with i2... 
    //  optimality = 1;
    //  case 1: i2 is in I.0a
    //    if (b.low-(F2-epsilon) > 2 * tol)
    //      optimality = 0;  
    //      i1 = i.low; 
    //      % For i2 in I.0a choose the better i1... 
    //      if ((F2-epsilon)-b.up > b.low-(F2-epsilon))
    //        i1 = i.up; 
    //      endif 
    //    elseif ((F2-epsilon)-b.up > 2 * tol)
    //      optimality = 0; 
    //      i1 = i.up; 
    //      % For i2 in I.0a choose the better i1... 
    //      if ((b.low-(F2-epsilon) > (F2-epsilon)-b.up)
    //        i1 = i.low; 
    //      endif 
    //    endif 
    //  case 2: i2 is in I.0b
    //    if (b.low-(F2+epsilon) > 2 * tol)
    //      optimality = 0; 
    //      i1 = i.low; 
    //      % For i2 in I.0b choose the better i1... 
    //      if ((F2+epsilon)-b.up > b.low-(F2+epsilon))
    //        i1 = i.up; 
    //      endif 
    //    elseif ((F2+epsilon)-b.up > 2 * tol)
    //      optimality = 0; 
    //      i1 = i.up; 
    //      % For i2 in I.0b choose the better i1... 
    //      if ((b.low-(F2+epsilon) > (F2+epsilon)-b.up)
    //        i1 = i.low; 
    //      endif 
    //    endif 
    //  case 3: i2 is in I.1
    //    if (b.low-(F2+epsilon) > 2 * tol)
    //      optimality = 0; 
    //      i1 = i.low; 
    //      % For i2 in I1 choose the better i1... 
    //      if ((F2+epsilon)-b.up > b.low-(F2+epsilon)
    //        i1 = i.up; 
    //      endif 
    //    elseif ((F2-epsilon)-b.up > 2 * tol)
    //      optimality = 0; 
    //      i1 = i.up; 
    //      % For i2 in I1 choose the better i1... 
    //      if (b.low-(F2-epsilon) > (F2-epsilon)-b.up)
    //        i1 = i.low; 
    //      endif 
    //    endif 
    //  case 4: i2 is in I.2
    //    if ((F2+epsilon)-b.up > 2*tol)
    //      optimality = 0, 
    //      i1 = i.up 
    //     endif 
    //  case 5: i2 is in I.3
    //    if ((b.low-(F2-epsilon) > 2*tol)
    //      optimality = 0, i1 = i.low 
    //    endif
    
    int i1 = i2;
    boolean bOptimality = true;
    //case 1: i2 is in I.0a
    if (iSet == I0a) {
      if (m_bLow - (F2 - m_epsilon) > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iLow;
	//% For i2 in I .0 a choose the better i1...
	if ((F2 - m_epsilon) - m_bUp > m_bLow - (F2 - m_epsilon)) {
	  i1 = m_iUp;
	}
      } else if ((F2 - m_epsilon) - m_bUp > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iUp;
	//% For i2 in I.0a choose the better i1... 
	if (m_bLow - (F2 - m_epsilon) > (F2 - m_epsilon) - m_bUp) {
	  i1 = m_iLow;
	}
      }
    } // case 2: i2 is in I.0b
    else if (iSet == I0b) {
      if (m_bLow - (F2 + m_epsilon) > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iLow; // % For i2 in I.0b choose the better i1... 
	if ((F2 + m_epsilon) - m_bUp > m_bLow - (F2 + m_epsilon)) {
	  i1 = m_iUp;
	}
      } else if ((F2 + m_epsilon) - m_bUp > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iUp; // % For i2 in I.0b choose the better i1... 
	if (m_bLow - (F2 + m_epsilon) > (F2 + m_epsilon) - m_bUp) {
	  i1 = m_iLow;
	}
      }
    } // case 3: i2 is in I.1
    else if (iSet == I1) {
      if (m_bLow - (F2 + m_epsilon) > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iLow;
	//% For i2 in I1 choose the better i1...
	if ((F2 + m_epsilon) - m_bUp > m_bLow - (F2 + m_epsilon)) {
	  i1 = m_iUp;
	}
      } else if ((F2 - m_epsilon) - m_bUp > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iUp; // % For i2 in I1 choose the better i1... 
	if (m_bLow - (F2 - m_epsilon) > (F2 - m_epsilon) - m_bUp) {
	  i1 = m_iLow;
	}
      }
    } //case 4: i2 is in I.2
    else if (iSet == I2) {
      if ((F2 + m_epsilon) - m_bUp > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iUp;
      }
    } //case 5: i2 is in I.3
    else if (iSet == I3) {
      if (m_bLow - (F2 - m_epsilon) > 2 * m_fTolerance) {
	bOptimality = false;
	i1 = m_iLow;
      }
    }
    // if (optimality == 1) 
    //    return 0
    //  if (takeStep(i1, i2))
    //    return 1 
    //   else
    //    return 0 
    //  endif 
    //endprocedure
    if (bOptimality) {
      return 0;
    }
    return takeStep(i1, i2, m_alpha[i2], m_alphaStar[i2], F2);
  }
  
  /** 
   * initialize various variables before starting the actual optimizer 
   * 
   * @param data 	data set used for learning
   * @throws Exception	if something goes wrong
   */
  protected void init(Instances data) throws Exception {
    super.init(data);
    // from Keerthi's pseudo code:
    //  set alpha and alpha' to zero for every example set I.1 to contain all the examples 
    //  Choose any example i from the training set. 
    //  set b.up = target[i]+epsilon 
    //  set b.low = target[i]-espilon 
    //  i.up = i.low = i; 
    // Initialize sets
    m_I0 = new SMOset(m_data.numInstances());
    m_iSet = new int [m_data.numInstances()];
    for (int i = 0; i < m_nInstances; i++) {
      m_iSet[i] = I1;
    }
    // m_iUp = m_random.nextInt(m_nInstances);
    m_iUp = 0;
    m_bUp = m_target[m_iUp] + m_epsilon;
    m_iLow = m_iUp;
    m_bLow = m_target[m_iLow] - m_epsilon;
    //init error cache
    m_error = new double[m_nInstances];
    for (int i = 0; i < m_nInstances; i++) {
      m_error[i] = m_target[i];
    }
  }
  
  /** 
   * use variant 1 of Shevade's et al.s paper
   * 
   * @throws Exception	if something goes wrong
   */
  protected void optimize1() throws Exception {
    //% main routine for modification 1 procedure main
    //  while (numChanged > 0 || examineAll)
    //    numChanged = 0; 
    int nNumChanged = 0;
    boolean bExamineAll = true;
    //  while (numChanged > 0 || examineAll)
    //    numChanged = 0; 
    while (nNumChanged > 0 || bExamineAll) {
      nNumChanged = 0;
      //    if (examineAll)
      //      loop I over all the training examples
      //        numChanged += examineExample(I) 
      //    else
      //      loop I over I.0
      //        numChanged += examineExample(I) 
      //        % It is easy to check if optimality on I.0 is attained... 
      //        if (b.up > b.low - 2*tol) at any I
      //          exit the loop after setting numChanged = 0 
      //        endif 
      if (bExamineAll) {
	for (int i = 0; i < m_nInstances; i++) {
	  nNumChanged += examineExample(i);
	}
      } else {
	for (int i = m_I0.getNext(-1); i != -1; i = m_I0.getNext(i)) {
	  
	  nNumChanged += examineExample(i);
	  if (m_bLow - m_bUp < 2 * m_fTolerance) {
	    nNumChanged = 0;
	    break;
	  }
	}
      } //    if (examineAll == 1)
      //      examineAll = 0; 
      //    elseif (numChanged == 0)
      //      examineAll = 1;
      //    endif 
      //  endwhile 
      //endprocedure
      if (bExamineAll) {
	bExamineAll = false;
      } else if (nNumChanged == 0) {
	bExamineAll = true;
      }
    }
  }
  
  /** 
   * use variant 2 of Shevade's et al.s paper 
   * 
   * @throws Exception	if something goes wrong
   */
  protected void optimize2() throws Exception {
    //% main routine for modification 2 procedure main
    int nNumChanged = 0;
    boolean bExamineAll = true;
    //  while (numChanged > 0 || examineAll)
    //    numChanged = 0; 
    while (nNumChanged > 0 || bExamineAll) {
      nNumChanged = 0;
      //    if (examineAll)
      //      loop I over all the training examples
      //        numChanged += examineExample(I) 
      //    else
      //      % The following loop is the only difference between the two 
      //      % SMO modifications. Whereas, modification 1, the type II 
      //      % loop selects i2 fro I.0 sequentially, here i2 is always 
      //      % set to the current i.low and i1 is set to the current i.up; 
      //      % clearly, this corresponds to choosing the worst violating 
      //      % pair using members of I.0 and some other indices
      //      inner.loop.success = 1; 
      //      do
      //        i2 = i.low 
      //	      alpha2, alpha2' = Lagrange multipliers for i2 
      //	      F2 = f-cache[i2] 
      //	      i1 = i.up 
      //	      inner.loop.success = takeStep(i.up, i.low) 
      //	      numChanged += inner.loop.success 
      //      until ( (b.up > b.low - 2*tol) || inner.loop.success == 0) 
      //      numChanged = 0; 
      //    endif 
      if (bExamineAll) {
	for (int i = 0; i < m_nInstances; i++) {
	  nNumChanged += examineExample(i);
	}
      } else {
	boolean bInnerLoopSuccess = true;
	do {
	  if (takeStep(m_iUp, m_iLow, m_alpha[m_iLow], m_alphaStar[m_iLow], m_error[m_iLow]) > 0) {
	    bInnerLoopSuccess = true;
	    nNumChanged += 1;
	  } else {
	    bInnerLoopSuccess = false;
	  }
	} while ((m_bUp <= m_bLow - 2 * m_fTolerance) && bInnerLoopSuccess);
	nNumChanged = 0;
      } //
      //    if (examineAll == 1)
      //      examineAll = 0 
      //    elseif (numChanged == 0)
      //      examineAll = 1 
      //    endif 
      //  endwhile 
      //endprocedure
      //
      if (bExamineAll) {
	bExamineAll = false;
      } else if (nNumChanged == 0) {
	bExamineAll = true;
      }
    }
  }
  
  /** 
   * wrap up various variables to save memeory and do some housekeeping after optimization
   * has finished.
   *
   * @throws Exception 	if something goes wrong
   */
  protected void wrapUp() throws Exception {
    m_b = -(m_bLow + m_bUp) / 2.0;
    m_target = null;
    m_error = null;
    super.wrapUp();
  }
  
  /** 
   * learn SVM parameters from data using Keerthi's SMO algorithm.
   * Subclasses should implement something more interesting.
   * 
   * @param instances	the data to work with
   * @throws Exception	if something goes wrong
   */
  public void buildClassifier(Instances instances) throws Exception {
    // initialize variables		
    init(instances); 

    // solve optimization problem
    if (m_bUseVariant1) {
      optimize1();
    } else {
      optimize2();
    } 
    
    // clean up
    wrapUp();
  }
}