Крис Ола: нейросети, многообразия и топология

Почему это конспект, а не перевод

У блога Криса Олы нет открытой лицензии, поэтому ниже — пересказ своими словами, с нашими примерами и кодом. Короткие цитаты даны в кавычках. Главное в эссе — анимации того, как сеть шаг за шагом «распутывает» данные; их стоит посмотреть в оригинале. Исходный текст эссе открыт на GitHub: colah/NN-Topology-Post.

Коротко

• Каждый слой нейросети переводит данные в новое представление (representation). Последний слой просто проводит прямую (в многомерном случае — гиперплоскость). Значит, задача скрытых слоёв — так деформировать пространство, чтобы классы стало можно разделить прямой.
• Слой вида $\tanh(Wx + b)$ с квадратной невырожденной матрицей $W$ растягивает и сжимает пространство, но не рвёт и не склеивает его. В топологии такие отображения называются гомеоморфизмами.
• Отсюда жёсткий вывод: если один класс со всех сторон окружён другим (круг внутри кольца), сеть, у которой в каждом слое всего 2 нейрона, не может разделить их ни при какой глубине. Добавьте третий нейрон — задача становится тривиальной.
• По гипотезе многообразий реальные данные (картинки, звук) лежат на маломерных «поверхностях» внутри огромного пространства. Классификация — это распутывание переплетённых поверхностей.
• Когда распутать честно нельзя, сеть идёт «лёгким путём»: растягивает перепутанные места в тонкие нити. Это даёт высокую точность, но огромные производные — и, возможно, объясняет состязательные примеры.

Как читать вместе с курсом

Эссе стоит открыть после урока 3.1.1 «Нейрон, слой, MLP»: там вы узнаёте, что слой — это линейное преобразование плюс нелинейность, и встречаете теорему об универсальной аппроксимации. Ола показывает обратную сторону: что не может сделать узкая сеть, сколько бы слоёв в ней ни было.

Топологические термины (гомеоморфизм, изотопия, зацепление) в эссе объяснены на пальцах. Строгие доказательства можно пропустить без потери главной мысли — запомните картинку «слой мнёт резиновый лист, но не режет его». Раздел про слой k-ближайших соседей лучше читать после урока 2.3.1 «kNN, деревья решений, ансамбли».

1. Смотрим, что сеть делает с точками

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

Но интереснее смотреть не на вход, а на то, куда скрытый слой переносит точки. Если у скрытого слоя два нейрона, каждая точка получает две новые координаты — активации этих нейронов, — и картинку снова можно нарисовать на плоскости. Оказывается, в этих новых координатах кривые расходятся так, что их разделяет обычная прямая. Это и есть смысл скрытого слоя: построить такое представление данных, в котором задача становится линейной.

2. Слой как непрерывная деформация

Самое красивое место эссе — анимация, где переход от входа к скрытому слою показан не скачком, а плавным движением. Слой $\tanh(Wx + b)$ раскладывается на три шага:

1. умножение на матрицу весов $W$ — линейное преобразование: поворот, растяжение, сдвиг «наискосок»;
2. прибавление вектора $b$ — параллельный перенос;
3. поэлементное применение гиперболический тангенсгиперболический тангенсEN hyperbolic tangent (tanh)tanh x = (eˣ − e⁻ˣ)/(eˣ + e⁻ˣ) — «сигмоида» со значениями от −1 до 1. Производная 1 − tanh² x. — каждая координата «сплющивается» в интервал $(-1, 1)$.

flowchart LR
x["точки x"] -->|"× W: повернуть и растянуть"| y["Wx"]
y -->|"+ b: сдвинуть"| z["Wx + b"]
z -->|"tanh: сплющить в (−1, 1)"| h["новое представление h"]

Слой tanh(Wx + b) как три последовательные деформации плоскости

Каждый из трёх шагов можно проиграть как анимацию, и тогда вся сеть выглядит как фильм: лист бумаги с нарисованными точками растягивается, поворачивается и сминается, пока синие и красные точки не окажутся по разные стороны прямой. У Олы так показана сеть из четырёх скрытых слоёв, которая распутывает две слегка закрученные спирали. А рядом — сеть, которая не справляется со спиралями, закрученными сильнее.

Ола подчёркивает: спирали трудны только потому, что сеть узкая. С широкими слоями эта задача решается легко. Узкие сети — удобная лаборатория: в двух-трёх измерениях всё видно глазами.

3. Топология слоя tanh: тянуть можно, резать нельзя

Посмотрите на три шага ещё раз. Ни один из них не разрывает пространство и не склеивает разные точки в одну, если матрица $W$ квадратная и невырожденная (её определитель не равен нулю, то есть разные точки она переводит в разные). Растягивать и сжимать — можно, резать и складывать пополам — нельзя.

Отображения с таким свойством топологи называют гомеоморфизмами: это взаимно однозначные отображения, непрерывные в обе стороны. Связное множество остаётся связным, дырка остаётся дыркой, «внутри» остаётся «внутри».

Ола формулирует это как теорему. Проверим каждый шаг словами:

• Умножение на $W$ с ненулевым определителем — взаимно однозначное линейное отображение, у него есть обратное ($W^{-1}$), и оба непрерывны.
• Сдвиг на $b$ обращается сдвигом на $-b$.
• $\tanh$ строго возрастает и непрерывна, у неё есть непрерывная обратная функция (если следить за областью значений). То же верно для сигмоиды и softplus. А вот у ReLUReLU (выпрямитель)EN rectified linear unit (ReLU)ReLU(z) = max(0, z). Дешёвая, не насыщается при z > 0; минус — «мёртвые» нейроны, у которых z < 0 на всех примерах. обратной нет: все отрицательные числа она отправляет в 0, то есть склеивает точки.

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

Проверим на числах

Возьмём $W = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}$. Её определитель $2 \cdot 1 - 1 \cdot 1 = 1 \ne 0$, значит разные точки перейдут в разные: из $W x = W y$ следует $x = y$. А у матрицы $\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ определитель $4 - 4 = 0$: точки $(2, -1)$ и $(0, 0)$ обе переходят в $(0, 0)$ — плоскость сплющилась в прямую.

4. Круг внутри кольца: где глубина не помогает

Теперь главный пример. На плоскости два класса:

$A = \{x : \lVert x \rVert < 1/3\}, \qquad B = \{x : 2/3 < \lVert x \rVert < 1\}.$

Читается так: $A$ — точки на расстоянии меньше $1/3$ от начала координат (маленький диск), $B$ — точки на расстоянии от $2/3$ до $1$ (кольцо вокруг диска). Например, точка $(0{,}1;\ 0{,}2)$ лежит на расстоянии $\sqrt{0{,}01 + 0{,}04} \approx 0{,}22$ и относится к $A$, а точка $(0{,}6;\ 0{,}5)$ — на расстоянии $\approx 0{,}78$, это $B$.

Утверждение Олы: сеть, у которой в каждом скрытом слое по 2 нейрона, не может правильно классифицировать эти данные при любой глубине.

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

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

Ола показывает, как такая сеть мучается при обучении: граница мечется и в итоге застревает в бесполезном локальном минимумелокальный минимумEN local minimumТочка, рядом с которой нет точек ниже, — дно «ямы». Глобальный минимум (global minimum) — самая низкая точка вообще., хотя около 80% точек всё же классифицируются верно. Он подписывает анимацию: «для этой сети усердия недостаточно».

С тремя нейронами в скрытом слое задача решается мгновенно: сеть поднимает диск в третье измерение, как горку на листе, и разделяет классы плоскостью. Это легко проверить самим.

import torch, math
torch.manual_seed(0)

def make_data(n=2000):
    # класс A: диск радиуса 1/3; класс B: кольцо от 2/3 до 1
    r = torch.cat([torch.rand(n) / 3, 2/3 + torch.rand(n) / 3])
    phi = torch.rand(2 * n) * 2 * math.pi
    X = torch.stack([r * torch.cos(phi), r * torch.sin(phi)], dim=1)
    y = torch.cat([torch.zeros(n), torch.ones(n)])
    return X, y

def train(width, depth=3, steps=3000, seed=0):
    torch.manual_seed(seed)
    X, y = make_data()
    layers, d_in = [], 2
    for _ in range(depth):                       # несколько скрытых слоёв одинаковой ширины
        layers += [torch.nn.Linear(d_in, width), torch.nn.Tanh()]
        d_in = width
    model = torch.nn.Sequential(*layers, torch.nn.Linear(d_in, 1))
    opt = torch.optim.Adam(model.parameters(), lr=0.01)
    for _ in range(steps):
        loss = torch.nn.functional.binary_cross_entropy_with_logits(model(X).squeeze(1), y)
        opt.zero_grad(); loss.backward(); opt.step()
    acc = ((model(X).squeeze(1) > 0).float() == y).float().mean().item()
    return acc

for width in [2, 3]:
    accs = [round(train(width, seed=s), 3) for s in range(3)]
    print(f"ширина {width}: точность {accs}")

Вывод (около минуты на CPU):

ширина 2: точность [0.932, 0.921, 0.935]
ширина 3: точность [1.0, 1.0, 1.0]

Три слоя по 2 нейрона дают 92–93%, но не 100%: часть точек кольца сеть «протаскивает» не туда. Этот обходной манёвр Ола разбирает в разделе 7. Три нейрона в каждом слое — и ошибок нет.

Одномерный вариант

Ещё проще то же самое видно на прямой: $A = [-\tfrac13, \tfrac13]$, а $B$ — два отрезка по бокам, $[-1, -\tfrac23]$ и $[\tfrac23, 1]$. Один нейрон (одна координата) разделить их не может: середина окружена краями. Два нейрона — могут. Ола описывает, что выучивает сеть: один нейрон «загорается» при $x > -\tfrac12$, второй — при $x > \tfrac12$. Если горит первый, а второй нет, мы в $A$.

Соберём это вручную, заменив $\tanh$ на ступеньку для наглядности: $h_1 = [x > -0{,}5]$, $h_2 = [x > 0{,}5]$, выход $= h_1 - 2h_2 - 0{,}5$, класс $A$, если выход положителен.

$x$	$h_1$	$h_2$	выход	класс
$-0{,}8$	0	0	$-0{,}5$	B
$0$	1	0	$+0{,}5$	A
$0{,}8$	1	1	$-1{,}5$	B

В плоскости $(h_1, h_2)$ три группы точек легли в три угла квадрата, и $A$ отделяется от $B$ прямой.

5. Гипотеза многообразий

Важно ли всё это для настоящих данных? Ола отвечает: да, если всерьёз принять гипотезу многообразий (manifold hypothesis). Она говорит, что естественные данные образуют маломерные многообразия — «поверхности» — внутри пространства, где они записаны.

Пример: чёрно-белая картинка 28×28 — точка в 784-мерном пространстве. Но почти все такие точки — шум. Настоящие изображения цифры «3» занимают тонкую «плёнку»: плавно сдвиньте тройку, поверните или сделайте толще — точка непрерывно поползёт по этой плёнке. Ола приводит и экспериментальный довод: в работе Карлссона и соавторов маленькие кусочки природных изображений образуют бутылку Клейна — конкретную двумерную поверхность.

Если гипотеза верна, классификатор по сути разделяет набор переплетённых многообразий. Ола оговаривается: вряд ли многообразие картинок собак целиком окружено многообразием кошек. Но бывают и более правдоподобные топологические ловушки — о них следующий раздел.

6. Зацепления и изотопия

Возьмите два тора (бублика), продетых друг в друга, как звенья цепи. Это зацепление (link) — объект теории узлов. В трёхмерном пространстве их нельзя растащить без разреза. Сети, у которой в каждом слое 3 нейрона, они не по силам: нужен четвёртый — дополнительное измерение.

Ола переворачивает взгляд: непрерывная анимация работы сети — это процедура распутывания. Если сеть шириной 3 справилась с зацеплением, значит, оно на самом деле было «незацеплением» (unlink): клубок, который можно разобрать без разрезов. В топологии такое плавное распутывание называется объемлющей изотопией (ambient isotopy) — семейством гомеоморфизмов $F_t$, которое при $t = 0$ ничего не меняет, а при $t = 1$ переводит исходную картину в итоговую.

Вторая теорема эссе: такая изотопия между входом и представлением слоя существует, если (а) матрица $W$ невырожденная, (б) разрешено переставлять нейроны скрытого слоя, (в) нейронов больше одного. Идея доказательства — снова по шагам:

• матрицу с положительным определителем можно плавно «довернуть» от единичной до $W$ (множество таких матриц связно); если определитель отрицательный, меняем местами два нейрона, и знак меняется;
• сдвиг проигрывается как $x \mapsto x + tb$ при $t$ от 0 до 1;
• нелинейность — как $x \mapsto (1 - t)x + t\,\sigma(x)$.

Дальше Ола размышляет вслух. Узлы и зацепления — одномерные многообразия, но для распутывания всех нужно четыре измерения. В общем случае любые $n$-мерные многообразия распутываются в $2n + 2$ измерениях. Ола честно пишет, что мало знает теорию узлов, и оставляет открытые вопросы — например, хватит ли трёх нейронов для любого незацепления. Эссе задумано как эксперимент «открытого исследования»: с вопросами к читателям.

7. Лёгкий путь: растянуть в нитку

Что делает сеть, которой не хватает измерений? Самое естественное и «дешёвое»: растащить многообразия как получится, а перепутанные места вытянуть в тонкие нити. Честного решения это не даёт, но точность получается высокой — поэтому такой локальный минимум заманчив. Именно это мы видели в коде: 93% вместо 100%.

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

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

8. Можно ли придумать слои получше

Чем больше Ола думает о стандартных слоях (аффинное преобразование плюс поэлементная активация), тем меньше они ему нравятся как инструмент для работы с многообразиями. Он предлагает два направления.

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

$F(x) = \frac{v_0 f_0(x) + v_1 f_1(x)}{1 + f_0(x) + f_1(x)},$

где $v_0, v_1$ — векторы сдвига, а $f_0, f_1$ — гауссовы «колокола» вокруг опорных точек. Вблизи первой опорной точки $f_0$ велико и сдвиг почти равен $v_0$, вдали от обеих $F(x) \approx 0$. Идея навеяна радиальными базисными функциями.

Слой k ближайших соседей. Требовать, чтобы классы в конце делились гиперплоскостью, — возможно, чрезмерно. Естественнее спрашивать: ближе ли точка к своим, чем к чужим? Это метод k ближайших соседейметод k ближайших соседей (kNN)EN k-nearest neighbors (kNN). Ола провёл опыт: обучил свёрточную сеть на MNISTMNIST (рукописные цифры)EN MNIST70 000 изображений рукописных цифр 28×28 (60 000 обучающих и 10 000 тестовых). «Hello, world» глубокого обучения. (около 1% ошибок на тесте), отрезал последний softmax-слой и классифицировал представления методом k ближайших соседей. Ошибка стабильно падала ещё на 0,1–0,2 процентного пункта.

Затем он попробовал учить сеть сразу под kNN. Взвешенный kNN (вес соседа $1/\text{расстояние}$) дифференцируем по представлению, поэтому его можно поставить вместо softmax. Чтобы не прогонять всю выборку на каждом шаге, каждый элемент мини-батча классифицируется по остальным элементам того же батча. Результат пока скромный: 4–5% ошибок. Но Оле нравится сама постановка: мы просим сеть сжимать каждое многообразие и раздвигать разные, а не обязательно разрезать пространство плоскостью. Сегодня эта идея узнаваема в контрастивном обучении и в поиске по эмбеддингам (урок 4.3.1).

9. Выводы автора

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

Что изменилось с 2014 года

Эссе написано до ResNet, нормализаций и трансформеров. Остаточная связь $x + f(x)$ (урок 3.4.2) — как раз «маленький сдвиг вдоль векторного поля» на каждом слое, и позже идею непрерывной деформации развили нейронные ОДУ. Ширина современных сетей — сотни и тысячи нейронов, так что топологический запрет Олы на практике почти не мешает. Ценность эссе — в картинке, которая остаётся верной: сеть учится такому представлению данных, в котором задача становится простой.

Что сделать руками

1. Запустите код из раздела 4. Замените Tanh на ReLU при ширине 2: ReLU — не гомеоморфизм, она склеивает точки. Изменилась ли точность? Почему теорема Олы к ReLU-сетям напрямую не применима, а задача всё равно трудная?
2. Увеличьте глубину до 6 при ширине 2. Растёт ли точность выше 93%? (Подсказка Олы: глубина не помогает.)
3. Откройте демо Карпатого на ConvNetJS, которое Ола советует в эссе: там видно, как скрытый слой деформирует плоскость во время обучения. Поставьте в слоях по 2 нейрона и попробуйте разделить «круг в кольце».
4. Повторите опыт Олы с kNN: обучите небольшой MLP на MNIST из урока 3.3.2 «nn.Module, оптимизаторы, цикл обучения», возьмите выходы предпоследнего слоя и классифицируйте их sklearn.neighbors.KNeighborsClassifier. Стало ли лучше, чем у softmax?

Словарик

EN	RU
representation	представление (данных)
hidden layer	скрытый слой
manifold	многообразие
manifold hypothesis	гипотеза многообразий
homeomorphism	гомеоморфизм — взаимно однозначное отображение, непрерывное в обе стороны
non-singular matrix	невырожденная матрица (определитель не равен нулю)
linearly separable	линейно разделимые (классы)
link / unlink	зацепление / незацепление (теория узлов)
ambient isotopy	объемлющая изотопия — плавное распутывание без разрезов
contractive penalty	сжимающий штраф (за большие производные слоя)
vector field	векторное поле
k-nearest neighbors (k-NN)	метод k ближайших соседей