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} = {гидроразрыв {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, km qquad alpha _ {i} = ho _ {i} s_ {i} ^ {op} q qquad 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} = гамма _ {k} I z = H_ {k} ^ {0} q {mathtt {For}} i = km, k-m + 1, ldots, k-1 qquad eta _ {i} = ho _ {i} y_ {i} ^ {op} z qquad z = z + s_ {i } (альфа _ {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, чтобы обрабатывать простые ограничения блока (также известные как связанные ограничения) для переменных; то есть ограничения вида $л я \leq Икс я \leq ты я$ куда $л я$ и $ты я$ - константы для каждой переменной, нижняя и верхняя границы, соответственно (для каждого $Икс я$ , одна или обе границы могут быть опущены).^[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]

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

^ ^а ^б Малуф, Роберт (2002). «Сравнение алгоритмов оценки максимального энтропийного параметра». Труды Шестой конференции по изучению естественного языка (CoNLL-2002). С. 49–55. Дои:10.3115/1118853.1118871.
^ ^а ^б ^c ^d Эндрю, Гален; Гао, Цзяньфэн (2007). «Масштабируемое обучение L₁-регуляризованных лог-линейных моделей». Материалы 24-й Международной конференции по машинному обучению. Дои:10.1145/1273496.1273501. ISBN 9781595937933. S2CID 5853259.
^ Matthies, H .; Стрэнг, Г. (1979). «Решение нелинейных уравнений конечных элементов». Международный журнал численных методов в инженерии. 14 (11): 1613–1626. Bibcode:1979IJNME..14.1613M. Дои:10.1002 / nme.1620141104.
^ Nocedal, J. (1980). «Обновление квазиньютоновских матриц с ограниченным объемом памяти». Математика вычислений. 35 (151): 773–782. Дои:10.1090 / S0025-5718-1980-0572855-7.
^ Byrd, R.H .; Nocedal, J .; Шнабель, Р. Б. (1994). «Представления квазиньютоновских матриц и их использование в методах с ограниченной памятью». Математическое программирование. 63 (4): 129–156. Дои:10.1007 / BF01582063. S2CID 5581219.
^ Byrd, R.H .; Lu, P .; Nocedal, J .; Чжу, К. (1995). «Алгоритм с ограниченной памятью для оптимизации с ограничениями». SIAM J. Sci. Comput. 16 (5): 1190–1208. Дои:10.1137/0916069.
^ ^а ^б Zhu, C .; Берд, Ричард Х .; Лу, Пейхуан; Нокедаль, Хорхе (1997). «L-BFGS-B: Алгоритм 778: L-BFGS-B, процедуры FORTRAN для крупномасштабной оптимизации с ограничениями». Транзакции ACM на математическом ПО. 23 (4): 550–560. Дои:10.1145/279232.279236. S2CID 207228122.
^ Schraudolph, N .; Yu, J .; Гюнтер, С. (2007). Стохастический квазиньютоновский метод онлайн-выпуклой оптимизации. АИСТАТС.
^ Мохтари, А .; Рибейро, А. (2015). «Глобальная конвергенция онлайновых BFGS с ограниченной памятью» (PDF). Журнал исследований в области машинного обучения. 16: 3151–3181.
^ Мохтари, А .; Рибейро, А. (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.
^ http://toms.acm.org/
^ Morales, J. L .; Нокедаль, Дж. (2011). "Замечание по" алгоритму 778: L-BFGS-B: подпрограммы Fortran для крупномасштабной оптимизации с ограничениями"". Транзакции ACM на математическом ПО. 38: 1–4. Дои: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

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

Лю, Д. С .; Нокедаль, Дж. (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.

[malouf-1] а ^б Малуф, Роберт (2002). «Сравнение алгоритмов оценки максимального энтропийного параметра». Труды Шестой конференции по изучению естественного языка (CoNLL-2002). С. 49–55. Дои:10.3115/1118853.1118871.

[owlqn-2] а ^б ^c ^d Эндрю, Гален; Гао, Цзяньфэн (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.

[LBFGSB1-6] Byrd, R.H .; Lu, P .; Nocedal, J .; Чжу, К. (1995). «Алгоритм с ограниченной памятью для оптимизации с ограничениями». SIAM J. Sci. Comput. 16 (5): 1190–1208. Дои:10.1137/0916069.

[algo778-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] ttp://toms.acm.org/

[LBFGSB_update-12] Morales, J. L .; Нокедаль, Дж. (2011). "Замечание по" алгоритму 778: L-BFGS-B: подпрограммы Fortran для крупномасштабной оптимизации с ограничениями"". Транзакции ACM на математическом ПО. 38: 1–4. Дои:10.1145/2049662.2049669. S2CID 16742561.

[13] ttp://users.eecs.northwestern.edu/~nocedal/lbfgsb.html

[14] ttps://www.microsoft.com/en-us/download/details.aspx?id=52452

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]