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

Воспроизвести медиа

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

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

Градиентный спуск обычно приписывают Коши , который первым предложил его в 1847 году. Адамар независимо предложил аналогичный метод в 1907 году. Его свойства сходимости для задач нелинейной оптимизации были впервые изучены Хаскеллом Карри в 1944 году, и этот метод становился все более и более изученным. и использовался в последующие десятилетия, также часто называемый крутым спуском.

Описание

Иллюстрация градиентного спуска на серии наборов уровней

Градиентный спуск основан на наблюдении , что если функция мульти-переменной будет определена и дифференцируема в окрестности точки , а затем уменьшается быстро , если один идет от в направлении отрицательного градиента на . Отсюда следует, что если ${\ Displaystyle F (\ mathbf {x})}$${\ Displaystyle \ mathbf {а}}$${\ Displaystyle F (\ mathbf {x})}$${\ Displaystyle \ mathbf {а}}$${\ displaystyle F}$${\ displaystyle \ mathbf {a}, - \ nabla F (\ mathbf {a})}$

${\ displaystyle \ mathbf {a} _ {n + 1} = \ mathbf {a} _ {n} - \ gamma \ nabla F (\ mathbf {a} _ {n})}$

для достаточно маленького тогда . Другими словами, член вычитается, потому что мы хотим двигаться против градиента к локальному минимуму. Имея в виду это наблюдение, мы начинаем с предположения о локальном минимуме и рассматриваем последовательность так , что ${\ displaystyle \ gamma \ in \ mathbb {R} _ {+}}$${\ Displaystyle F (\ mathbf {a_ {n}}) \ geq F (\ mathbf {a_ {n + 1}})}$${\ Displaystyle \ гамма \ набла F (\ mathbf {а})}$${\ Displaystyle \ mathbf {а}}$${\ displaystyle \ mathbf {x} _ {0}}$${\ displaystyle F}$${\ displaystyle \ mathbf {x} _ {0}, \ mathbf {x} _ {1}, \ mathbf {x} _ {2}, \ ldots}$

${\ displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} \ nabla F (\ mathbf {x} _ {n}), \ n \ geq 0.}$

У нас есть монотонная последовательность

${\ Displaystyle F (\ mathbf {x} _ {0}) \ geq F (\ mathbf {x} _ {1}) \ geq F (\ mathbf {x} _ {2}) \ geq \ cdots,}$

так что, будем надеяться, последовательность сходится к желаемому локальному минимуму. Обратите внимание, что значение размера шага может изменяться на каждой итерации. При определенных предположениях относительно функции (например, выпуклой и липшицевой ) и конкретном выборе (например, выбранном либо с помощью линейного поиска , удовлетворяющего условиям Вульфа , либо с помощью метода Барзилаи – Борвейна, показанного ниже), ${\ displaystyle (\ mathbf {x} _ {n})}$ ${\ displaystyle \ gamma}$${\ displaystyle F}$${\ displaystyle F}$ ${\ displaystyle \ nabla F}$ ${\ displaystyle \ gamma}$

${\ displaystyle \ gamma _ {n} = {\ frac {\ left | \ left (\ mathbf {x} _ {n} - \ mathbf {x} _ {n-1} \ right) ^ {T} \ left [\ nabla F (\ mathbf {x} _ {n}) - \ nabla F (\ mathbf {x} _ {n-1}) \ right] \ right |} {\ left \ | \ nabla F (\ mathbf {x} _ {n}) - \ nabla F (\ mathbf {x} _ {n-1}) \ right \ | ^ {2}}}}$

сходимость к локальному минимуму может быть гарантирована. Когда функция является выпуклой , все локальные минимумы также являются глобальными минимумами, поэтому в этом случае градиентный спуск может сходиться к глобальному решению. ${\ displaystyle F}$

Этот процесс проиллюстрирован на рисунке рядом. Здесь предполагается, что он определен на плоскости, а его график имеет форму чаши . Синие кривые - это контурные линии , то есть области, на которых значение является постоянным. Красная стрелка, исходящая из точки, показывает направление отрицательного градиента в этой точке. Обратите внимание, что (отрицательный) градиент в точке ортогонален линии контура, проходящей через эту точку. Мы видим, что градиентный спуск приводит нас к дну чаши, то есть к точке, где значение функции минимально. ${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle F}$

Аналогия для понимания градиентного спуска

Туман в горах

Основная интуиция градиентного спуска может быть проиллюстрирована гипотетическим сценарием. Человек застрял в горах и пытается спуститься (т. Е. Пытается найти глобальный минимум). Сильный туман, поэтому видимость крайне низкая. Следовательно, путь вниз с горы не виден, поэтому они должны использовать местную информацию, чтобы найти минимум. Они могут использовать метод градиентного спуска, который включает в себя рассмотрение крутизны холма в их текущем положении, а затем движение в направлении самого крутого спуска (т. Е. Под гору). Если бы они пытались найти вершину горы (т. Е. Максимум), то они бы продолжили движение в направлении наиболее крутого подъема (т. Е. В гору). Используя этот метод, они в конечном итоге спустятся с горы или, возможно, застрянут в какой-нибудь дыре (например, в локальном минимуме или седловой точке ), например, в горном озере. Однако предположим также, что крутизна холма не сразу очевидна при простом наблюдении, а скорее требует сложного инструмента для измерения, который у человека есть в данный момент. Чтобы измерить крутизну холма с помощью прибора, требуется некоторое время, поэтому им следует свести к минимуму использование прибора, если они хотят спуститься с горы до захода солнца. Тогда сложность состоит в том, чтобы выбрать частоту, с которой они должны измерять крутизну холма, чтобы не сбиться с пути.

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

Примеры

У градиентного спуска есть проблемы с патологическими функциями, такими как функция Розенброка, показанная здесь.

${\ displaystyle f (x_ {1}, x_ {2}) = (1-x_ {1}) ^ {2} +100 (x_ {2} -x_ {1} ^ {2}) ^ {2}. }$

Функция Розенброка имеет узкую изогнутую долину, которая содержит минимум. Дно долины очень плоское. Из-за изогнутой плоской впадины оптимизация идет медленно зигзагообразно с небольшими шагами к минимуму. В частности, эту проблему решает технология Whiplash Gradient Descent .

Зигзагообразный характер метода также очевиден ниже, где метод градиентного спуска применяется к

${\ Displaystyle F (x, y) = \ sin \ left ({\ frac {1} {2}} x ^ {2} - {\ frac {1} {4}} y ^ {2} +3 \ right ) \ cos \ left (2x + 1-e ^ {y} \ right).}$

Выбор размера шага и направления спуска

Поскольку использование слишком маленького шага замедлит сходимость, а слишком большое приведет к расхождению, поиск хорошей настройки является важной практической проблемой. Филип Вулф также выступал за использование на практике «разумного выбора направления [спуска]». Хотя использование направления, которое отклоняется от самого крутого направления спуска, может показаться нелогичным, идея состоит в том, что меньший уклон можно компенсировать, выдерживая гораздо большее расстояние. ${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$

Чтобы рассуждать об этом математически, давайте воспользуемся направлением и размером шага и рассмотрим более общее обновление: ${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ gamma _ {n}}$

${\ displaystyle \ mathbf {a} _ {n + 1} = \ mathbf {a} _ {n} - \ gamma _ {n} \, \ mathbf {p} _ {n}}$.

Поиск хороших настроек и требует немного подумать. Прежде всего, нам бы хотелось, чтобы направление обновления было под гору. Математически, позволяя обозначать угол между и , это требует, чтобы, чтобы сказать больше, нам нужно больше информации о целевой функции, которую мы оптимизируем. При достаточно слабом предположении, которое непрерывно дифференцируемо, мы можем доказать, что: ${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ gamma _ {n}}$${\ displaystyle \ theta _ {n}}$${\ Displaystyle \ набла Ф (\ mathbf {а_ {п}})}$${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ cos \ theta _ {n}> 0.}$${\ displaystyle F}$

${\ Displaystyle F (\ mathbf {a} _ {n + 1}) \ leq F (\ mathbf {a} _ {n}) - \ gamma _ {n} \ | \ nabla F (\ mathbf {a} _ {n}) \ | _ {2} \ | \ mathbf {p} _ {n} \ | _ {2} \ left [\ cos \ theta _ {n} - \ max _ {t \ in [0,1 ]} {\ frac {\ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n}) - \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}} {\ | \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}}} \ right]}$

( 1 )

Это неравенство означает, что величина, на которую мы можем быть уверены, что функция уменьшается, зависит от компромисса между двумя терминами в квадратных скобках. Первый член в квадратных скобках измеряет угол между направлением спуска и отрицательным градиентом. Второй член измеряет, насколько быстро меняется градиент по направлению спуска. ${\ displaystyle F}$

В принципе неравенство ( 1 ) можно оптимизировать и выбрать оптимальный размер и направление шага. Проблема в том, что оценка второго члена в квадратных скобках требует оценки , а дополнительные оценки градиента, как правило, дороги и нежелательны. Вот несколько способов обойти эту проблему: ${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ gamma _ {n}}$${\ Displaystyle \ набла F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n})}$

• Откажитесь от преимуществ продуманного направления спуска, задав его и используйте линейный поиск, чтобы найти подходящий размер шага , например такой, который удовлетворяет условиям Вульфа .${\ displaystyle \ mathbf {p} _ {n} = \ nabla F (\ mathbf {a_ {n}})}$${\ displaystyle \ gamma _ {n}}$
• Предполагая, что это дважды дифференцируемое, используйте его гессиан для оценки. Затем выберите и , оптимизируя неравенство ( 1 ).${\ displaystyle F}$${\ displaystyle \ nabla ^ {2} F}$${\ displaystyle \ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n}) - \ nabla F (\ mathbf {a} _ {n} ) \ | _ {2} \ приблизительно \ | t \ gamma _ {n} \ nabla ^ {2} F (\ mathbf {a} _ {n}) \ mathbf {p} _ {n} \ |.}$${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ gamma _ {n}}$
• Предполагая, что это липшицево , используйте его константу Липшица для оценки. Затем выберите и , оптимизируя неравенство ( 1 ).${\ displaystyle \ nabla F}$${\ displaystyle L}$${\ displaystyle \ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n}) - \ nabla F (\ mathbf {a} _ {n} ) \ | _ {2} \ leq Lt \ gamma _ {n} \ | \ mathbf {p} _ {n} \ |.}$${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ gamma _ {n}}$
• Создайте собственную модель для . Затем выберите и , оптимизируя неравенство ( 1 ).${\ displaystyle \ max _ {t \ in [0,1]} {\ frac {\ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ { n}) - \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}} {\ | \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}}} }$${\ displaystyle F}$${\ displaystyle \ mathbf {p} _ {n}}$${\ displaystyle \ gamma _ {n}}$
• При более строгих предположениях о функции, такой как выпуклость , могут быть возможны более продвинутые методы .${\ displaystyle F}$

Обычно, следуя одному из вышеперечисленных рецептов, можно гарантировать сходимость к локальному минимуму. Когда функция является выпуклой , все локальные минимумы также глобальные минимумы, поэтому в этом случае градиентного спуска может сходиться к глобальному решению. ${\ displaystyle F}$

Решение линейной системы

Алгоритм наискорейшего спуска, примененный к фильтру Винера

Градиентный спуск можно использовать для решения системы линейных уравнений

${\ displaystyle A \ mathbf {x} - \ mathbf {b} = 0}$

переформулирована как задача квадратичной минимизации. Если матрица системы вещественная симметричная и положительно определенная , целевая функция определяется как квадратичная функция с минимизацией ${\ displaystyle A}$

${\ Displaystyle F (\ mathbf {x}) = \ mathbf {x} ^ {T} A \ mathbf {x} -2 \ mathbf {x} ^ {T} \ mathbf {b},}$

так что

${\ displaystyle \ nabla F (\ mathbf {x}) = 2 (A \ mathbf {x} - \ mathbf {b}).}$

Для общей вещественной матрицы , линейной методом наименьших квадратов определяют ${\ displaystyle A}$

${\ Displaystyle F (\ mathbf {x}) = \ left \ | A \ mathbf {x} - \ mathbf {b} \ right \ | ^ {2}.}$

В традиционных линейных наименьших квадратов для реального и в евклидовой норме используется, в этом случае ${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$

${\ displaystyle \ nabla F (\ mathbf {x}) = 2A ^ {T} (A \ mathbf {x} - \ mathbf {b}).}$

Строка поиск минимизация, найти локально оптимальный размер шага на каждой итерации, может быть выполнена аналитический для квадратичных функций, и явных формул для локально оптимально известно. ${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$

Например, для вещественной симметричной и положительно определенной матрицы простой алгоритм может быть следующим: ${\ displaystyle A}$

${\ displaystyle {\ begin {align} & {\ text {повторять в цикле:}} \\ & \ qquad \ mathbf {r}: = \ mathbf {b} - \ mathbf {Ax} \\ & \ qquad \ гамма: = {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r}} / {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {Ar}} \\ & \ qquad \ mathbf {x}: = \ mathbf {x} + \ gamma \ mathbf {r} \\ & \ qquad {\ hbox {if}} \ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r} { \ text {достаточно мал, тогда выйдите из цикла}} \\ & {\ text {end repeat loop}} \\ & {\ text {return}} \ mathbf {x} {\ text {в качестве результата}} \ end {выровнено}}}$

Чтобы избежать умножения на два раза за итерацию, отметим, что подразумевается , что дает традиционный алгоритм: ${\ displaystyle A}$${\ Displaystyle \ mathbf {x}: = \ mathbf {x} + \ gamma \ mathbf {r}}$${\ Displaystyle \ mathbf {r}: = \ mathbf {r} - \ gamma \ mathbf {Ar}}$

${\ displaystyle {\ begin {align} & \ mathbf {r}: = \ mathbf {b} - \ mathbf {Ax} \\ & {\ text {повторять в цикле:}} \\ & \ qquad \ gamma: = {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r}} / {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {Ar}} \\ & \ qquad \ mathbf { x}: = \ mathbf {x} + \ gamma \ mathbf {r} \\ & \ qquad {\ hbox {if}} \ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r} {\ text {достаточно мал, тогда выйдите из цикла}} \\ & \ qquad \ mathbf {r}: = \ mathbf {r} - \ gamma \ mathbf {Ar} \\ & {\ text {end repeat loop}} \\ & {\ text {return}} \ mathbf {x} {\ text {как результат}} \ end {align}}}$

Этот метод редко используется для решения линейных уравнений, причем метод сопряженных градиентов является одной из самых популярных альтернатив. Количество градиентных итераций спуска обычно пропорциональна спектральной условию числа матрицы системы (отношение максимального до минимального собственных значений в ) , в то время как сходимость сопряженного метода градиента , как правило , определяется квадратный корень из числа состояния, т.е. , намного быстрее. Оба метода могут выиграть от предварительного кондиционирования , когда градиентный спуск может потребовать меньше допущений в отношении предварительного кондиционирования. ${\ Displaystyle \ каппа (А)}$${\ displaystyle A}$${\ displaystyle A ^ {T} A}$

Решение нелинейной системы

Градиентный спуск также можно использовать для решения системы нелинейных уравнений . Ниже приведен пример, показывающий, как использовать градиентный спуск для решения трех неизвестных переменных: x ₁ , x ₂ и x ₃ . В этом примере показана одна итерация градиентного спуска.

Рассмотрим нелинейную систему уравнений

${\ displaystyle {\ begin {cases} 3x_ {1} - \ cos (x_ {2} x_ {3}) - {\ tfrac {3} {2}} = 0 \\ 4x_ {1} ^ {2} - 625x_ {2} ^ {2} + 2x_ {2} -1 = 0 \\\ exp (-x_ {1} x_ {2}) + 20x_ {3} + {\ tfrac {10 \ pi -3} {3 }} = 0 \ end {case}}}$

Введем ассоциированную функцию

${\ Displaystyle G (\ mathbf {x}) = {\ begin {bmatrix} 3x_ {1} - \ cos (x_ {2} x_ {3}) - {\ tfrac {3} {2}} \\ 4x_ { 1} ^ {2} -625x_ {2} ^ {2} + 2x_ {2} -1 \\\ exp (-x_ {1} x_ {2}) + 20x_ {3} + {\ tfrac {10 \ pi -3} {3}} \\\ конец {bmatrix}},}$

куда

${\ displaystyle \ mathbf {x} = {\ begin {bmatrix} x_ {1} \\ x_ {2} \ x_ {3} \\\ end {bmatrix}}.}$

Теперь можно определить целевую функцию

${\ Displaystyle F (\ mathbf {x}) = {\ frac {1} {2}} G ^ {\ mathrm {T}} (\ mathbf {x}) G (\ mathbf {x}) = {\ frac {1} {2}} \ left [\ left (3x_ {1} - \ cos (x_ {2} x_ {3}) - {\ frac {3} {2}} \ right) ^ {2} + \ слева (4x_ {1} ^ {2} -625x_ {2} ^ {2} + 2x_ {2} -1 \ right) ^ {2} + \ left (\ exp (-x_ {1} x_ {2}) + 20x_ {3} + {\ frac {10 \ pi -3} {3}} \ right) ^ {2} \ right],}$

которые мы постараемся свести к минимуму. В качестве первоначальной догадки воспользуемся

${\ displaystyle \ mathbf {x} ^ {(0)} = \ mathbf {0} = {\ begin {bmatrix} 0 \\ 0 \\ 0 \\\ end {bmatrix}}.}$

Мы знаем это

${\ Displaystyle \ mathbf {x} ^ {(1)} = \ mathbf {0} - \ gamma _ {0} \ nabla F (\ mathbf {0}) = \ mathbf {0} - \ gamma _ {0} J_ {G} (\ mathbf {0}) ^ {\ mathrm {T}} G ​​(\ mathbf {0}),}$

где матрица Якоби имеет вид ${\ displaystyle J_ {G}}$

${\ Displaystyle J_ {G} (\ mathbf {x}) = {\ begin {bmatrix} 3 & \ sin (x_ {2} x_ {3}) x_ {3} & \ sin (x_ {2} x_ {3} ) x_ {2} \\ 8x_ {1} & - 1250x_ {2} + 2 & 0 \\ - x_ {2} \ exp {(-x_ {1} x_ {2})} & - x_ {1} \ exp ( -x_ {1} x_ {2}) & 20 \\\ end {bmatrix}}.}$

Рассчитываем:

${\ Displaystyle J_ {G} (\ mathbf {0}) = {\ begin {bmatrix} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 20 \ end {bmatrix}}, \ qquad G (\ mathbf {0}) = {\ begin { bmatrix} -2,5 \\ - 1 \\ 10,472 \ end {bmatrix}}.}$

Таким образом

${\ displaystyle \ mathbf {x} ^ {(1)} = \ mathbf {0} - \ gamma _ {0} {\ begin {bmatrix} -7.5 \\ - 2 \\ 209.44 \ end {bmatrix}},}$

а также

${\ Displaystyle F (\ mathbf {0}) = 0,5 \ left ((- 2,5) ^ {2} + (- 1) ^ {2} + (10,472) ^ {2} \ right) = 58,456.}$

Анимация, показывающая первые 83 итерации градиентного спуска, примененные к этому примеру. Поверхности изоповерхность из в текущей догадке , а стрелки показывают направление спуска. Из-за небольшого и постоянного размера шага сходимость происходит медленно.${\ Displaystyle F (\ mathbf {x} ^ {(n)})}$${\ Displaystyle \ mathbf {х} ^ {(п)}}$

Теперь необходимо найти подходящий такой, чтобы ${\ displaystyle \ gamma _ {0}}$

${\ Displaystyle F \ влево (\ mathbf {x} ^ {(1)} \ right) \ Leq F \ left (\ mathbf {x} ^ {(0)} \ right) = F (\ mathbf {0}) .}$

Это можно сделать с помощью любого из множества алгоритмов линейного поиска . Можно также просто догадаться, что дает ${\ displaystyle \ gamma _ {0} = 0,001,}$

${\ displaystyle \ mathbf {x} ^ {(1)} = {\ begin {bmatrix} 0,0075 \\ 0,002 \\ - 0,20944 \\\ end {bmatrix}}.}$

Оценка целевой функции при этом значении дает

${\ Displaystyle F \ влево (\ mathbf {х} ^ {(1)} \ вправо) = 0,5 \ влево ((- 2,48) ^ {2} + (- 1,00) ^ {2} + (6,28) ^ {2 } \ right) = 23,306.}$

Уменьшение от до следующего шага значения ${\ Displaystyle F (\ mathbf {0}) = 58,456}$

${\ Displaystyle F \ влево (\ mathbf {x} ^ {(1)} \ right) = 23.306}$

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

Комментарии

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

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

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

Градиентный спуск можно комбинировать с линейным поиском , находя локально оптимальный размер шага на каждой итерации. Поиск строки может занять много времени. И наоборот, использование фиксированного малого может привести к плохой сходимости. ${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$

Методы, основанные на методе Ньютона и обращении гессиана с использованием методов сопряженных градиентов , могут быть лучшими альтернативами. Обычно такие методы сходятся за меньшее количество итераций, но стоимость каждой итерации выше. Примером является метод BFGS, который заключается в вычислении на каждом шаге матрицы, на которую вектор градиента умножается, чтобы перейти в «лучшее» направление, в сочетании с более сложным алгоритмом линейного поиска , чтобы найти «лучшее» значение для чрезвычайно При больших задачах, где преобладают проблемы с памятью компьютера, следует использовать метод с ограниченным объемом памяти, такой как L-BFGS , вместо BFGS или метода наискорейшего спуска. ${\ displaystyle \ gamma.}$

Градиентный спуск можно рассматривать как применение метода Эйлера для решения обыкновенных дифференциальных уравнений к градиентному потоку . В свою очередь, это уравнение может быть получено как оптимальный регулятор для системы управления с заданной в форме обратной связи . ${\ displaystyle x '(t) = - \ nabla f (x (t))}$${\ Displaystyle х '(т) = и (т)}$${\ Displaystyle и (т)}$${\ Displaystyle и (т) = - \ набла ф (х (т))}$

Модификации

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

Методы быстрого градиента

Юрий Нестеров предложил простую модификацию, которая обеспечивает более быструю сходимость для выпуклых задач, и с тех пор получила дальнейшее обобщение. Для неограниченных гладких задач метод называется методом быстрого градиента (FGM) или методом ускоренного градиента (AGM). В частности, если дифференцируемая функция выпукла и является липшицевым , и не предполагается , что это сильно выпуклый , то ошибка в объективной стоимости , создаваемой на каждом шаге методом спуска градиента будет ограничена . При использовании метода ускорения Нестерова погрешность уменьшается на . Известно, что скорость уменьшения функции стоимости оптимальна для методов оптимизации первого порядка. Тем не менее, есть возможность улучшить алгоритм за счет уменьшения постоянного множителя. Оптимизирован метод градиентного (ОГМ) уменьшает эту константу на два раза и является оптимальным методом первого порядка для крупномасштабных проблем. ${\ displaystyle F}$${\ displaystyle \ nabla F}$${\ displaystyle F}$${\ displaystyle k}$ ${\ textstyle {\ mathcal {O}} \ left ({\ tfrac {1} {k}} \ right)}$${\ textstyle {\ mathcal {O}} \ left ({\ tfrac {1} {k ^ {2}}} \ right)}$${\ displaystyle {\ mathcal {O}} \ left ({k ^ {- 2}} \ right)}$

Для ограниченных или негладких задач FGM Нестерова называется методом быстрого проксимального градиента (FPGM), ускорением метода проксимального градиента .

Метод импульса или тяжелого мяча

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

Этот метод используется в стохастическом градиентном спуске # Momentum и как расширение алгоритмов обратного распространения , используемых для обучения искусственных нейронных сетей .

Расширения

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

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

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

дальнейшее чтение

• Бойд, Стивен ; Ванденберге, Ливен (2004). «Безусловная минимизация» (PDF) . Выпуклая оптимизация . Нью-Йорк: Издательство Кембриджского университета. С. 457–520. ISBN 0-521-83378-7.
• Чонг, Эдвин КП; Чак, Станислав Х. (2013). «Градиентные методы» . Введение в оптимизацию (Четвертое изд.). Хобокен: Вайли. С. 131–160. ISBN 978-1-118-27901-4.
• Химмельблау, Дэвид М. (1972). «Процедуры неограниченной минимизации с использованием производных». Прикладное нелинейное программирование . Нью-Йорк: Макгроу-Хилл. С. 63–132. ISBN 0-07-028921-2.

внешние ссылки

• Использование градиентного спуска в C ++, Boost, Ublas для линейной регрессии
• Серия видеороликов Khan Academy обсуждает градиентное восхождение
• Онлайн-книга, обучающая градиентному спуску в контексте глубокой нейронной сети
• «Градиентный спуск, как обучаются нейронные сети» . 3Синий1Коричневый . 16 октября 2017 г. - через YouTube .

arxiv.org/2108.1283