A descida de gradiente não encontra solução para os mínimos quadrados comuns neste conjunto de dados?

Estudei regressão linear e tentei no conjunto abaixo {(x, y)}, em que x especificou a área da casa em metros quadrados e y especificou o preço em dólares. Este é o primeiro exemplo no Andrew Ng Notes .

2104.400
1600.330
2400.369
1416.232
3000.540

Eu desenvolvi um código de exemplo, mas quando o executo, o custo está aumentando a cada etapa, enquanto ele deve estar diminuindo a cada etapa. Código e saída fornecidos abaixo. biasé W ₀ X ₀ , onde X ₀ = 1. featureWeightsé uma matriz de [X ₁ , X ₂ , ..., X _N ]

Eu também tentei uma solução python online disponível aqui e expliquei aqui . Mas este exemplo também está dando a mesma saída.

Onde está a lacuna na compreensão do conceito?

Código:

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

Resultado:

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

A resposta curta é que o tamanho do seu passo é muito grande. Em vez de descer a parede do desfiladeiro, seu passo é tão grande que você pula de um lado para o outro do alto !

Função de custo abaixo:

A resposta longa é que é difícil para uma descida de gradiente ingênua resolver esse problema porque os conjuntos de níveis de sua função de custo são elipses altamente alongadas, em vez de círculos. Para resolver esse problema de maneira robusta, observe que existem maneiras mais sofisticadas de escolher:

• um tamanho de etapa (do que codificar uma constante).
• uma direção de passo (que descida de gradiente).

Problema subjacente

O problema subjacente é que os conjuntos de níveis de sua função de custo são elipses altamente alongadas e isso causa problemas para a descida do gradiente. A figura abaixo mostra os conjuntos de níveis para a função de custo.

• $0$$\approx 26.789$ ao longo do chão do canyon), mas é para o outro recurso em que a derivada parcial tem uma inclinação muito maior .
• Se o tamanho da etapa for muito grande, você literalmente pulará sobre a região azul inferior e subirá em vez de descer.
• $\theta_0$

Sugiro ler esta resposta no Quora.

Solução rápida 1:

Mude seu código para private float ALPHA = 0.0000002f; e você deixará de exceder.

Solução rápida 2:

$X'X$

Correções mais avançadas

Se o objetivo era resolver eficientemente os mínimos quadrados comuns, em vez de simplesmente aprender a descida de gradiente para uma classe, observe o seguinte:

• Existem maneiras mais sofisticadas de calcular o tamanho da etapa, como a pesquisa de linhas e a regra de Armijo .
• Perto de uma resposta em que as condições locais prevalecem, o método de Newton obtém convergência quadrática e é uma ótima maneira de escolher uma direção e tamanho do passo.
• Resolver mínimos quadrados é equivalente a resolver um sistema linear. Algoritmos modernos não usam descida de gradiente ingênua. Em vez de:
  • $k$
  • Para sistemas grandes, eles formulam um problema de otimização e usam métodos iterativos, como os métodos do subespaço de Krylov .

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

A solução real é

  26.789880528523071
   0.165118878075797

Você descobrirá que eles atingem o valor mínimo para a função de custo.

Como Matthew (Gunn) já indicou, os contornos da função tridimensional de custo ou desempenho são altamente elípticos neste caso. Como o código Java usa um valor de tamanho de etapa único para os cálculos de descida do gradiente, as atualizações dos pesos (ou seja, a interceptação do eixo y e a inclinação da função linear) são ambas controladas por esse tamanho de etapa única.

Como resultado, o tamanho da etapa muito pequeno necessário para controlar a atualização do peso associado ao gradiente maior (neste caso, a inclinação da função linear) limita drasticamente a rapidez com que o outro peso com o gradiente menor (o interceptação do eixo y da função linear) é atualizada. Nas condições atuais, o último peso não converge para seu valor real de aproximadamente 26,7.

Dado o tempo e o esforço que você investiu para escrever seu código Java, sugiro modificá-lo para usar dois valores discretos de tamanho de etapa, um tamanho de etapa apropriado para cada peso. Andrew Ng sugere em suas anotações que é melhor usar a escala de recursos para garantir que os contornos da função de custo tenham uma forma mais regular (isto é, circular). No entanto, modificar seu código Java para usar um tamanho de etapa diferente para cada peso pode ser um bom exercício, além de analisar a escala de recursos.

Outra idéia a considerar é como os valores de peso inicial são selecionados. No seu código Java, você inicializou ambos os valores para zero. Também é bastante comum inicializar os pesos para valores fracionários pequenos. Nesse caso em particular, no entanto, essas duas abordagens não funcionariam à luz dos contornos altamente elípticos (isto é, não circulares) da função de custo tridimensional. Dado que os pesos para esse problema podem ser encontrados usando outros métodos, como a solução para o sistema linear sugerida por Matthew no final de sua postagem, você pode tentar inicializar os pesos com valores mais próximos dos pesos corretos e ver como o código original o uso de uma única etapa converge.

O código Python que você encontrou aborda a solução da mesma maneira que o código Java - ambos usam um único parâmetro de tamanho de etapa. Modifiquei esse código Python para usar um tamanho de etapa diferente para cada peso. Eu o incluí abaixo.

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

Ele é executado no Python 3, que requer parênteses ao redor do argumento para as instruções "print". Caso contrário, ele será executado no Python 2 removendo os parênteses. Você precisará criar um arquivo CSV com os dados do exemplo de Andrew Ng.

Use pode fazer referência cruzada ao código Python para verificar seu código Java.