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

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

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

Алгоритм

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

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

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

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

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

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

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

${displaystyle H_{k+1}=(I-ho _{k}s_{k}y_{k}^{ op })H_{k}(I-ho _{k}y_{k}s_{k}^{ op })+ho _{k}s_{k}s_{k}^{ op }.}$

Для фиксированного k мы определяем последовательность векторов ${displaystyle q_{k-m},ldots ,q_{k}}$ в качестве ${displaystyle q_{k}:=g_{k}}$ и ${displaystyle q_{i}:=(I-ho _{i}y_{i}s_{i}^{ op })q_{i+1}}$. Затем рекурсивный алгоритм вычисления ${displaystyle q_{i}}$ из ${displaystyle q_{i+1}}$ заключается в определении ${displaystyle alpha _{i}:=ho _{i}s_{i}^{ op }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 eta _{i}:=ho _{i}y_{i}^{ op }z_{i}}$ и ${displaystyle z_{i+1}=z_{i}+(alpha _{i}-eta _{i})s_{i}}$. Значение ${displaystyle z_{k}}$ тогда наше направление восхождения.

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

${displaystyle {egin{array}{l}q=g_{k}{mathtt {For}} i=k-1,k-2,ldots ,k-mqquad alpha _{i}=ho _{i}s_{i}^{ op }qqquad q=q-alpha _{i}y_{i}gamma _{k}={frac {s_{k-1}^{ op }y_{k-1}}{y_{k-1}^{ op }y_{k-1}}}H_{k}^{0}=gamma _{k}Iz=H_{k}^{0}q{mathtt {For}} i=k-m,k-m+1,ldots ,k-1qquad eta _{i}=ho _{i}y_{i}^{ op }zqquad z=z+s_{i}(alpha _{i}-eta _{i})z=-zend{array}}}$

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

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

Это обновление с двумя петлями работает только для обратного гессиана. Подходы к реализации L-BFGS с использованием прямого приближенного гессиана ${displaystyle B_{k}}$ также были разработаны, как и другие средства аппроксимации обратного гессиана.^[5]

Приложения

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

Варианты

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

L-BFGS-B

В L-BFGS-B алгоритм расширяет L-BFGS, чтобы обрабатывать простые ограничения блока (также известные как связанные ограничения) для переменных; то есть ограничения вида л_я ≤ Икс_я ≤ ты_я куда л_я и ты_я - константы для каждой переменной, нижняя и верхняя границы, соответственно (для каждого Икс_я, одна или обе границы могут быть опущены).^[6][7] Метод работает, определяя фиксированные и свободные переменные на каждом шаге (используя простой метод градиента), а затем используя метод L-BFGS для свободных переменных только для получения более высокой точности, а затем повторяя процесс.

OWL-QN

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

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

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

O-LBFGS

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

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

Вариант L-BFGS-B также существует как алгоритм 778 ACM TOMS.^[7][11] В феврале 2011 года некоторые из авторов исходного кода L-BFGS-B опубликовали крупное обновление (версия 3.0).

Эталонная реализация доступна в Фортран 77 (и с Фортран 90 интерфейс).^[12][13] Эта версия, как и более старые версии, была переведена на многие другие языки.

Реализация OWL-QN доступна разработчикам как реализация C ++.^[2][14]

Процитированные работы

1. Малуф, Роберт (2002). «Сравнение алгоритмов оценки максимального энтропийного параметра». Труды Шестой конференции по изучению естественного языка (CoNLL-2002). С. 49–55. Дои:10.3115/1118853.1118871.
2. Эндрю, Гален; Гао, Цзяньфэн (2007). «Масштабируемое обучение L₁-регуляризованных лог-линейных моделей». Материалы 24-й Международной конференции по машинному обучению. Дои:10.1145/1273496.1273501. ISBN  9781595937933. S2CID  5853259.
3. Matthies, H .; Стрэнг, Г. (1979). «Решение нелинейных уравнений конечных элементов». Международный журнал численных методов в инженерии. 14 (11): 1613–1626. Bibcode:1979IJNME..14.1613M. Дои:10.1002 / nme.1620141104.
4. Nocedal, J. (1980). «Обновление квазиньютоновских матриц с ограниченным объемом памяти». Математика вычислений. 35 (151): 773–782. Дои:10.1090 / S0025-5718-1980-0572855-7.
5. Byrd, R.H .; Nocedal, J .; Шнабель, Р. Б. (1994). «Представления квазиньютоновских матриц и их использование в методах с ограниченной памятью». Математическое программирование. 63 (4): 129–156. Дои:10.1007 / BF01582063. S2CID  5581219.
6. Byrd, R.H .; Lu, P .; Nocedal, J .; Чжу, К. (1995). «Алгоритм с ограниченной памятью для оптимизации с ограничениями». SIAM J. Sci. Comput. 16 (5): 1190–1208. Дои:10.1137/0916069.
7. Zhu, C .; Берд, Ричард Х .; Лу, Пейхуан; Нокедаль, Хорхе (1997). «L-BFGS-B: Алгоритм 778: L-BFGS-B, процедуры FORTRAN для крупномасштабной оптимизации с ограничениями». Транзакции ACM на математическом ПО. 23 (4): 550–560. Дои:10.1145/279232.279236. S2CID  207228122.
8. Schraudolph, N .; Yu, J .; Гюнтер, С. (2007). Стохастический квазиньютоновский метод онлайн-выпуклой оптимизации. АИСТАТС.
9. Мохтари, А .; Рибейро, А. (2015). «Глобальная конвергенция онлайновых BFGS с ограниченной памятью» (PDF). Журнал исследований в области машинного обучения. 16: 3151–3181.
10. Мохтари, А .; Рибейро, А. (2014). «RES: Регуляризованный стохастический алгоритм BFGS». Транзакции IEEE при обработке сигналов. 62 (23): 6089–6104. arXiv:1401.7625. Bibcode:2014ITSP ... 62.6089M. CiteSeerX  10.1.1.756.3003. Дои:10.1109 / TSP.2014.2357775. S2CID  15214938.
11. http://toms.acm.org/
12. Morales, J. L .; Нокедаль, Дж. (2011). "Замечание по" алгоритму 778: L-BFGS-B: подпрограммы Fortran для крупномасштабной оптимизации с ограничениями"". Транзакции ACM на математическом ПО. 38: 1–4. Дои:10.1145/2049662.2049669. S2CID  16742561.
13. http://users.eecs.northwestern.edu/~nocedal/lbfgsb.html
14. https://www.microsoft.com/en-us/download/details.aspx?id=52452

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

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