BFGS de memoria limitada ( L-BFGS o LM-BFGS ) es un algoritmo de optimización en la familia de métodos cuasi-Newton que se aproxima al algoritmo Broyden-Fletcher-Goldfarb-Shanno (BFGS) usando una cantidad limitada de memoria de computadora . Es un algoritmo popular para la estimación de parámetros en el aprendizaje automático . [1] [2] El problema objetivo del algoritmo es minimizar sobre valores no restringidos del vector real dónde 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 variable, pero donde BFGS almacena un densoAproximación al hessiano inverso ( siendo n el número de variables en el problema), L-BFGS almacena sólo 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 del hessiano inverso H k , L-BFGS mantiene un historial de las últimas m actualizaciones 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 de vector H k .
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 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 de Hesse (segunda derivada) de .
L-BFGS comparte muchas características con otros algoritmos cuasi-Newton, pero es muy diferente en cómo la multiplicación matriz-vector se lleva a cabo, donde es la dirección aproximada de Newton, es el gradiente actual, y es la inversa de la matriz de Hesse. Hay varios enfoques publicados que utilizan un historial de actualizaciones para formar este vector de dirección. Aquí, damos un enfoque común, la llamada "recursividad de dos bucles". [3] [4]
Tomamos como dado , la posición en la k -ésima iteración, y dónde es la función que se minimiza y todos los vectores son vectores columna. También asumimos que hemos almacenado las últimas m actualizaciones del formulario
- .
Definimos , y será la aproximación 'inicial' del hessiano inverso con el que comienza nuestra estimación en la iteración k .
El algoritmo se basa en la recursividad BFGS para el hessiano inverso como
Para una k fija definimos una secuencia de vectores como y . Luego, un algoritmo recursivo para calcular 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 de forma recursiva y . El valor de es entonces nuestra dirección de ascenso.
Por lo tanto, podemos calcular la dirección de descenso de la siguiente manera:
Esta formulación da la dirección de búsqueda para el problema de minimización, es decir, . Para problemas de maximización, uno debería tomar -z en su lugar. Tenga en cuenta que el hessiano inverso aproximado inicial se elige como una matriz diagonal o incluso un múltiplo de la matriz identidad, ya que es numéricamente eficiente.
El escalado de la matriz inicial 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 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 de Armijo , pero no pueden garantizar que la condición de curvatura quedará satisfecho con el paso elegido, ya que una longitud de paso mayor que puede ser necesario 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 la aproximación hessiana para capturar información importante sobre la curvatura.
Esta actualización de dos bucles solo funciona para el hessiano inverso. Enfoques para implementar L-BFGS usando el hessian aproximado directoTambién se han desarrollado, al igual que otros medios para aproximar el hessiano inverso. [5]
Aplicaciones
L-BFGS ha sido llamado "el algoritmo de elección" para ajustar modelos log-lineales (MaxEnt) y campos aleatorios condicionales con-regularización . [1] [2]
Variantes
Dado que BFGS (y por lo tanto L-BFGS) está diseñado para minimizar las 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 denominan métodos de conjunto activo, basados en el concepto de conjunto activo . La idea es que cuando se restringe a un pequeño vecindario del iterado 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 limitadas) 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). [6] [7] 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 en las variables libres solo para obtener una mayor precisión y luego repitiendo el proceso.
OWL-QN
El cuasi-Newton de memoria limitada Orthant-sabio ( OWL-QN ) es una variante de L-BFGS para el ajuste- modelos regularizados , aprovechando la escasez inherente de dichos modelos. [2] Minimiza las funciones de la forma
dónde 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, lo no diferenciable término se convierte en un término lineal suave que puede ser manejado por L-BFGS. Después de un paso L-BFGS, el método permite que algunas variables cambien de signo y repite el proceso.
O-LBFGS
Schraudolph y col. presentar una aproximación en línea tanto para BFGS como para L-BFGS. [8] Similar al descenso de gradiente estocástico , esto se puede utilizar para reducir la complejidad computacional mediante la evaluación de la función de error y el gradiente en un subconjunto dibujado al azar del conjunto de datos general en cada iteración. Se ha demostrado que O-LBFGS tiene una convergencia global casi segura [9] mientras que la aproximación en línea de BFGS (O-BFGS) no es necesariamente convergente. [10]
Implementación de variantes
La variante L-BFGS-B también existe como algoritmo ACM TOMS 778. [7] [11] 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 está disponible en Fortran 77 (y con una interfaz Fortran 90 ). [12] [13] Esta versión, al igual que las versiones anteriores, se ha convertido a muchos otros idiomas.
Una implementación OWL-QN está disponible como implementación C ++ por sus diseñadores. [2] [14]
Trabajos citados
- ↑ a b 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 el Aprendizaje del Lenguaje Natural (CoNLL-2002) . págs. 49–55. doi : 10.3115 / 1118853.1118871 .
- ^ a b c d Andrew, Galen; Gao, Jianfeng (2007). "Entrenamiento escalable de modelos log-lineales regularizados L₁" . Actas de la 24a Conferencia Internacional sobre Aprendizaje Automático . doi : 10.1145 / 1273496.1273501 . ISBN 9781595937933. S2CID 5853259 .
- ^ 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. Código bibliográfico : 1979IJNME..14.1613M . doi : 10.1002 / nme.1620141104 .
- ^ Nocedal, J. (1980). "Actualización de matrices de cuasi-Newton con almacenamiento limitado" . Matemáticas de la Computación . 35 (151): 773–782. doi : 10.1090 / S0025-5718-1980-0572855-7 .
- ^ Byrd, RH; Nocedal, J .; Schnabel, RB (1994). "Representaciones de matrices de 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 .
- ^ Byrd, RH; Lu, P .; Nocedal, J .; Zhu, C. (1995). "Un algoritmo de memoria limitada para la optimización restringida enlazada" . SIAM J. Sci. Computación. 16 (5): 1190–1208. doi : 10.1137 / 0916069 .
- ^ a b 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". Transacciones ACM en software matemático . 23 (4): 550–560. doi : 10.1145 / 279232.279236 . S2CID 207228122 .
- ^ Schraudolph, N .; Yu, J .; Günter, S. (2007). Un método estocástico cuasi-Newton para la optimización convexa en línea . AISTATS.
- ^ Mokhtari, A .; Ribeiro, A. (2015). "Convergencia global de BFGS de memoria limitada en línea" (PDF) . Revista de investigación sobre aprendizaje automático . 16 : 3151–3181.
- ^ Mokhtari, A .; Ribeiro, A. (2014). "RES: Algoritmo BFGS estocástico regularizado". Transacciones IEEE sobre procesamiento de señales . 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 .
- ^ http://toms.acm.org/
- ^ Morales, JL; Nocedal, J. (2011). "Observación sobre" algoritmo 778: L-BFGS-B: subrutinas de Fortran para optimización restringida a gran escala " ". Transacciones ACM en software matemático . 38 : 1–4. doi : 10.1145 / 2049662.2049669 . S2CID 16742561 .
- ^ http://users.eecs.northwestern.edu/~nocedal/lbfgsb.html
- ^ https://www.microsoft.com/en-us/download/details.aspx?id=52452
Otras lecturas
- Liu, DC; Nocedal, J. (1989). "Sobre el método de memoria limitada para la 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 de cuasi-Newton de memoria limitada" . Algoritmos de gradiente conjugado en optimización no convexa . Saltador. págs. 159-190. ISBN 978-3-540-85633-7.