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

Запрос «SVM» перенаправляется сюда; см. также другие значения.

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

Основная идея метода опорных векторов — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей наши классы. Разделяющей гиперплоскостью будет гиперплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора.

Постановка задачи

Несколько классифицирующих разделяющих прямых (гиперплоскостей). Но только одна достигает оптимального разделения

Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представлен как вектор (точка) в $p$-мерном пространстве (последовательность $p$ чисел). Каждая из этих точек принадлежит только одному из двух классов. Нас интересует, можем ли мы разделить точки гиперплоскостью размерностью ($p$−1). Это типичный случай линейной разделимости. Таких гиперплоскостей может быть много. Поэтому вполне естественно полагать, что максимизация зазора между классами способствует более уверенной классификации. То есть можем ли мы найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это бы означало, что расстояние между двумя ближайшими точками, лежащими по разные стороны гиперплоскости, максимально. Если такая гиперплоскость существует, то она нас будет интересовать больше всего; она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.

Формальное описание задачи

Мы полагаем, что точки имеют вид::

$\{ (\mathbf{x}_1, c_1), (\mathbf{x}_2, c_2), \ldots, (\mathbf{x}_n, c_n)\}$

где c_i принимает значение 1 или −1, в зависимости от того, какому классу принадлежит точка $\mathbf{x}_i$. Каждое $\mathbf{x}_i$ — это $p$-мерный вещественный вектор, обычно нормализованный значениями [0,1] или [-1,1]. Если точки не будут нормализованы, то точка с большими отклонениями от средних значений координат точек слишком сильно повлияет на классификатор. Мы можем рассматривать это как учебную коллекцию, в которой для каждого элемента уже задан класс, к которому он принадлежит. Мы хотим, чтобы алгоритм метода опорных векторов классифицировал их таким же образом. Для этого мы строим разделяющую гиперплоскость, которая имеет вид:

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

$\mathbf{w}\cdot\mathbf{x} - b=0.$

Вектор $\mathbf{w}$ — перпендикуляр к разделяющей гиперплоскости. Параметр b зависит от кратчайшего расстояния гиперплоскости до начала координат. Если параметр b равен нулю, гиперплоскость проходит через начало координат, что ограничивает решение.

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

$\mathbf{w}\cdot\mathbf{x} - b=1,$

$\mathbf{w}\cdot\mathbf{x} - b=-1.$

Если обучающая выборка линейно разделима, то мы можем выбрать гиперплоскости таким образом, чтобы между ними не лежала ни одна точка обучающей выборки и затем максимизировать расстояние между гиперплоскостями. Ширину полосы между ними легко найти из соображений геометрии, она равна $\frac{2}{\|\mathbf{w}\|}$^[1], таким образом наша задача минимизировать $\|\mathbf{w}\|$. Чтобы исключить все точки из полосы, мы должны убедиться для всех $i$, что

$\left[\begin{array}{lcr} \mathbf{w}\cdot\mathbf{x_i} - b \ge 1,\ c_i=1\mathrm{}\\ \mathbf{w}\cdot\mathbf{x_i} - b \le -1,\ c_i=-1\mathrm{}\\ \end{array}\right.$

Это может быть также записано в виде:

$c_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1, \quad 1 \le i \le n.\qquad\qquad(1)$

Случай линейной разделимости

Проблема построения оптимальной разделяющей гиперплоскости сводится к минимизации $\|\mathbf{w}\|$, при условии (1). Это задача квадратичной оптимизации, которая имеет вид:

$\left\{\begin{array}{lcr} \|\mathbf{w}\|^2 \to \min \\ c_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1, \quad 1 \le i \le n.\\ \end{array}\right.$

По теореме Куна — Таккера эта задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа $\left\{\begin{array}{lcr} \mathbf{L} (\mathbf{w}, \mathbf{b}; \mathbf{\lambda}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^n \mathbf{\lambda_i}(c_i((\mathbf{w}\cdot\mathbf{x_i})-b)-1)\to \min_{w,b} \max_{\lambda} \\ \mathbf{\lambda_i} \ge 0, \quad 1 \le i \le n\\ \end{array}\right.(2)$

где $\mathbf{\lambda}=(\mathbf{\lambda_1},\ldots, \mathbf{\lambda_n})$ — вектор двойственных переменных.

Сведем эту задачу к эквивалентной задаче квадратичного программирования, содержащую только двойственные переменные:

$\left\{\begin{array}{lcr} -\mathbf{L} (\mathbf{\lambda}) = -\sum_{i=1}^n \mathbf{\lambda_i}+ \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \mathbf{\lambda_i}\mathbf{\lambda_j}c_i c_j(\mathbf{x_i}\cdot \mathbf{x_j}) \to \min_{\lambda} \\ \mathbf{\lambda_i} \ge 0, \quad 1 \le i \le n\\ \sum_{i=1}^n \mathbf{\lambda_i}c_i = 0 \\ \end{array}\right.(3)$

Допустим мы решили данную задачу, тогда $\mathbf{w}$ и $\mathbf{b}$ можно найти по формулам:

$\mathbf{w} = \sum_{i=1}^n \mathbf{\lambda_i} c_i \mathbf{x_i}$

$\mathbf{b} = \mathbf{w} \cdot \mathbf{x_i} - c_i, \quad \mathbf \lambda_i > 0$

В итоге алгоритм классификации может быть записан в виде:

$a(x) = sign \left(\sum_{i=1}^n \mathbf{\lambda_i} c_i \mathbf{x_i}\cdot \mathbf{x} - b\right)(4)$

При этом суммирование идет не по всей выборке, а только по опорным векторам, для которых $\mathbf{\lambda_i}\ne0$.

Случай линейной неразделимости

Для того, чтобы алгоритм мог работать в случае, если классы линейно неразделимы, позволим ему допускать ошибки на обучающей выборке. Введем набор дополнительных переменных $\xi_i\ge0$, характеризующих величину ошибки на объектах $\mathbf{x}_i , \quad 1 \le i \le n$. Возьмем за отправную точку (2), смягчим ограничения неравенства, так же введём в минимизируемый функционал штраф за суммарную ошибку:

$\left\{\begin{array}{lcr} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \to \min_{w,b,\xi_i}\\ c_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i, \quad 1 \le i \le n \\ \xi_i\ge0, \quad 1 \le i \le n\\ \end{array}\right.$

Коэффициент $C$ — параметр настройки метода, который позволяет регулировать отношение между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки.

Аналогично, по теореме Куна-Таккера сводим задачу к поиску седловой точки функции Лагранжа:

$\left\{\begin{array}{lcr} \mathbf{L} (\mathbf{w}, \mathbf{b}, \mathbf{\xi}; \mathbf{\lambda},\mathbf{\eta}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^n \mathbf{\lambda_i}(c_i(\mathbf{w}\cdot\mathbf{x_i})-1) -\sum_{i=1}^n \mathbf{\xi_i} (\mathbf{\lambda_i}+\mathbf{\eta_i}-C) \to \min_{w,b,\xi} \max_{\lambda,\eta} \\ \mathbf{\xi_i} \ge 0, \mathbf{\lambda_i} \ge 0, \mathbf{\eta_i} \ge 0, \quad 1 \le i \le n\\ \left[\begin{array}{lcr} \mathbf{\lambda_i} = 0 \\ c_i(\mathbf{w}\cdot\mathbf{x_i} - b )=1-\xi_i, \\ \end{array}\right. \quad 1 \le i \le n \\ \left[\begin{array}{lcr} \mathbf{\eta_i} = 0 \\ \mathbf{\xi_i} =0, \\ \end{array}\right. \quad 1 \le i \le n \end{array}\right.$

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

$\left\{\begin{array}{lcr} -\mathbf{L} (\mathbf{\lambda}) = -\sum_{i=1}^n \mathbf{\lambda_i}+ \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \mathbf{\lambda_i}\mathbf{\lambda_j}c_i c_j(\mathbf{x_i}\cdot \mathbf{x_j}) \to \min_{\lambda} \\ 0 \le \mathbf{\lambda_i} \le \mathbf{C}, \quad 1 \le i \le n\\ \sum_{i=1}^n \mathbf{\lambda_i}c_i = 0 \\ \end{array}\right.$

На практике для построения машины опорных векторов решают именно эту задачу, а не (3), так как гарантировать линейную разделимость точек на два класса в общем случае не представляется возможным. Этот вариант алгоритма называют алгоритмом с мягким зазором (soft-margin SVM), тогда как в линейно разделимом случае говорят о жёстком зазоре (hard-margin SVM).

Для алгоритма классификации сохраняется формула (4), с той лишь разницей, что теперь ненулевыми $\mathbf{\lambda_i}$ обладают не только опорные объекты, но и объекты-нарушители. В определённом смысле это недостаток, поскольку нарушителями часто оказываются шумовые выбросы, и построенное на них решающее правило, по сути дела, опирается на шум.

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

Если есть основания полагать, что выборка почти линейно разделима, и лишь объекты-выбросы классифицируются неверно, то можно применить фильтрацию выбросов. Сначала задача решается при некотором C, и из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки $\mathbf{\xi_i}$. После этого задача решается заново по усечённой выборке. Возможно, придётся проделать несколько таких итераций, пока оставшиеся объекты не окажутся линейно разделимыми.

Ядра

Алгоритм построения оптимальной разделяющей гиперплоскости, предложенный в 1963 году Владимиром Вапником и Алексеем Червоненкисом — алгоритм линейной классификации. Однако в 1992 году Бернхард Босер, Изабель Гийон и Вапник предложили способ создания нелинейного классификатора, в основе которого лежит переход от скалярных произведений к произвольным ядрам, так называемый kernel trick (предложенный впервые М. А. Айзерманом, Э. М. Броверманом и Л. В. Розоноэром для метода потенциальных функций), позволяющий строить нелинейные разделители. Результирующий алгоритм крайне похож на алгоритм линейной классификации, с той лишь разницей, что каждое скалярное произведение в приведённых выше формулах заменяется нелинейной функцией ядра (скалярным произведением в пространстве с большей размерностью). В этом пространстве уже может существовать оптимальная разделяющая гиперплоскость. Так как размерность получаемого пространства может быть больше размерности исходного, то преобразование, сопоставляющее скалярные произведения, будет нелинейным, а значит функция, соответствующая в исходном пространстве оптимальной разделяющей гиперплоскости, будет также нелинейной.

Стоит отметить, что если исходное пространство имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой.

Наиболее распространённые ядра:

• Полиномиальное (однородное): $k(\mathbf{x},\mathbf{x}')=(\mathbf{x} \cdot \mathbf{x'})^d$
• Полиномиальное (неоднородное): $k(\mathbf{x},\mathbf{x}')=(\mathbf{x} \cdot \mathbf{x'} + 1)^d$
• Радиальная базисная функция: $k(\mathbf{x},\mathbf{x}')=\exp(-\gamma \|\mathbf{x} - \mathbf{x'}\|^2)$, для $\gamma > 0$
• Радиальная базисная функция Гаусса: $k(\mathbf{x},\mathbf{x}')=\exp\left(- \frac{\|\mathbf{x} - \mathbf{x'}\|^2}{2 \sigma^2}\right)$
• Сигмоид: $k(\mathbf{x},\mathbf{x}')=\tanh(\kappa \mathbf{x} \cdot \mathbf{x'}+c)$, для почти всех $\kappa > 0$ и $c < 0$

Примечания

1. ↑ К. В. Воронцов. Лекции по методу опорных векторов

Литература

• Юрий Лифшиц. Метод опорных векторов (Слайды) — лекция № 7 из курса «Алгоритмы для Интернета»

Ссылки

• Data Mining. 10. Лекция: Методы классификации и прогнозирования. Метод опорных векторов INTUIT.ru