我的随机梯度下降实现是否正确？

Question

我正在尝试开发随机梯度下降算法，但我不确定它是否100％正确。

• 我的随机梯度下降算法生成的成本有时与FMINUC或批量梯度下降生成的成本相差很远。
• 当我将学习率alpha设置为0.2时，批量梯度下降成本会收敛，但是我强制将学习率alpha设置为0.0001以使随机实现不发散。这种情况正常吗？

以下是我在训练集为10,000个元素且num_iter为100或500时得到的一些结果：

    FMINUC : 
    Iteration  #100 | Cost: 5.147056e-001

    BACTH GRADIENT DESCENT  500 ITER
    Iteration #500 - Cost = 5.535241e-001

    STOCHASTIC GRADIENT DESCENT 100 ITER
    Iteration #100 - Cost = 5.683117e-001  % First time I launched
    Iteration #100 - Cost = 7.047196e-001  % Second time I launched

逻辑回归的梯度下降实现

J_history = zeros(num_iters, 1); 

for iter = 1:num_iters 

    [J, gradJ] = lrCostFunction(theta, X, y, lambda);
    theta = theta - alpha * gradJ;
    J_history(iter) = J;

    fprintf('Iteration #%d - Cost = %d... \r\n',iter, J_history(iter));
end

逻辑回归的随机梯度下降实现

% number of training examples
m = length(y);

% STEP1 : we shuffle the data
data = [y, X];
data = data(randperm(size(data,1)),:);
y = data(:,1);
X = data(:,2:end);

for iter = 1:num_iters 

     for i = 1:m
        x = X(i,:); % Select one example
        [J, gradJ] = lrCostFunction(theta, x, y(i,:), lambda);
        theta = theta - alpha * gradJ;
     end

     J_history(iter) = J;
     fprintf('Iteration #%d - Cost = %d... \r\n',iter, J);

end

供参考，这是我例子中使用的逻辑回归成本函数

function [J, grad] = lrCostFunction(theta, X, y, lambda)

m = length(y); % number of training examples

% We calculate J    
hypothesis = sigmoid(X*theta); 
costFun = (-y.*log(hypothesis) - (1-y).*log(1-hypothesis));    
J = (1/m) * sum(costFun) + (lambda/(2*m))*sum(theta(2:length(theta)).^2);

% We calculate grad using the partial derivatives
beta = (hypothesis-y); 
grad = (1/m)*(X'*beta);
temp = theta;  
temp(1) = 0;   % because we don't add anything for j = 0  
grad = grad + (lambda/m)*temp; 
grad = grad(:);

end

- alexandrekow

Answer 1

这基本上是没问题的。如果你担心选择适当的学习率alpha，那么你应该考虑应用线性搜索方法。

线性搜索是一种在每次迭代时为梯度下降选择最佳学习率的方法，这比在整个优化过程中使用固定的学习率要好。学习率alpha的最佳值是局部（从当前theta沿着负梯度方向）最小化成本函数的值。

在梯度下降的每次迭代中，从学习率alpha = 0开始，并逐渐增加alpha，例如，通过固定步长deltaAlpha = 0.01。重新计算参数theta并评估成本函数。由于成本函数是凸函数，通过增加alpha（即向负梯度方向移动），成本函数将首先开始下降，然后（在某个时刻）开始上升。在那一刻停止线性搜索并取在成本函数开始上升之前的最后一个alpha。现在使用该alpha更新参数theta。如果成本函数从未开始上升，请在alpha = 1处停止。

注意：对于大的正则化因子（lambda = 100，lambda = 1000），deltaAlpha可能太大，导致梯度下降发散。如果是这种情况，请将deltaAlpha减小10倍（deltaAlpha = 0.001，deltaAlpha = 0.0001），直到找到梯度下降收敛的适当deltaAlpha。

此外，你应该考虑使用一些终止条件，而不是迭代次数，例如，当两个连续迭代之间的成本函数差异变得足够小（小于某个epsilon）时。

- Kodin

Answer 2

学习率小的原因是有道理的。简单来说，如果学习率以适当的速率下降，并且在相对温和的假设条件下，当目标函数为凸函数或拟凸函数时，随机梯度下降算法几乎总能收敛到全局最小值，否则几乎总能收敛到局部最小值。这实际上是Robbins-Siegmund定理的结果。

Robbins, Herbert; Siegmund, David O. (1971). "A convergence theorem for non negative almost supermartingales and some applications". In Rustagi, Jagdish S. Optimizing Methods in Statistics. Academic Press

- NKN

---

我理解的是，如果学习率固定，则成本将在全局最小值周围“振荡”，但永远无法达到它。这就是为什么如果我们按固定速率降低学习率，例如将其乘以0.8，那么算法的振荡会越来越少，并最终达到非常接近最小值的值。 - alexandrekow

是的，你说得对。当你使用固定的学习率时，我所说的情况就会发生。 - NKN

Answer 3

学习率始终在0到1之间。如果您将学习率设置得非常高，则由于跳过，它会较少地遵循所需内容。因此，请选择较小的学习率，即使需要更多时间。输出结果将更加令人信服。

- pinak