Является ли моя реализация стохастического градиентного спуска правильной?

Question

Я пытаюсь разработать стохастический градиентный спуск, но я не знаю, соответствует ли он на 100%.

• Стоимость, создаваемая моим алгоритмом стохастического градиентного спуска, иногда очень далека от того, который генерируется с помощью FMINUC или спуска градиента партии.
• , в то время как расходы на градиентный градиент партии сходятся, когда я устанавливаю скорость обучения альфа 0,2, я вынужден установить скорость обучения альфа 0,0001 для моей стохастической реализации, чтобы она не расходилась. Это нормально?

Вот некоторые результаты, которые я, полученные с помощью обучающего набора 10000 элементов и 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 

Answer 1

Это очень хорошо. Если вы беспокоитесь о выборе соответствующей скорости обучения alpha, вам следует подумать о применении метода поиска .

Поиск линии - это метод, который выбирает оптимальную скорость обучения для градиентного спуска на каждой итерации, что лучше, чем использование фиксированной скорости обучения на протяжении всего процесса оптимизации. Оптимальное значение для скорости обучения alpha - это то, которое локально (от текущего theta в направлении отрицательного градиента) минимизирует стоимость функции.

На каждой итерации градиентного спуска, начиная с курса обучения alpha = 0 и постепенно увеличивая alpha фиксированным шагом deltaAlpha = 0.01, например. Пересчитайте параметры theta и оцените функцию стоимости. Поскольку функция стоимости является выпуклой, увеличивая alpha (т. Е. Двигаясь в направлении отрицательного градиента), функция стоимости сначала начнет уменьшаться, а затем (в некоторый момент) увеличится. В этот момент прекратите поиск линии и возьмите последний alpha, прежде чем функция стоимости начнет увеличиваться. Теперь обновите параметры theta с помощью этого alpha. Если функция стоимости никогда не начнет увеличиваться, остановитесь на alpha = 1.

Примечание: Для больших факторов регуляризации (lambda = 100, lambda = 1000), возможно, что deltaAlpha является слишком большим, и что градиентный расходится. Если это так, уменьшите deltaAlpha 10 раз (deltaAlpha = 0.001, deltaAlpha = 0.0001), пока не дойдете до соответствующего deltaAlpha, для которого спуск градиента сходится.

Кроме того, вы должны подумать об использовании некоторого условия завершения, отличного от числа итераций, например. когда разница между стоимостными функциями в двух последующих итерациях становится достаточно маленькой (менее epsilon).

Answer 2

Существует причина, по малой величине скорости обучения. Короче говоря, когда темпы обучения убывают с соответствующей скоростью, и при условии относительно мягких предположений, стохастических градиентный сходится почти наверное к глобальному минимуму, когда целевая функция выпуклого или псевдовыпуклых, а иначе сходится почти наверное к a местный минимум. Это на самом деле является следствием теоремы Роббинса-Зигмунда.

Robbins, Herbert; Зигмунд, Дэвид О. (1971). «Теорема о сходимости для не отрицательных почти супермартингалов и некоторых приложений». В Rustagi, Jagdish S. Оптимизация методов в статистике. Academic Press

Answer 3

Скорость обучения всегда находится в диапазоне от 0 до 1. Если вы установили скорость обучения очень высоко, она следует в меньшей степени из-за пропуска. Так что возьмите небольшую скорость обучения, хотя требуется больше времени. Результат будет более убедительным.