Support Vector Machines 📐

Открой уроки 214, 279, 282 и 283 ещё раз одним взглядом — как список глав одной книги. В уроке 214 ты научился искать условный экстремум методом множителей Лагранжа: где градиент целевой функции становится параллелен градиенту ограничения. В уроке 279 эта идея выросла в условия Каруша-Куна-Таккера — то же самое рассуждение, но уже для ограничений-неравенств, с дополняющей нежёсткостью, которая решает, какое ограничение «активно», а какое можно игнорировать. В уроке 282 ты взял произвольную задачу с ограничениями и перешёл к двойственной формулировке — той же самой задаче, но с другими переменными, множителями Лагранжа, — и увидел, что для SVM эта двойственная задача устроена совершенно особым образом: исходные данные входят в неё только через скалярные произведения. А в уроке 283 ты довёл этот вывод до конца, доказал, что получившаяся задача — классическая выпуклая задача квадратичного программирования, и явно выписал матрицу $Q$, ограничения и условие выпуклости через теорему Мерсера.

Сегодняшний урок — не про новую математику. Все формулы, которые тебе понадобятся, ты уже вывел или видел выведенными в уроках 214, 279, 282 и 283 — мы не будем повторять этот вывод ещё раз, а будем на него ссылаться. Этот урок про другое: как эта цепочка формул превращается в работающую модель машинного обучения, которую ты вызываешь одной строкой sklearn.svm.SVC(kernel="rbf").fit(X, y), и что каждая часть этой строки означает на уровне геометрической интуиции и практического использования. Максимальный зазор, опорные векторы, параметр $C$, ядерный трюк — это не новые математические объекты, а новые имена для деталей той самой QP-задачи, которую ты уже видел собранной по частям.

Метод опорных векторов интересен ещё и тем, что это редкий случай алгоритма машинного обучения, у которого нет ни одного случайного элемента внутри: в отличие от случайного леса (урок 317) с его бэггингом и случайным выбором признаков, или градиентного бустинга (урок 318) со стохастическим сэмплированием, SVM при фиксированных гиперпараметрах и фиксированных данных всегда находит одно и то же решение — потому что это решение выпуклой задачи оптимизации с единственным глобальным минимумом, а не результат случайного поиска. Именно эта детерминированность и строгая математическая обоснованность на протяжении почти двух десятилетий, с середины 1990-х до появления глубокого обучения и градиентного бустинга как доминирующих инструментов, делали SVM моделью первого выбора в задачах классификации на табличных и не только табличных данных.

К концу урока ты будешь понимать, почему SVM ищет именно максимальный зазор, а не любую разделяющую границу, что такое опорные векторы и почему они одни определяют решение, как связаны прямая и двойственная задача SVM с квадратичным программированием из урока 283, зачем нужен параметр $C$ в мягком зазоре и как ядерный трюк позволяет проводить нелинейные границы, ни разу не вычисляя координаты точек в пространстве более высокой размерности.

История

Основы теории, на которой построен SVM, заложили советские математики Владимир Вапник и Алексей Червоненкис ещё в 1960-х годах, работая в московском Институте проблем управления. В 1963 году Вапник (вместе с Александром Лернером) предложил метод обобщённого портрета — по сути, первую версию линейного классификатора с максимальным зазором, хотя термин «support vector machine» тогда ещё не существовал. Параллельно Вапник и Червоненкис разрабатывали статистическую теорию обучения (VC-теорию, названную по первым буквам их фамилий), которая математически объясняла, почему одни классификаторы обобщаются на новые данные лучше других, — и идея максимального зазора оказалась естественным следствием этой теории: чем шире зазор между классами, тем меньше эффективная «размерность» (VC-размерность) семейства допустимых разделяющих гиперплоскостей, и тем надёжнее модель обобщается за пределы обучающей выборки.

Работа велась в СССР в относительной изоляции от западной академической среды, и годы спустя, уже в 1990-х, Вапник эмигрировал в США и присоединился к AT&T Bell Labs — туда же, где чуть позже разрабатывались алгоритмы бустинга (урок 318). Именно там, вместе с Бернхардом Бозером и Изабель Гийон, Вапник в 1992 году опубликовал статью, добавившую к линейному классификатору с максимальным зазором решающий ингредиент — ядерный трюк (kernel trick), который мы разберём отдельно в последнем блоке этого урока: замену скалярного произведения на произвольную ядерную функцию, позволяющую строить нелинейные разделяющие границы, не выходя за рамки той же самой выпуклой задачи оптимизации. Три года спустя, в 1995 году, Вапник вместе с Кориной Кортес опубликовал статью «Support-Vector Networks», где ввёл мягкий зазор (soft margin) с параметром $C$ — расширение, сделавшее метод применимым к реальным, не идеально разделимым данным. Именно эта статья 1995 года и считается точкой рождения SVM в его современном виде.

На протяжении следующих полутора десятилетий, с середины 1990-х до начала 2010-х, SVM с ядрами оставался одним из самых сильных и теоретически обоснованных инструментов классификации — особенно на задачах с умеренным объёмом данных (тысячи, а не миллионы примеров) и высокой размерностью признаков, вроде классификации текстов или биоинформатических данных, где число признаков могло на порядки превышать число обучающих примеров. Расцвет глубокого обучения в 2010-х сместил внимание индустрии на нейросети, а градиентный бустинг (урок 318) во многих табличных задачах обошёл SVM по чистой точности, — но там, где данных немного, а признаков много, sklearn.svm.SVC и сегодня остаётся одним из первых инструментов, которые стоит попробовать, и именно про эту нишу — «мало примеров, много признаков» — мы поговорим отдельно в конце урока.

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

Интуиция

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

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

Формула

Постановка задачи максимального зазора (жёсткий зазор). Разделяющая гиперплоскость задаётся уравнением $w^\top x + b = 0$. Для линейно разделимых данных с метками $y_i \in \{-1, +1\}$ ширина зазора между двумя параллельными гиперплоскостями $w^\top x + b = 1$ и $w^\top x + b = -1$, между которыми не должно быть ни одной обучающей точки, равна $\dfrac{2}{\|w\|}$. Максимизация этого зазора эквивалентна минимизации $\|w\|$, а в стандартной форме задачи — минимизации $\frac12\|w\|^2$ (это в точности прямая задача, с которой уже работали уроки 282 и 283):

$$\min_{w,b} \ \frac12\|w\|^2 \quad \text{при } y_i(w^\top x_i + b) \ge 1 \ \text{ для всех } i = 1,\dots,N$$

Примеры с разбором

Пример 1 (простой, геометрический): вычисление ширины зазора по известному $w$

Пусть в двумерной задаче найдено решение $w = (0{,}5,\ 0{,}5)$, $b = -1$. Найди ширину зазора.

Решение. Норма вектора весов: $\|w\| = \sqrt{0{,}5^2 + 0{,}5^2} = \sqrt{0{,}5} \approx 0{,}7071$. Ширина зазора: $\dfrac{2}{\|w\|} = \dfrac{2}{0{,}7071} \approx 2{,}8284$.

Ответ: ширина зазора $\approx 2{,}83$. Это в точности то же самое решение, что было получено в уроке 283 для двух точек $x_1=(1,1)$, $y_1=+1$ и $x_2=(-1,-1)$, $y_2=-1$, где было найдено $w^*=(0{,}5,\,0{,}5)$ и ширина зазора $2\sqrt2 \approx 2{,}83$ — граница проходит ровно по центру между двумя точками, а зазор равен расстоянию между ними.

Пример 2 (средний, геометрический): разделение точек и явная проверка, где проходит граница

Четыре точки на плоскости: $x_1=(1,2)$, $y_1=+1$; $x_2=(2,3)$, $y_2=+1$; $x_3=(0,-1)$, $y_3=-1$; $x_4=(1,-2)$, $y_4=-1$. Найдено решение $w=(0,1)$, $b=0$.

Решение. Проверим ограничения $y_i(w^\top x_i+b)\ge1$ для каждой точки: для $x_1$ — $1\cdot(0\cdot1+1\cdot2+0)=2\ge1$ ✓ (с запасом); для $x_2$ — $1\cdot(0\cdot2+1\cdot3+0)=3\ge1$ ✓ (с запасом); для $x_3$ — $(-1)\cdot(0\cdot0+1\cdot(-1)+0)=(-1)\cdot(-1)=1\ge1$ ✓ (точное равенство); для $x_4$ — $(-1)\cdot(0\cdot1+1\cdot(-2)+0)=(-1)\cdot(-2)=2\ge1$ ✓ (с запасом). Разделяющая прямая — горизонтальная линия $x_2^{\text{коорд}}=0$ (вторая координата равна нулю), зазор — полоса от $y=-1$ до $y=1$ по второй координате. Ширина зазора: $\dfrac{2}{\|w\|}=\dfrac{2}{1}=2$.

Ответ: только точка $x_3=(0,-1)$ выполняет ограничение с точным равенством — она и есть единственный опорный вектор среди четырёх точек; $x_1$, $x_2$, $x_4$ находятся дальше от границы, чем требует зазор, и в этой конкретной конфигурации не влияют на решение.

Пример 3 (сложный, геометрический): почему нельзя просто взять «любую» разделяющую прямую и назвать её оптимальной

Для тех же четырёх точек из примера 2 рассмотрим альтернативную разделяющую прямую $w'=(0,\,2)$, $b'=-2$ (то есть прямая $2x_2^{\text{коорд}}-2=0$, или $x_2^{\text{коорд}}=1$) — она тоже разделяет классы верно.

Решение. Проверим допустимость: для $x_3$ — $(-1)\cdot(2\cdot(-1)-2)=(-1)\cdot(-4)=4\ge1$ ✓, для $x_1$ — $1\cdot(2\cdot2-2)=1\cdot2=2\ge1$ ✓ — формально ограничения выполняются, но с очень разным запасом для разных точек, а $\|w'\|=2$, значит ширина зазора $\dfrac{2}{\|w'\|}=1$ — вдвое уже, чем у решения из примера 2. Более того, эта прямая $x_2^{\text{коорд}}=1$ проходит гораздо ближе к точкам верхнего класса ($x_1=(1,2)$ на расстоянии $1$ по вертикали), чем к нижнему ($x_3=(0,-1)$ на расстоянии $2$) — она смещена в сторону одного класса, а не проходит по центру полосы.

Ответ: прямая из примера 2 ($w=(0,1)$, $b=0$, зазор $2$) — оптимальная (максимальный зазор), прямая из этого примера — допустимая, но не оптимальная (зазор всего $1$, и граница смещена в сторону класса $-1$); SVM среди всех допустимых разделяющих гиперплоскостей всегда выбирает именно первую, потому что решает задачу минимизации $\|w\|$, а не просто ищет любое допустимое решение.

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

Формулировка «максимизировать зазор» — не одна из многих равноценных идей, как провести разделяющую границу, а конкретный выбор, обоснованный теорией Вапника и Червоненкиса: более широкий зазор соответствует более простому, менее склонному к переобучению классификатору в терминах VC-размерности — прямая связь с компромиссом смещения и дисперсии из урока 304, только выраженная не через сложность модели напрямую, а через геометрию разделяющей границы. Именно поэтому SVM в задачах с относительно небольшим числом обучающих примеров и высокой размерностью признаков (текстовая классификация, биоинформатика, где признаков часто больше, чем строк) исторически показывал результаты, сопоставимые с гораздо более сложными моделями, — теоретическая гарантия хорошего обобщения заложена прямо в формулировке задачи, а не выясняется эмпирически на кросс-валидации (урок 306).

Опорные векторы и постановка задачи как QP

Интуиция

В примерах предыдущего раздела ты уже заметил закономерность: не все точки одинаково важны для решения. В примере 2 только одна из четырёх точек ($x_3$) выполняла ограничение с точным равенством — лежала точно на границе зазора, — а три остальные находились дальше и формально «не мешали» найденному решению. Это не случайность конкретного примера, а прямое следствие теории KKT из урока 279: условие дополняющей нежёсткости требует, чтобы множитель Лагранжа $\alpha_i$ был ненулевым только для точек, ограничение которых активно (лежит точно на границе зазора), — и именно такие точки называются опорными векторами. Если убрать из обучающей выборки любую точку, не являющуюся опорным вектором, и переобучить SVM заново, решение не изменится ни на йоту — граница целиком определяется опорными векторами.

Формула

Опорные векторы через условие дополняющей нежёсткости KKT. Как показано в уроке 279 (для общей теории) и в уроке 282 (для SVM конкретно), в оптимуме выполняется

$$\alpha_i^*\bigl[y_i(w^{*\top}x_i+b^*) - 1\bigr] = 0 \ \text{ для каждого } i$$

Значит, либо $\alpha_i^*=0$ (точка не опорный вектор, лежит строго дальше зазора и не влияет на решение), либо $y_i(w^{*\top}x_i+b^*)=1$ (точка лежит ровно на границе зазора — это опорный вектор). Итоговый вектор весов восстанавливается только по опорным векторам: $w^* = \sum_{i:\ \alpha_i^*>0} \alpha_i^* y_i x_i$.

Примеры с разбором

Пример 1 (простой): подсчёт опорных векторов по значениям множителей

Обучающая выборка из 6 точек дала множители Лагранжа $\alpha = (0{,}0;\ 1{,}2;\ 0{,}0;\ 0{,}0;\ 0{,}8;\ 0{,}0)$.

Решение. Опорные векторы — это точки с $\alpha_i > 0$: индексы $2$ и $5$, со значениями $1{,}2$ и $0{,}8$. Остальные четыре точки ($\alpha_i=0$) не являются опорными векторами.

Ответ: только 2 из 6 точек — опорные векторы; вектор весов $w^* = 1{,}2\cdot y_2 x_2 + 0{,}8\cdot y_5 x_5$ — сумма всего по двум слагаемым, а не по шести.

Пример 2 (средний): предсказание нового объекта только через опорные векторы

Найдено решение SVM с двумя опорными векторами: $x_1=(2,1)$, $y_1=+1$, $\alpha_1=0{,}5$; $x_2=(-1,-1)$, $y_2=-1$, $\alpha_2=0{,}5$, $b^*=0{,}1$. Классифицируй новую точку $x_{\text{нов}}=(1,0)$.

Решение. Сначала восстановим $w^*=\alpha_1y_1x_1+\alpha_2y_2x_2=0{,}5\cdot1\cdot(2,1)+0{,}5\cdot(-1)\cdot(-1,-1)=(1,\,0{,}5)+(0{,}5,\,0{,}5)=(1{,}5,\,1{,}0)$. Значение решающей функции: $w^{*\top}x_{\text{нов}}+b^* = 1{,}5\cdot1+1{,}0\cdot0+0{,}1=1{,}6$.

Ответ: знак положителен ($1{,}6>0$), значит новая точка классифицируется как класс $+1$; заметь, что для этого предсказания понадобились только два опорных вектора, а не вся обучающая выборка — в реальных задачах с десятками тысяч примеров эта экономия существенна для скорости инференса.

Пример 3 (сложный): почему удаление неопорного вектора не меняет решение, а удаление опорного — меняет

Возьмём выборку из примера 2 этого раздела (задание с 6 точками) и добавим седьмую точку $x_7$ с $\alpha_7=0$, лежащую далеко от границы зазора внутри своего класса.

Решение. Раз $\alpha_7=0$, точка $x_7$ не входит в сумму $w^*=\sum_{i:\alpha_i^*>0}\alpha_i^*y_ix_i$ — она физически не участвует в формуле, определяющей разделяющую гиперплоскость. Удаление $x_7$ из обучающей выборки и повторное решение задачи КП даст в точности те же $\alpha_2^*, \alpha_5^*$ и то же $w^*, b^*$, потому что ограничения задачи для всех остальных точек не изменились, а $x_7$ и раньше не была активным ограничением. Если бы вместо $x_7$ была удалена точка с $\alpha_i>0$ (опорный вектор), задача КП изменилась бы — исчезло бы одно из ограничений, которое реально «держало» границу зазора, и оптимальное решение почти наверняка сдвинулось бы.

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

Постановка как задача квадратичного программирования (ссылка на урок 283)

Разберём здесь только практическую сторону: прямая задача максимального зазора $\min \frac12\|w\|^2$ при $y_i(w^\top x_i+b)\ge1$ — это задача КП с гессианом $Q=I$ (единичная матрица) по переменной $w$, которая, как доказано в уроке 283, положительно полуопределена всегда, независимо от данных, — значит, задача всегда выпуклая, и любой найденный минимум гарантированно глобальный. Полный вывод двойственной задачи через лагранжиан, включая все промежуточные шаги дифференцирования по $w$, $b$ и $\xi_i$, ты уже проделал в уроках 282 и 283 — здесь мы используем сразу итоговый результат:

Двойственная задача SVM (напоминание итога уроков 282–283).

$$\max_\alpha \ \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle x_i, x_j\rangle \quad \text{при } 0 \le \alpha_i \le C,\ \ \sum_{i=1}^N \alpha_i y_i = 0$$

Именно эту задачу решает libsvm внутри sklearn.svm.SVC — с помощью алгоритма SMO (Sequential Minimal Optimization, «последовательная минимальная оптимизация») Джона Платта, который, как ты видел в уроке 283, вынужден оптимизировать переменные парами $(\alpha_i,\alpha_j)$ именно из-за линейного ограничения равенства $\sum_i\alpha_iy_i=0$.

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

Понимание того, что решение SVM определяется исключительно опорными векторами, объясняет сразу две практические вещи. Во-первых, почему модель SVM часто получается компактной и быстрой в применении даже на больших датасетах — если, как отмечено в уроке 279, число опорных векторов составляет лишь несколько процентов от размера выборки, предсказание нового объекта требует вычислений, пропорциональных не всей обучающей выборке, а только этому небольшому подмножеству. Во-вторых, почему разреженность решения ($\alpha_i^*=0$ для большинства точек) — не побочный эффект, а прямое и неизбежное следствие условия дополняющей нежёсткости KKT, той самой теории, которую ты изучал в уроке 279 задолго до того, как узнал, что она объясняет структуру одного из самых популярных алгоритмов машинного обучения.

Мягкий зазор и параметр C

Интуиция

Реальные данные почти никогда не бывают идеально линейно разделимы: один или несколько объектов класса $+1$ могут оказаться территориально среди объектов класса $-1$ — из-за шума измерений, ошибок разметки или просто из-за того, что классы объективно немного перекрываются. Задача жёсткого зазора из предыдущих разделов в такой ситуации попросту не имеет допустимого решения: не существует гиперплоскости, для которой выполнялись бы все ограничения $y_i(w^\top x_i+b)\ge1$ одновременно. Мягкий зазор решает эту проблему, разрешая некоторым точкам нарушать ограничение зазора — но не бесплатно, а за штраф, который добавляется в целевую функцию и который тем больше, чем сильнее нарушение.

Формула

Прямая задача мягкого зазора (уже разбиралась как пример QP в уроке 283):

$$\min_{w,b,\xi} \ \frac{1}{2}\|w\|^2 + C\sum_{i=1}^N \xi_i \quad \text{при } y_i(w^\top x_i + b) \ge 1-\xi_i,\ \ \xi_i \ge 0$$

Переменные $\xi_i \ge 0$ (слэк-переменные, slack variables) измеряют, насколько точка $i$ нарушает зазор: $\xi_i=0$ означает, что точка либо на границе зазора, либо дальше от неё (как в жёсткой постановке), $0<\xi_i<1$ — точка внутри полосы зазора, но всё ещё с правильной стороны разделяющей границы, $\xi_i>1$ — точка перешла на неправильную сторону границы (ошибка классификации). Параметр $C>0$ — гиперпараметр, задающий цену одной единицы нарушения зазора в тех же единицах, что и $\frac12\|w\|^2$.

Примеры с разбором

Пример 1 (простой): вычисление $\xi_i$ по известному нарушению

Точка с меткой $y_i=+1$ и значением решающей функции $w^\top x_i+b = 0{,}3$.

Решение. Ограничение требует $y_i(w^\top x_i+b)\ge1-\xi_i$, то есть $1\cdot0{,}3\ge1-\xi_i$, откуда $\xi_i\ge1-0{,}3=0{,}7$. Минимально необходимое значение — $\xi_i=0{,}7$.

Ответ: $\xi_i=0{,}7$ — точка находится внутри полосы зазора (значение решающей функции $0{,}3$ между $-1$ и $1$), но пока ещё с правильной стороны границы ($0{,}3>0$, значит классифицируется верно), поскольку $\xi_i<1$.

Пример 2 (средний): влияние $C$ на компромисс между шириной зазора и числом ошибок

Рассмотрим один и тот же датасет с одним «выбросом» — точкой класса $+1$, залетевшей глубоко на территорию класса $-1$. Обучение с $C=100$ (большой штраф за нарушение) даёт узкий зазор, который аккуратно «огибает» выброс, стараясь классифицировать его правильно ценой уменьшения $\|w\|$-оптимальности. Обучение с $C=0{,}01$ (маленький штраф) даёт широкий зазор, полностью игнорирующий этот единичный выброс — модель «жертвует» правильной классификацией одной аномальной точки ради максимально широкого, устойчивого зазора для всех остальных.

Решение. Формально: при большом $C$ слагаемое $C\sum\xi_i$ в целевой функции доминирует над $\frac12\|w\|^2$, и оптимизатор предпочитает уменьшать $\xi_i$ (даже ценой роста $\|w\|$, то есть сужения зазора) — модель ведёт себя ближе к жёсткому зазору, старается классифицировать каждую обучающую точку правильно. При малом $C$ слагаемое $\frac12\|w\|^2$ доминирует, и оптимизатор охотнее допускает ненулевые $\xi_i$ (нарушения) ради минимизации $\|w\|$ — модель ведёт себя мягче, снисходительнее к отдельным нарушителям.

Ответ: $C$ — это буквально числовой курс обмена между шириной зазора и допустимым числом (и величиной) нарушений; большой $C$ → узкий зазор, мало ошибок на обучении, риск переобучения на шум; маленький $C$ → широкий зазор, больше допущенных нарушений, риск недообучения.

Пример 3 (сложный): переобучение и недообучение через $C$ — числовая иллюстрация на валидации

На одном датасете кредитного скоринга обучены три модели SVM с разными $C$, и получены следующие accuracy:

Решение. При $C=0{,}001$ модель слишком снисходительна к нарушениям, зазор чрезмерно широк, и модель недообучена — низкая точность и на обучении, и на валидации. При $C=1000$ модель почти не допускает нарушений на обучении (accuracy $0{,}99$), но эта точность не переносится на новые данные (валидация падает до $0{,}82$) — классический признак переобучения (урок 304): модель подстроилась под шум конкретной обучающей выборки, включая отдельные выбросы, которые не стоило аккуратно «огибать». При $C=1{,}0$ — лучший компромисс: разумная точность на обучении ($0{,}91$) и лучшая точность на валидации из всех трёх вариантов ($0{,}89$).

Ответ: оптимальное значение $C=1{,}0$ для этой задачи — оно находится не перебором «на глаз», а через кросс-валидацию (урок 306), точно так же, как подбирается коэффициент регуляризации $\lambda$ для Ridge/Lasso (урок 312) — $C$ в SVM играет обратную роль по сравнению с $\lambda$: большой $C$ соответствует слабой регуляризации (модель гонится за точностью на обучении), маленький $C$ — сильной регуляризации (модель жертвует точностью на обучении ради простоты границы).

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

Параметр $C$ — не техническая деталь, добавленная для удобства работы с зашумлёнными данными, а прямое математическое воплощение того же компромисса между смещением и дисперсией, который проходит через весь курс, начиная с урока 304. В терминах уже пройденной теории KKT из урока 279: наличие мягкого зазора добавляет к box-ограничениям $\alpha_i \ge 0$ верхнюю границу $\alpha_i \le C$ — то самое ограничение, вывод которого ты видел в уроке 283 через условие $\alpha_i = C - \mu_i$ и $\mu_i \ge 0$. Без параметра $C$ (то есть при $C=\infty$, что соответствует жёсткому зазору) SVM в принципе неприменим к подавляющему большинству реальных, не идеально разделимых датасетов — именно статья Вапника и Кортес 1995 года с мягким зазором сделала метод практически пригодным.

Ядерный трюк и RBF-ядро

Интуиция

Всё, что было разобрано до сих пор, находит только линейную разделяющую границу — прямую на плоскости, плоскость в трёхмерном пространстве, гиперплоскость в пространстве большей размерности. Но многие реальные датасеты линейно неразделимы в принципе: представь точки одного класса, расположенные кольцом вокруг точек другого класса, — никакая прямая линия эти классы не разделит. Один из вариантов решения — явно перевести точки в пространство более высокой размерности, где нелинейная в исходных координатах граница становится линейной (например, добавить координату $x_1^2+x_2^2$, и кольцевая граница в исходных координатах станет плоскостью в новых). Проблема в том, что для многих полезных преобразований новое пространство признаков может быть огромным или даже бесконечномерным, и явно вычислять координаты каждой точки в нём было бы вычислительно неподъёмно.

Ядерный трюк решает эту проблему элегантным обходным путём, который ты уже видел выведенным в уроке 282: двойственная задача SVM содержит данные только через скалярные произведения $\langle x_i,x_j\rangle$ — нигде в формуле не участвуют сами векторы $x_i$ по отдельности. Значит, если заменить скалярное произведение на функцию $K(x_i,x_j)$, которая равна скалярному произведению точек в каком-то (возможно, очень большом или бесконечномерном) преобразованном пространстве признаков, вся задача КП остаётся точно такой же формы — просто с другой матрицей $Q$. Преобразованные координаты при этом никогда не вычисляются явно — вычисляется только значение функции $K$, что зачастую в разы дешевле.

Формула

Ядерная функция (kernel function). Функция $K(x_i,x_j)$ называется допустимым ядром, если существует отображение $\phi: \mathbb{R}^d \to \mathcal{H}$ в некоторое (возможно, бесконечномерное) пространство признаков $\mathcal{H}$, такое что $K(x_i,x_j) = \langle \phi(x_i), \phi(x_j)\rangle$. Как показано в уроке 283, для того чтобы двойственная задача SVM с ядром $K$ оставалась выпуклой QP, достаточно, чтобы матрица Грама $K_{ij}=K(x_i,x_j)$ была положительно полуопределена для любого набора точек — это в точности теорема Мерсера. Двойственная задача с ядром:

$$\max_\alpha \ \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j\, K(x_i, x_j) \quad \text{при } 0 \le \alpha_i \le C,\ \ \sum_{i=1}^N \alpha_i y_i = 0$$

Полиномиальное ядро: $K(x_i,x_j) = (x_i^\top x_j + r)^p$, где $p$ — степень полинома.

RBF-ядро (Radial Basis Function, «функция радиального базиса», также известное как гауссово ядро), самое популярное на практике:

$$K(x_i,x_j) = \exp\!\left(-\gamma\|x_i-x_j\|^2\right)$$

где $\gamma>0$ — гиперпараметр, задающий, насколько быстро влияние точки убывает с расстоянием. RBF-ядро соответствует отображению в бесконечномерное пространство признаков, и тем не менее вычисляется за $O(d)$ операций — столько же, сколько обычное евклидово расстояние.

Примеры с разбором

Пример 1 (простой): вычисление RBF-ядра между двумя точками

$x_i=(1,2)$, $x_j=(3,1)$, $\gamma=0{,}5$.

Решение. $\|x_i-x_j\|^2 = (1-3)^2+(2-1)^2=4+1=5$. $K(x_i,x_j)=\exp(-0{,}5\cdot5)=\exp(-2{,}5)\approx0{,}0821$.

Ответ: $K(x_i,x_j)\approx0{,}0821$ — значение близко к нулю, потому что точки относительно далеко друг от друга при данном $\gamma$; для $x_i=x_j$ RBF-ядро всегда равно $\exp(0)=1$ — максимально возможное значение.

Пример 2 (средний, геометрический): почему линейная граница невозможна, а RBF-ядро решает задачу

Датасет: класс $+1$ — точки $(0,0)$, $(1,0)$, $(0,1)$, $(-1,0)$, $(0,-1)$ (пять точек около начала координат); класс $-1$ — точки $(3,3)$, $(-3,3)$, $(3,-3)$, $(-3,-3)$, $(5,0)$ (пять точек по периметру дальше от центра).

Решение. Проверим, можно ли разделить эти классы одной прямой: класс $+1$ образует небольшую группу вокруг начала координат, а класс $-1$ окружает её со всех сторон (сверху, снизу, слева и справа) — для любой прямой линии по обе стороны от неё окажутся точки обоих классов одновременно (например, прямая $x=0$ оставляет $(3,3)$ и $(-3,3)$ по разные стороны, но оба — класс $-1$; аналогично для любой другой прямой найдётся пара точек класса $-1$ по разные стороны от неё). Линейное разделение здесь принципиально невозможно ни при каком $w,b$. С RBF-ядром при подходящем $\gamma$ ситуация иная: для любой точки класса $+1$ расстояние до других точек класса $+1$ мало (они рядом с центром), а расстояние до точек класса $-1$ заметно больше — значит, $K$ между точками одного класса ($+1$) заметно выше, чем между точками разных классов, и в неявном признаковом пространстве RBF-ядра эти классы становятся линейно разделимы.

Ответ: SVM с линейным ядром на этих данных не сможет найти разделяющую границу лучше случайной, а SVM с RBF-ядром находит замкнутую (в исходных координатах — примерно круговую) границу вокруг центральной группы точек — ровно тот случай, ради которого и был изобретён kernel trick.

Пример 3 (сложный): влияние $\gamma$ на форму границы — недообучение и переобучение через ядро

На датасете из примера 2 обучены две модели SVM с RBF-ядром: одна с $\gamma=0{,}01$ (маленькое значение), другая с $\gamma=10$ (большое значение).

Решение. При малом $\gamma=0{,}01$ множитель $-\gamma\|x_i-x_j\|^2$ близок к нулю почти для всех пар точек в разумном диапазоне расстояний, а значит $K(x_i,x_j)\approx\exp(0)=1$ почти для любой пары — ядро «не различает» близкие и далёкие точки, влияние каждой обучающей точки на решение распространяется очень широко, и итоговая граница получается почти линейной, гладкой, недообученной (аналог слишком широкого «радиуса влияния» каждой точки). При большом $\gamma=10$, наоборот, $K(x_i,x_j)$ быстро падает почти до нуля уже для соседних точек — каждая обучающая точка «видит» влияние только от объектов, находящихся совсем рядом с ней, граница становится сильно изрезанной, плотно облегающей каждую обучающую точку в отдельности, — классический признак переобучения: модель точно классифицирует обучающую выборку, но плохо обобщается на новые точки, оказавшиеся чуть в стороне от обучающих.

Ответ: $\gamma$ в RBF-ядре играет роль, похожую на глубину дерева решений (урок 316) или на $k$ в методе ближайших соседей (урок 314) — маленькое значение даёт более простую, гладкую, возможно недообученную границу, большое значение даёт более сложную, изрезанную, возможно переобученную границу; на практике $C$ и $\gamma$ подбираются совместно через сеточный поиск (grid search) по кросс-валидации (урок 306), а не по отдельности.

from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV

param_grid = {
    "C": [0.1, 1, 10, 100],
    "gamma": [0.001, 0.01, 0.1, 1],
    "kernel": ["rbf"],
}

grid = GridSearchCV(SVC(), param_grid, cv=5, scoring="accuracy")
grid.fit(X_train, y_train)

print(grid.best_params_)              # например, {'C': 10, 'gamma': 0.01, 'kernel': 'rbf'}
print(grid.best_estimator_.support_vectors_.shape[0])  # число опорных векторов

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

Ядерный трюк — это не отдельная эвристика, добавленная к SVM позже, а прямое алгебраическое следствие того, что двойственная задача, выведенная в уроках 282 и 283, содержит данные только через скалярные произведения. Именно эта структурная особенность, а не какое-то отдельное архитектурное решение, делает возможной замену $\langle x_i,x_j\rangle \to K(x_i,x_j)$ без единого изменения остальной части задачи КП. Как отмечено в уроке 282, в прямой формулировке этот трюк был бы попросту невозможен: там вектор весов $w$ явно живёт в том же пространстве, что и признаки $x$, и, перейдя в бесконечномерное пространство RBF-ядра, пришлось бы работать с бесконечномерным $w$ — вычислительно неподъёмная задача. Именно поэтому переход к двойственной задаче в SVM — не техническое удобство, а необходимое условие для существования ядерного трюка вообще.

Почему SVM хорошо работает при небольшом числе примеров и высокой размерности признаков

Теория Вапника и Червоненкиса, с которой начинался этот урок, даёт формальное объяснение эмпирическому наблюдению: SVM особенно силён именно там, где обучающих примеров немного, а признаков много (текстовая классификация с десятками тысяч признаков-слов при паре тысяч документов, биоинформатика с тысячами генов-признаков при паре сотен образцов). Решение SVM определяется опорными векторами — как показано выше, их число часто оказывается заметно меньше числа обучающих примеров, а значит, эффективная сложность модели ограничивается не общим числом признаков, а числом опорных векторов и шириной зазора. Модели, эффективная сложность которых растёт вместе с числом признаков (например, обычная линейная регрессия без регуляризации при $d>N$, где число признаков превышает число примеров, становится вообще недоопределённой), в этом же режиме заведомо переобучаются или не имеют единственного решения.

Второй фактор — регуляризация встроена в саму формулировку задачи. Минимизация $\frac12\|w\|^2$ — это в точности та же идея, что L2-регуляризация Ridge из урока 312: SVM без всяких дополнительных штрафных слагаемых уже ищет решение с минимально возможной нормой весов среди всех допустимых. При небольшом числе обучающих примеров именно эта встроенная регуляризация не даёт модели «выучить наизусть» единичные случайности выборки — эффект похож на то, зачем нужна регуляризация в линейных моделях, но получен не добавлением штрафа к готовой функции потерь, а самой геометрической постановкой задачи как поиска максимального зазора.

Практика: 30 заданий

Базовые (задания 1-10)

Задание 1: Найдено решение SVM с $w=(3,4)$. Найди ширину зазора.

Задание 2: Найдено решение с $w=(0,2)$. Найди ширину зазора.

Задание 3: Точка $x_i$ с $y_i=+1$ и $w^\top x_i+b=1$. Является ли эта точка опорным вектором?

Задание 4: Множители Лагранжа для 5 точек: $\alpha=(0;\ 0{,}3;\ 0;\ 0{,}7;\ 0)$. Сколько опорных векторов в этой модели?

Задание 5: Точка с $y_i=+1$ и решающей функцией $w^\top x_i+b=0{,}5$. Найди минимально необходимое значение $\xi_i$.

Задание 6: Найди значение RBF-ядра между $x_i=(0,0)$ и $x_j=(2,0)$ при $\gamma=1$.

Задание 7: Найди значение полиномиального ядра $K(x_i,x_j)=(x_i^\top x_j+1)^2$ для $x_i=(1,1)$, $x_j=(2,0)$.

Задание 8: Обучены две модели: с $C=0{,}01$ и с $C=500$. Какая модель, скорее всего, точнее на обучающей выборке, но рискует хуже обобщаться на новые данные?

Задание 9: Верно ли, что удаление из обучающей выборки точки с $\alpha_i=0$ может изменить найденную разделяющую гиперплоскость?

Задание 10: Объясни своими словами, почему SVM ищет именно гиперплоскость с максимальным зазором, а не просто любую разделяющую границу.

Средние (задания 11-20)

Задание 11: Прямая задача жёсткого зазора для двух точек: $x_1=(2,0)$, $y_1=+1$; $x_2=(-2,0)$, $y_2=-1$. Найди оптимальные $w^*$, $b^*$ и ширину зазора (по симметрии оптимальная прямая — вертикальная ось).

Задание 12: Датасет: $x_1=(1,0)$, $y_1=+1$, $\alpha_1=0{,}4$; $x_2=(-1,0)$, $y_2=-1$, $\alpha_2=0{,}4$. Восстанови $w^*$.

Задание 13 (машинное обучение): По условию задания 12 классифицируй новую точку $x_{\text{нов}}=(0{,}5,\ 1)$, если $b^*=0$.

Задание 14: Найди RBF-ядро для $x_i=(1,1)$, $x_j=(1,1)$ при любом $\gamma>0$.

Задание 15: При обучении получены Train accuracy и Val accuracy для трёх значений $C$: $C=0{,}01\to(0{,}75;\ 0{,}74)$, $C=1\to(0{,}90;\ 0{,}88)$, $C=100\to(0{,}98;\ 0{,}80)$. Какое значение $C$ стоит выбрать?

Задание 16 (машинное обучение): Датасет с двумя классами, где класс $+1$ окружён классом $-1$ со всех сторон (как в примере из раздела про ядра). Почему линейное ядро здесь не сработает, независимо от значения $C$?

Задание 17: Верно ли утверждение: «SVM с полиномиальным ядром степени $p=1$ и $r=0$ эквивалентен линейному SVM»?

Задание 18: При $\gamma=0{,}001$ и при $\gamma=50$ обучены две модели RBF-SVM на одном датасете. У какой из них граница, скорее всего, будет более изрезанной?

Задание 19 (машинное обучение): Объясни, почему SVM особенно уместен в задаче классификации текстов, где документов 2000, а уникальных слов-признаков 50000.

Задание 20: Для датасета с $N=8$ точек лишь 3 оказались опорными векторами после обучения. Что произойдёт с решением, если добавить в выборку ещё одну точку, которая гарантированно окажется внутри своего класса, далеко от границы зазора?

Продвинутые (задания 21-30)

Задание 21 (машинное обучение): Датасет: $x_1=(0,2)$, $y_1=+1$; $x_2=(0,-2)$, $y_2=-1$; $x_3=(0,5)$, $y_3=+1$ (дальше от границы, чем $x_1$). Определи, какая из точек $x_1$ или $x_3$ с большей вероятностью станет опорным вектором, и почему.

Задание 22: Двойственная задача SVM для трёх точек дала $\alpha=(0{,}2;\ 0{,}3;\ 0{,}0)$ с метками $y=(+1,-1,+1)$. Проверь ограничение $\sum_i\alpha_iy_i=0$.

Задание 23: Дана матрица $Q=D_yKD_y$ для двух точек с $K=\begin{pmatrix}4&1\\1&4\end{pmatrix}$ и $y=(1,-1)$. Найди $Q$.

Задание 24 (машинное обучение): Почему при увеличении $\gamma$ в RBF-ядре число опорных векторов в обученной модели обычно растёт?

Задание 25: Прямая задача мягкого зазора для точки с $y_i=-1$ и $w^\top x_i+b=1{,}5$. Найди минимально необходимое $\xi_i$.

Задание 26 (машинное обучение): Объясни разницу между тем, что определяет решение в SVM (опорные векторы), и тем, что определяет решение в KNN (урок 314, все $k$ ближайших соседей на этапе предсказания).

Задание 27: Для матрицы $Q=\begin{pmatrix}4&-1\\-1&4\end{pmatrix}$ из задания 23 проверь, положительно ли она полуопределена (через определитель $2\times2$-подматриц или собственные значения).

Задание 28 (машинное обучение): На соревновании по классификации с 300 примерами и 4000 признаками (после векторизации текста) один участник использует SVM с линейным ядром, другой — градиентный бустинг (урок 318) с деревьями глубины 6. Какая модель, скорее всего, окажется устойчивее к переобучению в этом конкретном режиме данных, и почему?

Задание 29: Двойственная задача SVM для RBF-ядра: покажи, почему матрица $Q=D_yKD_y$ остаётся положительно полуопределённой при любом $\gamma>0$, если известно, что RBF-ядро всегда удовлетворяет теореме Мерсера.

Задание 30 (машинное обучение): Собери воедино: опиши своими словами всю цепочку от постановки задачи максимального зазора до вызова sklearn.svm.SVC(kernel="rbf", C=1.0, gamma="scale").fit(X, y), указав, на каком шаге используется каждый из уроков 214, 279, 282, 283.

Частые ошибки

Ошибка 1. Путают понятия «максимальный зазор» и «максимальная точность на обучающей выборке».

Как выглядит: «SVM с жёстким зазором всегда лучше SVM с мягким зазором, потому что жёсткий зазор не допускает ни одной ошибки классификации».

Почему возникает: название «жёсткий» интуитивно воспринимается как «более строгий, а значит более качественный», хотя на самом деле жёсткий зазор — это частный, вырожденный случай ($C=\infty$), применимый только к идеально линейно разделимым данным, и почти всегда хуже мягкого зазора на реальных зашумлённых датасетах.

Как правильно: оценивать не по тому, допускает ли модель нарушения зазора на обучении, а по валидационной метрике — мягкий зазор с разумным $C$ почти всегда обобщается лучше, чем попытка любой ценой добиться нулевого числа нарушений.

Ошибка 2. Считают, что опорных векторов всегда мало, независимо от структуры данных.

Как выглядит: «SVM всегда даёт компактное решение с горсткой опорных векторов, поэтому он эффективен на любых данных».

Почему возникает: обобщение частного эмпирического наблюдения (часто действительно опорных векторов немного) до универсального правила.

Как правильно: число опорных векторов напрямую зависит от структуры данных и выбранных гиперпараметров — при сильно перекрывающихся классах, маленьком $C$ или большом $\gamma$ (см. задание 24) число опорных векторов может приближаться к размеру всей обучающей выборки, и тогда преимущество компактности решения исчезает.

Ошибка 3. Путают роль $C$ в SVM с ролью коэффициента регуляризации $\lambda$ в Ridge/Lasso (урок 312) — считают, что большой $C$ означает сильную регуляризацию.

Как выглядит: «увеличим $C$, чтобы модель регуляризовалась сильнее и меньше переобучалась».

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

Как правильно: $C$ в SVM умножает штраф за нарушение зазора, а не штраф за сложность модели, — поэтому большой $C$ означает слабую регуляризацию (модель гонится за точностью на обучении), а маленький $C$ означает сильную регуляризацию (модель жертвует точностью ради широкого зазора); это обратная логика по сравнению с $\lambda$ в Ridge/Lasso, где больший $\lambda$ означает более сильную регуляризацию.

Ошибка 4. Пытаются применить ядерный трюк к прямой (не двойственной) формулировке SVM.

Как выглядит: «раз ядро задаёт отображение $\phi(x)$, просто подставим $\phi(x_i)$ вместо $x_i$ в прямую задачу $\min\frac12\|w\|^2$».

Почему возникает: kernel trick воспринимается как отдельная универсальная операция, применимая к любой формулировке SVM, а не как следствие конкретной алгебраической структуры именно двойственной задачи (урок 282, ошибка 6 в этом же ключе).

Как правильно: в прямой задаче вектор весов $w$ должен жить в том же пространстве, что и преобразованные признаки $\phi(x)$ — для RBF-ядра это бесконечномерное пространство, и явно работать с ним невозможно; ядерный трюк работает только в двойственной задаче, где $\phi(x)$ участвует исключительно внутри скалярных произведений, которые целиком заменяются на $K(x_i,x_j)$.

Ошибка 5. Забывают о необходимости масштабирования признаков перед обучением SVM.

Как выглядит: обучают SVC на признаках с сильно разным масштабом (например, «возраст» от 0 до 100 и «доход» от 0 до 10 000 000) без предварительной стандартизации.

Почему возникает: SVM формально не требует нормальности распределения признаков, и ошибка ненаглядна на первый взгляд — модель обучается и выдаёт какой-то результат без явных сообщений об ошибке.

Как правильно: и вычисление зазора через $\|w\|$, и особенно RBF-ядро через $\|x_i-x_j\|^2$ крайне чувствительны к масштабу признаков — признак с большим численным диапазоном начинает доминировать над остальными в вычислении расстояния; перед обучением SVM (в отличие, например, от случайного леса из урока 317, для которого масштабирование не требуется) практически всегда нужен StandardScaler или аналогичное преобразование.

Ошибка 6. Считают, что SVM возвращает вероятности классов напрямую, как логистическая регрессия.

Как выглядит: используют decision_function() SVM как готовую вероятность принадлежности классу.

Почему возникает: решающая функция $w^\top x+b$ действительно похожа по форме на логит в логистической регрессии (урок 313), и легко предположить, что достаточно применить сигмоиду — но у стандартного SVM нет вероятностной интерпретации, встроенной в саму задачу оптимизации.

Как правильно: значение decision_function() — это подписанное расстояние до разделяющей гиперплоскости (в масштабе $\|w\|$), а не вероятность; для получения откалиброванных вероятностей нужно явно включить probability=True в SVC, что запускает дополнительную процедуру калибровки (Платтово масштабирование) поверх уже обученной модели, а не является частью исходной задачи КП.

Главное запомнить

• SVM ищет среди всех разделяющих гиперплоскостей ту, что максимизирует зазор — минимальное расстояние до ближайших точек обоих классов, — что обосновано теорией Вапника-Червоненкиса как способ снизить эффективную сложность классификатора.

• Опорные векторы — это точки, лежащие ровно на границе зазора ($\alpha_i^*>0$); только они определяют разделяющую гиперплоскость, все остальные точки можно удалить из выборки без изменения решения.

• Прямая задача SVM — это задача квадратичного программирования $\min\frac12\|w\|^2$ при линейных ограничениях, выпуклая по построению (гессиан — единичная матрица), что подробно разобрано в уроке 283.

• Двойственная задача SVM выводится через лагранжиан и условия KKT (уроки 214, 279, 282) и имеет ровно $N$ переменных — множителей $\alpha_i$ — независимо от размерности признакового пространства.

• Мягкий зазор с параметром $C$ разрешает точкам нарушать зазор за штраф $C\xi_i$; большой $C$ означает слабую регуляризацию (модель точнее на обучении, но рискует переобучиться), малый $C$ — сильную регуляризацию (шире зазор, больше допущенных нарушений).

• Ядерный трюк заменяет скалярное произведение $\langle x_i,x_j\rangle$ в двойственной задаче на произвольную ядерную функцию $K(x_i,x_j)$, эквивалентную скалярному произведению в неявном пространстве более высокой (возможно, бесконечной) размерности, без явного вычисления координат в этом пространстве.

• RBF-ядро $K(x_i,x_j)=\exp(-\gamma\|x_i-x_j\|^2)$ — самое популярное ядро на практике; параметр $\gamma$ управляет «радиусом влияния» каждой точки — большое $\gamma$ даёт более изрезанную, склонную к переобучению границу.

• Решение SVM единственно и детерминированно при фиксированных гиперпараметрах — в отличие от случайного леса (урок 317) и градиентного бустинга (урок 318), в SVM нет случайных элементов, потому что это решение выпуклой задачи с единственным глобальным минимумом.

• SVM особенно силён в режиме «мало обучающих примеров, много признаков» — встроенная в постановку задачи регуляризация через $\min\|w\|^2$ не даёт модели переобучиться даже там, где число признаков превышает число примеров.

• $C$ и $\gamma$ подбираются совместно через кросс-валидацию (урок 306), а не по отдельности — они управляют разными, но взаимосвязанными аспектами сложности итоговой границы.

Связь с темами курса

Этот урок — прямая точка сборки для четырёх уроков математического блока курса. Урок 214 («Условный экстремум, метод Лагранжа») дал базовую технику поиска экстремума при ограничениях-равенствах — параллельность градиентов целевой функции и ограничения. Урок 279 («Условия оптимальности KKT») расширил эту технику на ограничения-неравенства через условие дополняющей нежёсткости — именно оно математически объясняет, почему решение SVM определяется лишь несколькими опорными векторами, а не всей обучающей выборкой. Урок 282 («Двойственность») показал общий механический рецепт перехода от прямой задачи к двойственной через лагранжиан и применил его именно к SVM, получив ключевое наблюдение: данные входят в двойственную задачу только через скалярные произведения — единственная причина, по которой ядерный трюк вообще возможен. Урок 283 («Квадратичное программирование») довёл этот вывод до конца, явно выписал матрицу $Q=D_yKD_y$, доказал выпуклость через теорему Мерсера и объяснил, что происходит внутри libsvm, когда вызывается .fit().

Сегодняшний урок не повторяет ни один из этих выводов заново, а показывает, как они складываются в готовую, практически применимую модель: постановка задачи максимального зазора — это геометрическая интерпретация урока 214 и 279 применительно к линейной классификации; переход к двойственной задаче и ядерному трюку — прямое следствие урока 282; гарантия глобальной сходимости QP-решателя SMO — следствие доказанной в уроке 283 выпуклости. Если сравнить SVM с моделями двух предыдущих уроков курса — случайным лесом (317) и градиентным бустингом (318), — разница философий становится особенно наглядной: и лес, и бустинг решают задачу эвристически, через построение множества деревьев решений, тогда как SVM решает задачу точно, как единственную выпуклую задачу оптимизации с доказанными гарантиями сходимости к глобальному минимуму.

Интересные факты

Владимир Вапник и Алексей Червоненкис разработали основы теории, на которой держится SVM, ещё в 1960-х годах в СССР — задолго до того, как метод получил современное название и стал известен на Западе; работа долгое время была относительно малоизвестна за пределами советской математической школы и получила широкое международное признание только после эмиграции Вапника в США в начале 1990-х.

Ключевая статья 1995 года «Support-Vector Networks» Вапника и Кортес, введшая мягкий зазор, стала одной из самых цитируемых работ в истории машинного обучения — по разным подсчётам, число её цитирований исчисляется десятками тысяч, что делает её одной из самых влиятельных статей в области.

Алгоритм SMO (Sequential Minimal Optimization, «последовательная минимальная оптимизация»), который Джон Платт предложил в 1998 году специально для эффективного обучения SVM, и сегодня, спустя более четверти века, лежит в основе большинства библиотечных реализаций SVM, включая libsvm внутри scikit-learn — редкий случай алгоритма оптимизации, который практически не менялся в своей основе на протяжении десятилетий.

Название «машина опорных векторов» (support vector machine) исторически возникло из «векторов», которые «поддерживают» (support) разделяющую гиперплоскость — в буквальном геометрическом смысле, как колонны поддерживают крышу здания: убери опорный вектор — и положение границы может измениться, убери любую другую точку — и ничего не произойдёт.

Лайфхаки

Перед обучением SVM всегда применяй масштабирование признаков (StandardScaler или MinMaxScaler) — без этого шага и вычисление зазора, и особенно RBF-ядро окажутся искажены признаками с большим численным диапазоном, и результат может оказаться заметно хуже, чем способна дать модель в принципе.

Начинай подбор гиперпараметров с kernel="rbf" и грубой логарифмической сетки для $C$ и $\gamma$ (например, степени десяти: $0{,}001,\ 0{,}01,\ 0{,}1,\ 1,\ 10,\ 100$) — оба параметра действуют мультипликативно на сложность границы, и линейная сетка почти всегда неэффективна.

Если обучающих примеров больше нескольких десятков тысяч, обычный SVC с нелинейным ядром может обучаться неприемлемо долго (сложность решения QP растёт быстрее линейной по числу примеров) — попробуй sklearn.svm.LinearSVC (оптимизированную под линейное ядро реализацию) или явное приближение ядра через sklearn.kernel_approximation.Nystroem в паре с обычным линейным классификатором.

После обучения всегда проверяй model.support_vectors_.shape[0] относительно общего размера выборки — если опорными векторами оказалось подавляющее большинство точек, это сигнал, что модель, скорее всего, переусложнена (слишком большой $\gamma$ или слишком большой $C$) и стоит пересмотреть сетку гиперпараметров.

Если нужны вероятности классов, а не просто метка, явно включай probability=True при создании SVC — и помни, что это запускает дополнительную, более медленную процедуру калибровки (пятикратную внутреннюю кросс-валидацию по умолчанию), а не бесплатный побочный продукт основного решения задачи КП.

Для задач с очень большим числом признаков и относительно небольшим числом примеров (текстовая классификация, биоинформатика) начинай не с RBF, а с kernel="linear" — часто линейное ядро уже даёт достойное качество за счёт высокой размерности исходного признакового пространства, при этом обучается заметно быстрее и даёт более интерпретируемые веса $w$.

Сегодняшний урок закрывает большую дугу курса: четыре отдельных, на первый взгляд самостоятельных математических темы — условный экстремум, условия KKT, двойственность, квадратичное программирование — оказались не разрозненными главами учебника оптимизации, а последовательными шагами одного и того же вывода, который заканчивается работающей, широко используемой моделью машинного обучения. В следующий раз, когда ты вызовешь SVC(kernel="rbf").fit(X, y) и получишь готовую разделяющую границу за долю секунды, — за этой строкой будет стоять не чёрный ящик, а вся цепочка рассуждений, которую ты теперь можешь восстановить от первой до последней формулы.