Supongo que esta es una cuestión básica y tiene que ver con la dirección de la gradiente de sí mismo, pero estoy buscando ejemplos donde 2º orden de los métodos (por ejemplo, BFGS) son más eficaces que la simple gradiente de la pendiente.
Respuestas
¿Demasiados anuncios?
He aquí un marco común para la interpretación de ambos gradiente de la pendiente y el método de Newton, que es, quizás, una forma útil de pensar la diferencia como un suplemento a @user777 la respuesta. (BFGS se aproxima al método de Newton; no voy a hablar de ella en particular aquí.)
Estamos minimizando la función de $f$, pero no sabemos cómo hacerlo directamente. En vez de eso, nos tomamos un local de aproximación a nuestro actual punto de $x$ y minimizar.
El método de Newton se aproxima a la función utilizando un segundo orden expansión de Taylor: $$ f(y) \aprox N_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y - x)^T \, \nabla^2 f(x) \, (y - x) ,$$ donde $\nabla f(x)$ indica el gradiente de $f$ en el punto de $x$ $\nabla^2 f(x)$ Hesse en $x$. Entonces los pasos a $\arg\min_y N_x(y)$ y se repite.
Gradiente de la pendiente, sólo tener el gradiente y no el de Hesse, no sólo puede hacer una aproximación de primer orden y minimizar los que, desde ya que @Hurkyl señaló que no tiene mínimo. En su lugar, se define un tamaño de paso de $t$ y paso a $x - t \nabla f(x)$. Pero tenga en cuenta que \begin{align} x - t \,\nabla f(x) &= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac{1}{2 t} \lVert y - x \rVert^2\right] \\&= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x)\right] .\end{align} Por lo tanto el gradiente de descenso minimiza una función $$G_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x).$$
Por lo tanto el gradiente de descenso es tipo de como usar el método de Newton, pero en lugar de tomar el segundo-orden de expansión de Taylor, se pretende que el de Hesse es $\tfrac1t I$. Esta $G$ a menudo es sustancialmente peor aproximación a $f$$N$, y por lo tanto el gradiente de descenso a menudo toma mucho peor pasos que el método de Newton. Esto es contrarrestado, por supuesto, por cada paso de la gradiente de la pendiente de ser mucho más barato para calcular que cada paso del método de Newton. Cual es mejor depende enteramente de la naturaleza del problema, su consumo de recursos computacionales, y sus requisitos de precisión.
Mirando @user777 el ejemplo de la minimización de una ecuación cuadrática $$ f(x) = \tfrac12 x^T a x + d^T x + c $$ por un momento, vale la pena señalar que esta perspectiva ayuda con la comprensión de ambos métodos.
Con el método de Newton, tendremos $N = f$, de modo que termina con la respuesta exacta (hasta el punto flotante de precisión de problemas) en un solo paso.
Gradiente de la pendiente, por otro lado, los usos $$ G_x(y) = f(x) + (x + d)^T y + \tfrac12 (x - y)^T \tfrac1t I (x-y) $$ cuyo plano tangente en $x$ es correcto, pero cuya curvatura es completamente equivocado, y de hecho arroja diferencias importantes en diferentes direcciones cuando los autovalores de a $A$ variar sustancialmente.
user777
Puntos
10934
Esencialmente, la ventaja de un segundo derivados método como el método de Newton es que no tiene la calidad de la cuadrática de la terminación. Esto significa que se puede minimizar una función cuadrática en un número finito de pasos. Un método de gradiente de descenso depende en gran medida el ritmo de aprendizaje, lo que puede causar la optimización a converger lentamente debido a que rebota en el óptimo, o divergen por completo. Estables las tasas de aprendizaje se pueden encontrar... pero relacionados con la computación de hesse. Incluso cuando se utiliza un estable la tasa de aprendizaje, usted puede tener problemas como la oscilación en torno a la óptima, es decir, que no siempre lleva a un "directo" o "eficiente" ruta de acceso hacia el mínimo. Así que se puede tomar de muchas iteraciones para terminar, incluso si usted está relativamente cerca de ella. BFGS y el método de Newton puede converger más rápidamente, incluso a pesar de que el esfuerzo computacional de cada paso es más caro.
A su solicitud de ejemplos: Supongamos que tenemos la función objetivo $$ F(x)=\frac{1}{2}x^Impuestos+d^Tx+c $$ El gradiente es $$ \nabla F(x)=Ax+d $$ y ponerlo en la empinada bajada forma constante tasa de aprendizaje $$ x_{k+1}= x_k-\alpha(Ax_k+d) = (I-\alpha)x_k-\alpha d. $$
Este será estable si las magnitudes de los vectores propios de a $I-\alpha A$ son de menos de 1. Podemos utilizar esta propiedad para mostrar que estable la tasa de aprendizaje satisface $$\alpha<\frac{2}{\lambda_{max}},$$ where $\lambda_{max}$ is the largest eigenvalue of $$. The steepest descent algorithm's convergence rate is limited by the largest eigenvalue and the routine will converge most quickly in the direction of its corresponding eigenvector. Likewise, it will converge most slowly in directions of the eigenvector of the smallest eigenvalue. When there is a large disparity between large and small eigenvalues for $$, gradient descent will be slow. Any $$ con esta propiedad se convergen lentamente mediante gradiente de la pendiente.
En el contexto específico de las redes neuronales, el libro de la Red Neuronal de Diseño tiene un poco de información sobre métodos de optimización numérica. La discusión anterior es una condensación de la sección 9-7.
Aksakal
Puntos
11351
En convexa de optimización que se aproxime a la función como el segundo grado del polinomio en el caso unidimensional: $$f(x)=c+\beta x + \alpha x^2$$
En este caso el de la segunda derivada $$\partial^2 f(x)/\partial x^2=2\alpha$$
Si usted sabe los derivados, entonces es fácil para obtener el siguiente cálculo para el óptimo: $$\text{guess}=-\frac{\beta}{2\alpha}$$
El multivariante caso es muy similar, sólo el uso de gradientes para los productos derivados.
