Метод опорных векторов

Заметка о линейных классификаторах заменила функцию потерь 0–1 выпуклыми суррогатами, а заметка о метриках классификации измерила, как ошибаются полученные классификаторы. Один вопрос остался открытым. Если два класса разделимы гиперплоскостью, разделяющих гиперплоскостей бесконечно много, у всех нулевая ошибка на обучении, и одна функция потерь на обучающей выборке не говорит, какую выбрать. Логистическая регрессия отвечает вероятностями, а метод опорных векторов (support vector machine, SVM) — геометрией: взять гиперплоскость, которая держится как можно дальше от ближайших обучающих точек (Boser, Guyon and Vapnik, 1992; Cortes and Vapnik, 1995). В этой заметке мы выводим это правило, распространяем его на перекрывающиеся классы и строим двойственную задачу. Она показывает, что решение зависит лишь от нескольких обучающих точек и только от скалярных произведений между ними. На втором факте строится следующая заметка.

Обозначения. Обучающие точки $x_1, \dots, x_n \in \mathbb R^d$ с метками $y_i \in \{-1, +1\}$. Линейный классификатор предсказывает $\operatorname{sign}(\langle w, x\rangle + b)$ с весами $w \in \mathbb R^d$ и смещением $b$; его оценка (score) — $f(x) = \langle w, x\rangle + b$. Как в заметке о линейных классификаторах, отступ объекта (margin) — это $M_i = y_i f(x_i)$: он положителен, когда $x_i$ классифицирована верно. Зазор гиперплоскости (margin) $\gamma$ — расстояние от гиперплоскости до ближайшей обучающей точки. $\lVert w \rVert$ — евклидова норма. Двойственные переменные — $\alpha_i$ и $\mu_i$.

Какую разделяющую прямую выбрать?#

Рисунок

Прямая с максимальным зазором и опорные векторы

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

Расстояние от точки $x$ до гиперплоскости $\langle w, x\rangle + b = 0$ равно

$$\operatorname{dist}(x) = \frac{\lvert \langle w, x\rangle + b \rvert}{\lVert w \rVert} :$$

для любой точки $x_0$ на гиперплоскости это расстояние — длина проекции $x - x_0$ на единичную нормаль $w / \lVert w \rVert$, то есть $\lvert\langle w, x - x_0\rangle\rvert / \lVert w\rVert$, а $\langle w, x_0\rangle = -b$. Для гиперплоскости, верно классифицирующей все точки, $\lvert f(x_i)\rvert = M_i$, поэтому её зазор равен $\gamma = \min_i M_i / \lVert w\rVert$.

Задача с жёстким зазором#

Умножение $w$ и $b$ на одно и то же положительное число не меняет ни классификатор, ни $\gamma$, поэтому один масштаб можно зафиксировать бесплатно. SVM фиксирует его так, чтобы у ближайших точек было $M_i = 1$: все точки удовлетворяют $M_i \ge 1$, а ближайшие — с равенством. Тогда $\gamma = 1/\lVert w\rVert$, полоса между гиперплоскостями $f(x) = -1$ и $f(x) = +1$ не содержит обучающих точек и имеет ширину $2/\lVert w\rVert$, а максимизировать зазор — значит минимизировать $\lVert w\rVert$. Возведение в квадрат и деление пополам делают целевую функцию гладкой:

$$\begin{aligned} &\min_{w,\, b}\ \tfrac12 \lVert w \rVert^2\\ &\text{subject to}\ \ y_i(\langle w, x_i\rangle + b) \ge 1, \quad i = 1, \dots, n . \end{aligned}$$

Это SVM с жёстким зазором (hard-margin SVM). Целевая функция строго выпукла по $w$, а ограничения линейны, поэтому для разделимых данных оптимальный $w$ единственен, а сама задача — задача квадратичного программирования (quadratic program), с которой справляются стандартные солверы.

Разобранный пример. Четыре точки: $A = (0, 0)$ и $B = (2, 0)$ с $y = -1$, $C = (1, 2)$ и $D = (3, 3)$ с $y = +1$. Отрицательные точки заполняют отрезок $x_2 = 0$, $0 \le x_1 \le 2$, а ближайшая к нему положительная точка — $C$, на расстоянии 2. Никакая разделяющая прямая не может быть дальше половины этого расстояния, 1, от обоих классов, и горизонтальная прямая $x_2 = 1$ этого достигает. В масштабе SVM это $w = (0, 1)$, $b = -1$: $M_A = M_B = M_C = 1$, $M_D = 2$, $\gamma = 1/\lVert w\rVert = 1$ и $\tfrac12\lVert w\rVert^2 = 0.5$. Три точки касаются полосы, $D$ — нет. Двойственная задача получит тот же ответ с другой стороны.

Когда классы перекрываются: переменные-штрафы#

Реальные классы перекрываются, и тогда никакой $w$ не удовлетворяет всем ограничениям $M_i \ge 1$. SVM с мягким зазором (soft-margin SVM; Cortes and Vapnik, 1995) позволяет каждой точке нарушить своё ограничение на величину штрафа (slack) $\xi_i \ge 0$ и платит $C$ за единицу штрафа:

$$\begin{aligned} &\min_{w,\, b,\, \xi}\ \tfrac12 \lVert w \rVert^2 + C \sum_{i=1}^n \xi_i\\ &\text{subject to}\ \ y_i(\langle w, x_i\rangle + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0 . \end{aligned}$$

Точка с $\xi_i = 0$ лежит по верную сторону от своего края полосы; $0 \lt \xi_i \lt 1$ означает, что точка внутри полосы, но ещё классифицирована верно; $\xi_i = 1$ — что она на гиперплоскости; $\xi_i \gt 1$ — что она по другую сторону от неё. Каждая неверно классифицированная точка вносит в $\sum_i \xi_i$ больше 1, поэтому суммарный штраф ограничивает число ошибок на обучении сверху. Константа $C \gt 0$ задаёт обменный курс между широкой полосой и малым числом нарушений: большое $C$ делает нарушения дорогими, малое $C$ допускает много нарушений, чтобы $\lVert w\rVert$ оставалась малой. На разделимых данных жёсткий зазор — предел при $C \to \infty$. На перекрывающихся данных он ничьим пределом не является: у ограничений жёсткого зазора нет ни одной допустимой точки, а большее $C$ лишь делает неизбежный штраф дороже.

Мягкий зазор — это кусочно-линейная функция потерь плюс L2#

При фиксированных $w$ и $b$ лучший штраф — наименьший допустимый: из $\xi_i \ge 1 - M_i$ и $\xi_i \ge 0$ получаем $\xi_i = \max(0, 1 - M_i)$. Подстановка убирает ограничения:

$$\min_{w,\, b}\ \ C \sum_{i=1}^n \max\big(0,\ 1 - y_i(\langle w, x_i\rangle + b)\big) + \tfrac12\lVert w\rVert^2 .$$

Первое слагаемое — это кусочно-линейная функция потерь (hinge loss) из заметки о линейных классификаторах, просуммированная по обучающей выборке; второе — гребневый штраф из заметки о регуляризации. Деление на $Cn$ даёт привычную форму «средняя потеря плюс $\lambda \lVert w\rVert^2$» с $\lambda = 1/(2Cn)$: большое $C$ — слабая регуляризация. Значит, SVM — не новый вид модели, а линейный классификатор, обученный с определённой суррогатной функцией потерь и L2-штрафом. Геометрия объясняет, почему именно эта пара естественна: штраф измеряет величину, обратную ширине полосы, а кусочно-линейная функция потерь штрафует только точки, которые в полосу заходят.

Вероятностный смысл у двух слагаемых разный. Штраф — это отрицательный логарифм гауссовского априорного распределения на $w$, как в MAP-оценке. А вот кусочно-линейная функция потерь не является отрицательным логарифмом правдоподобия. Условной модели $p(y \mid x) \propto e^{-C \max(0,\, 1 - y f(x))}$ нужно было бы, чтобы сумма $e^{-C\max(0,\,1 - f)} + e^{-C\max(0,\,1 + f)}$ была одинаковой для всех оценок $f$, а это не так: $2e^{-C}$ при $f = 0$ против $1 + e^{-2C}$ при $f = 1$. Для логистической функции потерь та же сумма в точности равна 1, поэтому логистическая регрессия выдаёт вероятности, а SVM — нет.

Что оценивает кусочно-линейная функция потерь, следует из рецепта раздела другие функции потерь — другие цели: минимизировать ожидаемую потерю отдельно в каждой точке $x$. При $\eta = P(Y = 1 \mid X = x)$ ожидаемая потеря оценки $f$ равна $\eta \max(0, 1 - f) + (1 - \eta)\max(0, 1 + f)$. На $[-1, 1]$ она равна $1 + (1 - 2\eta) f$, это прямая, а вне этого отрезка она только растёт. Поэтому минимум достигается при $f^* = +1$, если $\eta \gt 1/2$, и при $f^* = -1$, если $\eta \lt 1/2$: это знак байесовского классификатора и ничего больше (Lin, 2002), строка кусочно-линейной функции потерь в таблице раздела что оценивает каждый суррогат. При $\eta = 0.7$ и $\eta = 0.95$ кусочно-линейная функция потерь требует одной и той же оценки $+1$, а логистическая — логарифма шансов $0.85$ и $2.94$. SVM нацелен на верное решение и отбрасывает уверенность; когда нужны вероятности, их подгоняют потом по оценкам на отложенных данных, как в разделе о калибровке заметки о логистической регрессии (Platt, 1999).

Двойственная задача#

Структура решения видна в форме с ограничениями. Инструмент — двойственность Лагранжа (Boyd and Vandenberghe, 2004, глава 5). Запишем каждое ограничение в виде «нечто $\ge 0$»: $M_i - 1 + \xi_i \ge 0$ и $\xi_i \ge 0$. Дадим каждому множитель, $\alpha_i \ge 0$ и $\mu_i \ge 0$, и вычтем их из целевой функции:

$$\begin{aligned} L(w, b, \xi, \alpha, \mu) = {}&\tfrac12 \lVert w \rVert^2 + C \sum_i \xi_i\\ &- \sum_i \alpha_i \big(y_i(\langle w, x_i\rangle + b) - 1 + \xi_i\big) - \sum_i \mu_i \xi_i . \end{aligned}$$

Шаг 1: слабая двойственность. В любой допустимой точке $(w, b, \xi)$ обе вычитаемые суммы неотрицательны, поэтому $L$ не больше целевой функции. Следовательно, двойственная функция $g(\alpha, \mu) = \min_{w, b, \xi} L$ — нижняя оценка оптимального значения $p^*$ задачи SVM при любых $\alpha, \mu \ge 0$. Двойственная задача ищет лучшую нижнюю оценку, $d^* = \max_{\alpha, \mu \ge 0} g(\alpha, \mu) \le p^*$.

Шаг 2: сильная двойственность. Целевая функция выпукла, все ограничения аффинны, и задача допустима ($w = 0$, $b = 0$, $\xi_i = 1$ удовлетворяют всем ограничениям). Для таких задач выполнено уточнённое условие Слейтера, которое даёт $d^* = p^*$, причём двойственный оптимум достигается (Boyd and Vandenberghe, 2004, §5.2.3). Поэтому решение двойственной задачи решает и SVM.

Шаг 3: минимизируем $L$ по прямым переменным. $L$ — выпуклая квадратичная функция от $w$ и линейная от $b$ и от каждого $\xi_i$. Линейная функция имеет конечный минимум, только если её наклон равен нулю; иначе $g = -\infty$, что бесполезно как оценка. Приравниваем производные к нулю:

$$\begin{aligned} \frac{\partial L}{\partial w} &= w - \sum_i \alpha_i y_i x_i = 0 &&\Longrightarrow\ w = \sum_i \alpha_i y_i x_i ,\\ \frac{\partial L}{\partial b} &= -\sum_i \alpha_i y_i = 0 &&\Longrightarrow\ \sum_i \alpha_i y_i = 0 ,\\ \frac{\partial L}{\partial \xi_i} &= C - \alpha_i - \mu_i = 0 &&\Longrightarrow\ \mu_i = C - \alpha_i . \end{aligned}$$

Шаг 4: подставляем. При $\sum_i \alpha_i y_i = 0$ слагаемое с $b$ исчезает, при $C - \alpha_i - \mu_i = 0$ исчезают слагаемые с $\xi_i$, а $\sum_i \alpha_i y_i \langle w, x_i\rangle = \langle w, w\rangle$ по первому условию:

$$g(\alpha) = \tfrac12\lVert w\rVert^2 - \lVert w\rVert^2 + \sum_i \alpha_i = \sum_{i} \alpha_i - \tfrac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle .$$

Шаг 5: собираем ограничения. Условия $\mu_i = C - \alpha_i \ge 0$ и $\alpha_i \ge 0$ вместе дают $0 \le \alpha_i \le C$. Двойственная задача SVM с мягким зазором:

$$\begin{aligned} &\max_{\alpha}\ \sum_{i} \alpha_i - \tfrac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle\\ &\text{subject to}\ \ 0 \le \alpha_i \le C,\quad \sum_i \alpha_i y_i = 0 . \end{aligned}$$

Это вогнутая задача квадратичного программирования от $n$ переменных: матрица $(y_i y_j \langle x_i, x_j\rangle)$ — матрица Грама векторов $y_i x_i$ и потому положительно полуопределённая. Жёсткий зазор даёт ту же двойственную задачу без верхней границы $C$. Для дальнейшего важны две особенности. Данные входят только через скалярные произведения $\langle x_i, x_j\rangle$. А решение восстанавливается как $w = \sum_i \alpha_i y_i x_i$, так что классификатор равен

$$f(x) = \sum_{i} \alpha_i y_i \langle x_i, x\rangle + b ,$$

и это снова функция одних скалярных произведений.

Условия ККТ#

Сильная двойственность связывает прямое и двойственное решения. В оптимуме $p^* = d^* = g(\alpha) \le L(w, b, \xi, \alpha, \mu) \le p^*$, так что оба неравенства обращаются в равенства; второе заставляет каждое вычитаемое произведение быть нулём. Вместе со стационарностью из шага 3 и ограничениями это условия Каруша–Куна–Таккера (Karush–Kuhn–Tucker conditions, ККТ; Boyd and Vandenberghe, 2004, §5.5.3), необходимые, а для выпуклой задачи и достаточные условия оптимальности:

• стационарность: $w = \sum_i \alpha_i y_i x_i$, $\ \sum_i \alpha_i y_i = 0$, $\ \alpha_i + \mu_i = C$;
• прямая допустимость: $M_i \ge 1 - \xi_i$, $\ \xi_i \ge 0$;
• двойственная допустимость: $\alpha_i \ge 0$, $\ \mu_i \ge 0$;
• дополняющая нежёсткость (complementary slackness): $\alpha_i (M_i - 1 + \xi_i) = 0$, $\ \mu_i \xi_i = 0$.

Дополняющая нежёсткость говорит, что множитель может быть ненулевым, только если его ограничение активно (выполнено как равенство).

Разобранный пример, продолжение. Для четырёх точек у $D$ отступ $M_D = 2 \gt 1$, поэтому $\alpha_D = 0$. Стационарность даёт $w = -\alpha_A (0, 0) - \alpha_B (2, 0) + \alpha_C (1, 2) = (\alpha_C - 2\alpha_B,\ 2\alpha_C)$, и $w = (0, 1)$ требует $\alpha_C = \tfrac12$, $\alpha_B = \tfrac14$. Тогда $\sum_i \alpha_i y_i = 0$ даёт $\alpha_A = \alpha_C - \alpha_B = \tfrac14$. Все множители неотрицательны, поэтому условия ККТ выполнены и $w = (0, 1)$, $b = -1$ оптимальны. Двойственная целевая функция равна $\sum_i \alpha_i - \tfrac12\lVert w\rVert^2 = 1 - 0.5 = 0.5$, то есть прямой $\tfrac12\lVert w\rVert^2$. Суммирование дополняющей нежёсткости $\alpha_i(M_i - 1) = 0$ по точкам даёт $\sum_i \alpha_i = \lVert w\rVert^2$ для любого решения с жёстким зазором, так что зазор можно прочитать по одной двойственной задаче: $\gamma = 1/\sqrt{\sum_i \alpha_i}$. На первом рисунке $\sum_i \alpha_i = 1.5123$ и $\gamma = 0.81$.

Опорные векторы: что говорят двойственные переменные#

Рисунок

Мягкий зазор: что говорят двойственные переменные

Условия ККТ делят обучающие точки на три группы по значению $\alpha_i$:

• $\alpha_i = 0$. Тогда $\mu_i = C \gt 0$, поэтому $\xi_i = 0$ и $M_i \ge 1$: точка лежит по верную сторону от своего края полосы. В $w = \sum_i \alpha_i y_i x_i$ она не входит.
• $0 \lt \alpha_i \lt C$. Тогда $\mu_i \gt 0$ заставляет $\xi_i = 0$, а $\alpha_i \gt 0$ заставляет $M_i = 1 - \xi_i = 1$: точка лежит ровно на краю полосы. Такие точки дают смещение: из $y_i(\langle w, x_i\rangle + b) = 1$ и $y_i^2 = 1$ следует $b = y_i - \langle w, x_i\rangle$; для численной устойчивости это значение усредняют по всем таким точкам.
• $\alpha_i = C$. Тогда $\mu_i = 0$, $\xi_i$ может быть положительным и $M_i = 1 - \xi_i \le 1$: точка на краю, внутри полосы или по другую сторону гиперплоскости.

В обратную сторону: точка строго вне полосы ($M_i \gt 1$) обязана иметь $\alpha_i = 0$, а точка с положительным штрафом — $\alpha_i = C$. Точки с $\alpha_i \gt 0$ называются опорными векторами (support vectors); решение — взвешенная сумма только их. На рисунке опорными векторами являются 6 точек из 20: три на краях с $\alpha = 0.64, 0.68, 0.96$ и три с $\alpha = C = 1$ и штрафами $0.66$, $0.92$ (внутри полосы) и $1.54$ (классифицирована неверно).

У разреженности два практических следствия. Если удалить точку с $\alpha_i = 0$ и обучить модель заново, условия ККТ по-прежнему выполняются для тех же $w$ и $b$, так что решение не меняется; обучение на одних трёх опорных векторах из двадцати разделимых точек даёт ту же прямую, что и проверяет раздел «Код». А при валидации с исключением по одному (leave-one-out) каждая точка с $\alpha_i = 0$ классифицируется верно, когда её откладывают: классификатор, обученный без неё, тот же самый и оставляет её вне полосы. Поэтому ошибка leave-one-out не больше числа опорных векторов, делённого на $n$, если солвер возвращает то же решение после удаления точки с $\alpha_i = 0$. Это оценка для leave-one-out, которая, как и кросс-валидация, описывает процедуру на обучающих выборках размера $n - 1$; малое число опорных векторов — хороший знак, но не гарантия для риска одной развёрнутой модели при конечной выборке.

Как C обменивает зазор на ошибки#

На данных о раке молочной железы (569 опухолей, 30 стандартизованных признаков, 70% для обучения) выбор $C$ переводит решение от широкой полосы с множеством нарушений к узкой полосе, которая в точности подгоняет обучающую выборку:

$C$	опорных векторов	из них с $\alpha = C$	ширина полосы $2/\lVert w\rVert$	доля правильных на обучении	доля правильных на тесте
0.001	195	189	6.38	0.940	0.930
0.01	92	83	3.01	0.980	0.959
0.1	44	32	1.46	0.992	0.959
1	27	11	0.69	0.992	0.953
10	25	3	0.32	0.995	0.953
100	25	1	0.09	1.000	0.930

При малом $C$ почти каждый опорный вектор стоит на границе $\alpha = C$: полоса широкая, и многие точки внутри неё. С ростом $C$ полоса сужается, доля правильных ответов (accuracy) на обучении доходит до 1, а на тесте падает обратно до $0.930$: большое $C$ — слабая регуляризация и переобучение, в точности как малый гребневый штраф. $C$ — гиперпараметр, его выбирают кросс-валидацией по логарифмической сетке. Поскольку ширина полосы измеряется в единицах признаков, признаки нужно сначала стандартизовать; иначе признак с наибольшим масштабом доминирует в $\lVert w\rVert$.

Почему широкий зазор обобщается#

Первая оценка обобщающей способности из курса теории вероятностей контролировала разрыв между риском на обучении и истинным риском через число моделей-кандидатов. Гиперплоскостей в $\mathbb R^d$ бесконечно много, и классическая замена для $\ln K$ растёт с $d$: в высокой размерности то, что обучающая выборка разделена, мало что говорит. Зазоры убирают размерность. Пусть каждый вход удовлетворяет $\lVert x\rVert \le \rho$, а распределение разделимо с зазором $\gamma$ гиперплоскостью, проходящей через начало координат. Тогда с вероятностью не меньше $1 - \delta$ по обучающей выборке размера $n$ риск 0–1 у SVM с жёстким зазором не превосходит

$$\sqrt{\frac{4 (\rho/\gamma)^2}{n}} + \sqrt{\frac{2 \ln (2/\delta)}{n}}$$

(Shalev-Shwartz and Ben-David, 2014, теорема 15.4). Размерность $d$ сюда не входит, только отношение радиуса данных к зазору. При $\rho/\gamma = 10$, $n = 10\,000$ и $\delta = 0.05$ оценка равна $0.200 + 0.027 = 0.227$: она грубая, как все такие оценки, но выполняется в миллионе измерений так же, как в двух. Именно это делает разумным отобразить данные в пространство огромной размерности и разделить их там с широким зазором — программа следующей заметки.

Как это решают на практике#

У двойственной задачи одно ограничение-равенство, поэтому наименьший набор переменных, который можно менять, сохраняя $\sum_i \alpha_i y_i = 0$, — это пара. Последовательная минимальная оптимизация (sequential minimal optimization, SMO; Platt, 1998) раз за разом выбирает два множителя, решает задачу от двух переменных в замкнутом виде и обрезает каждый множитель до отрезка $[0, C]$. LIBSVM, солвер, на котором построен SVC из scikit-learn, берёт первым множителем тот, что сильнее всего нарушает условия ККТ, а вторым — тот, что в паре с ним сильнее всего увеличивает двойственную целевую функцию по оценке, использующей информацию второго порядка (LIBSVM минимизирует функцию, противоположную записанной выше двойственной, так что в его терминах это наибольшее уменьшение) (Fan, Chen and Lin, 2005; Chang and Lin, 2011). Рисунки этой заметки посчитаны тем же методом в нескольких десятках строк. Для линейных SVM на больших данных форму без ограничений, кусочно-линейная функция потерь плюс L2, минимизируют напрямую стохастическими шагами по субградиенту, как в Pegasos (Shalev-Shwartz et al., 2011); при фиксированной точности решения его стоимость не растёт с $n$. Линейный SVM на векторах TF-IDF много лет был стандартным сильным бейзлайном для классификации текстов (Joachims, 1998) — это постановка заметки о мешке слов курса NLP.

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

	Логистическая регрессия	Метод опорных векторов
Какая разделяющая прямая	максимального правдоподобия	с самым широким зазором
Функция потерь	логистическая, гладкая, нигде не равна нулю	кусочно-линейная, равна нулю при $M_i \ge 1$
Какие обучающие точки важны	все, каждая с весом $p_i - [y_i = 1]$ в градиенте	только опорные векторы, $\alpha_i \gt 0$
Выход	вероятность $P(y = 1 \mid x)$	оценка, знак которой — класс; для вероятностей нужна калибровка
Оптимизация	без ограничений, гладкая	задача квадратичного программирования, обычно решаемая через двойственную
Ручка регуляризации	$\lambda$	$C$, причём $\lambda = 1/(2Cn)$
Как входят данные	векторы признаков	скалярные произведения $\langle x_i, x_j\rangle$ в двойственной задаче

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

• Нет вероятностей. Кусочно-линейная функция потерь нацелена только на знак $P(y = 1 \mid x) - 1/2$; любую вероятность приходится подгонять потом, а для этого нужны отложенные данные.
• Чувствительность к масштабу и к $C$. Зазор — евклидово расстояние, поэтому признаки нужно стандартизовать, а $C$ — подбирать; в таблице доля правильных ответов на тесте меняется на три пункта по сетке.
• Выбросы всё равно тянут. Кусочно-линейная функция потерь растёт линейно, поэтому точка с ошибочной меткой далеко по другую сторону становится опорным вектором с $\alpha_i = C$ и сдвигает решение; граница $C$ ограничивает её влияние, но не устраняет.
• Линейность. В таком виде SVM разделяет гиперплоскостью в исходных признаках. Два концентрических кольца точек ему не по силам при любом $C$.
• Два класса. Для нескольких классов нужна сводка к бинарным задачам или совместная постановка; их сравнивает заметка о многоклассовой классификации.

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

• Расстояние от $x$ до гиперплоскости равно $\lvert\langle w, x\rangle + b\rvert / \lVert w\rVert$; масштаб, при котором у ближайших точек $M_i = 1$, делает зазор равным $1/\lVert w\rVert$, а ширину полосы — $2/\lVert w\rVert$.
• Жёсткий зазор: минимизировать $\tfrac12\lVert w\rVert^2$ при $M_i \ge 1$. Мягкий зазор: добавить штрафы $\xi_i$ по цене $C$, что равносильно минимизации $C\sum_i \max(0, 1 - M_i) + \tfrac12\lVert w\rVert^2$ — кусочно-линейной функции потерь плюс L2-штрафа.
• Двойственная задача: $\max \sum_i \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\langle x_i, x_j\rangle$ при $0 \le \alpha_i \le C$, $\sum_i \alpha_i y_i = 0$; сильная двойственность выполнена, и $w = \sum_i \alpha_i y_i x_i$.
• ККТ: $\alpha_i = 0$ вне полосы, $0 \lt \alpha_i \lt C$ ровно на её краю (эти точки дают $b$), $\alpha_i = C$ внутри полосы или при ошибке. Решение определяют только опорные векторы, $\alpha_i \gt 0$.
• Большое $C$ — слабая регуляризация. Кусочно-линейная функция потерь оценивает байесовское решение, а не вероятности. Оценки через зазор зависят от $\rho/\gamma$, а не от размерности.

Код#

Разобранный пример, оба рисунка, двойственная задача, решённая универсальным оптимизатором, и влияние $C$:

import numpy as np
from scipy.optimize import minimize
from sklearn.svm import SVC
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

def fit(X, y, C):
    m = SVC(kernel='linear', C=C, tol=1e-8).fit(X, y)
    alpha = np.zeros(len(y)); alpha[m.support_] = np.abs(m.dual_coef_[0])   # в dual_coef_ хранятся y_i * alpha_i
    return m.coef_[0], m.intercept_[0], alpha

# разобранный пример: четыре точки, жёсткий зазор (очень большое C)
X4 = np.array([[0, 0], [2, 0], [1, 2], [3, 3]]); y4 = np.array([-1, -1, 1, 1])
w, b, alpha = fit(X4, y4, 1e6)
print(w.round(3), round(b, 3), alpha.round(3))          # [0. 1.] -1.0 [0.25 0.25 0.5  0.  ]

# двадцать разделимых точек (первый рисунок); сначала класс -1
Xh = np.array([[-0.9, -0.7], [-1.7, -0.4], [-1.5, -1.9], [-0.6, -1], [-1.9, -0.2], [-2.6, -0.3], [-1.8, -0.7], [-1.7, -0.1], [-1.6, -0.4], [-1.5, -1.2],
               [2, 1.5], [0.7, 1.3], [0.4, 0.5], [1.5, -0.4], [0.1, 2.1], [2.8, 2], [0.4, 0.8], [1.5, 0.8], [2.5, 0.3], [0.3, 0.4]])
y = np.repeat([-1, 1], 10)
w, b, alpha = fit(Xh, y, 1e6)
sv = np.flatnonzero(alpha > 1e-6)
print(w.round(3), round(b, 3), round(2 / np.linalg.norm(w), 3), sv, alpha[sv].round(3))
# [0.87 0.87] 0.391 1.626 [ 0  3 19] [0.63  0.126 0.756]
print(round(alpha.sum(), 4), round(w @ w, 4))           # 1.5123 1.5123: в оптимуме с жёстким зазором sum(alpha) = ||w||^2
w2, b2, _ = fit(Xh[sv], y[sv], 1e6)
print(w2.round(3), round(b2, 3))                        # [0.87 0.87] 0.391: одни опорные векторы дают ту же прямую

# двадцать перекрывающихся точек (второй рисунок), C = 1
Xs = np.array([[-0.7, -1.3], [-1.6, -0.5], [-0.9, -0.3], [-2.2, -1], [-1.5, 0.1], [-0.4, -0.3], [-0.9, -0.5], [-0.5, -1.3], [0.4, 0.4], [0.7, -0.9],
               [1.6, 0.7], [0.1, 1.5], [0.3, 0.3], [1.1, -0.1], [0.4, 1.4], [1.9, 1.2], [1.8, 0.3], [1.7, 1.8], [1.8, -1.3], [2.3, 0.2]])
w, b, alpha = fit(Xs, y, 1.0)
M = y * (Xs @ w + b); xi = np.maximum(0, 1 - M)
print(w.round(3), round(b, 3), np.flatnonzero((alpha > 1e-6) & (alpha < 1 - 1e-6)), np.flatnonzero(alpha > 1 - 1e-6), xi[alpha > 1 - 1e-6].round(2))
# [1.256 0.762] -0.269 [ 5 11 18] [ 8  9 12] [1.54 0.92 0.66]
print(round(0.5 * w @ w + xi.sum(), 4), round(alpha.sum() - 0.5 * w @ w, 4))   # 4.2044 4.2044: прямая = двойственная

# та же двойственная задача, решённая универсальным оптимизатором: max sum(a) - 1/2 a^T Q a, 0 <= a <= C, sum(a y) = 0
Q = (y[:, None] * Xs) @ (y[:, None] * Xs).T
res = minimize(lambda a: 0.5 * a @ Q @ a - a.sum(), np.zeros(20), jac=lambda a: Q @ a - 1, method='SLSQP',
               bounds=[(0, 1)] * 20, constraints={'type': 'eq', 'fun': lambda a: a @ y}, options={'ftol': 1e-12, 'maxiter': 500})
a = res.x; w_dual = (a * y) @ Xs
free = (a > 1e-4) & (a < 1 - 1e-4)
print(w_dual.round(3), round(np.mean(y[free] - Xs[free] @ w_dual), 3))   # [1.256 0.762] -0.269

# влияние C на данных о раке молочной железы (569 опухолей, 30 стандартизованных признаков)
X, t = load_breast_cancer(return_X_y=True)
Xtr, Xte, ttr, tte = train_test_split(X, 2 * t - 1, test_size=0.3, random_state=0, stratify=t)
sc = StandardScaler().fit(Xtr); Xtr, Xte = sc.transform(Xtr), sc.transform(Xte)
for C in (0.001, 0.01, 0.1, 1, 10, 100):
    m = SVC(kernel='linear', C=C).fit(Xtr, ttr)
    at_C = int((np.abs(m.dual_coef_[0]) > C * (1 - 1e-6)).sum())
    print(C, len(m.support_), at_C, round(2 / np.linalg.norm(m.coef_[0]), 3), round(m.score(Xtr, ttr), 3), round(m.score(Xte, tte), 3))
# C, опорные векторы, из них с alpha = C, ширина полосы, доля правильных на обучении и на тесте
# 0.001 195 189 6.381 0.94 0.93 | 0.01 92 83 3.014 0.98 0.959 | 0.1 44 32 1.459 0.992 0.959
# 1 27 11 0.686 0.992 0.953     | 10 25 3 0.321 0.995 0.953    | 100 25 1 0.089 1.0 0.93

Дальше#

Двойственная задача и классификатор касаются данных только через скалярные произведения $\langle x_i, x_j\rangle$, а оценка через зазор не зависит от размерности. Оба факта указывают в одну сторону: заменить $x$ более богатым представлением $\phi(x)$, возможно огромной или бесконечной размерности, и никогда не вычислять само $\phi$, а только $\langle \phi(x_i), \phi(x_j)\rangle$. Следующая заметка показывает, какие функции могут играть роль такого скалярного произведения и что они дают: криволинейные разделяющие границы из той же задачи квадратичного программирования.

Литература#

• B. E. Boser, I. M. Guyon, V. N. Vapnik. A Training Algorithm for Optimal Margin Classifiers. COLT, 1992, pp. 144–152. Классификатор с жёстким зазором и его двойственная задача.
• C. Cortes, V. Vapnik. Support-Vector Networks. Machine Learning, 20(3), pp. 273–297, 1995. Мягкий зазор.
• S. Boyd, L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Глава 5: двойственность Лагранжа (§5.1–5.2), условие Слейтера и его уточнение для аффинных ограничений (§5.2.3), дополняющая нежёсткость и условия ККТ (§5.5.2–5.5.3).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Глава 15: жёсткий и мягкий SVM, теорема 15.4 (оценка через зазор), §15.3 (опорные векторы), §15.4 (двойственность), §15.5 (SGD).
• Y. Lin. Support Vector Machines and the Bayes Rule in Classification. Data Mining and Knowledge Discovery, 6(3), pp. 259–275, 2002. Минимум ожидаемой кусочно-линейной функции потерь.
• J. C. Platt. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. In A. Smola, P. Bartlett, B. Schölkopf, D. Schuurmans (eds.), Advances in Large Margin Classifiers, pp. 61–74. MIT Press, 1999.
• J. Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research, MSR-TR-98-14, 1998.
• C.-C. Chang, C.-J. Lin. LIBSVM: A Library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology, 2(3), 2011. Раздел 4.1: выбор рабочего множества.
• R.-E. Fan, P.-H. Chen, C.-J. Lin. Working Set Selection Using Second Order Information for Training Support Vector Machines. Journal of Machine Learning Research, 6, pp. 1889–1918, 2005.
• S. Shalev-Shwartz, Y. Singer, N. Srebro, A. Cotter. Pegasos: Primal Estimated Sub-Gradient Solver for SVM. Mathematical Programming, 127(1), pp. 3–30, 2011.
• T. Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. ECML, 1998, pp. 137–142.
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Раздел 7.1 (классификаторы с максимальным зазором, перекрывающиеся классы, связь с логистической регрессией), приложение E (множители Лагранжа).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Раздел 12.2 (опорный векторный классификатор), раздел 12.3.2 (SVM как метод со штрафом).
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций: лекция 5 (метод опорных векторов), лекция 14 (двойственная задача и ядерный SVM).