Keturunan gradien tidak menemukan solusi untuk kuadrat terkecil biasa pada dataset ini?

Saya telah mempelajari regresi linear dan mencobanya pada set di bawah ini {(x, y)}, di mana x menentukan luas rumah dalam kaki persegi, dan y menentukan harga dalam dolar. Ini adalah contoh pertama dalam Catatan Andrew Ng .

2104.400
1600.330
2400.369
1416.232
3000,540

Saya mengembangkan kode sampel tetapi ketika saya menjalankannya, biaya meningkat dengan setiap langkah sedangkan itu harus berkurang dengan setiap langkah. Kode dan hasil yang diberikan di bawah ini. biasadalah W ₀ X ₀ , di mana X ₀ = 1. featureWeightsadalah larik [X ₁ , X ₂ , ..., X _N ]

Saya juga mencoba solusi python online yang tersedia di sini , dan dijelaskan di sini . Tetapi contoh ini juga memberikan hasil yang sama.

Di mana celah dalam memahami konsep itu?

Kode:

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

Keluaran:

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

Jawaban singkatnya adalah ukuran langkah Anda terlalu besar. Alih-alih menuruni dinding ngarai, langkah Anda sangat besar sehingga Anda melompat dari satu sisi ke sisi yang lebih tinggi di sisi yang lain!

Fungsi biaya di bawah ini:

Jawaban panjangnya adalah sulit bagi penurunan gradien naif untuk menyelesaikan masalah ini karena set level fungsi biaya Anda adalah elips yang sangat memanjang daripada lingkaran. Untuk mengatasi masalah ini dengan kuat, perhatikan bahwa ada cara yang lebih canggih untuk memilih:

• ukuran langkah (dari hardcoding konstanta).
• arah langkah (dari gradient descent).

Masalah yang mendasarinya

Masalah yang mendasarinya adalah bahwa set level fungsi biaya Anda adalah elips yang sangat panjang, dan ini menyebabkan masalah penurunan gradien. Gambar di bawah ini menunjukkan set level untuk fungsi biaya.

• $0$$\approx 26.789$
• Jika ukuran anak tangga terlalu besar, Anda benar-benar akan melompati wilayah biru yang lebih rendah dan naik bukannya turun.
• $\theta_0$

Saya sarankan membaca jawaban ini di Quora.

Perbaikan cepat 1:

Ubah kode private float ALPHA = 0.0000002f;Anda dan Anda akan berhenti melakukan overshooting.

Perbaikan cepat 2:

$X'X$

Perbaikan lebih lanjut

Jika tujuannya adalah untuk menyelesaikan kuadrat terkecil yang efisien daripada sekadar mempelajari gradient descent untuk suatu kelas, amati bahwa:

• Ada cara yang lebih canggih untuk menghitung ukuran langkah, seperti pencarian garis dan aturan Armijo .
• Dekat jawaban di mana kondisi lokal berlaku, metode Newton memperoleh konvergensi kuadrat dan merupakan cara terbaik untuk memilih arah langkah dan ukuran.
• Memecahkan kuadrat terkecil setara dengan memecahkan sistem linear. Algoritma modern tidak menggunakan descent gradient naif. Sebagai gantinya:
  • $k$
  • Untuk sistem besar, mereka merumuskannya adalah masalah optimasi dan menggunakan metode berulang seperti metode ruang bagian Krylov .

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

Solusi sebenarnya adalah

  26.789880528523071
   0.165118878075797

Anda akan menemukan bahwa mereka mencapai nilai minimum untuk fungsi biaya.

Seperti yang telah ditunjukkan oleh Matthew (Gunn), kontur biaya 3-dimensi atau fungsi kinerja sangat elips dalam kasus ini. Karena kode Java Anda menggunakan nilai ukuran langkah tunggal untuk perhitungan gradient descent, pembaruan bobot (yaitu intersep sumbu y dan kemiringan fungsi linier) keduanya diatur oleh ukuran langkah tunggal ini.

Akibatnya, ukuran langkah yang sangat kecil yang diperlukan untuk mengontrol pembaruan berat terkait dengan gradien yang lebih besar (dalam hal ini, kemiringan fungsi linier) secara drastis membatasi seberapa cepat bobot lainnya dengan gradien yang lebih kecil ( sumbu y dari fungsi linier) diperbarui. Dalam kondisi saat ini, bobot terakhir tidak menyatu dengan nilai sebenarnya sekitar 26,7.

Mengingat waktu dan usaha yang telah Anda investasikan dalam menulis kode Java Anda, saya sarankan memodifikasinya untuk menggunakan dua nilai ukuran langkah diskrit, ukuran langkah yang sesuai untuk setiap bobot. Andrew Ng menyarankan dalam catatannya bahwa lebih baik menggunakan penskalaan fitur untuk memastikan bahwa kontur fungsi biaya lebih teratur (yaitu lingkaran) dalam bentuk. Namun, memodifikasi kode Java Anda untuk menggunakan ukuran langkah yang berbeda untuk setiap bobot mungkin merupakan latihan yang baik selain melihat penskalaan fitur.

Gagasan lain yang perlu dipertimbangkan adalah bagaimana nilai bobot awal dipetik. Dalam kode Java Anda, Anda menginisialisasi kedua nilai menjadi nol. Hal ini juga cukup umum untuk menginisialisasi bobot ke nilai fraksional kecil. Dalam kasus khusus ini, bagaimanapun, kedua pendekatan ini tidak akan bekerja dalam terang kontur yang sangat elips (yaitu non-lingkaran) dari fungsi biaya tiga dimensi. Mengingat bobot untuk masalah ini dapat ditemukan menggunakan metode lain, seperti solusi untuk sistem linier yang disarankan oleh Matthew di akhir jabatannya, Anda dapat mencoba menginisialisasi bobot ke nilai yang lebih dekat ke bobot yang benar dan melihat bagaimana kode asli Anda menggunakan konvergensi step-size tunggal.

Kode Python yang Anda temukan mendekati solusi dengan cara yang sama seperti kode Java Anda - keduanya menggunakan parameter ukuran langkah tunggal. Saya memodifikasi kode Python ini untuk menggunakan ukuran langkah yang berbeda untuk setiap berat. Saya sudah memasukkannya di bawah ini.

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

Ini berjalan di bawah Python 3, yang membutuhkan tanda kurung di sekitar argumen untuk pernyataan "cetak". Kalau tidak, itu akan berjalan di bawah Python 2 dengan menghapus tanda kurung. Anda harus membuat file CSV dengan data dari contoh Andrew Ng.

Gunakan referensi silang kode Python untuk memeriksa kode Java Anda.