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

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

История

Метод опорных векторов был разработан в 1960-х годах в лабораториях Bell Labs Владимиром Вапником и его коллегами (Алексей Червоненкис, Бернард Босер, Изабель Гийон). Первоначальная версия алгоритма (линейный SVM) была опубликована в 1963 году. Однако широкое признание метод получил только в 1990-х годах, когда Вапник и его группа предложили использовать «ядра» (kernel trick) для построения нелинейных классификаторов. В 1995 году вышла ключевая работа Вапника «The Nature of Statistical Learning Theory», где были формализованы теоретические основы SVM. С 2000-х годов метод активно применяется в биоинформатике, анализе текстов, компьютерном зрении и других областях.

Основные принципы

Линейно разделимый случай

В простейшем случае задача бинарной классификации состоит в разделении двух классов точек в n-мерном пространстве. SVM строит гиперплоскость, которая разделяет классы с максимальным зазором. Гиперплоскость задается уравнением:

w·x + b = 0,

где w — вектор нормали, b — смещение. Для точки x_i её класс определяется знаком функции f(x_i) = sign(w·x_i + b).

Опорными векторами называются точки обучающей выборки, которые лежат на границе зазора (то есть на расстоянии 1/||w|| от гиперплоскости). Только эти точки влияют на положение разделяющей границы; остальные точки можно удалить без изменения решения. Задача оптимизации сводится к минимизации ||w||² при условии, что все точки классифицированы правильно:

min (1/2) ||w||² при y_i (w·x_i + b) ≥ 1 для всех i.

Линейно неразделимый случай

Для данных, которые нельзя разделить гиперплоскостью без ошибок, вводится понятие «мягкого зазора» (soft margin). В этом случае допускаются ошибки классификации, но за них вводится штраф. Задача принимает вид:

min (1/2) ||w||² + C Σ ξ_i,

где ξ_i ≥ 0 — переменные, характеризующие величину ошибки для i-го примера, а C — гиперпараметр, регулирующий баланс между шириной зазора и количеством ошибок. Чем больше C, тем меньше допускается ошибок на обучающей выборке, но выше риск переобучения.

Нелинейные границы и ядра

Для построения нелинейных разделяющих поверхностей используется «ядерный трюк» (kernel trick). Исходные данные отображаются в пространство более высокой размерности с помощью функции φ(x). В этом новом пространстве данные могут стать линейно разделимыми. При этом скалярное произведение в новом пространстве заменяется на ядро K(x_i, x_j) = φ(x_i)·φ(x_j), которое можно вычислить без явного построения φ. Наиболее распространённые ядра:

• Линейное: K(x, y) = x·y.
• Полиномиальное: K(x, y) = (γ x·y + r)^d.
• Радиальная базисная функция (RBF): K(x, y) = exp(-γ ||x - y||²).
• Сигмоидное: K(x, y) = tanh(γ x·y + r).

Выбор ядра и его параметров (например, γ в RBF) существенно влияет на качество модели.

Алгоритм обучения

Обучение SVM сводится к решению задачи квадратичного программирования (QP). Для этого используются различные методы:

• Последовательная минимальная оптимизация (SMO): разбивает задачу на подзадачи, решая их аналитически. Наиболее распространённый алгоритм.
• Метод опорных векторов с наименьшими квадратами (LS-SVM): сводит задачу к решению системы линейных уравнений.
• Стохастический градиентный спуск (SGD): применяется для больших выборок.

На практике для обучения SVM используются библиотеки, такие как LIBSVM, scikit-learn (Python), e1071 (R) и другие.

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

Преимущества

• Эффективность в пространствах высокой размерности: SVM хорошо работает, когда число признаков превышает число примеров.
• Память: в модели хранятся только опорные векторы, что экономит память.
• Универсальность: с помощью ядер можно строить нелинейные границы.
• Теоретическая обоснованность: SVM основан на принципе минимизации структурного риска, что снижает риск переобучения.

Недостатки

• Чувствительность к масштабу признаков: перед обучением необходимо нормализовать данные.
• Сложность интерпретации: особенно при использовании нелинейных ядер.
• Выбор гиперпараметров: качество модели сильно зависит от C и параметров ядра.
• Вычислительная сложность: обучение может быть медленным на больших выборках (O(n²) или O(n³)).
• Не подходит для многоклассовой классификации напрямую: требуется разбиение на бинарные задачи (one-vs-one, one-vs-rest).

Применение

Классификация текстов и анализ тональности

SVM часто используется для категоризации документов, спам-фильтрации и определения тональности отзывов. Благодаря работе с разреженными данными (мешок слов) метод показывает высокую точность.

Биоинформатика

В задачах классификации генов, прогнозирования белковых структур и анализа микрочипов SVM применяется из-за малого числа образцов и большого числа признаков.

Компьютерное зрение

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

Финансы

В кредитном скоринге, прогнозировании банкротств и обнаружении мошеннических транзакций SVM применяется для бинарной классификации.

Медицина

Диагностика заболеваний (например, рака) на основе данных МРТ, КТ или генетических маркеров.

Разновидности

• SVR (Support Vector Regression): адаптация метода для задач регрессии. Вместо разделяющей полосы строится «труба» заданной ширины ε, внутри которой ошибка не штрафуется.
• One-class SVM: используется для обнаружения аномалий. Обучается только на одном классе (нормальных данных) и определяет, принадлежит ли новый объект к этому классу.
• Nu-SVM: вариант с другим параметром ν, который ограничивает долю опорных векторов и ошибок.

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

• Термин «опорные векторы» (support vectors) введён Вапником и Червоненкисом в 1974 году.
• SVM часто называют «методом с наибольшим зазором» (maximum margin classifier).
• В 2006 году на соревновании по классификации рукописных цифр (MNIST) SVM показал результат, близкий к человеческому, используя только пиксельные значения.
• В России метод опорных векторов активно развивался в Институте проблем передачи информации РАН.

Критика

Несмотря на популярность, SVM критикуется за «чёрный ящик» при использовании сложных ядер, а также за то, что он не даёт вероятностной оценки (только метку класса). Для получения вероятностей требуется дополнительная калибровка (например, метод Платта). Кроме того, в эпоху глубокого обучения SVM уступает нейронным сетям в задачах с очень большими объёмами данных (миллионы примеров), но остаётся предпочтительным выбором для малых и средних выборок.

Источники

• Vapnik, V. N. (1998). Statistical Learning Theory. Wiley.
• Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297.
• Cristianini, N., & Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press.
• Platt, J. C. (1999). Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods (pp. 185–208). MIT Press.
• Шапиро, Л., & Стокман, Дж. (2006). Компьютерное зрение. Бином.