En problemas de optimización matemática, a menudo se usa la primera derivada. ¿Por qué no el segundo, o derivados de orden superior?

Respuesta corta:
Existe una compensación entre un cálculo de un solo paso (tiempo + memoria) y el número de pasos necesarios para que un optimizador alcance un nivel óptimo (denominado tasa de convergencia). Los métodos de primer orden son más baratos en el cálculo de un solo paso, pero necesitan muchos más pasos para converger. Sin embargo, en una configuración moderna a gran escala, el cálculo más económico de un solo paso a menudo es más preferido.

Respuesta más larga:
Como dijo Justin Rising, si tiene una función que depende de muchas variables, el cálculo del hessian se está volviendo costoso (cuadrático en el número de variables; matriz de Hesse), mientras que el gradiente sigue siendo bastante barato (lineal en el número de variables )

Sin embargo, no hay blanco y negro, y hay muchos métodos entre el Descenso de degradado (un representante de primer orden) y el método de Newton (un representante de segundo orden). El propósito principal de usar Hessian en el método de Newton es obtener una información más rica sobre la curvatura de un espacio de parámetros y, por lo tanto, acelerar la convergencia del método de optimización. En particular para evitar que el optimizador ‘zigzaguee’ (Fig. 4.2 en Método de descenso más pronunciado). Como puede ver, aquí está la compensación entre los métodos de primer y segundo orden. Más precisamente, entre el costo de calcular un solo paso (lineal versus cuadrático) y su tasa de convergencia (el método de Newton tiene una tasa de convergencia mucho mejor). En la práctica, a veces es difícil decir a priori qué método tiene un tiempo total más bajo para encontrar un óptimo y necesita experimentar con varios métodos.

Sin embargo, dicha ‘información de curvatura’ también se puede incorporar de muchas otras maneras (más baratas), incluidos los métodos Cuasi Newton donde Hessian se aproxima a menudo por una matriz de bajo rango (método Cuasi-Newton), métodos basados ​​en el momento, trucos para elegir la tasa de aprendizaje, conjugado método de gradiente (método de gradiente conjugado), preacondicionamiento (preacondicionador), métodos de Hesse gratuitos donde muestra directamente los resultados de una aplicación de matriz de Hesse a un vector, métodos que se retuercen para resolver algunos problemas de optimización particulares, etc. Algunos de ellos Muktabh Mayank tiene ya mencionado.

El siguiente libro discute muchos de los métodos antes mencionados: Optimización numérica (Serie Springer en Investigación de Operaciones e Ingeniería Financiera): Jorge Nocedal, Stephen Wright: 9780387303031: Amazon.com: Libros

No creo que sea una afirmación totalmente correcta. Si está hablando de la optimización de Machine Learning (optimización de función convexa), se utilizan derivados de segundo orden.
Hessian Free Optimization es un método para resolver extremos usando derivadas de segundo orden.
Muchos otros métodos de cuasi-Newton de la primera derivada, como BFGS de memoria limitada, también son aproximaciones a la segunda derivada (que a menudo es difícil de calcular en el caso de las matrices).
Sin embargo, los métodos basados ​​en derivadas de primer orden son más comunes en comparación con los de segundo orden, ya que generalmente funcionan bien en comparación con los métodos basados ​​en derivadas de segundo orden y son fáciles de implementar. Los métodos basados ​​en el momento dan una inercia al SGD. El gradiente acelerado de Nesterov es un método que utiliza correcciones basadas en la primera derivada para converger rápidamente (las encuentro como los filtros de Kalman). Otra forma es variar la tasa de aprendizaje en lugar de usar derivadas de segundo orden, estos algoritmos parecen ser los convergentes más rápidos a partir de ahora (ADAGrad / ADADelta).

¡Todas las respuestas aquí son geniales! Solo mis dos centavos en el contexto del aprendizaje automático es que las llamadas funciones de pérdida dependen más de los datos, lo que hace que la función objetivo de las optimizaciones numéricas. Por supuesto, como otros lo dijeron, calcular los derivados de arpillera y de orden superior son bastante caros debido a la enorme cantidad de disponibilidad de datos. Creo que una razón importante por la que se prefieren los gradientes estocásticos es que la optimización está impulsada por los datos. Cuando calcula el hessian que lleva la estructura de toda la función objetivo, la contribución de un único punto de datos se vuelve insignificante en algún sentido. Ahora, este es un problema en la mayoría de los casos, especialmente si la función objetivo no es convexa. ¿Por qué? Porque intuitivamente significa que confiamos más en la formulación (en cierto sentido) que en los datos en sí, lo que significa que entendemos muy bien el problema (en teoría), que rara vez es el caso en el aprendizaje automático. Por ejemplo, hay muchos algoritmos y formulaciones para la factorización matricial, pero elegir uno para ir en general no es fácil. La jungla de factorización de matriz avanzada – igorcarron2

(No puedo respaldar mi respuesta con referencias, pero esta razón tiende a tener mucho sentido para mí porque cuando les pregunto a mis amigos por qué no usan el descenso de gradiente, la respuesta siempre es muy empírica, lo que no me resulta atractivo. Otra razón extraña es que escuchar es que el método de gradiente estocástico nos ayuda a omitir muchos mínimos locales, lo que también suena mal en teoría porque ¡ningún optimizador numérico querría hacer eso de 90 de cada 100 casos!)

Las primeras derivadas lo ayudan a encontrar máximos y mínimos porque si una función diferenciable tiene un máximo o un mínimo, su primera derivada será 0.

Sin embargo, lo contrario no siempre se cumple. A veces, una función tendrá una primera derivada de 0 en alguna parte, pero no hay máximo o mínimo allí. Por lo general, puede distinguir tres casos (máximo, mínimo o ninguno de los dos) observando el valor de la segunda derivada. Eso se llama la segunda prueba derivada.

Es concebible que la segunda prueba de derivada no haga la distinción, y en principio podría examinar las terceras derivadas, pero tal situación en la que tendría que hacerlo raramente si alguna vez sucede para aplicaciones reales.

La primera derivada, conocida como jacobiana, se usa para definir el cambio de una función con respecto a algunos parámetros. Entonces, cuando la optimización busca un mínimo local / global, debemos usar la propiedad “cambiante” de la función. En el descenso de gradiente, se utiliza la función jacobiana de pérdida. Y menos se usa porque los algoritmos de descenso funcionan en el concepto de disminución en cada nueva iteración hasta alcanzar el mínimo. Por ejemplo: f (x1)> f (x2)> f (x3) … y así sucesivamente.

Pero, una cosa, ¿quién te dijo que la segunda derivada no se usa en la optimización? La segunda derivada, la arpillera, es una propiedad importante de la convexidad. Define los criterios para ser convexos para cualquier función diferenciable, por ejemplo: f (x) = – log (x).

Finalmente, no tengo idea de derivados de orden superior. Le recomendaría que lea los capítulos 2º y 3º de Optimización convexa de Stephen Boyd de Stanford. ¡Es un libro asombroso!

Una de las principales razones para usar solo derivadas de primer orden es probablemente el costo de cálculo, por ejemplo, para algunos modelos de aprendizaje automático.

El primer orden es como el cálculo [matemático] O (N) [/ matemático],

[matemáticas] [\ frac {\ partial f} {\ partial x_1}, \ \ cdots, \ \ frac {\ partial f} {\ partial x_n}] [/ math]

pero el segundo orden es como el cálculo [matemático] O (N ^ 2) [/ matemático], es decir, la matriz de Hesse La matriz de Hesse – Wikipedia:

[matemáticas] {\ displaystyle {\ mathbf {H}} = {\ begin {bmatrix} {\ dfrac {\ partial ^ {2} f} {\ partial x_ {1} ^ {2}}} y {\ 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}}} y {\ 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}}.} [/ math]

Ejemplo CS231n Redes neuronales convolucionales para reconocimiento visual: la red VGG tiene parámetros 138M, O (138M) podría ser factible, pero O (138M * 138M) es demasiado complejo.

Además, tenemos que calcular la inversión.

(que puede ser [matemática] O (N ^ 3 [/ matemática] [matemática]) [/ matemática] Complejidad computacional de las operaciones matemáticas – Wikipedia)

de esta matriz de Hesse para realizar el descenso de gradiente de segundo orden, que también se llama método de Newton en optimización – Wikipedia:

[matemáticas] {\ displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} – [\ mathbf {H} f (\ mathbf {x} _ {n})] ^ {- 1} \ nabla f (\ mathbf {x} _ {n}), \ n \ geq 0.} [/ Math]

Además, como se indicó en otra respuesta, el descenso de gradiente usando el primer orden, aunque sea más lento que el segundo orden, puede resolver problemas prácticos. El entrenamiento en un escritorio de GPU durante 24 horas es más factible para la mayoría de las personas que el entrenamiento en supercomputadora durante 1 hora.

PD: en el ejemplo de VGG, en realidad puede ser inferior a 138M * 138M, porque los parámetros de diferentes capas pueden no necesitar ser calculados juntos, pero la idea es más o menos la misma: complejidad lineal versus complejidad cuadrada.

En un problema de alta dimensión, calcular el hessiano de la función relevante es a menudo muy costoso y numéricamente inestable. Es mejor usar otros métodos que no tengan esos problemas.

A grandes rasgos, los problemas de optimización están formulados para utilizar las mejores fuentes de información disponibles mientras se eliminan tantos datos / contextos extraños como sea posible. Para los problemas de nivel de cálculo elemental, la introducción de los multiplicadores de Lagrange utiliza la primera información derivada de manera muy efectiva para clasificar los puntos críticos y extremos. (Vea una versión rápida de los detalles en Wikipedia.) La información sobre derivados más altos está reservada para probar qué tipo de puntos críticos se han encontrado.

En optimizaciones restringidas a gran escala, incluso después de que las reformulaciones perspicaces exploten las matemáticas del contexto, generalmente hay millones de pasos entre un punto de partida y una solución. En tal caso, desea que cada paso de iteración funcione con los datos y cálculos más simples posibles. La representación estable y escasa de las primeras derivadas es más fácil que llevar el equipaje de las segundas derivadas estimadas. (Esta es un área donde los profesionales han probado una amplia variedad de enfoques alternativos, por lo que existe una sólida experiencia que guía qué enfoques funcionan mejor en qué circunstancias).

En una ruta de planeo diferente, si la configuración del problema satisface ciertas condiciones de intercambio, los pasos de optimización local siempre conducen a una optimización global. Esta es una situación maravillosa cuando ocurre, así que, por supuesto, esas situaciones se denominan “greedoides” porque pueden ser optimizadas por un algoritmo codicioso. Esto se usa, por ejemplo, para encontrar un árbol de expansión mínimo ponderado usando el algoritmo de Kruskal. Ninguno de los problemas derivados deriva en los cálculos de la solución explícitamente.

La optimización es un tema grande y complejo. No esperes que las primeras generalizaciones que pienses sean guías confiables para todo este tema.

Se usa * en optimización matemática, no se usa en aprendizaje profundo porque la complejidad cuadrática y cúbica de la computación y el almacenamiento de la matriz de Hesse, respectivamente, es computablemente insoluble.

El método de Newton sigue siendo el rey para la mayoría de los problemas de optimización, suponiendo que tenga cierta estructura en los datos y que pueda explotar la escasez de datos. Además, hay una serie de métodos cuasi-Newton en los que solo aproxima el Hessian y trabaja más rápido que el método de Newton.

El aprendizaje profundo es probablemente la única disciplina donde las optimizaciones de segundo orden no se usan tanto (al menos no todavía), y eso es por varias razones:

• El problema es altamente no convexo.
• Los optimizadores basados ​​en la pendiente del gradiente parecen funcionar muy bien en la práctica (realmente no debería, pero afortunadamente, funciona bien para nosotros).
• No es sencillo usar la propagación hacia atrás para calcular las Hesse. Vanilla backprop encuentra a los jacobianos por ti, pero no a los hessianos.
• Probablemente la razón más importante, en la práctica, las personas usan mini lotes en lugar del lote completo (más rápido y en general se generaliza mejor), y a partir de este momento (que yo sepa), no sabemos cómo hacer optimizadores de segundo orden trabajar con mini lotes.

Con respecto a la optimización matemática directa de una función, puede encontrar el mínimo o el máximo con la primera derivada. Si desea, por otro lado, encontrar dónde va la función de aumentar cada vez más a aumentar de manera decreciente (piense cuánto se curva), o disminuyendo de manera decreciente a disminuir cada vez más, como encontrar el punto de inflexión en el crecimiento logístico, deberá usa la segunda derivada.

A menudo, los derivados de orden inferior son lo que necesita para resolver un problema. Si el problema requiere que use derivados de orden superior, los usaría. Simplemente sucede que a menudo la primera derivada es suficiente.

Considere un problema de optimización no convexo a gran escala, donde desea encontrar los parámetros óptimos para una red neuronal con mil millones de parámetros. Usar un método de segundo orden requeriría tomar el inverso de una matriz de billones * billones. Tomar una inversa de una matriz tan grande sería muy costoso de realizar en términos de complejidad de tiempo y complejidad de espacio.

Esto está un poco fuera del campo izquierdo, pero en muchos sistemas físicos, la segunda derivada es una constante. (Por ejemplo, pocas cosas experimentan naturalmente ‘tirón’ continuo (x -> dx / dt ‘velocidad’ -> d2x / dt2 ‘aceleración’ -> d3x / dt3 ‘tirón’))

Debido a la convexidad de la función. Si tienes una función convexa. Entonces la derivada da un mínimo local y el mínimo local es un mínimo global. Las funciones objetivas en el aprendizaje automático son generalmente convexas y utilizan el descenso de gradiente