Regression
梯度下降在這個數據集上找不到普通最小二乘的解決方案？
我一直在研究線性回歸，並在下面的集合 {(x,y)} 上進行了嘗試，其中 x 以平方英尺為單位指定房屋面積，y 以美元為單位指定價格。這是Andrew Ng Notes中的第一個示例。
2104,400 1600,330 2400,369 1416,232 3000,540我開發了一個示例代碼，但是當我運行它時，成本隨著每一步而增加，而它應該隨著每一步而減少。下面給出的代碼和輸出。
bias是W 0 X 0，其中X 0 =1。featureWeights是 [X 1 ,X 2 ,…,X N ]的數組我還嘗試了此處提供的在線 python 解決方案，並在此處進行了解釋。但是這個例子也給出了相同的輸出。
理解這個概念的差距在哪裡？
代碼：
package com.practice.cnn; import java.util.Arrays; public class LinearRegressionExample { private float ALPHA = 0.0001f; private int featureCount = 0; private int rowCount = 0; private float bias = 1.0f; private float[] featureWeights = null; private float optimumCost = Float.MAX_VALUE; private boolean status = true; private float trainingInput[][] = null; private float trainingOutput[] = null; public void train(float[][] input, float[] output) { if (input == null || output == null) { return; } if (input.length != output.length) { return; } if (input.length == 0) { return; } rowCount = input.length; featureCount = input[0].length; for (int i = 1; i < rowCount; i++) { if (input[i] == null) { return; } if (featureCount != input[i].length) { return; } } featureWeights = new float[featureCount]; Arrays.fill(featureWeights, 1.0f); bias = 0; //temp-update-1 featureWeights[0] = 0; //temp-update-1 this.trainingInput = input; this.trainingOutput = output; int count = 0; while (true) { float cost = getCost(); System.out.print("Iteration[" + (count++) + "] ==> "); System.out.print("bias -> " + bias); for (int i = 0; i < featureCount; i++) { System.out.print(", featureWeights[" + i + "] -> " + featureWeights[i]); } System.out.print(", cost -> " + cost); System.out.println(); // if (cost > optimumCost) { // status = false; // break; // } else { // optimumCost = cost; // } optimumCost = cost; float newBias = bias + (ALPHA * getGradientDescent(-1)); float[] newFeaturesWeights = new float[featureCount]; for (int i = 0; i < featureCount; i++) { newFeaturesWeights[i] = featureWeights[i] + (ALPHA * getGradientDescent(i)); } bias = newBias; for (int i = 0; i < featureCount; i++) { featureWeights[i] = newFeaturesWeights[i]; } } } private float getCost() { float sum = 0; for (int i = 0; i < rowCount; i++) { float temp = bias; for (int j = 0; j < featureCount; j++) { temp += featureWeights[j] * trainingInput[i][j]; } float x = (temp - trainingOutput[i]) * (temp - trainingOutput[i]); sum += x; } return (sum / rowCount); } private float getGradientDescent(final int index) { float sum = 0; for (int i = 0; i < rowCount; i++) { float temp = bias; for (int j = 0; j < featureCount; j++) { temp += featureWeights[j] * trainingInput[i][j]; } float x = trainingOutput[i] - (temp); sum += (index == -1) ? x : (x * trainingInput[i][index]); } return ((sum * 2) / rowCount); } public static void main(String[] args) { float[][] input = new float[][] { { 2104 }, { 1600 }, { 2400 }, { 1416 }, { 3000 } }; float[] output = new float[] { 400, 330, 369, 232, 540 }; LinearRegressionExample example = new LinearRegressionExample(); example.train(input, output); } }輸出：
Iteration[0] ==> bias -> 0.0, featureWeights[0] -> 0.0, cost -> 150097.0 Iteration[1] ==> bias -> 0.07484, featureWeights[0] -> 168.14847, cost -> 1.34029099E11 Iteration[2] ==> bias -> -70.60721, featureWeights[0] -> -159417.34, cost -> 1.20725801E17 Iteration[3] ==> bias -> 67012.305, featureWeights[0] -> 1.51299168E8, cost -> 1.0874295E23 Iteration[4] ==> bias -> -6.3599688E7, featureWeights[0] -> -1.43594258E11, cost -> 9.794949E28 Iteration[5] ==> bias -> 6.036088E10, featureWeights[0] -> 1.36281745E14, cost -> 8.822738E34 Iteration[6] ==> bias -> -5.7287012E13, featureWeights[0] -> -1.29341617E17, cost -> Infinity Iteration[7] ==> bias -> 5.4369677E16, featureWeights[0] -> 1.2275491E20, cost -> Infinity Iteration[8] ==> bias -> -5.1600908E19, featureWeights[0] -> -1.1650362E23, cost -> Infinity Iteration[9] ==> bias -> 4.897313E22, featureWeights[0] -> 1.1057068E26, cost -> Infinity Iteration[10] ==> bias -> -4.6479177E25, featureWeights[0] -> -1.0493987E29, cost -> Infinity Iteration[11] ==> bias -> 4.411223E28, featureWeights[0] -> 9.959581E31, cost -> Infinity Iteration[12] ==> bias -> -4.186581E31, featureWeights[0] -> -Infinity, cost -> Infinity Iteration[13] ==> bias -> Infinity, featureWeights[0] -> NaN, cost -> NaN Iteration[14] ==> bias -> NaN, featureWeights[0] -> NaN, cost -> NaN
簡短的回答是您的步長太大。您的步幅如此之大，以至於您從一側跳到另一側更高的地方，而不是從峽谷壁上下來！
下面的成本函數：
長答案是天真的梯度下降很難解決這個問題，因為成本函數的水平集是高度拉長的橢圓而不是圓形。要穩健地解決這個問題，請注意有更複雜的方法可供選擇：
- 步長（而不是硬編碼一個常數）。
- 一個步進方向（比梯度下降）。
根本問題
潛在的問題是成本函數的水平集是高度拉長的橢圓，這會導致梯度下降問題。下圖顯示了成本函數的水平集。
- 對於高度橢圓的水平集，最陡下降的方向可能幾乎不與解的方向對齊。例如在這個問題中，截距項（你稱之為“偏差”）需要傳播很遠的距離（從 $ 0 $ 到 $ \approx 26.789 $ 沿著峽谷底部），但它是用於偏導數具有更大斜率的另一個特徵。
- 如果步長太大，您實際上會跳過較低的藍色區域並上升而不是下降。
- 但是，如果您減小步長，那麼您在獲得 $ \theta_0 $ 到適當的值變得非常緩慢。
我建議在 Quora 上閱讀這個答案。
快速修復1：
將您的代碼更改為
private float ALPHA = 0.0000002f;，您將停止超調。快速修復2：
如果您將 X 數據重新縮放為 2.104、1.600 等……您的水平集將變為球形，並且梯度下降會以更高的學習率快速收斂。這會降低設計矩陣的條件數 $ X’X $ .
更高級的修復
如果目標是有效地解決普通最小二乘，而不是簡單地學習一個類的梯度下降，請注意：
在當地條件佔優勢的答案附近，牛頓法獲得二次收斂，是選擇步長方向和大小的好方法。
求解最小二乘相當於求解線性系統。現代算法不使用天真的梯度下降。反而：
- 對於小型系統（ $ k $ 大約幾千個或更少），他們使用像 QR 分解和部分旋轉的東西。
- 對於大型系統，他們確實將其表述為優化問題並使用迭代方法，例如Krylov 子空間方法。
請注意，有許多軟件包可以解決線性系統 $ (X’X) b = X’y $ 為了 $ b $ 你可以檢查你的梯度下降算法的結果。
實際的解決方案是
26.789880528523071 0.165118878075797你會發現那些達到了成本函數的最小值。
