Return to Revisions

2 of 3

added 8171 characters in body

edited Mar 14, 2015 at 5:41

difference between stochastic gradient descent and batch

I've watch the canonical Andrew Ng video on the subject but I'm trying to translate those concepts into java, and I'm not quite sure I did it right.

The thing that's confusing me is, I made a toy example where I had just a few inputs which were identical between the training and test set and still the algorithm misclassified some of the instances of the test set. how is that possible if it's correctly implemented?

I posted the output to the bottom.

For stochastic gradient descent we don't calculate the whole gradient, isn't that right? It's just approximated. I think that would look like this:

  double cost, error, hypothesis;
  double[] gradient;
  int p, iteration;
  
  //Randomly shuffle examples in the training set.
  feature_matrix__train = shuffleArray(feature_matrix__train);

  iteration = 0;
  do 
  {
    iteration++;
    error = 0.0;
    cost = 0.0;
    
    //loop through all instances (complete one epoch)
    for (p = 0; p < number_of_files__train; p++) 
    {
        
      // 1. Calculate the hypothesis h = X * theta
      hypothesis = calculateHypothesis( theta, feature_matrix__train, p, globo_dict_size );

      // 2. Calculate the loss = h - y and maybe the squared cost (loss^2)/2m
      cost = HingeLoss.deriv(hypothesis, outputs__train[p]);

      // STOCHASTIC
      
      //update weights and bias
      for (int i = 0; i < globo_dict_size; i++) 
      {
          theta[i] -= ( LEARNING_RATE * cost * feature_matrix__train[p][i] );
      }
      theta[ globo_dict_size ] -= ( LEARNING_RATE * cost );
      

      //summation of squared error (error value for all instances)
      error += cost;
      
    }
      
  /* Error */
  System.out.println("Iteration " + iteration + " : RMSE = " + error);

  } 
  while( error != 0.0 );

I think my implementation of batch gradient descent is correct, the F1 measure when I run it is generally much better, it looks like this:

  double cost, error, hypothesis;
  double[] gradient;
  int p, iteration;
  
  //Randomly shuffle examples in the training set.
  feature_matrix__train = shuffleArray(feature_matrix__train);

  iteration = 0;
  do 
  {
    iteration++;
    error = 0.0;
    cost = 0.0;
    
    //loop through all instances (complete one epoch)
    for (p = 0; p < number_of_files__train; p++) 
    {
        
      // 1. Calculate the hypothesis h = X * theta
      hypothesis = calculateHypothesis( theta, feature_matrix__train, p, globo_dict_size );

      // 2. Calculate the loss = h - y and maybe the squared cost (loss^2)/2m
      cost = HingeLoss.deriv(hypothesis, outputs__train[p]);
      
      // 3. Calculate the gradient = X' * loss / m
      gradient = calculateGradent( theta, feature_matrix__train, p, globo_dict_size, cost, number_of_files__train);
      
      // BATCH
      
      double[] temp = new double[ globo_dict_size + 1 ];//one for bias
      
      // populate temp to facilitate simultaneous update
      for (int i = 0; i < globo_dict_size; i++) 
      {
          temp[i] = theta[i] - (LEARNING_RATE * gradient[i] );
      }

      // 4. Update the parameters theta = theta - alpha * gradient
      for (int i = 0; i < globo_dict_size; i++) 
      {
          theta[i] = temp[i];
      }

      
      //summation of squared error (error value for all instances)
      error += cost;
      
    }
  
  /* Error */
  System.out.println("Iteration " + iteration + " : RMSE = " + error);

  } 
  while( error != 0.0 );

common methods:

static double calculateHypothesis( double[] theta, double[][] feature_matrix, int file_index, int globo_dict_size )
{
    double hypothesis = 0.0;

     for (int i = 0; i < globo_dict_size; i++) 
     {
         hypothesis += ( theta[i] * feature_matrix[file_index][i] );
     }
     //bias
     hypothesis += theta[ globo_dict_size ];

     return hypothesis;
}

// 3. Calculate the gradient = X' * loss / m
static double[] calculateGradent( double theta[], double[][] feature_matrix, int file_index, int globo_dict_size, double cost, int number_of_files__train)
{
    double m = number_of_files__train;

    double[] gradient = new double[ globo_dict_size + 1 ];//one for bias?
    
    for (int i = 0; i < globo_dict_size; i++) 
    {
        gradient[i] = (1.0/m) * cost * feature_matrix[ file_index ][ i ] ;
    }
    gradient[ globo_dict_size ] = (1.0/m) * cost;
    
    return gradient;
}



/**
 * Computes the first derivative of the HingeLoss loss
 *
 * @param pred the predicted value
 * @param y the target value
 * @return the first derivative of the HingeLoss loss
 */
public static double deriv(double pred, double y)
{
    if (pred * y > 1)
        return 0;
    else
        return -y;
}

output:

Iteration 1 : RMSE = -16.0
Iteration 2 : RMSE = -17.0
Iteration 3 : RMSE = 33.0
Iteration 4 : RMSE = -27.0
Iteration 5 : RMSE = 6.0
Iteration 6 : RMSE = -26.0
Iteration 7 : RMSE = -63.0
Iteration 8 : RMSE = 99.0
Iteration 9 : RMSE = 4.0
Iteration 10 : RMSE = 14.0
Iteration 11 : RMSE = -65.0
Iteration 12 : RMSE = 38.0
Iteration 13 : RMSE = -74.0
Iteration 14 : RMSE = 47.0
Iteration 15 : RMSE = -5.0
Iteration 16 : RMSE = 13.0
Iteration 17 : RMSE = -1.0
Iteration 18 : RMSE = -5.0
Iteration 19 : RMSE = 2.0
Iteration 20 : RMSE = -19.0
Iteration 21 : RMSE = -2.0
Iteration 22 : RMSE = 1.0
Iteration 23 : RMSE = -3.0
Iteration 24 : RMSE = -1.0
Iteration 25 : RMSE = -4.0
Iteration 26 : RMSE = -6.0
Iteration 27 : RMSE = -12.0
Iteration 28 : RMSE = 6.0
Iteration 29 : RMSE = -7.0
Iteration 30 : RMSE = -25.0
Iteration 31 : RMSE = 4.0
Iteration 32 : RMSE = 2.0
Iteration 33 : RMSE = -50.0
Iteration 34 : RMSE = 25.0
Iteration 35 : RMSE = 14.0
Iteration 36 : RMSE = -9.0
Iteration 37 : RMSE = 2.0
Iteration 38 : RMSE = 2.0
Iteration 39 : RMSE = -5.0
Iteration 40 : RMSE = 5.0
Iteration 41 : RMSE = -6.0
Iteration 42 : RMSE = -1.0
Iteration 43 : RMSE = -9.0
Iteration 44 : RMSE = -14.0
Iteration 45 : RMSE = 7.0
Iteration 46 : RMSE = -3.0
Iteration 47 : RMSE = -1.0
Iteration 48 : RMSE = -3.0
Iteration 49 : RMSE = -17.0
Iteration 50 : RMSE = 35.0
Iteration 51 : RMSE = -53.0
Iteration 52 : RMSE = -8.0
Iteration 53 : RMSE = 7.0
Iteration 54 : RMSE = 8.0
Iteration 55 : RMSE = 1.0
Iteration 56 : RMSE = -5.0
Iteration 57 : RMSE = -4.0
Iteration 58 : RMSE = -8.0
Iteration 59 : RMSE = -4.0
Iteration 60 : RMSE = 45.0
Iteration 61 : RMSE = -35.0
Iteration 62 : RMSE = -8.0
Iteration 63 : RMSE = -1.0
Iteration 64 : RMSE = 35.0
Iteration 65 : RMSE = -28.0
Iteration 66 : RMSE = -14.0
Iteration 67 : RMSE = -3.0
Iteration 68 : RMSE = 44.0
Iteration 69 : RMSE = -31.0
Iteration 70 : RMSE = -17.0
Iteration 71 : RMSE = -4.0
Iteration 72 : RMSE = -5.0
Iteration 73 : RMSE = -3.0
Iteration 74 : RMSE = 1.0
Iteration 75 : RMSE = -2.0
Iteration 76 : RMSE = 0.0

predicted class = 50457.42199999997
actual class = 1
actual class = atheism
predicted class = 64779.12979999999
actual class = 1
actual class = atheism
predicted class = 155274.41369999992
actual class = 1
actual class = atheism
predicted class = 16268.929400000005
actual class = 1
actual class = atheism
predicted class = 65070.488
actual class = -1
actual class = sports
predicted class = 29475.583900000012
actual class = -1
actual class = sports
predicted class = 44683.86869999996
actual class = 1
actual class = atheism
predicted class = 44222.1551
actual class = -1
actual class = sports
predicted class = 52243.577699999965
actual class = 1
actual class = atheism
predicted class = 2616.7108000000007
actual class = -1
actual class = sports
predicted class = 60042.59569999995
actual class = -1
actual class = sports
predicted class = 151362.31789999982
actual class = 1
actual class = atheism
predicted class = 1243225.2315999991
actual class = -1
actual class = sports
predicted class = 18299.483299999996
actual class = 1
actual class = atheism
predicted class = 183967.4760999999
actual class = -1
actual class = sports
predicted class = 15069.4296
actual class = 1
actual class = atheism
predicted class = 12009.7902
actual class = -1
actual class = sports
predicted class = 23624.264300000006
actual class = -1
actual class = sports
predicted class = 4582409.735300005
actual class = 1
actual class = atheism
predicted class = 31978.257100000006
actual class = -1
actual class = sports
predicted class = 9173.9383
actual class = -1
actual class = sports
predicted class = 26639.34180000004
actual class = -1
actual class = sports
predicted class = 7773.108999999988
actual class = 1
actual class = atheism
predicted class = 7858.3247999999985
actual class = -1
actual class = sports
predicted class = 23991.052800000027
actual class = -1
actual class = sports
predicted class = 41800.70529999999
actual class = 1
actual class = atheism
predicted class = 40648.43809999998
actual class = -1
actual class = sports
predicted class = 26526.71990000001
actual class = -1
actual class = sports
predicted class = 295667.80159999954
actual class = -1
actual class = sports
predicted class = 201615.1067000001
actual class = 1
actual class = atheism
predicted class = 12022.424099999997
actual class = -1
actual class = sports
predicted class = 5715.703499999996
actual class = -1
actual class = sports
predicted class = 76849.6456
actual class = -1
actual class = sports
predicted class = 180076.8394000001
actual class = -1
actual class = sports
predicted class = 17258.7375
actual class = 1
actual class = atheism
predicted class = 73382.19260000015
actual class = 1
actual class = atheism
predicted class = 522607.88489999995
actual class = -1
actual class = sports
predicted class = 29335.05869999999
actual class = -1
actual class = sports
predicted class = 77580.97530000006
actual class = 1
actual class = atheism
predicted class = 25397.604300000006
actual class = -1
actual class = sports
predicted class = 10660.961499999998
actual class = -1
actual class = sports
predicted class = 79155.03400000003
actual class = -1
actual class = sports
predicted class = 817652.6782999998
actual class = -1
actual class = sports
predicted class = 8153.0061000000005
actual class = -1
actual class = sports
predicted class = 19349.6999
actual class = 1
actual class = atheism
predicted class = 21350.88440000001
actual class = -1
actual class = sports
predicted class = 26731.873499999998
actual class = 1
actual class = atheism
predicted class = 108112.69579999986
actual class = 1
actual class = atheism
predicted class = 1.4391430652699986E7
actual class = -1
actual class = sports
predicted class = 71244.78130000009
actual class = -1
actual class = sports
predicted class = 44915.25499999998
actual class = 1
actual class = atheism
predicted class = 33958.75449999999
actual class = 1
actual class = atheism
predicted class = 35446.303799999994
actual class = -1
actual class = sports
predicted class = 885375.7129999998
actual class = -1
actual class = sports
predicted class = 24358.666900000022
actual class = -1
actual class = sports
predicted class = 55900.22339999999
actual class = -1
actual class = sports
predicted class = 79179.33790000001
actual class = 1
actual class = atheism
predicted class = 21336.85710000005
actual class = 1
actual class = atheism
predicted class = 247084.00379999998
actual class = 1
actual class = atheism
predicted class = 6920.573299999997
actual class = -1
actual class = sports
predicted class = 73235.77759999997
actual class = -1
actual class = sports
predicted class = 253382.60780000009
actual class = -1
actual class = sports
predicted class = 104348.24040000005
actual class = -1
actual class = sports
predicted class = 11798.733500000002
actual class = -1
actual class = sports
predicted class = 32558.99090000001
actual class = 1
actual class = atheism
predicted class = 34856.22219999997
actual class = 1
actual class = atheism
predicted class = 151892.8714000001
actual class = 1
actual class = atheism
predicted class = 54951.380800000064
actual class = -1
actual class = sports
predicted class = 86296.1664999999
actual class = -1
actual class = sports
predicted class = 4698.202299999999
actual class = -1
actual class = sports
tp: 200.0
fp: 200.0
tn: 0.0
fn: 0.0

precision = 0.5
recall = 1.0
f_measure = 0.6666666666666666

machine-learning java

asked Mar 14, 2015 at 5:32

smatthewenglish