Перцептрон

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

Задача

Дано множество точек на плоскости $[-1,1]^2$, разделённых на два класса ($y = +1$ и $y = -1$) прямой линией $a x_1 + b x_2 + c = 0$. Нужно по обучающей выборке найти веса $w_1, w_2$ и смещение $b$ (bias), задающие разделяющую прямую:

$w_1 x_1 + w_2 x_2 + \text{bias} = 0$

Точки, для которых выражение положительно, относятся к классу $+1$, а для которых отрицательно -- к классу $-1$.

Линейная разделимость означает, что существует прямая, которая полностью разделяет точки двух классов. Чтобы гарантировать это, точки, лежащие слишком близко к разделяющей прямой (ближе маржи $\delta$), отбрасываются при генерации данных.

Идея алгоритма

Генерируем случайную прямую-«учителя» $a x_1 + b x_2 + c = 0$ с нормированными коэффициентами.
Создаём обучающую выборку из 4000 точек: для каждой точки $(x_1, x_2)$ определяем класс по знаку $a x_1 + b x_2 + c$. Точки ближе $\delta = 0.1$ к прямой отбрасываем (они в «зоне неопределённости»).
Создаём тестовую выборку из 20000 точек аналогично, с небольшим шумом в метках (около 1% инвертированных меток).
Инициализируем веса нулями: $w_1 = 0, w_2 = 0, \text{bias} = 0$.
Обучаем по правилу Розенблатта: проходим по обучающей выборке, и если точка классифицирована неверно ($y \cdot (w_1 x_1 + w_2 x_2 + \text{bias}) \leq 0$), корректируем веса: $w := w + \eta \cdot y \cdot x$, $\text{bias} := \text{bias} + \eta \cdot y$.
Если за целую эпоху (проход по всем данным) не было ни одной ошибки -- останавливаемся досрочно.
Вычисляем точность (accuracy) на обучающей и тестовой выборках.

Разбор

Гиперпараметры

| гиперпараметры
цел Ntrain, Ntest, epochs
вещ eta, delta
вещ noise_te         | доля шума в метках теста (для нереализуемости 100%)
Ntrain := 4000
Ntest := 20000
epochs := 50
eta := 0.1
delta := 0.1      | маржа для отбора точек
noise_te := 0.01  | ~1% инвертируем метки на тесте

$\eta = 0.1$ -- скорость обучения (learning rate), на сколько сильно корректируются веса при ошибке.
$\delta = 0.1$ -- маржа (отступ от разделяющей прямой), гарантирующая линейную разделимость.

Генерация прямой-учителя и обучающей выборки

Случайная прямая задаётся коэффициентами $a, b, c$, которые нормируются для удобства. При генерации обучающих данных точки с расстоянием до прямой меньше $\delta$ отбрасываются, чтобы гарантировать разделимость.

| параметры прямой-учителя (a*x1 + b*x2 + c = 0)
вещ la, lb, lc
la := rand(-1.0, 1.0)
lb := rand(-1.0, 1.0)
lc := rand(-0.2, 0.2)
| нормируем (не обязательно, просто косметика)
вещ norm
norm := sqrt(la*la + lb*lb)
если norm <> 0.0 то
  la := la / norm
  lb := lb / norm
  lc := lc / norm
все

| генерация train с отбрасыванием по марже delta
цел i
вещ x1, x2, s, vabs, y
i := 0
нц пока i < Ntrain
  x1 := rand(-1.0, 1.0)
  x2 := rand(-1.0, 1.0)
  s := la*x1 + lb*x2 + lc
  vabs := s; если vabs < 0.0 то vabs := -vabs все
  если vabs >= delta то
    y := 1.0; если s < 0.0 то y := -1.0 все
    X1tr[i] := x1; X2tr[i] := x2; Ytr[i] := y
    i := i + 1
  все
кц

Цикл обучения перцептрона

На каждом проходе (эпохе) проверяем все обучающие точки. Если предсказание неверное (маржа $y \cdot \text{pred} \leq 0$), обновляем веса по правилу Розенблатта. Если за эпоху не было ошибок -- выходим досрочно.

| модель: w ∈ R^2, bias
вещ w1, w2, bias
w1 := 0.0; w2 := 0.0; bias := 0.0

| обучение персептрона
цел e, mistakes
вещ pred, margin
нц для e от 0 до epochs-1
  mistakes := 0
  нц для i от 0 до Ntrain-1
    pred := w1*X1tr[i] + w2*X2tr[i] + bias
    margin := Ytr[i] * pred
    если margin <= 0.0 то
      w1 := w1 + eta * Ytr[i] * X1tr[i]
      w2 := w2 + eta * Ytr[i] * X2tr[i]
      bias := bias + eta * Ytr[i]
      mistakes := mistakes + 1
    все
  кц
  | если ошибок нет — выходим раньше
  если mistakes = 0 то выход все
кц

Подсчёт точности

Функция accuracy считает долю правильно классифицированных точек: для каждой точки вычисляет предсказание и сравнивает его знак с истинной меткой.

алг вещ accuracy(цел n, вещ таб X1[0:n-1], вещ таб X2[0:n-1], вещ таб Y[0:n-1], вещ w1, вещ w2, вещ bias)
нач
  цел i, correct
  вещ pred, y, acc
  correct := 0
  нц для i от 0 до n-1
    pred := w1*X1[i] + w2*X2[i] + bias
    y := 1.0; если pred < 0.0 то y := -1.0 все
    если y = Y[i] то correct := correct + 1 все
  кц
  acc := (1.0 * correct) / n
  знач := acc
кон

Вывод результатов

вещ acc_tr, acc_te
acc_tr := accuracy(Ntrain, X1tr, X2tr, Ytr, w1, w2, bias)
acc_te := accuracy(Ntest,  X1te,  X2te,  Yte,  w1, w2, bias)

вывод "perceptron: Ntrain=", Ntrain, ", Ntest=", Ntest, ", epochs=", epochs, ", eta=", eta, ", delta=", delta, нс
вывод "teacher line: a=", la, ", b=", lb, ", c=", lc, нс
вывод "train acc=", acc_tr, ", test acc=", acc_te, нс

Полная программа

| Персептрон для линейно разделимых 2D-точек.
| Задача: порождаем обучающую и тестовую выборки из квадрата [-1,1]^2.
| Истинная разметка задаётся случайной прямой a*x1 + b*x2 + c = 0.
| Чтобы гарантировать разделимость, отбрасываем точки ближе маржи δ к прямой.
| Обучаем персептрон по правилу Розенблатта и печатаем точность train/test.

алг main
нач
  | гиперпараметры
  цел Ntrain, Ntest, epochs
  вещ eta, delta
  вещ noise_te         | доля шума в метках теста (для нереализуемости 100%)
  Ntrain := 4000
  Ntest := 20000
  epochs := 50
  eta := 0.1
  delta := 0.1      | маржа для отбора точек
  noise_te := 0.01  | ~1% инвертируем метки на тесте

  | массивы данных
  вещ таб X1tr[0:Ntrain-1], X2tr[0:Ntrain-1], Ytr[0:Ntrain-1]
  вещ таб X1te[0:Ntest-1],  X2te[0:Ntest-1],  Yte[0:Ntest-1]

  | параметры прямой-учителя (a*x1 + b*x2 + c = 0)
  вещ la, lb, lc
  la := rand(-1.0, 1.0)
  lb := rand(-1.0, 1.0)
  lc := rand(-0.2, 0.2)
  | нормируем (не обязательно, просто косметика)
  вещ norm
  norm := sqrt(la*la + lb*lb)
  если norm <> 0.0 то
    la := la / norm
    lb := lb / norm
    lc := lc / norm
  все

  | генерация train с отбрасыванием по марже delta
  цел i
  вещ x1, x2, s, vabs, y
  i := 0
  нц пока i < Ntrain
    x1 := rand(-1.0, 1.0)
    x2 := rand(-1.0, 1.0)
    s := la*x1 + lb*x2 + lc
    vabs := s; если vabs < 0.0 то vabs := -vabs все
    если vabs >= delta то
      y := 1.0; если s < 0.0 то y := -1.0 все
      X1tr[i] := x1; X2tr[i] := x2; Ytr[i] := y
      i := i + 1
    все
  кц

  | генерация test
  i := 0
  нц пока i < Ntest
    x1 := rand(-1.0, 1.0)
    x2 := rand(-1.0, 1.0)
    s := la*x1 + lb*x2 + lc
    vabs := s; если vabs < 0.0 то vabs := -vabs все
    если vabs >= delta то
      y := 1.0; если s < 0.0 то y := -1.0 все
      | внесём небольшой шум в метки теста
      вещ r
      r := rand(0.0, 1.0)
      если r < noise_te то y := -y все
      X1te[i] := x1; X2te[i] := x2; Yte[i] := y
      i := i + 1
    все
  кц

  | модель: w ∈ R^2, bias
  вещ w1, w2, bias
  w1 := 0.0; w2 := 0.0; bias := 0.0

  | обучение персептрона
  цел e, mistakes
  вещ pred, margin
  нц для e от 0 до epochs-1
    mistakes := 0
    нц для i от 0 до Ntrain-1
      pred := w1*X1tr[i] + w2*X2tr[i] + bias
      margin := Ytr[i] * pred
      если margin <= 0.0 то
        w1 := w1 + eta * Ytr[i] * X1tr[i]
        w2 := w2 + eta * Ytr[i] * X2tr[i]
        bias := bias + eta * Ytr[i]
        mistakes := mistakes + 1
      все
    кц
    | если ошибок нет — выходим раньше
    если mistakes = 0 то выход все
  кц

  | точности
  вещ acc_tr, acc_te
  acc_tr := accuracy(Ntrain, X1tr, X2tr, Ytr, w1, w2, bias)
  acc_te := accuracy(Ntest,  X1te,  X2te,  Yte,  w1, w2, bias)

  вывод "perceptron: Ntrain=", Ntrain, ", Ntest=", Ntest, ", epochs=", epochs, ", eta=", eta, ", delta=", delta, нс
  вывод "teacher line: a=", la, ", b=", lb, ", c=", lc, нс
  вывод "train acc=", acc_tr, ", test acc=", acc_te, нс
кон

| --- Вспомогательные функции ---

| точность классификации при данных весах
алг вещ accuracy(цел n, вещ таб X1[0:n-1], вещ таб X2[0:n-1], вещ таб Y[0:n-1], вещ w1, вещ w2, вещ bias)
нач
  цел i, correct
  вещ pred, y, acc
  correct := 0
  нц для i от 0 до n-1
    pred := w1*X1[i] + w2*X2[i] + bias
    y := 1.0; если pred < 0.0 то y := -1.0 все
    если y = Y[i] то correct := correct + 1 все
  кц
  acc := (1.0 * correct) / n
  знач := acc
кон

▶ Запустить пример