为什么我的梯度是错误的（Coursera、逻辑回归、Julia）？

Question

我正在尝试在 Julia 中从 Coursera 进行逻辑回归，但它不起作用。

计算梯度的 Julia 代码：

sigmoid(z) = 1 / (1 + e ^ -z)

hypotesis(theta, x) = sigmoid(scalar(theta' * x))

function gradient(theta, x, y)
    (m, n) = size(x)
    h = [hypotesis(theta, x[i,:]') for i in 1:m]
    g = Array(Float64, n, 1)
    for j in 1:n
        g[j] = sum([(h[i] - y[i]) * x[i, j] for i in 1:m])
    end
    g
end

如果使用此渐变，则会产生错误的结果。不知道为什么，代码似乎是正确的。

full Julia script。在此脚本中，使用我的梯度下降实现和使用内置的 Optim 包计算出最佳 Theta，结果不同。

Answer 1

梯度是正确的（高达标量倍数，正如@roygvib 指出的那样）。问题出在梯度下降上。

如果你在梯度下降过程中查看成本函数的值，你会看到很多 NaN，这可能来自指数：降低步长（例如 1e-5）将避免溢出，但是你将不得不增加很多迭代次数（可能 10_000_000）。

更好（更快）的解决方案是让步长变化。例如，可以将步长乘以 1.1 如果成本函数在一步后改善（最优仍然在这个方向看起来很远：我们可以走得更快），如果不是，则将其除以 2（我们走得太快，最终超过了最小值）。

也可以在梯度方向上做线搜索来找到最佳步长（但这很耗时，可以用近似值代替，例如 Armijo 规则）。

重新调整预测变量也有帮助。

Answer 2

我尝试使用以下例程将 OP 代码中的 gradient() 与 cost_j() 的数值导数（这是最小化的 objective 函数）进行比较

function grad_num( theta, x, y )
    g = zeros( 3 )

    eps = 1.0e-6
    disp = zeros( 3 )

    for k = 1:3
        disp[:] = theta[:]

        disp[ k ]= theta[ k ] + eps
        plus = cost_j( disp, x, y )
        disp[ k ]= theta[ k ] - eps
        minus = cost_j( disp, x, y )

        g[ k ] = ( plus - minus ) / ( 2.0 * eps )
    end
    return g
end

但是从这两个例程中得到的梯度值似乎不太吻合（至少对于最小化的初始阶段）...所以我手动推导了cost_j( theta, x, y )的梯度，从中它似乎缺少 m 的除法：

#/ OP's code
# g[j] = sum( [ (h[i] - y[i]) * x[i, j] for i in 1:m ] )

#/ modified code
  g[j] = sum( [ (h[i] - y[i]) * x[i, j] for i in 1:m ] ) / m

因为我不太确定上面的代码和表达式是否真的正确，你能不能自己检查一下...?

但实际上，无论我使用原始梯度还是校正梯度，程序都收敛到相同的最小值（0.2034977016，与从Optim获得的几乎相同），因为两个梯度仅相差一个乘法因子！因为收敛的很慢，所以我也按照Vincent的建议自适应修改了步长alpha（这里我对acceleration/deceleration使用了比较适中的值）：

function gradient_descent(x, y, theta, alpha, n_iterations)
    ... 
    c = cost_j( theta, x, y )

    for i = 1:n_iterations
        c_prev = c
        c = cost_j( theta, x, y )

        if c - c_prev < 0.0
            alpha *= 1.01
        else
            alpha /= 1.05
        end
        theta[:] = theta - alpha * gradient(theta, x, y)
    end
    ...
end

并将此例程称为

optimal_theta = gradient_descent( x, y, [0 0 0]', 1.5e-3, 10^7 )[ 1 ]

cost_j 与迭代步骤的变化如下图所示。

为什么我的梯度是错误的（Coursera、逻辑回归、Julia）？

Why my Gradient is wrong (Coursera, Logistic Regression, Julia)?

gradient

julia

logistic-regression

gradient-descent