Машина учится

«Турнир ботов» из прошлой главы закончился неудобным признанием. Перебор и альфа-бета отсечение — механика, а чувство позиции, оценочную функцию, в Deep Blue годами настраивали люди. Для го её не сумел записать никто. Что делать, если человек не умеет написать правило? Вот задача попроще го. Перед вами рукописные цифры: каждую вывел от руки живой человек, заполняя бланк.

Каждая цифра — картинка 16 на 16 пикселей, то есть 256 чисел от 0 (бумага) до 1 (чернила). X — таблица numpy из 3823 таких строк, y — правильные ответы, какая цифра в каждой строке. Цифры написаны тремя десятками людей; этот открытый набор собрали в стамбульском университете Богазичи Этем Алпайдын и Дженк Кайнак, и с 1998 года он лежит в архиве машинного обучения UCI под лицензией CC BY 4.0.

Задание: напишите функцию, которая отличает четвёрку от девятки. Хотя бы в уме. «У девятки сверху замкнутая петля» — но у половины четвёрок на картинке верх тоже сомкнулся. «У четвёрки есть поперечная черта» — а у этой девятки хвост загнут, и он похож на черту. Каждое правило ломается на чьём-то почерке, а на каждую заплатку находятся новые исключения. Вы различаете эти цифры мгновенно и не можете объяснить как. Это та же стена, что у оценочной функции в го: знание есть, рецепта нет.

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

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

Тренировка 1. Прямая

Начнём с подопечного, у которого ручек всего две. В главе 8 мы проверяли закон Ципфа: на графике с логарифмическими шкалами частоты слов «Войны и мира» легли почти на прямую, и мы провели её на глаз — $45\,000 / r$. Пусть теперь прямую найдёт машина. Отметим точки: $x$ — десятичный логарифм места слова, $y$ — логарифм его частоты. Модель — прямая $y = w x + b$: вес $w$ задаёт наклон, $b$ — высоту.

Мера промаха

Чтобы тренировать, нужно уметь сказать, насколько плоха прямая. Для каждой точки промах — это $w x_i + b - y_i$: насколько прямая выше или ниже точки. Промахи бывают разного знака, поэтому их возводят в квадрат и усредняют:

$$L(w, b) = \frac1n \sum_{i=1}^{n} \bigl(w x_i + b - y_i\bigr)^2.$$

Такое число называют функцией потерь: чем она меньше, тем лучше модель. Квадрат выбран не случайно. Он всегда неотрицателен, большой промах он наказывает сильнее, чем несколько маленьких, и он гладкий — у него есть производная, а она нам сейчас понадобится. Сумму квадратов промахов минимизировали ещё Лежандр и Гаусс в начале XIX века. Для прямой есть и готовая формула наилучших $w$ и $b$ — её выводят в «Царице наук», в главе о лучшей прямой. Но у сети, которой мы закончим, таких формул нет, и нужен способ, который обходится без них.

Спуск

Представьте функцию потерь как местность: по двум осям — веса $w$ и $b$, высота — потери. Мы стоим в какой-то точке и хотим вниз. Всей карты не видно, но можно пощупать склон под ногами. Производная $\partial L/\partial w$ говорит, как быстро растут потери, если чуть увеличить $w$, а $\partial L/\partial b$ — то же про $b$. Пара этих производных — градиент, стрелка в сторону самого крутого подъёма. Значит, шагать надо против неё:

$$w \leftarrow w - \eta\,\frac{\partial L}{\partial w}, \qquad b \leftarrow b - \eta\,\frac{\partial L}{\partial b}.$$

Это градиентный спуск, путник в тумане из «Царицы наук». Число $\eta$ (греческая «эта») — шаг обучения. Производные нашей функции потерь считаются по школьным правилам: производная квадрата — удвоенное выражение, умноженное на производную того, что внутри:

$$\frac{\partial L}{\partial w} = \frac2n \sum_{i} \bigl(w x_i + b - y_i\bigr)\,x_i, \qquad \frac{\partial L}{\partial b} = \frac2n \sum_{i} \bigl(w x_i + b - y_i\bigr).$$

Возьмём 38 точек графика Ципфа — места 1, 2, 3, 4, 5, 6, 8, 10, 13 и так далее до 10 000, примерно поровну на каждый порядок, — и начнём с горизонтальной прямой $w = b = 0$.

Первый шаг неловкий: прямая задирается вверх, потому что все точки выше нуля и первым делом спуск тянет её к ним. Через сто шагов она почти на месте, через тысячу не меняется в третьем знаке: $w \approx -0{,}94$, $b \approx 4{,}48$, то есть частота слова на месте $r$ примерно $30\,000 / r^{0{,}94}$. Наша прикидка из главы 8 была неплохой, но потери у прямой машины в два с половиной раза меньше. Никто не подсказывал ей ни наклон, ни высоту — только точки и мера промаха.

Теперь поставьте rate = 0.16 и запустите снова. Через сто шагов веса — десятки тысяч, через тысячу — числа с полусотней цифр. Шаг оказался длиннее ямы: спуск перепрыгивает дно, попадает на противоположный склон выше, чем был, и с каждым прыжком улетает всё дальше. Где проходит граница, в «Царице наук» сказано точно: для квадратичной ямы шаг должен быть меньше $2/\lambda$, где $\lambda$ — кривизна ямы в самом крутом направлении. У нашей ямы $\lambda \approx 13{,}3$, граница около $0{,}15$. Вот как эта местность выглядит сверху.

Карта объясняет, почему даже хороший шаг ползёт: яма вытянута, как овраг. Вес $w$ умножается на $x$ от 0 до 4, а $b$ — на единицу, поэтому сдвиг $w$ меняет прямую сильнее, чем такой же сдвиг $b$, и склоны поперёк оврага гораздо круче, чем вдоль. Шаг, безопасный для крутых склонов, мал для пологого дна. Лекарство — вычесть из $x$ его среднее. Тогда наклон и высота перестают мешать друг другу, яма становится почти круглой, и спуск доходит до дна за два десятка шагов. Из этого выросло правило, которому следуют все, кто обучает модели: прежде чем учить, приведите входы к сравнимому масштабу. Оно пригодится вам в первой задаче главы.

Тренировка 2. Перцептрон

Прямая предсказывала число. Теперь подопечный должен выбирать: четвёрка или девятка, да или нет. Этот подопечный старше всех в лагере.

Ходить и говорить перцептрон так и не начал. Но то, что он умел, умеет и сегодня. Перцептрон — взвешенная сумма входов плюс сдвиг: $s = w_1 x_1 + w_2 x_2 + \ldots + w_n x_n + b$. Если $s > 0$, ответ «да» (+1), иначе «нет» (−1). На плоскости с двумя входами это прямая $w_1 x_1 + w_2 x_2 + b = 0$: по одну сторону «да», по другую «нет». У цифры 16 на 16 входов 256, и вместо прямой получается плоская граница в 256-мерном пространстве, но смысл тот же.

Правило обучения Розенблатта умещается в строку. Берём пример $x$ с правильным ответом $t = \pm 1$. Если перцептрон ответил верно, ничего не делаем. Если ошибся — прибавляем пример к весам со знаком правильного ответа: $w \leftarrow w + t\,x$, $b \leftarrow b + t$. После такой поправки сумма на этом же примере меняется на $t\,(|x|^2 + 1)$, то есть сдвигается в сторону правильного ответа. Перцептрон учится только на своих ошибках, и на плоскости видно, как каждая ошибка поворачивает прямую.

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

Запись w @ x — сумма попарных произведений весов и пикселей, наша $s$ без сдвига; numpy считает её одной командой. В первую эпоху перцептрон ошибается 38 раз, во вторую — 13, а с пятой ошибок единицы. До нуля он к десятой эпохе не доходит: несколько цифр в выборке написаны так, что простая граница их не отделяет. Но на экзамене, на почерке тринадцати незнакомых ему людей, он прав больше чем в 99 случаях из 100. Правило, которое мы не смогли сформулировать, записано в 257 числах.

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

Если границу провести можно, перцептрон её найдёт. Это теорема, и у неё одно из самых коротких доказательств в курсе.

Теорему доказали в начале 1960-х; самое известное доказательство, вот это, опубликовал Альберт Новиков в 1962 году. О том, что будет, если разделяющей границы не существует, теорема молчит.

Вентиль, которому он не научится

В главе 29 вы собирали из вентилей «исключающее или»: единица, когда входы различны. Дадим перцептрону четыре строки таблицы истинности XOR.

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

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

Тренировка 3. Сеть

Подсказка, как обойти стену, лежит в той же главе 29. XOR раскладывается в дизъюнктивную нормальную форму: $a \oplus c = (\lnot a \land c) \lor (a \land \lnot c)$. Каждая из трёх деталей — «не $a$ и $c$», «$a$ и не $c$», «или» — делится прямой, а значит, её может посчитать перцептрон. Поставим два перцептрона на входы, а третий — на их выходы. Получится нейронная сеть со скрытым слоем: «скрытым», потому что ответов для его нейронов в примерах нет — что им считать, сеть должна придумать сама.

Вот только правило Розенблатта тут не работает. Оно знает, как поправить нейрон, который сам ошибся. А в чём ошибся скрытый нейрон, если правильный ответ известен только для выхода? Нужен градиентный спуск, как на первой тренировке: функция потерь от всех девяти весов сети, и шаг против градиента. Мешает ступенька. Перцептрон отвечает +1 или −1, и если чуть повернуть вес, ответ не меняется вовсе — производная равна нулю почти везде, склона нет. Поэтому ступеньку сглаживают: вместо знака суммы нейрон выдаёт $\sigma(s) = 1/(1 + e^{-s})$ — плавный переход от 0 к 1. Такую функцию называют функцией активации. Теперь потери — гладкая функция всех весов.

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

Производная сигмоиды записывается через неё саму: $\sigma'(s) = \sigma(s)\,(1 - \sigma(s))$, отсюда множители y * (1 - y) и h * (1 - h). Через три тысячи шагов выход близок к 0, 1, 1, 0. Интереснее средние столбцы. Первый скрытый нейрон загорается только на входе (0, 1): он стал вентилем «не $a$ и $c$». Второй — только на (1, 0): «$a$ и не $c$». Выход включается, когда горит любой из них: это «или». Сеть сама собрала дизъюнктивную нормальную форму из главы 29. Никто не говорил ей, какие нужны вентили, — она нашла их спуском.

Поменяйте default_rng(1) на default_rng(5). Потери застрянут около 0,17, а выход на трёх входах из четырёх — около трети. Спуск пришёл в ямку, которая не самая глубокая, и выбраться из неё не может: склон под ногами во все стороны идёт вверх. У гладкой поверхности потерь сети таких ям бывает много. На практике спасают случайный старт, повторный запуск и лишние нейроны: в сети с запасом нейронов плохие ямы, как ни странно, попадаются реже. Это пригодится в задаче про XOR в конце главы.

Тренировка 4. Десять цифр

Теперь всерьёз: все десять цифр сразу. На вход — 256 пикселей, в скрытом слое — 64 нейрона, на выходе — десять, по одному на цифру. Чтобы из десяти выходов получить ответ, их суммы $z_0, \ldots, z_9$ превращают в вероятности функцией softmax:

$$p_k = \frac{e^{z_k}}{e^{z_0} + e^{z_1} + \ldots + e^{z_9}}.$$

Все $p_k$ положительны, в сумме дают единицу, и у большей суммы больше вероятность. Ответ сети — цифра с наибольшей вероятностью. Потери на примере — $-\ln p$ верной цифры: если сеть дала правильному ответу вероятность 0,9, потеря 0,1, если 0,01 — потеря 4,6. Это мера удивления: насколько сеть удивилась правильному ответу. Её любят не только за смысл. Производная таких потерь по суммам выходных нейронов на редкость проста: $p_k - 1$ для верной цифры и $p_k$ для остальных. «Сколько дала минус сколько надо» — с этого и начинается обратный проход.

Ещё две перемены. В скрытом слое вместо сигмоиды стоит функция $\max(0, s)$, по-английски ReLU: отрицательное — в ноль, положительное — как есть. Её производная — 0 или 1, считать её дёшево, и сигнал не затухает, проходя через много слоёв; сегодня это самая обычная функция активации. И градиент считают по пачке из 32 случайных примеров, а не по всем 3823 сразу: оценка выходит шумной, зато дешёвой. Такой спуск называют стохастическим; за эпоху он делает 120 шагов.

Строка dz[np.arange(len(batch)), labels] -= 1 вычитает единицу у каждого примера пачки в столбце его верной цифры, и получается «сколько дала минус сколько надо». Дальше обратный проход: градиент по W2 — произведение выходов скрытого слоя на ошибки выхода, ошибка скрытого слоя — ошибки выхода, пропущенные назад через W2 и через производную ReLU (h > 0).

За доли секунды сеть из 17 098 весов доходит до 98–99 % на обучающих цифрах и примерно до 95 % на экзамене. Её ошибки — под ячейкой. Часть из них простительна: некоторые цифры и человек прочтёт не с первого раза. Но половина ошибок под ячейкой — ясные семёрки, которые сеть приняла за девятки и пятёрки. Написаны они очень похоже, с одинаковым крючком слева у верхней черты, — видимо, одной рукой. И ни одна не перечёркнута посередине, а в обучающей выборке перечёркнуты девять семёрок из десяти: семёрок без черты сеть почти не видела. К этому мы ещё вернёмся.

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

Экзамен

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

На двадцати примерах — в среднем по два на цифру — сеть знает их все: 100 % на обучении. А на экзамене — около 60 %. Это переобучение: семнадцати тысяч весов хватает, чтобы запомнить двадцать картинок со всеми их случайными чертами — наклоном, толщиной, кляксой, — и модель запоминает их, вместо того чтобы искать общее. Чем больше примеров, тем труднее зубрить и тем меньше разрыв: на тысяче он около шести процентов, на всей выборке — три с половиной. (Шестьдесят процентов по двадцати примерам, впрочем, тоже неплохо: случайное угадывание дало бы десять.)

Главное правило лагеря такое: часть примеров откладывают до самого конца и ни разу не показывают модели. Это отложенная выборка. Только точность на ней говорит, как модель будет работать на новых данных. Точность на обучающих примерах говорит лишь о том, насколько хорошо модель их запомнила. Испортить отложенную выборку легко, а заметить порчу трудно. Если вы перепробуете двадцать вариантов сети и оставите тот, что лучше сдал экзамен, — экзамен стал частью обучения: вы подобрали модель под эти 1797 цифр. Поэтому настройки выбирают по третьей, проверочной части, а экзамен сдают один раз. У авторов нашего набора такая часть была: из 3823 цифр тридцати человек они учили модели на половине, 946 цифр держали для проверки, а экзаменом служили 1797 цифр тринадцати других людей. Мы для простоты учим на всех 3823, так что проверочной части в этой главе нет.

Но и у этого правила есть предел. Модель учится тому, что есть в данных, а не тому, что мы имели в виду: семёрки незнакомого почерка из прошлого раздела она путает с девятками. Бывает и хуже. В 2018 году агентство Reuters рассказало, что Amazon с 2014 года пробовала оценивать резюме кандидатов моделью, обученной на резюме, присланных в компанию за десять лет. Присылали их в основном мужчины, и к 2015 году выяснилось, что модель снижает оценку резюме, где встречается слово women's — «женский». Модель пытались поправить, но положиться на неё так и не смогли, и от проекта отказались. Отложенная выборка такую беду не поймает: она взята из тех же данных, с тем же перекосом, и на ней модель выглядит точной.

Ваш почерк

Последний экзамен — самый строгий. В выборке нет ни одной цифры, написанной вами. Обучите сеть на сервере и нарисуйте цифру пальцем или мышью.

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

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

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

Модель языка

Осталось объяснить, как устроены программы, которые пишут тексты. В главе 8 мы уже собрали одну: словарь «какое слово за каким шло» и случайный выбор следующего. Это была языковая модель — функция, которая по началу текста даёт вероятности следующего кусочка. Сделаем её чуть зорче: пусть угадывает следующий символ по четырём предыдущим. Обучать будем на первых 90 % романа, последние 10 % отложим.

Counter — словарь-счётчик: у отсутствующего ключа значение 0, а most_common(3) отдаёт три самых частых. defaultdict(Counter) сам заводит пустой счётчик для нового контекста. Получается не Толстой, но уже почти слова: «кутузов», «закричал», «противоположил». Модель знает только, что шло за четырьмя символами, — и всё равно пишет по-русски на вид.

Сравнивать такие модели будем экзаменом на отложенных 10 % романа. Мера удивления та же, что у сети с цифрами, только в битах, а не в натуральных логарифмах: $-\log_2 p$ того символа, что стоит в тексте. Если усреднить её по тексту, получится та же энтропия, что в главе о сжатии: с моделью, которая удивляется на 2 бита на символ, текст можно сжать до 2 бит на символ. Проверим модели с контекстом от нуля до пяти символов.

Без контекста модель знает только частоты букв: 4,6 бита. Каждый символ контекста помогает: 3,6, 2,9, 2,3, 2,1 бита. А на пяти символах — хуже, чем на четырёх. Это снова переобучение, теперь у языковой модели: пятисимвольных контекстов в романе сотни тысяч, большинство встречалось по разу-другому, и модель запоминает случайные продолжения вместо закономерностей. Добавочка 0,01 в формуле нужна по той же причине: без неё сочетание, которого не было в обучающем тексте, получило бы вероятность ноль и бесконечное удивление.

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

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

Задачи

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

Напишите fit_line(xs, ys): градиентным спуском найдите веса $w$ и $b$ прямой $y = w x + b$ с наименьшим средним квадратом промаха и верните пару (w, b). Тесты сравнивают ваши потери с потерями наилучшей прямой: проиграть ей можно не больше 1 %. Данные бывают неудобными: годы от 1900 до 2020, цены квартир в миллионах, все $x$ одинаковые, сто тысяч точек, которые нужно обработать быстрее двух секунд. Готовыми формулами — np.polyfit, np.linalg.lstsq и обращением матриц — пользоваться нельзя, тесты это проверяют.

Запустите тесты: на годах веса разлетаются. При $x \approx 2000$ кривизна ямы по $w$ порядка $2x^2 = 8$ миллионов, и безопасный шаг меньше $2/(8 \cdot 10^6)$. С таким шагом $b$ не сдвинется с места и за миллион шагов. Это овраг из виджета, только очень узкий.

Приведите $x$ к масштабу: $u = (x - m)/s$, где $m$ — среднее, $s$ — стандартное отклонение. Ищите прямую $y = w' u + b'$: у неё яма круглая, и при шаге 0,5 спуск сходится за считаные шаги. Потом верните её к исходному $x$: $w = w'/s$, $b = b' - w' m / s$.

Если все $x$ одинаковые, $s = 0$ и делить нельзя. Подойдёт горизонтальная прямая на высоте среднего $y$. А для ста тысяч точек замените суммы в цикле на операции numpy: np.mean(miss * u).

После замены $x$ на $u$ у функции потерь обе кривизны равны 2: $\partial^2 L/\partial w^2 = 2\,\overline{u^2} = 2$ и $\partial^2 L/\partial b^2 = 2$, а смешанная производная $2\,\bar u = 0$. Яма стала круглой, и шаг $\eta = 0{,}5 = 1/2$ попадает в дно за один шаг — дальше спуск стоит на месте. Без нормировки та же задача требует шага в миллионы раз меньше. Нормировка входов — первое, что делают перед обучением любой модели, от прямой до сети с миллиардами весов.

Напишите train_perceptron(points, labels, epochs). points — список точек (списков чисел одной длины), labels — ответы +1 и −1. Функция учит перцептрон правилом Розенблатта, начиная с нулевых весов, и возвращает пару (w, b) — список весов и сдвиг, — при которой каждая точка лежит строго на своей стороне: $t\,(w \cdot x + b) > 0$. Если за epochs эпох такой границы найти не удалось, верните None. Среди тестов — XOR, цифры из главы и точки с очень узким зазором.

В заготовке две беды. Первая — знак сравнения: точка ровно на границе ($s = 0$) не ошибка для заготовки, и нулевые веса в самом начале считаются верными для всех точек сразу. Вторая — она никогда не останавливается и не говорит, что границы нет.

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

Сравнение <= 0 вместо < 0 — не мелочь: без него перцептрон с нулевыми весами считает себя правым на всём и ничему не учится. Узкий зазор показывает, о чём говорит теорема: число ошибок растёт как $(R/\gamma)^2$, и при зазоре 0,01 перцептрону нужны десятки эпох (в тесте — 64), хотя граница есть. А вот обратное теорема не обещает: «не нашёл за 1000 эпох» ещё не доказывает, что границы нет, — может быть, зазор очень мал. Поэтому пустой ответ функции означает «не нашёл», и только.

Самый простой ученик ничего не обобщает: он запоминает все примеры, а на вопрос отвечает так, как отвечали похожие. Напишите knn_predict(train_x, train_y, test_x, k): для каждой строки test_x найдите $k$ ближайших строк train_x (расстояние — обычное, корень из суммы квадратов разностей) и верните метку, которая среди них встречается чаще всех. Если таких меток несколько, побеждает та, чей представитель ближе всех. Аргументы — массивы numpy, ответ — список или массив меток. Главный тест: все 1797 экзаменационных цифр по 3823 обучающим, точность не ниже 97 % и не дольше трёх секунд.

Заготовка верна по смыслу, но медленна: 1797 × 3823 расстояний по 256 пикселей — почти два миллиарда операций в цикле Python. Ничью она, кстати, решает правильно: соседи добавляются в словарь от ближнего к дальнему, а max из равных выбирает первый — сохраните это свойство.

Все расстояния сразу даёт одно умножение матриц: $|a - b|^2 = |a|^2 - 2\,a \cdot b + |b|^2$. Столбец $|a|^2$ по экзаменационным строкам, строка $|b|^2$ по обучающим и матрица test_x @ train_x.T складываются в таблицу 1797 × 3823. Корень извлекать не нужно: порядок соседей от него не меняется.

np.argsort(d, axis=1)[:, :k] даёт номера $k$ ближайших в каждой строке, уже по порядку от ближнего. Подсчёт голосов можно оставить в обычном цикле: их всего 1797 × $k$.

Около 98 % — больше, чем у нашей сети. На маленьких данных простые методы сильны, и сравнивать с ними полезно всегда: сложная модель должна выиграть у соседей, иначе зачем она. Но у соседей своя цена. Чтобы ответить, им нужна вся обучающая выборка и сравнение с каждым примером; сеть хранит 17 тысяч чисел и отвечает двумя умножениями матриц. На миллионе фотографий соседи уже не справляются ни по памяти, ни по точности: расстояние «пиксель к пикселю» не замечает, что кошка сдвинулась на полкадра.

Напишите train_gate(table, seed): обучите сеть со скрытым слоем вентилю с двумя входами. table — четыре нужных ответа для входов (0, 0), (0, 1), (1, 0), (1, 1), например [0, 1, 1, 0] для XOR; seed — зерно для случайного старта. Верните части сети (W1, b1, w2, b2): W1 размера 2 × $k$, b1 и w2 по $k$ чисел, b2 — число. Тесты сами считают выход $\sigma(\sigma(x W_1 + b_1)\,w_2 + b_2)$ и требуют, чтобы на всех четырёх входах он был по нужную сторону от 0,5. Проверяются все шестнадцать вентилей, а XOR и равенство — с двадцати разных стартов.

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

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

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

Куда дальше

Правило, которое человек не может записать, машина находит по примерам, если дать ей модель с ручками, меру промаха и спуск. Но считает всё это та же машина из части IV: биты, вентили, умножение чисел. Сеть, которая учит XOR, сама собрана из XOR.

Есть задача, перед которой эта машина бессильна всерьёз. Чтобы описать квантовое состояние пятидесяти крошечных магнитиков — спинов электронов, — нужно $2^{50}$, около $10^{15}$, комплексных чисел: петабайты памяти. Для трёхсот спинов чисел больше, чем атомов в наблюдаемой Вселенной. А природа как-то справляется с этим каждую долю секунды в любой молекуле. В 1981 году Ричард Фейнман сделал из этого вывод: если природа не классическая, то и машину для её моделирования стоит строить не на битах. Все наши машины до сих пор были построены на битах. Другой способ вычислять, который допускает физика, — в следующей главе.