Эпоха 1 · Истоки · 1958

3 Перцептрон

The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain · Frank Rosenblatt · Psychological Review
🟧 оригинал выборочно~1–1.5 чоригинал ↗
Суть за 20 секунд. Первый обучаемый нейрон: линейный классификатор с правилом, которое само двигает веса при ошибке, плюс доказанная гарантия — если данные линейно разделимы, обучение сойдётся за конечное число шагов. Великий и переоценённый: его пределы (XOR) запустят первую «зиму ИИ».

Контекст

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

Идея и механизм

Перцептрон считает взвешенную сумму и применяет знак:

y = sign(w·x + b)

Принципиально новое — правило обучения. Показываем примеры с меткой t ∈ {−1, +1}; при ошибке сдвигаем веса к правильному ответу:

w ← w + η (t − y) x

Геометрически w — нормаль к разделяющей гиперплоскости; на ошибке мы прибавляем сам входной вектор, поворачивая плоскость к неправильно классифицированной точке.

линейная алгебра Теорема сходимости: почему ошибок не больше (R/γ)²

Пусть данные разделимы единичным w* (‖w*‖ = 1) с зазором γ, то есть ti(w*·xi) ≥ γ для всех точек, и все ‖xi‖ ≤ R. Стартуем с w = 0. Оценим норму w после k ошибок с двух сторон.

Снизу. Каждая ошибка двигает w ← w + tixi, и проекция на w* растёт минимум на γ:

w*·wk ≥ kγ  ⟹   ‖wk‖ ≥ kγ  (Коши–Шварц)

Сверху. На ошибке ti(w·xi) ≤ 0, поэтому норма растёт не больше чем на R²:

‖wk‖² ≤ kR²  ⟹   ‖wk‖ ≤ √ k  R

Совмещаем. kγ ≤ ‖wk‖ ≤ √ k  R, откуда √ k  ≤ R/γ и финально:

k ≤ (R / γ)²    ∎

Число ошибок конечно и не зависит от размерности — только от геометрии (радиус данных / зазор). Это ранний образец margin-based обобщения, идея которого расцветёт в SVM (#10).

NumPy Реализация: обучение перцептрона 
import numpy as np

def perceptron(X, y, eta=1.0, epochs=100):
    w = np.zeros(X.shape[1]); b = 0.0
    for _ in range(epochs):
        errors = 0
        for xi, ti in zip(X, y):          # ti ∈ {−1, +1}
            if ti * (w @ xi + b) <= 0:     # ошибка классификации
                w += eta * ti * xi         # поворот плоскости к точке
                b += eta * ti
                errors += 1
        if errors == 0:                    # разделимо → сошлось
            break
    return w, b
w·x+b=0 w (нормаль)
Два класса (○ и ▢) и разделяющая прямая. Вектор весов w — нормаль к ней. Правило обучения поворачивает прямую к ошибочной точке, пока классы не разделены.
Аналогия. Вы разделяете на столе две кучки монет одной линейкой. Пара монет не на той стороне — вы чуть проворачиваете линейку в их сторону. Ещё ошибка — ещё проворот. Если кучки в принципе разделимы прямой, за конечное число поправок вы найдёте верное положение. Перцептрон делает ровно это в многомерном пространстве.

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

Перцептрон — прямой предок современного искусственного нейрона: линейная комбинация → нелинейность → обновление весов градиентного типа. Вся глубокая сеть — многослойная конструкция из таких элементов. И это первый случай доказуемого машинного обучения. Обратная сторона — назидательная: завышенные ожидания и реальное ограничение (только линейно разделимое) столкнутся в книге Минского и Паперта.

Связи

← опирается на1. Нейрон Маккаллока–Питтса

Тот же пороговый нейрон, но теперь с обучаемыми весами и алгоритмом, который настраивает их из размеченных примеров. Перцептрон — это МП-нейрон, которого научили учиться.

↔ ограничивается в4. Perceptrons (критика)

Теорема сходимости работает только для линейно разделимых данных. Минский и Паперт строго показывают, что XOR в этот класс не входит — и обрывают теорему ровно там, где кончается линейная разделимость.

→ ведёт к7. Backpropagation

Ограничение снимается добавлением скрытых слоёв — но их нужно уметь обучать. Backprop обобщает «двигай веса по ошибке» на многослойный случай через цепное правило, и XOR падает.

↔ перекликается10. SVM

Оба — линейные разделители, и оба завязаны на зазор γ. Но перцептрон зазор лишь использует (для гарантии сходимости), а SVM его максимизирует — выбирает не любую разделяющую плоскость, а самую устойчивую.

Вопросы пытливого ума

Теорема гарантирует сходимость — а если данные НЕ линейно разделимы?

Тогда гарантии нет: алгоритм будет вечно колебаться, перепрыгивая между весами, и никогда не остановится. На практике берут «pocket»-вариант (хранить лучшие встреченные веса) или переходят к методам, терпящим ошибки (логрег, SVM с мягким зазором). Сам этот провал на неразделимых данных — и есть то, что вскроют Минский и Паперт на примере XOR.

Граница (R/γ)² не зависит от размерности — разве это не странно?

Наоборот, это глубокий результат. Число ошибок определяется геометрией (радиус данных и зазор), а не числом признаков — можно работать в миллионмерном пространстве, и оценка та же. Это ранний пример margin-based анализа обобщения: «качество зависит от зазора, не от размерности». Та же философия лежит в основе SVM и теории Вапника.

Чем правило перцептрона отличается от градиентного спуска и логистической регрессии?

Правило перцептрона — это субградиент кусочной (hinge-подобной) потери, который срабатывает только на ошибках и не даёт вероятностей. Логистическая регрессия минимизирует гладкую вероятностную потерю и обновляется на каждом примере. Перцептрон — жёсткий частный предок этого семейства; SGD и логрег — его сглаженные, вероятностные потомки.

Что читать в оригинале

Читать выборочно: модель и правило обновления. Психологическое обрамление можно пролистать. А вот теорему сходимости (роль отношения R/γ) стоит понять — это первый мостик к идее зазора, которая станет ядром SVM и теории обобщения.