Размер шага адаптивного градиентного спуска, когда вы не можете найти строку

9

У меня есть целевая функция E зависит от значения ϕ(x,t=1.0), где ϕ(x,t)это решение для PDE. Я оптимизируюEпо градиентному спуску на исходное состояние ФДЭ:ϕ(x,t=0.0), То есть я обновляюϕ(x,t=0.0)а затем придется интегрировать PDE, чтобы вычислить мой остаток. Это означает, что если бы мне пришлось искать строку для шага градиентного спуска (назовите егоα), для каждого потенциального значения α Мне пришлось бы заново интегрировать PDE.

В моем случае это было бы слишком дорого. Есть ли другой вариант для шага адаптивного градиентного спуска?

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

Спасибо!

NLi10Me
источник
Я не думаю, что хочу изменить способ интеграции PDE в данный момент, так как для меня это было бы основным переписыванием кода. Кроме того, PDE не так сложен, как то, что мне приходится решать его на очень плотной сетке в пространстве-времени, так как мне требуется очень высокая точность чисел.
NLi10Me
С другой стороны, метод BB (с которым я не был знаком) кажется довольно хорошим; все, что мне нужно сделать, это отслеживать состояние и градиент предыдущей итерации, и я получаю приближение второго порядка ... это кажется очень хорошим. Тем не менее, вывод предполагает выпуклый квадратик, и моя проблема почти наверняка нет. Хотя я также нахожу (и доволен) локальные, а не глобальные минимумы. Знаете ли вы, насколько хорошо BB справился с очень большими задачами?
NLi10Me
Полагаю, что я имел в виду под локальными минимумами, так это то, что в окрестности локального минимума какая-то функция не является квадратичной? Я думаю, что мое начальное состояниеϕ(0)(x,t=0.0)достаточно близко к минимуму, так как во многих случаях я получаю плавную сходимость даже при статическом размере шага. Таким образом, несмотря на то, что он очень большой по размеру, и, в общем, если вы рассматриваете все пространство поиска, проблема является невыпуклой / неквадратичной, может ли BB по-прежнему быть хорошим выбором без поиска строки?
NLi10Me
Другие "ингредиенты" для E экспериментальные данные изображения. ϕ(x,t=1.0)пытается деформировать одно изображение, чтобы «соответствовать» другому (измеряется с помощью некоторого функционала соответствия, такого как норма L2, интегрированного в воксели). Для некоторых пар изображений я получаю плавную конвергенцию с (мой текущий выбор) статическим размером шага. Для других пар изображений я получаю много колебаний. Система должна быть полностью автоматизирована, поэтому я не могу вернуться и вручную отредактировать размер шага для проблемных пар изображений.
NLi10Me
Правильно, мне нужно решить сопряженную систему, чтобы получить градиент (это более неприятная система и занимает больше времени). Хорошо, я думаю, что я попробую BB с поиском обратной линии. Спасибо очень много для консультации; моих советников часто трудно достать, и многие из них интересуются не столько реализацией, сколько просто моделью. Я считаю, что численные методы - это ключевой компонент для демонстрации того, хороша ли модель в первую очередь, поэтому еще раз спасибо, я действительно ценю это.
NLi10Me

Ответы:

15

Я начну с общего замечания: информация первого порядка (т. Е. Использование только градиентов, которые кодируют наклон) может дать вам только информацию о направлении: она может сказать вам, что значение функции уменьшается в направлении поиска, но не в течение какого времени , Чтобы решить, как далеко идти вдоль направления поиска, вам нужна дополнительная информация (градиентный спуск с постоянной длиной шага может не сработать даже для выпуклых квадратичных задач). Для этого у вас есть два варианта:

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

Если, как вы пишете, у вас нет доступа ко вторым производным, и оценка функции объектива стоит очень дорого, ваша единственная надежда - пойти на компромисс: используйте достаточно приблизительную информацию второго порядка, чтобы получить подходящую длину шага кандидата, такую ​​что строка поиск нужен только O(1) оценки (т. е. не более (небольшая) постоянная кратность усилий, необходимых для оценки градиента).

Одной из возможностей является использование длины шага Барзилай - Борвейна (см., Например, Флетчер: О методе Барзилай-Борвейна . Оптимизация и управление с приложениями, 235–256, Appl. Optim., 96, Springer, New York, 2005 ). Идея состоит в том, чтобы использовать конечно-разностную аппроксимацию кривизны вдоль направления поиска, чтобы получить оценку размера шага. В частности, выберитеα0>0 произвольный набор g0:=f(x0) а затем для k=0,...:

  1. Набор sk=αk1gk а также xk+1=xk+sk
  2. оценивать gk+1=f(xk+1) и установить yk=gk+1gk
  3. Набор αk+1=(yk)Tyk(yk)Tsk

Можно показать, что этот выбор сходится (на практике очень быстро) для квадратичных функций, но сходимость не является монотонной (т. Е. Значение функцииf(xk+1) может быть больше чем f(xk), но только время от времени; см. график на стр. 10 в статье Флетчера). Для неквадратичных функций вам необходимо объединить это с поиском строк, который необходимо изменить, чтобы справиться с немонотонностью. Одна возможность выбораσk(0,αk1) (например, путем возврата), так что

f(xkσkgk)maxmax(kM,1)jkf(xj)γσk(gk)Tgk,
где - типичный параметр Armijo, а управляет степенью монотонности (например, ). Есть также вариант, в котором вместо значений функции используются значения градиента, но в вашем случае вычисление градиента даже дороже, чем функции, поэтому здесь это не имеет смысла. (Примечание: Вы, конечно, можете попытаться слепо принять длину шага BB и довериться удаче, но если вам нужна какая-либо надежность - как вы написали в своих комментариях - это было бы действительно плохой идеей.)γ(0,1)MM=10

Альтернативный (и, на мой взгляд, гораздо лучший) подход будет использовать это приближение конечных разностей уже при расчете направления поиска; это называется квазиньютоновским методом . Идея состоит в том, чтобы постепенно построить аппроксимацию гессиана , используя различия градиентов. Например, вы можете взять (единичная матрица) и для решить и установить с помощью как указано выше, и . (Это называется Broyden update2f(xk)H0=Idk=0,

(1)Hksk=gk,
Hk+1=Hk+(ykHksk)T(sk)T(sk)Tsk
ykxk+1=xk+skи редко используется на практике; Лучшим, но немного более сложным обновлением является обновление BFGS , для которого - и больше информации - я обращаюсь к книге « Численная оптимизация» Носедала и Райта .) Недостатком является то, что а) для этого потребуется решение линейной системы на каждом этапе (но только размером неизвестного, который в вашем случае является начальным условием, следовательно, усилия должны основываться на решении PDE для получения градиента, а также существуют правила обновления для приближений обратного гессиана, которые требуют вычисления только одной матрицы -векторный продукт) и б) вам все еще нужен поиск строки, чтобы гарантировать сходимость ...

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

qk(s)=12sTHks+sTgk.
sΔkΔkσk
ρk:=f(xk)f(xk+sk)f(xk)qk(sk)
фактического и прогнозируемого уменьшения значения функции. Если очень мало, ваша модель была плохой, и вы отбрасываете и попробуйте снова с . Если близко к , ваша модель хороша, и вы устанавливаете и увеличиваете . В противном случае вы просто устанавливаете и оставляете покое. Чтобы вычислить фактический минимизатор изρkskΔk+1<Δkρk1xk+1=xk+skΔk+1>Δkxk+1=xk+skΔkskminsΔkqk(s)существует несколько стратегий, позволяющих избежать решения проблемы полной ограниченной оптимизации; мой фаворит - усеченный метод компьютерной графики Стейхауга . Для более подробной информации, я снова обращаюсь к Nocedal и Wright.
Кристиан Клэйсон
источник
Я только сейчас смотрю на это снова и понимаю, что у меня есть вопрос. На третьем шаге для метода BB у вас есть ; где и . Числитель и знаменатель в выражении для выглядят как внутренние произведения. В моем случае , где - векторное пространство с нетривиальной римановой метрикой: K. То есть . Влияет ли это на определение ? αk+1=(yk)Tyk(yk)Tskyk=gk+1gksk=αk1gkαk+1gkVVgk,gkV=gk,KgkL2αk+1
NLi10Me
Да, если у вас нетривиальная структура векторного пространства, вы должны соблюдать это в алгоритмах. В частности, следует различать внутренние произведения двух функций в одном пространстве (например, и ) и произведения двойственности между функцией в пространстве и единицей в двойственном пространстве (например, и ) - для последнего нужно включить отображение Рисса, чтобы сначала превратить его во внутренний продукт. (Это можно интерпретировать как предварительную подготовку.)ykykskyk
Кристиан Клэйсон,
Доктор Клэйсон, я представлю на ISBI 2017 статью с подробным описанием некоторых экспериментов, которые я провел, используя метод поиска линии BB + для задачи регистрации диффеоморфного изображения. Хотели бы вы быть включены в качестве автора на рукопись? Я еще не написал это, но у меня есть большинство экспериментов, либо завершенных, либо в стадии выполнения. Пожалуйста, дайте мне знать.
NLi10Me
@ NLi10Me Спасибо за любезное предложение, но я не сделал ничего такого, что заслуживало бы соавторства - все, что я написал, - это стандартный учебник. Если вы сильно к этому относитесь, вы можете поблагодарить меня за «полезные замечания по поводу (что бы это ни помогло)», но даже этого не потребуется. Знать, что то, что я написал, было полезно, достаточно!
Кристиан Клэйсон
1
Извините, вы правы, это опечатка - исправлено! (Условие Армихо часто записывается как , где - направление поиска - не обязательно отрицательное градиент - и размер шага, который должен прояснить, что происходит.)f(x+σs)f(x)γf(x)T(σs)sσ
Кристиан Клэйсон