Как это может быть пойман в ловушку в седловой точке?

14

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

Решение может быть слишком тривиальным, чтобы я его не понял.

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

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

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

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

Я немного запутался в двух других частях.

Fixining_ranges
источник
1
Моти понимает это. Седловая точка с очень высокими уклонами и окруженная нулевым уклоном запускает градиентный спуск с большими ступенями в «бесплодные земли», из которых она не может восстановиться. Подумайте о поиске скважины на плоской равнине. Теперь подумайте о колодце, как о сухом, так и о муравейнике в центре. Градиентный спуск, который приземляется на муравейнике, но не на самой вершине, радикально отразит поиск. А теперь представьте, что размер шага для поиска в тысячу раз больше диаметра скважины. Если поиск всегда находит хорошо, муравейник побегов оно Монтаны
EngrStudent - восстановит Монику
Я запутался, что вы спрашиваете. Вы не понимаете, почему SGD не может попасть в седловую точку из-за наследственного шума, который имеет SGD, так что, по вашему мнению, он должен уйти? (в отличие от того, что это был полный пакет GD, тогда, если градиент равен нулю и нет шума, он не может сбежать, это то, о чем вы просите?)
Буратино

Ответы:

16

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

Схематическое изображение седловой точки

Теперь дело в том, оптимизируете ли вы с помощью мини-пакетаили стохастический градиентный спуск, основная невыпуклая функция та же самая, и градиент является свойством этой функции. Выполняя мини-серию, вы одновременно рассматриваете много образцов и делаете шаг градиента, усредненный по всем из них. Это уменьшает дисперсию. Но если направление среднего градиента все еще указывает в том же направлении, что и седловая точка, то вы все равно рискуете застрять там. Аналогия в том, что если вы делаете 2 шага вперед и 1 шаг назад, усредняя их, вы в конечном итоге делаете 1 шаг вперед. Если вместо этого вы выполняете SGD, вы делаете все шаги один за другим, но если вы все еще движетесь в одном направлении, вы можете достичь седловой точки и обнаружить, что градиент со всех сторон довольно плоский, а размер шага равен слишком маленький, чтобы пройти через эту плоскую часть. Это не

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

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

Сложные седловые регионы

Методы, такие как импульс, АДАГРАД, Адам и т. Д., Могут вырваться из этого, рассматривая прошлые градиенты. Рассмотрим импульс,

vt=γvt1+ηthetaJ(θ)

vt1

сурьма
источник
Ну, не совсем! Для ответа на практике см: stats.stackexchange.com/a/284399/117305
alifornia
@AliAbbasinasab Я думаю, что сурьма хорошо объясняет. Конечно, застревание в обычном седле вряд ли, как вы упоминаете в своем ответе, но он просто показал возможность того, что SGD может быть пойман. И мне он только показал некоторые необычные точки седла, которые SGD не может избежать.
Казуя Томита
2

Не должно.

[ 1 ] показал, что градиентный спуск со случайной инициализацией и соответствующим постоянным размером шага не сходится к седловой точке. Это долгая дискуссия, но чтобы дать вам представление о том, почему смотрите следующий пример:

f(x,y)=12x2+14y412y2

введите описание изображения здесь

z1=[00],z2=[01],z3=[01]

z2z3z1

z0=[x0]z1z1xR2

2f(x,y)=[1003y21]

2f(z1)xxz1

alifornia
источник
С таким же успехом можно выбрать функцию контрпримеров, в которой вы будете каждый раз застревать в седловой точке ...
Ян Кукачка
1
Я не смог найти вашу ссылку [1] - не могли бы вы привести полную цитату? В то же время можно создать контрпримеры к вашему заявлению, указав, что оно должно основываться на дополнительных неустановленных предположениях.
whuber
@whuber вы можете легко приготовить контрпримеры. Например, если у вас есть только строка в качестве пробела. Я просто попытался добавить пункт, который не может быть очевидным для многих (изначально это было не слишком очевидно для меня, почему). Что касается ссылки, я понятия не имею, почему вы не можете достичь этого. Я дважды проверил, ссылка действительна и обновляется. Вы можете выполнить поиск «Градиентный спуск сходится к минимизаторам», Джейсон Д. Ли, Макс Симховиц, Майкл И. Джордан † и Бенджамин Рехт † partment Кафедра электротехники и компьютерных наук † Департамент статистики Калифорнийского университета, Беркли, 19 апреля 2019 г. "
Калифорния,
Спасибо за ссылку. Беглый взгляд на него (ссылка теперь работает) показывает, что анализ ограничен «строгими седлами» (где существуют как положительные, так и отрицательные собственные значения гессиана), что исключает множество возможностей. Заключительные утверждения статьи включают «мы отмечаем, что существуют очень сложные безусловные проблемы оптимизации, когда строгое условие седла не выполняется», и они предлагают минимизировать кварту в качестве примера.
whuber
0

Если вы переходите к ссылочной статье (они также эмпирически показывают, как их подход без седел действительно улучшает мини-пакет SGD), они утверждают:

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

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

Кажется возможным, что можно попробовать итеративный подход, при котором каждый перезапускает мини-пакет SGD после его завершения (т. Е. Сбрасывает скорость обучения), чтобы увидеть, можно ли избежать проблемной области.

Мотин
источник
0

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

Если вы не уменьшите количество шагов, то перепрыгнете через минимум и сильно их упустите. Вы должны как-то уменьшить размер шага.

Аксакал почти наверняка бинарный
источник