¿Cómo se puede quedar atrapado en un punto de silla?

Question

Actualmente estoy un poco confundido por cómo el descenso de gradiente de mini-batch puede quedarse atrapado en un punto de silla.

La solución podría ser tan trivial que no lo entiendo.

Obtienes una nueva muestra en cada época, y calcula un nuevo error en función de un nuevo lote, por lo que la función de costo es estática solo para cada lote, lo que significa que el gradiente también debería cambiar para cada mini-batch... pero ¿según esto una implementación vanilla tendría problemas con los puntos de silla?

Otro desafío clave para minimizar funciones de error altamente no convexas comunes para redes neuronales es evitar quedar atrapado en sus numeros mínimos locales subóptimos. Dauphin et al. [19] argumentan que el la dificultad surge de hecho no de los mínimos locales sino de los puntos de silla, es decir, puntos donde una dimensión sube y otra baja. Estos puntos de silla suelen estar rodeados por un meseta del mismo error, lo que hace que sea notoriamente difícil para el SGD escapar, ya que el el gradiente está cerca de cero en todas las dimensiones.

¡Significa que especialmente el SGD tendría una clara ventaja contra los puntos de silla, ya que fluctúa hacia su convergencia... Las fluctuaciones y el muestreo aleatorio, y la función de costo siendo diferente para cada época deberían ser razones suficientes para no quedar atrapado en uno.

Para el descenso de gradiente de lote completo, ¿tiene sentido que pueda quedar atrapado en un punto de silla, ya que la función de error es constante.

Estoy un poco confundido en las otras dos partes.

Answer 1

Observa la imagen a continuación de Off Convex. En una función convexa (imagen más a la izquierda), solo hay un mínimo local, que también es el mínimo global. Pero en una función no convexa (imagen más a la derecha), puede haber varios mínimos locales y a menudo unir dos mínimos locales da como resultado un punto de silla. Si te acercas desde un punto más alto, el gradiente es relativamente más plano y corres el riesgo de quedarte atascado allí, especialmente si te mueves solo en una dirección.

Ahora, la cuestión es que, ya sea que estés optimizando utilizando mini-batch o descenso de gradiente estocástico, la función no convexa subyacente es la misma y el gradiente es una propiedad de esta función. Al hacer mini-batch, se consideran muchas muestras a la vez y se da un paso de gradiente promediado sobre todas ellas. Esto reduce la varianza. Pero si la dirección promedio del gradiente sigue apuntando en la misma dirección que el punto de silla, sigues corriendo el riesgo de quedarte atascado allí. La analogía es que si das 2 pasos hacia adelante y uno hacia atrás, al promediar esos pasos, terminas dando solo 1 paso hacia adelante. Si en cambio realizas SGD, das todos los pasos uno tras otro, pero si sigues moviéndote en una sola dirección, puedes llegar al punto de silla y descubrir que el gradiente en todos los lados es bastante plano y que el tamaño del paso es demasiado pequeño para superar esta parte plana. Esto no tiene nada que ver con si consideraste varios puntos a la vez o uno por uno en orden aleatorio.

Observa la visualización aquí. Incluso con SGD, si las fluctuaciones ocurren solo a lo largo de una dimensión, con los pasos cada vez más pequeños, convergerá en el punto de silla. En este caso, el método de mini-batch solo reduciría la cantidad de fluctuación pero no cambiaría la dirección del gradiente.

A veces, SGD puede escapar de puntos de silla simples, si las fluctuaciones ocurren a lo largo de otras direcciones y si el tamaño del paso es lo suficientemente grande como para superar la planitud. Pero a veces, las regiones de silla pueden ser bastante complejas, como se muestra en la imagen a continuación.

La forma en que métodos como momentum, ADAGRAD, Adam, etc., logran salir de esto es considerando los gradientes pasados. Considera el momentum,

$$ v_t = \gamma v_{t-1} + \eta \nabla_{theta} J(\theta) $$

que agrega una parte del último gradiente, $v_{t-1}$. En caso de que hayas estado yendo de un lado a otro en una dirección, cambiando de signo, termina frenando tu progreso. Mientras que si ha habido progreso positivo constante en una dirección, termina acumulándose y siguiendo en esa dirección.

Answer 2

No debería.

[1] ha demostrado que el descenso de gradiente con inicialización aleatoria y tamaño de paso constante adecuado no converge a un punto silla. Es una larga discusión, pero para darte una idea de por qué, mira el siguiente ejemplo:

$$f(x,y)=\frac12 x^2+ \frac14y^4 - \frac12y^2$$

Los puntos críticos son $$z_1=\begin{bmatrix}0\\0\end{bmatrix}, z_2=\begin{bmatrix}0\\1\end{bmatrix}, z_3=\begin{bmatrix}0\\-1\end{bmatrix}$$.

Los puntos $z_2$ y $z_3$ son mínimos locales aislados, y $z_1$ es un punto silla.

El descenso de gradiente inicializado desde cualquier punto de la forma $z_0=\begin{bmatrix}x\\0\end{bmatrix}$ converge al punto silla $z_1$. Cualquier otro punto inicial diverge o converge a un mínimo local, por lo que el conjunto estable de $z_1$ es el eje $x$, que es un conjunto de medida cero en $\mathbb{R}^2$. Al calcular el Hessiano, $$\nabla^2f(x,y)=\begin{bmatrix}1&&0\\0&&3y^2-1\end{bmatrix}$$

descubrimos que $\nabla^2f(z_1)$ tiene un eigenvalor positivo con un eigenvector que abarca el eje $x$, coincidiendo así con nuestra caracterización anterior del conjunto estable. Si el punto inicial se elige al azar, existe cero probabilidad de inicializar en el eje $x$ y por lo tanto cero probabilidad de converger al punto silla $z_1$.

Answer 3

Si vas al documento de referencia (también muestran empíricamente cómo su enfoque sin silla en realidad mejora el SGD de mini-lote), se establece:

Un paso del método de descenso de gradiente siempre apunta en la dirección correcta cerca de un punto de silla...y por lo tanto se dan pequeños pasos en direcciones que corresponden a valores propios de pequeño valor absoluto.

También señalan la presencia de "mesetas" cerca de los puntos de silla (en otras palabras, la silla no es empinada) - en estos casos, tomar pasos demasiado pequeños resultaría en una convergencia prematura antes de haber escapado de la región de silla. Dado que se trata de una optimización no convexa, la convergencia de la tasa de aprendizaje empeoraría esto.

Parece posible que se pueda intentar un enfoque iterativo, donde se reinicie el SGD de mini-lote una vez que se complete (es decir, restableciendo la tasa de aprendizaje) para ver si se puede escapar de la región problemática.

Answer 4

Creo que el problema es que al acercarse a un punto de silla entras en un plateau, es decir, un área con gradientes bajos (en valor absoluto). Especialmente cuando te acercas desde la cresta. Por lo tanto, tu algoritmo disminuye el tamaño del paso. Con un tamaño de paso disminuido, ahora todos los gradientes (en todas las direcciones) son pequeños en valor absoluto. Entonces, el algoritmo se detiene, pensando que está en el mínimo.

Si no disminuyes los pasos entonces estarás saltando sobre el mínimo, y pasándolos por alto muchas veces. Debes disminuir el tamaño del paso de alguna manera.