Забор со стрелкой

Забор, стрелка и расстояние со знаком

В уроке 6 перцептрон делил плоскость прямой. В общем случае границу называют гиперплоскостью (hyperplane): это все точки \(\vb{x}\), для которых \(\vb{w}\T\vb{x} + w_0 = 0\). При двух входах это прямая, при трёх — плоскость, дальше воображение отказывает, а формула остаётся той же.

Картинка на весь урок: гиперплоскость — это забор, а к забору прибита стрелка \(\vb{w}\). Стрелка торчит перпендикулярно забору и показывает сторону, где перцептрон отвечает \(+1\). Число \(w_0\) двигает забор параллельно самому себе.

Чтобы превратить картинку в формулу, хватает одной идеи: расстояние до забора — это проекция на направление стрелки. Вывод со слайда «Hyperplanes Linear Algebra» занимает пять шагов, и это экзаменационный материал.

1. Возьмём две любые точки \(\vb{u}\) и \(\vb{v}\) на заборе (на слайде они названы \(\vb{x}_1\) и \(\vb{x}_2\)). Обе обнуляют выражение:

   \[ w_0 + \vb{w}\T\vb{u} = 0 \] \[ w_0 + \vb{w}\T\vb{v} = 0 \]

2. Вычтем одно из другого, \(w_0\) сократится:

   \[ \vb{w}\T(\vb{u} - \vb{v}) = 0 \]

   Вектор \(\vb{u} - \vb{v}\) лежит вдоль забора, а его скалярное произведение с \(\vb{w}\) равно нулю. Значит, \(\vb{w}\) перпендикулярен забору: это нормаль (normal vector).

3. Длина \(\vb{w}\) может быть любой, а мерить расстояния нужно стрелкой единичной длины (на слайде — «versor»):

   \[ \vb{w}^{*} = \frac{\vb{w}}{\norm{\vb{w}}} \]

4. Возьмём любую точку \(\vb{x}_0\) на заборе. Для неё уравнение забора даёт

   \[ \vb{w}\T\vb{x}_0 = -w_0 \]

5. Расстояние от \(\vb{x}\) до забора — проекция вектора \(\vb{x} - \vb{x}_0\) на единичную нормаль. Подставим шаги 3 и 4:

   \[ \begin{aligned} \vb{w}^{*\mathsf{T}}(\vb{x} - \vb{x}_0) &= \frac{\vb{w}\T\vb{x} - \vb{w}\T\vb{x}_0}{\norm{\vb{w}}} \\[4pt] &= \frac{\vb{w}\T\vb{x} + w_0}{\norm{\vb{w}}} \end{aligned} \]

   Точка \(\vb{x}_0\) исчезла: какую ни возьми, ответ один.

Знак \(d\) говорит, по какую сторону забора стоит точка, а модуль — как далеко она от него.

Проверим на числах, которые в этом уроке встретятся ещё дважды. Забор \(x_1 - x_2 = 0\), то есть \(\vb{w} = (1, -1)\) и \(w_0 = 0\). Точка \(\vb{x} = (1, 2)\):

Точка стоит в 0.71 от забора, на стороне, противоположной стрелке. В виджете ниже это стартовое положение.

Один тест на правильность: знак произведения t·a

Стрелка задаёт сторону «плюс». Теперь добавим данные: у каждой точки \(\vb{x}_i\) есть target \(t_i\). Слайд 54 лекции 2 кодирует классы как \(+1\) и \(-1\) («Let's code the perceptron output as +1/-1»). Перцептрон считает активацию \(a_i = \vb{w}\T\vb{x}_i + w_0\) и отвечает её знаком, \(\sign(a_i)\); в конспекте этот ответ обозначен \(\hat y_i\).

Зачем \(\pm 1\), а не 0 и 1? Чтобы правильность ответа проверялась одним умножением. Перебери четыре случая.

Слайд 54 говорит то же двумя строчками: «If an output which should be +1 is misclassified then \(\vb{w}\T\vb{x} + w_0 \lt 0\)» и «For an output with -1 we have the opposite». Это вторая и четвёртая строки таблицы.

Точка классифицирована верно тогда и только тогда, когда \(t_i\,a_i \gt 0\).

Чем измерить ошибку: функция D

Теперь нужна error function: одно число, которое говорит, насколько плохо стоит забор, и которое можно уменьшать по градиенту.

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

Вторая мысль — спросить у каждой ошибочной точки не «ты ошиблась?», а «далеко ли тебе до своей стороны?». Расстояние меняется плавно. Для ошибочной точки \(t_i\,a_i \lt 0\), значит \(-t_i\,a_i\) — положительное число, пропорциональное её расстоянию до забора. Сложим такие числа по всем ошибочным точкам.

Слайд 54 лекции 2 с этого и начинает: «the error function the Hebbian rule is minimizing is the distance of misclassified points from the decision boundary». А про саму \(D\) говорит коротко: «non negative and proportional to the distance of the misclassified points». Если развернуть эту фразу, получатся три свойства (в конспекте они на стр. 117).

• \(D \ge 0\): каждое слагаемое \(-t_i\,a_i\) положительно.
• \(D = 0\), когда ошибочных точек нет: сумма пуста.
• \(D\) тем больше, чем больше ошибочных точек и чем дальше они забрались на чужую сторону.

Теперь сравним обоих кандидатов на одном опыте. Возьмём забор с рис. 2 и будем двигать его параллельно самому себе: стрелка \(\vb{w} = (1, 1)\) прежняя, меняется только \(w_0\). Для каждого положения посчитаем и число ошибочных точек, и \(D\).

Градиент D — это и есть правило Хебба

Дальше та же механика, что в уроке 13: взять производные и шагнуть против них. Разница одна: \(D\) устроена так просто, что градиент пишется сразу, без backpropagation.

1. Функция ошибки. Множество \(M\) считаем замороженным: оно посчитано для текущих весов.

   \[ D = -\sum_{i \in M} t_i\,(\vb{w}\T\vb{x}_i + w_0) \]

2. Производная по \(\vb{w}\). В скобке от \(\vb{w}\) зависит только \(\vb{w}\T\vb{x}_i\), и его производная равна \(\vb{x}_i\):

   \[ \pd{D}{\vb{w}} = -\sum_{i \in M} t_i\,\vb{x}_i \]

3. Производная по \(w_0\) ещё проще: производная скобки равна 1.

   \[ \pd{D}{w_0} = -\sum_{i \in M} t_i \]

4. Gradient descent: шаг против градиента. Два минуса дают плюс:

   \[ \vb{w} \leftarrow \vb{w} + \eta \sum_{i \in M} t_i\,\vb{x}_i \] \[ w_0 \leftarrow w_0 + \eta \sum_{i \in M} t_i \]

   Это batch-версия: один шаг учитывает все ошибочные точки сразу. Он толкает их в нужную сторону, но не обещает, что все они перейдут забор за один раз (конспект на стр. 118 здесь оптимистичнее, чем следует).

5. Stochastic gradient descent берёт из суммы одно слагаемое — одну ошибочную точку \(i\) — и шагает сразу:

   \[ \begin{pmatrix} \vb{w}^{k+1} \\ w_0^{k+1} \end{pmatrix} = \begin{pmatrix} \vb{w}^{k} \\ w_0^{k} \end{pmatrix} + \eta \begin{pmatrix} t_i\,\vb{x}_i \\ t_i \end{pmatrix} \]

6. Вспомним bias trick: \(w_0\) — это вес при входе \(x_0 = 1\). На слайде это второе равенство: в нижней строке вместо \(t_i\) написано \(t_i \cdot x_0\). Тогда нижняя строка — то же правило, что и верхняя, и для каждого веса \(w_j\), включая \(w_0\):

   \[ \Delta w_j = \eta\, x_j\, t \]

   Это Hebbian learning со слайда 11 лекции 2 (там индекс входа — \(i\), а \(k\) — номер шага), применённое только к ошибочным точкам.

Правило Hebbian learning — это stochastic gradient descent на функции \(D(\vb{w}, w_0)\): одна ошибочная точка, один шаг.

Что делает один шаг

Вернёмся к забору \(x_1 - x_2 = 0\) и точке \(\vb{x} = (1, 2)\). Пусть её \(t = +1\). Активация \(a = -1\), значит \(t\,a = -1 \le 0\): ошибка. Шаг с \(\eta = 0.5\):

Новая активация положительна, точка перешла на свою сторону:

Точка с \(t = +1\) тянет стрелку к себе, точка с \(t = -1\) отталкивает её от себя. В обоих случаях произведение \(t_i\,a_i\) этой точки растёт, и легко посчитать, на сколько:

В примере: \(-1 + 0.5 \cdot (1^2 + 2^2 + 1) = 2\). Прибавка всегда положительна, но её может не хватить, чтобы перейти через ноль. К тому же шаг ради одной точки может вытолкнуть на чужую сторону другие. Поэтому по данным ходят кругами, пока за целый проход не случится ни одного исправления.

К этому месту в конспекте приложен рис. 14 (стр. 120): линейная регрессия, по осям два её параметра. Batch gradient descent идёт к минимуму гладкой линией, SGD — ломаной вокруг неё. Подпись обещает «faster but noisier convergence». Точнее так: один шаг SGD стоит одного примера вместо \(N\), поэтому на единицу вычислений он продвигается дальше. Зато каждый шаг шумный, и при постоянном \(\eta\) траектория продолжает дрожать около минимума. Подробности — в уроке 13.

Весь алгоритм целиком — это Listing 1 со стр. 121, с двумя уточнениями: стартовать можно и с нулей, а проверка нестрогая.

w, w0 ← старт (слайд 12: нули)
выбрать η > 0
повторять проходы по данным:
  для каждой пары (x_i, t_i):
    a_i ← wᵀx_i + w0
    если t_i · a_i ≤ 0:
      w  ← w  + η · t_i · x_i
      w0 ← w0 + η · t_i
стоп: проход без исправлений

Когда забор перестаёт качаться

В тренажёре были оба исхода: на двух облаках забор замер, на XOR и с перебежчиком в чужом облаке — нет. Это не особенность примеров, а теорема.

Теорема уже встречалась в уроке 7, вместе с двумя вопросами со слайда 12 лекции 2. Теперь на них можно ответить на языке множества \(M\) и функции \(D\). Возьмём оттуда же OR в кодировке \(\pm 1\), старт \(\vb{w} = [0\ 0\ 0]\), \(\eta = 0.5\), и допишем к знакомой таблице столбец \(D\).

«Does the procedure always converge?» Нет: только на разделимых данных. Остановка означает, что за целый проход ни одна точка не дала \(t_i\,a_i \le 0\), то есть \(M\) пусто. OR разделим — три исправления, и второй проход идёт уже без ошибок. На XOR разделяющего забора нет, и \(M\) не пустеет никогда: четыре исправления возвращают веса в \([0\ 0\ 0]\), и всё повторяется по кругу.

«Does it always converge to the same sets of weights?» Тоже нет. Разделяющих заборов бесконечно много, у каждого \(D = 0\), и алгоритм останавливается на первом, который ему попался. Тот же OR со старта \((1, -1, 0.5)\) заканчивается в \((1, 1, 0.5)\), а не в \((0.5, 0.5, 0.5)\). А если начать с нулей и показать точки в обратном порядке, хватит одного исправления вместо трёх. В тренажёре то же видно по кнопке «Случайный старт»: забор каждый раз замирает в новом положении.

Чего теорема не обещает

• Лучший забор. Алгоритм не знает слова «отступ» (margin): забор может встать вплотную к точкам.
• Быстрый ответ. «Конечное число» бывает большим, если классы почти соприкасаются.
• Разумное поведение на неразделимых данных. Не «забор с наименьшим числом ошибок», а вечное качание. На практике число проходов ограничивают.
• Скрытые слои. У скрытого нейрона нет своего target, а у ступеньки нет наклона. Слайд 16 лекции 2 говорит об этом прямо: «Unfortunately Hebbian learning does not work any more». Отсюда гладкие активации и backpropagation. Поэтому фразу конспекта со стр. 114, что backpropagation — «a generalization of the Perceptron rule», не стоит понимать буквально: общая у них идея шага против градиента, а само правило перцептрона на скрытые слои не переносится.

Разгадка

Вернёмся к моторам из начала урока. Они не считали производных и всё же спускались по градиенту. Функция, по которой они спускались, — это \(D(\vb{w}, w_0)\): сумма расстояний ошибочных точек до забора, умноженная на \(\norm{\vb{w}}\). Её градиент по одной точке равен \(-t_i\,\vb{x}_i\): выражение настолько простое, что его исполняет мотор с потенциометром. Отдельный шаг может \(D\) и увеличить, как любой шаг SGD; но на разделимых данных вся цепочка шагов приводит к \(D = 0\). Правило из урока 7 и рецепт из уроков 13–15 — одно и то же: выбрать функцию ошибки, взять градиент, шагнуть против него.

Карта главы 2

Глава началась с одного нейрона и закончилась им же. В ней двенадцать уроков, и они складываются в три акта.

Акт первый: один нейрон проводит одну прямую и учится на ошибках, но XOR ему не по силам. Акт второй: нейроны собираются в Feed Forward Neural Network с гладкими активациями, и такая сеть способна приблизить любую непрерывную функцию. Акт третий: как найти веса. Он сводится к трём вопросам, и на каждый у перцептрона уже был свой игрушечный ответ.

Конспект на стр. 114 объясняет, зачем после всего этого возвращаться в 1957 год: в перцептроне уже были три идеи, на которых стоит обучение любой современной сети. Решение из взвешенной суммы входов. Исправление весов по ошибке на примере. Постепенное улучшение за много проходов по данным.