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

2019-04-01T08:06:12Z

212.237.8.84:

{{в разработке}}

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

== Метод опорных векторов в задаче классификации ==

Рассмотрим задачу бинарной классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, +1\}$.

Пусть задана обучающая выборка пар "объект-ответ": $T^\ell = (\vec{x}_i, y_i)_{i=1}^\ell$. Необходимо построить алгоритм классификации $a(\vec{x}) : X \to Y$.

=== Разделяющая гиперплоскость ===

[[Файл:svm_hyperplane.png|300px|thumb|right|Примеры разделяющих гиперплоскостей в $\mathbb{R}^2$]]

В пространстве $\mathbb{R}^n$ уравнение $\langle \vec{w}, \vec{x} \rangle - b = 0$ при заданных $\vec{w}$ и $b$ определяет гиперплоскость — множество векторов $\vec{x} = (x_1, \ldots, x_n)$, принадлежащих пространству меньшей размерности $\mathbb{R}^{n-1}$. Например, для $\mathbb{R}^1$ гиперплоскостью является точка, для $\mathbb{R}^2$ — прямая, для $\mathbb{R}^3$ — плоскость и т.д. Параметр $\vec{w}$ определяет вектор нормали к гиперплоскости, а через $\frac{b}{\lVert \vec{w} \rVert}$ выражается расстояние от гиперплоскости до начала координат.

Гиперплоскость делит $\mathbb{R}^n$ на два полупространства: $\langle \vec{w}, \vec{x} \rangle - b > 0$ и $\langle \vec{w}, \vec{x} \rangle - b < 0$.

Говорят, что гиперплоскость разделяет два класса $C_1$ и $C_2$, если объекты этих классов лежат по разные стороны от гиперплоскости, то есть выполнено либо

$\begin{cases}\langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_1 \\ \langle \vec{w}, \vec{x} \rangle - b < 0, && \forall x \in C_2\end{cases}$

либо

$\begin{cases}\langle \vec{w}, \vec{x} \rangle - b < 0, && \forall x \in C_1 \\ \langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_2\end{cases}$

=== Линейно разделимая выборка ===

Пусть выборка линейно разделима, то есть существует некоторая гиперплоскость, разделяющая классы $-1$ и $+1$. Тогда в качестве алгоритма классификации можно использовать линейный пороговый классификатор:

$a(\vec{x}) = sign(\langle \vec{w}, \vec{x} \rangle - b) = sign\left(\sum\limits_{i=1}^\ell w_i x_i - b\right)$

где $\vec{x} = (x_1, \ldots, x_n)$ — вектор значений признаков объекта, а $\vec{w} = (w_1, \ldots, w_n) \in \mathbb{R}^n$ и $b \in \mathbb{R}$ — параметры гиперплоскости.

Но для двух линейно разделимых классов возможны различные варианты построения разделяющих гиперплоскостей. Метод опорных векторов выбирает ту гиперплоскость, которая максимизирует отступ между классами:
{{Определение
|definition=
'''Отступ''' (англ. ''margin'') — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M_i$, тем ближе объект $\vec{x}_i$ подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M_i$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $\vec{x}_i$. <br><br> Для линейного классификатора отступ определяется уравнением: $M_i(\vec{w}, b) = y_i(\langle \vec{w}, \vec{x}_i \rangle - b)$
}}
Если выборка линейно разделима, то существует такая гиперплоскость, отступ от которой до каждого объекта положителен:

$\exists \vec{w}, b : \; M_i(\vec{w}, b) = y_i(\langle \vec{w}, \vec{x}_i \rangle - b) > 0, \; i = 1\ldots\ell$

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

Заметим, что при умножении $\vec{w}$ и $b$ на константу $c \neq 0$ уравнение $\langle c\vec{w}, \vec{x} \rangle - cb = 0$ определяет ту же самую гиперплоскость, что и $\langle \vec{w}, \vec{x} \rangle - b = 0$. Для удобства проведём нормировку: выберем константу $c$ таким образом, чтобы $\min\limits_i M_i(\vec{w}, b) = 1$. При этом в каждом из двух классов найдётся хотя бы один объект, отступ которого равен этому минимуму: иначе можно было бы сместить гиперплоскость в сторону класса с большим отступом.

[[Файл:SVM_margin.png|300px|thumb|right|Оптимальная разделяющая гиперплоскость в $\mathbb{R}^2$]]
Нормировка позволяет определить разделяющую полосу между классами, как множество точек, расстояние от которых до гиперплоскости меньше $1$: $\{x: -1 < \langle \vec{w}, \vec{x}_i \rangle - b < 1\}$.

Ширину разделяющей полосы можно выразить как проекцию

{{Теорема
|id=kkt
|author=Условия Каруша—Куна—Таккера
|statement=
Пусть поставлена задача нелинейного программирования с ограничениями:
$$
\begin{cases}
f(x) \to \min\limits_{x \in X} \\
g_i(x) \leq 0,\;i=1\ldots m \\
h_j(x) = 0,\;j=1\ldots k
\end{cases}
$$

Если $\hat{x} \in \arg\min f$ — решение задачи при наложенных ограничениях, то существуют множители $\mu_i, i = 1\ldots m$, $\lambda_j, j = 1\ldots k$, что для функции Лагранжа $L(x; \mu, \lambda)$ выполняются условия:

$$\begin{cases}\frac{\partial L}{\partial x} = 0 \quad L(x; \mu, \lambda) = f(x) + \sum\limits_{i=1}^m \mu_i g_i(x) + \sum\limits_{j=1}^k \lambda_j h_j(x) \\ g_i(x) \leq 0,\;h_j(x) = 0 \quad \text{(исходные ограничения)} \\ \mu_i \geq 0 \quad \text{(двойственные ограничения)} \\ \mu_i g_i(x) = 0 \quad \text{(условие дополняющей нежёсткости)} \end{cases}$$
}}

В качестве аппроксимации функции потерь возьмём $L(x_i, y_i) = max(0, 1 - M_i(w, w_0))$

Запишем функционал для метода оптимизации эмпирического риска с использованием данной функции потерь и регуляризации:

$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$

=== Линейно неразделимая выборка ===

== Метод опорных векторов в задаче регрессии ==
// TODO

== См. также ==
* [[Обзор библиотек для машинного обучения на Python]]
* [[Общие понятия]]

== Примечания ==
<references/>

== Источники информации ==
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%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 machinelearning.ru {{---}} Машина опорных векторов]
* [https://www.youtube.com/watch?v=Adi67_94_gc&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=5 Лекция "Линейные методы классификации: метод опорных векторов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
* [https://ru.wikipedia.org/wiki/%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 Wikipedia {{---}} Метод опорных векторов]
* Alexey Nefedov {{---}} [https://svmtutorial.online/ Support Vector Machines: A Simple Tutorial]
* John Platt {{---}} [https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/ Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines]

[[Категория: Машинное обучение]]
[[Категория: Классификация]]
[[Категория: Регрессия]]

Викиконспекты - Вклад участника [ru]

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