BFGS de memoria limitada

Algoritmo de optimización

BFGS de memoria limitada ( L-BFGS o LM-BFGS ) es un algoritmo de optimización de la familia de métodos cuasi-Newton que se aproxima al 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 el aprendizaje automático . ^{[2] [3]} El problema objetivo del algoritmo es minimizar sobre valores sin restricciones del vector real donde es una función escalar diferenciable. ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle f}$

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 donde BFGS almacena una aproximación densa a la hessiana inversa ( siendo n el número de variables en el problema), L-BFGS almacena solo unos pocos vectores que representan la aproximación implícitamente. Debido a su requisito de memoria lineal resultante, el método L-BFGS es particularmente adecuado para problemas de optimización con muchas variables. En lugar de la hessiana inversa 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 menudo ). Estas actualizaciones se utilizan para realizar implícitamente operaciones que requieren el producto H _{k -vector.} ${\displaystyle n\times n}$ ${\displaystyle m<10}$

Algoritmo

El algoritmo comienza con una estimación inicial del valor óptimo, , y procede iterativamente a refinar esa estimación con una secuencia de mejores estimaciones . Las derivadas de la función se utilizan como un factor clave del algoritmo para identificar la dirección del descenso más pronunciado y también para formar una estimación de la matriz hessiana (segunda derivada) de . ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots }$ ${\displaystyle g_{k}:=\nabla f(\mathbf {x} _{k})}$ ${\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 lleva a cabo la multiplicación matriz-vector, donde es la dirección aproximada de Newton, es el gradiente actual y es la inversa de la matriz de Hesse. Existen múltiples enfoques publicados que utilizan un historial de actualizaciones para formar este vector de dirección. Aquí, presentamos un enfoque común, la denominada "recursión de dos bucles". ^{[4] [5]} ${\displaystyle d_{k}=-H_{k}g_{k}}$ ${\displaystyle d_{k}}$ ${\displaystyle g_{k}}$ ${\displaystyle H_{k}}$

Tomamos como dada la posición en la k -ésima iteración y donde 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 ${\displaystyle x_{k}}$ ${\displaystyle g_{k}\equiv \nabla f(x_{k})}$ ${\displaystyle f}$

${\displaystyle s_{k}=x_{k+1}-x_{k}}$

${\displaystyle y_{k}=g_{k+1}-g_{k}}$.

Definimos , y será la aproximación 'inicial' del hessiano inverso con el que comienza nuestra estimación en la iteración k . ${\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}$ ${\displaystyle H_{k}^{0}}$

El algoritmo se basa en la recursión BFGS para el hessiano inverso como

${\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 una k fija definimos una secuencia de vectores como y . Luego, un algoritmo recursivo para calcular a partir de es definir y . También definimos otra secuencia de vectores como . Hay otro algoritmo recursivo para calcular estos vectores que es definir y luego definir recursivamente y . El valor de es entonces nuestra dirección de ascenso. ${\displaystyle q_{k-m},\ldots ,q_{k}}$ ${\displaystyle q_{k}:=g_{k}}$ ${\displaystyle q_{i}:=(I-\rho _{i}y_{i}s_{i}^{\top })q_{i+1}}$ ${\displaystyle q_{i}}$ ${\displaystyle q_{i+1}}$ ${\displaystyle \alpha _{i}:=\rho _{i}s_{i}^{\top }q_{i+1}}$ ${\displaystyle q_{i}=q_{i+1}-\alpha _{i}y_{i}}$ ${\displaystyle z_{k-m},\ldots ,z_{k}}$ ${\displaystyle z_{i}:=H_{i}q_{i}}$ ${\displaystyle z_{k-m}=H_{k}^{0}q_{k-m}}$ ${\displaystyle \beta _{i}:=\rho _{i}y_{i}^{\top }z_{i}}$ ${\displaystyle z_{i+1}=z_{i}+(\alpha _{i}-\beta _{i})s_{i}}$ ${\displaystyle z_{k}}$

De esta manera podemos calcular la dirección de descenso de la siguiente manera:

${\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-1}^{\top }y_{k-1}}{y_{k-1}^{\top }y_{k-1}}}\\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 proporciona la dirección de búsqueda para el problema de minimización, es decir, . Para los problemas de maximización, se debería tomar -z en su lugar. Nótese que la matriz hessiana inversa aproximada inicial se elige como una matriz diagonal o incluso un múltiplo de la matriz identidad, ya que esto es numéricamente eficiente. ${\displaystyle z=-H_{k}g_{k}}$ ${\displaystyle H_{k}^{0}}$

El escalado de la matriz inicial garantiza 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 de línea de Wolfe para garantizar que se cumpla la condición de curvatura y que la actualización de BFGS sea estable. Tenga en cuenta que algunas implementaciones de software utilizan una búsqueda de línea de retroceso Armijo , pero no pueden garantizar que la condición de curvatura se cumpla con el paso elegido, ya que puede ser necesaria una longitud de paso mayor que para satisfacer esta condición. Algunas implementaciones abordan esto omitiendo la actualización de BFGS cuando es negativo o demasiado cercano a cero, pero este enfoque generalmente no se recomienda ya que las actualizaciones pueden omitirse con demasiada frecuencia para permitir que la aproximación hessiana capture información de curvatura importante. Algunos solucionadores emplean la llamada actualización (L)BFGS amortiguada que modifica cantidades y para satisfacer la condición de curvatura. ${\displaystyle \gamma _{k}}$ ${\displaystyle y_{k}^{\top }s_{k}>0}$ ${\displaystyle 1}$ ${\displaystyle y_{k}^{\top }s_{k}}$ ${\displaystyle H_{k}}$ ${\displaystyle s_{k}}$ ${\displaystyle y_{k}}$

La fórmula de recursión de dos bucles es ampliamente utilizada por optimizadores sin restricciones debido a su eficiencia en la multiplicación por el hessiano inverso. Sin embargo, no permite la formación explícita ni del hessiano directo ni del inverso 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 el hessiano directo y/o inverso. ^[6] Esto representa el hessiano como una suma de una matriz diagonal y una actualización de bajo rango. Tal representación permite el uso de L-BFGS en entornos restringidos, por ejemplo, como parte del método SQP.

Aplicaciones

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

Variantes

Dado que BFGS (y, por lo tanto, L-BFGS) está diseñado para minimizar funciones suaves sin restricciones , el algoritmo L-BFGS debe modificarse para manejar funciones que incluyen componentes o restricciones no diferenciables . Una clase popular de modificaciones se denomina métodos de conjunto activo, basados ​​en el concepto de conjunto activo . La idea es que cuando se restringe a un pequeño vecindario 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ímite) en variables; es decir, restricciones de la forma l _i ≤ x _i ≤ u _i donde l _i y u _i son límites inferior y superior 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 mayor precisión, y luego repitiendo el proceso.

BÚHO-QN

El quasi-Newton de memoria limitada orthant-wise ( OWL-QN ) es una variante de L-BFGS para ajustar modelos regularizados , que explota la escasez inherente de dichos modelos. ^[3] Minimiza funciones de la forma ${\displaystyle \ell _{1}}$

${\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}}$

donde 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 posterior para que tenga el mismo signo. Una vez que se fija el signo, el término no diferenciable se convierte en un término lineal suave que puede manejarse mediante L-BFGS. Después de un paso L-BFGS, el método permite que algunas variables cambien de signo y repite el proceso. ${\displaystyle g}$ ${\displaystyle \|{\vec {x}}\|_{1}}$

O-LBFGS

Schraudolph et al. presentan una aproximación en línea tanto para BFGS como para L-BFGS. ^[9] De manera similar al descenso de gradiente estocástico , esto se puede utilizar para reducir la complejidad computacional evaluando la función de error y el gradiente en un subconjunto extraído 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

Las implementaciones de código abierto notables incluyen:

• ALGLIB implementa L-BFGS en C++ y C#, así como una versión separada con restricciones lineales y de caja, BLEIC.
• optimLa rutina optimizadora de propósito general de R utiliza el método L-BFGS-B.
• El método de minimización del módulo de optimización de SciPy también incluye una opción para utilizar L-BFGS-B.

Entre las implementaciones notables que no son de código abierto se incluyen:

• La variante L-BFGS-B también existe como algoritmo ACM TOMS 778. ^{[8] [12]} 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 ). ^{[13] [14]} 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] [15]}

Obras citadas

1. Liu, DC; Nocedal, J. (1989). "Sobre el método de memoria limitada para optimización a gran escala". Programación matemática B . 45 (3): 503–528. CiteSeerX  10.1.1.110.6443 . doi :10.1007/BF01589116. S2CID  5681609.
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 de Lenguaje Natural (CoNLL-2002) . págs. 49–55. doi : 10.3115/1118853.1118871 .
3. Andrew, Galen; Gao, Jianfeng (2007). "Entrenamiento escalable de modelos log-lineales regularizados 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". Revista internacional de métodos numéricos en ingeniería . 14 (11): 1613–1626. Bibcode :1979IJNME..14.1613M. doi :10.1002/nme.1620141104.
5. Nocedal, J. (1980). "Actualización de matrices cuasi-newtonianas 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". Programación matemática . 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 optimización con restricciones limitadas". SIAM J. Sci. Comput. 16 (5): 1190–1208. doi :10.1137/0916069. S2CID  6398414.
8. Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). "L-BFGS-B: Algoritmo 778: L-BFGS-B, rutinas FORTRAN para optimización restringida 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 estocástico cuasi-Newton 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) . Revista de investigación en aprendizaje automático . 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 . Código Bibliográfico :2014ITSP...62.6089M. CiteSeerX 10.1.1.756.3003 . doi :10.1109/TSP.2014.2357775. S2CID  15214938. 
12. "Página de inicio de TOMS". toms.acm.org .
13. Morales, JL; Nocedal, J. (2011). "Observación sobre el algoritmo 778: L-BFGS-B: subrutinas Fortran para optimización limitada a gran escala"". Transacciones ACM sobre software matemático . 38 : 1–4. doi :10.1145/2049662.2049669. S2CID  16742561.
14. "Código de optimización no lineal L-BFGS-B". users.iems.northwestern.edu .
15. "Optimizador cuasi-Newton de memoria limitada basado en Orthant para objetivos regularizados L1". Centro de descargas de Microsoft .

Lectura adicional

• Liu, DC; Nocedal, J. (1989). "Sobre el método de memoria limitada para optimización a gran escala". Programación matemática 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-newtonianos con memoria limitada". Algoritmos de gradiente conjugado en optimización no convexa . Springer. págs. 159–190. ISBN 978-3-540-85633-7.