SVM и kernel trick

SVM (метод опорных векторов) — классификатор максимального зазора: границу определяют только опорные векторы, а kernel trick разделяет линейно неразделимое. Разбираем margin, параметры C и gamma, RBF-ядро — вечную классику собеседований.

Интуиция: самая широкая улица

Два класса точек на плоскости можно разделить бесконечным числом прямых. Какая лучше? SVM (support vector machine) отвечает: та, что проходит по середине самой широкой «улицы» между классами — максимально далеко и от тех, и от других. Расстояние от границы до ближайших точек называется зазором (margin), и SVM его максимизирует.

Зачем? Новые данные никогда не совпадают со старыми: они слегка «дрожат» вокруг обучающих точек. Если граница прижата вплотную к одному из классов, малейший сдвиг новой точки перебрасывает её через границу. Широкий зазор — это запас прочности, и на практике он означает лучшее обобщение (generalization).

Как это работает: опорные векторы и параметр C

Модель — обычная линейная граница:

SVM ищет w и b, при которых улица максимально широка, а все точки — за её пределами со своей стороны. Ключевое следствие: положение границы определяют только точки, лежащие ровно на краях улицы, — опорные векторы (support vectors). Остальные точки можно удалить, подвинуть (не залезая в улицу) — граница не шелохнётся. Поэтому обученный SVM хранит не всю выборку, а лишь опорные векторы.

Реальные данные зашумлены и часто линейно неразделимы, поэтому используют мягкий зазор (soft margin): отдельным точкам разрешают нарушать улицу за штраф. Компромисс регулирует гиперпараметр C: большой C — нарушения дорогие, улица узкая, модель подстраивается под каждую точку и рискует переобучиться; маленький C — улица широкая и гладкая, но часть точек классифицируется с ошибкой (риск недообучения).

Kernel trick: разделяем неразделимое

Что делать, если классы «кольцом» — один внутри другого? Никакая прямая не поможет. Идея: перевести данные в пространство большей размерности, где они разделимы. Например, для кольца добавим третий признак z = x² + y² (квадрат расстояния от центра) — и внутренний класс окажется «ниже» внешнего, их разделит обычная плоскость.

Трюк (kernel trick) в том, что явно строить это отображение φ не нужно. Математика SVM использует точки только через скалярные произведения, а ядро (kernel) считает скалярное произведение сразу в новом пространстве:

Мы получаем разделение в пространстве огромной (для RBF — бесконечной) размерности по цене вычислений в исходном. Самое популярное ядро — RBF (radial basis function):

Это «мера похожести»: 1 для совпадающих точек, быстро падает с расстоянием. Параметр γ (gamma) задаёт радиус влияния точки: маленькая gamma — влияние широкое, граница гладкая; большая — каждая точка влияет только на ближайшую окрестность, и граница распадается на «островки» вокруг обучающих точек — классическое переобучение. Полиномиальное ядро K(a, b) = (a·b + c)^d соответствует добавлению всех произведений признаков до степени d — им когда-то решали распознавание рукописных цифр.

SVM сегодня: зачем он на собеседовании

На табличных данных SVM уступил место градиентному бустингу, а на изображениях и текстах — нейросетям. Главная практическая причина — масштабирование: ядровому SVM нужна матрица ядра n×n и обучение стоимостью O(n²)–O(n³) по числу примеров, так что на миллионах строк он неподъёмен (линейные варианты вроде LIBLINEAR живее, но проигрывают бустингу по качеству).

Тем не менее теория SVM — вечный материал собеседований, потому что проверяет понимание сразу трёх фундаментальных идей: обобщение через максимальный зазор, разреженность решения (важны только опорные векторы) и превращение нелинейной задачи в линейную через ядра. А сама kernel-идея — «сходство как скалярное произведение» — живёт в современных архитектурах: в attention веса softmax(QKᵀ) — это в точности скалярные произведения запросов и ключей как мера похожести токенов, и существуют «линейные attention», построенные буквально на ядрах.