Персептрон 🧠

В уроке 326 ты познакомился с общей формулой искусственного нейрона: взвешенная сумма входов, к которой применяется функция активации. Эта формула звучит абстрактно, пока за ней не стоит конкретная историческая модель — а она есть, и появилась она на 15 лет раньше, чем большинство людей вообще начало думать об «искусственном интеллекте» как о работающей технологии. В 1958 году психолог Фрэнк Розенблатт построил устройство, которое умело не просто вычислять взвешенную сумму, а обучаться — подстраивать свои веса на основе собственных ошибок, без единой строчки явно запрограммированных правил. Это устройство называлось персептрон, и весь современный глубокий обучение в самом буквальном смысле выросло из этой одной идеи.

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

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

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

История

Фрэнк Розенблатт работал психологом в Корнеллской авиационной лаборатории (Cornell Aeronautical Laboratory) и интересовался не столько инженерией, сколько тем, как устроено обучение в биологическом мозге — в частности, идеями Дональда Хебба о том, что связи между нейронами усиливаются при совместной активности. В 1958 году Розенблатт не просто предложил математическую формулу — он построил физическое устройство под названием Mark I Perceptron: сетчатку из 400 фотоэлементов, реагирующих на свет, соединённую с блоком из электромеханических потенциометров, которые играли роль весов связей. Обучение происходило буквально механически: маленькие электромоторы физически проворачивали ручки потенциометров, увеличивая или уменьшая сопротивление — то есть вес — в зависимости от того, ошиблась машина или нет. Персептрон Розенблатта был первой работающей моделью нейрона (после чисто теоретической, необучаемой модели Маккаллока-Питтса 1943 года, о которой шла речь в уроке 326), которая училась на собственном опыте методом проб и ошибок.

Демонстрация Mark I Perceptron вызвала настоящий ажиотаж. Пресса того времени — включая широко цитируемые публикации вроде The New York Times — рассказывала об устройстве, которое ВМФ США якобы представлял как зародыш машины, способной в будущем ходить, говорить, видеть, писать, воспроизводить себя и даже осознавать собственное существование. Подобные заявления сегодня выглядят как карикатура на хайп вокруг ИИ, но в 1958 году они воспринимались всерьёз: финансирование от военных агентств текло щедро, а сам Розенблатт публично предсказывал, что персептроны в обозримом будущем станут основой для распознавания речи и изображений на уровне, недостижимом для «обычных» компьютеров той эпохи. Ожидания были подняты на высоту, которую единственный слой обучаемых линейных весов физически не мог оправдать.

Отрезвление пришло в 1969 году, когда Марвин Минский и Сеймур Пейперт (оба — из MIT) опубликовали книгу «Perceptrons: An Introduction to Computational Geometry». Минский, что немаловажно, сам ещё в 1951 году строил одну из первых обучаемых нейросетевых машин (SNARC) и прекрасно понимал предмет изнутри — его критика не была критикой стороннего скептика. Книга представляла собой строгий математический анализ возможностей и ограничений однослойного персептрона и содержала доказательство, которое мы разберём ниже во всех деталях: персептрон в принципе не способен выучить функцию XOR, потому что она не является линейно разделимой — и это не вопрос недостатка данных, времени обучения или удачной инициализации весов, а фундаментальное свойство самой модели.

Проблема была не в самом доказательстве — оно безупречно, — а в том, как его интерпретировало научное сообщество и, что важнее, органы финансирования. Книга Минского и Пейперта, а также независимо опубликованный в Великобритании доклад Лайтхилла (Lighthill Report) 1973 года, критически оценивший перспективы ИИ в целом, способствовали резкому сокращению грантов на нейросетевые исследования со стороны DARPA и других агентств на протяжении 1970-х годов. Исследования нейронных сетей на доброе десятилетие стали считаться научным тупиком, а внимание индустрии переключилось на символьный ИИ — экспертные системы и логический вывод. Возрождение началось лишь в 1986 году, когда Дэвид Румельхарт, Джеффри Хинтон и Рональд Уильямс опубликовали статью об алгоритме обратного распространения ошибки (backpropagation) для многослойных сетей — том самом инструменте, который снимает именно то ограничение, которое доказали Минский и Пейперт, и о котором пойдёт речь в уроке 328. Розенблатт этого возрождения не увидел: он погиб в результате несчастного случая на воде в 1971 году, за 15 лет до того, как его исходная идея — обучаемый искусственный нейрон — вернулась в центр внимания уже в виде многослойных сетей.

Математическая модель: взвешенная сумма и ступенчатая активация

Интуиция

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

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

Формула

Персептрон Розенблатта. Взвешенная сумма входов сравнивается с порогом; выход — строго бинарный:

$$z = \sum_{i=1}^n w_i x_i + b = w_1x_1+w_2x_2+\dots+w_nx_n+b$$

$$y = f(z) = \begin{cases}1, & z>0\\0,& z\le 0\end{cases}$$

Функция $f$ здесь — ступенчатая функция (функция Хевисайда), а не гладкая активация вроде sigmoid или ReLU из урока 326: персептрон либо полностью «срабатывает», либо не срабатывает вовсе. Геометрически уравнение $z=0$, то есть $w_1x_1+\dots+w_nx_n+b=0$, задаёт гиперплоскость (в двумерном случае — обычную прямую), разделяющую пространство признаков на два полупространства: класс персептрон определяет по тому, по какую сторону от этой границы оказался объект. Смещение $b$ играет роль отрицательного порога: исходная формулировка Розенблатта использовала порог $\theta$ и условие $\sum w_ix_i \ge \theta$, что в точности совпадает с записью через $b=-\theta$.

Разбор примеров

Пример 1 (оценка заявки персептроном). Пусть персептрон принимает решение об одобрении небольшого кредита по двум признакам: $x_1$ — нормализованный доход, $x_2$ — оценка стабильности занятости, с весами $w_1=0{,}8$, $w_2=0{,}5$, $b=-3$. Заявитель А: $x_1=2$, $x_2=3$. Тогда $z = 0{,}8\cdot2+0{,}5\cdot3-3 = 1{,}6+1{,}5-3 = 0{,}1 > 0$ — персептрон одобряет заявку ($y=1$). Заявитель Б: $x_1=1$, $x_2=2$. Тогда $z=0{,}8\cdot1+0{,}5\cdot2-3=0{,}8+1-3=-1{,}2 \le 0$ — персептрон отказывает ($y=0$). Обрати внимание: персептрон не сообщает, насколько он «уверен» в решении, — заявитель А с $z=0{,}1$ и гипотетический заявитель с $z=10$ получат абсолютно одинаковый выход $y=1$, хотя во втором случае решение явно увереннее. Это прямое следствие ступенчатой активации, которая теряет всю информацию о величине $z$, кроме её знака.

Пример 2 (уравнение разделяющей прямой и граничный случай). Для тех же весов $w_1=0{,}8$, $w_2=0{,}5$, $b=-3$ разделяющая прямая задаётся уравнением $0{,}8x_1+0{,}5x_2-3=0$, то есть $x_2 = 6-1{,}6x_1$. При $x_1=0$ прямая проходит через точку $(0,6)$, при $x_1=3{,}75$ — через точку $(3{,}75;\,0)$. Возьмём точку ровно на этой прямой: $x_1=3$, $x_2=1{,}2$. Тогда $z=0{,}8\cdot3+0{,}5\cdot1{,}2-3=2{,}4+0{,}6-3=0$. По определению модели ($z>0 \Rightarrow y=1$, иначе $y=0$) точка ровно на границе получает $y=0$ — персептрон классифицирует свою собственную разделяющую линию как часть отрицательного класса. Это не философская тонкость, а конкретное следствие строгого неравенства в формуле, которое стоит явно проверять при реализации модели в коде.

Пример 3 (смещение сдвигает границу, не меняя её наклон). Возьмём те же веса $w_1=0{,}8$, $w_2=0{,}5$, но два разных смещения: $b=-3$ и $b=-1$. Классифицируем одну и ту же точку $x_1=1$, $x_2=2$ обеими версиями персептрона. При $b=-3$: $z=0{,}8+1-3=-1{,}2\le0 \Rightarrow y=0$ (отказ). При $b=-1$: $z=0{,}8+1-1=0{,}8>0 \Rightarrow y=1$ (одобрение). Веса $w_1$, $w_2$ определяют направление разделяющей прямой (её наклон и то, какие признаки для решения важнее), а смещение $b$ определяет, насколько далеко эта прямая сдвинута от начала координат, то есть буквально задаёт «строгость» порога — ровно ту же роль, которую в исходной формулировке Розенблатта играл порог $\theta = -b$.

Почему это важно

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

Правило обучения персептрона: как исправляются ошибки

Интуиция

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

Формула

Правило обучения персептрона (Розенблатт, 1958). Для каждого обучающего примера $(x, y)$ персептрон сначала делает предсказание $\hat y = f(w\cdot x+b)$, а затем обновляет веса только если предсказание неверно:

$$w_i \leftarrow w_i + \eta\,(y-\hat y)\,x_i, \qquad b \leftarrow b+\eta\,(y-\hat y)$$

где $\eta>0$ — скорость обучения (learning rate). Если $\hat y=y$ (предсказание верное), то $y-\hat y=0$, и веса не меняются вовсе; если персептрон ошибся, то $y-\hat y=\pm1$, и веса сдвигаются на $\pm\eta x_i$. Один полный проход по всей обучающей выборке называется эпохой; правило применяется эпоха за эпохой, пока не будет сделано ни одной ошибки за целый проход целиком.

Разбор примеров

Пример 1 (полная трассировка обучения на логической функции И). Возьмём классическую логическую функцию И (AND): точки $(0,0)\to0$, $(0,1)\to0$, $(1,0)\to0$, $(1,1)\to1$ — это линейно разделимая задача. Начнём с нулевых весов $w_1=w_2=b=0$, скорость обучения $\eta=1$, примеры предъявляются циклически в указанном порядке. Вот полная трассировка всех шагов до сходимости:

Начиная с шага 21 персептрон целую эпоху (шаги 21–24) не совершает ни одной ошибки — алгоритм сошёлся. Итого потребовалось 6 эпох, 24 предъявления примеров и ровно 10 обновлений весов. Финальные веса $(2,1,-2)$ задают разделяющую прямую $2x_1+x_2-2=0$, то есть $x_2=2-2x_1$ — легко проверить, что она действительно корректно разделяет все четыре точки функции И.

Пример 2 (почему верное предсказание не меняет веса). Возьмём шаг 20 из трассировки выше: веса $(2,1,-2)$, пример $(1,1)$ с целевым значением $y=1$. Предсказание: $z=2\cdot1+1\cdot1-2=1>0 \Rightarrow \hat y=1$. Поскольку $y=\hat y=1$, разность $y-\hat y=0$, и формула обновления даёт $\Delta w_1=\eta\cdot0\cdot1=0$, $\Delta w_2=0$, $\Delta b=0$ — веса остаются буквально теми же самыми числами. Это принципиально отличает правило обучения персептрона от, например, стохастического градиентного спуска на гладкой функции потерь (урок 286): там обновление обычно происходит на каждом шаге, пусть и исчезающе малое, тогда как персептрон в буквальном смысле «не трогает» веса, если и так угадал верно.

Пример 3 (скорость обучения масштабирует веса, но не влияет на число ошибок). Повтори трассировку из примера 1, но с $\eta=0{,}1$ вместо $\eta=1$, при тех же нулевых начальных весах. Первое обновление на шаге 4 даст $\Delta w_1=0{,}1\cdot(1-0)\cdot1=0{,}1$, то есть веса станут $(0{,}1;\,0{,}1;\,0{,}1)$ — ровно в 10 раз меньше, чем при $\eta=1$. Дальше происходит нечто важное: поскольку при нулевой инициализации весь вектор весов на любом шаге равен $\eta$, умноженному на «единичную» версию из примера 1, а знак $z=w\cdot x+b$ не меняется при умножении всех весов на положительное число, — персептрон совершит ошибку ровно на тех же самых шагах, что и в основной трассировке, ни одним шагом раньше или позже. После тех же 6 эпох финальные веса окажутся равны $(0{,}2;\,0{,}1;\,-0{,}2)$ — ровно в 10 раз меньше $(2,1,-2)$, но задающие ту же самую разделяющую прямую (потому что прямая определяется отношением коэффициентов, а не их абсолютной величиной). Скорость обучения здесь влияет лишь на масштаб итоговых весов, а не на то, сколько ошибок будет сделано и на каких примерах, — это особый случай, справедливый именно из-за нулевой инициализации и жёсткой ступенчатой активации.

Почему это важно

Стоит явно проговорить один тонкий момент: правило обучения персептрона исторически появилось раньше общей теории градиентного спуска и на самом деле не является градиентным спуском в строгом смысле — ступенчатая функция активации не дифференцируема в точке разрыва и имеет нулевую производную почти всюду, поэтому классическая формула $w \leftarrow w-\eta\nabla L(w)$ из урока 285 к ней буквально неприменима. Правило Розенблатта — это отдельная, самостоятельно выведенная эвристика коррекции ошибок, которая по счастливому совпадению оказалась математически удачной (что мы докажем в следующем разделе). Именно поэтому логистическая регрессия из урока 313 заменяет жёсткую ступеньку на гладкую sigmoid-функцию — это позволяет определить настоящую, дифференцируемую функцию потерь и обучать модель полноценным градиентным спуском, а не отдельной эвристикой, придуманной специально под конкретную недифференцируемую активацию.

Теорема сходимости: почему линейная разделимость решает всё

Интуиция

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

Формула

Теорема сходимости персептрона (Новиков, 1962). Пусть обучающая выборка линейно разделима с отступом (margin) $\gamma>0$: существует вектор весов $w^*$ с $\|w^*\|=1$ такой, что для всех примеров $y_i\,(w^*\cdot x_i)\ge\gamma$ (здесь удобнее использовать метки $y_i\in\{+1,-1\}$ и включить смещение в веса через дополнительную координату, равную единице). Пусть также все входные векторы ограничены по норме: $\|x_i\|\le R$ для всех $i$. Тогда алгоритм обучения персептрона совершит не более

$$M \le \left(\frac{R}{\gamma}\right)^2$$

ошибок (обновлений весов) прежде чем сойдётся к разделяющим весам, — независимо от порядка предъявления примеров и от начальных значений весов.

Разбор примеров

Пример 1 (численная проверка границы на нашем датасете И). Возьмём разделяющие веса $w_1=1$, $w_2=1$, $b_0=-1{,}5$ (легко проверить: они корректно разделяют все четыре точки функции И). В однородных координатах $x'=(x_1,x_2,1)$ и метках $y\in\{+1,-1\}$ ($y=+1$ для класса 1, $y=-1$ для класса 0) вычислим ненормированные отступы $y_i\cdot(w\cdot x'_i)$: для $(0,0,1)$, $y=-1$: значение $=-1\cdot(-1{,}5)=1{,}5$; для $(0,1,1)$ и $(1,0,1)$, $y=-1$: значение $=-1\cdot(1-1{,}5)=0{,}5$ в обоих случаях; для $(1,1,1)$, $y=+1$: значение $=1\cdot(2-1{,}5)=0{,}5$. Минимальный ненормированный отступ равен $0{,}5$. Норма весов $\|w\|=\sqrt{1^2+1^2+1{,}5^2}=\sqrt{4{,}25}\approx2{,}062$, поэтому нормированный отступ $\gamma\approx0{,}5/2{,}062\approx0{,}2425$. Максимальная норма входного вектора $R=\|(1,1,1)\|=\sqrt3\approx1{,}732$. Граница теоремы: $M\le(1{,}732/0{,}2425)^2\approx51$. В нашей реальной трассировке (раздел про правило обучения) персептрон сошёлся всего за 10 обновлений — заметно меньше теоретической границы в 51. Это нормально и ожидаемо: теорема даёт гарантию конечности и верхнюю оценку, а не точный прогноз числа шагов, — на практике реальное число ошибок часто оказывается заметно меньше границы.

Пример 2 (отступ определяет порядок величины гарантии, а не только знак). Возьмём два гипотетических датасета с одинаковой максимальной нормой входов $R=2$, но разным отступом: у датасета A отступ мал, $\gamma=0{,}05$ (точки почти прижаты к границе), у датасета Б отступ велик, $\gamma=0{,}5$ (точки расположены далеко по обе стороны от границы). Граница теоремы для A: $M\le(2/0{,}05)^2=1\,600$; для Б: $M\le(2/0{,}5)^2=16$. Стократная разница в отступе превращается в стократную разницу в гарантированной верхней границе числа ошибок — квадратичная зависимость от $1/\gamma$ означает, что даже небольшое уменьшение отступа может резко замедлить сходимость в худшем случае.

Пример 3 (несовместимые метки — предвестник проблемы XOR). Возьмём вырожденный «датасет» из двух одинаковых точек с разными метками: $x=(1,1)$ помечена как класс 1, и та же самая точка $x=(1,1)$ помечена как класс 0. Такая выборка тривиально не является линейно разделимой (это буквально противоречие: одна и та же точка не может лежать сразу по обе стороны от любой прямой). Условие теоремы Новикова — существование отступа $\gamma>0$ — не выполняется вообще ни для каких весов, и гарантия сходимости просто не применима. При запуске обучения персептрон будет бесконечно чередовать обновления, пытаясь угодить сначала одной, потом другой метке одной и той же точки, никогда не выходя на состояние «ноль ошибок за эпоху». Этот вырожденный пример — упрощённая иллюстрация того же самого явления, которое в куда более содержательной форме встречается в задаче XOR, разобранной в следующем разделе.

Почему это важно

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

Проблема XOR: доказательство фундаментального ограничения

Интуиция

Исключающее ИЛИ (XOR) — простейшая логическая функция, которая возвращает 1, если ровно один из двух входов равен 1, и 0 в остальных случаях: $(0,0)\to0$, $(0,1)\to1$, $(1,0)\to1$, $(1,1)\to0$. На первый взгляд это выглядит не сложнее функции И или ИЛИ, которые персептрон прекрасно выучивает. Но стоит нанести эти четыре точки на плоскость, и сразу становится видно: точки одного класса (1) находятся по диагонали друг напротив друга, и точки другого класса (0) — тоже по диагонали друг напротив друга, причём диагонали пересекаются ровно в центре квадрата. Никакая одна прямая линия физически не может отделить одну диагональ от другой — какую бы прямую ты ни провела, она неизбежно окажется на «неправильной» стороне хотя бы для одной из четырёх точек.

Формула

Теорема о линейной неразделимости XOR. Не существует весов $w_1, w_2, b$, при которых персептрон со ступенчатой активацией правильно классифицирует все четыре точки функции XOR: $(0,0)\to0$, $(0,1)\to1$, $(1,0)\to1$, $(1,1)\to0$.

Разбор примеров

Пример 1 (алгебраическое доказательство от противного). Предположим, что такие веса $w_1, w_2, b$ всё же существуют. Тогда из правильной классификации каждой точки следуют четыре неравенства (класс 0 означает $z\le0$, класс 1 означает $z>0$):

из $(0,0)\to0$: $\quad b \le 0$;

из $(1,1)\to0$: $\quad w_1+w_2+b \le 0$;

из $(0,1)\to1$: $\quad w_2+b > 0$, то есть $w_2 > -b$;

из $(1,0)\to1$: $\quad w_1+b > 0$, то есть $w_1 > -b$.

Сложив последние два строгих неравенства, получаем $w_1+w_2 > -2b$. Но из второго неравенства мы знаем, что $w_1+w_2 \le -b$. Объединяя оба факта, получаем цепочку $-2b < w_1+w_2 \le -b$, откуда следует $-2b<-b$, то есть $-b<0$, то есть $b>0$. Но из самого первого неравенства $b\le0$. Мы получили одновременно $b>0$ и $b\le0$ — прямое противоречие. Значит, исходное предположение неверно: весов, разделяющих XOR, не существует ни при каких значениях $w_1, w_2, b$.

Пример 2 (геометрическое доказательство через выпуклые оболочки). Есть общий факт: два множества точек можно разделить прямой линией тогда и только тогда, когда их выпуклые оболочки не пересекаются. Возьмём отрезок, соединяющий точки класса 1: $(0,1)$ и $(1,0)$. Его середина — точка $(0{,}5;\,0{,}5)$. Теперь возьмём отрезок, соединяющий точки класса 0: $(0,0)$ и $(1,1)$. Его середина — тоже точка $(0{,}5;\,0{,}5)$. Оба отрезка проходят через одну и ту же точку плоскости — значит, выпуклая оболочка класса 1 (отрезок между $(0,1)$ и $(1,0)$) и выпуклая оболочка класса 0 (отрезок между $(0,0)$ и $(1,1)$) пересекаются в точке $(0{,}5;\,0{,}5)$. Раз выпуклые оболочки классов пересекаются, разделяющей прямой не существует в принципе — это ровно та же геометрическая картина, которую видно на рисунке с диагоналями квадрата, но выраженная строгим языком выпуклой геометрии.

Пример 3 (персептрон никогда не останавливается на XOR — конкретный устойчивый цикл). Запустим обучение персептрона на XOR с нулевых весов, $\eta=1$, порядок примеров $(0,0),(0,1),(1,0),(1,1)$. Первая эпоха: на $(0,0)$ ошибки нет; на $(0,1)$ ошибка ($\hat y=0$, $y=1$), веса становятся $(0,1,1)$; на $(1,0)$ ошибки нет ($z=1>0$, $\hat y=1=y$); на $(1,1)$ ошибка ($\hat y=1$, $y=0$), веса становятся $(-1,0,0)$. Дальше, начиная со второй эпохи, персептрон входит в устойчивый цикл длины ровно 4, в котором он ошибается абсолютно на каждом из четырёх примеров, каждую эпоху, без исключения: $(-1,0,0) \to (-1,1,1) \to (0,1,2) \to (-1,0,1) \to (-1,0,0) \to \dots$ — и так до бесконечности. Ни на одном шаге этого цикла ошибок не становится меньше; персептрон не приближается к решению, а буквально бесконечно повторяет одну и ту же последовательность ошибочных весов. Без явного ограничения числа эпох алгоритм в коде просто никогда не завершится.

Пример 4 (три из четырёх точек — уже разделимы). Убери из выборки XOR всего одну точку, $(1,1)\to0$, оставив только $(0,0)\to0$, $(0,1)\to1$, $(1,0)\to1$. Веса $w_1=1$, $w_2=1$, $b=-0{,}5$ разделяют эти три точки безупречно: $(0,0)$: $z=-0{,}5\le0\to0$ верно; $(0,1)$: $z=0{,}5>0\to1$ верно; $(1,0)$: $z=0{,}5>0\to1$ верно. Но эти же самые веса на полной четвёрке XOR дают на точке $(1,1)$: $z=1+1-0{,}5=1{,}5>0\to1$, тогда как истинная метка — 0, то есть ошибку ровно на одной точке из четырёх. Это показывает, что невозможность разделить именно все четыре точки одновременно — тонкое, глобальное свойство всей комбинации меток вместе, а не следствие «какой-то одной особенно сложной» точки: любые три точки XOR по отдельности линейно разделимы, и только их совместное присутствие создаёт противоречие, доказанное в примерах 1 и 2.

Почему это важно

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

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Персептрон с весами $w_1=2$, $w_2=-1$, $b=-1$ получает вход $x=(3,1)$. Найди $z$ и выход $y$.

Задание 2: Тот же персептрон ($w_1=2$, $w_2=-1$, $b=-1$) получает вход $x=(0,5)$. Найди выход.

Задание 3: Разделяющая граница персептрона задана уравнением $3x_1-2x_2+6=0$ (то есть $w_1=3$, $w_2=-2$, $b=6$). К какому классу персептрон отнесёт точку $(1,1)$?

Задание 4: Персептрон текущими весами верно классифицировал пример $(x=(2,-1),\ y=1)$. Как изменятся веса $\Delta w_1, \Delta w_2, \Delta b$ по правилу обучения персептрона?

Задание 5: Персептрон с весами $w_1=0{,}5$, $w_2=0{,}5$, $b=-0{,}5$ получает пример $x=(1,0)$ с истинной меткой $y=1$. Найди предсказание, определи, есть ли ошибка, и вычисли новые веса при $\eta=1$.

Задание 6 (машинное обучение): Верно ли, что персептрон способен со временем со 100%-й точностью выучить абсолютно любую обучающую выборку, если тренировать его достаточно долго? Обоснуй.

Задание 7: Обучающая выборка ИЛИ (OR): $(0,0)\to0$, $(0,1)\to1$, $(1,0)\to1$, $(1,1)\to1$. Проверь, правильно ли классифицирует все четыре точки персептрон с весами $w_1=1$, $w_2=1$, $b=-0{,}5$.

Задание 8: Чем ступенчатая функция активации (функция Хевисайда) персептрона принципиально отличается от sigmoid из урока 326?

Задание 9: Персептрон с весами $w_1=-1$, $w_2=1$, $b=0$. Найди уравнение разделяющей прямой в виде $x_2=\dots$

Задание 10: Обучающая выборка состоит из единственного примера $x=(4,4)$, $y=0$; начальные веса $w_1=w_2=b=0$. Сделает ли персептрон ошибку на первом шаге? Если да, какими станут веса после одного обновления ($\eta=1$)?

Средние задания (11–20)

Задание 11: Датасет: $(1,1)\to1$, $(2,2)\to1$, $(-1,-1)\to0$, $(-2,-1)\to0$; начальные веса $(0,0,0)$, $\eta=1$, примеры предъявляются в указанном порядке. Выполни первую эпоху и укажи финальные веса, а также, была ли хотя бы одна ошибка.

Задание 12: Используя веса $(1,1,1)$ из задания 11, проверь все четыре точки. Сойдётся ли персептрон уже после первой эпохи?

Задание 13: Для датасета И с финальными весами $(2,1,-2)$ (из основной трассировки урока) вычисли ненормированный отступ $|z|$ точки $(1,1)$.

Задание 14: Для тех же весов $(2,1,-2)$ вычисли $z$ для всех четырёх точек датасета И и укажи, какая точка имеет наименьший по модулю отступ.

Задание 15: По теореме Новикова оцени верхнюю границу числа ошибок, если известно, что $\|w^*\|=1$ обеспечивает отступ $\gamma=0{,}1$, а все входные векторы ограничены нормой $R=2$.

Задание 16: Как изменится граница из задания 15, если удастся найти веса, дающие вдвое больший отступ ($\gamma=0{,}2$) при том же $R=2$?

Задание 17: Обучающая выборка содержит одну и ту же точку $x=(1,1)$ дважды — один раз с меткой 1, другой раз с меткой 0. Сойдётся ли персептрон когда-нибудь на такой выборке? Почему?

Задание 18: Покажи, что если убрать точку $(1,1)\to0$ из выборки XOR, оставшиеся три точки $(0,0)\to0$, $(0,1)\to1$, $(1,0)\to1$ становятся линейно разделимы. Приведи подходящие веса.

Задание 19 (машинное обучение): Объясни, почему теорема сходимости персептрона не гарантирует ничего для линейно неразделимых данных, и что происходит с алгоритмом на практике, если не ограничить число эпох.

Задание 20: Персептрон-фильтр спама: $w_1=0{,}6$ (число ссылок в письме), $w_2=-0{,}2$ (длина письма в тысячах символов), $b=-0{,}5$. Классифицируй письмо A: $x_1=2$, $x_2=0{,}5$; и письмо Б: $x_1=0$, $x_2=3$.

Продвинутые задания (21–30)

Задание 21: Выполни трассировку обучения персептрона на датасете ИЛИ: $(0,0)\to0$, $(0,1)\to1$, $(1,0)\to1$, $(1,1)\to1$, начальные веса $(0,0,0)$, $\eta=1$, в указанном порядке. Найди веса после первой эпохи.

Задание 22: Продолжи трассировку задания 21 на вторую эпоху. Сошёлся ли персептрон уже после неё?

Задание 23: Заверши трассировку заданий 21–22 до полной сходимости. Укажи итоговые веса и общее число эпох.

Задание 24 (машинное обучение): Сравни персептрон и логистическую регрессию (урок 313) по трём осям: функция активации, гладкость и способ обучения.

Задание 25: На датасете XOR персептрон стартует с нулевых весов, $\eta=1$, порядок примеров $(0,0),(0,1),(1,0),(1,1)$. После какого по счёту примера веса впервые становятся равны $(-1,0,0)$?

Задание 26: Используя устойчивый цикл длины 4 из раздела «Проблема XOR», укажи, сколько ошибок в среднем совершает персептрон за одну эпоху после того, как он входит в этот цикл.

Задание 27: Приведи веса $w_1, w_2, b$, которые ошибочно классифицируют ровно одну из четырёх точек XOR (то есть верно классифицируют 3 из 4).

Задание 28 (машинное обучение): Объясни, почему критика Минского и Пейперта была математически безупречной, но её интерпретация индустрией — избыточной. Какую роль в этом сыграло появление многослойных сетей и backpropagation в 1986 году?

Задание 29: Персептрон обучается на линейно разделимом датасете с $R=5$ и оптимальным отступом $\gamma=1$. Во сколько раз увеличится гарантированная верхняя граница числа ошибок, если признаки не отмасштабировать и норма векторов вырастет до $R=15$ при том же отступе $\gamma=1$?

Задание 30 (машинное обучение, синтез): Сформулируй одним связным ответом, чем персептрон отличается от полноценной нейронной сети из урока 326 и от логистической регрессии из урока 313, и почему для решения XOR нужно нечто большее, чем один персептрон.

Частые ошибки

• Путают персептрон с логистической регрессией. Персептрон выдаёт жёсткое 0 или 1 без каких-либо промежуточных значений, тогда как логистическая регрессия (урок 313) выдаёт вероятность в интервале $(0,1)$. Ожидать от персептрона «степени уверенности» — ошибка: вся информация о величине $z$, кроме её знака, теряется ступенчатой активацией безвозвратно.

• Считают, что персептрон сойдётся на любых данных при достаточном числе эпох. Теорема Новикова гарантирует сходимость только при линейной разделимости. Перед запуском обучения стоит хотя бы приблизительно оценить (визуально в 2D/3D или логически, как для XOR), разделимы ли классы линейно, — иначе алгоритм без ограничения по эпохам будет работать бесконечно.

• Путают правило обучения персептрона с обновлением на каждом шаге, как в обычном стохастическом градиентном спуске. В отличие от SGD на гладкой функции потерь (урок 286), где обновление происходит почти всегда, персептрон в принципе не меняет веса, если предсказание уже верное, — разность $y-\hat y$ в этом случае строго равна нулю.

• Воспринимают верхнюю границу теоремы сходимости $(R/\gamma)^2$ как точную оценку скорости обучения. Это гарантированный верхний предел числа ошибок, а не прогноз реального их количества — как показано в разделе про теорему, реальное число обновлений может оказаться в несколько раз меньше границы.

• Считают критику Минского и Пейперта опровержением нейросетей в целом. Доказательство 1969 года касалось исключительно однослойного персептрона без скрытых нейронов; оно ничего не говорит о принципиальной невозможности обучаемых многослойных архитектур, что было явно продемонстрировано появлением backpropagation в 1986 году (урок 328).

• Забывают о строгом неравенстве $z>0$ в определении модели. Точка ровно на разделяющей границе ($z=0$) по определению относится к классу 0, а не к какому-то «промежуточному» состоянию. Несогласованность этого условия в собственной реализации (использование >= вместо > или наоборот) — частый источник трудно отлавливаемых пограничных багов.

• Не масштабируют признаки перед обучением персептрона. Как показано в задании 29, при неотмасштабированных признаках с большой нормой $R$ гарантированная верхняя граница числа необходимых обновлений растёт квадратично — а вместе с ней часто растёт и реальное время сходимости на практике.

Главное запомнить

• Персептрон — это искусственный нейрон (урок 326) со ступенчатой функцией активации: $y=1$, если $z=w\cdot x+b>0$, иначе $y=0$ — первая обучаемая модель нейрона, построенная Фрэнком Розенблаттом в 1958 году.

• Геометрически персептрон строит ровно одну разделяющую прямую (гиперплоскость) в пространстве признаков и не способен построить никакую более сложную границу решения.

• Правило обучения персептрона обновляет веса только при ошибке: $w_i \leftarrow w_i+\eta(y-\hat y)x_i$; при верном предсказании $y-\hat y=0$, и веса остаются неизменными.

• Теорема сходимости персептрона (Новиков, 1962) гарантирует конечную сходимость за не более $(R/\gamma)^2$ ошибок, но только при условии линейной разделимости данных с отступом $\gamma>0$.

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

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

• Критика Минского и Пейперта 1969 года была математически безупречной, но её интерпретация как приговора всем нейросетям способствовала почти десятилетнему сокращению финансирования этой области исследований — периоду, известному как «зима искусственного интеллекта».

• Проблема XOR решается не отказом от идеи обучаемого нейрона, а добавлением хотя бы одного скрытого слоя — именно это и продемонстрировал алгоритм обратного распространения ошибки в 1986 году, а разберём мы это уже в уроке 328.

• Правило обучения персептрона исторически предшествует общей теории градиентного спуска и формально не является им: ступенчатая активация не дифференцируема, поэтому логистическая регрессия (урок 313) заменяет её гладкой sigmoid-функцией, чтобы обучаться полноценным градиентным спуском.

• Масштабирование признаков напрямую влияет на скорость практической сходимости персептрона: увеличение нормы входных векторов $R$ квадратично увеличивает гарантированную верхнюю границу числа необходимых обновлений весов.

Связь с темами курса

Этот урок напрямую опирается на общую формулу искусственного нейрона из урока 326: персептрон — её частный случай с самой простой из возможных активаций, ступенчатой функцией вместо гладких sigmoid, ReLU или tanh. Одновременно этот урок готовит почву для логистической регрессии (урок 313), которую теперь можно осмыслить иначе: это тот же самый линейный классификатор $w\cdot x+b$, но с гладкой активацией, позволяющей применить настоящий градиентный спуск (урок 285) вместо эвристического правила Розенблатта, не работающего с недифференцируемой ступенькой.

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

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

Интересные факты

• Mark I Perceptron 1958 года был не абстрактной формулой, а физическим устройством размером с комнату: сетчатка из 400 фотоэлементов подключалась к блоку электромеханических потенциометров, роль весов в котором играло электрическое сопротивление, а обучение происходило буквально механически — маленькие электромоторы физически проворачивали ручки потенциометров при каждой ошибке.

• Пресса конца 1950-х годов освещала персептрон Розенблатта с энтузиазмом, который сегодня выглядит откровенным перебором: широко цитировались заявления о будущей машине, способной ходить, говорить, видеть и даже осознавать собственное существование, — редкий по масштабу пример завышенных ожиданий вокруг ранней технологии искусственного интеллекта.

• Зима искусственного интеллекта 1970-х годов не сводилась только к книге Минского и Пейперта: в 1973 году в Великобритании вышел не менее влиятельный доклад Лайтхилла (Lighthill Report), критически оценивший перспективы исследований ИИ в целом и приведший к резкому сокращению государственного финансирования этой области в британских университетах — два независимых удара по репутации нейросетевого подхода с разницей всего в четыре года.

• В более поздних изданиях книги «Perceptrons» Минский и Пейперт признавали, что многослойные персептроны в принципе способны преодолеть ограничение XOR, но выражали скепсис относительно того, что для таких сетей когда-либо найдётся эффективный алгоритм обучения. Этот конкретный скептический прогноз оказался неверным: алгоритм backpropagation, найденный в 1986 году, оказался именно таким эффективным способом обучения многослойных сетей, которого, по мнению авторов, не существовало.

• Сам Фрэнк Розенблатт не дожил до реабилитации своей идеи: он погиб в результате несчастного случая на воде в 1971 году, за полтора десятилетия до того, как многослойные сети на основе его исходной модели искусственного нейрона вернули нейросетевой подход в центр внимания науки.

Лайфхаки

• Перед тем как обучать одиночный персептрон, попробуй хотя бы приблизительно оценить линейную разделимость данных — визуально на графике в двух-трёх измерениях или логически, как для XOR. Если разделимость под вопросом, разумнее сразу перейти к логистической регрессии, SVM (урок 319) или небольшой многослойной сети (урок 328).

• В собственной реализации всегда явно фиксируй, какое неравенство используется на границе — строгое z > 0 или нестрогое z >= 0, — и делай это единообразно во всём коде. Несогласованность именно на границе (как в задании 14, где точка легла ровно на $z=0$) — частый источник трудноуловимых расхождений между ожидаемым и фактическим поведением модели.

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

• Масштабируй признаки перед обучением персептрона так же, как это делается для градиентного спуска (урок 285). Как показано в задании 29, большая норма входных векторов $R$ квадратично увеличивает верхнюю границу числа необходимых обновлений — а на практике часто пропорционально замедляет и реальную сходимость.

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

• Минимальная рабочая реализация персептрона умещается в несколько строк и полезна как учебный ориентир для проверки собственного понимания правила обучения:

import numpy as np

def train_perceptron(X, y, lr=1.0, max_epochs=100):
    w = np.zeros(X.shape[1])
    b = 0.0
    for epoch in range(max_epochs):
        errors = 0
        for xi, yi in zip(X, y):
            z = np.dot(w, xi) + b
            y_pred = 1 if z > 0 else 0
            if y_pred != yi:
                w += lr * (yi - y_pred) * xi
                b += lr * (yi - y_pred)
                errors += 1
        if errors == 0:
            break
    return w, b, epoch + 1

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