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

Эта статья находится в разработке!

Метод опорных векторов (англ. 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$.

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

Примеры разделяющих гиперплоскостей в $\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}$ — параметры гиперплоскости.

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

Определение:

Отступ (англ. margin) — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M_i$, тем ближе объект $\vec{x}_i$ подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M_i$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $\vec{x}_i$. Для линейного классификатора отступ определяется уравнением: $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$

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

Оптимальная разделяющая гиперплоскость в $\mathbb{R}^2$

Заметим, что при умножении $\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 M_i(\vec{w}, b) = 1$. При этом в каждом из двух классов найдётся хотя бы один "граничный" объект обучающей выборки, отступ которого равен этому минимуму: иначе можно было бы сместить гиперплоскость в сторону класса с большим отступом, тем самым увеличив минимальное расстояние от гиперплоскости до объектов обучающей выборки.

Обозначим любой "граничный" объект из класса $+1$ как $\vec{x}_+$, из класса $-1$ как $\vec{x}_-$. Их отступ равен единице, то есть

$\begin{cases} M_+(\vec{w}, b) = (+1)(\langle \vec{w}, \vec{x}_+ \rangle - b) = 1 \\ M_-(\vec{w}, b) = (-1)(\langle \vec{w}, \vec{x}_- \rangle - b) = 1 \end{cases}$

Нормировка позволяет ограничить разделяющую полосу между классами: $\{x: -1 < \langle \vec{w}, \vec{x}_i \rangle - b < 1\}$. Внутри неё не может лежать ни один объект обучающей выборки. Ширину разделяющей полосы можно выразить как проекцию вектора $\vec{x}_+ - \vec{x}_-$ на нормаль к гиперплоскости $\vec{w}$. Чтобы разделяющая гиперплоскость находилась на наибольшем расстоянии от точек выборки, ширина полосы должна быть максимальной:

$\frac{\langle \vec{x}_+ - \vec{x}_-, \vec{w} \rangle}{\lVert w \rVert} = \frac{\langle \vec{x}_+, \vec{w} \rangle - \langle \vec{x}_-, \vec{w} \rangle - b + b}{\lVert w \rVert} = \frac{(+1)\left(\langle \vec{x}_+, \vec{w} \rangle - b\right) \, + \, (-1)\left(\langle \vec{x}_-, \vec{w} \rangle - b\right)}{\lVert w \rVert} = \\ = \frac{M_+(\vec{w}, b) \, + \, M_-(\vec{w}, b)}{\lVert w \rVert} = \frac{2}{\lVert w \rVert} \to \max \; \Rightarrow \; \lVert w \rVert \to \min$

Это приводит нас к постановке задачи оптимизации в терминах квадратичного программирования:

$\begin{cases} \lVert \vec{w} \rVert^2 \to \min\limits_{w,b} \\ M_i(\vec{w}, b) \geq 1, \quad i = 1, \ldots, \ell \end{cases}$

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

На практике линейно разделимые выборки практически не встречаются: в данных возможны выбросы и нечёткие границы между классами. В таком случае поставленная выше задача не имеет решений, и необходимо ослабить ограничения, позволив некоторым объектам попадать на "территорию" другого класса. Для каждого объекта отнимем от отступа некоторую положительную величину $\xi_i$, но потребуем чтобы эти введённые поправки были минимальны. Это приведёт к следующей постановке задачи:

$\begin{cases} \frac{1}{2} \lVert \vec{w} \rVert^2 \color{red}{+ C \sum\limits_{i=1}^\ell \xi_i} \to \min\limits_{w, b, \color{red}{\xi}} \\ M_i(\vec{w}, b) \geq 1 \color{red}{- \xi_i}, \quad i = 1, \ldots, \ell \\ \color{red}{\xi_i \geq 0, \quad i = 1, \ldots, \ell} \\ \end{cases}$

Мы не знаем, какой из функционалов $\frac{1}{2} \lVert \vec{w} \rVert^2$ и $\sum\limits_{i=1}^\ell \xi_i$ важнее, поэтому вводим коэффициент $C$, который будем оптимизировать с помощью кросс-валидации. В итоге мы получили задачу, у которой всегда есть единственное решение.

Заметим, что мы можем упростить постановку задачи:

$\begin{cases} \xi_i \geq 0 \\ \xi_i \geq 1 - M_i(\vec{w}, b) \\ \sum\limits_{i=1}^\ell \xi_i \to \min \end{cases} \,\Rightarrow\, \begin{cases} \xi_i \geq \max(0, 1 - M_i(\vec{w}, b)) \\ \sum\limits_{i=1}^\ell \xi_i \to \min \end{cases} \,\Rightarrow\, \xi_i = (1- M_i(\vec{w}, b))_+$

Получим эквивалентную задачу безусловной минимизации:

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

Теорема (Условия Каруша—Куна—Таккера):

Пусть поставлена задача нелинейного программирования с ограничениями: $$ \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} $$ Если $x$ — точка локального минимума при наложенных ограничениях, то существуют такие множители $\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}$$

По теореме Каруша—Куна—Таккера, поставленная нами задача минимизации эквивалентна двойственной задаче для функции Лагранжа:

$\mathscr{L}(\vec{w},b,\xi; \lambda, \eta) = \frac{1}{2} \lVert w \rVert^2 - \sum\limits_{i=1}^\ell \lambda_i \left(M_i(\vec{w}, b) - 1\right) - \sum\limits_{i=1}^\ell \xi_i \left(\lambda_i + \eta_i - C\right)$

$\lambda_i$ — переменные, двойственные к ограничениям $M_i \geq 1 - \xi_i$

$\eta_i$ — переменные, двойственные к ограничениям $\xi_i \geq 0$

$\begin{cases} \frac{\partial \mathscr{L}}{\partial w} = 0, \quad \frac{\partial \mathscr{L}}{\partial b} = 0, \quad \frac{\partial \mathscr{L}}{\partial \xi} = 0 \\ \xi_i \geq 0, \quad \lambda_i \geq 0, \quad \eta_i \geq 0, && i = 1, \ldots, \ell \\ \lambda_i = 0 \;\text{либо}\; M_i(\vec{w},b) = 1 - \xi_i, && i = 1, \ldots, \ell \\ \eta_i = 0 \;\text{либо}\; \xi_i = 0, && i = 1, \ldots, \ell \end{cases}$

Необходимые условия седловой точки функции Лагранжа:

$\begin{array}{lcl} \frac{\partial \mathscr{L}}{\partial w} = \vec{w} - \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i = 0 & \Rightarrow & \vec{w} = \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i \\ \frac{\partial \mathscr{L}}{\partial b} = -\sum\limits_{i=1}^\ell \lambda_i y_i = 0 & \Rightarrow & \sum\limits_{i=1}^\ell \lambda_i y_i = 0 \\ \frac{\partial \mathscr{L}}{\partial \xi_i} = -\lambda_i - \eta_i + C = 0 & \Rightarrow & \eta_i + \lambda_i = C, \quad i = 1, \ldots, \ell \end{array}$

Типизация объектов:

1. $\lambda_i = 0; \eta_i = C; \xi_i = 0; M_i \geq 1$ — периферийные (неинформативные) объекты
2. $0 < \lambda_i < C; 0 < \eta_i < C; \xi_i = 0; M_i = 1$ — опорные граничные объекты
3. $\lambda_i = С; \eta_i = 0; \xi_i > 0; M_i < 1$ — опорные объекты-нарушители

Определение:

Опорный объект (опорный вектор, англ. support vector) — объект $\vec{x}_i$, соответствующий которому множитель Лагранжа отличен от нуля: $\lambda_i \neq 0$.

Двойственная задача:

$\begin{cases} -\mathscr{L}(\lambda) = -\sum\limits_{i=1}^\ell \lambda_i + \frac{1}{2} \sum\limits_{i=1}^\ell \sum\limits_{j=1}^\ell \lambda_i \lambda_j y_i y_j \langle \vec{x}_i, \vec{x}_j \rangle \to \min\limits_\lambda \\ 0 \leq \lambda_i \leq C, \quad i = 1, \ldots, \ell \\ \sum\limits_{i=1}^\ell \lambda_i y_i = 0 \end{cases}$

Решение прямой задачи выражается через решение двойственной:

$\begin{cases} \vec{w} = \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i \\ b = \langle \vec{w}, \vec{x}_i \rangle - y_i, \quad \text{для любого}\; i: \lambda_i > 0, M_i = 1 \end{cases}$

Линейный классификатор:

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

Нелинейное обобщение, kernel trick

Переход к спрямляющему пространству более высокой размерности: $\psi : X \to H$.

Определение:

Ядро (англ. kernel) — функция $K: X \times X \to \mathbb{R}$, которая является скалярным произведением в некотором гильбертовом пространстве: $K(\vec{x}_1, \vec{x}_2) = \langle \psi(\vec{x}_1), \psi(\vec{x}_2) \rangle$ при некотором $\psi : X \to H$, где $H$ — гильбертово пространство.

Теорема:

Функция $K(\vec{x}_1, \vec{x}_2)$ является ядром тогда и только тогда, когда выполнены условия: $\begin{cases}K(\vec{x}_1, \vec{x}_2) = K(\vec{x}_2, \vec{x}_1) & \text{(симметричность)} \\[1ex] \forall g: X \to \mathbb{R} \quad \int\limits_X \int\limits_X K(\vec{x}_1, \vec{x}_2) g(\vec{x}_1) g(\vec{x}_2) d \vec{x}_1 d \vec{x}_2 \geq 0 & \text{(неотрицательная определенность)}\end{cases}$

Точный алгоритм выбора ядер не описан, однако существуют исследования в области генетических алгоритмов.

Конструктивные методы синтеза ядер:

1. $K(\vec{x}_1, \vec{x}_2) = \langle \vec{x}_1, \vec{x}_2 \rangle \quad$ (скалярное произведение)
2. $K(\vec{x}_1, \vec{x}_2) = \alpha \quad$ (константа $\alpha \in \mathbb{R}_+$)
3. $K(\vec{x}_1, \vec{x}_2) = K_1(\vec{x}_1, \vec{x}_2) + K_2(\vec{x}_1, \vec{x}_2) \quad$ (сумма ядер)
4. $K(\vec{x}_1, \vec{x}_2) = K_1(\vec{x}_1, \vec{x}_2) * K_2(\vec{x}_1, \vec{x}_2) \quad$ (произведение ядер)
5. $K(\vec{x}_1, \vec{x}_2) = \psi(\vec{x}_1) * \psi(\vec{x}_2) \quad$ (произведение функций $\psi : X \to \mathbb{R}$)
6. $K(\vec{x}_1, \vec{x}_2) = K_1(\phi(\vec{x}_1), \phi(\vec{x}_2)) \quad$ (ядро от функций $\phi : X \to X$)
7. $K(\vec{x}_1, \vec{x}_2) = \int\limits_X s(\vec{x}_1, \vec{z}) s(\vec{x}_2, \vec{z}) d \vec{z} \quad$ ($s : X \times X \to \mathbb{R}$ — симметричная интегрируемая функция)
8. $K(\vec{x}_1, \vec{x}_2) = f(K_1(\vec{x}_1, \vec{x}_2)) \quad$ ($f: \mathbb{R} \to \mathbb{R}$ представима в виде сходящегося степенного ряда с неотрицательными коэффициентами)

Примеры ядер:

• $K(\vec{x}_1, \vec{x}_2) = (\langle \vec{x}_1, \vec{x}_2 \rangle + c)^d, \quad c, d \in \mathbb{R}$ — полиномиальное ядро
• $K(\vec{x}_1, \vec{x}_2) = \sigma(\langle \vec{x}_1, \vec{x}_2 \rangle)$ — нейросеть с заданной функцией активации $\sigma(z)$ (не при всех $\sigma$ является ядром)
• $K(\vec{x}_1, \vec{x}_2) = \exp(-\beta \lVert \vec{x}_1 - \vec{x}_2 \rVert^2)$ — сеть радиальных базисных функций (англ. RBF)

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

// TODO

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

Преимущества SVM перед методом стохастического градиента и нейронными сетями:

• Задача выпуклого квадратичного программирования имеет единственное решение
• Метод опорных векторов эквивалентен двухслойной нейронной сети, где число нейронов на скрытом слое определяется автоматически как число опорных векторов

Недостатки классического SVM:

• Неустойчивость к шуму
• Нет общих подходов к оптимизации ядра под задачу
• Нет отбора признаков
• Необходимо подбирать константу $C$

Модификации

Существуют различные дополнения и модификации метода опорных векторов, направленные на устранение описанных недостатков:

• Метод релевантных векторов (Relevance Vector Machine, RVM)
• 1-norm SVM (LASSO SVM)
• Doubly Regularized SVM (ElasticNet SVM)
• Support Features Machine (SFM)
• Relevance Features Machine (RFM)

См. также

• Обзор библиотек для машинного обучения на Python
• Общие понятия

Источники информации

• 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