Стандартный градиентный спуск будет вычислять градиент для всего набора обучающих данных.
for i in range(nb_epochs):
params_grad = evaluate_gradient(loss_function, data, params)
params = params - learning_rate * params_grad
Для заранее определенного числа эпох мы сначала вычисляем вектор градиента weights_grad функции потерь для всего набора данных с нашими параметрами вектора параметров.
Stochastic Gradient Descent, напротив, выполняет обновление параметров для каждого примера обучения x (i) и метки y (i).
for i in range(nb_epochs):
np.random.shuffle(data)
for example in data:
params_grad = evaluate_gradient(loss_function, example, params)
params = params - learning_rate * params_grad
Говорят, что SGD намного быстрее. Однако я не понимаю, как это может быть намного быстрее, если у нас все еще есть цикл по всем точкам данных. Разве вычисление градиента в GD намного медленнее, чем вычисление GD для каждой точки данных в отдельности?
Код приходит отсюда .
Ответы:
Короткий ответ:
Длинный ответ:
Мое обозначение следует за курсом обучения Эндрю Н.Г. Если вы не знакомы с ним, вы можете просмотреть серию лекций здесь .
Давайте предположим регрессию на квадрате потерь, функция стоимости
и градиент
для градиента достойного (GD), мы обновляем параметр
Вот почему мы экономим время:
Предположим, у нас есть 1 миллиард точек данных.
В GD, чтобы обновить параметры один раз, нам нужен (точный) градиент. Это требует суммирования этих 1 миллиарда точек данных для выполнения 1 обновления.
В SGD мы можем думать об этом как о попытке получить приближенный градиент вместо точного градиента . Аппроксимация исходит из одной точки данных (или нескольких точек данных, называемых мини-пакетами). Поэтому в SGD мы можем очень быстро обновить параметры. Кроме того, если мы «зациклим» все данные (называемые одной эпохой), у нас фактически будет 1 миллиард обновлений.
Хитрость в том, что в SGD вам не нужно иметь 1 миллиард итераций / обновлений, а гораздо меньше итераций / обновлений, скажем, 1 миллион, и у вас будет «достаточно хорошая» модель для использования.
Я пишу код для демонстрации идеи. Сначала мы решаем линейную систему с помощью нормального уравнения, а затем решаем ее с помощью SGD. Затем мы сравниваем результаты в терминах значений параметров и конечных значений целевой функции. Чтобы визуализировать это позже, у нас будет 2 параметра для настройки.
Результаты:
Вот значения функции стоимости за итерации, мы можем видеть, что она может эффективно уменьшить потери, что иллюстрирует идею: мы можем использовать подмножество данных для аппроксимации градиента и получения «достаточно хороших» результатов.
sq_loss_gr_approx
источник