L-BFGS

Материал из MachineLearning.

(Различия между версиями)

Iurii Patrakov (Обсуждение | вклад)
(Новая: {{well|Статья написана с использованием LLM '''GPT-5''' и проверена участником ~~~~}} '''L-BFGS''' — это [[квазиньютоно...)
К следующему изменению →

Версия 23:09, 9 июля 2026

Статья написана с использованием LLM GPT-5 и проверена участником Iurii Patrakov 03:09, 10 июля 2026 (MSD)

L-BFGS — это квазиньютоновский метод численной оптимизации для минимизации гладких функций многих переменных, который приближает обратную матрицу вторых производных, но хранит не всю матрицу, а только небольшую историю последних изменений параметров и градиентов. Название расшифровывается как метод Бройдена—Флетчера—Гольдфарба—Шанно ограниченной памяти (англ. Limited-memory BFGS).

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

Содержание

1 Идея метода
2 Схема работы
3 История
4 Значение для искусственного интеллекта и машинного обучения
5 Применения
6 Сравнение с другими методами
7 Ограничения
8 Современные направления
9 Практические замечания
10 См. также
11 Литература
12 Ссылки

Идея метода

В задаче безусловной минимизации требуется найти

$x^*=\arg\min_x f(x),$

где $f(x)$ — дифференцируемая скалярная функция, а $x$ — вектор параметров. Метод Ньютона использует матрицу вторых производных, или матрицу Гессе, чтобы учитывать кривизну функции:

$x_{k+1}=x_k-\alpha_k \nabla^2 f(x_k)^{-1}\nabla f(x_k).$

На практике вычислять, хранить и обращать матрицу Гессе слишком дорого. Квазиньютоновские методы строят приближение этой матрицы по наблюдаемым изменениям градиента. Классический метод Бройдена—Флетчера—Гольдфарба—Шанно хранит плотную матрицу размера $n\times n$ , где $n$ — число параметров. Для больших моделей это неприемлемо.

L-BFGS вместо матрицы хранит только последние $m$ пар векторов:

$s_k=x_{k+1}-x_k,$

$y_k=\nabla f(x_{k+1})-\nabla f(x_k).$

Здесь $s_k$ описывает, как изменились параметры, а $y_k$ — как изменился градиент. Эти пары несут информацию о локальной кривизне функции. Обычно $m$ выбирают небольшим, например от 3 до 20, поэтому память метода составляет $O(mn)$ , а не $O(n^2)$ .

Схема работы

Одна итерация L-BFGS обычно состоит из следующих шагов:

вычисляется градиент $g_k=\nabla f(x_k)$ ;
по сохранённым парам $(s_i,y_i)$ неявно строится действие приближённой обратной матрицы Гессе на градиент;
выбирается направление спуска $p_k=-H_k g_k$ ;
длина шага $\alpha_k$ подбирается поиском по прямой (англ. line search), часто с условиями Вольфе;
параметры обновляются: $x_{k+1}=x_k+\alpha_k p_k$ ;
новая пара $(s_k,y_k)$ добавляется в память, а самая старая удаляется.

Ключевой вычислительный приём — двухпроходная рекурсия (англ. two-loop recursion). Она позволяет умножить приближение обратной матрицы Гессе на градиент, не формируя саму матрицу. Поэтому L-BFGS можно применять там, где обычный BFGS невозможен из-за памяти.

Важное условие устойчивости обновления:

$y_k^\top s_k>0.$

Оно означает, что наблюдаемое изменение градиента согласуется с положительной кривизной вдоль сделанного шага. В выпуклых задачах при корректном поиске по прямой это условие обычно выполняется. В невыпуклых задачах, типичных для глубокого обучения, возможны нарушения, поэтому реализации могут пропускать плохие обновления или применять сглаженные варианты.

История

Метод Бройдена—Флетчера—Гольдфарба—Шанно был предложен в начале 1970-х годов как один из наиболее успешных квазиньютоновских методов. Его ограниченная по памяти версия связана прежде всего с работами Хорхе Носедаля.

В 1980 году Носедаль предложил идею обновления квазиньютоновских матриц с ограниченным хранением. В 1989 году Дун Лю и Хорхе Носедаль подробно исследовали L-BFGS для крупномасштабной оптимизации. Позднее появились важные расширения, в том числе L-BFGS-B — вариант для задач с простыми ограничениями на параметры, например $l_i\leq x_i\leq u_i$ .

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

Значение для искусственного интеллекта и машинного обучения

В искусственном интеллекте L-BFGS важен по нескольким причинам.

Во-первых, он часто сходится за меньшее число итераций, чем обычный градиентный спуск, потому что учитывает приближение кривизны функции потерь. Это особенно полезно в задачах, где вычисление градиента дорого, но возможно достаточно точно.

Во-вторых, метод не требует явного вычисления матрицы Гессе. Для многих моделей машинного обучения доступны функция потерь и её градиент, особенно при использовании автоматического дифференцирования, но полная матрица вторых производных слишком велика.

В-третьих, L-BFGS хорошо работает для гладких детерминированных задач: логистической регрессии, условных случайных полей, максимизации правдоподобия, подбора параметров статистических моделей, некоторых задач обучения малых и средних нейронных сетей.

До распространения стохастических методов первого порядка L-BFGS был одним из основных инструментов обучения моделей с большим числом признаков, особенно в обработке текста и вероятностном моделировании. В современных больших нейросетях он применяется реже, но остаётся важным базовым методом, эталоном для сравнения и инструментом для задач, где можно считать точный или почти точный градиент по всей выборке.

Применения

L-BFGS применяется в следующих областях:

обучение обобщённых линейных моделей;
логистическая регрессия и модели максимальной энтропии;
условные случайные поля;
гладкая регуляризованная минимизация эмпирического риска;
подгонка параметров вероятностных моделей методом максимального правдоподобия;
оптимизация параметров в научном моделировании;
обратные задачи и вычислительная физика;
оптимизация в обработке естественного языка;
локальная донастройка параметров небольших нейронных сетей или моделей с полным градиентом.

Отдельно используется вариант L-BFGS-B, поддерживающий покомпонентные ограничения на параметры. Например, он полезен, когда параметры должны оставаться неотрицательными или лежать в заданном интервале.

Сравнение с другими методами

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

По сравнению со стохастическими методами, такими как стохастический градиентный спуск, Adam или RMSProp, L-BFGS лучше приспособлен к детерминированной оптимизации по полному набору данных. Если градиент сильно зашумлён из-за малых мини-пакетов, качество квазиньютоновских обновлений ухудшается: метод начинает строить приближение кривизны по шумным различиям градиентов.

Ограничения

У L-BFGS есть несколько существенных ограничений.

Метод предполагает гладкость функции. Для негладких задач он может работать эмпирически, но теоретические гарантии слабее.
Он чувствителен к шуму в градиентах. Поэтому прямое применение с малыми мини-пакетами в глубоком обучении часто менее устойчиво, чем применение методов Adam или стохастического градиентного спуска.
Для хорошей работы обычно нужен надёжный поиск длины шага, что может требовать нескольких вычислений функции потерь на итерацию.
В сильно невыпуклых задачах приближение кривизны может быть неинформативным или даже вредным.
Метод хранит только ограниченную историю, поэтому не обладает всей информацией, которую имел бы полный BFGS.
Масштабирование признаков и параметров существенно влияет на качество работы.

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

Современные направления

Современные исследования L-BFGS и родственных методов развиваются в нескольких направлениях.

Стохастические квазиньютоновские методы пытаются совместить идею ограниченной памяти с обучением по мини-пакетам.
Регуляризованные и демпфированные варианты делают обновления устойчивее при шумных или невыпуклых функциях.
Проксимальные квазиньютоновские методы расширяют подход на задачи с негладкими слагаемыми, например с $L_1$ -регуляризацией.
Компактные представления квазиньютоновских матриц используются в задачах с ограничениями и методах доверительной области.
Гибридные алгоритмы сочетают L-BFGS с автоматическим дифференцированием, адаптивными методами первого порядка и распределёнными вычислениями.
В глубоком обучении L-BFGS изучается как инструмент для небольших моделей, полного градиента, дообучения и анализа ландшафта функции потерь, хотя в массовом обучении больших моделей чаще используются стохастические методы.

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

Практические замечания

При использовании L-BFGS обычно важны следующие параметры и решения:

размер памяти $m$ : малые значения уменьшают затраты, большие могут улучшить приближение кривизны;
критерий остановки: норма градиента, изменение функции или ограничение числа итераций;
способ поиска длины шага;
масштабирование признаков и начальное приближение обратной матрицы Гессе;
обработка случаев, когда $y_k^\top s_k$ слишком мало или отрицательно.

Для новичка полезно понимать L-BFGS как «градиентный спуск с памятью о локальной форме поверхности». Для специалиста важнее то, что эта память является не эвристической, а квазиньютоновской аппроксимацией обратной кривизны, реализованной через компактное хранение пар $(s,y)$ .

См. также

Литература

Nocedal J. Updating Quasi-Newton Matrices with Limited Storage // Mathematics of Computation. 1980. Vol. 35, No. 151. P. 773–782.
Liu D. C., Nocedal J. On the Limited Memory Method for Large Scale Optimization // Mathematical Programming. 1989. Vol. 45. P. 503–528.
Byrd R. H., Lu P., Nocedal J., Zhu C. A Limited Memory Algorithm for Bound Constrained Optimization // SIAM Journal on Scientific Computing. 1995. Vol. 16, No. 5. P. 1190–1208.
Zhu C., Byrd R. H., Lu P., Nocedal J. Algorithm 778: L-BFGS-B: FORTRAN Subroutines for Large Scale Bound Constrained Optimization // ACM Transactions on Mathematical Software. 1997. Vol. 23, No. 4. P. 550–560.
Nocedal J., Wright S. J. Numerical Optimization. 2nd ed. New York: Springer, 2006.
Fletcher R. Practical Methods of Optimization. 2nd ed. Chichester: Wiley, 1987.

Ссылки

L-BFGS Nonlinear Optimization Code — страница реализации L-BFGS у Хорхе Носедаля.
L-BFGS-B Nonlinear Optimization Code — страница реализации L-BFGS-B.
scipy.optimize.minimize(method='L-BFGS-B') — документация реализации L-BFGS-B в SciPy.
optim — документация функции оптимизации в R, включающей метод L-BFGS-B.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=L-BFGS»

Категории: Численная оптимизация | Машинное обучение | Методы оптимизации | Искусственный интеллект