Оптимизация функций сделана правильно
BFGS относится к категории алгоритмов оптимизации, основанных на квазиньютоновских подходах.
Где и как это используется
BFGS — это тип алгоритма оптимизации второго порядка. BFGS используется в машинном обучении в таких алгоритмах, как логистическая регрессия и т. Д. Его основное использование заключается в необходимой минимизации функции стоимости в алгоритме машинного обучения, чтобы правильно найти алгоритм наилучшего приближения, требуемый для модели.
Так что же такое квазиньютоновский подход?
По сути, в соответствии с методом Ньютона для поиска корней функции с несколькими переменными, любую функцию можно разделить на следующие категории:
где матрица Якоби имеет вид
Любой ньютоновский метод, в котором матрица Якоби заменена аппроксимацией, считается квазиньютоновским методом.
Почему методы Ньютона предпочтительнее градиентного спуска
Как вы, возможно, знаете, в градиентном спуске мы намерены минимизировать заданную функцию стоимости, изображенную как
Здесь α — скорость обучения функции градиентного спуска.
Здесь действие функции градиентного спуска зависит исключительно от параметра производной функции, поэтому этот метод классифицируется как метод оптимизации первого порядка. Хотя этот метод является хорошим способом оптимизации заданной функции стоимости, поскольку мы линейно работаем с локальной и ограниченной информацией на каждом шаге, это приводит к определенным ограничениям для него.
Поэтому мы ищем более эффективный метод, требующий и анализирующий больше информации и параметров, то есть метод оптимизации второго порядка.
Метод Ньютона
Рассмотрим функцию f(x) с соответствующим размером шага ε.
Согласно аппроксимации Тейлора, аппроксимация функции на данном шаге будет,
Требуемая функция будет минимизирована, когда приведенное ниже значение равно 0.
Следовательно, значение ε будет выглядеть следующим образом:
Как мы видим, в отличие от оптимизации первого порядка, здесь значение размера шага анализирует и учитывает поведение второго порядка требуемой функции.
Итерация будет следующей,
Теперь, в случае нескольких измерений,
первая производная заменяется градиентом функции
а вторая производная заменяется на Гессиан H.
i.e.
Гессиан H функции определяется как матрица частных производных второго порядка от f.
i.e.
Итак, наконец, для нескольких измерений n итерационная схема будет
Этот метод обычно дает очень высокую скорость оптимизации, намного выше, чем у градиентного спуска.
Так почему бы не всегда использовать метод Ньютона?
У него есть определенные недостатки:
а. Методы Ньютона можно использовать, только если функция дважды дифференцируема.
b. Этот метод работает только для сходящихся функций и неэффективен при оптимизации в случае множественных требований оптимизации кривизны, например, для нейронных сетей.
c. Основным недостатком является то, что для каждой итерации метода Ньютона требуется решение большой линейной системы уравнений, что для крупномасштабных задач может быть очень затратным в вычислительном отношении. Вычисление и анализ гессиана H, как правило, требуют непозволительно большого количества времени.
На смену приходят квазиньютоновские методы!
Суть квазиньютоновского метода заключается в том, чтобы обеспечить устойчивость вычислений за счет снижения затрат на вычисления и итерации на каждом шаге оптимизации. Это достигается путем простого аппроксимации гессиана H на шаге итерации вместо фактического вычисления всего точного значения.
Значение приближения обозначается как B, ина каждой итерации n+1 новое приближение Гессе B получается с использованием предыдущей информации об градиенте.
БФГС
Теперь, чтобы использовать метод квазиньютона для оптимизации, необходимо наложить определенные ограничения для расчета приближения Гессе, B.
Один из этих методов ограничений называется методом BFGS, названным в честь его создателей: Бройдена, Флетчера, Гольдфарба и Шэнно.
Ограничения следующие:
a. B на каждом последующем шаге должно быть значительно близко к своему значению на предыдущем шаге, поэтому мы намерены минимизировать разницу между ними, т.е.
б. «Матричная норма» – это математический термин для классификации близости между двумя значениями. В BFGS для работы выбрана норма Фробениуса. Используя этот метод, итеративное значение B получается в виде
где U и V — симметричные матрицы первого ранга.
c. U, V и инверсия B определяется с помощью метода, называемого формула Вудбери и, следовательно, приводит к тому, что дальнейшие итерации полностью освобождаются от пересчета и инверсии гессиана H, что приводит к более быстрому и более эффективному методу оптимизации функций.
Реализация
Давайте начнем с определения функции (константы, определенные массивом)
Тогда давайте напишем функцию для его производной
Наконец, давайте используем метод BFGS для его оптимизации, задавая необходимые значения
Вывод будет выглядеть так,
Спасибо за чтение этой статьи, я надеюсь, что смог дать некоторое представление о понимании и использовании этого алгоритма.
Не стесняйтесь обращаться ко мне по моим контактам в социальных сетях;
