Supongamos que un diferenciable, convexo función de $F(x)$ existe. A continuación, $b = a - \gamma\bigtriangledown F(a)$ implica que el $F(b) <= F(a)$ $\gamma$ es elegido correctamente. El objetivo es encontrar el óptimo $\gamma$ a cada paso. En mi libro, con el fin de hacer esto, el libro de texto dice que uno debe minimizar $G(\gamma)=$ $F(x-\gamma\bigtriangledown F(x))$ para $\gamma$. También se dice que debe ser minimizado a través de una búsqueda en línea. Mi pregunta es ¿por qué no puede esta función se minimizd por simple cálculo? No estoy seguro de lo que significa realizar una búsqueda en línea en esta función. También estoy seguro de por qué queremos minimizar esta función para encontrar el óptimo tamaño de paso.
Respuestas
¿Demasiados anuncios?
Se están ya utilizando el cálculo cuando usted realiza una búsqueda de degradados en el primer lugar. En algún momento, usted tiene que parar el cálculo de los derivados y empezar a descender! :-)
Con toda seriedad, a pesar de que: lo que está describiendo es la línea exacta de la búsqueda. Es decir, usted realmente quiere encontrar el minimizando el valor de $\gamma$, $$\gamma_{\text{best}} = \mathop{\textrm{arg min}}_\gamma F(a+\gamma v), \quad v = -\nabla F(a).$$ Es muy raro, y probablemente fabricado, en el caso de que te permite calcular de manera eficiente $\gamma_{\text{best}}$ analíticamente. Es mucho más probable que usted va a tener que realizar algún tipo de gradiente o de Newton descenso en $\gamma$ sí mismo para encontrar $\gamma_{\text{best}}$.
El problema es que si usted hace la matemáticas en esto, usted va a terminar teniendo para el cálculo del gradiente $\nabla F$ en cada iteración de esta línea de búsqueda. Después de todo: $$\frac{d}{d\gamma} F(a+\gamma v) = \langle \nabla F(a+\gamma v), v \rangle$$ Mire cuidadosamente: el gradiente $\nabla F$ tiene que ser evaluado en cada uno de los valores de $\gamma$ lo intenta.
Eso es un uso ineficiente de lo que probablemente será el más caro de computación en su algoritmo! Si estás calcular el gradiente de todos modos, la mejor cosa a hacer es el uso que se mueva en la dirección que indica que usted se mueva---no permanecer pegado a lo largo de una línea.
Lo que usted quiere en la práctica, es barato para calcular un aceptable $\gamma$. La forma más común de hacer esto es un retroceso de la línea de búsqueda. Con esta estrategia, usted comienza con un paso inicial de tamaño de $\gamma$---por lo general un pequeño aumento en el último paso de tamaño que se establecieron en. A continuación, comprobar para ver si el punto de $a+\gamma v$ es de buena calidad. Una prueba común es el Armijo-Goldstein condición $$F(a+\gamma v) \leq F(a) - c \gamma \|\nabla F(a)\|_2^2$$ para algunos $c<1$. Si el paso pasa esta prueba, seguir adelante y tomar---no pierdas el tiempo tratando de ajustar su tamaño de paso más. Si el paso es demasiado grande---por ejemplo, si $F(a+\gamma v)>F(a)$---a continuación, esta prueba va a fallar, y que debe reducir su tamaño de paso hacia abajo (es decir, la mitad) e inténtelo de nuevo.
Esto es generalmente mucho más barato que hacer una exacta línea de búsqueda.
He encontrado un par de casos específicos en los que una línea exacta de la búsqueda puede ser calculada de forma más barata de lo que se describe arriba. Esto implicó la construcción de una fórmula simplificada para $F(a+\gamma v)$ , permitiendo que los derivados $\tfrac{d}{d\gamma}F(a+\gamma v)$ ser calculada de forma más barata que el gradiente completo $\nabla F$. Un caso concreto es el cómputo de la analítica en el centro de un lineal de la matriz de la desigualdad. Pero incluso en ese caso, que en general fue mejor en general que acaba de hacer backtracking.
Shabaz
Puntos
403
Hay una buena discusión de esto en el capítulo 10 de Recetas Numérica. Las versiones antiguas de internet son libres.
Tienes razón en que si usted tiene $F$ en una simple forma suficiente, usted puede minimizar $\gamma$ por cálculo. Usted podría incluso ser capaz de encontrar el mínimo directamente, sin necesidad de iteración. A menudo, usted no tiene que en esa forma. $x$ $\bigtriangledown F(x)$ son los dos vectores y puede que no sea posible calcular $\bigtriangledown F(x)$ analíticamente pero se puede buscar un valor mínimo.
Lo que significa realizar una búsqueda en línea se oculta en el simbolismo. El valor de $G(\gamma)$ es, precisamente, el valor de $F$ a lo largo de una línea desde el punto actual $x$ en la dirección $\bigtriangledown F(x)$. Se debe recordar que de los parámetros de la línea en tres dimensiones: un punto más de una variable de veces un vector de dirección. La razón por la que hacen esto es porque este es el mejor punto a lo largo de esa línea. Se espera que el valor disminuirá a lo largo de esa dirección (debido a que usted ha elegido la pendiente, que es la dirección del descenso más), pero si usted va demasiado lejos va a empezar a aumentar de nuevo. ¿Por qué no parar en el fondo del valle y probar de nuevo?
Algunos de los métodos Numéricos de Recetas no necesitan a los cálculos de la gradiente. Ellos vienen con instrucciones para minimizar encima de otras maneras.
error404
Puntos
1
No a tu pregunta,
pero una adaptación tamaño de paso puede vencer a un constante $\gamma$,
y un $\gamma_i$ componente que puede vencer a un solo $\gamma$ para todos los componentes.
Ver RmsProp,
rmsprop.py
y Zeiler, ADADELTA: Una adaptación de la tasa de aprendizaje métodode 2012, 6p.
Pero tenga cuidado con recursiva / IIR !
