Поиск строки с возвратом - Backtracking line search

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

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

Мотивация

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

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

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

Основываясь на выбранном параметре управления , условие Армийо – Гольдштейна проверяет, приводит ли пошаговое перемещение от текущего положения к измененному положению адекватно соответствующее уменьшение целевой функции. Условие выполнено, см. Armijo (1966) , если

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

Таким образом, стратегия поиска строки с возвратом начинается с относительно большого размера шага и многократно сжимает его в несколько раз, пока не будет выполнено условие Армийо – Гольдштейна.

Поиск завершится после конечного числа шагов для любых положительных значений и меньше 1. Например, Армийо использовал 12 для обоих и в Армийо (1966) .

Алгоритм

Это условие взято из Armijo (1966) . Начиная с максимального возможного значения размера шага , используя параметры управления поиском и , алгоритм поиска строки с возвратом может быть выражен следующим образом:

  1. Набор и счетчик итераций .
  2. Пока условие не будет выполнено, многократно увеличивайте и устанавливайте
  3. Вернитесь как решение.

Другими словами, уменьшайте коэффициент в каждой итерации до тех пор, пока не будет выполнено условие Армиджо – Гольдштейна.

Минимизация функций с помощью поиска по строке с возвратом на практике

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

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

Таким образом, подробные шаги см. В Armijo (1966) , Bertsekas (2016) :

  1. Выберите начальную начальную точку и установите счетчик итераций .
  2. Пока не будет выполнено какое-либо условие остановки, выберите направление спуска , увеличьте и обновите положение до .
  3. Возвратитесь как минимизирующая позиция и как минимум функции.

Чтобы обеспечить хорошее поведение, необходимо, чтобы некоторые условия выполнялись . Грубо говоря не должно быть слишком далеко . Точная версия такова (см., Например, Bertsekas (2016) ). Существуют константы, чтобы выполнялись следующие два условия:

  1. Для всех п . Здесь есть евклидова норма о . (Это гарантирует, что если , то тоже . В более общем смысле, если , то тоже .) Более строгая версия требует также обратного неравенства: для положительной константы .
  2. Для всех п . (Это условие гарантирует, что направления и подобны.)

Нижняя граница скорости обучения

Это решает вопрос, существует ли систематический способ нахождения положительного числа - в зависимости от функции f, точки и направления спуска - так, чтобы все скорости обучения удовлетворяли условию Армийо. Когда , мы можем выбрать в порядке , где - локальная константа Липшица для градиента вблизи точки (см. Непрерывность Липшица ). Если функция есть , то она близка к гессиану функции в точке . См. Armijo (1966) для более подробной информации.

Верхняя граница скорости обучения

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

Показано, что верхняя граница скорости обучения существует, если нужно, чтобы построенная последовательность сходилась к невырожденной критической точке , см. Truong & Nguyen (2020) : Скорость обучения должна быть ограничена сверху примерно на . Здесь H - гессиан функции в предельной точке, - обратный к ней и - норма линейного оператора . Таким образом, этот результат применяется, например, при использовании поиска строки с возвратом для функций Морзе . Обратите внимание, что в размерности 1 это число, и, следовательно, эта верхняя граница имеет тот же размер, что и нижняя граница в разделе «Нижняя граница для скорости обучения».

С другой стороны, если предельная точка вырождена, скорость обучения может быть неограниченной. Например, модификация линейного поиска с обратным отслеживанием, названная неограниченным градиентным спуском с обратным отслеживанием (см. Truong & Nguyen (2020) ), позволяет скорости обучения быть в размере , где - константа. Эксперименты с простыми функциями, например, показывают, что неограниченный градиентный спуск с обратным отслеживанием сходится намного быстрее, чем базовая версия в разделе «Минимизация функций с использованием обратного поиска по строке на практике».

Эффективность времени

Аргументом против использования строкового поиска с возвратом, в частности при крупномасштабной оптимизации, является то, что выполнение условия Armijo обходится дорого. Существует способ (так называемое двустороннее отслеживание с возвратом) с хорошими теоретическими гарантиями, который был протестирован с хорошими результатами в глубоких нейронных сетях , см. Truong & Nguyen (2020) . (Там также можно найти хорошие / стабильные реализации условия Armijo и его комбинации с некоторыми популярными алгоритмами, такими как Momentum и NAG, на таких наборах данных, как Cifar10 и Cifar100.) Наблюдается, что если последовательность сходится (как желательно, когда используется метода итеративной оптимизации), то последовательность скоростей обучения должна мало отличаться, когда n достаточно велико. Следовательно, при поиске , если всегда начинать с , можно потратить много времени, если окажется, что последовательность находится далеко от . Вместо этого следует искать , начиная с . Второе наблюдение - то, что может быть больше , и, следовательно, следует позволить увеличить скорость обучения (а не только уменьшить, как в разделе «Алгоритм»). Вот подробный алгоритм двустороннего поиска с возвратом: На шаге n

  1. Установить . Набор и счетчик итераций .
  2. (Увеличьте скорость обучения, если условие Армиджо выполнено.) Если , то, пока это условие и условие, которые выполнены, повторно устанавливают и увеличивают j.
  3. (В противном случае уменьшите скорость обучения, если условие Armijo не выполняется.) Если наоборот , то до тех пор, пока условие не будет выполнено, многократно увеличивайте и устанавливайте
  4. Возврат к скорости обучения .

Nocedal & Wright (2000) можно найти описание алгоритма с пунктами 1), 3) и 4) выше, который не тестировался в DNN до цитируемой статьи.)

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

  1. Установить счетчик итераций j = 0.
  2. На шагах используйте двусторонний поиск с возвратом.
  3. На каждом шаге k в наборе : Set . Если , то выбираем и . (Итак, в этом случае используйте скорость обучения без изменений.) В противном случае, если , используйте двусторонний поиск с возвратом. Увеличьте k на 1 и повторите.
  4. Увеличьте 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.

Практические аспекты использования в стохастической настройке и реализации в DNN

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

1) Стохастическая оптимизация:

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

В общем, очень сложно вычислить математическое ожидание, особенно при работе, например, с DNN (см. Следующую часть). Следовательно, мы можем сделать только следующее:

На шаге n: выберите случайным образом переменные (по отношению к заданному распределению) и замените (неизвестную) функцию приближением .

Нам нужно изменить поиск линии возврата Armijo следующим образом: Затем выбирается направление спуска и скорость обучения Armijo выбирается относительно функции .

Отмечается, что в целом можно изменить. Есть работы, которые позволяют приумножить. Следующий пример объясняет мотивацию такой схемы (также см. Теоретическое обоснование позже). Однако в разделе о реализации в DNN будет объяснено, что при реализации этой схемы возникают трудности / не очень хорошая производительность.

Пример 1. Рассмотрим простую функцию , которая является выпуклой с единственной критической точкой . Напомним нормальное распределение . Тогда где - случайная величина с распределением . Затем можно проверить с помощью Python, что если мы выберем и для всего шага n и запустим поиск строки с возвратом Armijo с максимальной скоростью обучения , в этой настройке, как описано выше, то у нас будет расхождение (не конвергенция, как можно было бы надеяться на это тоже простая выпуклая функция)! [Здесь происходит то, что, хотя и мало, существует ненулевая вероятность случайного значения is , и в этом случае поиск по строке с возвратом Armijo будет сильно отталкиваться от точки 0!]

Другой способ, заимствованный из классической работы Роббинса и Монро (1951) , в SGD сохранить постоянным (даже можно выбрать постоянное значение 1), но пусть скорость обучения будет равна 0. [Даже если случайное значение равно , поскольку скорость обучения все меньше и меньше, эта схема будет отталкивать от 0 меньше, чем с возвратом.] Хотя эта схема хорошо работает и для этого примера, опять же при настройке DNN экспериментальные результаты не очень хороши.

Стоит также отметить, что если использовать SGD и поддерживать k_n постоянным, но при этом постоянные скорости обучения, то можно наблюдать расхождение даже для некоторых значений скоростей обучения, для которых есть гарантия сходимости для F (x). То, что упоминается в Примере 1, не является ошибкой самого Backtracking, но также и SGD, наиболее изученного алгоритма оптимизации.

Пример 1 '. Та же функция F (x) и распределение . Выберите и для всего шага n. Обратите внимание , что функция Р (х) с . Следовательно, согласно классической теории, для скорости обучения SGD с постоянной скоростью обучения будет сходиться для F (x). Однако можно проверить с помощью Python, что для связанной задачи стохастической оптимизации, даже при выборе меньшей скорости обучения 0,1, наблюдается расхождение до бесконечности! С другой стороны, при скорости обучения 0,05 наблюдается сходимость к минимуму 0. Следовательно, кажется, что даже для этой простой функции выбор (постоянной) скорости обучения должен учитывать распределение, а не только то, что из детерминированная функция F (x), чтобы получить сходимость для задачи стохастической оптимизации. [Примечание: если здесь выполняется поиск строки с возвратом Armijo с максимальной скоростью обучения , то наблюдается сходимость! Следовательно, поиск по строке с возвратом в Armijo по-прежнему помогает выбрать для использования хорошую скорость обучения по сравнению с SGD с постоянной скоростью обучения.]

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

Теорема о прототипе: Позвольте быть выпуклым (или сильно выпуклым) и в . Тогда обе следующие схемы гарантируют сходимость: Схема 1: Отслеживание с возвратом при увеличении размеров «мини-пакета» . Схема 2: SGD со снижением скорости обучения до 0.

Причина, по которой эти схемы дают не очень хорошие экспериментальные результаты в DNN, может быть по следующим причинам:

- Реализация не учитывает различия между стохастической оптимизацией и DNN (подробнее см. В следующем разделе);

и / или

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

Стоит отметить, что текущие успешные реализации Backtracking в DNN используют постоянные размеры мини-пакетов . Однако отличие от примера 1 состоит в том, что k_n = 1 не выбирается, поскольку оно слишком мало. Действительно, есть следующее.

Пример 2. Пусть функция F (x) и распределение такие же , как в примере 1, где . Если выбрать все n, то с помощью Python можно проверить, сходится ли поиск строки возврата Armijo с максимальной скоростью обучения в этой стохастической настройке!

Это можно объяснить тем, что в этом примере выбор для всех n недостаточно хорош, чтобы аппроксимировать функцию F (x), но выбор для всех n является хорошим приближением. То же самое происходит с DNN: нужно выбрать достаточно большой размер мини-пакета в зависимости от конкретного вопроса и настройки (см. Следующий раздел). Люди, знакомые с математическим расчетом в бакалавриате, могут найти аналогию в использовании сумм Римана для приближения интеграла .

2) DNN:

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

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

Резюме

Таким образом, поиск строки с обратным отслеживанием (и модификации) - это метод, который легко реализовать, применим для очень общих функций, имеет очень хорошую теоретическую гарантию (как для сходимости к критическим точкам, так и для предотвращения седловых точек) и хорошо работает на практике. Несколько других методов, которые имеют хорошую теоретическую гарантию, такие как Уменьшение скорости обучения или Стандартный GD со скоростью обучения <1 / L - оба требуют, чтобы градиент целевой функции был непрерывным по Липшицу, оказываются частным случаем поиска строки с обратным отслеживанием или удовлетворяют условию Армийо. Несмотря на то, что априори требуется, чтобы функция стоимости была непрерывно дифференцируемой для применения этого метода, на практике этот метод можно успешно применять также для функций, которые непрерывно дифференцируются на плотном открытом подмножестве, таком как или . Последние функции появляются в глубоких нейронных сетях .

Смотрите также

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