Перцептрон с нуля: что вычисляет нейрон

Перцептрон берет измерения, умножает каждое на число, которым сам управляет, складывает результаты, добавляет еще одно число и смотрит на знак.

Запишем измерения одной детали как вектор $\mathbf{x} = (x_1, x_2)$ — ширина и вес. Перцептрон хранит вектор весов $\mathbf{w} = (w_1, w_2)$ и смещение $b$. Его оценка равна

а ответ — знак этой оценки: принять, если $s(\mathbf{x}) \geq 0$, иначе отклонить.

Это вся модель. Все, что перцептрон когда-либо узнает о фабрике, живет в трех числах.

На геометрии стоит задержаться, потому что эта картинка будет работать все следующие двадцать девять глав, даже когда уравнения перестанут помещаться в одну строку. Множество точек, где $s(\mathbf{x}) = 0$ — где перцептрон ровно не определился, — это прямая на плоскости. По одну сторону оценка положительна, и все принимается; по другую она отрицательна, и все отклоняется. Для перцептрона обучение означает двигать эту прямую.

Из алгебры напрямую следуют два факта об этой прямой, и оба пригодятся позже:

• $\mathbf{w}$ перпендикулярен ей. Вектор весов не лежит вдоль границы, он указывает поперек нее, в сторону принятия.
• $b$ сдвигает ее, не поворачивая. Без смещения прямая была бы вынуждена проходить через начало координат, что для фабрики, измеряющей миллиметры и граммы, было бы абсурдным ограничением: это означало бы, что деталь нулевой ширины и нулевого веса находится ровно на границе.

Сначала перцептрон ничего не знает: $\mathbf{w} = (0, 0)$ и $b = 0$. Каждая оценка равна нулю, поэтому он принимает все.

Теперь показывайте ему примеры по одному. Принятые детали помечайте $y = +1$, отклоненные — $y = -1$. Для каждого примера задавайте один вопрос: правильный ли получился знак? Компактно этот вопрос записывается как проверка, положительно ли $y \cdot s(\mathbf{x})$: если метка и оценка согласны по знаку, их произведение положительно, а если не согласны — отрицательно.

Если ответ да, ничего не меняйте. Если нет — подтолкните:

Это весь алгоритм, и важно понять почему именно такой толчок правильный, а не просто выучить его. Допустим, деталь должна была быть принята ($y = +1$), но оценка оказалась отрицательной. Добавление $\mathbf{x}$ к $\mathbf{w}$ меняет оценку на той же самой детали на

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

Обратите внимание, чего здесь нет. Здесь нигде нет производной. Это не недосмотр, а первая по-настоящему важная идея курса.

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

Это настоящее решение, но еще и тупик. В главе 2 нам понадобится loss, который откуда-то выводится, а не просто выбирается; в главе 4 — модель, сообщающая, насколько она уверена; в главе 5 — что-то большее, чем один слой. И ни к чему из этого нельзя прийти от правила, которое знает только «неправильно». Вернуть пригодный наклон — вот что вынуждает следующие две главы. Но перцептрон умеет делать то, чего не умеет ни один его преемник: учиться вообще без анализа.

Чистый Python, без NumPy. Списки и цикл. NumPy появится в следующей главе, где арифметика перестанет помещаться в цикл, который вам захочется читать; вводить его сейчас означало бы спрятать арифметику за библиотекой ровно в тот момент, когда вы хотите ее видеть.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Четыре выделенные строки — это алгоритм. Все остальное — служебная обвязка.

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

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

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

Запустим:

None [-142.1, -13.0] 54.0

Двести эпох, 454 исправления, а сходимости нет. Веса большие и с неправильным знаком. Что-то не так — только вот все так, и причина этого — самое полезное в этой главе.

У перцептрона есть гарантия, доказанная Новиковым в 1962 году.¹ Если данные вообще можно разделить прямой, алгоритм сделает не больше

исправлений, прежде чем перестанет делать их вовсе, где $R$ — радиус данных, длина самого длинного вектора-примера, а $\gamma$ — margin: расстояние от разделяющей гиперплоскости до ближайшей точки в расширенном пространстве, где смещение является третьей координатой. Именно поэтому центрирование данных меняет его, хотя расстояние в миллиметрах не меняется.

Гарантия безусловна, и в ней не упоминаются эпохи, скорости обучения или удача. В ней также не упоминается время, и именно в этом дело.

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

Теорема ни разу не была нарушена. Если запускать исходную версию достаточно долго, она действительно сходится — на эпохе 11 976, после 29 870 исправлений, — с большим запасом внутри своей границы 2 633 550. И этот разрыв сам по себе важен: теорема ограничивает худший случай, а не типичный. Просто ей понадобилось в шестьдесят раз больше эпох, чем кто-либо стал бы ждать.

Вторая строка — те же восемь деталей, те же двадцать строк кода, к которым добавлены три строки для вычитания средней ширины и среднего веса из каждого измерения. И все. Это единственное изменение. Оно сдвигает облако точек так, что оно охватывает начало координат, а не плавает где-то у (22, 57), и эффект на границу оказывается в пятнадцать тысяч раз, потому что улучшаются оба члена сразу: $R$ падает с 74 до 13, поскольку точки больше не измеряются от далекого начала координат, а $\gamma$ растет с 0,045 до 0,989, потому что margin измеряется относительно вектора весов, которому больше не нужно нести огромное смещение, чтобы добраться до данных.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Сошлось за две эпохи, исправив себя ровно один раз.

Здесь есть настоящий урок, и это не «не забывайте нормализовать входы», хотя забывать и правда не стоит. Урок в том, что гарантия того, что алгоритм когда-нибудь закончит, ничего не говорит о том, будете ли вы рядом, когда это случится, а зазор между этими двумя вещами обычно геометрический. Это первое появление паттерна, который вы снова встретите в главе 6 с инициализацией, в главе 10 с расписаниями скорости обучения и в главе 13 с квантизацией: математика говорит, что вещь возможна, а инженерия решает, практична ли она. Курс, который учит вас только теореме, вручает вам модель, которая обучается три дня, и обвиняет вас.

Теперь неудача, которая завершила первую эпоху нейросетей, и она помещается в четыре строки.

Забудем фабрику. Возьмем два входа, каждый из которых равен 0 или 1, и попросим ответ быть $+1$, когда ровно один из них равен 1:

Это XOR — исключающее «или». Прежде чем читать дальше, нарисуйте четыре точки на бумаге: три угла единичного квадрата и четвертый. Отметьте два диагональных угла $(0,1)$ и $(1,0)$ как «принять», а $(0,0)$ и $(1,1)$ как «отклонить». Теперь проведите одну прямую так, чтобы две принятые точки оказались по одну сторону, а две отклоненные — по другую.

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

Сложим два средних неравенства: $w_1 + w_2 + 2b \geq 0$, значит $w_1 + w_2 \geq -2b$. Последнее говорит $w_1 + w_2 < -b$. Вместе: $-2b \leq w_1 + w_2 < -b$, что требует $-2b < -b$, а это требует $b > 0$. А первое неравенство говорит $b < 0$. Такого $b$ нет, значит нет и таких весов. Ни один перцептрон, с какими угодно числами, не классифицирует XOR.

Все равно запустите его, потому что увидеть, как алгоритм терпит неудачу, ценнее, чем услышать, что так и будет:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

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

В 1969 году Марвин Минский и Сеймур Пейперт опубликовали Perceptrons — математическое исследование объемом в книгу о том, что именно эта модель может и не может представлять.² XOR — самый цитируемый результат, и обычно эту цитату используют как обвинение: будто книга из соперничества или злобы убила исследования нейросетей на пятнадцать лет.

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

Популярная история также неверна исторически. Минский и Пейперт прямо обсуждают многослойные перцептроны и говорят, что вопрос об их возможностях открыт: они подозревали, что расширение теории окажется «стерильным», но это прогноз, а не доказательство, и он был неверен. В 1969 году не хватало не идеи складывать слои; не хватало способа обучать такой стек. Правило перцептрона не может этого сделать: ему нужно знать, насколько ошибается каждая единица, а у единицы, спрятанной в середине, нет собственной метки для сравнения. Этот пробел оставался открытым, пока backpropagation не была популяризирована в 1986 году,³ и закрытием этого пробела занимается глава 5.

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

Перцептрону шестьдесят восемь лет, и вы только что написали один. Стоит точно понимать, какие его части все еще есть в машине, с которой вы закончите этот курс, потому что ответ такой: больше, чем вы думаете.

Перцептрон застрял сразу на двух вещах, и оказывается, что это одна и та же вещь.

Он не может представить XOR, потому что одной прямой недостаточно. Исправить это значит сложить слои: первый слой изгибает пространство, второй проводит прямую в изогнутом пространстве. Это глава 5.

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

Значит, перед стеком должна появиться loss function с пригодной производной. И не такая, которую выбрали потому, что ее удобно дифференцировать, а такая, которая откуда-то берется, говорит что-то истинное о данных, и чей gradient вытекает из этого смысла, а не подгоняется задним числом, чтобы выглядеть аккуратно.

Это глава 2, и она начинается с вопроса, на который перцептрону никогда не приходилось отвечать: не «хороша ли эта деталь?», а «насколько вероятны эти показания, если это правда?»

Вместе с этой главой также стоит прочитать исходную статью Розенблатта The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), которая читается легче, чем можно подумать по ее репутации; McCulloch and Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), статью, где нейрон впервые был смоделирован как порог над взвешенной суммой; раздел о перцептроне в A Course in Machine Learning Хэла Доме III, где то же обновление выводится с другим акцентом; а также главы 2 и 3 книги Deisenroth, Faisal and Ong Mathematics for Machine Learning о линейной алгебре, если блок выше дал вам меньше, чем хотелось.