ML Данные и машинное обучение Алгоритм
Перцептрон и обратное распространение
Также: Perceptron · перцептрон Розенблатта · backpropagation · обратное распространение ошибки · многослойный перцептрон · MLP · averaged perceptron · усреднённый перцептрон · XOR · исключающее или
Перцептрон — линейное правило с простейшим обучением: ошибся — сдвинь веса к правильному ответу. На рукописных цифрах он узнаёт 94–95 из 100, но не умеет «исключающее или». Скрытый слой это исправляет, а обратное распространение считает все производные сети за цену двух проходов вместо тысяч.
Сорок три человека написали цифры на бланках; бланки отсканировали, каждую цифру ужали до картинки 8 × 8, где в клетке — сколько чёрных точек из шестнадцати. Тридцать человек дали 3823 цифры для обучения, тринадцать других — 1797 для проверки. Перцептрон — линейное правило, придуманное в 1958 году, — после четырёх проходов по обучающим цифрам узнаёт 94,6 из ста проверочных. Сеть со скрытым слоем из 32 нейронов, обученная обратным распространением, — около 96. Обе модели ниже учатся прямо в браузере, за секунду. Нарисуйте цифру — или возьмите проверочную.
Рисунок готовится так же, как готовили данные: чернила обрезаются по рамке, растягиваются в квадрат 32 × 32 и считаются блоками 4 × 4 — посередине видно, что получает модель.
Идея перцептрона
У каждой цифры свой вектор из 64 весов и сдвига. Ответ — цифра, у которой сумма «вес × клетка» больше всех. Учится перцептрон только на ошибках: если на картинке x он назвал p, а правильно t, к весам t прибавляется x, а из весов p вычитается. Так в следующий раз сумма у t на этой картинке станет больше, а у p — меньше. Всё в целых числах, никакого шага обучения.
Это линейный классификатор: граница между двумя цифрами — гиперплоскость в 64-мерном пространстве картинок. Если такая граница существует с запасом, перцептрон находит её за конечное число ошибок, сколько бы картинок ни было.
Пусть у картинок |x| ≤ R, ответы y = ±1, и есть единичный вектор u, для которого y·(u·x) ≥ γ > 0 на всех картинках. Тогда перцептрон с двумя классами, начав с нуля, ошибётся не больше (R/γ)² раз — при любом порядке и любом числе проходов.
При ошибке на (x, y) вес меняется: w ← w + y·x, причём ошибка значит y·(w·x) ≤ 0. Проекция на u растёт хотя бы на γ: u·w увеличивается на y·(u·x) ≥ γ. Квадрат длины растёт не больше чем на R²: |w + yx|² = |w|² + 2y(w·x) + |x|² ≤ |w|² + R². После k ошибок u·w ≥ kγ и |w|² ≤ kR². Так как u единичный, u·w ≤ |w|, значит kγ ≤ √k·R, то есть k ≤ (R/γ)².
Цифры этим условиям не подчиняются: обучающие цифры десяти классов, по-видимому, не разделяются линейно, и перцептрон продолжает ошибаться — 530 ошибок на первом проходе, 196 на четвёртом. А верность на проверке прыгает: 92,2 %, 89,6 %, 92,0 %, 89,6 % — веса качаются от последних ошибок. Лечит это усреднение: ответ даёт не последний вектор весов, а среднее всех векторов за обучение (Йоав Фройнд и Роберт Шапир, 1999). Среднее считается без хранения истории — копится сумма поправок, умноженных на номер шага. Усреднённый перцептрон даёт 93,3, 94,3, 94,5 и 94,6 % — спокойно и лучше.
Чего не может одна граница
Не существует w1, w2, b, при которых w·x + b > 0 на (0, 1) и (1, 0) и ≤ 0 на (0, 0) и (1, 1).
Сложим условия для (0, 1) и (1, 0): w1 + w2 + 2b > 0. Сложим для (0, 0) и (1, 1): b + (w1 + w2 + b) = w1 + w2 + 2b ≤ 0. Противоречие.
Перцептрон на «исключающем или» ошибается на каждом проходе — в листинге он делает четыре ошибки и после сотого. Марвин Минский и Сеймур Пейперт в книге 1969 года показали, что такие ограничения у одного слоя принципиальные: проверить чётность числа точек или связность фигуры он не может. Выход — промежуточный слой: нейроны, каждый из которых проводит свою границу, а следующий слой собирает из их ответов. Двух скрытых нейронов для «исключающего или» хватает: один проводит границу «хоть одна единица», другой — «обе единицы».
Обучение скрытого слоя
У скрытого нейрона нет правильного ответа — неизвестно, что он должен выдавать. Поэтому вместо правила «ошибся — сдвинь» учат градиентным спуском: ступенька заменяется гладкой функцией (tanh, сигмоида), ошибка — гладкой функцией потерь, и все веса сдвигаются против её градиента. Вопрос — как быстро посчитать градиент по всем весам. Подробно, с автоградом своими руками, это разобрано в главе «Как ошибка течёт назад» курса «Своя LLM с нуля»; здесь — почему это дёшево.
Пусть сеть вычисляет потери цепочкой элементарных операций — сложений, умножений, tanh, exp, — всего N операций. Тогда производные потерь по всем весам вычисляются за O(N) операций — столько же, сколько сам проход вперёд, с постоянным множителем.
Запишем вычисление как граф: узел — промежуточное значение, ребро — его использование в следующей операции. Для каждого узла v нужна производная потерь по нему, ∂L/∂v. По цепному правилу она равна сумме по всем рёбрам v → w произведений ∂L/∂w · ∂w/∂v, а ∂w/∂v — производная одной элементарной операции, известная из прохода вперёд: для умножения — второй множитель, для tanh — 1 − tanh². Обойдём узлы в обратном порядке: когда дошли до v, все w после него уже посчитаны. Каждое ребро используется один раз, у элементарной операции не больше двух входов, значит, рёбер не больше 2N, и обратный проход — O(N). Производные по весам — это производные по входным узлам графа.
Разностная производная — изменить вес на ±10−5 и пересчитать потери — требует двух проходов на каждый вес. Для сети 64 → 16 → 10 с 1210 весами это 2420 проходов против одного вперёд и одного назад.
Код
Листинг показывает три вещи. Усреднённый перцептрон на цифрах — в целых числах, так что Python и Go считают одно и то же до бита. «Исключающее или» с двумя скрытыми нейронами выучилось из пяти случайных стартов из десяти, остальные застряли на полпути. С восемью нейронами — из десяти из десяти: лишние нейроны дают спуску больше путей. И проверка градиента: разностные производные по всем 1210 весам совпали с обратным проходом до 10−7.
Веса перцептрона — это картинки: оранжевые клетки голосуют «за» свою цифру, синие — «против». Читаются они хуже, чем хотелось бы: у нуля синяя середина — чернила в центре говорят «это не ноль», — а остальные картинки пёстрые. Перцептрон учится не рисовать цифры, а отличать их друг от друга, и вес клетки зависит от того, с какими цифрами её чаще путают. Скрытые нейроны сети ещё пестрее: каждый реагирует на какое-то сочетание клеток, и смысл появляется только в том, как последний слой их складывает. На графике снизу — верность на проверке по проходам: у перцептрона она скачет, у усреднённого растёт спокойно, сеть уходит выше — до 96,3 %.
Сколько это стоит
Время обратного прохода растёт пропорционально числу весов, разностных производных — пропорционально его квадрату. При 1210 весах в Python разница уже почти в сто раз, при 4810 в Go — больше чем в тысячу. У сети с миллиардом весов разностный градиент потребовал бы двух миллиардов проходов вперёд на один шаг обучения; обратный проход стоит как пара проходов.
Где легко ошибиться
- Последний вектор вместо среднего. Без усреднения перцептрон отвечает весами, подогнанными под последние ошибки, и его верность на новых данных скачет на несколько процентов от прохода к проходу.
- Одинаковые начальные веса. Если все скрытые нейроны начинают с одних и тех же весов, градиенты у них одинаковые, и они навсегда остаются копиями друг друга. Начальные веса берут случайными.
- Мало нейронов. Два нейрона для «исключающего или» — ровно впритык, и спуск находит решение не из каждого старта. Сети берут с запасом.
- Проверка градиента — с допуском и по модулю разницы. Относительная разница для крошечных производных тонет в шуме округления разностной схемы; сравнивают абсолютную разницу с масштабом самих производных.
- Масштаб входов. Числа 0…16 в tanh сразу насыщают нейроны: производная 1 − tanh² почти ноль, и обучение стоит. Входы делят на 16.
Где работает
Нейросети. Любая современная сеть учится градиентным спуском, а градиент считает обратное распространение — в PyTorch, JAX и TensorFlow это обратный проход по записанному графу вычислений.
Линейные модели для текста. Усреднённый перцептрон долго был стандартом для разметки текста — частей речи, имён — после работы Майкла Коллинза 2002 года: быстрый, простой и почти такой же точный, как более сложные модели того времени.
Научные расчёты. Обратное распространение — частный случай автоматического дифференцирования в обратном режиме; так считают производные сложных моделей в оптимизации, механике и климатических расчётах, не выводя формул.
Распознавание. Цифры и буквы на конвертах, чеках и бланках — задача, на которой нейросети впервые стали работать в массовых системах в 1990-х.
История
Фрэнк Розенблатт описал перцептрон в 1958 году и построил машину Mark I Perceptron: 400 фотоэлементов, веса — потенциометры, которые поворачивали моторы. Альберт Новиков в 1962 году доказал теорему о конечном числе ошибок. Марвин Минский и Сеймур Пейперт в 1969 году разобрали, чего один слой не может, и интерес к нейросетям надолго упал. Обратный режим дифференцирования описал Сеппо Линнаинмаа в 1970 году, применить его к сетям предложил Пол Вербос в 1974 году, а широко известным метод сделала статья Дэвида Румельхарта, Джеффри Хинтона и Рональда Уильямса 1986 года. Набор рукописных цифр этой статьи собрали Этем Алпайдын и Дженк Кайнак в 1998 году.
Задачи
Посчитать все производные маленькой сети за один обратный проход.
Все производные сетиДанные: Рукописные цифры: Optical Recognition of Handwritten Digits, E. Alpaydin, C. Kaynak (1998), UCI, CC BY 4.0