Квазиньютоновские методы

Шубхам П. Кулкарни (16 585); Дипак К. Ядав (17088 г.);

Цель этой статьи — предоставить интуитивно понятное введение в мощный (и популярный) итеративный метод решения (как следует из названия) задач оптимизации вместе с числовыми иллюстрациями. Мы предполагаем знание частных производных (исчисление 201) и надеемся дать полное объяснение с помощью математической интуиции. Начнем со стандартной постановки задачи:

Большинство инженерных и проектных задач можно сформулировать в простой форме как задачу оптимизации (максимума или минимума) следующим образом:

Невыполнимая задача

Минимизация функции f(x) по вектору ее параметров x — это процесс поиска такого параметра x, при котором значение функции в этой точке минимально. Это невыполнимая задача!

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

«Решение уравнения»: большинство из нас знакомы с этой невозможной задачей поиска и подходом к ее решению для случая одномерной функции, где минимумы задаются точкой, в которой производная функции равна нулю. Это проистекает из интуиции, что производная функции в любой точке x дает наклон касательной. Представьте себе одномерную функцию (скажем, параболическую) с учетом наклона в точке x, теперь, если этот наклон отличен от нуля, есть шанс еще больше уменьшить значение функции, двигаясь в направлении, противоположном наклону.

Всю вышеописанную структуру можно дословно расширить до многомерных функций (т. е. функциональных машин, которые используют вектор для вывода скаляра). На помощь приходит мощь строгих определений частных производных, где частное дифференцирование по каждой входной переменной дает наклон касательного вектора, лежащего в касательной плоскости. Представьте себе трехмерную чашу (двухмерная функция), если касательная плоскость в любой точке не горизонтальна (подсказка: производная = 0), существует направление, в котором значение функции уменьшается.

Таким образом, наша невозможная задача поиска (бесконечно) сводится к решению вышеприведенного уравнения, которое часто оказывается очень трудным. Здорово!

В качестве примера давайте рассмотрим двумерную функцию, как показано ниже: (Примечание: эта функция широко известна как функция Розенброка)

Это двумерная функция, принимающая упорядоченную пару [x,y] и возвращающая скалярное значение. На следующем рисунке показан тип визуализации (известный как контурный график) для такой функции, где каждая линия показывает кривую для постоянного значения функции.

Цель состоит в том, чтобы найти минимумы функции (или, что то же самое, решить уравнение градиента). Оглядываясь назад, мы знаем, что минимумы — это упорядоченная пара (1,1), где значение функции равно 0. В следующей увеличенной версии контурного графика (подсказка: новая цветная карта) белая область указывает на долину функции Розенброка (т.е. минимумы область)

Алгоритмы спуска

«Алгоритмы спуска». Решение уравнения, приравнивающего градиент функции, равной нулю, может быть неосуществимым (или даже невозможным) даже для простых на вид функций. Однако идея о том, что значение функции увеличивается при движении в «определенном» направлении, может быть использована для получения итеративного процесса (называемого алгоритмом) для достижения решения приведенного выше уравнения. Если конкретное направление равно направлению градиента в точке (напротив), результирующий алгоритм называется градиентным спуском:

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

Градиентный спуск

Напомним, что градиентный спуск — это итерационный метод нахождения локального минимума действительнозначной дифференцируемой целевой функции f(x).

Чтобы найти локальный минимум, мы начинаем со случайной начальной точки и итеративно делаем шаги, пропорциональные отрицательному градиенту функции f в текущей точке. Поскольку градиент функции указывает в направлении наискорейшего подъема, отрицательный градиент указывает в направлении наискорейшего спуска, и, таким образом, на каждом шаге градиентного спуска мы движемся в направлении, где f(x) уменьшается быстрее всего. Символически итерация градиентного спуска записывается как

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

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

Обратите внимание на сходимость, начиная с другой начальной точки для функции Розенброка, представленной в предыдущем разделе. Каждая линия (красная и синяя) соответствует одному шагу нашего итеративного уравнения.

Стоит отметить, что потребовалось около 10000 шагов (итераций), чтобы достичь фактического решения (то есть [1,1]) в пределах 1e-5. Оглядываясь назад, проблема была выбрана таким образом, чтобы фактическое решение было известно.

Если мы хотим достичь решения за меньшее количество итераций (быстрее), в нашем итеративном подходе требуется модификация. Он вдохновлен методом поиска корней сэра Исаака Ньютона (1680).

Метод Ньютона

Для простоты сначала рассмотрим функцию f одной переменной. Консультируясь с Тейлором (1715), мы знаем, что аппроксимация второго порядка f относительно точки xᴋ+ϵ определяется выражением

Эта функция (аппроксимация Тейлора) минимизируется, когда

Таким образом, мы можем попробовать новую схему итерации

который также учитывает поведение целевой функции второго порядка.

Обобщая до n измерений, первая производная заменяется градиентом ∇f, а вторая производная заменяется гессианом H.

Гессиан скалярнозначной функции f представляет собой квадратную матрицу частных производных второго порядка от f.

Таким образом, в измерениях n наша новая итерационная схема записывается так:

Этот метод оптимизации, при котором мы учитываем поведение целевой функции второго порядка в дополнение к ее поведению первого порядка, известен как метод Ньютона. (В честь сэра Исаака Ньютона!)

На каждой итерации k метод Ньютона аппроксимирует функцию f в точке xᴋ параболой, а затем продолжает минимизировать это приближение, делая шаг к минимуму этой параболы (на самом деле здесь есть оговорка, к которой мы вернемся позже). Обратите внимание, что по сравнению с обычным градиентным спуском больше нет необходимости устанавливать параметр скорости обучения, потому что теперь размер нашего шага определяется точно расстоянием до минимума подобранной параболы в этой точке.

Метод Ньютона применительно к уже знакомой функции Розенброка, где мы знаем, что минимумы лежат в [1,1], приводит к следующим итерационным иллюстрациям, а общее количество итераций находится в диапазоне 30–40.

Когда мы сравниваем эти 40 итераций с примерно 10000 для случая градиентного спуска, видна резкая разница в скорости сходимости метода Ньютона по сравнению с обычным градиентным спуском.

Скорость достижения решения настолько высока, что можно спросить: «Зачем вообще использовать градиентный спуск, если метод Ньютона сходится к минимуму намного быстрее?»

Но, как говорится, «судя о книге по обложке», мы упускаем из виду две основные проблемы метода Ньютона:

Рассмотрим функцию Химмерблау:

Он имеет четыре одинаковых локальных минимума:

  1. Высокая чувствительность к начальным условиям. Смотрите на изображении выше:здесь метод Ньютона не может сходиться (как показано красной точкой) к минимуму, когда начальная точка равна (0,5, -2), но BFGS (метод загадки на данный момент ) успешно сходится к одному из минимумов. Поэтому трудно выбрать начальные точки так, чтобы метод Ньютона сходился. Особенно актуально для невыпуклой модели будут нейронные сети. В оставшейся части этой статьи мы ограничим наше внимание только выпуклыми целевыми функциями.
  2. Положительный определенный гессиан; - если гессиан не является положительно определенным, обновление может увеличить значение целевой функции. Соответственномы требуем, чтобы гессиан был положительно определенным.
  3. Вычислительно дорого. По мере увеличения размеров нашей задачи накладные расходы памяти и времени очень быстро выходят из-под контроля. Например, в 50 измерениях нам придется вычислять 50(50+1)/2 = 1275 значений для гессиана на каждом шаге, а затем выполнять примерно еще (53*2500) операций, чтобы инвертировать его. На данный момент ясно, что выгода от увеличения скорости сходимости будет намного перевешиваться большими затратами на дополнительное время вычислений. (вычисление шкалы Гессе как O(n²), инвертирование шкалы как O(n³) )

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

Оказывается, существует класс методов оптимизации, называемых квазиньютоновскими методами, которые делают именно это.

Квазиньютоновские методы

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

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

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

На данном этапе характер схемы обновления для B остается неясным, поскольку конкретное обновление для B задается с помощью конкретного используемого квазиньютоновского метода. Однако существует одно условие, которое должно быть общим для всех квазиньютоновских методов, а именно гессианское приближение B должно удовлетворять квазиньютоновскому условию (или уравнению секущей):

которое получается из разложения Тейлора первого порядка ∇ f(xᴋ₊₁) относительно ∇f( xᴋ). Кроме того, мы можем проверить положительную определенность нашей аппроксимации Гессе B, предварительно умножив квазиньютоновское условие на Δxᴋᵀ, поэтому наше требование положительной определенности (т.е. условие кривизны) может быть выражено как Δxᴋᵀ yᴋ ›0.
Прежде чем двигаться дальше, давайте сделаем шаг назад и рассмотрим только одно измерение, в котором наша интуиция сильна. Уравнение секущей в одном измерении имеет вид

и условие кривизны удовлетворяется требованием
(f′ᴋ₊₁−f′ᴋ )/(xᴋ₊₁−xᴋ) › 0. Находя f″ и подставляя в метод Ньютона в одном измерении, получаем

Таким образом, здесь у нас есть метод оптимизации, который использует (приблизительное) поведение целевой функции второго порядка, чтобы сходиться быстрее, фактически без каких-либо вторых производных. Вместо этого на каждой итерации k+1 мы строим приближенную обратную вторую производную, используя только величины из предыдущих шагов — в данном случае первую производную из двух предыдущих итераций k и k−1.

Этот метод — аппроксимация метода Ньютона в одном измерении путем замены второй производной ее аппроксимацией конечной разностью — известен как метод секущих, подкласс квазиньютоновских методов.

Теперь вернемся к нашему n-мерному условию квазиньютона (уравнение 4). На первый взгляд кажется, что мы могли бы работать аналогично нашему одномерному случаю: мы можем просто найти Bᴋ₊₁ напрямую и подставить его в итерационный шаг Ньютона. Готово и вычищено, верно?

На самом деле не совсем. Несмотря на обманчивое сходство с нашим одномерным случаем, помните, что B в общем случае является симметричной матрицей n × n с n (n+1)/2 компонентов, тогда как наше уравнение содержит только n компонентов. Это означает, что мы пытаемся найти n(n+1)/2 неизвестных с помощью всего n уравнений, что делает это недоопределенным. система. На самом деле, мы смогли найти единственное решение уравнения секущей только в одном измерении, потому что неизвестные компоненты гессиана, равные 1(1+1)/2 = 1, совпадают с одним уравнением, которое у нас есть. В общем случае существует n(n+1)/2 − n= n(n −1)/2 неизвестных, для которых мы не можем решить.

Здесь на помощь приходят квазиньютоновские методы, в которых метод секущих обобщается на многомерные целевые функции. Вместо аппроксимации второй производной просто с помощью конечной разности, как в методе секущих, квазиньютоновские методы должны накладывать дополнительные ограничения. Однако общая тема по-прежнему актуальна — на каждой итерации k+1 новая аппроксимация Гессе Bᴋ₊₁ получается с использованиемтолько предыдущего градиента информация.

Способы получения этой следующей градиентной аппроксимации порождают различные квазиньютоновские методы. В оставшейся части этой статьи мы обсудим самый популярный из таких методов, называемый BFGS. Алгоритм назван в честь Чарльза Джорджа Бройдена, Роджера Флетчера, Дональда Гольдфарба и Дэвида Шэнно, которые независимо придумали алгоритм в 1970 году.

Квазиньютоновские обновления

Повторение: целью было найти минимум заданной (дважды дифференцируемой) функции (скажем, Розенброка). Эту невозможную задачу удалось решить с помощью градиентного уравнения (grad f =0).

Мы подошли к решению этого уравнения, используя градиентный спуск — начиная с некоторой начальной точки, мы медленно движемся вниз, делая итерационные шаги, пропорциональные отрицательному градиенту функции в каждой точке. Затем Ньютон научил нас, что мы можем сделать гораздо меньше шагов и гораздо быстрее сойтись к минимуму, если мы также рассмотрим поведение функции второго порядка, вычисляя (обратный) гессиан на каждом шаге. Однако за это приходится платить, поскольку вычисление (и инвертирование) гессиана требует много ресурсов. Компромиссом было бы вместо этого просто аппроксимировать гессиана на каждом шаге с учетом квазиньютоновского условия. В одном измерении это равносильно аппроксимации второй производной путем замены ее конечно-разностной аппроксимацией; (так называемый метод секущих). В более чем одном измерении квазиньютоновское условие не определяет однозначно оценку Гессе B, и нам нужно наложить дополнительные ограничения на B, чтобы найти его. .

Для измерений n›1 квазиньютоновское условие не определено. Чтобы определить схему обновления для B, нам потребуется наложить дополнительные ограничения. Одним из таких ограничений, о котором мы уже упоминали, является симметрия и положительная определенность B — эти свойства должны сохраняться при каждом обновлении. Еще одно желательное свойство, которое нам нужно, это чтобы Bᴋ₊₁ был достаточно близок к Bᴋ при каждом обновлении k+1. Формальный способ охарактеризовать понятие «близости» для матриц — это матричная норма, т. е. минимизация ||Bᴋ₊₁−Bᴋ||.

Обновление первого ранга

Эта проблема оказывается эквивалентной обновлению нашего приблизительного гессиана на каждой итерации путем добавления двух симметричных матриц первого ранга(называемых обновлением первого ранга-DFP):

Значения обновления выбираются таким образом, чтобы удовлетворять условиям секущих, что дает:

Обновление второго ранга:

Другой естественной возможностью является использование обновления второго ранга (обновление BFGS) следующим образом:

С огромным удовольствием мы повторяем ту же процедуру, чтобы получить значения u (оказывается таким же, как обновление первого ранга) и вычислить значение второго члена (v), используя то же уравнение секущей: (Любое замечательное квазиньютоновское обновление должно удовлетворяют уравнению секущих)

Используя это условие:

В некотором смысле приведенный выше вывод как процедуру гораздо легче следовать и вспоминать, чем запоминать формулу соуса, полученную при подстановке u и v обратно в уравнение обновления второго ранга B. Тем не менее, у нас есть алгоритм квазиньютона во всей его красе:

Для читателя, ориентированного на практику, приведенное выше уравнение не будет удовлетворительным, если мы не проиллюстрируем, что оно не только работает с функцией Розенброка, но и создает гораздо более быстрые итерации:

Здесь стоит упомянуть дополнительную деталь — инициализацию аппроксимированной матрицы Гессе B. Один из способов — использовать единичную матрицу, и в этом случае первый шаг будет эквивалентен ванильному градиентному спуску, а последующие обновления будут постепенно уточнять его, чтобы приблизиться к обратный гессиан. Другой подход заключается в вычислении и инвертировании истинного гессиана в начальной точке. Это запустит алгоритм с более эффективными шагами, но потребует первоначальных затрат на вычисление истинного гессиана и его инвертирование.

Заключительные замечания

Вот еще несколько визуализаций при вызове «функции черного ящика» scipy.optimize.minimize(method=‘BFGS'), однако вместо того, чтобы рассматривать ее как полный черный ящик, надеюсь, вы теперь посмотрите на улыбающиеся функции Розенброка, полностью осознавая, что BFGS просто итеративно делает положительно-определенное сохранение обновления второго ранга для приближенного обратного гессиана функции потерь, чтобы эффективно найти ее минимум

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

Наконец, вот tldr (слишком долго не читал) для самых ленивых из нас:

В качестве мысленной заметки мы могли бы подумать об этих двух вещах:

  1. Обновление второго ранга было естественным продолжением обновления первого ранга, не можем ли мы использовать приближение третьего ранга? Какие проблемы? Почему BFGS лучше (на сегодняшний день)?
  2. Подумайте о реализации и скорости этого алгоритма. Как гарантировать, что обновление матрицы B всегда будет положительно определенным? Как избежать инверсии на каждой итерации?

Код Python для алгоритмов можно найти здесь: https://github.com/intellist/Quasi_Newton_Optimization

использованная литература

  1. Дж. Nocedal and S. Wright Numerical Optimization, Springer, (2006) — часто используется в качестве учебника.
  2. Э. Зак и П Чонг, Введение в оптимизацию, 4-е издание — дополнительные теоретические аспекты.
  3. Запись в блоге Фабиана Педрегосы (Google AI) о методах Ньютона (2018)
  4. Квазиньютоновские методы в Википедии

Оригинальные документы (из блога Фабиана):

  1. Сходимость класса алгоритмов минимизации двойного ранга
    Бройден, К.Г., 1970. Журнал прикладной математики IMA. Издательство Оксфордского университета.
  2. Новый подход к алгоритмам с переменной метрикой
    Флетчер Р., 1970. Компьютерный журнал. Издательство Оксфордского университета.
  3. Семейство методов переменной метрики, полученных вариационными средствами
    Гольдфарб, Д., 1970. Математика вычислений.
  4. Обусловление квазиньютоновских методов минимизации функций
    Шанно, Д.Ф., 1970. Математика вычислений.