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

Метод опорных векторов (англ. Support Vector Machine, SVM) — совокупность алгоритмов обучения с учителем, применяемых для задач классификации, регрессионного анализа и обнаружения выбросов. Основная идея метода заключается в построении разделяющей гиперплоскости в пространстве признаков, которая максимизирует зазор (маржу) между классами объектов. Метод был разработан в 1960-е годы Владимиром Вапником и Алексеем Червоненкисом и получил широкое распространение в 1990-е годы после введения в него ядровых функций.

¶Основная концепция

В задаче бинарной классификации обучающая выборка представляет собой множество пар (xᵢ, yᵢ), где xᵢ — вектор признаков в n-мерном пространстве, а yᵢ — метка класса, принимающая значения +1 или −1. Алгоритм SVM ищет гиперплоскость, задаваемую уравнением w·x − b = 0, которая разделяет точки разных классов. Среди всех возможных разделяющих гиперплоскостей выбирается та, для которой расстояние до ближайших точек каждого класса (так называемых опорных векторов) максимально. Эта гиперплоскость называется оптимальной разделяющей гиперплоскостью.

Максимизация зазора повышает обобщающую способность модели — её способность корректно классифицировать объекты, не входившие в обучающую выборку. Математически задача сводится к минимизации нормы вектора весов ‖w‖ при условии, что все обучающие точки удовлетворяют ограничению yᵢ(w·xᵢ − b) ≥ 1.

¶Жёсткий и мягкий зазоры

В первоначальной формулировке (жёсткий зазор) предполагалось, что данные линейно разделимы. Однако на практике это условие выполняется редко. Для работы с зашумлёнными и перекрывающимися данными Кортес и Вапник в 1995 году предложили модификацию с мягким зазором. В этой версии вводится набор дополнительных переменных ξᵢ (штрафов), которые допускают нарушение границы зазора для отдельных точек. Целевая функция приобретает вид:

(1/2)‖w‖² + C·Σξᵢ → min

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

¶Ядровые функции

Ключевым расширением метода стало применение так называемого ядрового трюка. Если данные не разделимы линейно в исходном пространстве признаков, их можно отобразить в пространство более высокой размерности с помощью некоторого преобразования φ(x). Вычисления в этом пространстве были бы дорогостоящими, однако благодаря теореме Мерсера скалярное произведение в новом пространстве можно заменить функцией ядра K(xᵢ, xⱼ) = φ(xᵢ)·φ(xⱼ), которая вычисляется непосредственно в исходном пространстве.

Наиболее распространённые ядра:

линейное: K(xᵢ, xⱼ) = xᵢ·xⱼ;
полиномиальное: K(xᵢ, xⱼ) = (γ·xᵢ·xⱼ + r)^d;
радиальная базисная функция (RBF): K(xᵢ, xⱼ) = exp(−γ·‖xᵢ − xⱼ‖²);
сигмоидальное: K(xᵢ, xⱼ) = tanh(γ·xᵢ·xⱼ + r).

Выбор ядра и его параметров (например, γ в RBF) существенно влияет на качество модели. Параметр γ определяет радиус влияния отдельной обучающей точки: малые значения дают гладкую границу, большие — более сложную и изрезанную.

¶Решение задачи оптимизации

Обучение SVM сводится к решению задачи выпуклой квадратичной оптимизации. Прямое решение этой задачи требует обращения матрицы размером n×n, что делает метод неприменимым для больших выборок. Для практического использования разработаны специальные алгоритмы декомпозиции, наиболее известным из которых является SMO (Sequential Minimal Optimization), предложенный Джоном Платтом в 1998 году. Алгоритм SMO разбивает большую задачу оптимизации на последовательность минимальных подзадач, каждая из которых решается аналитически, что позволяет обучать SVM на выборках с тысячами и миллионами примеров.

¶Многоклассовая классификация

Базовый алгоритм SVM решает задачу бинарной классификации. Для работы с задачами, содержащими более двух классов, применяются стратегии сведения к бинарным задачам. Стратегия «один против всех» (one-vs-rest) обучает K классификаторов, каждый из которых отделяет один класс от остальных; итоговый класс определяется по максимальному отклику. Стратегия «один против одного» (one-vs-one) обучает K(K−1)/2 классификаторов для всех пар классов и использует голосование. На практике стратегия «один против одного» часто оказывается более точной, хотя и требует большего числа моделей.

¶Преимущества и недостатки

К достоинствам метода опорных векторов относят:

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

Недостатки метода:

чувствительность к выбору параметров (в первую очередь C и параметров ядра), требующая перебора или оптимизации;
слабая интерпретируемость нелинейных моделей;
вычислительная сложность обучения на очень больших выборках, хотя алгоритм SMO существенно смягчает эту проблему;
необходимость масштабирования признаков перед обучением, так как метод чувствителен к разным шкалам измерений.

¶Применение

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

распознавание изображений и рукописного текста;
классификация текстов и тональности высказываний;
биоинформатика (предсказание функций белков, классификация генов);
медицинская диагностика (анализ снимков, выявление заболеваний по биомаркерам);
геоинформационные системы (классификация спутниковых снимков);
финансовый скоринг и прогнозирование банкротства;
обнаружение аномалий в промышленных системах.

До появления и широкого распространения градиентного бустинга и глубоких нейронных сетей SVM считался одним из лучших методов «из коробки» для структурированных данных умеренного размера. В задачах с небольшим числом обучающих примеров и высокой размерностью признаков SVM по-прежнему демонстрирует конкурентоспособные результаты.

¶Связь с другими методами

SVM тесно связан с логистической регрессией и перцептроном: все три метода строят линейные разделяющие поверхности, но отличаются функцией потерь. SVM использует шарнирную функцию потерь (hinge loss), которая штрафует только точки, лежащие внутри зазора или с ошибочной стороны границы. В отличие от нейронных сетей, обучение SVM гарантированно находит глобальный оптимум, однако SVM не масштабируется на задачи с объёмами данных, характерными для глубокого обучения.