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

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

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

Алгоритм

Алгоритм начинается с первоначальной оценки оптимального значения, $\mathbf {x} _{0}$и итеративно уточняет эту оценку с помощью последовательности лучших оценок $\mathbf {x} _{1},\mathbf {x} _{2},\ldots$. Производные функции $g_{k}:=\nabla f(\mathbf {x} _{k})$ используются в качестве ключевого фактора алгоритма для определения направления наискорейшего спуска, а также для формирования оценки матрицы Гессе (второй производной) $f(\mathbf {x} )$.

L-BFGS имеет много общего с другими квазиньютоновскими алгоритмами, но сильно отличается от метода умножения матрицы на вектор. $d_{k}=-H_{k}g_{k}$ осуществляется, где $d_{k}$ - приблизительное направление Ньютона, $g_{k}$ текущий градиент, и $H_{k}$ является обратной матрицей Гессе. Существует множество опубликованных подходов, использующих историю обновлений для формирования этого вектора направления. Здесь мы даем общий подход, так называемую «двухцикловую рекурсию».

Мы принимаем как данность $x_{k}$, позиция на k -й итерации, и $g_{k}\equiv \nabla f(x_{k})$ где $f$ — минимизируемая функция, а все векторы являются векторами-столбцами. Мы также предполагаем, что мы сохранили m последних обновлений вида

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

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

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

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

$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 определим последовательность векторов $q_{k-m},\ldots ,q_{k}$ как $q_{k}:=g_{k}$ и $q_{i}:=(I-\rho _{i}y_{i}s_{i}^{\top })q_{i+1}$. Тогда рекурсивный алгоритм вычисления $q_{i}$ от $q_{i+1}$ это определить $\alpha _{i}:=\rho _{i}s_{i}^{\top }q_{i+1}$ и $q_{i}=q_{i+1}-\alpha _{i}y_{i}$. Мы также определим еще одну последовательность векторов $z_{k-m},\ldots ,z_{k}$ как $z_{i}:=H_{i}q_{i}$. Существует еще один рекурсивный алгоритм вычисления этих векторов, который заключается в определении $z_{k-m}=H_{k}^{0}q_{k-m}$ а затем рекурсивно определить $\beta _{i}:=\rho _{i}y_{i}^{\top }z_{i}$ и $z_{i+1}=z_{i}+(\alpha _{i}-\beta _{i})s_{i}$. Стоимость $z_{k}$ тогда это наше направление восхождения.

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

${\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=-H_{k}g_{k}$. Поэтому для задач максимизации вместо этого следует использовать -z . Обратите внимание, что исходный приближенный обратный гессиан $H_{k}^{0}$ выбирается как диагональная матрица или даже кратная единичной матрице, поскольку это численно эффективно.

Масштабирование исходной матрицы $\gamma _{k}$ гарантирует, что направление поиска хорошо масштабируется и поэтому длина единичного шага принимается в большинстве итераций. Поиск линии Вульфа используется, чтобы гарантировать, что условие кривизны удовлетворено и обновление BFGS стабильно. Обратите внимание, что некоторые реализации программного обеспечения используют поиск линии с возвратом Armijo , но не могут гарантировать, что условие кривизны $y_{k}^{\top }s_{k}>0$ будет удовлетворен выбранным шагом, поскольку длина шага больше, чем $1$ может потребоваться для выполнения этого условия. Некоторые реализации решают эту проблему, пропуская обновление BFGS при $y_{k}^{\top }s_{k}$ отрицательное значение или слишком близко к нулю, но этот подход обычно не рекомендуется, поскольку обновления могут быть пропущены слишком часто, чтобы обеспечить аппроксимацию Гессе. $H_{k}$ для сбора важной информации о кривизне. Некоторые решатели используют так называемое демпфированное обновление (L)BFGS, которое изменяет величины. $s_{k}$ и $y_{k}$ для выполнения условия кривизны.

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

Приложения

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

Варианты

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

Л-БФГС-Б

Алгоритм L-BFGS-B расширяет L-BFGS для обработки простых ограничений блока (также известных как связанные ограничения) для переменных; то есть ограничения вида l _i ≤ x _i ≤ u _i, где l _i и u _i — постоянные нижняя и верхняя границы для каждой переменной соответственно (для каждого x _i одна или обе границы могут быть опущены). Этот метод работает путем идентификации фиксированных и свободных переменных на каждом этапе (с использованием простого градиентного метода), а затем использования метода L-BFGS для свободных переменных только для получения более высокой точности, а затем повторения процесса.

СОВА-QN

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

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

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

О-ЛБФГС

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

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

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

• ALGLIB реализует L-BFGS на C++ и C#, а также отдельную коробочную/линейно ограниченную версию BLEIC.
• Р 's optim Программа оптимизатора общего назначения использует метод L-BFGS-B.
• Метод минимизации модуля оптимизации SciPy также включает возможность использования L-BFGS-B.

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

• Вариант L-BFGS-B также существует как алгоритм ACM TOMS 778. В феврале 2011 года некоторые из авторов исходного кода L-BFGS-B опубликовали крупное обновление (версию 3.0).
• Эталонная реализация на Фортране 77 (и с интерфейсом Фортрана 90 ). Эта версия, как и более ранние версии, конвертирована на многие другие языки.
• Реализация OWL-QN C++, созданная его разработчиками.

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

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