线性回归的梯度下降实现问题

Question

我正在学习 this Coursera class 机器学习/线性回归。以下是他们如何描述用于求解估计的 OLS 系数的梯度下降算法：

因此他们使用 w 作为系数，H 作为设计矩阵（或他们所说的特征），y 作为因变量。而它们的收敛准则通常是RSS的梯度小于tole运行ce epsilon的范数；也就是说，他们对"not converged"的定义是：

我在让这个算法收敛时遇到了问题，我想知道我是否在我的实现中忽略了一些东西。下面是代码。请注意，我还通过 statsmodels regression library 运行我在其中使用的示例数据集 (df)，只是为了查看回归可以收敛并获得与之相关的系数值。它做到了，他们是：

Intercept    4.344435
x1           4.387702
x2           0.450958

这是我的实现。在每次迭代时，它打印 RSS 梯度的范数：

import numpy as np
import numpy.linalg as LA
import pandas as pd
from pandas import DataFrame

# First define the grad function: grad(RSS) = -2H'(y-Hw)
def grad_rss(df, var_name_y, var_names_h, w):
    # Set up feature matrix H
    H = DataFrame({"Intercept" : [1 for i in range(0,len(df))]})
    for var_name_h in var_names_h:
        H[var_name_h] = df[var_name_h]

    # Set up y vector
    y = df[var_name_y]

    # Calculate the gradient of the RSS:  -2H'(y - Hw)
    result = -2 * np.transpose(H.values) @ (y.values - H.values @ w)

    return result

def ols_gradient_descent(df, var_name_y, var_names_h, epsilon = 0.0001, eta = 0.05):
    # Set all initial w values to 0.0001 (not related to our choice of epsilon)
    w = np.array([0.0001 for i in range(0, len(var_names_h) + 1)])

    # Iteration counter
    t = 0

    # Basic algorithm: keep subtracting eta * grad(RSS) from w until
    # ||grad(RSS)|| < epsilon.
    while True:
        t = t + 1

        grad = grad_rss(df, var_name_y, var_names_h, w)
        norm_grad = LA.norm(grad)

        if norm_grad < epsilon:
            break
        else:
            print("{} : {}".format(t, norm_grad))
            w = w - eta * grad

            if t > 10:
                raise Exception ("Failed to converge")

    return w

# ########################################## 

df = DataFrame({
        "y" : [20,40,60,80,100] ,
        "x1" : [1,5,7,9,11] ,
        "x2" : [23,29,60,85,99]         
    })

# Run
ols_gradient_descent(df, "y", ["x1", "x2"])

不幸的是，这并没有收敛，实际上打印出一个随着每次迭代而爆炸的范数：

1 : 44114.31506051333
2 : 98203544.03067812
3 : 218612547944.95386
4 : 486657040646682.9
5 : 1.083355358314664e+18
6 : 2.411675439503567e+21
7 : 5.368670935963926e+24
8 : 1.1951287949674022e+28
9 : 2.660496151835357e+31
10 : 5.922574875391406e+34
11 : 1.3184342751414824e+38
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
......
Exception: Failed to converge

如果我足够多地增加最大迭代次数，它不会收敛，而是会爆炸到无穷大。

这里是执行错误，还是我误解了class注释中的解释？

已更新答案

正如@Kant 建议的那样，eta 需要在每次迭代时更新。该课程本身有一些示例公式，但其中 none 有助于收敛。 This section of the Wikipedia page about gradient descent mentions the Barzilai-Borwein approach 作为更新 eta 的好方法。我实现了它并更改了我的代码以在每次迭代时用它更新 eta，并且回归成功收敛。下面是我对回归中使用的变量的维基百科版本公式的 t运行slation，以及实现它的代码。同样，在我原来的 ols_gradient_descent 循环中调用此代码来更新 eta.

def eta_t (w_t, w_t_minus_1, grad_t, grad_t_minus_1):
    delta_w = w_t - w_t_minus_1
    delta_grad = grad_t - grad_t_minus_1

    eta_t = (delta_w.T @ delta_grad) / (LA.norm(delta_grad))**2

    return eta_t

Answer 1

尝试减小 eta 的值。如果 eta 太高，梯度下降可能会发散。

线性回归的梯度下降实现问题

Issue with gradient descent implementation of linear regression

python

machine-learning

least-squares

gradient-descent

已更新答案