BFGS с ограниченной памятью

Алгоритм оптимизации

BFGS с ограниченной памятью ( L-BFGS или LM-BFGS ) — это алгоритм оптимизации в семействе квазиньютоновских методов , который аппроксимирует алгоритм Бройдена–Флетчера–Гольдфарба–Шенно (BFGS), используя ограниченный объем компьютерной памяти . ^[1] Это популярный алгоритм для оценки параметров в машинном обучении . ^{[2] [3]} Целевая задача алгоритма — минимизация по неограниченным значениям действительного вектора, где — дифференцируемая скалярная функция. ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle f}$

Как и оригинальный BFGS, L-BFGS использует оценку обратной матрицы Гессе для управления поиском через переменное пространство, но там, где BFGS хранит плотное приближение к обратному Гессе ( n — число переменных в задаче), L-BFGS хранит только несколько векторов, которые неявно представляют приближение. Из-за его результирующего линейного требования к памяти метод L-BFGS особенно хорошо подходит для задач оптимизации со многими переменными. Вместо обратного Гессе H _k , L-BFGS сохраняет историю последних m обновлений позиции x и градиента ∇ f ( x ), где, как правило, размер истории m может быть небольшим (часто ). Эти обновления используются для неявного выполнения операций, требующих произведения векторов H _k . ${\displaystyle n\times n}$ ${\displaystyle m<10}$

Алгоритм

Алгоритм начинается с начальной оценки оптимального значения, и итеративно продолжается для уточнения этой оценки с помощью последовательности лучших оценок . Производные функции используются в качестве ключевого драйвера алгоритма для определения направления наискорейшего спуска, а также для формирования оценки матрицы Гессе (второй производной) . ${\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 имеет много общих черт с другими квазиньютоновскими алгоритмами, но сильно отличается тем, как выполняется умножение матрицы на вектор, где — приблизительное направление Ньютона, — текущий градиент, а — обратная матрица Гессе. Существует несколько опубликованных подходов, использующих историю обновлений для формирования этого вектора направления. Здесь мы приводим общий подход, так называемую «двухцикловую рекурсию». ^{[4] [5]} ${\displaystyle d_{k}=-H_{k}g_{k}}$ ${\displaystyle d_{k}}$ ${\displaystyle g_{k}}$ ${\displaystyle H_{k}}$

Мы принимаем как заданное , позицию на k -й итерации, и где - минимизируемая функция, и все векторы являются векторами-столбцами. Мы также предполагаем, что мы сохранили последние m обновлений формы ${\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}}$.

Мы определяем , и будет «начальным» приближением обратного гессиана, с которого начинается наша оценка на итерации k . ${\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}$ ${\displaystyle H_{k}^{0}}$

Алгоритм основан на рекурсии BFGS для обратного гессиана:

${\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 }.}$

Для фиксированного k мы определяем последовательность векторов как и . Тогда рекурсивный алгоритм для вычисления из заключается в определении и . Мы также определяем другую последовательность векторов как . Существует еще один рекурсивный алгоритм для вычисления этих векторов, который заключается в определении и затем рекурсивном определении и . Значение тогда является нашим направлением восхождения. ${\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}}$

Таким образом, мы можем вычислить направление спуска следующим образом:

${\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}}}$

Эта формулировка дает направление поиска для задачи минимизации, т.е. . Для задач максимизации следует, таким образом, вместо этого взять -z . Обратите внимание, что начальный приближенный обратный гессиан выбирается как диагональная матрица или даже кратная единичной матрице, поскольку это численно эффективно. ${\displaystyle z=-H_{k}g_{k}}$ ${\displaystyle H_{k}^{0}}$

Масштабирование исходной матрицы гарантирует, что направление поиска хорошо масштабируется, и, следовательно, длина единичного шага принимается в большинстве итераций. Линейный поиск Вульфа используется для обеспечения того, чтобы условие кривизны было выполнено, а обновление BFGS было стабильным. Обратите внимание, что некоторые программные реализации используют линейный поиск с возвратом Armijo , но не могут гарантировать, что условие кривизны будет выполнено выбранным шагом, поскольку длина шага может быть больше, чем требуется для выполнения этого условия. Некоторые реализации решают эту проблему, пропуская обновление BFGS, когда отрицательно или слишком близко к нулю, но этот подход обычно не рекомендуется, поскольку обновления могут быть пропущены слишком часто, чтобы позволить приближению Гессе захватить важную информацию о кривизне. Некоторые решатели используют так называемое затухающее (L)BFGS-обновление, которое изменяет величины и для выполнения условия кривизны. ${\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}}$

Формула двухконтурной рекурсии широко используется неограниченными оптимизаторами из-за ее эффективности при умножении на обратный гессиан. Однако она не допускает явного формирования прямого или обратного гессиана и несовместима с небоксовыми ограничениями. Альтернативным подходом является компактное представление , которое включает низкоранговое представление для прямого и/или обратного гессиана. ^[6] Это представляет гессиан как сумму диагональной матрицы и низкорангового обновления. Такое представление позволяет использовать L-BFGS в ограниченных условиях, например, как часть метода SQP.

Приложения

L-BFGS был назван «алгоритмом выбора» для подгонки логарифмически линейных (MaxEnt) моделей и условных случайных полей с -регуляризацией . ^{[2] [3]} ${\displaystyle \ell _{2}}$

Варианты

Поскольку BFGS (и, следовательно, L-BFGS) разработан для минимизации гладких функций без ограничений , алгоритм L-BFGS должен быть модифицирован для обработки функций, которые включают недифференцируемые компоненты или ограничения. Популярный класс модификаций называется методами активного набора, основанными на концепции активного набора . Идея заключается в том, что при ограничении небольшой окрестностью текущей итерации функция и ограничения могут быть упрощены.

L-BFGS-B

Алгоритм L-BFGS-B расширяет L-BFGS для обработки простых ограничений типа box (они же граничные ограничения) на переменные; то есть ограничений вида l _i ≤ x _i ≤ u _i , где l _i и u _i являются постоянными нижними и верхними границами для каждой переменной соответственно (для каждого x _i одна или обе границы могут быть опущены). ^{[7] [8]} Метод работает путем определения фиксированных и свободных переменных на каждом шаге (с использованием простого градиентного метода), а затем использования метода L-BFGS только для свободных переменных для получения более высокой точности, а затем повторения процесса.

СОВА-QN

Квази-Ньютон с ограниченной памятью по ортанту ( OWL-QN ) — это вариант L-BFGS для подгонки регуляризованных моделей , использующий присущую таким моделям разреженность . ^[3] Он минимизирует функции вида ${\displaystyle \ell _{1}}$

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

где — дифференцируемая выпуклая функция потерь . Метод является методом типа активного множества: на каждой итерации он оценивает знак каждого компонента переменной и ограничивает последующий шаг тем же знаком. После того, как знак зафиксирован, недифференцируемый член становится гладким линейным членом, который может быть обработан L-BFGS. После шага L-BFGS метод позволяет некоторым переменным менять знак и повторяет процесс. ${\displaystyle g}$ ${\displaystyle \|{\vec {x}}\|_{1}}$

O-LBFGS

Шраудольф и др. представляют онлайн- аппроксимацию как для BFGS, так и для L-BFGS. ^[9] Подобно стохастическому градиентному спуску , это может быть использовано для снижения вычислительной сложности путем оценки функции ошибки и градиента на случайно выбранном подмножестве общего набора данных в каждой итерации. Было показано, что O-LBFGS имеет глобальную почти верную сходимость ^[10] , в то время как онлайн-аппроксимация BFGS (O-BFGS) не обязательно сходится. ^[11]

Реализация вариантов

Известные реализации с открытым исходным кодом включают в себя:

• ALGLIB реализует L-BFGS на языках C++ и C#, а также отдельную версию с блочными/линейно ограниченными функциями, BLEIC.
• Универсальная процедура оптимизатора Roptim использует метод L-BFGS-B.
• Метод минимизации модуля оптимизации SciPy также включает возможность использования L-BFGS-B.

Известные реализации с закрытым исходным кодом включают в себя:

• Вариант L-BFGS-B также существует как алгоритм ACM TOMS 778. ^{[8] [12]} В феврале 2011 года некоторые из авторов оригинального кода L-BFGS-B опубликовали крупное обновление (версия 3.0).
• Эталонная реализация на Fortran 77 (и с интерфейсом Fortran 90 ). ^{[13] [14]} Эта версия, как и более старые версии, была преобразована во многие другие языки.
• Реализация OWL-QN C++ его разработчиками. ^{[3] [15]}

Цитируемые работы

1. Лю, Д. К.; Нокедаль, Дж. (1989). «О методе ограниченной памяти для крупномасштабной оптимизации». Математическое программирование B. 45 ( 3): 503–528. CiteSeerX  10.1.1.110.6443 . doi :10.1007/BF01589116. S2CID  5681609.
2. Malouf, Robert (2002). "Сравнение алгоритмов для оценки параметра максимальной энтропии". Труды Шестой конференции по изучению естественного языка (CoNLL-2002) . стр. 49–55. doi : 10.3115/1118853.1118871 .
3. Эндрю, Гален; Гао, Цзяньфэн (2007). "Масштабируемое обучение L₁-регуляризованных логлинейных моделей". Труды 24-й Международной конференции по машинному обучению . doi :10.1145/1273496.1273501. ISBN 9781595937933. S2CID  5853259.
4. Matthies, H.; Strang, G. (1979). «Решение нелинейных уравнений конечных элементов». Международный журнал численных методов в машиностроении . 14 (11): 1613–1626. Bibcode :1979IJNME..14.1613M. doi :10.1002/nme.1620141104.
5. Nocedal, J. (1980). «Обновление квазиньютоновских матриц с ограниченной памятью». Математика вычислений . 35 (151): 773–782. doi : 10.1090/S0025-5718-1980-0572855-7 .
6. Берд, Р. Х.; Нокедаль, Дж.; Шнабель, Р. Б. (1994). «Представления квазиньютоновских матриц и их использование в методах с ограниченной памятью». Математическое программирование . 63 (4): 129–156. doi :10.1007/BF01582063. S2CID  5581219.
7. Берд, Р. Х.; Лу, П.; Нокедаль, Дж.; Чжу, К. (1995). «Алгоритм с ограниченной памятью для оптимизации с ограниченными ограничениями». 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: Алгоритм 778: L-BFGS-B, процедуры FORTRAN для крупномасштабной ограниченной оптимизации". ACM Transactions on Mathematical Software . 23 (4): 550–560. doi : 10.1145/279232.279236 . S2CID  207228122.
9. Шраудольф, Н.; Ю, Дж.; Гюнтер, С. (2007). Стохастический квазиньютоновский метод для выпуклой оптимизации в режиме онлайн . AISTATS.
10. Мохтари, А.; Рибейро, А. (2015). «Глобальная конвергенция онлайн-BFGS с ограниченной памятью» (PDF) . Журнал исследований машинного обучения . 16 : 3151–3181. arXiv : 1409.2045 .
11. Mokhtari, A.; Ribeiro, A. (2014). «RES: регуляризованный стохастический алгоритм BFGS». Труды IEEE по обработке сигналов . 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. "Главная TOMS". toms.acm.org .
13. Моралес, Дж. Л.; Нокедаль, Дж. (2011). «Замечание по «алгоритму 778: L-BFGS-B: подпрограммы Fortran для крупномасштабной ограниченной оптимизации»". Труды ACM по математическому программному обеспечению . 38 : 1–4. doi :10.1145/2049662.2049669. S2CID  16742561.
14. "L-BFGS-B Нелинейный код оптимизации". users.iems.northwestern.edu .
15. "Квази-Ньютоновский оптимизатор с ограниченной памятью Orthant-Wise для L1-регуляризованных целей". Центр загрузки Microsoft .

Дальнейшее чтение

• Лю, Д. К.; Нокедаль, Дж. (1989). «О методе ограниченной памяти для крупномасштабной оптимизации». Математическое программирование B. 45 ( 3): 503–528. CiteSeerX  10.1.1.110.6443 . doi :10.1007/BF01589116. S2CID  5681609.
• Хагиги, Ария (2 декабря 2014 г.). «Численная оптимизация: понимание L-BFGS».
• Pytlak, Radoslaw (2009). "Ограниченные по памяти квазиньютоновские алгоритмы". Алгоритмы сопряженных градиентов в невыпуклой оптимизации . Springer. С. 159–190. ISBN 978-3-540-85633-7.