梯度下降在这个数据集上找不到普通最小二乘的解决方案?

机器算法验证 回归 最小二乘 梯度下降 监督学习
2022-03-22 21:49:00

我一直在研究线性回归,并在下面的集合 {(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
2个回答

简短的回答是您的步长太大。您的步幅如此之大,以至于您从一侧跳到另一侧更高的地方,而不是从峡谷壁上下来!

下面的成本函数:

在此处输入图像描述

长答案是,天真的梯度下降很难解决这个问题,因为成本函数的水平集是高度拉长的椭圆而不是圆形。要稳健地解决这个问题,请注意有更复杂的方法可供选择:

  • 步长(而不是硬编码一个常数)。
  • 一个步进方向(比梯度下降)。

根本问题

潜在的问题是成本函数的水平集是高度拉长的椭圆,这会导致梯度下降问题。下图显示了成本函数的水平集。

  • 对于高度椭圆的水平集,最陡下降的方向可能几乎不与解的方向对齐。例如,在这个问题中,截距项(你称之为“偏差”)需要传播很长的距离(从的距离),但它是用于偏导数更大的另一个特征坡。026.789
  • 如果步长太大,您实际上会跳过较低的蓝色区域并上升而不是下降。
  • 但是,如果您减小步长,则使达到正确值的进度会变得非常缓慢。θ0

我建议在 Quora 上阅读这个答案。

在此处输入图像描述

快速修复1:

将您的代码更改为private float ALPHA = 0.0000002f;,您将停止超调。

快速修复2:

如果您将 X 数据重新缩放为 2.104、1.600 等……您的水平集将变为球形,并且梯度下降会以更高的学习率快速收敛。这会降低设计矩阵的条件数。XX

更高级的修复

如果目标是有效地解决普通最小二乘,而不是简单地学习一个类的梯度下降,请注意:

  • 有更复杂的方法来计算步长,例如线搜索Armijo 规则
  • 在当地条件占优势的答案附近,牛顿法获得二次收敛,是选择步长方向和大小的好方法。
  • 求解最小二乘相当于求解线性系统。现代算法不使用天真的梯度下降。反而:
    • 对于小型系统(在几千或更少的数量级),它们使用诸如带有部分旋转的 QR 分解之类的东西。k
    • 对于大型系统,他们确实将其表述为优化问题并使用迭代方法,例如Krylov 子空间方法。

请注意,有许多软件包可以解决线性系统(XX)b=Xy for的问题,您可以对照它检查梯度下降算法的结果。b

实际的解决方案是

  26.789880528523071
   0.165118878075797

你会发现那些达到了成本函数的最小值。

正如 Matthew (Gunn) 已经指出的,在这种情况下,3 维成本或性能函数的轮廓是高度椭圆的。由于您的 Java 代码使用单个步长值进行梯度下降计算,因此权重的更新(即线性函数的 y 轴截距和斜率)都受此单个步长大小控制。

因此,控制与较大梯度(在这种情况下,线性函数的斜率)相关的权重更新所需的非常小的步长极大地限制了具有较小梯度的另一个权重的速度(线性函数的 y 轴截距)被更新。在当前条件下,后者的权重不会收敛到其大约 26.7 的真实值。

考虑到您在编写 Java 代码时投入的时间和精力,我建议对其进行修改以使用两个离散的步长值,即每个权重的适当步长。Andrew Ng 在他的笔记中建议最好使用特征缩放来确保成本函数的轮廓在形式上更规则(即圆形)。但是,除了查看特征缩放之外,修改 Java 代码以对每个权重使用不同的步长可能是一个很好的练习。

要考虑的另一个想法是如何选择初始权重值。在您的 Java 代码中,您将这两个值都初始化为零。将权重初始化为小的分数值也很常见。然而,在这种特殊情况下,鉴于三维成本函数的高度椭圆(即非圆形)轮廓,这两种方法都不起作用。鉴于可以使用其他方法找到此问题的权重,例如 Matthew 在他的帖子末尾建议的线性系统的解决方案,您可以尝试将权重初始化为更接近正确权重的值,并查看您的原始代码如何使用单个步长收敛。

您找到的 Python 代码以与 Java 代码相同的方式接近解决方案 - 都使用单个步长参数。我修改了这个 Python 代码,为每个权重使用不同的步长。我已经把它包括在下面了。

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

它在 Python 3 下运行,它需要在“print”语句的参数周围加上括号。否则,它将通过删除括号在 Python 2 下运行。您需要使用 Andrew Ng 示例中的数据创建一个 CSV 文件。

使用可以交叉引用 Python 代码来检查您的 Java 代码。