Как внедряется ускоренный градиентный спуск Нестерова в Tensorflow?

Question

Документация для tf.train.MomentumOptimizer предлагает параметр use_nesterov для использования метода ускоренного градиента Нестерова (NAG).

Однако NAG требует градиента в месте, отличном оттекущая переменная, которую нужно вычислить, и интерфейс apply_gradients допускает только передачу текущего градиента.Поэтому я не совсем понимаю, как алгоритм NAG может быть реализован с помощью этого интерфейса.

В документации сказано следующее о реализации:

use_nesterov: если True, то использовать NesterovMomentum.См. Sutskever et al., 2013 .Эта реализация всегда вычисляет градиенты по значению переменной (переменных), переданных оптимизатору.Использование Nesterov Momentum заставляет переменную (и) отслеживать значения, названные theta_t + mu*v_t в статье.

Прочитав статью в ссылке, я немного не уверен, отвечает ли это описание моемувопрос или нет.Как реализовать алгоритм NAG, если для интерфейса не требуется функция градиента?

Answer 1

TL; DR

Реализация Нестерова в TF действительно является приближением исходной формулы, действительной для высоких значений импульса.

Подробности

Это отличный вопрос.В статье обновление NAG определяется как

v<sub>t+1</sub> = μ.v<sub>t</sub> - λ.∇f(θ<sub>t</sub> + μ.v<sub>t</sub>)
θ<sub>t+1</sub> = θ<sub>t</sub> + v<sub>t+1</sub>

, где f - наша функция стоимости, θ<sub>t</sub> наши параметры во время t, μ импульс, λ обучениетемп;v<sub>t</sub> является внутренним аккумулятором NAG.

Основным отличием от стандартного импульса является использование градиента при θ<sub>t</sub> + μ.v<sub>t</sub>, , а не при θ<sub>t</sub>.Но, как вы сказали, тензор потока использует только градиент на θ<sub>t</sub>.Так в чем же хитрость?

Часть этой хитрости фактически упоминается в той части документации, которую вы цитировали: алгоритм отслеживает θ<sub>t</sub> + μ.v<sub>t</sub>, , а не θ<sub>t</sub>.Другая часть исходит из аппроксимации, действительной для высокого значения импульса.

Давайте сделаем небольшое изменение в бумаге для записи, чтобы аккумулятор придерживался определения тензорного потока.Давайте определим a<sub>t</sub> = v<sub>t</sub> / λ.Правила обновления немного изменены как

a<sub>t+1</sub> = μ.a<sub>t</sub> - ∇f(θ<sub>t</sub> + μ.λ.a<sub>t</sub>)
θ<sub>t+1</sub> = θ<sub>t</sub> + λ.a<sub>t+1</sub>

(Мотивация для этого изменения в TF состоит в том, что теперь a - это чистый градиент импульса, независимый от скорости обучения. Это делает процесс обновления устойчивым к изменениямв λ, распространенной на практике возможности, которую статья не рассматривает.)

Если мы отметим ψ<sub>t</sub> = θ<sub>t</sub> + μ.λ.a<sub>t</sub>, то

a<sub>t+1</sub> = μ.a<sub>t</sub> - ∇f(ψ<sub>t</sub>)
ψ<sub>t+1</sub> = θ<sub>t+1</sub> + μ.λ.a<sub>t+1</sub>
    = θ<sub>t</sub> + λ.a<sub>t+1</sub> + μ.λ.a<sub>t+1</sub>
    = ψ<sub>t</sub> + λ.a<sub>t+1</sub> + μ.λ.(a<sub>t+1</sub> - a<sub>t</sub>)
    = ψ<sub>t</sub> + λ.a<sub>t+1</sub> + μ.λ.[(μ-1)a<sub>t</sub> - ∇f(ψ<sub>t</sub>)]
    ≈ ψ<sub>t</sub> + λ.a<sub>t+1</sub>

Это последнее приближение справедливо для сильных значенийимпульс, где μ близко к 1, так что μ-1 близка к нулю, и ∇f(ψ<sub>t</sub>) мала по сравнению с a - это последнее приближение более спорно на самом деле, и менее действительны для направления при частом переключателя градиента.

Теперь у нас есть обновление, которое использует градиент текущей позиции, и правила довольно просты - на самом деле они соответствуют стандартному импульсу.

Однако мы хотим θ<sub>t</sub>не ψ<sub>t</sub>.По этой причине мы вычитаем μ.λ.a<sub>t+1</sub> из ψ<sub>t+1</sub> непосредственно перед его возвратом - и для восстановления ψ он снова добавляется первым делом при следующем вызове.

Answer 2

Я не смог увидеть никакой информации об этом в Интернете, и связанная статья, конечно, не помогла, поэтому я посмотрел на модульные тесты для tf.train.MomentumOptimizer, из которых я вижу тестыдля реализации как классического импульса, так и режимов NAG.

Сводка

var = var + accum * learning_rate * momentum
accum = accum * momentum + g
var = var - learning_rate * accum
var = var - accum * learning_rate * momentum

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

average_grad_0 = accum # previous rolling average
average_grad_1 = accum * momentum + g # updated rolling average
grad_diff = average_grad_1 - average_grad_0
adjustment = -learning_rate * (grad_diff * momentum + average_grad_1)
var += adjustment
accum = average_grad_new

Другими словами, мне кажется, что реализация tensorflow мне кажетсяпытается угадать «скорректированный градиент» в NAG, предполагая, что новый градиент будет оцениваться текущим средним градиентом плюс произведение импульса и изменения среднего градиента.Я хотел бы увидеть доказательства этого!

Далее подробно рассказывается о том, как классические режимы и режимы нестеров реализованы в tensorflow в соответствии с тестами.

Классический режим Momentum

Для use_nesterov=False, основанного на функции doTestBasic, у нас есть следующие начальные параметры:

learning_rate = 2.0
momentum = 0.9
var_0 = 1.0 # at time 0
grad = 0.1

На самом деле, это только первый элемент grads_0 и vars_0 массивов, но я сосредоточусь только на одном значении.Для последующих временных шагов у нас есть

var_1 = 1.0 - (0.1 * 2.0)
var_2 = 1.0 - (0.1 * 2.0) - ((0.9 * 0.1 + 0.1) * 2.0)

, который я собираюсь интерпретировать как значение;

var_1 = var_0 - (grad * learning_rate)
var_2 = var_1 - ((momentum * grad + grad) * learning_rate)

Если мы предположим, что для целей модульных тестов grad_0 == grad_1 == grad тогдаэто имеет смысл как формулировка классического импульса.

Режим ускоренного градиента (NAG) Нестерова

Для use_nesterov=True я посмотрел на функцию _update_nesterov_momentum_numpy и тест testNesterovMomentumcase.

Функция _update_nesterov_momentum_numpy имеет следующее определение:

  def _update_nesterov_momentum_numpy(self, var, accum, g, lr, momentum):
    var = var + accum * lr * momentum
    accum = accum * momentum + g
    var = var - lr * accum
    var = var - accum * lr * momentum
    return var, accum

и вызывается в модульных тестах следующим образом:

    for t in range(1, 5):
      opt_op.run()
      var0_np, accum0_np = self._update_nesterov_momentum_numpy(
          var0_np, accum0_np, var0_np * 10, 2.0, 0.9)