При (неограниченной) минимизации поиск строки с обратным отслеживанием , схема поиска, основанная на условии Армийо – Гольдштейна , представляет собой метод поиска строки для определения величины перемещения в заданном направлении поиска . Он включает в себя начало с относительно большой оценки размера шага для движения вдоль направления поиска и итеративное уменьшение размера шага (т. Е. «Обратное отслеживание») до тех пор, пока не будет наблюдаться уменьшение целевой функции , адекватно соответствующее уменьшению, которое ожидается , основанный на локальном градиенте целевой функции.
Поиск строки с возвратом обычно используется для градиентного спуска , но его также можно использовать в других контекстах. Например, он может быть использован с методом Ньютона, если матрица Гесса является положительно определенной .
Мотивация
Учитывая исходную позицию и направление поиска , задача линейного поиска - определить размер шага что адекватно снижает целевую функцию (предполагается т.е. непрерывно дифференцируемые ), т. е. найти значение что уменьшает относительно . Однако обычно нежелательно тратить значительные ресурсы на поиск значения чтобы точно минимизировать . Это связано с тем, что вычислительные ресурсы, необходимые для нахождения более точного минимума в одном конкретном направлении, могут вместо этого использоваться для определения лучшего направления поиска. Как только улучшенная начальная точка была идентифицирована с помощью линейного поиска, другой последующий линейный поиск обычно будет выполняться в новом направлении. Таким образом, цель состоит в том, чтобы просто определить ценность который обеспечивает разумное улучшение целевой функции, а не нахождение фактического минимизирующего значения .
Поиск строки с возвратом начинается с большой оценки и многократно сжимает его. Сжатие продолжается до тех пор, пока не будет найдено значение, достаточно маленькое, чтобы обеспечить уменьшение целевой функции, адекватно соответствующее ожидаемому уменьшению на основе градиента локальной функции.
Определите локальный наклон функции по направлению поиска в виде (где обозначает скалярное произведение ). Предполагается, что - вектор, для которого возможно некоторое локальное убывание, т. е. предполагается, что .
На основе выбранного параметра управления , условие Армийо – Гольдштейна проверяет, действительно ли пошаговое движение из текущей позиции на измененную позицию достигает адекватно соответствующего уменьшения целевой функции. Условие выполнено, см. Armijo (1966) , если
Это условие, при правильном использовании как часть поиска строки, может гарантировать, что размер шага не будет чрезмерно большим. Однако одного этого условия недостаточно, чтобы гарантировать, что размер шага будет почти оптимальным, поскольку любое значение который достаточно мал, будет удовлетворять условию.
Таким образом, стратегия поиска строки с возвратом начинается с относительно большого размера шага и многократно сжимает его в раз. до тех пор, пока не будет выполнено условие Армийо – Гольдштейна.
Поиск завершится после конечного числа шагов для любых положительных значений а также которые меньше 1. Например, Armijo использовал 1 ⁄ 2 для обоих а также в Армийо (1966) .
Алгоритм
Это условие взято из Armijo (1966) . Начиная с максимального возможного значения размера шага, используя параметры управления поиском а также , алгоритм поиска строки с возвратом можно выразить следующим образом:
- Набор и счетчик итераций .
- Пока не будет выполнено условие, многократно увеличивать и установить
- Возвращаться как решение.
Другими словами, уменьшить с коэффициентом в каждой итерации, пока не будет выполнено условие Армиджо – Гольдштейна.
Минимизация функций с помощью поиска по строке с возвратом на практике
На практике вышеупомянутый алгоритм обычно повторяется для создания последовательности , , чтобы сходиться к минимуму, при условии, что такой минимум существует и выбирается соответствующим образом на каждом шаге. Для градиентного спуска выбран как .
Значение для которое удовлетворяет условию Армийо – Гольдштейна, зависит от а также , и поэтому ниже обозначается . Это также зависит от, , а также конечно, хотя эти зависимости можно оставить неявными, если предполагается, что они исправлены в отношении проблемы оптимизации.
Таким образом, подробные шаги см. В Armijo (1966) , Bertsekas (2016) :
- Выберите начальную отправную точку и установить счетчик итераций .
- Пока не будет выполнено какое-либо условие остановки, выберите направление спуска. , приращение , и обновите позицию на .
- Возвращаться как минимизирующая позиция и как минимум функции.
Чтобы гарантировать хорошее поведение, необходимо, чтобы некоторые условия выполнялись . Грубо говоря не должен быть слишком далеко от . Точная версия такова (см., Например, Bertsekas (2016) ). Есть константы так что выполняются следующие два условия:
- Для всех n, . Здесь,является евклидова норма о. (Это гарантирует, что если, то также . В более общем смысле, если, то также .) Более строгий вариант требует также обратного неравенства: для положительной постоянной .
- Для всех n, . (Это условие гарантирует, что направления а также похожи.)
Нижняя граница скорости обучения
Это решает вопрос о том, существует ли систематический способ найти положительное число. - в зависимости от функции f точка и направление спуска - чтобы все скорости обучения удовлетворяют условию Армийо. Когда, мы можем выбрать в порядке , где - локальная константа Липшица для градиента рядом с точкой (см. липшицевость ). Если функция, тогда близка к гессиану функции в точке . См. Armijo (1966) для более подробной информации.
Верхняя граница скорости обучения
В той же ситуации, когда , интересный вопрос заключается в том, насколько большие скорости обучения могут быть выбраны в условии Армийо (то есть, когда нет ограничения на в разделе «Минимизация функций с помощью поиска по строке с возвратом на практике»), так как большая скорость обучения при ближе к предельной точке (если существует) может ускорить сходимость. Например, в условиях Вульфа нет упоминания о но вводится другое условие, называемое условием кривизны.
Показано, что существует верхняя граница скорости обучения, если требуется построенная последовательность сходится к невырожденной критической точке , см. Truong & Nguyen (2020) : скорость обучения должна быть ограничена сверху примерно. Здесь H - гессиан функции в предельной точке,является его обратным , и- норма линейного оператора . Таким образом, этот результат применяется, например, при использовании поиска строки с возвратом для функций Морзе . Обратите внимание, что в измерении 1 является числом, и поэтому эта верхняя граница имеет тот же размер, что и нижняя граница в разделе «Нижняя граница для скорости обучения».
С другой стороны, если предельная точка вырождена, скорость обучения может быть неограниченной. Например, модификация линейного поиска с обратным отслеживанием, названная неограниченным градиентным спуском с обратным отслеживанием (см. Truong & Nguyen (2020) ), позволяет скорости обучения быть в размере, где является константой. Эксперименты с простыми функциями, такими как показывают, что неограниченный градиентный спуск с обратным отслеживанием сходится намного быстрее, чем базовая версия в разделе «Минимизация функций с использованием поиска по строке с возвратом на практике».
Эффективность времени
Аргументом против использования строкового поиска с возвратом, в частности при крупномасштабной оптимизации, является то, что выполнение условия Armijo обходится дорого. Существует способ (так называемое двустороннее отслеживание с возвратом) с хорошими теоретическими гарантиями, который был протестирован с хорошими результатами в глубоких нейронных сетях , см. Truong & Nguyen (2020) . Заметим, что если последовательность сходится (по желанию, если использовать метод итеративной оптимизации), то последовательность скоростей обучения должен мало отличаться, когда n достаточно велико. Поэтому в поисках, если всегда начинать с , можно было бы потратить много времени, если бы выяснилось, что последовательность находится далеко от . Вместо этого нужно искать начиная с . Второе наблюдение: может быть больше, чем , а значит, нужно позволить увеличить скорость обучения (а не просто уменьшить, как в разделе Алгоритм). Вот подробный алгоритм двустороннего поиска с возвратом: На шаге n
- Набор . Набор и счетчик итераций .
- (Увеличьте скорость обучения, если выполняется условие Армийо.) Если , то пока это условие и условие, что удовлетворены, повторно устанавливаются и увеличиваем j.
- (В противном случае уменьшите скорость обучения, если условие Армийо не выполняется.) Если наоборот , то до выполнения условия многократно увеличивать и установить
- Возвращаться для скорости обучения .
(В Nocedal & Wright (2000) можно найти описание алгоритма с пунктами 1), 3) и 4) выше, который не тестировался в DNN до цитируемой статьи.)
Можно дополнительно сэкономить время за счет гибридной смеси между двусторонним обратным отслеживанием и базовым алгоритмом стандартного градиентного спуска. Эта процедура также имеет хорошую теоретическую гарантию и хорошие результаты испытаний. Грубо говоря, мы запускаем двусторонний поиск с возвратом несколько раз, а затем используем скорость обучения, полученную в результате, без изменений, за исключением случаев, когда значение функции увеличивается. Вот как это делается. Заранее выбирают число N, а число.
- Установить счетчик итераций j = 0.
- На ступеньках , используйте двусторонний поиск с возвратом.
- На каждом шаге k в множестве : Набор . Если, тогда выбирай а также . (Итак, в этом случае используйте скорость обучения без изменений.) В противном случае, если , используйте двусторонний поиск с возвратом. Увеличьте k на 1 и повторите.
- Увеличьте j на 1.
Теоретическая гарантия (для градиентного спуска)
По сравнению с условиями Вульфа, которые являются более сложными, условие Армийо имеет лучшую теоретическую гарантию. Действительно, до сих пор поиск линии с возвратом и его модификации являются наиболее теоретически гарантированными методами среди всех алгоритмов численной оптимизации, касающихся сходимости к критическим точкам и избегания седловых точек , см. Ниже.
Критические точки - это точки, в которых градиент целевой функции равен 0. Локальные минимумы являются критическими точками, но есть критические точки, которые не являются локальными минимумами. Пример - седловые точки. Седловые точки - это критические точки, в которых есть хотя бы одно направление, в котором функция является (локальным) максимумом. Следовательно, эти точки далеки от локальных минимумов. Например, если функция имеет хотя бы одну седловую точку, она не может быть выпуклой . Значимость седловых точек для алгоритмов оптимизации заключается в том, что при крупномасштабной (т. Е. Многомерной) оптимизации можно увидеть больше седловых точек, чем минимумов, см. Bray & Dean (2007) . Следовательно, хороший алгоритм оптимизации должен уметь избегать седловых точек. В условиях глубокого обучения также преобладают седловые точки, см. Dauphin et al. (2014) . Таким образом, для применения в глубоком обучении нужны результаты для невыпуклых функций.
Для сходимости к критическим точкам: например, если функция стоимости является реальной аналитической функцией , то в Absil, Mahony & Andrews (2005) показано , что сходимость гарантирована. Основная идея заключается в использовании неравенства Лоясевича, которым обладает реальная аналитическая функция. Для негладких функций, удовлетворяющих неравенству Лоясевича , указанная выше гарантия сходимости расширена, см. Attouch, Bolte & Svaiter (2011) . В Bertsekas (2016) есть доказательство того, что для каждой последовательности, построенной с помощью поиска строки с возвратом, точка кластера (то есть предел одной подпоследовательности , если подпоследовательность сходится) является критической точкой. Для случая функции с не более чем счетным числом критических точек (например, функция Морса ) и компактными подуровнями , а также с липшицевым непрерывным градиентом, когда используется стандартный GD со скоростью обучения <1 / L (см. Раздел о стохастическом градиенте спуск), то сходимость гарантирована, см., например, главу 12 в Lange (2013) . Здесь предположение о компактных подуровнях состоит в том, чтобы убедиться, что мы имеем дело только с компактными множествами евклидова пространства. В общем случае, когда f предполагается только равными имеют не более чем счетное число критических точек, сходимость гарантирована, см. Truong & Nguyen (2020) . В той же ссылке аналогичная сходимость гарантируется для других модификаций поиска по строке с обратным отслеживанием (таких как неограниченный градиентный спуск с обратным отслеживанием, упомянутый в разделе «Верхняя граница скорости обучения»), и даже если функция имеет несчетное количество критических точек, все же можно вывести некоторые нетривиальные факты о поведении сходимости. В стохастической настройке, при том же предположении, что градиент является липшицевым, и используется более ограниченная версия (требующая, кроме того, чтобы сумма скоростей обучения была бесконечной, а сумма квадратов скоростей обучения была конечной) схемы убывающей скорости обучения (см. раздел Стохастический градиентный спуск) и, кроме того, функция строго выпуклая, то сходимость устанавливается в хорошо известном результате Роббинса и Монро (1951) , см. Бертсекас и Цициклис (2006) для обобщений на менее ограничительные версии Уменьшающейся скорости обучения. схема. Ни один из этих результатов (для невыпуклых функций) до сих пор не был доказан ни для одного другого алгоритма оптимизации. [ необходима цитата ]
Во избежание седловых точек: например, если градиент функции стоимости является липшицевым и выбирается Стандартный GD со скоростью обучения <1 / L, то со случайным выбором начальной точки (точнее, вне набора с нулевой мерой Лебега ) построенная последовательность не будет сходиться к невырожденной седловой точке (доказано в Lee et al. (2016) ), и в более общем плане также верно, что построенная последовательность будет не сходятся к вырожденной седловой точке (доказано в Panageas & Piliouras (2017) ). При том же предположении, что градиент является липшицевым и используется схема убывающей скорости обучения (см. Раздел Стохастический градиентный спуск), то избегание седловых точек установлено в Panageas, Piliouras & Wang (2019) .
Особый случай: (Стандартный) Стохастический градиентный спуск
Хотя тривиально упомянуть, что если градиент функции стоимости является непрерывным по Липшицу с константой Липшица L, то при выборе постоянной скорости обучения и размера 1 / L возникает особый случай поиска строки с обратным отслеживанием (для градиентный спуск). Это использовалось, по крайней мере, в Armijo (1966) . Однако эта схема требует наличия хорошей оценки L, в противном случае, если скорость обучения слишком велика (относительно 1 / L), то схема не имеет гарантии сходимости. Можно увидеть, что пойдет не так, если функция стоимости будет сглаживанием (около точки 0) функции f (t) = | t |. Однако такая хорошая оценка трудна и трудоемка для больших размеров. Кроме того, если градиент функции не является глобально липшицевым, то эта схема не имеет гарантии сходимости. Например, это похоже на упражнение в Bertsekas (2016) для функции стоимости и для любой выбранной постоянной скорости обучения со случайной начальной точкой последовательность, построенная по этой специальной схеме, не сходится к глобальному минимуму 0.
Если кто-то не заботится об условии, что скорость обучения должна быть ограничена 1 / L, то эта специальная схема использовалась намного раньше, по крайней мере, с 1847 года Коши , которую можно назвать стандартной GD (чтобы отличить от SGD). В настройке Stochastic (например, в настройке мини-пакета в Deep Learning ) стандартный GD называется стохастическим градиентным спуском или SGD.
Даже если функция стоимости имеет глобально непрерывный градиент, хорошая оценка константы Липшица для функций стоимости в глубоком обучении может оказаться невыполнимой или нежелательной, учитывая очень большие размеры глубинных нейронных сетей . Следовательно, существует метод тонкой настройки скорости обучения при применении Standard GD или SGD. Один из способов - выбрать несколько скоростей обучения из поиска по сетке в надежде, что некоторые из скоростей обучения могут дать хорошие результаты. (Однако, если функция потерь не имеет глобального липшицевого градиента, то пример свыше показывает, что поиск по сетке не может помочь.) Другой способ - это так называемый адаптивный стандартный GD или SGD, некоторые представители - Adam, Adadelta, RMSProp и так далее, см. Стохастический градиентный спуск . В адаптивном стандартном GD или SGD скорости обучения могут изменяться на каждом шаге n итерации, но другим способом, чем при поиске линии с возвратом для градиентного спуска. По-видимому, было бы дороже использовать поиск по строке с возвратом для градиентного спуска, так как нужно выполнять поиск по петле до тех пор, пока не будет выполнено условие Armijo, в то время как для адаптивных стандартных GD или SGD поиск по петле не требуется. Большинство из этих адаптивных стандартных GD или SGD не имеют свойства спуска., для всех n, как поиск строки с возвратом для градиентного спуска. Лишь немногие из них обладают этим свойством и обладают хорошими теоретическими свойствами, но они оказываются частными случаями поиска строки с возвратом или, в более общем смысле, условия Армийо Armijo (1966) . Первый - это когда кто-то выбирает постоянную скорость обучения <1 / L, как упоминалось выше, если можно иметь хорошую оценку L. Второй - это так называемая скорость обучения диминшинга, используемая в хорошо известной статье Robbins & Монро (1951) , если снова функция имеет глобально непрерывный липшицев градиент (но константа Липшица может быть неизвестна) и скорость обучения сходится к 0.
Резюме
Таким образом, поиск строки с обратным отслеживанием (и модификации) - это метод, который легко реализовать, применим для очень общих функций, имеет очень хорошую теоретическую гарантию (как для сходимости к критическим точкам, так и для предотвращения седловых точек) и хорошо работает на практике. Несколько других методов, которые имеют хорошую теоретическую гарантию, такие как Уменьшение скорости обучения или Стандартный GD со скоростью обучения <1 / L - оба требуют, чтобы градиент целевой функции был непрерывным по Липшицу, оказываются частным случаем поиска строки с обратным отслеживанием или удовлетворяют условию Армийо. Несмотря на то, что априори требуется, чтобы функция стоимости была непрерывно дифференцируемой для применения этого метода, на практике можно успешно применить этот метод также для функций, которые непрерывно дифференцируются на плотном открытом подмножестве, таком как или же . Последние функции появляются в глубоких нейронных сетях .
Смотрите также
- Градиентный спуск
- Стохастический градиентный спуск
- Условия Вульфа
Рекомендации
- Absil, PA; Mahony, R .; Эндрюс, Б. (2005). «Сходимость итераций методов спуска для аналитических функций стоимости» . SIAM J. Optim. 16 (2): 531–547. DOI : 10.1137 / 040605266 .
- Армийо, Ларри (1966). «Минимизация функций, имеющих липшицевы первые частные производные» . Pacific J. Math . 16 (1): 1–3. DOI : 10.2140 / pjm.1966.16.1 .
- Attouch, H .; Bolte, J .; Свайтер, Б.Ф. (2011). «Сходимость методов спуска для полуалгебраических и ручных задач: проксимальные алгоритмы, расщепление вперед – назад и регуляризованные методы Гаусса – Зейделя» . Математическое программирование . 137 (1–2): 91–129. DOI : 10.1007 / s10107-011-0484-9 .
- Бертсекас, Дмитрий П. (2016), Нелинейное программирование , Athena Scientific , ISBN 978-1886529052
- Бертсекас, Д.П .; Цициклис, Дж. Н. (2006). «Сходимость градиентов в градиентных методах с ошибками» . SIAM J. Optim. 10 (3): 627–642. DOI : 10.1137 / S1052623497331063 .
- Брей, Эй Джей; Дин, Д.С. (2007). «Статистика критических точек гауссовских полей на пространствах большой размерности» . Письма с физическим обзором . 98 (15): 150–201. arXiv : cond-mat / 0611023 . Bibcode : 2007PhRvL..98o0201B . DOI : 10.1103 / PhysRevLett.98.150201 . PMID 17501322 .
- Дофин, Ю.Н. Pascanu, R .; Gulcehre, C .; Чо, К .; Ganguli, S .; Бенджио, Ю. (2014). «Выявление и решение проблемы седловой точки в многомерной невыпуклой оптимизации» . NeurIPS . 14 : 2933–2941. arXiv : 1406,2572 .
- Ланге, К. (2013). Оптимизация . Нью-Йорк: Публикации Springer-Verlag . ISBN 978-1-4614-5838-8.
- Деннис, JE ; Шнабель, РБ (1996). Численные методы безусловной оптимизации и нелинейных уравнений . Филадельфия: Публикации SIAM . ISBN 978-0-898713-64-0.
- Ли, Джей Ди; Simchowitz, M .; Иордания, Мичиган; Рехт, Б. (2016). «Градиентный спуск сводится только к минимайзерам» . Труды исследований машинного обучения . 49 : 1246–1257.
- Нокедаль, Хорхе ; Райт, Стивен Дж. (2000), Численная оптимизация , Springer-Verlag , ISBN 0-387-98793-2
- Panageas, I .; Пилюрас, Г. (2017). «Градиентный спуск сходится только к минимизаторам: неизолированным критическим точкам и инвариантным областям» (PDF) . Конференция «Инновации в теоретической информатике» : 2: 1–2: 12. DOI : 10,4230 / LIPIcs.ITCS.2017.2 .
- Panageas, I .; Piliouras, G .; Ван, X. (2019). «Методы первого порядка почти всегда избегают седловых точек: случай исчезающих размеров шага» (PDF) . NeurIPS . arXiv : 1906.07772 .
- Роббинс, H .; Монро, С. (1951). «Метод стохастической аппроксимации» . Анналы математической статистики . 22 (3): 400–407. DOI : 10.1214 / АОМ / 1177729586 .
- Чыонг, TT; Нгуен, Х.-Т. (6 сентября 2020 г.). "Метод обратного градиентного спуска и некоторые приложения в крупномасштабной оптимизации. Часть 2: Алгоритмы и эксперименты" . Прикладная математика и оптимизация : 30. DOI : 10.1007 / s00245-020-09718-8 .CS1 maint: дата и год ( ссылка )