Hispanopedia Wiki
Articulo de referencia

BFGS de memoria limitada

El algoritmo BFGS de memoria limitada ( L-BFGS o LM-BFGS ) es un algoritmo de optimización perteneciente a la colección de métodos cuasi-Newton que aproxima el algoritmo Broyden...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo BFGS de memoria limitada ( L-BFGS o LM-BFGS ) es un algoritmo de optimización perteneciente a la colección de métodos cuasi-Newton que aproxima el algoritmo Broyden-Fletcher-Goldfarb-Shanno (BFGS) utilizando una cantidad limitada de memoria de computadora . [ 1 ] Es un algoritmo popular para la estimación de parámetros en aprendizaje automático . [ 2 ] [ 3 ] El problema objetivo del algoritmo es minimizarF(incógnita){\displaystyle f(\mathbf {x} )}sobre valores no restringidos del vector realincógnita{\displaystyle \mathbf {x} }dóndeF{\displaystyle f}es una función escalar diferenciable.

Al igual que el BFGS original, L-BFGS utiliza una estimación de la matriz hessiana inversa para dirigir su búsqueda a través del espacio de variables, pero mientras que BFGS almacena una matriz hessiana densanorte×norte{\displaystyle n\times n}En la aproximación a la inversa de la matriz hessiana ( donde n es el número de variables del problema), L-BFGS almacena solo unos pocos vectores que representan la aproximación implícitamente. Debido a su requerimiento de memoria lineal resultante, el método L-BFGS es particularmente adecuado para problemas de optimización con muchas variables. En lugar de la inversa de la matriz hessiana H k , L-BFGS mantiene un historial de las m actualizaciones pasadas de la posición x y el gradiente ∇ f ( x ), donde generalmente el tamaño del historial m puede ser pequeño (a menudometro<10{\displaystyle m<10}Estas actualizaciones se utilizan para realizar implícitamente operaciones que requieren el producto de vectores H k .

Algoritmo

El algoritmo comienza con una estimación inicial del valor óptimo,incógnita0{\displaystyle \mathbf {x} _{0}}y procede iterativamente a refinar esa estimación con una secuencia de mejores estimaciones.incógnita1,incógnita2,…{\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots }. Las derivadas de la funcióngramok:=∇F(incógnitak){\displaystyle g_{k}:=\nabla f(\mathbf {x} _{k})}se utilizan como un impulsor clave del algoritmo para identificar la dirección de descenso más pronunciado y también para formar una estimación de la matriz hessiana (segunda derivada) deF(incógnita){\displaystyle f(\mathbf {x} )}.

L-BFGS comparte muchas características con otros algoritmos cuasi-Newton, pero es muy diferente en la forma en que se realiza la multiplicación matriz-vector.dk=−Hkgramok{\displaystyle d_{k}=-H_{k}g_{k}}se lleva a cabo, dondedk{\displaystyle d_{k}}es la dirección aproximada de Newton, gramok{\displaystyle g_{k}}es el gradiente actual, yHk{\displaystyle H_{k}}es la inversa de la matriz hessiana. Existen varios enfoques publicados que utilizan un historial de actualizaciones para formar este vector de dirección. Aquí presentamos un enfoque común, la llamada "recursión de dos bucles". [ 4 ] [ 5 ]

Tomamos como dadoincógnitak{\displaystyle x_{k}}, la posición en la k -ésima iteración, ygramok≡∇F(incógnitak){\displaystyle g_{k}\equiv \nabla f(x_{k})}dóndeF{\displaystyle f}es la función que se está minimizando, y todos los vectores son vectores columna. También asumimos que hemos almacenado las últimas m actualizaciones de la forma

sk=incógnitak+1−incógnitak{\displaystyle s_{k}=x_{k+1}-x_{k}}
yk=gramok+1−gramok{\displaystyle y_{k}=g_{k+1}-g_{k}}.

Nosotros definimosρk=1yk⊤sk{\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}, yHk0{\displaystyle H_{k}^{0}}será la aproximación 'inicial' de la inversa de la matriz hessiana con la que comienza nuestra estimación en la iteración k .

El algoritmo se basa en la recursión BFGS para la inversa de la matriz hessiana como

Hk+1=(I−ρkskyk⊤)Hk(I−ρkyksk⊤)+ρksksk⊤.{\displaystyle H_{k+1}=(I-\rho _{k}s_{k}y_{k}^{\top })H_{k}(I-\rho _{k}y_{k}s_{k}^{\top })+\rho _{k}s_{k}s_{k}^{\top }.}

Para un k fijo definimos una secuencia de vectoresqk−metro,…,qk{\displaystyle q_{k-m},\ldots ,q_{k}}comoqk:=gramok{\displaystyle q_{k}:=g_{k}}yqi:=(I−ρiyisi⊤)qi+1{\displaystyle q_{i}:=(I-\rho _{i}y_{i}s_{i}^{\top })q_{i+1}}. Luego, un algoritmo recursivo para calcularqi{\displaystyle q_{i}}deqi+1{\displaystyle q_{i+1}}es definirαi:=ρisi⊤qi+1{\displaystyle \alpha _{i}:=\rho _{i}s_{i}^{\top }q_{i+1}}yqi=qi+1−αiyi{\displaystyle q_{i}=q_{i+1}-\alpha _{i}y_{i}}También definimos otra secuencia de vectores.zk−metro,…,zk{\displaystyle z_{k-m},\ldots ,z_{k}}comozi:=Hiqi{\displaystyle z_{i}:=H_{i}q_{i}}. Existe otro algoritmo recursivo para calcular estos vectores que consiste en definirzk−metro=Hk0qk−metro{\displaystyle z_{k-m}=H_{k}^{0}q_{k-m}}y luego definir recursivamenteβi:=ρiyi⊤zi{\displaystyle \beta _{i}:=\rho _{i}y_{i}^{\top }z_{i}}yzi+1=zi+(αi−βi)si{\displaystyle z_{i+1}=z_{i}+(\alpha _{i}-\beta _{i})s_{i}}. El valor dezk{\displaystyle z_{k}}Esa es entonces nuestra dirección de ascenso.

Por lo tanto, podemos calcular la dirección de descenso de la siguiente manera:

q=gramokFor i=k−1,k−2,…,k−metroαi=ρisi⊤qq=q−αiyiγk=sk−metro⊤yk−metroyk−metro⊤yk−metroHk0=γkIz=Hk0qFor i=k−metro,k−metro+1,…,k−1βi=ρiyi⊤zz=z+si(αi−βi)z=−z{\displaystyle {\begin{array}{l}q=g_{k}\\{\mathtt {For}}\ i=k-1,k-2,\ldots ,k-m\\\qquad \alpha _{i}=\rho _{i}s_{i}^{\top }q\\\qquad q=q-\alpha _{i}y_{i}\\\gamma _{k}={\frac {s_{k-m}^{\top }y_{k-m}}{y_{k-m}^{\top }y_{k-m}}}\\H_{k}^{0}=\gamma _{k}I\\z=H_{k}^{0}q\\{\mathtt {For}}\ i=k-m,k-m+1,\ldots ,k-1\\\qquad \beta _{i}=\rho _{i}y_{i}^{\top }z\\\qquad z=z+s_{i}(\alpha _{i}-\beta _{i})\\z=-z\end{array}}}

Esta formulación da la dirección de búsqueda para el problema de minimización, es decir,z=−Hkgramok{\displaystyle z=-H_{k}g_{k}}Para problemas de maximización, se debe tomar -z en su lugar. Nótese que la inversa aproximada inicial del hessianoHk0{\displaystyle H_{k}^{0}}Se elige como una matriz diagonal o incluso un múltiplo de la matriz identidad, ya que esto es numéricamente eficiente.

El escalado de la matriz inicialγk{\displaystyle \gamma _{k}}asegura que la dirección de búsqueda esté bien escalada y, por lo tanto, la longitud del paso unitario se acepta en la mayoría de las iteraciones. Se utiliza una búsqueda lineal de Wolfe para asegurar que se cumpla la condición de curvatura y que la actualización BFGS sea estable. Tenga en cuenta que algunas implementaciones de software utilizan una búsqueda lineal de retroceso de Armijo , pero no pueden garantizar que se cumpla la condición de curvatura.yk⊤sk>0{\displaystyle y_{k}^{\top }s_{k}>0}se satisfará con el paso elegido ya que una longitud de paso mayor que1{\displaystyle 1}puede ser necesario para satisfacer esta condición. Algunas implementaciones abordan esto omitiendo la actualización de BFGS cuandoyk⊤sk{\displaystyle y_{k}^{\top }s_{k}}es negativo o demasiado cercano a cero, pero este enfoque no se recomienda generalmente ya que las actualizaciones pueden omitirse con demasiada frecuencia para permitir la aproximación de Hessiano.Hk{\displaystyle H_{k}}para capturar información importante sobre la curvatura. Algunos solucionadores emplean la llamada actualización (L)BFGS amortiguada que modifica cantidades.sk{\displaystyle s_{k}}yyk{\displaystyle y_{k}}para satisfacer la condición de curvatura.

La fórmula de recursión de dos bucles es ampliamente utilizada por los optimizadores sin restricciones debido a su eficiencia en la multiplicación por la inversa de la matriz hessiana. Sin embargo, no permite la formación explícita de la matriz hessiana directa ni de la inversa, y es incompatible con restricciones que no sean de caja. Un enfoque alternativo es la representación compacta , que implica una representación de bajo rango para la matriz hessiana directa y/o inversa. [ 6 ] Esta representa la matriz hessiana como la suma de una matriz diagonal y una actualización de bajo rango. Dicha representación permite el uso de L-BFGS en entornos con restricciones, por ejemplo, como parte del método SQP.

Aplicaciones

L-BFGS ha sido denominado "el algoritmo de elección" para ajustar modelos log-lineales (MaxEnt) y campos aleatorios condicionales conℓ2{\displaystyle \ell _{2}}-regularización . [ 2 ] [ 3 ]

Variantes

Dado que BFGS (y por ende L-BFGS) está diseñado para minimizar funciones suaves sin restricciones , el algoritmo L-BFGS debe modificarse para manejar funciones que incluyan componentes no diferenciables o restricciones. Una clase popular de modificaciones son los métodos de conjunto activo, basados ​​en el concepto de conjunto activo . La idea es que, al restringirse a un entorno pequeño de la iteración actual, la función y las restricciones se pueden simplificar.

L-BFGS-B

El algoritmo L-BFGS-B extiende L-BFGS para manejar restricciones de caja simples ( también conocidas como restricciones de límites) en variables; es decir, restricciones de la forma l i ≤ x i ≤ u i donde l i y u i son límites inferiores y superiores constantes por variable, respectivamente (para cada x i , se pueden omitir uno o ambos límites). [ 7 ] [ 8 ] El método funciona identificando variables fijas y libres en cada paso (usando un método de gradiente simple), y luego usando el método L-BFGS solo en las variables libres para obtener una mayor precisión, y luego repitiendo el proceso.

BÚHO-QN

El método cuasi-Newton de memoria limitada por ortantes ( OWL-QN ) es una variante de L-BFGS para el ajuste.ℓ1{\displaystyle \ell _{1}}- modelos regularizados , explotando la escasez inherente de dichos modelos. [ 3 ] Minimiza funciones de la forma

F(incógnita→)=gramo(incógnita→)+do‖incógnita→‖1{\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}}

dóndegramo{\displaystyle g}es una función de pérdida convexa diferenciable . El método es un método de tipo conjunto activo: en cada iteración, estima el signo de cada componente de la variable y restringe el paso subsiguiente para que tenga el mismo signo. Una vez que el signo está fijo, la no diferenciable‖incógnita→‖1{\displaystyle \|{\vec {x}}\|_{1}}El término se convierte en un término lineal suave que puede ser procesado por L-BFGS. Después de un paso de L-BFGS, el método permite que algunas variables cambien de signo y repite el proceso.

O-LBFGS

Schraudolph et al. presentan una aproximación en línea tanto para BFGS como para L-BFGS. [ 9 ] De forma similar al descenso de gradiente estocástico , esto puede utilizarse para reducir la complejidad computacional evaluando la función de error y el gradiente en un subconjunto seleccionado aleatoriamente del conjunto de datos general en cada iteración. Se ha demostrado que O-LBFGS tiene una convergencia global casi segura [ 10 ] mientras que la aproximación en línea de BFGS (O-BFGS) no es necesariamente convergente. [ 11 ]

Implementación de variantes

Entre las implementaciones de código abierto más destacadas se incluyen:

Entre las implementaciones no de código abierto más destacadas se incluyen:

  • La variante L-BFGS-B también existe como algoritmo ACM TOMS 778. [ 8 ] [ 13 ] En febrero de 2011, algunos de los autores del código L-BFGS-B original publicaron una actualización importante (versión 3.0).
  • Una implementación de referencia en Fortran 77 (y con una interfaz Fortran 90 ). [ 14 ] [ 15 ] Esta versión, así como versiones anteriores, se ha convertido a muchos otros lenguajes.
  • Una implementación de OWL-QN en C++ por sus diseñadores. [ 3 ] [ 16 ]

Obras citadas

  1. ↑ Liu, DC; Nocedal, J. (1989). "Sobre el método de memoria limitada para la optimización a gran escala" . Mathematical Programming B. 45 ( 3): 503– 528. CiteSeerX 10.1.1.110.6443 . doi : 10.1007/BF01589116 . S2CID 5681609 .  
  2. 1 2 Malouf, Robert (2002). "Una comparación de algoritmos para la estimación de parámetros de máxima entropía" . Actas de la Sexta Conferencia sobre Aprendizaje del Lenguaje Natural (CoNLL-2002) . págs. 49–55 . doi : 10.3115/1118853.1118871 . 
  3. 1 2 3 4 Andrew, Galen; Gao, Jianfeng (2007). "Entrenamiento escalable de modelos log-lineales regularizados con L₁" . Actas de la 24.ª Conferencia Internacional sobre Aprendizaje Automático . doi : 10.1145/1273496.1273501 . ISBN 9781595937933. S2CID 5853259 . 
  4. ↑ Matthies, H.; Strang, G. (1979). "La solución de ecuaciones de elementos finitos no lineales". International Journal for Numerical Methods in Engineering . 14 (11): 1613– 1626. Bibcode : 1979IJNME..14.1613M . doi : 10.1002/nme.1620141104 .
  5. ↑ Nocedal, J. (1980). "Actualización de matrices cuasi-Newton con almacenamiento limitado" . Matemáticas de la computación . 35 (151): 773– 782. doi : 10.1090/S0025-5718-1980-0572855-7 .
  6. ↑ Byrd, RH; Nocedal, J.; Schnabel, RB (1994). "Representaciones de matrices cuasi-Newton y su uso en métodos de memoria limitada". Mathematical Programming . 63 (4): 129– 156. doi : 10.1007/BF01582063 . S2CID 5581219 . 
  7. ↑ Byrd, RH; Lu, P.; Nocedal, J.; Zhu, C. (1995). "Un algoritmo de memoria limitada para la optimización con restricciones de límites" . SIAM J. Sci. Comput. 16 (5): 1190– 1208. Bibcode : 1995SJSC...16.1190B . doi : 10.1137/0916069 . S2CID 6398414 . 
  8. 1 2 Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). "L-BFGS-B: Algoritmo 778: L-BFGS-B, rutinas FORTRAN para optimización con restricciones de límites a gran escala" . ACM Transactions on Mathematical Software . 23 (4): 550– 560. doi : 10.1145/279232.279236 . S2CID 207228122 . 
  9. ↑ Schraudolph, N.; Yu, J.; Günter, S. (2007). Un método cuasi-Newton estocástico para la optimización convexa en línea . AISTATS.
  10. ↑ Mokhtari, A.; Ribeiro, A. (2015). "Convergencia global de BFGS de memoria limitada en línea" (PDF) . Journal of Machine Learning Research . 16 : 3151–3181 . arXiv : 1409.2045 .
  11. ↑ Mokhtari, A.; Ribeiro, A. (2014). "RES: Algoritmo BFGS estocástico regularizado". IEEE Transactions on Signal Processing . 62 (23): 6089– 6104. arXiv : 1401.7625 . Bibcode : 2014ITSP...62.6089M . CiteSeerX 10.1.1.756.3003 . doi : 10.1109/TSP.2014.2357775 . S2CID 15214938 .  
  12. ↑ "Documentación oficial de Optim.jl" . Documentación de Optim.jl .
  13. ↑ "Página principal de TOMS" . toms.acm.org .
  14. ↑ Morales, JL; Nocedal, J. (2011). "Comentario sobre el "algoritmo 778: L-BFGS-B: subrutinas Fortran para optimización a gran escala con restricciones de límites"". ACM Transactions on Mathematical Software . 38 : 1– 4. doi : 10.1145/2049662.2049669 . S2CID 16742561 . 
  15. ↑ "Código de optimización no lineal L-BFGS-B" . users.iems.northwestern.edu .
  16. ↑ "Optimizador cuasi-Newton de memoria limitada Orthant-Wise para objetivos regularizados L1" . Centro de descargas de Microsoft .

Lecturas adicionales

  • Liu, DC; Nocedal, J. (1989). "Sobre el método de memoria limitada para la optimización a gran escala" . Mathematical Programming B. 45 ( 3): 503– 528. CiteSeerX 10.1.1.110.6443 . doi : 10.1007/BF01589116 . S2CID 5681609 .  
  • Haghighi, Aria (2 de diciembre de 2014). "Optimización numérica: comprensión de L-BFGS" .
  • Pytlak, Radoslaw (2009). «Algoritmos cuasi-Newton de memoria limitada» . Algoritmos de gradiente conjugado en optimización no convexa . Springer. pp. 159–190 . ISBN  978-3-540-85633-7.