Как стохастический градиентный спуск может сэкономить время по сравнению со стандартным градиентным спуском?

15

Стандартный градиентный спуск будет вычислять градиент для всего набора обучающих данных.

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 для каждой точки данных в отдельности?

Код приходит отсюда .

Алина
источник
1
Во втором случае вам понадобится небольшая партия для аппроксимации всего набора данных. Это обычно работает довольно хорошо. Таким образом, запутанная часть, вероятно, состоит в том, что похоже, что число эпох одинаково в обоих случаях, но вам не понадобится столько же эпох в случае 2. «Гиперпараметры» будут разными для этих двух методов: GD nb_epochs! = SGD nb_epochs. Допустим, в качестве аргумента: GD nb_epochs = SGD examples * nb_epochs, так что общее число циклов одинаково, но вычисление градиента происходит быстрее в SGD.
Нима Мусави
Этот ответ на резюме является хорошим и связанным.
Жубарб

Ответы:

23

Короткий ответ:

  • При настройке большого количества данных (скажем, нескольких миллионов точек данных) расчет стоимости или градиента занимает очень много времени, потому что нам необходимо суммировать по всем точкам данных.
  • Нам НЕ нужно иметь точный градиент, чтобы уменьшить стоимость в данной итерации. Некоторое приближение градиента будет работать хорошо.
  • Стохастический градиент достойного (SGD) аппроксимирует градиент, используя только одну точку данных. Таким образом, оценка градиента экономит много времени по сравнению с суммированием по всем данным.
  • При «разумном» количестве итераций (это число может составлять пару тысяч и намного меньше, чем число точек данных, которые могут быть миллионами), приличный стохастический градиент может получить разумное хорошее решение.

Длинный ответ:

Мое обозначение следует за курсом обучения Эндрю Н.Г. Если вы не знакомы с ним, вы можете просмотреть серию лекций здесь .

Давайте предположим регрессию на квадрате потерь, функция стоимости

J(θ)знак равно12мΣязнак равно1м(часθ(Икс(я))-Y(я))2

и градиент

dJ(θ)dθзнак равно1мΣязнак равно1м(часθ(Икс(я))-Y(я))Икс(я)

для градиента достойного (GD), мы обновляем параметр

θNевесзнак равноθоLd-α1мΣязнак равно1м(часθ(Икс(я))-Y(я))Икс(я)

1/мИкс(я),Y(я)

θNевесзнак равноθоLd-α(часθ(Икс(я))-Y(я))Икс(я)

Вот почему мы экономим время:

Предположим, у нас есть 1 миллиард точек данных.

  • В GD, чтобы обновить параметры один раз, нам нужен (точный) градиент. Это требует суммирования этих 1 миллиарда точек данных для выполнения 1 обновления.

  • В SGD мы можем думать об этом как о попытке получить приближенный градиент вместо точного градиента . Аппроксимация исходит из одной точки данных (или нескольких точек данных, называемых мини-пакетами). Поэтому в SGD мы можем очень быстро обновить параметры. Кроме того, если мы «зациклим» все данные (называемые одной эпохой), у нас фактически будет 1 миллиард обновлений.

Хитрость в том, что в SGD вам не нужно иметь 1 миллиард итераций / обновлений, а гораздо меньше итераций / обновлений, скажем, 1 миллион, и у вас будет «достаточно хорошая» модель для использования.


Я пишу код для демонстрации идеи. Сначала мы решаем линейную систему с помощью нормального уравнения, а затем решаем ее с помощью SGD. Затем мы сравниваем результаты в терминах значений параметров и конечных значений целевой функции. Чтобы визуализировать это позже, у нас будет 2 параметра для настройки.

set.seed(0);n_data=1e3;n_feature=2;
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)
res1=solve(t(A) %*% A, t(A) %*% b)

sq_loss<-function(A,b,x){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1])
}

sq_loss_gr_approx<-function(A,b,x){
  # note, in GD, we need to sum over all data
  # here i is just one random index sample
  i=sample(1:n_data, 1)
  gr=2*(crossprod(A[i,],x)-b[i])*A[i,]
  return(gr)
}

x=runif(n_feature)
alpha=0.01
N_iter=300
loss=rep(0,N_iter)

for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr_approx(A,b,x)
  loss[i]=sq_loss(A,b,x)
}

Результаты:

as.vector(res1)
[1] 0.4368427 0.3991028
x
[1] 0.3580121 0.4782659

124.1343123.0355

Вот значения функции стоимости за итерации, мы можем видеть, что она может эффективно уменьшить потери, что иллюстрирует идею: мы можем использовать подмножество данных для аппроксимации градиента и получения «достаточно хороших» результатов.

введите описание изображения здесь

введите описание изображения здесь

1000sq_loss_gr_approx3001000

Хайтау Ду
источник
Я думал, что аргумент о «скорости» больше о том, сколько операций / итераций необходимо, чтобы сходиться к локальному оптимуму? (А также тот случайный градиентный спуск имеет тенденцию сходиться к лучшей оптиме.)
GeoMatt22
Насколько я понял, в коде Python, который я предоставил, переменная "data" - то же самое. Мини-пакетный градиент приличный - код отличается от SDG (и именно там он использует только небольшую часть данных). Кроме того, в предоставленном вами объяснении, хотя мы избавляемся от суммы в SDG, мы по-прежнему вычисляем обновление для каждой точки данных. Я до сих пор не понимаю, как обновление параметра во время цикла по каждой точке данных происходит быстрее, чем просто взять сумму по всем точкам данных одновременно.
Алина
@ GeoMatt22 В предоставленной мною ссылке говорится: «С другой стороны, это в конечном итоге усложняет сближение до точного минимума, поскольку SGD будет продолжать превышать допустимые пределы». Это означает, что это не сходится к лучшей оптиме. Или я ошибся?
Алина
@ Тоня Я не эксперт, но, например, эта очень влиятельная статья в области глубокого обучения дает аргумент «более быстрое и надежное обучение» для стохастического градиентного спуска. Обратите внимание, что он не использует «сырую» версию, но использует различные оценки кривизны для установки (зависящей от координат) скорости обучения.
GeoMatt22
1
@ Тоня, да. любое «слабое» приближение градиента будет работать. Вы можете проверить «повышение градиента», что является аналогичной идеей. С другой стороны, я пишу код для демонстрации идеи. Я опубликую это, когда это будет готово.
Haitao Du