Почему XOR потребовал глубины

В уроке 13 мы упёрлись в стену: один нейрон не берёт XOR. В уроке 15 перцептрон подтвердил это делом — на неразделимых данных он мечется без конца. Сегодня мы пробьём стену, и окажется, что она невысокая: достаточно одного скрытого слоя, который не проводит границу, а перекраивает само пространство, где она проводится.

Стена, к которой мы вернулись

Соберём вместе два тупика прошлых уроков. Логический нейрон Мак-Каллока–Питтса не смог вычислить XOR: его единичные наборы лежат на разных диагоналях квадрата, а одна прямая две диагонали не разделит. Перцептрон Розенблатта не смог обучиться на неразделимой паре ирисов: там, где прямой между классами не существует, правило коррекции по ошибке вечно доворачивает границу, не сходясь. Оба тупика — одно и то же ограничение, сформулированное на языке логики и на языке геометрии: один нейрон умеет только линейную границу.

Марвин Минский и Сеймур Пейперт в 1969 году показали этот предел с математической строгостью, и многие прочли их книгу как приговор всему направлению. Приговор оказался ошибкой чтения: предел касался одного слоя, а не идеи нейросети. Выход, который тогда не разглядели, геометрически прост, и мы построим его руками — без всякого обучения, просто расставив веса, как в уроке 13.

Скрытый слой: прямые как новые признаки

Идея одна и коротка. Поставим между входом и выходом промежуточный слой нейронов — назовём его скрытым. Каждый скрытый нейрон, как обычно, проводит свою прямую и выдаёт $0$ или $1$: он отвечает на вопрос «по какую сторону от моей прямой лежит точка?». Выходной нейрон получает на вход не исходные координаты $x_1,x_2$, а ответы скрытых нейронов — и проводит свою прямую уже в этом новом пространстве.

Ключ вот в чём: скрытые нейроны не решают задачу, они меняют систему координат. Исходные признаки «длина» и «ширина» заменяются признаками «справа ли от прямой $h_1$» и «справа ли от прямой $h_2$». И задача, неразделимая в старых координатах, может оказаться разделимой в новых. Граница по-прежнему прямая — но прямая в пространстве, которое скрытый слой перекроил.

XOR за три нейрона, вид сбоку

Вернёмся к XOR и построим сеть руками, пользуясь вентилями из урока 13. Нам нужно, чтобы выход был $1$ на «разных» наборах $(0,1),(1,0)$ и $0$ на «одинаковых» $(0,0),(1,1)$. Возьмём два скрытых нейрона:

$$h_1 = \mathbf 1[x_1 + x_2 \ge 1]\ (\text{ИЛИ}), \qquad h_2 = \mathbf 1[x_1 + x_2 \le 1]\ (\text{НЕ-И}),$$

и один выходной, берущий их И: $y=\mathbf 1[h_1 + h_2 \ge 2]$. Проверим по строкам. На $(0,0)$: $h_1=0$ (сумма $0<1$), значит $y=0$. На $(1,1)$: $h_2=0$ (сумма $2>1$), значит $y=0$. На $(0,1)$ и $(1,0)$: сумма ровно $1$, оба скрытых нейрона выдают $1$, и $y=1$. Единицы стоят точно на «разных» наборах — это XOR. Три нейрона в два слоя взяли то, что одному не по силам.

$x_1$	$x_2$	$h_1$ (ИЛИ)	$h_2$ (НЕ-И)	$y$ (И)
0	0	0	1	0
0	1	1	1	1
1	0	1	1	1
1	1	1	0	0

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Главный трюк: пространство, в котором XOR разделим

Теперь — сердце урока. Посмотрим, куда скрытый слой отправляет четыре входные точки. В исходных координатах $(x_1,x_2)$ единицы XOR лежат на одной диагонали, нули — на другой, и прямой их не разнять. Но нанесём те же четыре точки в новых координатах $(h_1,h_2)$ — по ответам скрытых нейронов.

Точка $(0,0)$ даёт $(h_1,h_2)=(0,1)$; точка $(1,1)$ даёт $(1,0)$; а обе «разные» точки $(0,1)$ и $(1,0)$ дают одно и то же $(1,1)$. Смотрите, что произошло: два нуля XOR разъехались в углы $(0,1)$ и $(1,0)$ скрытого квадрата, а обе единицы слиплись в угол $(1,1)$. В новом пространстве класс единиц собрался в одной точке, класс нулей — в двух других, и теперь их спокойно разделяет одна прямая (например, $h_1+h_2\ge 2$). Задача, неразделимая на входе, стала линейно разделимой после скрытого слоя:

$$(x_1,x_2)\ \xrightarrow{\ \text{скрытый слой}\ }\ (h_1,h_2), \qquad \{(0,1),(1,0)\}\mapsto(1,1),\quad \{(0,0)\!\to\!(0,1),\ (1,1)\!\to\!(1,0)\}.$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

От двух прямых к любой границе

XOR потребовал двух скрытых прямых. А что можно огородить бо́льшим их числом? Выходной нейрон, берущий И нескольких скрытых, срабатывает только там, где выполнены все их условия сразу:

$$y=\mathbf 1\Bigl[\textstyle\sum_{j} h_j \ge m\Bigr], \qquad h_j=\mathbf 1[w_j\cdot x\ge b_j],$$

и при пороге $m$, равном числу скрытых нейронов, это в точности пересечение всех их полуплоскостей. Пересечение полуплоскостей — это выпуклый многоугольник: тремя прямыми огораживается треугольник, четырьмя — четырёхугольник, и так любая выпуклая область. Возьмём вместо И — ИЛИ, и выход сработает там, где выполнено хоть одно условие: получится объединение областей, уже не обязательно выпуклое.

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

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

На реальных данных: две луны и горб проката

XOR — идеальный, но крошечный пример. Чтобы увидеть кривую границу живьём, возьмём классический для машинного обучения набор «две луны»: два серпа точек, вложенных друг в друга так, что ни одна прямая их не разделит — линейно неразделимая пара, как versicolor и virginica из урока 15, только нагляднее. Один нейрон здесь бессилен; двухслойная сеть с несколькими скрытыми прямыми огибает серпы кусочной границей и разделяет их почти без ошибок.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Чего мы пока не умеем

За всё приходится платить, и здесь плата такая: веса скрытого слоя мы расставили руками, зная ответ заранее. Для XOR это легко — четыре строки, логика на виду. Но для «двух лун» с их сотнями точек, а тем более для картинок и текстов, подобрать веса промежуточных нейронов вручную немыслимо: мы не знаем заранее, какие прямые проводить в скрытом пространстве.

И здесь возникает трудность, которая застопорила нейросети на годы. Правило перцептрона из урока 15 учит по ошибке только выходной нейрон: для него известен правильный ответ. А какой «правильный ответ» у скрытого нейрона? Никто не говорит ему, какую прямую проводить, — его цель определяется лишь тем, как его выход потом используют следующие слои. Как разослать ошибку с выхода назад, к скрытым весам, чтобы каждый узнал свою долю вины? Формально скрытый вес $w_j$ влияет на ошибку $E$ не напрямую, а через выход:

$$\frac{\partial E}{\partial w_j} =\underbrace{\frac{\partial E}{\partial y}}_{\text{из выхода}}\cdot \frac{\partial y}{\partial h_j}\cdot \frac{\partial h_j}{\partial w_j},$$

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

Русская линия: теорема Колмогорова

Почему композиция простых элементов способна выразить что угодно — вопрос не инженерный, а математический, и глубочайший ответ на него дал Андрей Колмогоров. В 1957 году он вместе с учеником Владимиром Арнольдом доказал теорему о суперпозиции: любую непрерывную функцию многих переменных можно точно представить композицией и суммой функций одной переменной. Иными словами, «сложная функция многих аргументов» всегда разбирается на слои простых одномерных функций — ровно та архитектура, что у нейросети: слой преобразований, потом сложение, потом снова преобразование.

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

Лаборатория: согните пространство руками

Порядок опытов. Перед вами «две луны», неразделимые прямой. Добавляйте скрытые нейроны — каждый рисует свою прямую — и настраивайте их наклон и сдвиг; выходной слой комбинирует их в И или ИЛИ. Соберите из нескольких прямых замкнутую область вокруг одного серпа и посмотрите, как счётчик верно разделённых точек ползёт вверх. Переключитесь на XOR и убедитесь, что двух скрытых прямых хватает. Вы делаете руками ровно то, чему сеть научится сама в следующем блоке, — гнёте пространство, пока граница не станет простой.

Сборка: стена оказалась порожком

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

Задачи