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

132

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?

Fei Yang
fuente
24
Para redes neuronales, la sección "8.6 Métodos aproximados de segundo orden" de deeplearningbook.org ofrece una buena descripción general. En resumen "Más allá de los desafíos creados por ciertas características de la función objetivo, como los puntos de silla de montar, la aplicación del método de Newton para entrenar grandes redes neuronales está limitada por la importante carga computacional que impone". Existen alternativas que intentan obtener algunas de las ventajas del método de Newton mientras esquivan los obstáculos computacionales, pero tienen sus propios problemas.
Franck Dernoncourt
1
vea esta pregunta y comentarios relacionados, stats.stackexchange.com/questions/232305/…
Haitao Du
1
Tenga en cuenta que los otros comentarios tienen una aplicabilidad más amplia al aprendizaje automático más allá del simple "aprendizaje profundo". Sin embargo, aunque todos los problemas de ML pueden tender a ser "grandes datos", no todos los problemas de ML son necesariamente "grandes características" (es decir, muchos parámetros para ajustar), aunque el aprendizaje profundo siempre lo es.
GeoMatt22
1
Vale la pena señalar que en el aprendizaje automático fuera del aprendizaje profundo, L-BFGS (que, más o menos, se aproxima al método de Newton) es un algoritmo de optimización bastante común.
Dougal
2
El método de Newton asume la convexidad, los problemas modernos de LD (redes neutrales) no son probables cerca de la convexidad, aunque es cierto que allí hay un área de investigación abierta. Por lo tanto, el método de Newton es probablemente un estimador tan malo como lineal en cualquier lugar, pero cerca del punto de cálculo. Probablemente gane muy poco por un aumento cuadrático en la computación. Dicho esto, una conferencia reciente en Berkeley tuvo un presentador que continuó mostrando progreso en el uso de métodos de segundo orden, por lo que no está muerto de ninguna manera.
David Parks

Respuestas:

95

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 2NN2

jwimberley
fuente
55
Vale la pena señalar que (las cosas basadas en) el método de Gauss-Newton son probablemente más comunes. Esta es una especialización de Newton para mínimos cuadrados no lineales.
GeoMatt22
44
No llamaría a Gauss-Newton una especialización de Newton para mínimos cuadrados no lineales. Yo lo llamaría una aproximación bastarda de Newton para mínimos cuadrados no lineales, que utiliza una aproximación hessiana más inexacta, cuanto mayores son los residuos en las ecuaciones ajustadas y, en consecuencia, más lejos está el argumento de la óptima.
Mark L. Stone
1
@ MarkL.Stone justo, estaba tratando de no entrar en tecnicismos :) Es cierto que los métodos de estilo Gauss-Newton intentan "falsificar" el segundo orden con solo la información del primer orden. Personalmente, nunca he usado los métodos de Newton para la optimización, solo Gauss-Newton (o LM, o ~ UKF similar) o los métodos DFO-SQP (por ejemplo, BOBYQA ). "Optimidad" es una pregunta difícil, diría ... para un problema de ML, frente a un problema de optimización de diseño de ingeniería, la confiabilidad / información de un "Hessian local" puede ser dudosa. ¿Quizás el DFO-SQP no local es ~ "Newton estocástico"? (por ejemplo, "en línea")
GeoMatt22
1
Pensándolo bien, los enfoques DFO-SQP tienden a ser no locales en el espacio de parámetros , en lugar de lotes de datos. El UKF puede ser el más cercano en sabor al "Newton estocástico", ya que está en línea con memoria limitada ... pero efectivamente asume un hessiano definido positivo (es decir, Gaussiano aprox.).
GeoMatt22
1
En realidad, esa es una razón engañosa, ya que hay métodos de segundo orden como CG que no requieren calcular el hessian. k iteraciones de CG solo costarán kN. Es correcto que CG teóricamente coincidiría con Newton solo en k = N, pero realmente no necesita tantas iteraciones.
user25322
40

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.

Nick Alger
fuente
2
Creo que estamos en un acuerdo violento entre nosotros, no con todos los demás.
Mark L. Stone
1
Es como comparar si el Reino Unido o los Estados Unidos producen mejores matemáticos de investigación comparando las habilidades matemáticas de los que abandonan la escuela secundaria de drogadictos de 26 años, en lugar de comparar el escalón más alto de estudiantes graduados en matemáticas que salen de las mejores escuelas de cada país. El documento está firmado, sellado y entregado, nadie, y quiero decir que nadie lo está cambiando o retirando ahora. Incrogable.
Mark L. Stone
3
@ MarkL.Stone Parece que ocurrió una conversación aquí y se eliminó mientras estaba fuera. De todos modos, creo que tienes razón en que estamos de acuerdo entre nosotros y con nadie más. Supongo que esto es de esperar en función de nuestros antecedentes en comparación con las otras personas aquí. Como probablemente espere, no pienso mucho en el documento vinculado. Por otro lado, creo que el múltiple método de Newton de Riemann , donde se dispara una trayectoria geodésica en una dirección de búsqueda de Newton, es una técnica muy prometedora para problemas muy difíciles.
Nick Alger
2
¿Cómo lidiarías con un gran conjunto de entrenamiento? Si tiene, por ejemplo, 1 millón de muestras de entrenamiento, solo evaluar el objetivo de optimización actual requiere probar 1 millón de muestras. Y debe hacerlo varias veces durante una búsqueda de línea. Entonces, para cuando haya completado 1 paso de Newton, el Descenso de gradiente estocástico habrá realizado algunos millones de actualizaciones.
nikie
2
Nick y @ MarkL.Stone: ¿Estás hablando esencialmente de este enfoque ? Esto es algo que fue brevemente popular en el aprendizaje profundo, especialmente para redes recurrentes, pero desde entonces ha caído en desgracia, supongo porque simplemente no funcionó mucho mejor empíricamente que los métodos de gradiente adaptativo. Si simplemente estuvieran haciendo algo mal, y usted arregla lo que sea y demuestre que generalmente supera a la variante SGD estándar actual Adam, podría tener un gran impacto: el documento de Adam ha tenido 1345 citas en dos años ...
Dougal
33

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.

Cam.Davidson.Pilon
fuente
3
¿Podría agregar alguna explicación de por qué esto es así? En teoría, el método de Newton realiza un descenso gradiente ponderado con pesos "óptimos" para cada uno de los vectores propios.
nbubis
44
Lo que dice ese artículo sobre los métodos de Newton "queriendo" converger en puntos de silla de montar solo es cierto para las implementaciones basura del método de Newton.
Mark L. Stone
El documento reparameteriza el problema en términos de valores propios y vectores propios, y lo utiliza para mostrar que el descenso del gradiente se aleja de un punto de silla de montar: se mueve hacia el punto de silla de montar en la dirección de los vectores electrónicos negativos, pero se aleja en la dirección de vectores electrónicos positivos, por lo que finalmente deja el punto de silla de montar. Newton, por otro lado, no tiene tal garantía.
Elizabeth Santorella
Sin embargo, el nuevo algoritmo que defienden en este documento es (una variante del) método de Newton. Es básicamente el método de Newton para las direcciones de curvatura positiva y el método de Newton negativo para las direcciones de curvatura negativa.
Nick Alger
26

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=x2y2
ingrese la descripción de la imagen aquí

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

xn+1=xn[Hf(xn)]1f(xn)

Consigamos el Hessian :

H=[2fx122fx1x22fx1xn2fx2x12fx222fx2xn2fxnx12fxnx22fxn2].

H=[2002]

Invierta:

[Hf]1=[1/2001/2]

Obtenga el gradiente:

f=[2x2y]

Obtenga la ecuación final:

[xy]n+1=[xy]n[1/2001/2][2xn2yn]=[xy]n[xy]n=[00]

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.

Aksakal
fuente
1
Gracias a ti, realmente entendí cómo funciona este método de la A a la Z, así que muchas gracias por este claro ejemplo.
greenoldman
¿Cuál sería el punto favorito aquí?
Ben
14

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 )HO(N2)NgO(N)H1gO(N3)

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.H1

  • 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(N2)

  • 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.

Elizabeth Santorella
fuente
(+1) Vale la pena señalar que L-BFGS es del mismo orden de complejidad que el descenso de gradiente en cuanto a la cantidad de parámetros. Este no es el caso de BFGS. Por lo tanto, no es solo la parte de memoria limitada de L-BFGS lo que lo hace atractivo.
Cliff AB
12

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.

Nat
fuente
3
Chico, debes usar implementaciones terribles de Newton y Cuasi-Newton. Si se usa con un Hessian definido no positivo, use regiones de confianza o realice una búsqueda lineal a lo largo de las direcciones de curvatura negativa. Si es así, son MÁS confiables que el descenso más pronunciado (es decir, el descenso de gradiente con búsqueda de línea o región de confianza). En resumen, el descenso gradual es mucho menos confiable que un método Cuasi-Newton implementado adecuadamente, que es menos confiable que un método Newton implementado adecuadamente. Sin embargo, el tiempo de cálculo y los requisitos de memoria por iteración son una cuestión diferente.
Mark L. Stone
44
Creo que te refieres a la función perfectamente cuadrática. Es decir, el método de Newton converge en una sola iteración con una función objetivo cuadrática, que tiene un gradiente lineal.
Elizabeth Santorella
1
@ElizabethSantorella: ¡Sí, tienes razón! Actualicé la respuesta.
Nat
2
La ventaja de un método de Newton bien implementado y protegido sobre el descenso más pronunciado aumenta la función más desagradable, más mal acondicionada y más no convexa. Si está minimizando la función cuadrática de mejor comportamiento que existe, teniendo un término cuadrático , es decir, Hessian = matriz de identidad, entonces el descenso más pronunciado está bien, y es el mismo que el método de Newton. 1/2xTx
Mark L. Stone
1
He presentado mi caso. Si quieres pensar en el descenso más empinado, el descenso en gradiente es maravilloso, especialmente en funciones mal comportadas, ese es tu problema. Noquearse.
Mark L. Stone
7

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.

cobre.hat
fuente
0

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,H1λ=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.

Jarek Duda
fuente