Метод опорных векторов (Support vector machine)

Линейно разделимый случай SVM

Пусть дана выборка $(x_i, y_i),~i=1\ldots N,~x_i \in R^D,~y_i \in \{-1; 1\}$

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

$a(x) = sign(w^Tx + w_0),~w \in R^D,~w_0 \in R$

Какой геометрический смысл у линейного классификатора? Он строит гиперплоскость, которая задается уравнением:

$w^{T}x + w_0 = 0$

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

$w^Tx + w_0 = b ,~~~b > 0$

Найдем расстояние от него до гиперплоскости. Известно, что расстояние может быть посчитано по формуле: $\frac{|w^Tx + w_0|}{\|w\|}$ В нашем случае расстояние до гиперплоскости равно $\frac{b}{\|w\|}$.

Таким образом ширина разделяющей полосы будет равна $\frac{2b}{\|w\|}$ и наша задача заключается в нахождении вектора $w$. Он должен быть таким, чтобы гиперплоскость линейно разделяла нашу выборку и ширина зазора между классами была максимальной. Зачем это нужно? Мы знаем, что чем больше значение $\langle w,x \rangle$тем классификатор увереннее в ответе. Поэтому мы и хотим увеличить ширину зазора между классами, чтобы повысить качество классификации.

Итак, перейдем к математической постановке задачи:

$\begin{cases} \frac{2b}{\|w\|} \rightarrow \underset{w, w_0}{\max} \\ \forall x_i,~y = 1 ~~w^Tx_i + w_0 \ge b \\ \forall x_i,~y = -1 ~~w^Tx_i + w_0 \le -b \end{cases}$

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

$y_i\left(w^Tx_i + w_0\right) \ge b$

Если точка $(w,w_0, b)$ - решение задачи, то для $\forall \alpha > 0 ~~(\alpha w,~\alpha w_0,~\alpha b)$ - тоже решение. Положим $b=1$, т.к. мы можем масштабировать $(w,w_0, b)$.

Итого получим следующую задачу:

$\begin{cases} \|w\| \rightarrow \underset{w, w_0}{\min} \\ y_i\left(w^Tx_i + w_0\right) \ge 1 ~~~\forall i\in 1, \dots , N\\ \end{cases}$

Выделяют два типа объектов:

• Опорные вектора: $y_i\left( w^Tx_i + w_0 \right) = 1$
• Неинформативные векторы: $y_i\left( w^Tx_i + w_0 \right) > 1$

Но все это не имеет отношения к жизни, потому что линейно разделимых выборок не бывает.

Линейно неразделимый случай SVM

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

$\begin{cases} \|w\| \rightarrow \underset{w, w_0}{\min} \\ y_i\left(w^Tx_i + w_0\right) \ge 1 - \xi_i ~~~\forall i\in 1, \dots , N\\ \xi_i \ge 0,~~i = 1,\dots,N \end{cases}$

$\xi$ надо как-то штрафовать, чтобы они не были слишком большими. В итоге получим следующую задачу:

$\begin{cases} \frac{1}{2}\|w\|^2 + C \sum_{i = 1}^{N}\xi_i \rightarrow \underset{w, w_0, \xi}{\min} \\ y_i\left(w^Tx_i + w_0\right) \ge 1 - \xi_i ~~~\forall i\in 1, \dots , N\\ \xi_i \ge 0,~~i = 1,\dots,N \end{cases}$

Параметр $C$ определяет цену ошибки классификации. Заметим, что в качестве штрафа мы также могли взять $C\sum_{i}^{N}\xi_i^2$.

Классификация типов объектов

Выделяют несколько типов объектов:

• Неинформативные: $y_i\left( w^Tx_i + w_0 \right) > 1$
• Опорные векторы: $y_i\left(w^Tx_i + w_0\right) \le 1$
  • Граничные опорные векторы: $y_i\left( w^Tx_i + w_0 \right) = 1$
  • Опорные вектора-нарушители:
    • $y_i\left(w^Tx_i + w_0\right) > 0$ - векторы, лежащие внутри разделяющей полосы, но в своем классе
    • $y_i\left(w^Tx_i + w_0\right) < 0$ - векторы, которые классифицируются неверно

Какой функции потерь и регуляризатору соответствует SVM?

Рассмотрим еще раз линейно неразделимый случай SVM.

$\begin{cases} \frac{1}{2}\|w\|^2 + C \sum_{i = 1}^{N}\xi_i \rightarrow \underset{w, w_0, \xi}{\min} \\ y_i\left(w^Tx_i + w_0\right) \ge 1 - \xi_i ~~~\forall i\in 1, \dots , N\\ \xi_i \ge 0,~~i = 1,\dots,N \end{cases}$

Постараемся избавиться от $\xi$. Ясно, что из последних двух неравенства можем получить:$\begin{cases} \xi_i \ge 1 - y_i\left(w^Tx_i + w_0\right) \\ \xi_i \ge 0,~~i = 1,\dots,N \end{cases}$

Или иначе это можно записать: $\xi_i = \max\left(1 - y_i\left(w^Tx_i + w_0\right), 0\right) \ge 0$

И тогда нашу задачу можно переписать в виде:

$\frac{1}{2} \|w\|^2 + C \sum_{i = 1}^{N} \max \left(1 - y_i\left(w^Tx_i + w_0\right), 0\right) \rightarrow \underset{w, w_0}{\min}$

Это и есть функция потерь, которую мы пытаемся минимизировать. Видно, что в данном случае используется $L_2$ регуляризация, а функция потерь является кусочно - линейной.

Вывод решения

Запишем еще раз условия задачи:

$\begin{cases} \frac{1}{2}\|w\|^2 + C \sum_{i = 1}^{N}\xi_i \rightarrow \underset{w, w_0, \xi}{\min} \\ y_i\left(w^Tx_i + w_0\right) \ge 1 - \xi_i ~~~\forall i\in 1, \dots , N\\ \xi_i \ge 0,~~i = 1,\dots,N \end{cases}$

Запишем Лагранжиан:

$L(w,b,\xi,\lambda,\mu) = \frac{1}{2}\|w\|^2 + C \sum_{i = 1}^{N}\xi_i - \sum_{i = 1}^{N}\lambda_i[y_i (w^T x_i + b) - 1 + \xi_i] - \sum_{i = 1}^{N} \mu_i \xi_i$

Выпишем Условия Куна-Таккера:

$\begin{cases} \bigtriangledown_w L = w - \sum_{i=1}^{l} \lambda_i y_i x_i = 0 \Longrightarrow w = \sum_{i=1}^{l} \lambda_i y_i x_i \\ \bigtriangledown_b L = - \sum_{i=1}^{l} \lambda_i y_i = 0 \Longrightarrow \sum_{i=1}^{l} \lambda_i y_i = 0 \\ \bigtriangledown_{\xi_i} L = C - \lambda_i - \mu_i \Longrightarrow \mu_i + \lambda_i = C \\ \lambda_i[y_i (w^T x_i + b) - 1 + \xi_i] = 0 \Longrightarrow (\lambda_i=0)\ or\ (y_i (w^T x_i + b) = 1 - \xi_i) \\ \mu_i \xi_i = 0 \Longrightarrow (\mu_i=0)\ or\ (\xi_i=0) \\ \xi_i \ge 0,\ \lambda_i \ge 0,\ \mu_i \ge 0 \end{cases}$
Воспользуемся этими условиями и перепишем Лагранжиан:

$L = \frac{1}{2}\|\sum_{i=1}^{l} \lambda_i y_i x_i\|^2 - \sum_{i,j=1}^{l} \lambda_i \lambda_j y_i y_j x_{i}^T x_j - b \sum_{i=1}^{l} \lambda_i y_i + \sum_{i=1}^{l} \lambda_i + \sum_{i=1}^{l} \xi_i (C - \lambda_i - \mu_i) =$ $= \sum_{i=1}^{l} \lambda_i - \frac{1}{2} \sum_{i,j=1}^{l} \lambda_i \lambda_j y_i y_j x_{i}^T x_j$

Таким образом мы перешли к двойственной задаче:

$\begin{cases} \sum_{i=1}^{l} \lambda_i - \frac{1}{2} \sum_{i,j=1}^{l} \lambda_i \lambda_j y_i y_j x_{i}^T x_j \rightarrow \underset{\lambda}{max} \\ 0 \le \lambda_i \le\ C,\ i=1,2,...,l \\ \sum_{i=1}^{l} \lambda_i y_i = 0 \\ \end{cases}$

Обобщение через ядра

Вместо скалярного произведения можно использовать ядра: $\begin{cases} \sum_{i=1}^{l} \lambda_i - \frac{1}{2} \sum_{i,j=1}^{l} \lambda_i \lambda_j y_i y_j K(x_i,x_j) \rightarrow \underset{\lambda}{max} \\ 0 \le \lambda_i \le\ C,\ i=1,2,...,l \\ \sum_{i=1}^{l} \lambda_i y_i = 0 \\ \end{cases}$

В этом случае классификатор будет иметь вид:

$a(x)= sign(\sum_{i=1}^{l} \lambda_i y_i K(x_i, x) + b)$