|
|
| Строка 1: |
Строка 1: |
| - | {{well|Статья написана с использованием LLM '''GPT-4 Turbo''' и проверена участником [[Участник:Amir Baidanov|Amir Baidanov]] 00:32, 19 июля 2026 (MSD)}}
| |
| | | | |
| - | '''Метод опорных векторов''' (Support Vector Machine, SVM) — один из наиболее известных алгоритмов [[обучение с учителем|обучения с учителем]], используемый для задач [[классификация|классификации]], [[регрессия|регрессии]] и [[поиск аномалий|поиска аномалий]]. Основная идея метода заключается в построении разделяющей [[гиперплоскость|гиперплоскости]], которая максимизирует [[отступ|отступ]] между классами. SVM сочетает в себе геометрическую интерпретацию, строгую математическую постановку и мощный аппарат [[ядерный трюк|ядерных функций]], что делает его одним из самых изучаемых и применяемых алгоритмов в машинном обучении.
| |
| - |
| |
| - |
| |
| - |
| |
| - | == Интуитивная картина ==
| |
| - | Представьте, что на плоскости расположены точки двух цветов — красные и синие. Нужно провести прямую линию, которая разделяет их наилучшим образом. Если данные линейно разделимы, существует бесконечно много таких прямых. SVM выбирает ту, которая проходит на максимальном расстоянии от точек обоих классов. Это расстояние называется [[отступ|отступом]], а точки, которые находятся ближе всего к разделяющей линии и определяют её положение, — [[опорные векторы|опорными векторами]].
| |
| - |
| |
| - | Если данные не разделяются прямой линией, SVM позволяет либо допустить ошибки классификации (штрафные переменные), либо перейти в пространство более высокой размерности, где данные становятся линейно разделимыми (ядерный трюк). Например, точки, образующие окружность вокруг центра, можно разделить, перейдя в трёхмерное пространство с добавлением радиальной координаты.
| |
| - |
| |
| - | == Математическая постановка для линейно разделимого случая ==
| |
| - | Пусть дана [[обучающая выборка]] <tex>\{(x_i, y_i)\}_{i=1}^N</tex>, где <tex>x_i \in \mathbb{R}^d</tex> — признаки, <tex>y_i \in \{-1, +1\}</tex> — метки классов. Требуется найти гиперплоскость
| |
| - |
| |
| - | <tex>w \cdot x + b = 0</tex>,
| |
| - |
| |
| - | где <tex>w</tex> — вектор весов, <tex>b</tex> — смещение, которая разделяет классы с максимальным отступом.
| |
| - |
| |
| - | Для линейно разделимого случая существует такая гиперплоскость, что
| |
| - |
| |
| - | <tex>y_i (w \cdot x_i + b) \geq 1 \quad \forall i</tex>.
| |
| - |
| |
| - | Отступ определяется как <tex>\frac{2}{\|w\|}</tex>. Максимизация отступа эквивалентна минимизации <tex>\frac{1}{2} \|w\|^2</tex>. Таким образом, задача сводится к [[квадратичное программирование|квадратичному программированию]]:
| |
| - |
| |
| - | <tex>\min_{w,b} \frac{1}{2} \|w\|^2</tex>
| |
| - |
| |
| - | при ограничениях
| |
| - |
| |
| - | <tex>y_i (w \cdot x_i + b) \geq 1, \quad i = 1, \dots, N</tex>.
| |
| - |
| |
| - | Эта задача имеет единственное решение благодаря [[выпуклая функция|выпуклости]] целевой функции и линейности ограничений.
| |
| - |
| |
| - | == Линейно неразделимый случай и штрафные переменные ==
| |
| - | В реальных задачах данные часто не являются линейно разделимыми. Для таких случаев вводятся [[штрафные переменные]] <tex>\xi_i \geq 0</tex>, позволяющие нарушать ограничения:
| |
| - |
| |
| - | <tex>y_i (w \cdot x_i + b) \geq 1 - \xi_i, \quad i = 1, \dots, N</tex>.
| |
| - |
| |
| - | Целевая функция модифицируется добавлением штрафа за нарушения:
| |
| - |
| |
| - | <tex>\min_{w,b,\xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i</tex>,
| |
| - |
| |
| - | где <tex>C > 0</tex> — [[параметр регуляризации]], контролирующий компромисс между максимизацией отступа и минимизацией ошибок на обучающей выборке. При <tex>C \to \infty</tex> алгоритм стремится к жёсткому разделению (если это возможно), при малых <tex>C</tex> — допускает больше ошибок, но строит более широкий отступ.
| |
| - |
| |
| - | == Ядерный трюк ==
| |
| - | Ключевое усовершенствование SVM — [[ядерный трюк]], позволяющий строить нелинейные разделяющие поверхности без явного перехода в пространство более высокой размерности. Вместо скалярного произведения <tex>x_i \cdot x_j</tex> используется [[ядро (функция)|ядро]] <tex>K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)</tex>, где <tex>\phi</tex> — отображение в пространство признаков.
| |
| - |
| |
| - | Наиболее популярные ядра:
| |
| - | * '''Линейное''': <tex>K(x, z) = x \cdot z</tex>;
| |
| - | * '''Полиномиальное''': <tex>K(x, z) = (x \cdot z + r)^d</tex>, где <tex>d</tex> — степень полинома, <tex>r</tex> — константа;
| |
| - | * '''[[Радиальная базисная функция]] (RBF)''': <tex>K(x, z) = \exp(-\gamma \|x - z\|^2)</tex>, где <tex>\gamma > 0</tex> — параметр ширины;
| |
| - | * '''Сигмоидное''': <tex>K(x, z) = \tanh(\kappa (x \cdot z) + c)</tex>.
| |
| - |
| |
| - | Выбор ядра и его параметров критически влияет на качество классификации. RBF-ядро является наиболее универсальным и часто используется по умолчанию, но требует тщательной настройки <tex>\gamma</tex> и <tex>C</tex>.
| |
| - |
| |
| - | == Связь с теорией обобщения ==
| |
| - | SVM имеет прочное теоретическое обоснование в рамках [[теория Вапника — Червоненкиса|теории Вапника — Червоненкиса]]. Для класса гиперплоскостей с отступом <tex>\rho</tex> [[VC-размерность]] ограничена сверху величиной <tex>\min(d, \lfloor R^2 / \rho^2 \rfloor) + 1</tex>, где <tex>R</tex> — радиус шара, содержащего данные <ref name="vapnik1998">Vapnik V. N. (1998). ''Statistical Learning Theory''. Wiley.</ref>. Это означает, что максимизация отступа эквивалентна минимизации VC-размерности и, следовательно, улучшению обобщающей способности. Однако на практике эта теоретическая оценка часто оказывается завышенной, и качество обобщения зависит не только от отступа, но и от свойств данных.
| |
| - |
| |
| - | == Практические аспекты ==
| |
| - | === Выбор ядра и параметров ===
| |
| - | Выбор ядра и его параметров — ключевая задача при использовании SVM. Обычно применяется [[сеточный поиск]] по параметрам <tex>C</tex> и <tex>\gamma</tex> (для RBF-ядра) с [[кросс-валидация|кросс-валидацией]]. Рекомендуется использовать логарифмическую шкалу, например <tex>C \in \{10^{-3}, 10^{-2}, \dots, 10^3\}</tex>, <tex>\gamma \in \{10^{-3}, 10^{-2}, \dots, 10^3\}</tex>.
| |
| - |
| |
| - | === Масштабирование признаков ===
| |
| - | SVM чувствителен к масштабу признаков, поскольку ядро RBF использует евклидово расстояние. Перед обучением необходимо выполнить [[нормализация данных|нормализацию]] или [[стандартизация данных|стандартизацию]] признаков:
| |
| - |
| |
| - | <tex>x_i' = \frac{x_i - \mu_i}{\sigma_i}</tex>,
| |
| - |
| |
| - | где <tex>\mu_i</tex> и <tex>\sigma_i</tex> — среднее и стандартное отклонение <tex>i</tex>-го признака.
| |
| - |
| |
| - | === Вычислительная сложность ===
| |
| - | Обучение SVM требует решения задачи квадратичного программирования размера <tex>N</tex> (число объектов). Сложность наилучших алгоритмов составляет <tex>O(N^2)</tex> в худшем случае, а для больших наборов данных (сотни тысяч и более) классический SVM становится вычислительно дорогим. Для ускорения обучения разработаны [[библиотека LIBSVM|специализированные библиотеки]] (LIBSVM, LIBLINEAR) и методы [[аппроксимация ядра|аппроксимации ядра]], такие как [[Random Kitchen Sinks]] и [[Nyström approximation]].
| |
| - |
| |
| - | == Преимущества и недостатки ==
| |
| - | === Преимущества ===
| |
| - | * Строгое теоретическое обоснование и связь с теорией обобщения;
| |
| - | * Эффективность в пространствах высокой размерности;
| |
| - | * Работает хорошо при небольшом числе обучающих объектов и большом числе признаков;
| |
| - | * Возможность использования ядер для построения нелинейных решений;
| |
| - | * Устойчивость к переобучению благодаря регуляризации.
| |
| - |
| |
| - | === Недостатки ===
| |
| - | * Высокая вычислительная сложность обучения для больших данных;
| |
| - | * Чувствительность к выбору ядра и параметров;
| |
| - | * Результат трудно интерпретировать при использовании нелинейных ядер;
| |
| - | * Неэффективен при наличии шума в данных и пересекающихся классов;
| |
| - | * Требует масштабирования признаков.
| |
| - |
| |
| - | == Сравнение с другими методами ==
| |
| - | По сравнению с [[логистическая регрессия|логистической регрессией]] SVM обычно даёт более точные результаты на небольших выборках и в пространствах высокой размерности, но уступает в интерпретируемости. Против [[нейронные сети|нейронных сетей]] SVM выигрывает на малых данных, но проигрывает на очень больших выборках и сложных структурированных данных (изображения, текст), где нейронные сети показывают превосходство.
| |
| - |
| |
| - | == Современные модификации ==
| |
| - | * '''ν-SVM''' — параметризация с использованием <tex>\nu</tex> вместо <tex>C</tex>, где <tex>\nu \in (0,1]</tex> контролирует долю опорных векторов и долю ошибок <ref name="scholkopf2000">Schölkopf B., Smola A. J., Williamson R. C., Bartlett P. L. (2000). New support vector algorithms. ''Neural Computation'', 12(5): 1207–1245.</ref>;
| |
| - | * '''SVM для регрессии (SVR)''' — модификация для задач регрессии с ε-нечувствительной функцией потерь <ref name="drucker1997">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.</ref>;
| |
| - | * '''Одноклассовый SVM''' — алгоритм для поиска аномалий, строящий границу вокруг данных одного класса <ref name="scholkopf1999">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.</ref>;
| |
| - | * '''Метод опорных векторов с ранжированием (RankSVM)''' — применяется в задачах ранжирования, например, в поисковых системах.
| |
| - |
| |
| - | === Пример: работа SVM на двумерных данных ===
| |
| - | Рассмотрим задачу классификации на двумерных данных с двумя классами. В линейно разделимом случае SVM находит гиперплоскость, максимизирующую отступ, при этом опорными векторами становятся точки, лежащие на границах отступа (рис. 1).
| |
| - |
| |
| - | При добавлении выбросов или перекрытии классов используется штрафной параметр <tex>C</tex>. При большом <tex>C</tex> (например, <tex>C = 100</tex>) классификатор старается минимизировать число ошибок, строя узкий отступ, что может привести к переобучению и высокой чувствительности к шуму. При малом <tex>C</tex> (например, <tex>C = 0.01</tex>) алгоритм строит широкий отступ, допуская больше ошибок, но улучшая обобщение. Число опорных векторов при этом растёт, поскольку больше точек попадают в область отступа или нарушают его.
| |
| - |
| |
| - | На нелинейно разделимых данных (например, точки образуют две окружности) использование RBF-ядра позволяет найти нелинейную границу. Параметр <tex>\gamma</tex> контролирует радиус влияния каждого обучающего объекта: при большом <tex>\gamma</tex> граница становится извилистой и может переобучаться, при малом — более гладкой, но может недостаточно точно разделять классы.
| |
| - |
| |
| - | == Краткий вывод ==
| |
| - | Метод опорных векторов — один из наиболее теоретически обоснованных алгоритмов классификации, основанный на максимизации отступа и использовании ядерного трюка. Он эффективен на небольших и средних выборках, особенно в пространствах высокой размерности, но требует тщательного выбора ядра и параметров регуляризации. Основные ограничения — вычислительная сложность и чувствительность к масштабированию признаков. Современные модификации расширяют область применения SVM на задачи регрессии и обнаружения аномалий.
| |
| - |
| |
| - | '''Схема работы метода:'''
| |
| - |
| |
| - | <tex>\text{данные} \to \text{выбор ядра и параметра } C \to \text{решение задачи оптимизации} \to \text{опорные векторы} \to \text{разделяющая гиперплоскость} \to \text{классификация новых объектов}</tex>
| |
| - |
| |
| - | == См. также ==
| |
| - | * [[Опорные векторы]]
| |
| - | * [[Ядерный трюк]]
| |
| - | * [[Теория Вапника — Червоненкиса]]
| |
| - | * [[Регуляризация]]
| |
| - | * [[Логистическая регрессия]]
| |
| - | * [[Обучение с учителем]]
| |
| - |
| |
| - | == Примечания ==
| |
| - | <references/>
| |
| - |
| |
| - | == Литература ==
| |
| - | # 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.
| |
| - |
| |
| - | == Ссылки ==
| |
| - | * [http://www.kernel-machines.org/ Kernel Machines] — сайт, посвящённый методам опорных векторов и ядерным методам.
| |
| - | * [https://www.csie.ntu.edu.tw/~cjlin/libsvm/ LIBSVM] — популярная библиотека для SVM.
| |
| - | * [https://scikit-learn.org/stable/modules/svm.html SVM в scikit-learn] — документация и примеры использования.
| |
| - |
| |
| - | [[Категория:Машинное обучение]]
| |
| - | [[Категория:Методы классификации]]
| |
| - | [[Категория:Ядерные методы]]
| |
| - | [[Категория:Оптимизация]]
| |
