¿Cuál es la diferencia entre el descenso de gradiente basado en el momento y el descenso de gradiente acelerado de Nesterov?

Entonces, el descenso de gradiente basado en el impulso funciona de la siguiente manera:

$v=self.momentum*m-lr*g$

donde es la actualización de peso anterior, y g es el gradiente actual con respecto a los parámetros p , l r es la tasa de aprendizaje y s e l f . m o m e n t u m es una constante.$m$$g$$p$$lr$$self.momentum$

$p_{new} = p + v = p + self.momentum * m - lr * g$

y el descenso acelerado de gradiente de Nesterov funciona de la siguiente manera:

$p_{new} = p + self.momentum * v - lr * g$

que es equivalente a:

$p_{new} = p + self.momentum * (self.momentum * m - lr * g ) - lr * g$

o

$p_{new} = p + self.momentum^2 * m - (1 + self.momentum) * lr * g$

fuente: https://github.com/fchollet/keras/blob/master/keras/optimizers.py

Entonces, para mí, parece que el descenso acelerado de gradiente de Nesterov solo le da más peso al término lr * g sobre el término de cambio de peso perceptible m (en comparación con el impulso anterior simple). ¿Es correcta esta interpretación?

La respuesta de Arech sobre el impulso de Nesterov es correcta, pero el código esencialmente hace lo mismo. Entonces, a este respecto, el método de Nesterov da más peso al término , y menos peso al término v .$lr \cdot g$$v$

Para ilustrar por qué la implementación de Keras es correcta, tomaré prestado el ejemplo de Geoffrey Hinton .

El método de Nesterov adopta el enfoque "apuesta-> corrección".
w ′ = w + v ′ El vector marrón es m ⋅ v (apuesta / salto), el vector rojo es - l r ⋅ ∇ ( w + m ⋅ v ) (corrección), y el vector verde es m ⋅ v - l r $v' = m \cdot v - lr \cdot \nabla(w+m \cdot v)$
$w' = w + v'$
$m \cdot v$$-lr \cdot \nabla(w+m \cdot v)$ (donde realmente deberíamos movernos a). ∇ ( ⋅ ) es la función de gradiente.$m \cdot v-lr \cdot \nabla(w+m \cdot v)$$\nabla(\cdot)$

El código se ve diferente porque se mueve por el vector marrón en lugar del vector verde , ya que el método de Nesterov solo requiere evaluar lugar de ∇ ( w ) . Por eso en cada paso queremos$\nabla(w+m \cdot v) =: g$$\nabla(w)$

1. volver a donde estábamos $(1 \rightarrow 0)$
2. siga el vector verde a donde deberíamos estar $(0 \rightarrow 2)$
3. hacer otra apuesta $(2 \rightarrow 3)$

El código de Keras escrito para abreviar es , y hacemos algunas matemáticas$p' = p + m \cdot (m \cdot v - lr \cdot g) - lr \cdot g$

$\begin{align} p' &= p - m \cdot v + m \cdot v + m \cdot (m \cdot v - lr \cdot g) - lr \cdot g\\ &= p - m \cdot v + m \cdot v - lr \cdot g + m \cdot (m \cdot v - lr \cdot g)\\ &= p - m \cdot v + (m \cdot v-lr \cdot g) + m \cdot (m \cdot v-lr \cdot g) \end{align}$

$1 \rightarrow 0 \rightarrow 2 \rightarrow 3$$1 \rightarrow 2 \rightarrow 3$

$p - m \cdot v$$p$

Me parece que la pregunta del OP ya fue respondida, pero trataría de dar otra explicación (con suerte intuitiva) sobre el momento y la diferencia entre el momento clásico (CM) y el gradiente acelerado (NAG) de Nesterov.

tl; dr
Simplemente salte a la imagen al final.
El razonamiento de NAG_ball es otra parte importante, pero no estoy seguro de que sería fácil de entender sin todo lo demás.

$\theta$$f(\theta)$

En otras noticias, últimamente aparecieron estas dos bolas inteligentes:

Resulta (de acuerdo con el comportamiento observado de las bolas, y de acuerdo con el artículo sobre la importancia de la inicialización y el impulso en el aprendizaje profundo , que describe tanto CM como NAG en la sección 2) que cada bola se comporta exactamente como uno de estos métodos , y entonces los llamaríamos "CM_ball" y "NAG_ball":
(NAG_ball está sonriendo, porque recientemente vio el final de la Lección 6c - El método de impulso, por Geoffrey Hinton con Nitish Srivastava y Kevin Swersky , y por eso cree más que nunca que su comportamiento lleva a encontrar un mínimo más rápido).

Así es como se comportan las bolas:

• 
  $\theta_t$$t$$v_t$$t$$\theta_t=\theta_{t-1}+v_t$
• $v_t$
  • $v_{t-1}$
    $v_{t-1}$
    $\mu$$0.9 \le \mu <1$$\mu v_{t-1}$
    $\mu$
    
  • 
    
    $\epsilon$$\epsilon>0$
    $\epsilon$
    $g$$-\epsilon g$
• $$v_t=\mu v_{t-1} -\epsilon g$$
• 
  $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}\right)$$

• 
  

  $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}+\mu v_{t-1}\right)$$

  Razonamiento de NAG_ball

  • Cualquier salto que ocurra primero, mi Momentum Jump sería el mismo.
    Así que debería considerar la situación como si ya hubiera realizado mi Momentum Jump, y estoy a punto de hacer mi Slope Jump.
  • Ahora, mi Slope Jump comenzará conceptualmente desde aquí, pero puedo elegir si calculo cuál sería mi Slope Jump como si comenzara antes del Momentum Jump, o como si comenzara aquí.
  • $\theta$$\theta$$\theta$
    
    

$\theta$
$f(\theta)$$7$

Apéndice 1 - Una demostración del razonamiento de NAG_ball

En este fascinante gif de Alec Radford , puedes ver que NAG se desempeña posiblemente mejor que CM ("Momentum" en el gif).
(El mínimo es dónde está la estrella y las curvas son líneas de contorno . Para obtener una explicación sobre las líneas de contorno y por qué son perpendiculares al gradiente, vea los videos 1 y 2 del legendario 3Blue1Brown ).

Un análisis de un momento específico demuestra el razonamiento de NAG_ball:

• La flecha morada (larga) es el subpaso de impulso.
• La flecha roja transparente es el subpaso de gradiente si comienza antes del subpaso de impulso.
• La flecha negra es el subpaso de gradiente si comienza después del subpaso de impulso.
• CM terminaría en el blanco de la flecha roja oscura.
• NAG terminaría en el blanco de la flecha negra.

Apéndice 2 - cosas / términos que inventé (por el bien de la intuición)

• CM_ball
• NAG_ball
• Doble salto
• Momentum Jump
• Momento perdido debido a la fricción con el aire.
• Salto en pendiente
• Ansia de una pelota
• Yo observando las bolas ayer

Apéndice 3 - términos que no inventé

• La forma en que se comportan CM y NAG:
  • Principalmente dependía de la sección 2 del documento sobre la importancia de la inicialización y el impulso en el aprendizaje profundo .
    
  • Además, una descripción general de los algoritmos de optimización de descenso de gradiente (una publicación de blog de Sebastian Ruder) realmente me ayudó a comprender CM y NAG (y mucho más).
• Coeficiente de impulso: un término utilizado al menos por el artículo
• Tasa de aprendizaje

No lo creo.

Hay una buena descripción de las propiedades de Nesterov Momentum (también conocido como Gradiente Acelerado de Nesterov) en, por ejemplo, Sutskever, Martens et al. "Sobre la importancia de la inicialización y el impulso en el aprendizaje profundo" 2013 .

La principal diferencia es que en el momento clásico primero corrige su velocidad y luego da un gran paso de acuerdo con esa velocidad (y luego repite), pero en el momento de Nesterov primero da un paso en la dirección de la velocidad y luego realiza una corrección a un vector de velocidad basado en nueva ubicación (luego repita).

es decir, impulso clásico:

vW(t+1) = momentum.*Vw(t) - scaling .* gradient_F( W(t) )
W(t+1) = W(t) + vW(t+1)

Si bien el impulso de Nesterov es este:

vW(t+1) = momentum.*Vw(t) - scaling .* gradient_F( W(t) + momentum.*vW(t) )
W(t+1) = W(t) + vW(t+1)

En realidad, esto hace una gran diferencia en la práctica ...

Agregado: un curso de Stanford sobre redes neuronales, cs231n , ofrece otra forma de los pasos:

v = mu * v_prev - learning_rate * gradient(x)   # GD + momentum
v_nesterov = v + mu * (v - v_prev)              # keep going, extrapolate
x += v_nesterov

Aquí vestá el estado de velocidad, también conocido como paso, y mues un factor de impulso, típicamente 0,9 más o menos. ( v, xY learning_ratepueden ser vectores muy largas; con numpy, el código es el mismo.)

ven la primera línea es el descenso en gradiente con impulso; v_nesterovextrapola, continúa. Por ejemplo, con mu = 0.9,

v_prev  v   --> v_nesterov
---------------
 0  10  -->  19
10   0  -->  -9
10  10  -->  10
10  20  -->  29

La siguiente descripción tiene 3 términos: el
término 1 solo es descenso de gradiente simple (GD),
1 + 2 da GD + impulso,
1 + 2 + 3 da Nesterov GD.

$x_t \to y_t$$y_t \to x_{t+1}$

$\qquad y_t = x_t + m (x_t - x_{t-1}) \quad$ - impulso, predictor
$\qquad x_{t+1} = y_t + h\ g(y_t) \qquad$ - gradiente

$g_t \equiv - \nabla f(y_t)$$h$

$y_t$

$\qquad y_{t+1} = y_t$
$\qquad \qquad + \ h \ g_t \qquad \qquad \quad$ - gradiente
$\qquad \qquad + \ m \ (y_t - y_{t-1}) \qquad$ - impulso de paso
$\qquad \qquad + \ m \ h \ (g_t - g_{t-1}) \quad$ - impulso gradiente

El último término es la diferencia entre GD con impulso simple y GD con impulso de Nesterov.

$m$$m_{grad}$
$\qquad \qquad + \ m \ (y_t - y_{t-1}) \qquad$ - impulso de paso
$\qquad \qquad + \ m_{grad} \ h \ (g_t - g_{t-1}) \quad$ - impulso gradiente

$m_{grad} = 0$$m_{grad} = m$
$m_{grad} > 0$
$m_{grad} \sim -.1$

$m_t$$h_t$