Во введении обсуждалось, что истинный риск нейронной сети выходит на асимптоту при стремлении ширины сети (то есть числа нейронов в слое) к бесконечности. Это намекает нам на то, что существует предельная модель, «бесконечно широкая сеть». В этом параграфе мы обсудим подходы к анализу её поведения.
Динамика обучения нейронной сети описывается эволюцией в пространстве весов – например, правилом обновления весов в градиентном спуске. Но в каком виде можно записать эволюцию бесконечно широкой сети, в которой весов бесконечно много? Есть два способа это сделать.
Первый способ – ввести меру в пространстве весов
В качестве примера рассмотрим нейронную сеть с одним скрытым слоем, скалярным выходом и скалярным входом:
Это выражение можно представить в виде , где мера на сосредоточена в весах, ассоциированных с каждым из нейронов скрытого слоя:
Здесь – мера, сосредоточенная в .
При стремлении ширины к бесконечности может иметь предел. Так, если все веса насемплированы независимо из стандартного нормального распределения , предельная мера принимает вид двумерного стандартного нормального распределения , а предсказание предельной сети можно записать в виде .
Заметим, что множитель в определении модели выше принципиально важен для того, чтобы предельная мера и представление предельной сети в виде интеграла по мере были определены. Такая параметризация носит название mean-field parameterization.
Динамику эволюции весов также можно представить в виде эволюции меры. В самом деле, в случае конечной ширины градиентный спуск говорит нам о том, как за один шаг оптимизации меняются веса, ассоциированные с каждым из нейронов, или, что то же самое, как меняется мера . Заменив в этом выражении меру на предельную, можно получить эволюцию предельной меры.
К сожалению, представление эволюции предельной сети в виде эволюции меры не даёт сказать много о свойствах предельной модели. Так, известно, что предельная модель всегда сходится в глобальный минимум на обучающей выборке, см статью On the global convergence of gradient descent for over-parameterized models using optimal transport, но мало что известно о её обобщающей способности.
Более того, лишь сети с одним скрытым слоем допускают простую формулировку в форме эволюции меры в пределе бесконечной ширины, см. статьи Mean field analysis of neural networks: A central limit theorem, On the global convergence of gradient descent for over-parameterized models using optimal transport и Trainability and accuracy of neural networks: An interacting particle system approach. Для сетей с большим числом слоёв подобная формулировка также возможна, см. статьи A mean-field limit for certain deep neural networks и A rigorous framework for the mean field limit of multilayer neural networks, но анализ усложняется.
Так, сходимость в глобальный минимум для сети с двумя скрытыми слоями была доказана лишь совсем недавно в работе Global convergence of three-layer neural networks in the mean field regime; для более глубоких сетей подобные результаты пока неизвестны.
Второй способ – вместо эволюции весов рассматривать эволюцию предсказаний модели в каждой точке
Для простоты рассмотрим задачу минимизации квадратичной функции потерь на наборе данных размера :
Будем оптимизировать эту функцию потерь градиентным спуском с шагом :
Ниже нам будет удобнее рассматривать градиентный спуск с непрерывным временем вместо дискретного:
Переход к непрерывному времени соответствует устремлению к нулю шага , если при этом число шагов растёт как , где округление применяется в любую сторону.
Обозначим через предсказание в точке модели в момент времени . Оно зависит от времени следующим образом:
Введём обозначение:
С помощью него уравнение выше можно записать более коротко:
Здесь и дальше мы будем считать, что имеет размерность .
Функция называется эмпирическим нейрокасательным ядром (Neural Tangent Kernel, NTK); подробнее о ядрах мы поговорим ниже в параграфе про ядровые методы.
Заметим, что в уравнении вся информация о весах содержится в ядре, которое является отображением из в . Как мы увидим ниже, при определённых условиях, при стремлении ширины сети к бесконечности ядро имеет предел и он не зависит от .
Обозначив этот предел через , мы приходим к следующему виду эволюции предсказаний бесконечно широкой сети:
Здесь и далее будем называть (не эмпирическим) нейрокасательным ядром или NTK. Такой термин был введён в оригинальной работе Neural tangent kernel: Convergence and generalization in neural networks.
В этом случае динамика предсказаний интегрируется следующим образом. На обучающей выборке
что даёт
Подставляя решение в , получаем
и, наконец,
Прежде, чем доказывать сходимость ядра, мы обсудим, как может применяться предельное ядро и представление эволюции предсказаний в форме (1).
Применение NTK-анализа
NTK как математический аппарат
Нам удалось проинтегрировать динамику предсказаний в явном виде. Что это даёт?
Во-первых, мы получаем достаточное условие на сходимость в глобальный минимум на обучающей выборке. Таким условием является положительная определённость матрицы Грама ядра: для некоторого .
В самом деле, в этом случае,
что даёт
Во-вторых, раз явное решение известно, можно написать оценку на обобщающую способность.
Оба этих результата опираются на то, что ядро постоянно. Как мы покажем ниже, постоянство нейрокасательного ядра нейронной сети можно гарантировать лишь в пределе бесконечной ширины. Тем не менее, если сеть конечна, но достаточно широка, можно показать, что её ядро достаточно близко к предельному, и оценки сохраняют силу.
Например, для обоснования сходимости в глобальный минимум достаточно показать, что наименьшее собственное значение эмпирического ядра с высокой вероятностью остаётся отделённым от нуля в течение обучения: с вероятностью для . В самом деле, из этого следует, что
а значит,
Формальное доказательство вы можете найти в работе Gradient Descent Provably Optimizes Over-parameterized Neural Networks, а также в конспекте лекций автора этого параграфа.
Вот ещё несколько результатов, полученных в этом направлении:
- улучшенные оценки на минимальную ширину в работе Quadratic suffices for over-parametrization via matrix chernoff bound;
- оценки для случая глубоких сетей в работе Gradient descent finds global minima of deep neural networks;
- оценки на обобщающую способность, полученные через близость ядра к предельному, в работе Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks.
Определение патологий обучения
Как мы увидим позже, NTK реальных, стандартно параметризованных, имеющих конечную ширину сетей может меняться за время обучения существенным образом: см. эмпирическую работу Deep learning versus kernel learning и теоретический анализ для сетей с одним скрытым слоем Dynamically Stable Infinite-Width Limits of Neural Classifiers.
Тем не менее, ядро в инициализации может выявить определённые патологии соответствующей нейронной сети. Рассмотрим один из примеров применения.
В некоторых состоящих из однородных блоков архитектурах (скажем, ResNet) можно увеличивать (и даже устремлять к бесконечности) число слоёв или блоков, и логично задаться вопросом о том, как при этом будет вести себя процесс обучения.
Необходимым условием обучаемости является хороший первый шаг обучения. Если он исчезающе мал, то сеть не обучится ни на первом, ни на каком-либо другом шаге. Если он слишком велик, то обучение разойдётся на первом же шаге. Как мы увидим ниже, индикатором проблем является плохая обусловленность NTK в инициализации. Например, его собственные значения могут с ростом глубины стремиться к нулю или, наоборот, к бесконечности. В первом случае какие-то из компонент выборки никогда не выучатся, во втором обучение невозможно ни при каком конечном темпе обучения.
Чтобы в этом убедиться, рассмотрим разложение матрицы Грама ядра по собственным векторами:
где , а векторы образуют ортонормированный базис. Разложим предсказание сети по этому базису: . Так как базис ортонормированный, каждая из компонент эволюционирует независимо от других. В самом деле, для дискретного градиентного спуска с шагом имеем
Таким образом, если , то никогда не сойдётся к .
Кроме того, для того, чтобы процесс сходился, шаг должен убывать обратно пропорционально наибольшему собственному числу . Если последнее стремится к бесконечности, то стремится к нулю, а значит, будем мало для всех , для которых конечен; соответствующие компоненты также никогда не сойдутся.
Подробности см. в работе Rapid training of deep neural networks without skip connections or normalization layers using Deep Kernel Shaping, а также в более ранних работах Exponential expressivity in deep neural networks through transient chaos, Deep information propagation, Resurrecting the sigmoid in deep learning through dynamical isometry, Dynamical isometry and a mean field theory of cnns, в которых использовалась похожая идея, но не использовалось понятие NTK явно. См. также главу про инициализацию в конспекте лекций.
NTK и Ядровые методы
Предельное NTK нейронной сети можно использовать в любом ядровом методе, например, в SVM. Обсудим это поподробнее и заодно разберёмся, почему NTK вообще называют ядром.
Рассмотрим задачу линейной регрессии:
Эту же задачу можно эквивалентно переписать следующим образом:
где – пространство линейных отображений с некоторой нормой на нём.
Сделаем линейное пространство евклидовым, введя на нём следующее скалярное произведение. Для и определим
Это скалярное произведение порождает норму , что и делает формулировку (5) эквивалентной формулировке (4).
Пространство линейных моделей слишком узко, однако ничто не мешает нам рассмотреть задачу вида (5), в которой будет произвольным нормированным пространством функций. Наиболее хорошо изучен случай, когда функции из являются линейными моделями в некотором (возможно, бесконечномерном) гильбертовом пространстве признаков: , где отображает в это пространство. Если последнее всё же конечномерно, то мы можем использовать матричную запись ; элементы в этой записи обычно называют первичными переменными (primal variables).
Пространство функций также оказывается гильбертовым: соответствующее скалярное произведение имеет вид
Таким образом, , если .
Любому отображению можно сопоставить симметричную положительно-определённую функцию ; функции такого вида называются ядрами.
В силу фундаментальной теоремы о представителе любое решение задачи (4) принимает вид
В отличие от , вектор всегда конечномерен: его размерность равна размеру обучающей выборки. Элементы называют двойственными (dual) переменными.
Упомянутый результат позволяет перейти от минимизации в бесконечномерном пространстве функций (или, что то же самое, минимизации в бесконечномерном пространстве признаков), к минимизации в конечномерном пространстве двойственных переменных:
Если в качестве функции потерь взять квадратичную , то получим ядровую регрессию; если же взять hinge loss , то SVM.
Заметим, что двойственная задача полностью сформулирована в терминах ядра : отображение в потенциально бесконечное пространство признаков более нигде не возникает. Поэтому мы можем использовать в качестве любую симметричную положительно определённую функцию двух переменных, не думая о том, для какого пространства признаков оно будет ядром (есть теорема, что такие функции всегда являются ядрами). Это может быть очень полезно. Так, если для эмпирического NTK в инициализации имеем , но совершенно неочевидно, какое отображение соответствует предельному NTK: .
Таким образом, мы можем использовать в качестве ядра в двойственной задаче (6) наряду с линейным или гауссовским ядром . Такой подход привлекателен тем, что обучение ядровых методов более устойчиво и имеет меньше гиперпараметров. При этом можно надеяться, что результат обучения ядрового метода с NTK в качестве ядра будет близок к результату обучения соответствующей нейронной сети.
Основная проблема ядровых методов в том, что они требуют вычисления матрицы Грама ядра на обучающем наборе данных . Её размер (где – размер выборки), так что применение ядровых методов на больших данных сильно усложняется. Более того, наивное вычисление динамики из формулы (3) требует обращения матрицы Грама, которое занимает времени.
Тем не менее, определённые оптимизации существуют. Так например, в работе Kernel methods through the roof предлагается способ приближённого вычисления () за памяти и времени. Другие подходы см. в работах Fast Finite Width Neural Tangent Kernel и Neural tangents: Fast and easy infinite neural networks in python.
Так или иначе, на малых наборах данных выражение (3) можно вычислить точно, см. результаты в работе Harnessing the power of infinitely wide deep nets on small-data tasks. Существуют также примеры задач, в которых матрицу Грама ядра достаточно посчитать только для малых , см., например, Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks.
Ещё одна проблема использования NTK в ядровых методах состоит в том, что явный подсчёт предельного NTK доступен только для сетей, состоящих из слоёв из определённого класса. В этот класс входят полносвязные и свёрточные слои, average pooling, ряд нелинейностей с одним аргументом (включая, например, ReLU и erf), layer norm, но не входят max pooling и batch norm, часто используемые в реальных архитектурах. Явный подсчёт предельного NTK для «хороших» сетей реализован в библиотеке NeuralTangents; часть явных формул для подсчёта можно найти в статье On exact computation with an infinitely wide neural net.
Тем не менее, даже в тех случаях, когда посчитать предельное NTK не представляется возможным, в качестве ядра для ядрового метода можно использовать эмпирическое NTK в инициализации
Такое ядро можно рассматривать как шумную и смещённую оценку предельного; для уменьшения шума можно использовать Монте-Карло оценку матожидания. Некоторые оптимизации подсчёта эмпирического ядра см. в работе Neural tangents: Fast and easy infinite neural networks in python.
NTK не единственное ядро, которое можно сопоставить нейронной сети. Так, NNGP-ядро – это ядро гауссовского процесса, реализуемого сетью в пределе бесконечной ширины. Подробнее можно почитать в работах Deep Neural Networks as Gaussian Processes, Wide neural networks of any depth evolve as linear models under gradient descent, Random neural networks in the infinite width limit as Gaussian processes или в конспекте лекций. Можно показать, что оно соответствует NTK-ядру для сети, в которой учится лишь выходной слой.
Так как, в отличие от NTK, для подсчёта NNGP-ядра не требуется обратный проход (backward pass), последнее более вычислительно эффективно; Towards nngp-guided neural architecture search – пример работы, в которой предпочтение отдаётся NNGP-ядру именно по этой причине.
Сходимость эмпирического ядра
Вы этом параграфе мы покажем, что при определённой параметризации эмпирическое NTK не зависит ни от времени, ни от инициализации. Мы начнём с иллюстративного примера, прежде чем формулировать строгую теорему.
Рассмотрим сеть с одним скрытым слоем, скалярным выходом и гауссовской инициализацией весов; вход для простоты тоже положим скалярным:
Здесь – ширина скрытого слоя.
Следуя одной из стандартных схем инициализации из статьи Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, дисперсия каждого слоя выбирается обратно пропорционально числу входных нейронов (подробнее см. в параграфе про тонкости обучения нейросетей).
Назовём описанную выше параметризацию стандартной.
Для сходимости ядра нам придётся несколько её видоизменить:
Назовём новую параметризацию NTK-параметризацией.
Отметим, что распределение выходов нейронов в инициализации остаётся неизменным при переходе от стандартной к NTK-параметризации. Что меняется – это динамика градиентного спуска:
При приращения весов для такой параметризации имеют порядок , в то время как сами веса имеют порядок при . Поэтому и при для любого данного и . Другими словами, с ростом размера скрытого слоя градиент будет стремиться к нулю, и каждый из весов в пределе останется в начальной точке.
Сравним с градиентным спуском в стандартной параметризации:
В этом случае веса выходного слоя имеют порядок при , но получают приращения порядка в этот момент времени, в то время как веса входного слоя имеют порядок при , но получают в этот момент времени приращения порядка .
В новой параметризации эмпирическое NTK выглядит следующим образом:
Так как и при для любых заданных и , выражение выше асимптотически эквивалентно
а значит, сходится к
при в силу закона больших чисел.
Предельное ядро не зависит ни от времени , ни от инициализации. Мы будем называть это ядро нейрокасательным или просто NTK (его не стоит путать с эмпирическим NTK ).
Ещё раз подчеркнём, что это работает для NTK-параметризации, но не для стандартной. Для стандартной параметризации эмпирическое NTK в инициализации расходится с шириной:
Подробнее мы поговорим об этом в одном из следующих параграфов.
Для NTK-параметризации сходимость эмпирического ядра выполняется не только для сетей с одним скрытым слоем. Так, рассмотрим полносвязную сеть с слоями:
Здесь , и для всех остальных .
Положим, что веса инициализируются из стандартного нормального распределения. Поставим задачу оптимизации дифференцируемой функции потерь :
где – объединение всех весов сети.
Теорема ниже доказана в оригинальной работе по NTK:
Теорема. В предположениях выше, если из и липшицева и из и липшицева, то сходится к по вероятности при последовательно .
Оказывается, что эта теорема верна не только для полносвязных сетей с гладкими активациями.
Определим тензорную программу как начальный набор переменных определённых типов и последовательность команд. Каждая команда порождает новую переменную, действуя на уже имеющиеся.
Переменные бывают трёх типов:
- : матрицы с независимыми элементами из ;
- : вектора размера с асимптотически независимыми нормальными элементами;
- : образы -переменных относительно поэлементных нелинейностей.
Для переменной запись будет означать, что имеет тип .
Команды бывают следующие:
- trspop: (перевести переменную типа со значением в переменную типа со значением );
- matmul: ;
- lincomb: ;
- nonlin: (здесь мы несколько выходных векторов агрегируем в один с помощью покоординатной, возможно, нелинейной функции).
Формализм тензорных программ позволяет представить прямой и обратный проход широкого класса нейронных архитектур, который включает свёрточные сети, рекуррентные сети, сети с residual слоями. Хотя и ни одна из операций выше не может порождать новые -переменные (веса), любое наперёд заданное число шагов градиентного спуска можно представить в рамках одной тензорной программы (посредством «развёртывания» шагов градиентного спуска).
Назовём величину шириной тензорной программы.
Основная «предельная» теорема тензорных программ представлена ниже:
Master theorem (G. Yang, Tensor programs III: Neural matrix laws). Рассмотрим тензорную программу с -величинами, удовлетворяющую определённым начальным условиям. Пусть все нелинейности и функция полиномиально ограничены. Тогда
почти наверное при , где и могут быть вычислены по некоторым рекурентным правилам.
Оказывается, что если тензорная программа выражает прямой и обратной проход в некоторой нейронной сети, то NTK сети в инициализации всегда можно представить в виде для некоторой функции , см. Tensor programs II: Neural tangent kernel for any architecture.Таким образом, теорема выше доказывает существование и детерминированность предельного ядра в инициализации, а также даёт способ его вычисления. Более того, это верно и для ядра в любой фиксированный момент времени, см. Tensor Programs IIb.
В качестве иллюстрации обратимся вновь к сети с одним скрытым слоем. Рассмотрим тензорную программу, вычисляющую прямой и обратный проходы на входах и . Такая программа порождает следующие -величины: , , и . Напомним, что эмпирическое NTK равно
Положив
получим выражение как раз в виде, требуемом Master Theorem.
Стандартная параметризация и эволюция ядра
Как было отмечено в предыдущем параграфе, эмпирическое NTK двухслойной сети расходится с шириной при стандартной параметризации.
При , так как независимы и имеют порядок , сумма расходится пропорционально .Так как для квадратичной функции потерь , предсказание модели в любой точке получает приращение порядка на первом же шаге обучения; для задачи регрессии такая модель теряет смысл.
Однако для классификации величина предсказаний не играет роли: для бинарной классификации важен лишь знак, а для многоклассовой – индекс максимального логита. Таким образом, в этом случае, несмотря на расходящееся ядро, предел при бесконечной ширине имеет смысл, см. Dynamically Stable Infinite-Width Limits of Neural Classifiers.
Рассмотрим нормализованное эмпирическое NTK . Его предел в инициализации равен . Назовём этот предел нормализованным NTK и обозначим .
В отличие от ядра в NTK-параметризации, нормализованное NTK при стандартной параметризации зависит от времени:
Напомним, как выглядит градиентный спуск в стандартной параметризации:
При , , в то время как . Так как и , для любого , не зависящего от , , , и .
Наивная оценка сумм даёт для любого , не зависящего от . Таким образом, нормализованное ядро зависит от времени даже в пределе бесконечной ширины. Экспериментальный анализ эволюции ядра реальной нейронной сети в стандартной параметризации см. в работе Deep learning versus kernel learning.
Преимущество нейронных сетей над ядровыми методами, в том числе с NTK, может быть связано, в частности, с зависимостью предельного ядра от времени. В самом деле, ядро измеряет «похожесть» в некотором пространстве признаков. Для NTK это пространство фиксировано, в то время как нейронная сеть меняет своё ядро по ходу обучения, возможно, делая его более подходящим для задачи.