Понимание «почти все локальные минимумы имеют значение функции, очень похожее на глобальный оптимум»

46

В недавнем сообщении в блоге Rong Ge было сказано, что:

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

Откуда эта вера?

Джон Донн
источник
15
Я буду удивлен, если это не эмпирический вывод.
usεr11852 говорит восстановить Monic

Ответы:

69

Недавняя статья «Поверхности потерь многослойных сетей» предлагает некоторые возможные объяснения этому. Из их резюме (жирный шрифт мой):

«Мы предполагаем, что как моделируемый отжиг, так и SGD сходятся к полосе низких критических точек, и что все найденные критические точки имеют локальные минимумы высокого качества, измеренные по ошибке теста. Это подчеркивает существенное различие между крупными и мелкими сетями где для последних локальные минимумы низкого качества имеют ненулевую вероятность восстановления. Наконец, мы доказываем, что восстановление глобального минимума становится сложнее по мере увеличения размера сети и что на практике это не имеет значения, поскольку глобальный минимум часто приводит к перегрузке ».

Многие влиятельные люди в глубоком обучении (Yann LeCunn и Yoshua Bengio, чтобы назвать некоторых) и некоторые исследователи, приходящие больше с математической точки зрения (Rong Ge и другие сотрудники Sanjeev Arora) обсуждали и изучали эти идеи.

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

Кроме того, они используют модель «спинового стекла», которую они даже называют просто моделью и не обязательно указывают на истинную картину, чтобы показать, что достижение глобального минимизатора из локальных минимумов может занять экспоненциально много времени:

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

Исследование Rong Ge сосредоточено на прорыве седловых точек. Йошуа Бенжио и его сотрудники выдвинули довольно смелую гипотезу Седл-Пойнт:

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

источник здесь: Идентификация и атака на проблему седловой точки в многомерной невыпуклой оптимизации.

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

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

Справедливо задаться вопросом, могут ли методы импульса и другие новые алгоритмы оптимизации, которые могут оценить некоторые свойства кривизны 2-го порядка, избежать седловых точек. Знаменитая анимация Алек Рэдфорд здесь .

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

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

Инди AI
источник
14
+1 Впечатляюще информативный и авторитетный ответ - всего в нескольких легко понятных параграфах он отражает идеи и текущие направления в значительном подполе.
whuber
Спасибо за ваш ответ. Поскольку вы упомянули Янна ЛеКуна, не могли бы вы указать ему конкретную ссылку, в которой обсуждаются эти или подобные идеи?
Джон Донн
2
Эй, Джон: статья «Поверхность потерь многослойных сетей», на которую я ссылался в статье, написана в соавторстве с Янном. Еще одна похожая статья, написанная в соавторстве с Янном, - « Исследования больших ландшафтов» . Две статьи очень похожи, та, на которую я ссылался изначально, кажется более популярной.
Инди AI
Ссылка "Нет больше локальных минимумов" не работает. Благодаря быстрому поиску в Google я не смог найти сообщение в блоге, на которое оно ссылается. Сообщение в блоге не в сети? Или просто переехал?
ЛКМ