8

我正在尝试为斯坦福机器学习讲座（ 25:00 左右的第 2讲）中解释的梯度下降算法编写一些代码。下面是我最初使用的实现，我认为它是从讲座中正确复制的，但是当我将大数 ( >8) 添加到训练集时它不会收敛。

我正在输入一个数字X，然后point (X,X)被添加到训练集中，所以目前，我只是想让它收敛到y=ax+bwherea=1=theta\[1\]和b=0=theta\[0\]。训练集是数组x，y其中(x[i],y[i])是一个点。

void train()
{
    double delta;
    for (int i = 0; i < x.size(); i++)
    {
        delta = y[i]-hypothesis(x[i]);
        theta[1] += alpha*delta*x[i];
        theta[0] += alpha*delta*1;
    }
}

void C_Approx::display()
{
    std::cout<<theta[1]<<"x + "<<theta[0]<<" \t "<<"f(x)="<<hypothesis(1)<<std::endl;
}

我得到的一些结果：我输入一个数字，它运行train()了几次，然后display()

1
0.33616x + 0.33616   f(x)=0.67232
1
0.482408x + 0.482408     f(x)=0.964816
1
0.499381x + 0.499381     f(x)=0.998762
1
0.499993x + 0.499993     f(x)=0.999986
1
0.5x + 0.5   f(x)=1

它通过后发散的一个例子8：

1
0.33616x + 0.33616   f(x)=0.67232
2
0.705508x + 0.509914     f(x)=1.21542
3
0.850024x + 0.449928     f(x)=1.29995
4
0.936062x + 0.330346     f(x)=1.26641
5
0.951346x + 0.231295     f(x)=1.18264
6
0.992876x + 0.137739     f(x)=1.13062
7
0.932206x + 0.127372     f(x)=1.05958
8
1.00077x + 0.000493063   f(x)=1.00126
9
-0.689325x + -0.0714712      f(x)=-0.760797
10
4.10321e+08x + 4.365e+07     f(x)=4.53971e+08
11
1.79968e+22x + 1.61125e+21   f(x)=1.9608e+22
12
-3.9452e+41x + -3.26957e+40      f(x)=-4.27216e+41

我尝试了这里提出的缩放步骤的解决方案，并得到了类似的结果。我究竟做错了什么？

4

6 回答 6

9

你的实现很好。通常，当 α 太大时，随机梯度下降可能会发散。对于大型数据集，你会做的是获取一个合理大小的随机样本，找到能给你最好结果的 α，然后将其用于其余部分。

于 2011-10-16T14:34:26.337 回答
4

我遇到了同样的问题（尽管在 Java 中），因为我的学习率太大。
简而言之，我正在使用α = 0.001，我必须推动它0.000001才能看到实际的收敛。

当然，这些值与您的数据集相关联。

于 2014-03-03T10:05:15.507 回答
1

当您的成本函数增加或上下循环时，您通常有一个太大的值alpha。你alpha在用什么？

从 an 开始alpha = 0.001，看看是否收敛？如果不尝试各种alphas (0.003, 0.01, 0.03, 0.1, 0.3, 1)并找到一个快速收敛的。

缩放数据（归一化）仅对 1 个特征（您的theta[1]）无济于事，因为归一化仅适用于2+特征（多元线性回归）。

还要记住，对于少数特征，您可以使用正态方程来获得正确答案。

于 2011-10-20T15:08:47.463 回答
1

使用回溯线搜索来保证收敛。实现起来非常简单。请参阅 Stephen Boyd，Convex Optimization 以供参考。您可以为回溯线搜索选择一些标准的 alpha、beta 值，例如 0.3 和 0.8。

于 2016-04-22T06:19:24.197 回答
0

如果我理解正确，您的训练集只有在一条线的边缘有一个非零梯度？除非你从这条线开始（实际上是从你的训练点之一开始），否则你不会找到这条线。您始终处于局部最小值。

于 2011-10-16T14:22:50.137 回答
0

从您的描述来看，您正在解决什么问题并不清楚。发布外部资源的链接也是非常危险的——你可能会在 stackoverflow 中被阻止。

在任何情况下 - 梯度下降方法和具有固定步长（ML社区称之为学习率）的（次梯度下降）不应该收敛。

ps 机器学习社区对“收敛条件”和“收敛到什么”并不感兴趣——他们有兴趣创建通过交叉验证并获得良好结果的“某物”。

如果您对优化感到好奇 - 开始研究凸优化。不幸的是，很难找到它的工作，但它为各种数学优化事情中发生的事情增添了清晰的视野。

这是为简单的二次目标演示它的源代码：

#!/usr/bin/env python
# Gradiend descend method (without stepping) is not converged for convex         
# objective

alpha = 0.1

#k = 10.0 # jumping around minimum
k = 20.0   # diverge
#k = 0.001  # algorithm converged but gap to the optimal is big

def f(x): return k*x*x
def g(x): return 2*k*x

x0 = 12
xNext = x0
i = 0
threshold = 0.01

while True:
    i += 1
    xNext = xNext + alpha*(-1)*(g(xNext))
    obj = (xNext)
    print "Iteration: %i, Iterate: %f, Objective: %f, Optimality Gap: %f" % (i, xNext, obj, obj - f(0.0))

    if (abs(g(xNext)) < threshold):
        break
    if i > 50:
        break

print "\nYou launched application with x0=%f,threshold=%f" % (x0, threshold)
于 2018-06-08T21:40:01.810 回答