Нейронные сети, графы и эмерджентность30.07.2023 18:46

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

Нейронные сети

Нейронные сети сейчас — крайне активно развивающаяся сфера, в которой каждый день происходит новая научная революция, появляются новые архитектуры, фундаментально меняющие всю область и быстро имплементируемые в реальные продукты. Однако для этой, относительно новой области, все еще существует ряд крайне важных проблем, методы решения которых сейчас, с моей точки зрения, оставляют желать лучшего. Одна из интереснейших проблем сейчас заключается в том, что новые архитектуры — это по сути, рукомахательно придуманные лайфхаки. Посмотрим на конкретные примеры:
YoloR: You Only Learn One Representation: Unified Network for Multiple Tasks

Архитектура YoloR, основная магия заключается в implicit knowledge блоке

Данная сеть на датасете COCO в рамках задачи детектирования изображения превосходит большинство своих конкурентов по ряду параметров (во всяком случае превосходила на момент выхода).

Сравнение разных версий Yolo

Однако, если вы решитесь прочитать саму статью о данной модели, то все объяснение, почему данная сеть стала работать лучше, будет сводиться к «Ну, потому что implicit knowledge», без каких то подробностей. Нестрого говоря, вся магия данной архитектуры заключается в блоке без входов. И почему это работает — не очень ясно.

Базовая идея сети типа трансформер

Но может, это плохой пример? Обратимся к тому, что у всех на слуху: Трансформеры.
Начало данной, без преувеличения, прорывной архитектуры было положено в статье:
Attention Is All You Need

Основная идея статьи, как следует из названия, заключается в том, что добавление multi-head attention позволяет превосходить практически любые другие архитектуры.

Multi-head attention

И это касается не только обработки текстов — трансформеры так же прекрасно справляются с обработкой изображений (SWIN).
Так в чем же проблема?
А в том, что, что архитектура на чистом multi-head attention не просто плоха — она не будет работать:
Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth
А что будет, если мы совсем уберем из типичной архитектуры трансформера self-attention? Мы получим
MLP-Mixer: An all-MLP Architecture for Vision

MLP-Mixer, по сути представляет собой ViT без attention

В котором все self-attention будут заменены на обычные MLP слои. И если мы попробуем сравнить эту архитектуру с аналогами, но с использованием attention механизма, мы неожиданно осознаем, что потери в качестве работы будут незначительны:

Сравнение Mixer архитектуры с другими SOTA моделями

При этом никакого фундаментального и цельного математического бэкграунда, который бы объяснял, почему одна сеть лучше другой в определенной задаче — нет.
Я совру, если скажу, что никто не пытается это изучать. Выходит множество статей на эту тему: On the Mathematical Understanding of ResNet, The Modern Mathematics of Deep Learning, etc. Мне нравятся эти статьи, они необходимы и интересны для разработок архитектур под конкретные задачи…
Однако глобально проблема не меняется. Сейчас попытки формализовать бэкграунд нейронных сетей сфокусированы в основном на работе с отдельными частями сети — слоями, блоками и функциями.
Но, возможно, недостаточно просто смотреть на вопросы сходимости, отдельные блоки сети и т.д. Возможно, стоит посмотреть на проблему шире?

Графы

Базовый скелет нейронной сети — это граф весов. В таком случае, архитектура сети — ее устройство, всяческие skip-connections, feature pyramids — это различные топологии сети. Топологические, в широком смысле, свойства графа могут задаваться его инвариантами. Таким образом графы с одинаковыми инвариантами могут пониматься как одинаковые. В качестве одного из самых интересных инвариантов можно указать полиномы Татта. Допустим у нас есть граф G = (V, E) — где V — число вершин, E — число ребер. Тогда полином Татта:

$T_G(x,y)=\sum\nolimits_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$

где k (A) — число компонент связности графа (V, A). Данные полиномы задают широкий спектр различных свойств графа, таких как число деревьев T (2,1), число остовов T (1, 1), etc. В широком смысле полиномы Татта характеризуют степень связности графа. Опишем простой пример расчета полинома. Интересно то, что полином Татта может быть рассчитан рекурсивно:

$T_{\emptyset} (x,y) = 1\\ \text{If e is a loop: } T_G (x, y) = yT_{G \backslash e} (x, y) \\ \text{If e is a bridge: } T_{G} = xT_{G/e} (x,y)\\ \text{else: } T_G (x,y) = T_{G \backslash e} (x,y) + T_{G/e} (x, y)$

где G\e — граф G с удаленным ребром e, G/e — граф G, где вершины при ребре e — склеены. Пример:

Пример расчета полинома Татта

Смотрим на ребро, помеченное пунктирной линией. Полином такого графа распадается на сумму двух:
1) Справа пунктирное ребро удалено
2) Слева пунктирное ребро стянуто. Результат стягивания аналогично распадается на сумму двух других полиномов. В итоге, рекурсивно получаем сумму мономов, указанных на изображении.

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

Эмерджентность

Самое характерное свойство эмерджентной системы: Наличие у системы свойств, не присущих её компонентам по отдельности. Простейший пример эмерджентности, который, я уверен, известен многим из читателей: Клеточные автоматы.

Пример клеточного автомата: Источник

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

Но как это все связано с нейронными сетями, графами и полиномами Татта?
На самом деле эмерджентность — это свойство не только клеточных автоматов или их аналогов, но любых сложных систем. То есть систем, состоящих из множества отдельных компонент. И самый характерный пример подобных систем, с точки зрения физики — это фазовые переходы. Простейший пример — модель Поттса на графе.

$H_p = -J_p \sum_{(i,j)}\delta(s_i,s_j)$

где s — вектора, заданные в вершинах графа (будем называть их «спины»), J — какой то коэффициент (можно считать его матрицей смежности графа), H — гамильтониан модели Поттса (энергия), дельта — дельта Кронекера.
Проще говоря, данная модель говорит: чем больше рядом с тобой соседей, таких же как ты, тем лучше (тем меньше твоя энергия).

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

Но как же все это связано с полиномами Татта, о которых я писал?
Дело в том, что в статистической физике основным математическим инструментом является функция от гамильтониана:

$Z = \operatorname{tr} ( e^{-\beta \hat{H}} )$

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

Но к чему весь этот пассаж о фазовых переходах?
Дело в том, что нейронные сети, по своей сути, являются сложной системой. Но, что более интересно: в них есть фазовые переходы. И тут можно задаться вопросом: А вдруг возможно этот же фреймворк использовать для анализа зависимости свойств нейронной сети от ее архитектуры?

Послесловие

На самом деле я не упомянул еще важную взаимосвязь: Известно, что нейронные сети, по крайней мере в каких то случаях, могут быть переформулированы в теоретико-игровых терминах как задача поиска решения для какой то игры. И на самом деле, в каком то смысле, некоторые равновесные состояния в теории игр соответствуют фазовым переходам из статистической физики (модель Поттса <=> QRE).

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

Такой подход позволил бы нам учитывать коллективное поведение нейронной сети в целом, а не свойств отдельных ее элементов.