1
$\begingroup$

I've watched 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
Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Let me try to help.

Batch gradient descent, basically go over all samples until convergence. Stochastic gradient descent, is doing the same thing with 2 exceptions: the first one is is evaluating each sample individually (what changes the cost function) and the second shuffles the array of samples. The reason the data is randomly shuffled at beginning is because the algorithm is looking for convergence by trying random data points instead of looking into all the data points; however and because this still under the umbrella of probability, convergence might take the same time as batch gradient descent (if the shuffling sorts the data leaving the array in the original order, unlikely but possible).

Remember, stochastic descent looks to jump thought the data in order to find the global minimum in a random way. This works when the data set is big enough as stated by Ng. If you try this with a data-set with 10 items, then this might perform in a similar way to the batch gradient descent.

Also, remember about the simultaneous update that needs to happen in order to estimate theta0 and theta1.

As a recommendation to debug your algorithm, first perform the implementation of batch gradient descent and then modify it to the stochastic model. compare the codes and debug each step on the batch gradient. Compare those results to the random jumps performed by the stochastic one.

i hope this gives you some light.

Improve this answer
$\endgroup$
1
  • $\begingroup$ i appreciate your consideration, but i don't understand your explaination. these are the steps of batch, if i'm not mistaken: 1. Calculate the hypothesis h = X * theta, 2. Calculate the loss = h - y and maybe the squared cost (loss^2)/2m, 3. Calculate the gradient = X' * loss / m, 4,update weights and bias is that right? what would be the steps, pseudocode for stochastic gradient descent, and how would that differ from match gradient descent? $\endgroup$
    – smatthewenglish
    Commented Mar 14, 2015 at 7:22
1
$\begingroup$

Stochastic gradient descent involved "incremental training", where the network's weights and biases are updated *after each *input is presented.

Batch training means that the complete gradient is computed after all inputs are applied to the network, before the weights and biases are updated.

In other words, with batch training, the network's weights and biases are kept constant while the error is calculated. Stochastic gradient descent method updates the error along with new weights and biases for each input.

Although that may not help solve your problem at hand, I hope that gives a general idea of the difference.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.