Spadek gradientu nie znajduje rozwiązania dla zwykłych najmniejszych kwadratów w tym zestawie danych?

Studiowałem regresję liniową i wypróbowałem ją poniżej zestawu {(x, y)}, gdzie x określał powierzchnię domu w metrach kwadratowych, ay określał cenę w dolarach. To jest pierwszy przykład w notatkach Andrew Ng .

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

Opracowałem przykładowy kod, ale kiedy go uruchamiam, koszt rośnie z każdym krokiem, podczas gdy powinien maleć z każdym krokiem. Kod i dane wyjściowe podane poniżej. biasto W ₀ X ₀ , gdzie X ₀ = 1. featureWeightsjest tablicą [X ₁ , X ₂ , ..., X _N ]

Wypróbowałem również dostępne online rozwiązanie python tutaj i wyjaśniłem tutaj . Ale ten przykład daje również ten sam wynik.

Gdzie jest luka w zrozumieniu koncepcji?

Kod:

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

Wynik:

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

Krótka odpowiedź brzmi: twój rozmiar kroku jest za duży. Zamiast schodzić po ścianie kanionu, twój krok jest tak duży, że przeskakujesz z jednej strony na wyżej z drugiej!

Funkcja kosztów poniżej:

Długa odpowiedź jest taka, że ​​naiwnemu zejściu gradientowemu trudno jest rozwiązać ten problem, ponieważ zestawy poziomów funkcji kosztu są bardziej wydłużonymi elipsami niż okręgami. Aby skutecznie rozwiązać ten problem, pamiętaj, że istnieją bardziej wyrafinowane sposoby wyboru:

• rozmiar kroku (niż stałe kodowanie).
• kierunek kroku (niż opadanie gradientu).

Zasadniczy problem

Podstawowym problemem jest to, że zestawy poziomów funkcji kosztu są bardzo wydłużonymi elipsami, co powoduje problemy z opadaniem gradientu. Poniższy rysunek pokazuje zestawy poziomów dla funkcji kosztu.

• W przypadku wysoce eliptycznych zestawów poziomów kierunek najbardziej stromego zejścia może ledwo zrównać się z kierunkiem rozwiązania. Na przykład w tym problemie pojęcie przechwytywania (tak „odchylenie”) musi przebyć dużą odległość (od do wzdłuż dna kanionu), ale dotyczy innej cechy, w której pochodna częściowa ma znacznie większą wartość nachylenie.$0$$\approx 26.789$
• Jeśli rozmiar kroku jest zbyt duży, dosłownie przeskoczysz dolny niebieski region i wzniesiesz się zamiast zejść.
• ALE jeśli zmniejszysz swój stopień, postęp w doprowadzeniu do właściwej wartości staje się boleśnie powolny.$\theta_0$

Proponuję przeczytać tę odpowiedź na Quora.

Szybka poprawka 1:

Zmień kod na, private float ALPHA = 0.0000002f;a przestaniesz przekraczać.

Szybka poprawka 2:

Jeśli przeskalujesz swoje dane X do 2.104, 1.600 itp., Twoje zestawy poziomów staną się sferyczne, a spadek gradientu szybko zbiegnie się z wyższą szybkością uczenia się. Obniża to liczbę warunków macierzy projektowej .$X'X$

Bardziej zaawansowane poprawki

Jeśli celem było efektywne rozwiązanie zwykłych najmniejszych kwadratów zamiast po prostu nauczenie się spadku gradientowego dla klasy, zauważ, że:

• Istnieją bardziej zaawansowane sposoby obliczania wielkości kroku, takie jak wyszukiwanie linii i reguła Armijo .
• W pobliżu odpowiedzi, w której przeważają warunki lokalne, metoda Newtona uzyskuje kwadratową zbieżność i jest świetnym sposobem na wybór kierunku i wielkości kroku.
• Rozwiązanie najmniejszych kwadratów jest równoznaczne z rozwiązaniem układu liniowego. Współczesne algorytmy nie używają naiwnego spadku gradientu. Zamiast:
  • W przypadku małych systemów ( rzędu kilku tysięcy lub mniej) używają czegoś takiego jak rozkład QR z częściowym obrotem.$k$
  • W przypadku dużych systemów formułują, że jest to problem optymalizacji i używają metod iteracyjnych, takich jak metody podprzestrzeni Kryłowa .

Zauważ, że istnieje wiele pakietów, które rozwiążą układ liniowy$(X'X) b = X'y$ dla i możesz porównać z tym wyniki algorytmu spadku gradientu.$b$

Rzeczywistym rozwiązaniem jest

  26.789880528523071
   0.165118878075797

Przekonasz się, że osiągają one minimalną wartość dla funkcji kosztu.

Jak już wskazał Matthew (Gunn), kontury trójwymiarowej funkcji kosztu lub wydajności są w tym przypadku wysoce eliptyczne. Ponieważ kod Java wykorzystuje pojedynczą wartość krok wielkości gradientu obliczeń pochodzenia, aktualizacje do wagi (czyli punkt przecięcia osi y, a nachylenie funkcji liniowej) są zarówno reguluje tego jednego kroku wielkości.

W rezultacie bardzo mały rozmiar kroku wymagany do kontrolowania aktualizacji ciężaru związanego z większym gradientem (w tym przypadku nachylenie funkcji liniowej) drastycznie ogranicza szybkość, z jaką inny ciężar z mniejszym gradientem ( punkt przecięcia funkcji liniowej w osi y) jest aktualizowany. W obecnych warunkach ta ostatnia waga nie jest zbieżna z jej prawdziwą wartością około 26,7.

Biorąc pod uwagę czas i wysiłek, jaki zainwestowałeś w pisanie kodu Java, sugerowałbym zmodyfikowanie go tak, aby używał dwóch dyskretnych wartości wielkości kroku, odpowiedniej wielkości kroku dla każdej wagi. Andrew Ng sugeruje w swoich notatkach, że lepiej jest stosować skalowanie funkcji, aby zapewnić, że kontury funkcji kosztu są bardziej regularne (tj. Okrągłe) w formie. Jednak modyfikowanie kodu Java w celu użycia innego rozmiaru kroku dla każdej wagi może być dobrym ćwiczeniem oprócz patrzenia na skalowanie funkcji.

Innym pomysłem do rozważenia jest sposób wybierania początkowych wartości masy. W kodzie Java zainicjowałeś obie wartości na zero. Dość często zdarza się również, że wartości początkowe są inicjowane małymi wartościami ułamkowymi. Jednak w tym konkretnym przypadku oba te podejścia nie działałyby w świetle wysoce eliptycznych (tj. Nieokrągłych) konturów trójwymiarowej funkcji kosztu. Biorąc pod uwagę wagi tego problemu można znaleźć przy użyciu innych metod, takich jak rozwiązanie dla systemu liniowego sugerowane przez Matthew na końcu jego postu, możesz spróbować zainicjować wagi do wartości bliższych prawidłowym wagom i zobaczyć, jak oryginalny kod za pomocą zbieżności pojedynczego kroku.

Znaleziony kod Pythona podchodzi do rozwiązania w taki sam sposób jak kod Java - oba używają jednego parametru wielkości kroku. Zmodyfikowałem ten kod Python, aby dla każdego ciężaru używał innego rozmiaru kroku. Zawarłem to poniżej.

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()

Działa pod Pythonem 3, który wymaga nawiasów wokół argumentu instrukcji „print”. W przeciwnym razie będzie działał pod Pythonem 2, usuwając nawiasy. Musisz utworzyć plik CSV z danymi z przykładu Andrew Ng.

Użyj może odwoływać się do kodu Python, aby sprawdzić kod Java.