Логический нейрон Мак-Каллока–Питтса

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

Идея на разломе двух наук

Мы открываем новый модуль. Позади остался мир данных — таблицы, их паспорта, законы, которые из них добывают. Впереди — устройство, которое будет эти законы находить само: искусственный нейрон и то, как он учится. Но прежде чем нейрон научится, стоит понять, на что он способен вообще без обучения, с весами, поставленными вручную. Ответ 1943 года удивителен: почти на всё, что описывается словами «и», «или», «не».

Статью «A Logical Calculus of the Ideas Immanent in Nervous Activity» написали нейрофизиолог Уоррен Мак-Каллок и логик Уолтер Питтс. Они задали вопрос на стыке двух далёких дисциплин: если нейрон мозга — это устройство, которое либо срабатывает, либо нет, нельзя ли описать работу нервной сети языком математической логики? И показали, что можно, а заодно, сами того не планируя, дали инженерам чертёж логического элемента ровно тогда, когда те строили первые вычислительные машины.

Пороговый элемент

Договоримся о модели. У нейрона есть входы $x_1,\ldots,x_d$, каждый принимает значение 0 или 1 — «сигнала нет» или «сигнал есть». Каждому входу приписан вес $w_i$ — число, задающее, насколько сильно этот вход влияет. Нейрон складывает взвешенные сигналы и сравнивает сумму с порогом $b$:

$$z=\sum_{i=1}^{d}w_i x_i, \qquad y=\mathbf 1\!\left[\,z\ge b\,\right],$$

где $\mathbf 1[\cdot]$ — индикатор: единица, если условие в скобках истинно, иначе ноль. Всё поведение нейрона задаётся набором чисел $(w_1,\ldots,w_d,b)$; меняя их, мы меняем логику. Положительный вес возбуждает — толкает сумму к порогу; отрицательный подавляет — тянет назад. Порог решает, какой суммы «достаточно».

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

Что на самом деле означают веса

Прежде чем собирать вентили, договоримся, что весам можно и чего нельзя приписывать. Соблазн читать $w_i$ как «важность входа $i$» велик, но обманчив. Во-первых, значение имеет только сумма относительно порога: пара $(w_1,w_2,b)=(1,1,2)$ и пара $(10,10,20)$ задают один и тот же вентиль И — умножьте все числа на положительную константу, и решение нейрона не изменится. Абсолютная величина веса сама по себе не значит ничего; значат лишь отношения весов и порога.

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

Три вентиля из одного нейрона

Проверим силу модели на трёх базовых операциях логики. Возьмём два входа и подберём веса руками.

Логическое И (оба входа должны быть единицами). Возьмём $w_1=w_2=1$, $b=2$. Сумма достигает порога 2 только когда оба входа равны единице — это и есть И. Логическое ИЛИ (хотя бы один вход): те же веса, но порог $b=1$; теперь хватает одной единицы. Отрицание НЕ (один вход, переворачивает значение): $w_1=-1$, $b=0$; при $x_1=0$ сумма 0 достигает порога и выход 1, при $x_1=1$ сумма $-1$ порога не достигает и выход 0.

$x_1$	$x_2$	И ($b{=}2$)	ИЛИ ($b{=}1$)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Один пороговый элемент, три фундаментальные операции — только за счёт смены двух чисел. А поскольку любую логическую функцию можно записать через И, ИЛИ и НЕ (это доказывают на первом курсе как совершенную дизъюнктивную нормальную форму), уже отсюда следует главная теорема: сеть нейронов Мак-Каллока–Питтса вычисляет любую булеву функцию. Мозг-как-схема оказался полноценным логическим устройством.

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

Любая функция — это сеть: конструкция

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

Возьмём произвольную функцию $f$ от $d$ входов, заданную таблицей истинности. Выпишем все строки, где $f=1$. Каждая такая строка — это конкретный набор нулей и единиц, и его можно «поймать» одним нейроном: поставить вес $+1$ на входы, которые в строке равны единице, вес $-1$ на входы-нули и подобрать порог так, чтобы нейрон срабатывал исключительно на этом наборе. Если в строке $k$ единиц, порог $b=k$ делает дело: только точное совпадение даёт сумму $k$, любое отклонение — меньше.

Так на первом слое мы ставим по одному нейрону-детектору на каждую единичную строку. Каждый детектор молчит везде, кроме своей строки. Осталось объединить их: во втором слое один нейрон-ИЛИ срабатывает, если сработал хоть один детектор. Готово — двухслойная сеть повторяет любую наперёд заданную таблицу истинности:

f(x)=igvee_{\,r:\,f(r)=1}\;igl[\,x=r\,igr],

где каждый терм $[x=r]$ реализован нейроном-детектором строки. Это и есть совершенная дизъюнктивная нормальная форма, переписанная в нейронах: конъюнкции — детекторы первого слоя, дизъюнкция — нейрон второго. Двух слоёв достаточно для чего угодно; вопрос лишь в том, сколько нейронов уйдёт.

Плата за универсальность — размер. Детекторов ровно столько, сколько единичных строк, а их у «злой» функции может быть до $2^{d-1}$, то есть экспоненциально много. Двухслойная сеть умеет всё, но иногда ценой необозримого первого слоя; более глубокие сети те же функции считают компактнее — и это одна из причин, почему обучение ушло «вглубь». Пока же нам важно другое: принципиальных пределов у сети нет, предел был у одного нейрона.

Геометрия: нейрон — это прямая

У логики порогового элемента есть точный геометрический двойник. Изобразим два входа как точку на плоскости: четыре возможных набора $(x_1,x_2)$ — это четыре угла единичного квадрата. Условие срабатывания $w_1x_1+w_2x_2\ge b$ задаёт полуплоскость, а её граница

$$w_1 x_1 + w_2 x_2 = b$$

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

Для И единичный угол один — $(1,1)$, и его легко отсечь прямой от трёх остальных. Для ИЛИ по одну сторону остаётся один нулевой угол $(0,0)$. Оба разделяются прямой — оба реализуются нейроном. Функции, для которых такая прямая существует, называют линейно разделимыми, и пока их можно строить поштучно.

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

Сколько функций берёт один нейрон

Раз каждая линейно разделимая функция реализуется нейроном, а неразделимая — нет, естественно спросить: много ли их? Для двух двоичных входов всего функций $2^{4}=16$ — по одному биту выхода на каждую из четырёх строк таблицы. Перечислив их, можно убедиться: ровно $14$ из $16$ линейно разделимы, и лишь две — XOR и её отрицание «равенство» — нет.

$$\#\{\text{функции от 2 входов}\}=2^{4}=16, \qquad \#\{\text{разделимые}\}=14 .$$

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

XOR: стена, о которую разбилась эпоха

Теперь функция, которая переломила историю нейросетей. Исключающее ИЛИ, XOR, выдаёт единицу, когда входы различны, и ноль, когда одинаковы: $(0,1)$ и $(1,0)$ дают 1, $(0,0)$ и $(1,1)$ дают 0. Единичные углы — на одной диагонали квадрата, нулевые — на другой. И никакая прямая не отделит одну диагональ от другой.

Это не «пока не придумали» — это доказуемо. Пусть нейрон с весами $w_1,w_2$ и порогом $b$ вычисляет XOR. Выпишем четыре условия:

$$\begin{aligned} (0,0)\to 0:&\quad 0 < b,\\ (1,0)\to 1:&\quad w_1 \ge b,\\ (0,1)\to 1:&\quad w_2 \ge b,\\ (1,1)\to 0:&\quad w_1 + w_2 < b. \end{aligned}$$

Сложим второе и третье неравенства: $w_1+w_2\ge 2b$. Из первого $b>0$, значит $2b>b$, и потому $w_1+w_2\ge 2b>b$. Но четвёртая строка требует $w_1+w_2<b$. Получили $w_1+w_2<b$ и $w_1+w_2>b$ одновременно — противоречие. Значит, весов и порога, задающих XOR, не существует: одиночный нейрон принципиально не умеет исключающего ИЛИ.

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

Два слоя ломают стену

Приговор оказался приговором одиночному нейрону, а не сети. Заметим тождество: $x_1 \text{ XOR } x_2$ истинно, когда «хотя бы один вход есть» и при этом «не оба сразу», то есть

$$x_1 \oplus x_2 = (x_1 \lor x_2)\ \land\ \lnot(x_1 \land x_2).$$

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

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

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

Считающая абстракция и её эхо в кремнии

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

$$\text{нейрон } \mathbf 1[\textstyle\sum w_i x_i\ge b] \;\;\longleftrightarrow\;\; \text{логический вентиль.}$$

Именно этот изоморфизм и позволил статье 1943 года стать мостом между биологией и вычислительной техникой. Когда через два года Джон фон Нейман проектировал архитектуру первых ЭВМ, он описывал их логические узлы языком Мак-Каллока и Питтса — не потому, что строил мозг, а потому, что их формализм был самым чистым описанием «элемента, принимающего двоичное решение».

Нейроны, которые считают

Логикой дело не исчерпывается. Раз есть И, ИЛИ и НЕ, из нейронов можно собрать арифметику. Сложение двух двоичных цифр $a$ и $b$ даёт бит суммы и бит переноса: сумма — это $a\text{ XOR }b$, перенос — это $a\land b$. XOR мы уже собрали, И — тривиально; значит, полусумматор реализуется нейронной схемой, а из полусумматоров цепочкой строится сложение чисел любой длины.

Распишем полусумматор явно. Бит переноса $c=a\land b$ — один нейрон И. Бит суммы $s=a\oplus b$ — те самые три нейрона XOR из предыдущего раздела. Пять пороговых элементов складывают одну пару битов; чтобы складывать многозначные числа, полусумматоры соединяют в цепочку, передавая перенос из разряда в разряд, — ровно как это делает арифметико-логическое устройство процессора.

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

Отсюда рукой подать до тезиса, эхом отзывающегося на урок о вычислимости: сеть пороговых элементов — не слабее логической схемы компьютера, а с памятью (петлёй обратной связи) приближается к машине Тьюринга. Мак-Каллок и Питтс формально связали нейронную сеть с автоматом, и это не осталось курьёзом: Джон фон Нейман цитировал их статью в 1945 году в докладе о конструкции ЭВМ EDVAC, описывая логические элементы будущего компьютера как «нейроны». Две ветви — живой мозг и кремниевая машина — на несколько лет заговорили одним языком.

Первый нейрон, который учился

Ограничение «веса ставит человек» продержалось недолго. В 1958 году психолог Фрэнк Розенблатт представил перцептрон — устройство с той же пороговой формулой, но снабжённое правилом, которое меняет веса само, по ошибкам. Идея проста до дерзости: показали пример, нейрон ответил, сравнили с правильным ответом; ошибся в сторону «мало» — чуть прибавили веса активных входов, ошибся в сторону «много» — чуть убавили. Повторяй, пока ошибки не иссякнут.

$$w_i \leftarrow w_i + \eta\,(y_{ ext{верный}}-y_{ ext{нейрона}})\,x_i .$$

Это первое в нашем курсе правило обучения — крошечный сдвиг весов в сторону меньшей ошибки, и мы разберём его строго в следующих уроках. Розенблатт доказал теорему сходимости: если данные линейно разделимы, перцептрон за конечное число шагов найдёт разделяющую прямую сам. Пресса встретила его восторженно, вплоть до заголовков об «электронном мозге», — и именно этот перегретый оптимизм Минский и Пейперт остудят через одиннадцать лет, напомнив про XOR. Маятник от восторга к «зиме» и обратно к глубоким сетям — сквозной сюжет всей истории ИИ, и его первый размах умещается в один пороговый элемент.

Чего этот нейрон не умеет

За всей мощью — одно зияющее ограничение, и оно определит весь дальнейший модуль. Нейрон Мак-Каллока–Питтса не учится. Все веса и пороги в этом уроке мы подбирали руками, зная нужный ответ заранее; сама модель не способна взглянуть на примеры и настроить $w_i$ под них. Это калькулятор с зашитой программой, а не ученик.

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

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

Лаборатория: соберите логику руками

Порядок опытов. Выберите целевую функцию — И, ИЛИ, НЕ, запрет — и крутите два веса и порог, пока таблица истинности нейрона не совпадёт с целевой: табло считает угаданные строки. Понаблюдайте за прямой на квадрате входов: это и есть граница нейрона, вы двигаете её весами и порогом. Затем выберите XOR и убедитесь, что ни одно положение прямой не даёт всех четырёх строк, — а потом включите режим двух слоёв и решите XOR тремя нейронами.

Сборка: сколько логики в одном пороге

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

Задачи