Метод опорных векторов (SVM)
Метод опорных векторов (англ. support vector machine, SVM) — семейство алгоритмов обучения с учителем, использующихся для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки наиболее оптимальным способом.
Метод опорных векторов в задаче классификации
Рассмотрим задачу бинарной классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, +1\}$.
Пусть задана обучающая выборка пар "объект-ответ": $X^\ell = (\vec{x}_i, y_i)_{i=1}^\ell$. Необходимо построить алгоритм классификации $a(\vec{x}) : X \to Y$.
Разделяющая гиперплоскость
В пространстве $\mathbb{R}^n$ уравнение $\langle \vec{w}, \vec{x} \rangle - b = 0$ при заданных $\vec{w}$ и $b$ определяет гиперплоскость — (n-1)-мерное множество векторов $\vec{x} = (x^1, \ldots, x^n)$. Для $\mathbb{R}^1$ это точка, для $\mathbb{R}^2$ — прямая, для $\mathbb{R}^3$ — плоскость и т.д. Эта гиперплоскость делит $\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_{j=1}^\ell w_j x^j - b\right)$
где $\vec{x} = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $\vec{w} = (w_1, \ldots, w_n) \in \mathbb{R}^n$ и $b \in \mathbb{R}$ — параметры алгоритма.
Но для двух линейно разделимых классов существует бесконечное множество разделяющих гиперплоскостей. Метод опорных векторов выбирает ту гиперплоскость, которая максимизирует отступ между классами:
| Определение: |
| Отступ (англ. margin) — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M(x_i, y_i)$, тем ближе объект подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M(x_i, y_i)$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $x_i$.
Для задачи бинарной классификации: $M(x_i, y_i) = y_i(\langle x_i, w \rangle - w_0)$ Для задачи классификации на несколько классов: $M(x_i, y_i) = \langle x_i, w_{y_i}\rangle - \max\limits_{y \in \mathbb{Y}, y \ne y_i} \langle x_i, w_y\rangle$ |
Таким образом, для линейно разделимой выборки существует такая гиперплоскость, отступ от которой до каждого объекта положителен:
$\exists \vec{w}, b : M_i(\vec{w}, b) = y_i(\langle \vec{w}, \vec{x} \rangle - b) > 0, \; i = 1\ldots\ell$
| Теорема (Условия Каруша—Куна—Таккера): |
Пусть поставлена задача нелинейного программирования с ограничениями:
$$ \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
См. также
Примечания
Источники информации
- machinelearning.ru — Машина опорных векторов
- Лекция "Линейные методы классификации: метод опорных векторов" — К.В. Воронцов, курс "Машинное обучение" 2014
- Wikipedia — Метод опорных векторов
- Alexey Nefedov — Support Vector Machines: A Simple Tutorial
- John Platt — Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
