Gradientenabstieg findet keine Lösung für gewöhnliche kleinste Fehlerquadrate in diesem Datensatz?

Ich habe lineare Regression studiert und es unter der Menge {(x, y)} versucht, wobei x die Fläche des Hauses in Quadratfuß und y den Preis in Dollar angab. Dies ist das erste Beispiel in Andrew Ng Notes .

2104,400
1600,330
2400,369
1416,232
3000,540

Ich habe einen Beispielcode entwickelt, aber wenn ich ihn ausführe, steigen die Kosten mit jedem Schritt, während sie mit jedem Schritt sinken sollten. Code und Ausgabe unten angegeben. biasist W ₀ X ₀ , wobei X ₀ = 1 ist. featureWeightsist ein Array von [X ₁ , X ₂ , ..., X _N ]

Ich habe auch eine Online-Python-Lösung ausprobiert, die hier verfügbar und hier erklärt ist . Dieses Beispiel liefert aber auch die gleiche Ausgabe.

Wo ist die Lücke im Verständnis des Konzepts?

Code:

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);
    }
}

Ausgabe:

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

Die kurze Antwort ist, dass Ihre Schrittgröße zu groß ist. Anstatt die Schluchtwand abwärts, Ihr Schritt ist so groß , dass Sie Springen über von einer Seite zur höher oben auf der anderen Seite !

Kostenfunktion unten:

Die lange Antwort lautet, dass es für einen naiven Gradientenabstieg schwierig ist, dieses Problem zu lösen, da die Niveausätze Ihrer Kostenfunktion eher langgestreckte Ellipsen als Kreise sind. Beachten Sie, dass es komplexere Auswahlmöglichkeiten gibt, um dieses Problem zuverlässig zu lösen:

• eine Schrittgröße (als eine Konstante fest zu codieren).
• eine Schrittrichtung (als Gradientenabstieg).

Zugrunde liegende Problem

Das zugrunde liegende Problem besteht darin, dass Niveausätze Ihrer Kostenfunktion stark verlängerte Ellipsen sind, und dies führt zu Problemen beim Gradientenabstieg. Die folgende Abbildung zeigt Level-Sets für die Kostenfunktion.

• $0$$\approx 26.789$
• Wenn die Schrittgröße zu groß ist, springen Sie buchstäblich über den unteren blauen Bereich und steigen auf, anstatt abzusteigen.
• $\theta_0$

Ich schlage vor, diese Antwort auf Quora zu lesen .

Schnellreparatur 1:

Ändern Sie Ihren Code in private float ALPHA = 0.0000002f;und Sie hören auf zu überschießen.

Schnellreparatur 2:

$X'X$

Fortgeschrittenere Korrekturen

Wenn das Ziel darin besteht, gewöhnliche kleinste Quadrate effizient zu lösen, anstatt einfach die Gradientenabnahme für eine Klasse zu lernen, beachten Sie Folgendes:

• Es gibt ausgefeiltere Methoden zur Berechnung der Schrittgröße, z. B. die Liniensuche und die Armijo-Regel .
• In der Nähe einer Antwort, bei der lokale Bedingungen vorherrschen, erhält die Newton-Methode eine quadratische Konvergenz und ist eine großartige Möglichkeit, eine Schrittrichtung und -größe zu wählen.
• Das Lösen der kleinsten Quadrate entspricht dem Lösen eines linearen Systems. Moderne Algorithmen verwenden keinen naiven Gradientenabstieg. Stattdessen:
  • $k$
  • Für große Systeme formulieren sie ein Optimierungsproblem und verwenden iterative Methoden wie die Krylov-Subraum- Methoden.

$(X'X) b = X'y$$b$

Die eigentliche Lösung ist

  26.789880528523071
   0.165118878075797

Sie werden feststellen, dass diese den Mindestwert für die Kostenfunktion erreichen.

Wie Matthew (Gunn) bereits angedeutet hat, sind die Konturen der dreidimensionalen Kosten- oder Leistungsfunktion in diesem Fall sehr elliptisch. Da Ihr Java-Code für die Gradientenabstiegsberechnungen einen einzelnen Schrittgrößenwert verwendet, werden die Aktualisierungen der Gewichte (dh der y-Achsenabschnitt und die Steigung der linearen Funktion) beide von dieser einzelnen Schrittgröße bestimmt.

Infolgedessen begrenzt die sehr kleine Schrittgröße, die erforderlich ist, um die Aktualisierung des mit dem größeren Gradienten verbundenen Gewichts (in diesem Fall der Steigung der linearen Funktion) zu steuern, drastisch, wie schnell das andere Gewicht mit dem kleineren Gradienten (dem y-Achsenabschnitt der linearen Funktion) wird aktualisiert. Unter den gegenwärtigen Bedingungen konvergiert das letztere Gewicht nicht zu seinem wahren Wert von ungefähr 26,7.

In Anbetracht der Zeit und des Aufwands, die Sie in das Schreiben Ihres Java-Codes investiert haben, würde ich vorschlagen, diesen zu ändern, um zwei diskrete Schrittgrößenwerte zu verwenden, eine geeignete Schrittgröße für jedes Gewicht. Andrew Ng schlägt in seinen Notizen vor, dass es besser ist, Feature-Skalierung zu verwenden, um sicherzustellen, dass die Konturen der Kostenfunktion eine regelmäßigere (dh kreisförmige) Form haben. Das Ändern Ihres Java-Codes, um für jedes Gewicht eine andere Schrittgröße zu verwenden, kann jedoch eine gute Übung sein, zusätzlich zur Betrachtung der Merkmalsskalierung.

Eine andere zu berücksichtigende Idee ist, wie die anfänglichen Gewichtswerte ausgewählt werden. In Ihrem Java-Code haben Sie beide Werte auf Null initialisiert. Es ist auch durchaus üblich, die Gewichte auf kleine gebrochene Werte zu initialisieren. In diesem speziellen Fall würden diese beiden Ansätze jedoch angesichts der stark elliptischen (dh nicht kreisförmigen) Konturen der dreidimensionalen Kostenfunktion nicht funktionieren. Wenn die Gewichte für dieses Problem mit anderen Methoden ermittelt werden können, beispielsweise mit der von Matthew am Ende seines Beitrags vorgeschlagenen Lösung für das lineare System, können Sie versuchen, die Gewichte auf Werte zu initialisieren, die näher an den richtigen Gewichten liegen, und überprüfen, wie der ursprüngliche Code lautet unter Verwendung einer einzigen Schrittgröße konvergiert.

Der gefundene Python-Code nähert sich der Lösung auf die gleiche Weise wie Ihr Java-Code - beide verwenden einen einzelnen Schrittgrößenparameter. Ich habe diesen Python-Code geändert, um für jedes Gewicht eine andere Schrittgröße zu verwenden. Ich habe es unten aufgenommen.

from numpy import *

def compute_error_for_line_given_points(b, m, points):
    totalError = 0
    for i in range(0, len(points)):
        x = points[i, 0]
        y = points[i, 1]
        totalError += (y - (m * x + b)) ** 2
    return totalError / float(len(points))

def step_gradient(b_current, m_current, points, learningRate_1, learningRate_2):
    b_gradient = 0
    m_gradient = 0
    N = float(len(points))
    for i in range(0, len(points)):
        x = points[i, 0]
        y = points[i, 1]
        b_gradient += -(2/N) * (y - ((m_current * x) + b_current))
        m_gradient += -(2/N) * x * (y - ((m_current * x) + b_current))
    new_b = b_current - (learningRate_1 * b_gradient)
    new_m = m_current - (learningRate_2 * m_gradient)
    return [new_b, new_m]

def gradient_descent_runner(points, starting_b, starting_m, learning_rate_1, learning_rate_2, num_iterations):
    b = starting_b
    m = starting_m
    for i in range(num_iterations):
        b, m = step_gradient(b, m, array(points), learning_rate_1, learning_rate_2)
    return [b, m]

def run():
    #points = genfromtxt("data.csv", delimiter=",")
    #learning_rate = 0.0001
    #num_iterations = 200

    points = genfromtxt("test_set.csv", delimiter=",")
    learning_rate_1 = 0.5
    learning_rate_2 = 0.0000001
    num_iterations = 1000

    initial_b = 0 # initial y-intercept guess
    initial_m = 0 # initial slope guess


    print("Starting gradient descent at b = {0}, m = {1}, error = {2}".format(initial_b, initial_m, compute_error_for_line_given_points(initial_b, initial_m, points)))
    print("Running...")

    [b, m] = gradient_descent_runner(points, initial_b, initial_m, learning_rate_1, learning_rate_2, num_iterations)

    print("After {0} iterations b = {1}, m = {2}, error = {3}".format(num_iterations, b, m, compute_error_for_line_given_points(b, m, points)))

if __name__ == '__main__':
    run()

Es läuft unter Python 3, für das die Klammern um das Argument für die "print" -Anweisungen erforderlich sind. Andernfalls wird es unter Python 2 ausgeführt, indem die Klammern entfernt werden. Sie müssen eine CSV-Datei mit den Daten aus dem Beispiel von Andrew Ng erstellen.

Mit können Sie den Python-Code querverweisen, um Ihren Java-Code zu überprüfen.