Varios métodos de optimización comunes
La mayoría de los problemas encontrados en el estudio y el trabajo se pueden modelar en un modelo de optimización para su solución. Por ejemplo, el algoritmo de aprendizaje automático que estamos aprendiendo ahora. La esencia de la mayoría de los algoritmos de aprendizaje automático es establecer una optimización. modelo, optimice la función objetivo (o función de pérdida) a través de métodos de optimización para entrenar el mejor modelo. Los métodos de optimización comunes (optimización) incluyen el método de descenso de gradiente, el método de Newton, el método cuasi-Newton, el método de gradiente de yugo, etc.
1. Descenso de gradiente
El método de descenso de gradiente es el método de optimización más antiguo, más simple y más utilizado. El método de descenso de gradiente es sencillo de implementar. Cuando la función objetivo es una función convexa, la solución del método de descenso de gradiente es una solución global. En general, no se garantiza que la solución sea la solución óptima global y el método de descenso de gradiente no es necesariamente el más rápido. La idea de optimización del método de descenso de gradiente es utilizar la dirección de gradiente negativo de la posición actual como dirección de búsqueda. Debido a que esta dirección es la dirección de descenso más rápida de la posición actual, también se denomina "método de descenso más pronunciado". Cuanto más cerca esté el método de descenso más pronunciado del valor objetivo, menor será el tamaño del paso y más lento será el progreso.
Desventajas del método de descenso de gradiente:
(1) La velocidad de convergencia se ralentiza cuando se acerca al valor mínimo
(2) Pueden ocurrir algunos problemas durante; Problema de búsqueda en línea recta;
(3) puede disminuir en forma de "zigzag".
En el aprendizaje automático, se han desarrollado dos métodos de descenso de gradiente basados en el método básico de descenso de gradiente, a saber, el método de descenso de gradiente estocástico y el método de descenso de gradiente por lotes.
Por ejemplo, para un modelo de regresión lineal (Logística Lineal), supongamos que la siguiente h(x) es la función a ajustar, J( ) es la función de pérdida, es el parámetro y el valor Se resuelve iterativamente. Finalmente sale la función h() que se va a instalar. Donde m es el número de muestras en el conjunto de entrenamiento y n es el número de características.
1) Descenso de gradiente por lotes (BGD)
(1) Encuentre la derivada parcial de J( ) para obtener el gradiente correspondiente a cada theta:
p >
(2) Dado que la función de riesgo debe minimizarse, cada parámetro se actualiza de acuerdo con la dirección negativa del gradiente:
(3) De la fórmula anterior, se puede observar que Esta es una solución óptima global, pero en cada paso de iteración, se deben utilizar todos los datos del conjunto de entrenamiento. Si m es grande, entonces es concebible que la velocidad de iteración de este método sea bastante lenta. Entonces, esto introduce otro método: el descenso de gradiente estocástico.
Para el método de descenso de gradiente por lotes, el número de muestras es m, x es un vector n-dimensional, y todas las m muestras deben incluirse en el cálculo en una iteración, y la cantidad de cálculo es una la iteración es m*n2.
2) Descenso de gradiente estocástico (SGD)
(1) La función de riesgo anterior se puede escribir de la siguiente forma La función de pérdida corresponde a cada muestra en el conjunto de entrenamiento La granularidad. , y el descenso de gradiente por lotes anterior corresponde a todas las muestras de entrenamiento:
(2) La función de pérdida de cada muestra se actualiza tomando la derivada parcial para obtener el gradiente correspondiente:
( 3) El descenso del gradiente estocástico se actualiza iterativamente una vez para cada muestra. Si el tamaño de la muestra es grande (por ejemplo, cientos de miles), solo se pueden usar decenas de miles o miles de muestras, y
Iterar. Para la solución óptima, en comparación con el descenso de gradiente por lotes anterior, una iteración requiere cientos de miles de muestras de entrenamiento. Si se itera 10 veces, las muestras de entrenamiento deben recorrerse 10 veces. Sin embargo, un problema asociado con SGD es que hay más ruido que BGD, por lo que SGD no avanza hacia la dirección de optimización general en cada iteración.
El descenso de gradiente estocástico solo utiliza una muestra para cada iteración, y la cantidad de cálculo para una iteración es n2. Cuando el número de muestras m es grande, la velocidad de una iteración del descenso de gradiente estocástico es mucho mayor que. el del método de descenso de gradiente por lotes. La relación entre los dos se puede entender así: el método de descenso de gradiente estocástico mejora la eficiencia de optimización general a costa de perder una pequeña parte de la precisión y aumentar un cierto número de iteraciones. El mayor número de iteraciones es mucho menor que el número de muestras.
Resumen del método de descenso de gradiente por lotes y del método de descenso de gradiente estocástico:
Descenso de gradiente por lotes: minimice la función de pérdida de todas las muestras de entrenamiento para que la solución final sea el máximo global. Las soluciones óptimas, es decir, resolver parámetros que minimizan la función de riesgo, son ineficientes para problemas de muestras a gran escala.
Descenso de gradiente estocástico: minimiza la función de pérdida de cada muestra. Aunque la función de pérdida obtenida en cada iteración no es hacia la dirección óptima global, la dirección general es hacia la solución óptima global. El resultado suele estar cerca de la solución óptima global, que es adecuada para situaciones de muestra de entrenamiento a gran escala.
2. Método de Newton y Métodos Cuasi-Newton
1) Método de Newton
El método de Newton es un método para resolver ecuaciones aproximadamente en el dominio de lo real y lo complejo. números. El método utiliza los primeros términos de la serie de Taylor de la función f? (x) para encontrar las raíces de la ecuación f? (x) = 0. La característica más importante del método de Newton es su rápida velocidad de convergencia.
Pasos específicos:
Primero, seleccione un x0 cercano al punto cero de la función f? (x) y calcule la f? (x 0) correspondiente y la pendiente tangente. f?'? (x 0) (aquí f'? representa la derivada de la función f ?). Luego calculamos la coordenada x de la intersección de la recta que pasa por el punto (x 0, f ? (x 0)) y tiene pendiente f ? (x 0) y el eje x? para encontrar la solución a la siguiente ecuación:
Llamamos a la coordenada x? del punto recién obtenido x 1. Por lo general, x 1 estará más cerca de la solución de la ecuación f ? x 0. Entonces ahora podemos comenzar la siguiente iteración con x 1. La fórmula de iteración se puede simplificar de la siguiente manera:
Se ha demostrado que si f ? ' es continua y el punto cero x a encontrar está aislado, entonces hay un área alrededor del punto cero x, como siempre que el valor inicial Si x 0 se encuentra en esta área adyacente, entonces el método de Newton debe converger. Y, si f ? ' ( x ) no es 0, entonces el método de Newton tendrá el rendimiento de convergencia cuadrada, esto significa que con cada iteración, los dígitos significativos del resultado del método de Newton se duplicarán. La siguiente figura es un ejemplo del proceso de ejecución del método de Newton.
Dado que el método de Newton se basa en la tangente de la posición actual para determinar la siguiente posición, el método de Newton también se denomina vívidamente "método de la tangente".
Acerca de la comparación de eficiencia entre el método de Newton y el método de descenso de gradiente:
Esencialmente, el método de Newton es una convergencia de segundo orden y el descenso de gradiente es una convergencia de primer orden, por lo que el método de Newton es más rápido. . Para decirlo de manera más simple, por ejemplo, si desea encontrar el camino más corto hasta el fondo de una cuenca, el método de descenso de gradiente solo elige la dirección con la pendiente más alta desde su posición actual y da un paso a la vez, no. sólo considerará si la pendiente es lo suficientemente grande, sino también si la pendiente aumentará después de dar un paso. Por lo tanto, se puede decir que el método de Newton puede ver más allá que el método de descenso de gradiente y llegar al fondo más rápido. (El método de Newton tiene una visión más amplia, por lo que toma menos desvíos; por el contrario, el método de descenso de gradiente solo considera el óptimo local y no tiene un pensamiento global).
Según la explicación en wiki, geométricamente hablando, El método de Newton utiliza una superficie cuadrática para ajustarse a la superficie local en su ubicación actual, mientras que el método de descenso de gradiente utiliza un plano para ajustarse a la superficie local actual. En circunstancias normales, el ajuste de una superficie cuadrática será más preciso que el de un plano. Bien, entonces la ruta de descenso seleccionada por el método de Newton será más consistente con la ruta de descenso óptima real.
Nota: El rojo es la ruta iterativa del método de Newton y el verde es la ruta iterativa del método de descenso de gradiente.
Resumen de las ventajas y desventajas del método de Newton:
Ventajas: convergencia de segundo orden, velocidad de convergencia rápida
Desventajas: el método de Newton es un algoritmo iterativo; , Cada paso Ambos necesitan resolver la matriz inversa de la matriz de Hesse de la función objetivo, y el cálculo es relativamente complicado.
2) Métodos Quasi-Newton
El método Quasi-Newton es uno de los métodos más eficaces para resolver problemas de optimización no lineal. Fue desarrollado por el Laboratorio Nacional Argonne de Estados Unidos. en la década de 1950. Propuesto por el físico de laboratorio W.C. El algoritmo diseñado por Davidon fue considerado uno de los inventos más creativos en el campo de la optimización no lineal en ese momento. Pronto, R. Fletcher y M. J. D. Powell confirmaron que este nuevo algoritmo era mucho más rápido y confiable que otros métodos, haciendo que el tema de la optimización no lineal avanzara a pasos agigantados de la noche a la mañana.
La idea esencial del método cuasi-Newton es mejorar la desventaja del método de Newton de que necesita resolver la matriz inversa de la matriz compleja de Hesse cada vez. Utiliza una matriz definida positiva para. aproximar la inversa de la matriz de Hesse, simplificando así la complejidad de la operación. El método cuasi-Newton, al igual que el método de descenso más pronunciado, sólo requiere conocer el gradiente de la función objetivo en cada iteración. Al medir el cambio de gradiente, se construye un modelo de la función objetivo que es suficiente para producir una convergencia superlineal. Este tipo de método es significativamente mejor que el método de descenso más pronunciado, especialmente para problemas difíciles. Además, como el método cuasi-Newton no requiere información sobre la segunda derivada, a veces es más eficaz que el método de Newton. Hoy en día, el software de optimización incluye una gran cantidad de algoritmos cuasi-Newton para resolver problemas de optimización sin restricciones, con restricciones y a gran escala.
Pasos específicos:
La idea básica del método cuasi-Newton es la siguiente. Primero, construya el modelo cuadrático de la función objetivo en la iteración actual xk:
Aquí Bk es una matriz definida positiva simétrica, por lo que tomamos la solución óptima de este modelo cuadrático como dirección de búsqueda y obtenemos la nueva Punto de iteración:
Entre ellos, requerimos el tamaño de paso ak para satisfacer la condición de Wolfe. Esta iteración es similar al método de Newton, excepto que se utiliza la matriz aproximada de Hesse Bk en lugar de la matriz real de Hesse. Por tanto, el aspecto más crítico del método cuasi-Newton es la actualización de la matriz Bk en cada iteración. Ahora supongamos que se obtiene una nueva iteración xk+1 y se obtiene un nuevo modelo cuadrático:
Utilizamos la información del paso anterior tanto como sea posible para seleccionar Bk. Específicamente, requerimos
y así obtenemos
Esta fórmula se llama ecuación secante. Los métodos cuasi-Newton comúnmente utilizados incluyen el algoritmo DFP y el algoritmo BFGS.
Enlace original: [Matemáticas] Varios métodos de optimización comunes - Notas de la encuesta - Blog Park