¿Por qué el método de Newton no se usa ampliamente en el aprendizaje automático?

Esto es algo que me ha estado molestando por un tiempo, y no pude encontrar ninguna respuesta satisfactoria en línea, así que aquí va:

Después de revisar un conjunto de conferencias sobre optimización convexa, el método de Newton parece ser un algoritmo muy superior al descenso de gradiente para encontrar soluciones óptimas a nivel mundial, porque el método de Newton puede proporcionar una garantía para su solución, es invariante afín y, sobre todo, converge en Mucho menos pasos. ¿Por qué los algoritmos de optimización de segundo orden, como el método de Newton, no se usan tanto como el descenso de gradiente estocástico en problemas de aprendizaje automático?

La pendiente de gradiente maximiza una función utilizando el conocimiento de su derivada. El método de Newton, un algoritmo de búsqueda de raíz, maximiza una función utilizando el conocimiento de su segunda derivada. Eso puede ser más rápido cuando se conoce la segunda derivada y es fácil de calcular (el algoritmo de Newton-Raphson se usa en la regresión logística). Sin embargo, la expresión analítica para la segunda derivada es a menudo complicada o intratable, y requiere muchos cálculos. Los métodos numéricos para calcular la segunda derivada también requieren muchos cálculos: si se requieren valores para calcular la primera derivada, se requieren para la segunda derivada.N $N$$N^2$

Más personas deberían usar el método de Newton en el aprendizaje automático *. Digo esto como alguien con experiencia en optimización numérica, que ha incursionado en el aprendizaje automático en los últimos años.

Los inconvenientes en las respuestas aquí (e incluso en la literatura) no son un problema si utiliza el método de Newton correctamente. Además, los inconvenientes que importan también ralentizan el descenso del gradiente en la misma cantidad o más, pero a través de mecanismos menos obvios.

• El uso de la búsqueda lineal con las condiciones de Wolfe o el uso de regiones de confianza evita la convergencia a los puntos de silla. Una implementación adecuada de descenso de gradiente también debería estar haciendo esto. El artículo al que se hace referencia en Cam.Davidson. La respuesta de Pilon señala problemas con el "método de Newton" en presencia de puntos de silla de montar, pero la solución que recomiendan es también un método de Newton.

• El uso del método de Newton no requiere la construcción de toda la arpillera (densa); puede aplicar el inverso del hessiano a un vector con métodos iterativos que solo usan productos de matriz-vector (por ejemplo, métodos de Krylov como el gradiente conjugado). Ver, por ejemplo, el método de región de confianza CG-Steihaug.

• Puede calcular eficientemente los productos de matriz-vector de Hesse resolviendo dos ecuaciones adjuntas de orden superior de la misma forma que la ecuación adjunta que ya se utiliza para calcular el gradiente (por ejemplo, el trabajo de dos pasos de propagación hacia atrás en el entrenamiento de redes neuronales).

• El mal acondicionamiento ralentiza la convergencia de los solucionadores lineales iterativos, pero también ralentiza el descenso del gradiente por igual o peor. El uso del método de Newton en lugar del descenso de gradiente desplaza la dificultad de la etapa de optimización no lineal (donde no se puede hacer mucho para mejorar la situación) a la etapa de álgebra lineal (donde podemos atacarla con todo el arsenal de técnicas de preacondicionamiento de álgebra lineal numérica).

• Además, el cálculo cambia de "muchos muchos pasos baratos" a "unos pocos pasos costosos", lo que abre más oportunidades para el paralelismo en el nivel de subpaso (álgebra lineal).

Para obtener información básica sobre estos conceptos, recomiendo el libro "Optimización numérica" de Nocedal y Wright.

* Por supuesto, el método de Newton no lo ayudará con L1 u otras funciones de penalización de promoción de detección / dispersión comprimidas similares, ya que carecen de la suavidad requerida.

Hace poco aprendí esto yo mismo: el problema es la proliferación de puntos de silla en el espacio de alta dimensión, con el que los métodos de Newton quieren converger. Vea este artículo: Identificar y atacar el problema del punto de silla en la optimización no convexa de alta dimensión .

De hecho, la relación entre el número de puntos de silla y los mínimos locales aumenta exponencialmente con la dimensionalidad N.

Mientras que la dinámica de descenso del gradiente se repele desde un punto de silla de montar para reducir el error siguiendo las direcciones de curvatura negativa, ... el método de Newton no trata los puntos de silla de forma adecuada; Como se argumenta a continuación, los puntos de silla de montar se vuelven atractivos bajo la dinámica de Newton.

Una combinación de dos razones:

• El método de Newton atrae a los puntos de silla de montar;
• Los puntos de silla de montar son comunes en el aprendizaje automático o, de hecho, en cualquier optimización multivariable.

Mire la función

$$f=x^2-y^2$$

Si aplica el método de Newton multivariante , obtendrá lo siguiente.

$$\mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{H}f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n)$$

Consigamos el Hessian :

$$\mathbf{H}= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

$$\mathbf{H}= \begin{bmatrix} 2 & 0 \\[2.2ex] 0 & -2 \end{bmatrix}$$

Invierta:

$$[\mathbf{H} f]^{-1}= \begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix}$$

Obtenga el gradiente:

$$\nabla f=\begin{bmatrix} 2x \\[2.2ex] -2y \end{bmatrix}$$

Obtenga la ecuación final:

$$\mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_{n+1} = \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n -\begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix} \begin{bmatrix} 2x_n \\[2.2ex] -2y_n \end{bmatrix}= \mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_n - \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n = \begin{bmatrix} 0 \\[2.2ex] 0 \end{bmatrix}$$

Entonces, ves cómo el método de Newton te llevó al punto de silla en .$x=0,y=0$

En contraste, el método de descenso de gradiente no conducirá al punto de silla de montar. El gradiente es cero en el punto de silla de montar, pero un pequeño paso alejaría la optimización como se puede ver en el gradiente de arriba: su gradiente en la variable y es negativo.

Hiciste dos preguntas: ¿por qué no más personas usan el método de Newton y por qué tanta gente usa el descenso de gradiente estocástico? Estas preguntas tienen respuestas diferentes, porque hay muchos algoritmos que disminuyen la carga computacional del método de Newton pero a menudo funcionan mejor que SGD.

Primero: el Método de Newton lleva mucho tiempo por iteración y requiere mucha memoria. Como señala jwimberley, el Método de Newton requiere calcular la segunda derivada, , que es , donde es el número de características, mientras que calcular el gradiente, , es solo . Pero el siguiente paso es , que es para calcular. Entonces, aunque calcular el Hessian es costoso, invertirlo o resolver mínimos cuadrados a menudo es aún peor. (Si tiene características dispersas, las asíntotas se ven mejor, pero otros métodos también funcionan mejor, por lo que la dispersión no hace que Newton sea relativamente más atractivo).O ( N 2 ) N g O ( N ) H - 1 g O ( N 3$H$$O(N^2)$$N$$g$$O(N)$$H^{-1} g$$O(N^3)$

Segundo, muchos métodos, no solo el descenso de gradiente, se usan con más frecuencia que Newton; a menudo son imitaciones del método de Newton, en el sentido de que se aproximan a un paso de Newton a un costo computacional más bajo por paso pero requieren más iteraciones para converger. Algunos ejemplos:

• Debido al costo de invertir el hessiano, los métodos `` cuasi-Newton '' como BFGS aproximan el hessiano inverso , , observando cómo ha cambiado el gradiente en los últimos pasos.$H^{-1}$

• BFGS todavía requiere mucha memoria en configuraciones de alta dimensión porque requiere almacenar todo el Hessian inverso aproximado. La memoria limitada BFGS (L-BFGS) calcula la dirección del siguiente paso como el Hessian inverso aproximado multiplicado por el gradiente, pero solo requiere almacenar las últimas actualizaciones de gradiente; no almacena explícitamente el hessiano inverso aproximado.$O(N^2)$

• Cuando no desea tratar con aproximadas segundas derivadas, el descenso de gradiente es atractivo porque solo usa información de primer orden. El descenso de gradiente se aproxima implícitamente al hessiano inverso como la tasa de aprendizaje multiplicada por la matriz de identidad. Yo, personalmente, rara vez uso el descenso de gradiente: L-BFGS es tan fácil de implementar, ya que solo requiere especificar la función objetivo y el gradiente; tiene una mejor aproximación inversa de Hesse que la pendiente de gradiente; y porque el descenso de gradiente requiere ajustar la tasa de aprendizaje.

• A veces tiene una gran cantidad de observaciones (puntos de datos), pero podría aprender casi tan bien de una menor cantidad de observaciones. Cuando ese es el caso, puede utilizar "métodos por lotes", como el descenso de gradiente estocástico, que se desplaza utilizando subconjuntos de observaciones.

La dirección de descenso del gradiente es más barata de calcular, y realizar una búsqueda de línea en esa dirección es una fuente más confiable y constante de progreso hacia un óptimo. En resumen, el descenso de gradiente es relativamente confiable.

El método de Newton es relativamente costoso porque necesita calcular el Hessian en la primera iteración. Luego, en cada iteración subsiguiente, puede recalcular completamente el Hessian (como en el método de Newton) o simplemente "actualizar" el Hessian de la iteración anterior (en métodos cuasi-Newton) que es más barato pero menos robusto.

En el caso extremo de una función muy bien comportada, especialmente una función perfectamente cuadrática, el método de Newton es el claro ganador. Si es perfectamente cuadrático, el método de Newton convergerá en una sola iteración.

En el caso extremo opuesto de una función que se comporta muy mal, el descenso del gradiente tenderá a ganar. Escogerá una dirección de búsqueda, buscará esa dirección y, en última instancia, dará un paso pequeño pero productivo. Por el contrario, el método de Newton tenderá a fallar en estos casos, especialmente si intenta utilizar las aproximaciones cuasi-Newton.

Entre el descenso de gradiente y el método de Newton, hay métodos como el algoritmo Levenberg-Marquardt (LMA), aunque he visto los nombres confundidos un poco. La esencia es usar una búsqueda más informada por el gradiente de descenso cuando las cosas son caóticas y confusas, luego cambiar a una búsqueda más informada por el método de Newton cuando las cosas se vuelven más lineales y confiables.

Para grandes dimensiones, el Hessian es típicamente costoso de almacenar y resolver para una dirección puede ser costoso. También es más difícil de paralelizar.$Hd = g$

El método de Newton funciona bien cuando está cerca de una solución, o si el hessiano varía lentamente, pero necesita algunos trucos para lidiar con la falta de convergencia y la falta de definición.

A menudo se busca una mejora, en lugar de una solución exacta, en cuyo caso el costo adicional de Newton o métodos similares a Newton no está justificado.

Hay varias formas de mejorar lo anterior, como los métodos de métrica variable o región de confianza.

Como nota al margen, en muchos problemas, un problema clave es el escalado y el Hessian proporciona excelente información de escalado, aunque a un costo. Si uno puede aproximarse al Hessian, a menudo puede mejorar considerablemente el rendimiento. Hasta cierto punto, el método de Newton proporciona la "mejor" escala en que es afín invariante.

Existen muchas dificultades con respecto al uso del método de Newton para SGD, especialmente:

• necesita una matriz de Hesse: ¿cómo estimarla, por ejemplo, a partir de gradientes ruidosos con una precisión suficiente a un costo razonable?

• Full Hessian es demasiado costoso, más bien necesitamos algunas restricciones, por ejemplo, a un subespacio (¿qué subespacio?),

• necesita , lo que es costoso y muy inestable para la estimación ruidosa; puede ser borroso alrededor de invirtiendo hasta el infinito,$H^{-1}$$\lambda=0$

• El método de Newton atrae directamente a un punto cercano con gradiente cero ... que generalmente es una silla de montar aquí. ¿Cómo repelerlos en su lugar? Por ejemplo , Newton sin silla de montar invierte las direcciones de curvatura negativas, pero requiere el control de signos de valores propios,

• sería bueno hacerlo en línea: en lugar de hacer muchos cálculos en un solo punto, intente dividirlo en muchos pasos pequeños para explotar más información local.

Podemos pasar del 1er orden al 2do orden en pequeños pasos, por ejemplo, agregando una actualización de solo 3 promedios al método de impulso, simultáneamente podemos ajustar la parábola en su dirección para una elección más inteligente del tamaño del paso ... Modelado de segundo orden en un subespacio de baja dimensión. can todavía puede usar las coordenadas restantes para el descenso de gradiente simultáneo.