多變量梯度下降的Java實現

Question

我試圖在Java中實現多變量梯度下降算法（來自AI coursera課程），並且我無法確定位於我的代碼中的故障位於何處。

這是下面程序的輸出：

Before train: parameters := [0.0, 0.0, 0.0] -> cost function := 2.5021875E9 
After first iteration: parameters := [378.5833333333333, 2.214166666666667, 50043.75000000001] -> cost function := 5.404438291015627E9 

正如你所看到的，第一次迭代後，該值是路要走。我究竟做錯了什麼？

這是我想要實現的算法：

，代碼：

import java.util.*; 

    public class GradientDescent { 

     private double[][] trainingData; 
     private double[] means; 
     private double[] scale; 

     private double[] parameters; 
     private double  learningRate; 

     GradientDescent() { 
      this.learningRate = 0D; 
     } 

     public double predict(double[] inp){ 
      double[] features = new double[inp.length + 1]; 
      features[0] = 1; 
      for(int i = 0; i < inp.length; i++) { 
       features[i+1] = inp[i]; 
      } 

      double prediction = 0; 
      for(int i = 0; i < parameters.length; i++) { 
       prediction = parameters[i] * features[i]; 
      } 

      return prediction; 
     } 

     public void train(){ 
      double[] tempParameters = new double[parameters.length]; 
      for(int i = 0; i < parameters.length; i++) { 
       tempParameters[i] = parameters[i] - learningRate * partialDerivative(i); 
       //System.out.println(tempParameters[i] + " = " + parameters[i] + " - " + learningRate + " * " + partialDerivative(i)); 
      } 

      System.out.println("Before train: parameters := " + Arrays.toString(parameters) + " -> cost function := " + costFunction()); 
      parameters = tempParameters; 
      System.out.println("After first iteration: parameters := " + Arrays.toString(parameters) + " -> cost function := " + costFunction()); 
     } 

     private double partialDerivative(int index) { 
      double sum = 0; 
      for(int i = 0; i < trainingData.length; i++) { 
       double[] input = new double[trainingData[i].length - 1]; 
       int j = 0; 
       for(; j < trainingData[i].length - 1; j++) { 
        input[j] = trainingData[i][j]; 
       } 
       sum += ((predict(input) - trainingData[i][j]) * trainingData[i][index]); 
      } 

      return (1D/trainingData.length) * sum; 
     } 

     public double[][] getTrainingData() { 
      return trainingData; 
     } 
     public void setTrainingData(double[][] data) { 
      this.trainingData = data; 
      this.means = new double[this.trainingData[0].length-1]; 
      this.scale = new double[this.trainingData[0].length-1]; 

      for(int j = 0; j < data[0].length-1; j++) { 
       double min = data[0][j], max = data[0][j]; 
       double sum = 0; 
       for(int i = 0; i < data.length; i++) { 
        if(data[i][j] < min) min = data[i][j]; 
        if(data[i][j] > max) max = data[i][j]; 
        sum += data[i][j]; 
       } 
       scale[j] = max - min; 
       means[j] = sum/data.length; 
      } 
     } 

     public double[] getParameters() { 
      return parameters; 
     } 
     public void setParameters(double[] parameters) { 
      this.parameters = parameters; 
     } 

     public double getLearningRate() { 
      return learningRate; 
     } 
     public void setLearningRate(double learningRate) { 
      this.learningRate = learningRate; 
     } 

     /**    1  m   i  i 2 
     * J(theta) = ----- * SUM(h  (x) - y ) 
     *    2*m i=1 theta 
     */ 
     public double costFunction() { 
      double sum = 0; 

      for(int i = 0; i < trainingData.length; i++) { 
       double[] input = new double[trainingData[i].length - 1]; 
       int j = 0; 
       for(; j < trainingData[i].length - 1; j++) { 
        input[j] = trainingData[i][j]; 
       } 
       sum += Math.pow(predict(input) - trainingData[i][j], 2); 
      } 

      double factor = 1D/(2*trainingData.length); 
      return factor * sum; 
     } 

     @Override 
     public String toString() { 
      StringBuilder sb = new StringBuilder("hypothesis: "); 
      int i = 0; 
      sb.append(parameters[i++] + " + "); 
      for(; i < parameters.length-1; i++) { 
       sb.append(parameters[i] + "*x" + i + " + "); 
      } 
      sb.append(parameters[i] + "*x" + i); 

      sb.append("\n Feature scale: "); 
      for(i = 0; i < scale.length-1; i++) { 
       sb.append(scale[i] + " "); 
      } 
      sb.append(scale[i]); 

      sb.append("\n Feature means: "); 
      for(i = 0; i < means.length-1; i++) { 
       sb.append(means[i] + " "); 
      } 
      sb.append(means[i]); 

      sb.append("\n Cost fuction: " + costFunction()); 

      return sb.toString(); 
     } 

     public static void main(String[] args) { 

      final double[][] TDATA = { 
       {200, 2, 20000}, 
       {300, 2, 41000}, 
       {400, 3, 51000}, 
       {500, 3, 61500}, 
       {800, 4, 41000}, 
       {900, 5, 141000} 
      }; 

      GradientDescent gd = new GradientDescent(); 
      gd.setTrainingData(TDATA); 
      gd.setParameters(new double[]{0D,0D,0D}); 
      gd.setLearningRate(0.00001); 
      gd.train(); 
      //System.out.println(gd); 
      //System.out.println("PREDICTION: " + gd.predict(new double[]{300, 2})); 
     } 
    } 

---

編輯：

我已經更新了使其更具可讀性的代碼，並試圖將其映射到道格拉斯使用的符號。我認爲現在效果更好，但仍然存在我不完全瞭解的陰暗區域。

看來，如果我有多個參數（如下面的例子中，房間數量和麪積），預測與第二個參數（在這個區域中）強烈相關，並且它沒有太多影響更改第一個參數（房間數量）。

這裏是預測{2, 200}：

PREDICTION: 200000.00686158828 

這裏是{5, 200}預測：

PREDICTION: 200003.0068315415 

正如你可以看到有勉強的兩個值之間的差額。

當我試圖將數學轉化爲代碼時，仍然存在錯誤嗎？

下面是更新後的代碼：

import java.util.*; 

public class GradientDescent { 

    private double[][] trainingData; 
    private double[] means; 
    private double[] scale; 

    private double[] parameters; 
    private double  learningRate; 

    GradientDescent() { 
     this.learningRate = 0D; 
    } 

    public double predict(double[] inp) { 
     return predict(inp, this.parameters); 
    } 
    private double predict(double[] inp, double[] parameters){ 
     double[] features = concatenate(new double[]{1}, inp); 

     double prediction = 0; 
     for(int j = 0; j < features.length; j++) { 
      prediction += parameters[j] * features[j]; 
     } 

     return prediction; 
    } 

    public void train(){ 
     readjustLearningRate(); 

     double costFunctionDelta = Math.abs(costFunction() - costFunction(iterateGradient())); 

     while(costFunctionDelta > 0.0000000001) { 
      System.out.println("Old cost function : " + costFunction()); 
      System.out.println("New cost function : " + costFunction(iterateGradient())); 
      System.out.println("Delta: " + costFunctionDelta); 

      parameters = iterateGradient(); 
      costFunctionDelta = Math.abs(costFunction() - costFunction(iterateGradient())); 
      readjustLearningRate(); 
     } 
    } 

    private double[] iterateGradient() { 
     double[] nextParameters = new double[parameters.length]; 
     // Calculate parameters for the next iteration 
     for(int r = 0; r < parameters.length; r++) { 
      nextParameters[r] = parameters[r] - learningRate * partialDerivative(r); 
     } 

     return nextParameters; 
    } 
    private double partialDerivative(int index) { 
     double sum = 0; 
     for(int i = 0; i < trainingData.length; i++) { 
      int indexOfResult = trainingData[i].length - 1; 
      double[] input = Arrays.copyOfRange(trainingData[i], 0, indexOfResult); 
      sum += ((predict(input) - trainingData[i][indexOfResult]) * trainingData[i][index]); 
     } 

     return sum/trainingData.length ; 
    } 
    private void readjustLearningRate() { 

     while(costFunction(iterateGradient()) > costFunction()) {   
      // If the cost function of the new parameters is higher that the current cost function 
      // it means the gradient is diverging and we have to adjust the learning rate 
      // and recalculate new parameters 
      System.out.print("Learning rate: " + learningRate + " is too big, readjusted to: "); 
      learningRate = learningRate/2; 
      System.out.println(learningRate); 
     } 
     // otherwise we are taking small enough steps, we have the right learning rate 
    } 

    public double[][] getTrainingData() { 
     return trainingData; 
    } 
    public void setTrainingData(double[][] data) { 
     this.trainingData = data; 
     this.means = new double[this.trainingData[0].length-1]; 
     this.scale = new double[this.trainingData[0].length-1]; 

     for(int j = 0; j < data[0].length-1; j++) { 
      double min = data[0][j], max = data[0][j]; 
      double sum = 0; 
      for(int i = 0; i < data.length; i++) { 
       if(data[i][j] < min) min = data[i][j]; 
       if(data[i][j] > max) max = data[i][j]; 
       sum += data[i][j]; 
      } 
      scale[j] = max - min; 
      means[j] = sum/data.length; 
     } 
    } 

    public double[] getParameters() { 
     return parameters; 
    } 
    public void setParameters(double[] parameters) { 
     this.parameters = parameters; 
    } 

    public double getLearningRate() { 
     return learningRate; 
    } 
    public void setLearningRate(double learningRate) { 
     this.learningRate = learningRate; 
    } 

    /**    1  m   i  i 2 
    * J(theta) = ----- * SUM(h  (x) - y ) 
    *    2*m i=1 theta 
    */ 
    public double costFunction() { 
     return costFunction(this.parameters); 
    } 
    private double costFunction(double[] parameters) { 
     int m = trainingData.length; 
     double sum = 0; 

     for(int i = 0; i < m; i++) { 
      int indexOfResult = trainingData[i].length - 1; 
      double[] input = Arrays.copyOfRange(trainingData[i], 0, indexOfResult); 
      sum += Math.pow(predict(input, parameters) - trainingData[i][indexOfResult], 2); 
     } 

     double factor = 1D/(2*m); 
     return factor * sum; 
    } 

    private double[] normalize(double[] input) { 
     double[] normalized = new double[input.length]; 
     for(int i = 0; i < input.length; i++) { 
      normalized[i] = (input[i] - means[i])/scale[i]; 
     } 

     return normalized; 
    } 

    private double[] concatenate(double[] a, double[] b) { 
     int size = a.length + b.length; 

     double[] concatArray = new double[size]; 
     int index = 0; 

     for(double d : a) { 
      concatArray[index++] = d; 
     } 
     for(double d : b) { 
      concatArray[index++] = d; 
     } 

     return concatArray; 
    } 

    @Override 
    public String toString() { 
     StringBuilder sb = new StringBuilder("hypothesis: "); 
     int i = 0; 
     sb.append(parameters[i++] + " + "); 
     for(; i < parameters.length-1; i++) { 
      sb.append(parameters[i] + "*x" + i + " + "); 
     } 
     sb.append(parameters[i] + "*x" + i); 

     sb.append("\n Feature scale: "); 
     for(i = 0; i < scale.length-1; i++) { 
      sb.append(scale[i] + " "); 
     } 
     sb.append(scale[i]); 

     sb.append("\n Feature means: "); 
     for(i = 0; i < means.length-1; i++) { 
      sb.append(means[i] + " "); 
     } 
     sb.append(means[i]); 

     sb.append("\n Cost fuction: " + costFunction()); 

     return sb.toString(); 
    } 

    public static void main(String[] args) { 

     final double[][] TDATA = { 
      //number of rooms, area, price 
      {2, 200, 200000}, 
      {3, 300, 300000}, 
      {4, 400, 400000}, 
      {5, 500, 500000}, 
      {8, 800, 800000}, 
      {9, 900, 900000} 
     }; 

     GradientDescent gd = new GradientDescent(); 
     gd.setTrainingData(TDATA); 
     gd.setParameters(new double[]{0D, 0D, 0D}); 
     gd.setLearningRate(0.1); 
     gd.train(); 
     System.out.println(gd); 
     System.out.println("PREDICTION: " + gd.predict(new double[]{3, 600})); 
    } 
} 

Answer 1

看來你有一個良好的開端，但也有在數學代碼翻譯的一些問題。看下面的數學。

有我走上澄清數學和算法的收斂機制幾步之遙。

1. 爲了提高易讀性，而不是使用一個括弧上標表示行，在表示法中使用更標準的逗號分隔的下標。
2. 試圖對求和控制變量使用零基數來匹配Java/C索引約定，而不會在數學中引入錯誤。 （希望做得正確。）
3. 做了課程材料暗示的各種替代。
4. 確定發佈代碼中的變量名稱與數學表示之間的映射關係。

之後，在summation循環中出現了比缺失加號多的錯誤。部分派生似乎需要重寫或重大修改來匹配課程概念。

請注意，k = 0-> n的內環產生所有特徵的點積，然後應用在i = 0-> m-1循環內以​​解釋每個訓練情況。

所有這些都必須包含在每個迭代r中。該外部循環的循環標準不應該是某個最大的r值。一旦收斂足夠完成，您將需要滿足一些標準。

---

響應評論其他注意事項：

這是困難的，因爲代碼代表的原因是什麼Martin Fowler的稱爲Symantic峽發現的不協調。在這種情況下，它介於三件事情之間。

1. 數學表示
2. 講座術語
3. 算法代碼

它是可能的重構成員變量和斷裂從x矩陣（如下所示）的y向量將促進斑點不協調。

private int countMExamples; 
private int countNFeatures; 
private double[][] aX; 
private double[] aY; 
private double[] aMeans; 
private double[] aScales; 
private double[] aParamsTheta; 
private double learnRate; 

Answer 2

你計算你的預測時缺少+。應該重量*輸入值與

prediction += parameters[i] * features[i];

作爲產生您使用的偏導數的激活函數被求和是h _θ = Σ _我^X我θ^我 。

此外，它看起來像你將需要降低你的學習率，以獲得訓練函數的收斂。

-

我不知道課程的內容，所以我不知道，如果你期望的具體結果，但我認爲現在的問題就在於你的訓練數據。

訓練數據沒有提供不分如何顯著任一輸入影響的結果，因爲兩個輸入彼此產生一個按比例增加的結果成比例地增加。我會建議提供一個數據集，以便在兩個輸入之間有更大的變化和更少的依賴性。

如果你與獲取數據使用，你可以嘗試（與下面提供的數據其實你有更好的運氣）的UCI housing data set.掙扎。

-

我已經運行新的代碼，並解決以下問題解決的效果很好。您的更新引入了兩個主要缺陷，即動態學習率和培訓終止情況。

動態學習速率是一種有效的方法，但是創建一個函數，適當地減小學習率是困難的。您目前的方法會過快地降低學習速度，導致它減少到一個值，這會使您的權重發生如此微不足道的變化，從而使算法過早停止。目前，保持恆定的學習速度並手動調整它。

你的訓練結束的情況下，需要在成本函數你的條件這麼小的變化將導致算法在火車上你的訓練數據。結果將會是該算法在訓練數據上表現良好，但對新事物表現不佳，因爲它基於訓練數據獨有的細節進行預測。

我會建議大大減少要求，或者更好的是，實施一個火車驗證循環。每次迭代都會在不同的驗證集上測試您的參數，並根據該性能終止。

此外，我對輸入數據的上述建議對於簡單梯度下降算法來說很差。房屋數據集不是線性可分的，所以梯度下降算法（優化線性函數h _θ）只會使預測值接近平均值。

相反，你應該使用的數據是線性可分的，如UCI Iris data set。通過解決上述兩個問題，您的算法可以準確地處理這些數據。

最後，我同意道格拉斯的觀點，你應該考慮重寫你的算法，使其更加清晰。儘管當前的實現有效，但如果代碼簡潔且有組織，它將有助於您的學習過程。您正在使用不具描述性的變量名稱，混合程序和OOP方法，以及隨意封裝方法。