Перцептрон учится границе

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

От ручных весов к самонастройке

В уроке о логическом нейроне веса подбирал человек: чтобы получить И или ИЛИ, мы сами придумывали числа $w_1,w_2,b$. Это годится для четырёх строк таблицы истинности, но не для тысячи фотографий или сотни цветков — там нужную границу руками не нащупать. В уроке о кибернетике мелькнуло лекарство: система, которая правит себя по ошибке. Сегодня мы соберём его до конца.

В 1958 году американский психолог Фрэнк Розенблатт объединил пороговый элемент с правилом обучения по ошибке и назвал результат перцептроном. Он не только описал его на бумаге, но и построил в железе: Mark I Perceptron — шкаф с $400$ фотоэлементами-«глазами» и мотором, крутившим потенциометры-веса. Машина училась отличать простые фигуры, и газеты писали об «электронном мозге, который сам учится видеть». Восторг был преждевременным, но зерно — настоящим: перцептрон стал первым устройством, находящим разделяющую границу без подсказки, где её проводить.

Правило, которое двигает границу

Как и логический нейрон, перцептрон берёт вход $x=(x_1,\ldots,x_d)$, считает взвешенную сумму и выдаёт знак. Условимся, что классы помечены $+1$ и $-1$, а порог спрятан в вес при постоянном входе (приём $x_0\equiv 1$ из урока 13), так что решение — это просто знак скалярного произведения:

$$\hat y = \operatorname{sign}(w\cdot x).$$

Теперь главное — как учить. Возьмём примеры по одному. Если на примере $x$ с верной меткой $y$ перцептрон не ошибся, вес не трогаем. Если ошибся — сдвигаем вес в сторону правильного ответа:

$$w \leftarrow w + \eta\,(y - \hat y)\,x .$$

Множитель $y-\hat y$ равен нулю при верном ответе (учить нечего) и $\pm 2$ при ошибке — знак говорит, в какую сторону чинить. По сути правило простое: ошиблись на точке класса $+1$ — прибавили к весу эту точку; ошиблись на точке класса $-1$ — вычли. Каждое исправление чуть-чуть поворачивает разделяющую прямую так, чтобы провинившаяся точка оказалась ближе к своей стороне.

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

Геометрия одного исправления

Почему прибавление точки к вектору весов поворачивает границу в нужную сторону? Вспомним из урока 13: вектор весов $w$ перпендикулярен разделяющей прямой и смотрит в сторону класса $+1$. Пусть точка $x$ класса $+1$ ошибочно попала на отрицательную сторону — значит, $w\cdot x<0$, вектор $w$ отвернут от неё. Правило добавляет $x$ к $w$; новый вектор $w+\eta\cdot 2x$ качнулся в сторону $x$, и скалярное произведение подросло:

$$(w+2\eta x)\cdot x = w\cdot x + 2\eta\,\|x\|^2 > w\cdot x .$$

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

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

Теорема сходимости: почему это вообще заканчивается

Правило понятно, но откуда уверенность, что довороты когда-нибудь прекратятся, а не будут дёргать границу вечно? Ответ дал в 1962 году Альберт Новиков, и это одна из самых изящных теорем раннего машинного обучения. Она говорит: если два класса вообще можно разделить прямой — если существует хоть какая-то идеальная граница с зазором $\gamma$ (наименьшим расстоянием от точек до неё) — то перцептрон найдёт разделяющую прямую, сделав не больше

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

ошибок, где $R$ — радиус наименьшего шара, вмещающего все точки. Число ошибок конечно и не зависит ни от количества точек, ни от порядка их предъявления — только от того, насколько широк зазор между классами. Широкий зазор (большое $\gamma$) — быстрая сходимость; узкий — медленная, но всё равно конечная. Перцептрон не может ошибаться вечно, если правильная граница вообще существует.

Набросок доказательства стоит увидеть — он держится на двух простых неравенствах, зажимающих число ошибок с двух сторон. Пусть $w^*$ — единичный вектор идеальной границы, так что $y\,(w^*\!\cdot x)\ge \gamma$ для всех точек. Следим за нашим вектором $w$ после $k$ ошибок (на верных примерах он не меняется). При каждой ошибке проекция $w$ на идеальное направление растёт не меньше чем на $\gamma$:

$$w^*\!\cdot w \;\ge\; k\,\gamma \qquad\text{(проекция копится линейно).}$$

А длина самого $w$ растёт медленно — не быстрее чем как $\sqrt{k}$, потому что на ошибке $\|w\|^2$ прибавляет не больше $R^2$:

$$\|w\|^2 \;\le\; k\,R^2 \qquad\text{(длина копится как корень).}$$

Но проекция вектора не может превышать его длины: $w^*\!\cdot w\le \|w\|$. Подставив оба неравенства, получаем $k\gamma\le\sqrt{k}\,R$, откуда $\sqrt k\le R/\gamma$ и $k\le (R/\gamma)^2$. Линейно растущая проекция упирается в корнево растущую длину — и это лобовое столкновение и ограничивает число ошибок сверху. Красота в том, что доказательство ничего не знает про размерность, число точек и порядок: всё решают геометрические $R$ и $\gamma$.

На реальных данных: перцептрон и ирисы Фишера

Теорию проверим на самом знаменитом датасете в истории статистики. В 1936 году Рональд Фишер опубликовал измерения $150$ ирисов трёх видов — по $50$ каждого; у каждого цветка длина и ширина лепестка и чашелистика. Копия лежит в репозитории: scripts/data/iris.data. Возьмём два признака — длину и ширину лепестка — и научим перцептрон отличать вид setosa от вида versicolor.

Эти два вида разделяются идеально: у всех setosa лепесток короче $2$ см, у всех versicolor длиннее $3$ см, между ними пустая полоса шириной больше сантиметра — широкий зазор. Запустим правило: перцептрон делает $11$ ошибок на первом проходе по данным, доворачивая границу, а на втором проходе не ошибается ни разу и останавливается. Теорема Новикова не соврала: разделимые классы с широким зазором взяты за две эпохи.

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

Когда прямой не существует

А если классы прямой не разделяются? Возьмём из тех же ирисов пару потруднее — versicolor против virginica. Их лепестки перекрываются: самые крупные versicolor больше самых мелких virginica, пустой полосы нет, ни одна прямая не разделит их без ошибок. Запустим перцептрон — и он не остановится никогда. Число ошибок за эпоху скачет — $43$, $36$, $30$, $24$, снова $41$ — но к нулю не приходит, граница дёргается из стороны в сторону, вечно гоняясь за точками, которых не поймать.

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

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

Взлёт, падение и что осталось

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

Что из перцептрона осталось навсегда? Три вещи, и все три — с нами до последнего урока курса. Форма решения $\operatorname{sign}(w\cdot x)$ живёт в каждом искусственном нейроне. Идея учить по ошибке, шажок за шажком, выросла в градиентный спуск, на котором стоит всё глубокое обучение. А зазор из теоремы Новикова стал фундаментом теории обобщения. Машину-шкаф забыли; её математику — нет.

Скорость обучения и порядок примеров

Два практических вопроса, которые зададут и о перцептроне, и о всех его потомках. Первый — скорость $\eta$. Для перцептрона она на удивление безобидна: домножение $\eta$ на положительную константу лишь пропорционально масштабирует весь вектор весов, а знак $\operatorname{ sign}(w\cdot x)$ от масштаба не зависит — граница та же. Поэтому для чистого перцептрона $\eta$ можно взять любой положительный, хоть единицу; настоящей головной болью скорость обучения станет позже, для гладких моделей с градиентным спуском.

Второй вопрос — порядок предъявления примеров. Он влияет: перебирая точки в разном порядке, перцептрон приходит к разным разделяющим прямым (любая годится, лишь бы разделяла) и за разное число шагов. Теорема Новикова гарантирует конечность при любом порядке, но не единственность ответа. Эта чувствительность к порядку — черта онлайн-обучения по одному примеру; способы её усмирить (перемешивание, усреднение, пакеты) мы разберём, когда дойдём до стохастического спуска.

Лаборатория: научите границу вживую

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

Сборка: первая машина, нашедшая границу сама

Перцептрон соединил три идеи курса в работающее обучение: пороговый нейрон из урока 13 дал форму решения, коррекция по ошибке из урока 14 — закон изменения весов, а метка учителя превратила изменение в осмысленное движение к цели. Каждая ошибочная точка доворачивает границу к себе; теорема Новикова обещает, что при существовании разделяющей прямой доворотов будет конечное число, тем меньше, чем шире зазор между классами. На ирисах Фишера мы увидели обе стороны обещания: разделимые setosa и versicolor взяты за две эпохи, а неразделимые versicolor и virginica заставляют алгоритм метаться вечно. Предел всё тот же — одна прямая; и всё тот же выход намечен — слои, преобразующие пространство, пока граница не станет прямой. Но чтобы обучать слои, правила «поправь по ошибке» уже мало: понадобится заменить жёсткий порог гладкой функцией и научиться считать, куда шагнуть, не по одной точке, а по всей ошибке сразу. С этого начинается следующий блок — про то, как обучение становится оптимизацией.

Задачи