Линейные классификаторы и суррогатные функции потерь

Заметка о регуляризации завершила раздел о линейной регрессии моделью, которая предсказывает число и не гонится за шумом. Но многие целевые переменные — не числа, а классы: спам или нет, дефолт или погашение кредита, злокачественная опухоль или доброкачественная. Соблазнительный короткий путь — закодировать два класса как $-1$ и $+1$, обучить метод наименьших квадратов с гребневым штрафом и предсказывать знак полученного значения. В этой заметке мы покажем, почему метод наименьших квадратов с линейной моделью плохо справляется с этой задачей, что вместо неё должен минимизировать линейный классификатор и как в эту картину вписывается старейший алгоритм обучения — перцептрон. Введённые здесь функции потерь вернутся во всех остальных заметках раздела: логистическая (logistic loss) — в логистической регрессии, кусочно-линейная (hinge loss) — в методе опорных векторов.

Обозначения. Обучающая выборка — $(x_1, y_1), \dots, (x_n, y_n)$, где $x_i \in \mathbb R^d$, а метки $y_i \in \{-1, +1\}$. У линейного классификатора есть веса $w \in \mathbb R^d$ и свободный член (bias) $b$; его оценка (score) — $f(x) = \langle w, x\rangle + b$, а предсказание — $a(x) = \operatorname{sign} f(x)$. Отступ (margin) примера $i$ — это $M_i = y_i f(x_i)$. $[\,\cdot\,]$ равно 1, если условие в скобках выполнено, и 0 иначе; $\lVert w\rVert$ — евклидова норма. $\eta(x) = P(y = +1 \mid x)$ — вероятность положительного класса в точке $x$.

Почему не метод наименьших квадратов на метках?#

Возьмём шесть точек на прямой: отрицательные в $-3, -2, -1$ и положительные в $1, 2, 3$. Метод наименьших квадратов на метках $\pm 1$ даёт $f(x) = 3x/7$, и граница $f(x) = 0$ проходит через $x = 0$, ровно посередине между классами. Теперь добавим ещё три положительные точки в $20, 21, 22$ — настолько явно положительные, что никакое разумное правило не должно сдвинуться. Решение метода наименьших квадратов становится $f(x) = (27x - 37)/456$, граница смещается в $x = 37/27 \approx 1.37$, и положительная точка $x = 1$ теперь классифицируется неверно. Логистическая регрессия, предмет следующей заметки, на тех же девяти точках оставляет границу в $0$ без единой ошибки.

Причина становится видна, если записать функцию потерь через отступ. Поскольку $y^2 = 1$,

$$(y - f)^2 = y^2 (1 - y f)^2 = (1 - M)^2 .$$

Квадратичная ошибка — функция отступа, которая минимальна при $M = 1$ и растёт в обе стороны. Три далёкие точки при новом решении получают оценки примерно от $1.1$ до $1.2$, то есть отступы больше 1, и квадратичная ошибка штрафует их за то, что они слишком правы: чтобы опустить их оценки к 1, прямую нужно сделать более пологой, а это тянет границу вправо. У линейного классификатора функция потерь, наказывающая за большие положительные отступы, позволяет лёгким точкам сдвигать границу; функции потерь ниже за них никогда не наказывают.

Гиперплоскость делит пространство#

Множество $\{x : \langle w, x\rangle + b = 0\}$ — гиперплоскость: прямая на плоскости, плоскость в трёхмерном пространстве. Классификатор относит одну её сторону к $+1$, а другую к $-1$. Для двух точек $x, x'$ на гиперплоскости $\langle w, x - x'\rangle = 0$, поэтому $w$ перпендикулярен любому направлению внутри неё: $w$ — вектор нормали, и он смотрит в положительную сторону.

Расстояние до границы. Запишем любую точку как $x = x_\perp + r\, w/\lVert w\rVert$, где $x_\perp$ — её проекция на гиперплоскость, а $r$ — расстояние со знаком вдоль единичной нормали. Поскольку $\langle w, x_\perp\rangle + b = 0$,

$$f(x) = \langle w, x_\perp\rangle + b + r \frac{\langle w, w\rangle}{\lVert w\rVert} = r \lVert w\rVert, \qquad r = \frac{\langle w, x\rangle + b}{\lVert w\rVert} .$$

Оценка — это расстояние со знаком до границы, измеренное в единицах $1/\lVert w\rVert$. Умножение $w$ и $b$ на одну и ту же положительную константу меняет оценки, но не меняет ни границу, ни предсказания, поэтому у линейного классификатора есть одна лишняя степень свободы; регуляризация её устранит. Свободный член можно убрать, дописав к каждому $x$ постоянный признак $1$, а к $w$ — $b$; так это сделано в коде ниже.

Разобранный пример. При $w = (3, 4)$ и $b = -5$ граница — прямая $3x_1 + 4x_2 = 5$, и $\lVert w\rVert = 5$. У точки $x = (3, 1)$ оценка $9 + 4 - 5 = 8$, то есть она лежит на положительной стороне на расстоянии $8/5 = 1.6$. Её проекция на прямую — $x - (8/25)\, w = (2.04, -0.28)$, и действительно, $3 \cdot 2.04 + 4 \cdot (-0.28) = 5$.

Рисунок

Линейный классификатор: граница, нормаль и отступ

Отступ#

Отступ $M_i = y_i(\langle w, x_i\rangle + b)$ объединяет метку и оценку в одно число. Его знак говорит, верно ли классифицирован пример; его величина, делённая на $\lVert w\rVert$, — расстояние до границы, то есть мера уверенности. На рисунке у ближайшей к границе из верно классифицированных точек $M = 0.9$, а у точки класса $-1$, лежащей глубоко на положительной стороне, $M = -5.5$. Доля ошибок на обучении — доля неположительных отступов:

$$\frac1n \sum_{i=1}^n [M_i \le 0] ,$$

где $M_i = 0$, точка ровно на границе, считается ошибкой. Функция $[M \le 0]$ — это функция потерь 0–1 (0–1 loss), записанная как функция отступа.

Почему число ошибок нельзя минимизировать напрямую#

Доля ошибок — естественная целевая функция, но использовать её нельзя по двум причинам.

• Нет градиента. Как функция от $(w, b)$ она кусочно-постоянна: малое изменение весов либо ничего не меняет, либо перебрасывает одну точку через границу. Её градиент равен нулю почти всюду и не определён в точках скачков, так что градиентному спуску не за чем следовать.
• Вычислительная сложность. Найти гиперплоскость с наименьшим числом ошибок на обучении — NP-трудная задача, когда классы перекрываются (Höffgen, Simon and Van Horn, 1995), и даже найти такую, у которой число ошибок не более чем в константу раз больше наилучшего, трудно (Ben-David, Eiron and Long, 2003). Прост только разделимый случай: гиперплоскость с $y_i(\langle w, x_i\rangle + b) \ge 1$ для всех $i$ — допустимая точка задачи линейного программирования, и её находят за полиномиальное время.

При этом то, что оценивает доля ошибок, — правильная цель. Её теоретический аналог, математическое ожидание функции потерь 0–1, минимизирует байесовский классификатор (Bayes classifier), который предсказывает более вероятный класс, $\operatorname{sign}(2\eta(x) - 1)$, как указано в таблице других функций потерь и других целей. Вопрос в том, как прийти к нему вычислением, которое работает.

Суррогатные функции потерь: верхние оценки, которые можно минимизировать#

Если $\tilde L(M) \ge [M \le 0]$ при всех $M$, то

$$\frac1n \sum_{i=1}^n [M_i \le 0] \;\le\; \frac1n \sum_{i=1}^n \tilde L(M_i) .$$

Обычно выбирают одну из следующих функций:

$$\begin{aligned} \text{логистическая:} \quad & \tilde L(M) = \log_2\big(1 + e^{-M}\big), \\ \text{кусочно-линейная:} \quad & \tilde L(M) = \max(0,\, 1 - M), \\ \text{экспоненциальная:} \quad & \tilde L(M) = e^{-M}, \\ \text{квадрат кусочно-линейной:} \quad & \tilde L(M) = \max(0,\, 1 - M)^2 . \end{aligned}$$

Логистическую функцию потерь обычно записывают с натуральным логарифмом, $\log(1 + e^{-M})$. Эта версия равна $\log 2 \approx 0.69$ при $M = 0$ и вблизи нуля не является верхней оценкой; деление на $\log 2$, как выше, делает её верхней оценкой и никак не меняет точку минимума.

Оценка ограничивает долю ошибок сверху, но не следует за ней. С этой функцией потерь у отступов $(-0.1, 3)$ средняя суррогатная потеря $0.57$ и одна ошибка из двух, а у отступов $(0.1, 0.5)$ — $0.81$ и ни одной ошибки.

Рисунок

Функция потерь 0–1 и её выпуклые верхние оценки

При $M = -1$, на одну единицу по неверную сторону, четыре функции потерь равны $1.89$, $2$, $2.72$ и $4$; при $M = 2$, при уверенно верном ответе, — $0.18$, $0$, $0.14$ и $0$. Квадратичная ошибка $(1 - M)^2$ из начального примера тоже ограничивает ступеньку сверху, но это единственная кривая на рисунке, которая справа снова растёт. Остальные различия важны на практике:

Функция потерь	Выпуклая	Гладкая	Ноль для уверенно верных ответов	Рост при $M \to -\infty$	Где используется
логистическая	да	да	нет, лишь стремится к 0	линейный	логистическая регрессия
кусочно-линейная	да	нет, излом при $M = 1$	да, при $M \ge 1$	линейный	метод опорных векторов
экспоненциальная	да	да	нет	экспоненциальный	AdaBoost
квадрат кусочно-линейной	да	один раз дифференцируема	да, при $M \ge 1$	квадратичный	LinearSVC из scikit-learn (функция потерь по умолчанию)
квадратичная ошибка	да	да	нет, снова растёт при $M > 1$	квадратичный	метод наименьших квадратов на метках $\pm 1$

Выпуклость делает их минимизируемыми. Каждый отступ $M_i = y_i(\langle w, x_i\rangle + b)$ линеен по $(w, b)$, а выпуклая функция от линейной выпукла. Среднее выпуклых функций выпукло, поэтому каждый локальный минимум эмпирического суррогатного риска глобален и градиентные методы к нему сходятся. Гладкость определяет, какие методы применимы: градиентный спуск и метод Ньютона для логистической функции потерь, субградиенты или переформулировка задачи для кусочно-линейной.

Рост слева определяет устойчивость. Точка с неверной меткой находится при большом отрицательном отступе. Линейные функции потерь штрафуют её пропорционально тому, насколько она неверна, экспоненциальная — экспоненциально, так что одна плохая метка может доминировать в сумме; в этом известная слабость AdaBoost на зашумлённых метках (Hastie, Tibshirani and Friedman, 2009, Section 10.6). Экспоненциальная функция потерь вернётся в заметке о градиентном бустинге.

Что оценивает каждая суррогатная функция#

В отдельной точке $x$ с $\eta = \eta(x)$ оценка $f$ несёт ожидаемую суррогатную потерю $\eta \tilde L(f) + (1 - \eta) \tilde L(-f)$, поскольку метка равна $+1$ с вероятностью $\eta$. Минимизация по $f$ даёт оценку, которую выдавала бы идеально гибкая модель, обученная на неограниченном объёме данных. Для логистической функции потерь с натуральным логарифмом $\frac{d}{df}\log(1 + e^{-f}) = -(1 - \sigma(f))$, где $\sigma(f) = 1/(1 + e^{-f})$, поэтому производная ожидаемой потери равна

$$-\eta\,\big(1 - \sigma(f)\big) + (1 - \eta)\, \sigma(f) = \sigma(f) - \eta = 0 \quad\Longrightarrow\quad f^* = \log\frac{\eta}{1 - \eta} .$$

Остальные строки получаются так же (Hastie, Tibshirani and Friedman, 2009, Table 12.1); строку кусочно-линейной функции выводит заметка о методе опорных векторов.

Функция потерь	Точка минимума $f^*(\eta)$	При $\eta = 0.8$	Восстанавливает $\eta$?
логистическая	$\log\frac{\eta}{1-\eta}$, логарифм шансов	$1.386$	да
экспоненциальная	$\frac12 \log\frac{\eta}{1-\eta}$	$0.693$	да
кусочно-линейная	$\operatorname{sign}(2\eta - 1)$	$1$	нет
квадрат кусочно-линейной, квадратичная ошибка	$2\eta - 1$	$0.6$	да, на $[-1, 1]$

В каждой строке знак совпадает со знаком $2\eta - 1$, поэтому каждая суррогатная функция, минимизированная по всем функциям, даёт байесовский классификатор. Это свойство называется калиброванностью для классификации (classification calibration), и для выпуклой суррогатной функции оно выполняется ровно тогда, когда функция потерь дифференцируема в $0$ и её производная там отрицательна (Bartlett, Jordan and McAuliffe, 2006; Zhang, 2004). Строки различаются тем, что ещё они сохраняют. Точка минимума кусочно-линейной функции равна $\pm 1$ при любом $\eta$, поэтому оценка, обученная с ней, говорит, по какую сторону лежит точка, и ничего не говорит о том, насколько эта сторона вероятна; точка минимума логистической функции — сам логарифм шансов (log-odds), из которого $\eta = \sigma(f^*)$. Экспоненциальная и квадратичные строки тоже обращаются, через другие связи: $\eta = \sigma(2f^*)$ и $\eta = (f^* + 1)/2$; при оценках из таблицы обе дают $0.8$.

Строка квадратичной ошибки объясняет и пример из начала заметки. По всем функциям квадратичная ошибка на метках $\pm 1$ калибрована для классификации и даже восстанавливает $\eta$. Подвела линейная подгонка: прямая не может всюду следовать за $2\eta - 1$, и квадратичная ошибка тратит её наклон на далёкие точки, которые и так классифицированы верно. Логистическая функция потерь — отправная точка следующей заметки.

Перцептрон: стохастический градиентный спуск при нулевом отступе#

Перцептрон (perceptron) Розенблатта (1958) — старейшее правило обучения линейного классификатора. Он перебирает примеры по одному и исправляет веса только после ошибки:

$$\text{если } y_i(\langle w, x_i\rangle + b) \le 0: \qquad w \leftarrow w + y_i x_i, \quad b \leftarrow b + y_i .$$

Это стохастический градиентный спуск по функции потерь перцептрона (perceptron loss) $\max(0, -M)$ с шагом 1. Градиент $\max(0, -y_i(\langle w, x_i\rangle + b))$ по $w$ равен $-y_i x_i$ для неверно классифицированного примера и $0$ для верного; при $M_i = 0$ у функции потерь излом, и правило берёт субградиент $-y_i x_i$. Если веса стартуют с нуля, величина шага не важна: каждая итерация тогда — сумма векторов $\pm x_i$, и другой шаг лишь масштабирует её, что не меняет ни одного предсказания. Функция потерь перцептрона выпукла, но не ограничивает функцию потерь 0–1 сверху (при $M = 0$ она равна $0$). Кусочно-линейная функция отличается от неё сдвигом к $1 - M$: она штрафует и верно классифицированные точки с отступом меньше 1 и, как показывает заметка о методе опорных векторов, отодвигает границу от данных.

Разобранный пример. Четыре точки, свободный член — третья координата: $x_1 = (2, 1)$ и $x_2 = (1, 3)$ положительные, $x_3 = (-1, 1)$ и $x_4 = (0, -2)$ отрицательные. Начнём с $w = (0, 0)$, $b = 0$ и пройдём точки по порядку:

Шаг	Точка	Отступ до шага	Обновление	$w$ после	$b$ после
1	$x_1$, $y = +1$	$0$	прибавить $x_1$	$(2, 1)$	$1$
2	$x_2$, $y = +1$	$2 + 3 + 1 = 6$	нет	$(2, 1)$	$1$
3	$x_3$, $y = -1$	$-(-2 + 1 + 1) = 0$	вычесть $x_3$	$(3, 0)$	$0$
4	$x_4$, $y = -1$	$-(0 + 0 + 0) = 0$	вычесть $x_4$	$(3, 2)$	$-1$

На втором проходе отступы при $3x_1 + 2x_2 - 1$ равны $7, 8, 2, 5$, все положительны, и алгоритм останавливается после трёх обновлений.

Почему он останавливается на разделимых данных. Пусть некоторый единичный вектор $u$ разделяет данные с отступом $\gamma > 0$, то есть $y_i \langle u, x_i\rangle \ge \gamma$ для всех $i$, и $\lVert x_i\rVert \le R$ (свободный член включён в $x$, поэтому оба условия выполняются в расширенном пространстве). Начнём с $w_0 = 0$ и обозначим через $w_k$ веса после $k$ обновлений. Каждое обновление вызвано точкой с $y\langle w_k, x\rangle \le 0$, поэтому

$$\langle w_{k+1}, u\rangle = \langle w_k, u\rangle + y\langle x, u\rangle \ge \langle w_k, u\rangle + \gamma, \qquad \lVert w_{k+1}\rVert^2 = \lVert w_k\rVert^2 + 2y\langle w_k, x\rangle + \lVert x\rVert^2 \le \lVert w_k\rVert^2 + R^2 .$$

После $k$ обновлений $\langle w_k, u\rangle \ge k\gamma$ и $\lVert w_k\rVert \le \sqrt k\, R$, и по неравенству Коши–Буняковского $k\gamma \le \langle w_k, u\rangle \le \lVert w_k\rVert \le \sqrt k R$. Следовательно,

$$k \le \Big(\frac{R}{\gamma}\Big)^2 ,$$

это оценка Новикова (1962). Она не зависит ни от числа точек, ни от размерности, а только от ширины зазора между классами относительно разброса данных. Это оценка худшего случая: на 200 случайных точках на плоскости с зазором не меньше $0.1$ по обе стороны от прямой через начало координат оценка равна $253$ обновлениям, а перцептрону нужно 4 (раздел «Код»).

Когда классы перекрываются, какая-то точка всегда классифицирована неверно, обновления никогда не прекращаются, и итоговые веса зависят от того, где прервали запуск. Усреднение векторов весов по всем шагам или голосование между ними даёт устойчивый классификатор с похожими гарантиями (Freund and Schapire, 1999), но стандартный ответ — минимизировать выпуклую суррогатную функцию потерь с регуляризатором.

Линейная разделимость#

Обучающая выборка линейно разделима (linearly separable), если какая-нибудь гиперплоскость классифицирует её целиком верно. Шаблон XOR — положительные точки в $(0, 0)$ и $(1, 1)$, отрицательные в $(1, 0)$ и $(0, 1)$ — не разделим: любая прямая, которая оставляет обе положительные точки с одной стороны, оставляет там и отрицательную. Минский и Пейперт (1969) сделали это ограничение одиночного перцептрона знаменитым. Его исправляет новый признак: если добавить $x_1 x_2$, четыре точки становятся разделимыми в трёх измерениях. Добавить признаки вручную, неявно через ядра или выучить их в нейронной сети — вот три способа, которыми курс выходит за пределы прямых.

В больших размерностях возникает обратная проблема: разделимо почти всё. Ковер (1965) подсчитал, сколько разметок $n$ точек общего положения в $\mathbb R^d$ может реализовать аффинная гиперплоскость. Если метки — случайные подбрасывания монеты, вероятность того, что они линейно разделимы, равна

$$P(n, d) = \frac{1}{2^{n-1}} \sum_{k=0}^{d} \binom{n-1}{k} .$$

При $n \le d + 1$ она равна 1 — разделима любая разметка; при $n = 2(d + 1)$ она равна ровно $1/2$; дальше она быстро падает. В размерности $d = 5$ формула даёт $1$, $0.5$ и $0.072$ для 6, 12 и 18 точек, а 400 случайных разметок на каждый размер дают $1$, $0.48$ и $0.065$ (раздел «Код»). Поскольку $P(n, d)$ убывает с ростом $n$, классификатор, у которого параметров не меньше половины числа примеров ($d + 1$ вместе со свободным членом, то есть $n \le 2(d + 1)$), разделяет случайные метки с вероятностью не меньше $1/2$, а при $n \le d + 1$ — всегда. Поэтому нулевая ошибка на обучении ничего не доказывает: её достигают и чисто шумовые метки; модель мешка слов с десятками тысяч признаков находится ровно в этом режиме. Это классификационное лицо переобучения из заметки о валидации.

Что добавляет регуляризатор#

На разделимых данных суррогатные функции потерь ведут себя плохо двумя разными способами. Логистическая и экспоненциальная продолжают убывать при увеличении $w$ вдоль любого разделяющего направления, поэтому у них нет точки минимума и веса уходят на бесконечность; кусочно-линейная и её квадрат обращаются в ноль, как только все отступы превышают 1, и тогда любое большее кратное $w$ — столь же хорошее решение. Гребневый штраф из заметки о регуляризации,

$$\frac1n \sum_{i=1}^n \tilde L\big(y_i(\langle w, x_i\rangle + b)\big) + \lambda \lVert w\rVert^2 ,$$

исправляет и то и другое. Целевая функция теперь строго выпукла по $w$ и неограниченно растёт при $\lVert w\rVert \to \infty$, поэтому у неё ровно одна точка минимума по $w$, и она конечна. У штрафа есть и геометрический смысл: при условии на отступы $M_i \ge 1$ расстояние от границы до ближайшей точки не меньше $1/\lVert w\rVert$, так что уменьшение $\lVert w\rVert$ при отступах не меньше 1 максимизирует зазор между классами. Этот компромисс — метод опорных векторов. Для логистической функции потерь у штрафа есть и третье прочтение — гауссовское априорное распределение на веса, которое развивает следующая заметка; штраф лассо тоже работает и, как в регрессии, обнуляет веса.

Что изменилось#

	Метод наименьших квадратов на метках $\pm 1$	Линейный классификатор с суррогатной функцией потерь
Потеря на одном примере	$(1 - M)^2$	выпуклая верхняя оценка $[M \le 0]$: логистическая, кусочно-линейная, экспоненциальная
Уверенно верные ответы	штрафуются при $M > 1$	бесплатны или почти бесплатны
Смысл оценки	$2\eta - 1$, через функцию потерь, которая гонится и за далёкими точками	логарифм шансов (логистическая), только сторону (кусочно-линейная)
Разделимые данные	единственное решение, которое может ошибаться	нулевая потеря в пределе (логистическая, экспоненциальная) или точно (кусочно-линейная); регуляризатор выбирает одно решение
Обучение	нормальные уравнения	градиентные методы; перцептрон как SGD при нулевом отступе

Ограничения#

• Граница — гиперплоскость. Взаимодействия вроде XOR не видны без новых признаков.
• Суррогатная функция — не метрика. Минимизация логистической или кусочно-линейной функции потерь ограничивает долю ошибок, но важной величиной может быть полнота при фиксированной доле ложных тревог или стоимость ошибок; заметка о метриках классификации разделяет эти две вещи.
• Оценки — не вероятности. Оптимальная оценка превращается в вероятность только через известную связь: $\sigma(f^*)$ для логистической функции потерь, $\sigma(2f^*)$ для экспоненциальной, $(f^* + 1)/2$ для квадратичных; у кусочно-линейной такой связи нет. Даже тогда вероятности приближённы при конечной выборке и линейной модели, которая может не содержать $f^*$.
• Выбросы всё равно тянут. Линейный рост мягче экспоненциального, но точка с неверной меткой далеко по неверную сторону всё равно даёт наибольшее слагаемое суммы.
• Гарантии относятся к обучающей выборке. Нулевая ошибка на обучении и малая суррогатная потеря мало что говорят, когда число признаков приближается к числу примеров, как показывает подсчёт Ковера.

Что нужно запомнить#

• Линейный классификатор предсказывает $\operatorname{sign}(\langle w, x\rangle + b)$; $w$ — нормаль к границе, а $(\langle w, x\rangle + b)/\lVert w\rVert$ — расстояние со знаком до неё.
• Отступ $M = y(\langle w, x\rangle + b)$ положителен при верном ответе и измеряет уверенность. Квадратичная ошибка на метках $\pm 1$ равна $(1 - M)^2$ и наказывает за большие отступы.
• У функции потерь 0–1 нет полезного градиента, и её минимизация NP-трудна; выпуклые верхние оценки (логистическая, кусочно-линейная, экспоненциальная, квадрат кусочно-линейной) ограничивают долю ошибок и поддаются минимизации.
• Все эти суррогатные функции ведут к байесовскому классификатору. Логистическая к тому же восстанавливает логарифм шансов, экспоненциальная и квадратичные восстанавливают $\eta$ через другие связи, кусочно-линейная — только сторону.
• Перцептрон — это SGD по $\max(0, -M)$; на разделимых данных он делает не больше $(R/\gamma)^2$ ошибок, а на перекрывающихся никогда не останавливается.
• В больших размерностях разделимость — обычное дело ($P = 1/2$ при $n = 2(d + 1)$ случайных метках); регуляризатор делает решение единственным и конечным, а с кусочно-линейной функцией потерь максимизирует отступ.

Код#

Метод наименьших квадратов против функции потерь для классификации, суррогатные функции потерь и их точки минимума, перцептрон и его оценка, подсчёт Ковера:

import numpy as np
from math import comb
from scipy.optimize import linprog, minimize_scalar
from sklearn.linear_model import LogisticRegression

rng = np.random.default_rng(0)

# 1. МНК на метках ±1: три далёкие, явно положительные точки сдвигают границу
x = np.array([-3, -2, -1, 1, 2, 3, 20, 21, 22.])
y = np.r_[-np.ones(3), np.ones(6)]
b, w = np.linalg.lstsq(np.c_[np.ones_like(x), x], y, rcond=None)[0]
print(round(-b / w, 4), int((np.sign(b + w * x) != y).sum()))            # 1.3704 1: положительная точка x = 1 потеряна
lr = LogisticRegression().fit(x[:, None], y)
print(round(-lr.intercept_[0] / lr.coef_[0, 0], 4), int((lr.predict(x[:, None]) != y).sum()))   # -0.0002 0

# 2. суррогатные функции потерь при отступах -1, 0 и 2
M = np.array([-1, 0, 2.])
losses = {'logistic': np.log2(1 + np.exp(-M)), 'hinge': np.maximum(0, 1 - M), 'exponential': np.exp(-M),
          'squared hinge': np.maximum(0, 1 - M) ** 2, 'squared error': (1 - M) ** 2}
for name, v in losses.items():
    print(name, v.round(3))
# logistic [1.895 1. 0.183] | hinge [2. 1. 0.] | exponential [2.718 1. 0.135]
# squared hinge [4. 1. 0.] | squared error [4. 1. 1.]
# меньший суррогат не обязательно означает меньше ошибок: средняя логистическая потеря и доля ошибок для двух пар отступов
for pair in ([-0.1, 3], [0.1, 0.5]):
    print(np.log2(1 + np.exp(-np.array(pair))).mean().round(2), np.mean(np.array(pair) <= 0))   # 0.57 0.5 | 0.81 0.0

# 3. что оценивает каждая суррогатная функция: точка минимума eta L(f) + (1 - eta) L(-f) при eta = 0.8
eta = 0.8
for name, L in [('logistic', lambda m: np.log2(1 + np.exp(-m))), ('hinge', lambda m: max(0, 1 - m)),
                ('exponential', lambda m: np.exp(-m)), ('squared hinge', lambda m: max(0, 1 - m) ** 2)]:
    f = minimize_scalar(lambda f: eta * L(f) + (1 - eta) * L(-f), bounds=(-5, 5), method='bounded', options={'xatol': 1e-9}).x
    print(name, round(f, 3))
# logistic 1.386 (log 4) | hinge 1.0 | exponential 0.693 (log 2) | squared hinge 0.6

# 4. перцептрон на четырёх точках разобранного примера, затем на разделимом облаке против оценки Новикова
def perceptron(X, y, max_epochs=1000):
    Xb = np.c_[X, np.ones(len(X))]
    w, updates = np.zeros(Xb.shape[1]), 0
    for _ in range(max_epochs):
        mistakes = 0
        for xi, yi in zip(Xb, y):
            if yi * (w @ xi) <= 0:
                w, updates, mistakes = w + yi * xi, updates + 1, mistakes + 1
        if mistakes == 0:
            return w, updates
    return w, updates

print(perceptron(np.array([[2., 1], [1, 3], [-1, 1], [0, -2]]), np.array([1, 1, -1, -1])))   # (array([ 3.,  2., -1.]), 3)
u = np.array([0.6, 0.8])                       # разделяющее направление, через начало координат
X = rng.uniform(-1, 1, (2000, 2))
X = X[np.abs(X @ u) >= 0.1][:200]              # зазор не меньше 0.1 по обе стороны от прямой
y = np.sign(X @ u)
Xb = np.c_[X, np.ones(len(X))]                 # перцептрон учит и свободный член: работаем в расширенном пространстве
R, gamma = np.linalg.norm(Xb, axis=1).max(), (y * (Xb @ np.r_[u, 0])).min()
print(perceptron(X, y)[1], round((R / gamma) ** 2, 1))                   # 4 253.4: четыре обновления, оценка 253

# 5. Ковер: вероятность, что случайные метки на n точках общего положения в R^5 линейно разделимы
def separable(X, y):
    A = -y[:, None] * np.c_[X, np.ones(len(X))]     # y_i (w·x_i + b) >= 1 как A [w, b] <= -1
    return linprog(np.zeros(X.shape[1] + 1), A_ub=A, b_ub=-np.ones(len(X)), bounds=(None, None)).status == 0
d = 5
for n in (6, 12, 18):
    share = np.mean([separable(rng.normal(size=(n, d)), rng.choice([-1., 1.], n)) for _ in range(400)])
    exact = sum(comb(n - 1, k) for k in range(d + 1)) / 2 ** (n - 1)
    print(n, share, round(exact, 4))
# 6 1.0 1.0 | 12 0.48 0.5 | 18 0.065 0.0717

Дальше#

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

Литература#

• F. Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408, 1958.
• A. B. J. Novikoff. On convergence proofs on perceptrons. Proceedings of the Symposium on the Mathematical Theory of Automata, 12, 615–622. Polytechnic Institute of Brooklyn, 1962.
• M. Minsky, S. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969.
• T. M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, EC-14(3), 326–334, 1965.
• K.-U. Höffgen, H. U. Simon, K. S. Van Horn. Robust trainability of single neurons. Journal of Computer and System Sciences, 50(1), 114–125, 1995.
• S. Ben-David, N. Eiron, P. M. Long. On the difficulty of approximately maximizing agreements. Journal of Computer and System Sciences, 66(3), 496–514, 2003.
• P. L. Bartlett, M. I. Jordan, J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473), 138–156, 2006.
• T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1), 56–85, 2004.
• Y. Freund, R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3), 277–296, 1999.
• C. Cortes, V. Vapnik. Support-vector networks. Machine Learning, 20(3), 273–297, 1995.
• J. Friedman, T. Hastie, R. Tibshirani. Additive logistic regression: a statistical view of boosting. The Annals of Statistics, 28(2), 337–407, 2000. (AdaBoost как минимизация экспоненциальной функции потерь.)
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Раздел 4.5 (разделяющие гиперплоскости и перцептрон), раздел 10.6 (функции потерь и устойчивость), раздел 12.3.2 и таблица 12.1 (функции потерь и их теоретические точки минимума).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Глава 9 (полупространства и перцептрон), раздел 12.3 (суррогатные функции потерь).
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций: лекция 4: линейная классификация (отступы и верхние оценки доли ошибок), лекция 5 (логистическая и кусочно-линейная функции потерь).