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

Материал из MachineLearning.

Версия от 20:36, 18 июля 2026; Amir Baidanov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM GPT-4 Turbo и проверена участником Amir Baidanov 00:32, 19 июля 2026 (MSD)

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

Содержание

1 Интуитивная картина
2 Математическая постановка для линейно разделимого случая
3 Линейно неразделимый случай и штрафные переменные
4 Ядерный трюк
5 Связь с теорией обобщения
6 Практические аспекты
7 Преимущества и недостатки
- 7.1 Преимущества
- 7.2 Недостатки
8 Сравнение с другими методами
9 Современные модификации
- 9.1 Пример: работа SVM на двумерных данных
10 Краткий вывод
11 См. также
12 Примечания
13 Литература
14 Ссылки

Интуитивная картина

Представьте, что на плоскости расположены точки двух цветов — красные и синие. Нужно провести прямую линию, которая разделяет их наилучшим образом. Если данные линейно разделимы, существует бесконечно много таких прямых. SVM выбирает ту, которая проходит на максимальном расстоянии от точек обоих классов. Это расстояние называется отступом, а точки, которые находятся ближе всего к разделяющей линии и определяют её положение, — опорными векторами.

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

Математическая постановка для линейно разделимого случая

Пусть дана обучающая выборка $\{(x_i, y_i)\}_{i=1}^N$ , где $x_i \in \mathbb{R}^d$ — признаки, $y_i \in \{-1, +1\}$ — метки классов. Требуется найти гиперплоскость

$w \cdot x + b = 0$ ,

где $w$ — вектор весов, $b$ — смещение, которая разделяет классы с максимальным отступом.

Для линейно разделимого случая существует такая гиперплоскость, что

$y_i (w \cdot x_i + b) \geq 1 \quad \forall i$ .

Отступ определяется как $\frac{2}{\|w\|}$ . Максимизация отступа эквивалентна минимизации $\frac{1}{2} \|w\|^2$ . Таким образом, задача сводится к квадратичному программированию:

$\min_{w,b} \frac{1}{2} \|w\|^2$

при ограничениях

$y_i (w \cdot x_i + b) \geq 1, \quad i = 1, \dots, N$ .

Эта задача имеет единственное решение благодаря выпуклости целевой функции и линейности ограничений.

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

В реальных задачах данные часто не являются линейно разделимыми. Для таких случаев вводятся штрафные переменные $\xi_i \geq 0$ , позволяющие нарушать ограничения:

$y_i (w \cdot x_i + b) \geq 1 - \xi_i, \quad i = 1, \dots, N$ .

Целевая функция модифицируется добавлением штрафа за нарушения:

$\min_{w,b,\xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i$ ,

где $C > 0$ — параметр регуляризации, контролирующий компромисс между максимизацией отступа и минимизацией ошибок на обучающей выборке. При $C \to \infty$ алгоритм стремится к жёсткому разделению (если это возможно), при малых $C$ — допускает больше ошибок, но строит более широкий отступ.

Ядерный трюк

Ключевое усовершенствование SVM — ядерный трюк, позволяющий строить нелинейные разделяющие поверхности без явного перехода в пространство более высокой размерности. Вместо скалярного произведения $x_i \cdot x_j$ используется ядро $K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)$ , где $\phi$ — отображение в пространство признаков.

Наиболее популярные ядра:

Линейное: $K(x, z) = x \cdot z$ ;
Полиномиальное: $K(x, z) = (x \cdot z + r)^d$ , где $d$ — степень полинома, $r$ — константа;
Радиальная базисная функция (RBF): $K(x, z) = \exp(-\gamma \|x - z\|^2)$ , где $\gamma > 0$ — параметр ширины;
Сигмоидное: $K(x, z) = \tanh(\kappa (x \cdot z) + c)$ .

Выбор ядра и его параметров критически влияет на качество классификации. RBF-ядро является наиболее универсальным и часто используется по умолчанию, но требует тщательной настройки $\gamma$ и $C$ .

Связь с теорией обобщения

SVM имеет прочное теоретическое обоснование в рамках теории Вапника — Червоненкиса. Для класса гиперплоскостей с отступом $\rho$ VC-размерность ограничена сверху величиной $\min(d, \lfloor R^2 / \rho^2 \rfloor) + 1$ , где $R$ — радиус шара, содержащего данные ^[1]. Это означает, что максимизация отступа эквивалентна минимизации VC-размерности и, следовательно, улучшению обобщающей способности. Однако на практике эта теоретическая оценка часто оказывается завышенной, и качество обобщения зависит не только от отступа, но и от свойств данных.

Практические аспекты

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

Выбор ядра и его параметров — ключевая задача при использовании SVM. Обычно применяется сеточный поиск по параметрам $C$ и $\gamma$ (для RBF-ядра) с кросс-валидацией. Рекомендуется использовать логарифмическую шкалу, например $C \in \{10^{-3}, 10^{-2}, \dots, 10^3\}$ , $\gamma \in \{10^{-3}, 10^{-2}, \dots, 10^3\}$ .

Масштабирование признаков

SVM чувствителен к масштабу признаков, поскольку ядро RBF использует евклидово расстояние. Перед обучением необходимо выполнить нормализацию или стандартизацию признаков:

$x_i' = \frac{x_i - \mu_i}{\sigma_i}$ ,

где $\mu_i$ и $\sigma_i$ — среднее и стандартное отклонение $i$ -го признака.

Вычислительная сложность

Обучение SVM требует решения задачи квадратичного программирования размера $N$ (число объектов). Сложность наилучших алгоритмов составляет $O(N^2)$ в худшем случае, а для больших наборов данных (сотни тысяч и более) классический SVM становится вычислительно дорогим. Для ускорения обучения разработаны специализированные библиотеки (LIBSVM, LIBLINEAR) и методы аппроксимации ядра, такие как Random Kitchen Sinks и Nyström approximation.

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

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

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

Недостатки

Высокая вычислительная сложность обучения для больших данных;
Чувствительность к выбору ядра и параметров;
Результат трудно интерпретировать при использовании нелинейных ядер;
Неэффективен при наличии шума в данных и пересекающихся классов;
Требует масштабирования признаков.

Сравнение с другими методами

По сравнению с логистической регрессией SVM обычно даёт более точные результаты на небольших выборках и в пространствах высокой размерности, но уступает в интерпретируемости. Против нейронных сетей SVM выигрывает на малых данных, но проигрывает на очень больших выборках и сложных структурированных данных (изображения, текст), где нейронные сети показывают превосходство.

Современные модификации

ν-SVM — параметризация с использованием $\nu$ вместо $C$ , где $\nu \in (0,1]$ контролирует долю опорных векторов и долю ошибок ^[1];
SVM для регрессии (SVR) — модификация для задач регрессии с ε-нечувствительной функцией потерь ^[1];
Одноклассовый SVM — алгоритм для поиска аномалий, строящий границу вокруг данных одного класса ^[1];
Метод опорных векторов с ранжированием (RankSVM) — применяется в задачах ранжирования, например, в поисковых системах.

Пример: работа SVM на двумерных данных

Рассмотрим задачу классификации на двумерных данных с двумя классами. В линейно разделимом случае SVM находит гиперплоскость, максимизирующую отступ, при этом опорными векторами становятся точки, лежащие на границах отступа (рис. 1).

При добавлении выбросов или перекрытии классов используется штрафной параметр $C$ . При большом $C$ (например, $C = 100$ ) классификатор старается минимизировать число ошибок, строя узкий отступ, что может привести к переобучению и высокой чувствительности к шуму. При малом $C$ (например, $C = 0.01$ ) алгоритм строит широкий отступ, допуская больше ошибок, но улучшая обобщение. Число опорных векторов при этом растёт, поскольку больше точек попадают в область отступа или нарушают его.

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

Краткий вывод

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

Схема работы метода:

$\text{данные} \to \text{выбор ядра и параметра } C \to \text{решение задачи оптимизации} \to \text{опорные векторы} \to \text{разделяющая гиперплоскость} \to \text{классификация новых объектов}$

См. также

Примечания

Литература

Vapnik V., Chervonenkis A. (1963). A note on one class of perceptrons. Automation and Remote Control, 24: 774–780.
Vapnik V., Chervonenkis A. (1974). Теория распознавания образов. Наука, Москва.
Boser B. E., Guyon I. M., Vapnik V. N. (1992). A training algorithm for optimal margin classifiers. Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, 144–152.
Cortes C., Vapnik V. (1995). Support-vector networks. Machine Learning, 20(3): 273–297.
Vapnik V. N. (1998). Statistical Learning Theory. Wiley.
Schölkopf B., Smola A. J. (2002). Learning with Kernels. MIT Press.
Bishop C. M. (2006). Pattern Recognition and Machine Learning. Springer.
Hastie T., Tibshirani R., Friedman J. (2009). The Elements of Statistical Learning. Springer.
Schölkopf B., Platt J. C., Shawe-Taylor J., Smola A. J., Williamson R. C. (1999). Estimating the support of a high-dimensional distribution. Neural Computation, 13(7): 1443–1471.
Drucker H., Burges C. J. C., Kaufman L., Smola A., Vapnik V. (1997). Support vector regression machines. Advances in Neural Information Processing Systems, 9: 155–161.

Ссылки

Kernel Machines — сайт, посвящённый методам опорных векторов и ядерным методам.
LIBSVM — популярная библиотека для SVM.
SVM в scikit-learn — документация и примеры использования.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2_%28SVM%29»

Категории: Машинное обучение | Методы классификации | Ядерные методы | Оптимизация