Support Vector Machine (SVM)

Машина опорных векторов (SVM) — это алгоритм обучения с учителем, который классифицирует данные, находя гиперплоскость, разделяющую два класса с максимально возможным отступом — расстоянием между границей и ближайшими обучающими точками каждого класса. Только эти ближайшие точки — опорные векторы — определяют границу. Ядерные функции позволяют SVM обучаться на нелинейных границах, а модификации алгоритма подходят для регрессии и обнаружения выбросов. Владимир Вапник и его коллеги разработали этот метод в AT&T Bell Labs: версию с ядром — в 1992 году, а используемая сегодня формулировка с мягким отступом была опубликована Кортесом и Вапником в 1995 году. До появления глубокого обучения SVM были одними из самых точных классификаторов для текста, изображений и биологических данных и по-прежнему хорошо работают на небольших и средних наборах данных с большим количеством признаков.

Как работают SVM#

Линейная SVM предсказывает класс по знаку w·x + b, поэтому её граница принятия решений — гиперплоскость w·x + b = 0. Если масштабировать веса так, чтобы для ближайших точек выполнялось |w·x + b| = 1, ширина отступа составит 2/‖w‖. При обучении отступ максимизируется за счёт минимизации ‖w‖² при условии, что каждая обучающая точка находится по правильную сторону от него. Реальные классы пересекаются, поэтому SVM с мягким отступом позволяет точкам пересекать отступ, а величину штрафа задаёт параметр регуляризации C. Функция потерь на основе шарнирного отступа не штрафует точки, правильно классифицированные за пределами отступа, а для остальных назначает штраф, линейно растущий с величиной нарушения. Малое значение C допускает больше нарушений и даёт более широкий и плавный отступ, а большое значение C точнее подгоняет модель под обучающие данные, повышая риск переобучения. В обученной модели ненулевые веса имеют только точки на отступе или за его неверной стороной; это опорные векторы. Перемещение любой другой точки, пока она не пересечёт отступ, не изменит границу.

Ядерный трюк#

Если гиперплоскость не разделяет классы, можно отобразить данные в пространство большей размерности, где разделение станет возможным: два концентрических кольца в 2D можно разделить плоскостью, добавив третий признак x₁² + x₂², который показывает расстояние каждой точки от центра. В двойственной форме обучение и предсказание SVM используют данные только через скалярные произведения пар точек, поэтому ядерная функция k(x, x′) может напрямую возвращать скалярное произведение в отображённом пространстве, не вычисляя сами отображённые координаты. Это и есть ядерный трюк. Часто используются линейное, полиномиальное ядра и радиальная базисная функция (RBF) exp(−γ‖x − x′‖²), где γ определяет радиус влияния каждого опорного вектора. В этом примере для двух концентрических колец обучается SVC из scikit-learn с линейным ядром и RBF-ядром:

from sklearn.datasets import make_circles
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

# Two concentric rings: no straight line separates the classes
X, y = make_circles(n_samples=500, factor=0.4, noise=0.1, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)

for kernel in ("linear", "rbf"):
    clf = SVC(kernel=kernel, C=1.0)
    clf.fit(X_train, y_train)
    print(f"{kernel}: test accuracy {clf.score(X_test, y_test):.2f}, support vectors {clf.n_support_.sum()}")

Линейное ядро набирает 0,43 на отложенных точках — хуже случайного угадывания — и сохраняет в качестве опорных векторов 360 из 375 обучающих точек. RBF-ядро идеально разделяет кольца (1,00), используя всего 42 опорных вектора.

Выбор ядра и гиперпараметров#

Расстояния и скалярные произведения зависят от масштаба признаков, поэтому сначала входные данные SVM стандартизируют. Практическое руководство авторов LIBSVM, библиотеки, на которой основан SVC из scikit-learn, рекомендует масштабировать признаки, начать с RBF-ядра и выбирать C и γ с помощью поиска по сетке и перекрёстной проверки. Когда признаков намного больше, чем примеров, как в текстовых данных, линейное ядро работает примерно так же хорошо и обучается гораздо быстрее. Обучение SVM с ядром занимает как минимум квадратично больше времени при увеличении числа примеров, поэтому при десятках тысяч примеров и больше точную модель с ядром заменяют линейными SVM или приближёнными ядерными признаками.

SVM в компьютерном зрении#

В классическом компьютерном зрении признаки, разработанные вручную, сочетались с линейными SVM. Детектор пешеходов Далала и Триггса 2005 года оценивал гистограммы ориентированных градиентов (HOG) с помощью линейной SVM, а детектор объектов R-CNN 2014 года классифицировал CNN-признаки каждого региона-кандидата с помощью отдельной линейной SVM для каждого класса, пока в 2015 году Fast R-CNN не заменил их слоем softmax, обучаемым вместе с сетью. Современные детекторы совместно обучают экстрактор признаков и классификатор, а SVM по-прежнему служат быстрыми классификаторами для фиксированных признаков. Линейная SVM, обученная на векторах, которые YOLO26 возвращает из model.embed() (по одному эмбеддингу на изображение), представляет собой линейный зонд, который добавляет новую категорию изображений без переобучения сети.

Применение#

• Классификация текстов: векторы частотности слов имеют десятки тысяч разреженных измерений. Линейные SVM точно разделяют темы, спам и тональность — преимущество, которое Торстен Йоахимс показал на задаче классификации текстов в 1998 году.
• Биоинформатика: в исследованиях экспрессии генов опухоли классифицируют по тысячам измеренных генов и всего нескольким десяткам или сотням пациентов. В таких условиях отступ помогает ограничить переобучение, а строковые ядра позволяют напрямую сравнивать последовательности белков.
• Обнаружение аномалий: SVM с одним классом обучается строить границу только вокруг нормальных данных и помечает точки за её пределами. Это подходит для обнаружения мошенничества и мониторинга оборудования, когда неисправности слишком редки, чтобы размечать их.
• Регрессия: регрессия на опорных векторах аппроксимирует функцию внутри трубки шириной ε, игнорирует ошибки меньше ε и оставляет в качестве опорных векторов только точки на границе трубки или за её пределами.

SVM и родственные алгоритмы#

• Метод k ближайших соседей (KNN): хранит весь обучающий набор и во время предсказания сравнивает каждую новую точку с соседями, тогда как SVM хранит только опорные векторы.
• Деревья решений и случайные леса: разделяют данные по одному признаку за раз, не требуют масштабирования признаков и работают со смешанными числовыми и категориальными столбцами, тогда как SVM нужны числовые масштабированные данные.
• Нейронные сети: обучают отображение признаков на данных, а не задают его с помощью ядра, поэтому масштабируются до миллионов изображений, на которых SVM с ядрами работают слишком медленно.
• Логистическая регрессия: тоже обучает линейную границу, но минимизирует логарифмическую функцию потерь по всем обучающим точкам и выдаёт вероятности. SVM выдаёт знаковые расстояния до границы, а SVC из scikit-learn вычисляет вероятности только с помощью probability=True, которая выполняет масштабирование Платта с внутренней 5-блочной перекрёстной проверкой.