Метод опорных векторов (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}^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$
Мы хотим построить такую разделяющую гиперплоскость, чтобы объекты обучающей выборки находились на наибольшем расстоянии от неё.
Заметим, что при умножении $\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}$$ При этом искомая точка является седловой точкой функции Лагранжа: минимумом по $x$ и максимумом по двойственным переменным $\mu$. |
По теореме Каруша—Куна—Таккера, поставленная нами задача минимизации эквивалентна двойственной задаче для функции Лагранжа:
$\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}$
Заметим, что $\eta_i \geq 0$, $\lambda_i \geq 0$, $C > 0$, поэтому из последнего ограничения получаем $0 \leq \eta_i \leq C$, $0 \leq \lambda_i \leq C$.
Диапазон значений $\lambda_i$ (которые, как указано выше, соответствуют ограничениям на величину отступа) позволяет нам разделить объекты обучающей выборки на три типа:
- $\lambda_i = 0 \; \Rightarrow \; \eta_i = C; \; \xi_i = 0; \; M_i \geq 1 \;$ — периферийные (неинформативные) объекты — лежат в своём классе, не влияют на выбор разделяющей гиперплоскости (см. ограничение на $\vec{w}$)
- $0 < \lambda_i < C \; \Rightarrow \; 0 < \eta_i < C; \; \xi_i = 0; \; M_i = 1 \;$ — опорные граничные объекты — лежат ровно на границе разделяющей полосы
- $\lambda_i = C \; \Rightarrow \; \eta_i = 0; \; \xi_i > 0; \; M_i < 1 \;$ — опорные объекты-нарушители — лежат внутри разделяющей полосы либо на стороне другого класса
| Определение: |
| Опорный объект (опорный вектор, англ. support vector) — объект $\vec{x}_i$, соответствующий которому множитель Лагранжа отличен от нуля: $\lambda_i \neq 0$. |
Теперь подставим ограничения, которые мы получили при дифференцировании, в функцию Лагранжа. Получим следующую постановку двойственной задачи, которая зависит только от двойственных переменных $\lambda$:
$\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}$
Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\ell$-мерного куба с ребром $C$ и гиперплоскости $\langle \lambda, y \rangle = 0$, что является выпуклым многогранником размерности $\ell-1$. И в этом многограннике нужно найти минимум квадратичного функционала.
Существуют различные методы поиска решения: можно воспользоваться универсальным солвером задачи квадратичного программирования (CPLEX, Gurobi), либо алгоритмом, специально заточенным под поставленную задачу (SMO).
После того, как мы получили вектор коэффициентов $\vec{\lambda}$, можем выразить решение прямой задачи через решение двойственной:
$\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}$
И для удобства перепишем линейный классификатор, выразив $\vec{w}$ через $\vec{\lambda}$:
$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$ (скалярное произведение)
- $K(\vec{x}_1, \vec{x}_2) = \alpha \quad$ (константа $\alpha \in \mathbb{R}_+$)
- $K(\vec{x}_1, \vec{x}_2) = K_1(\vec{x}_1, \vec{x}_2) + K_2(\vec{x}_1, \vec{x}_2) \quad$ (сумма ядер)
- $K(\vec{x}_1, \vec{x}_2) = K_1(\vec{x}_1, \vec{x}_2) * K_2(\vec{x}_1, \vec{x}_2) \quad$ (произведение ядер)
- $K(\vec{x}_1, \vec{x}_2) = \psi(\vec{x}_1) * \psi(\vec{x}_2) \quad$ (произведение функций $\psi : X \to \mathbb{R}$)
- $K(\vec{x}_1, \vec{x}_2) = K_1(\phi(\vec{x}_1), \phi(\vec{x}_2)) \quad$ (ядро от функций $\phi : X \to X$)
- $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}$ — симметричная интегрируемая функция)
- $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)
См. также
Примечания
Источники информации
- 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
