Задача обучения параметрической модели ставится как задача минимизации эмпирического риска
где – выборка размера , а – функция риска, например, . Часто интересующая нас функция риска не дифференцируема по второму аргументу, что делает градиентную оптимизацию неприменимой. По этой причине вместо исходной функции риска вводят её дифференцируемый выпуклый суррогат, то есть некоторую выпуклую и дифференцируемую по второму аргументу функцию . Новый функционал эмпирического риска имеет вид
Если дифференцируема по , то из дифференцируемости следует дифференцируемость , что делает возможной градиентную оптимизацию. А если выпукла по , то из выпуклости следует выпуклость , что даёт гарантии на сходимость градиентного спуска в глобальный минимум.
Увы, в общем случае нейронные сети не выпуклы как функции своих весов. Это можно увидеть на простом примере. Пусть , где , и – скаляры, а . Гессиан как функции в любой точке равен ; его собственные числа равны и , что и означает, что для любого ненулевого функция не выпукла.
Таким образом, даже для выпуклой функция потерь нейронной сети не обязана быть выпуклой функцией весов.
У невыпуклых функций могут быть минимумы, не являющиеся глобальными, в которых может «застревать» градиентный спуск. Тем не менее, на практике часто оказывается, что градиентный спуск всегда находит точку со сколь угодно близким к глобальному минимуму значением функции потерь.
Это наблюдение приводит к гипотезе, что, хотя поверхность функции потерь не обязана быть выпуклой, все её минимумы глобальны для используемых нами сетей и тех наборов данных, на которых мы их обучаем.
Известны два случая, для которых эту гипотезу удаётся доказать. Первый – это линейные сети. Второй – это достаточно широкие нелинейные сети (ширина одного из слоёв не меньше числа примеров в выборке). К сожалению, оба примера нереалистичны: выразительная способность линейных сетей не выше, чем у обыкновенной линейной модели, а ширина реальных нейронных сетей не настолько велика (порядка нейронов против примеров в ImageNet), причём улучшить оценку на ширину в общем случае невозможно, см. Q. Nguyen A note on connectivity of sublevel sets in deep learning. Возможно, для получения лучших оценок исследователям предстоит научиться учитывать структуру данных обучающей выборки.
Исторически первое доказательство глобальности всех локальных минимумов линейной сети содержится в работе Deep learning without poor local minima. Более простое доказательство в немного более общем случае можно найти в работе Depth creates no bad local minima. Ещё более простое доказательство есть в работе Deep linear networks with arbitrary loss: All local minima are global, но оно подходит только для сетей без боттлнеков ( ). Последнее подробно разобрано в конспекте лекций автора этого параграфа.
Здесь мы разберём только второй случай (достаточно широкие нелинейные сети) как потенциально более перспективный.
Все минимумы достаточно широкой нелинейной сети глобальны
Рассмотрим нейронную сеть с одним скрытым слоем:
где функция активации применяется поэлементно. Рассмотрим набор данных размера , где , а . Применяя соотношения выше к этому набору, получим следующие значения выходов слоёв:
Поставим задачу оптимизации квадратичной функции потерь
где – норма Фробениуса.
Теорема 1 (On the local minima free condition of backpropagation learning) Если аналитична, ограничена и не тождественно равна нулю, ширина скрытого слоя не меньше и все столбцы матрицы различны, то все локальные минимумы глобальны.
Доказательство. Пусть – локальный минимум , и пусть , – соответствующие ему скрытые представления. Тогда – локальный минимум .
Задача оптимизации выпуклая, поэтому – глобальный минимум .
Если , то система , где – неизвестная матрица, гарантировано имеет решение для каждого . Следовательно,
а значит, – глобальный минимум .
Заметим, что для выполнения равенства необходимо .
Пусть теперь . Если тем не менее , то – по-прежнему глобальный минимум . Пусть
Докажем, что не может быть локальным минимумом до тех пор, пока выполнены условия следующей леммы, которую мы докажем позже:
Лемма 1. Если , функция аналитична, ограничена и не тождественно равна нулю, а все столбцы матрицы различны, то лебегова мера множества равна нулю.
Так как и – непрерывна как функция от , существует , для которого
где через мы обозначили -окрестность точки в пространстве весов.
Из леммы 1 следует, что для любого найдётся , для которого . Возьмём . Для соответствующего имеем ; при этом . Как было отмечено выше, задача минимизации выпуклая, и оптимум её равен нулю, так как . Поэтому градиентный спуск, применённый к и стартующий в , сойдётся в некоторую точку , для которой .
Мы знаем, что в нашей эпсилон-окрестности функция потерь положительна, значит, найденная точка находится вне её: .
Таким образом, найдётся такое, что для любых существует пара такая, что градиентный спуск, примененный к , стартующий в и действующий только на , сходится в точку .
Очевидно, что если «для любых » заменить на «для любых », утверждение выше останется верным. Это означает, что динамика градиентного спуска, действующего только на , не устойчива по Ляпунову в точке . Следовательно, не может быть точкой минимума (иначе градиентный спуск был бы устойчив), а значит, условие невыполнимо в условиях леммы 1. Таким образом, все локальные минимумы глобальны. Теорема 1 доказана.
Доказательство леммы 1. Пусть – наборов индексов из длины . Рассмотрим – подматрицу матрицы , состоящую из строк , проиндексированных набором . В терминах условие эквивалентно .
Так как аналитична, а определитель – аналитическая функция элементов матрицы, – аналитическая функция от для любого .
Нам понадобится следующая лемма, доказательство которой вы можете найти в The loss surface of deep and wide neural networks (лемма 4.3):
Лемма 2. В условиях леммы 1, найдётся , для которого .
Из леммы 2 и эквивалентности выше следует, что найдётся , такой что для некоторого имеет место неравенство . Так как определитель – аналитическая функция , а всякая не тождественно нулевая аналитическая функция принимает значение ноль лишь на множестве меры ноль по Лебегу, то лебегова мера множества равна нулю. Таким образом, лемма 1 доказана.
Обобщения
При доказательстве теоремы 1 мы воспользовались следующими условиями:
- Все обучающие примеры (столбцы матрицы ) различны;
- Число скрытых слоёв равно одному;
- Ширина (последнего) скрытого слоя не меньше числа примеров: ;
- Функция активации аналитична, ограничена и не тождественно равна нулю;
- Функция ошибки квадратична.
Можем ли мы ослабить какие-то из них?
Если какие-то из примеров совпадают и соответствующие метки также одинаковы, теорема обобщается тривиально. Если же метки не совпадают, то нулевая ошибка, вообще говоря, недостижима. Тем не менее, доказательство меняется по большому счёту лишь в том, что вместо будет фигурировать число различных примеров.
Рассмотрим сеть с скрытыми слоями, действующую на набор данных размера :
Для обобщения теоремы 1 на глубокие сети с широким последним скрытым слоем, достаточно обобщить лемму 1. Например, можно воспользоваться следующим результатом (лемма 4.4 из The loss surface of deep and wide neural networks)
Лемма 3. Пусть аналитична, ограничена и не тождественно равна нулю, и пусть . Тогда если и все строки матрицы различны, то лебегова мера множества равна нулю.
Третье предположение можно попытаться ослабить с двух сторон.
Во-первых, можно требовать меньшего числа нейронов в скрытом слое. В общем случае этот подход не работает: в статье A note on connectivity of sublevel sets in deep learning доказывается, что – это наименьшая ширина, при которой теорема выполняется для набора данных общего вида с различными примерами. Тем не менее, для реальных нейронных сетей градиентный спуск нередко находит глобальный минимум, хотя их ширина часто гораздо меньше размера набора данных, на которых они обучаются. Возможно, оценки на минимальную ширину удастся улучшить, если учесть структуру данных: например, если все примеры разбиваются на подмножества с элементами, находящимися близко друг к другу и имеющими одинаковые метки.
Во-вторых, можно предположить, что самым широким является не последний скрытый слой, а один из промежуточных: для некоторого . Но тогда задача не выпукла, а значит, из не следует, что , и градиентный спуск, действующий на , не обязан сходиться в точку, в которой (он может застрять в локальном минимуме). Тем не менее, поставив ряд дополнительных условий, теорему 1 можно обобщить:
Теорема 2. Пусть – локальный минимум и выполнены следующие условия:
- аналитична, ограничена, не тождественно равна нулю;
- производная нигде не обращается в ноль;
- ;
- ;
- .
Тогда – глобальный минимум .
Условие 4 необходимо, чтобы из следовало . Отметим, что из условия 4 также следует, что , то есть нейронная сеть должна сужаться, начиная со следующего после самого широкого слоя.
Условие 5 необходимо, чтобы в случае построить малое возмущение минимума , которое снова является минимумом, но для которого ; невырожденный гессиан позволяет применить для этого теорему об обратной функции.
Если функция активации не аналитична, то лемма 3 неверна. В самом деле, для однородной (например, для ReLU или leaky ReLU) паттерны активаций, , не меняются при малом возмущении весов. Значит, мы, вообще говоря, не можем найти такое малое возмущение, для которого ранг будет полным.
Вместо малого возмущения в работе On Connected Sublevel Sets in Deep Learning явно строятся пути в пространстве весов, на которых функция потерь не возрастает и достигает нуля. Если такой путь можно построить из произвольной точки, то все (строгие) локальные минимумы глобальны. Оказывается, что для построения такого пути аналитичность функции активации не требуется. Более того, при определённых условиях можно доказать, что из любых двух точек в пространстве весов можно построить соответствующие пути так, чтобы они сходились в одной точке. Это значит, что множество подуровня связно при любом – эффект, впервые эмпирически обнаруженный в работах Loss surfaces, mode connectivity, and fast ensembling of DNNs и Essentially No Barriers in Neural Network Energy Landscape.
Связность множеств подуровня сильнее глобальности всех строгих минимумов. В самом деле, если бы существовал строгий локальный минимум уровня , то для достаточно малого ему бы соответствовала отдельная связная компонента множества подуровня . С другой стороны, если все локальные минимумы глобальны, но изолированы, то множество подуровня несвязно для достаточно малого .
Вместо того, чтобы строить пути, на которых функция потерь достигает нуля, можно строить пути, на которых функция потерь достигает сколь угодно малого значения . Это позволяет обобщить результат на функции потерь , для которых минимум по второму аргументу, ответу сети, не достигается. Пример такой функции – кросс-энтропия. Так мы приходим к следующей теореме:
Теорема (On Connected Sublevel Sets in Deep Learning). Пусть выполнены следующие условия:
- , строго монотонна и не найдётся ненулевых с , таких что ;
- выпукла по второму аргументу и для любого ;
- Существует , для которого и для всех .
Тогда если , то
- Для каждого найдутся веса , для которых ;
- Множество подуровня связно для каждого .