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

Метод опорных векторов (Шаблон:Lang-en) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как частный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором.

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

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

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

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

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

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

$\{({𝐱}_1,c_1),({𝐱}_2,c_2),\dots ,({𝐱}_n,c_n)\}$

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

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

$𝐰\cdot 𝐱-b=0.$

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

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

$𝐰\cdot 𝐱-b=1,$

$𝐰\cdot 𝐱-b=-1.$

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

$[\begin{array}{c}𝐰\cdot {𝐱}_{𝐢}-b\ge 1,c_i=1\\ 𝐰\cdot {𝐱}_{𝐢}-b\le -1,c_i=-1\end{array}$

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

$c_i(𝐰\cdot {𝐱}_{𝐢}-b)\ge 1,1\le i\le n.(1)$

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

Задача построения оптимальной разделяющей гиперплоскости сводится к минимизации $\Vert 𝐰\Vert$, при условии (1). Это задача квадратичной оптимизации, которая имеет вид:

$\{\begin{array}{c}\Vert 𝐰{\Vert }^2\to \min \\ c_i(𝐰\cdot {𝐱}_{𝐢}-b)\ge 1,1\le i\le n.\end{array}$

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

$\{\begin{array}{c}𝐋(𝐰,𝐛;\mathit{\lambda })=\frac{1}{2}\Vert 𝐰{\Vert }^2-\sum _{i=1}^n{\mathit{\lambda }}_{𝐢}(c_i((𝐰\cdot {𝐱}_{𝐢})-b)-1)\to \underset{w,b}{\min }\underset{\lambda }{\max }\\ {\mathit{\lambda }}_{𝐢}\ge 0,1\le i\le n\end{array}(2)$

где $\mathit{\lambda }=({\mathit{\lambda }}_{\mathrm{𝟏}},\dots ,{\mathit{\lambda }}_{𝐧})$ — вектор двойственных переменных.

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

$\{\begin{array}{c}-𝐋(\mathit{\lambda })=-\sum _{i=1}^n{\mathit{\lambda }}_{𝐢}+\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\mathit{\lambda }}_{𝐢}{\mathit{\lambda }}_{𝐣}{c}_i{c}_j({𝐱}_{𝐢}\cdot {𝐱}_{𝐣})\to \underset{\lambda }{\min }\\ {\mathit{\lambda }}_{𝐢}\ge 0,1\le i\le n\\ \sum _{i=1}^n{\mathit{\lambda }}_{𝐢}{c}_i=0\end{array}(3)$

Допустим мы решили данную задачу, тогда $𝐰$ и $𝐛$ можно найти по формулам:

$𝐰=\sum _{i=1}^n{\mathit{\lambda }}_{𝐢}{c}_i{𝐱}_{𝐢}$

$𝐛=𝐰\cdot {𝐱}_{𝐢}-c_i,{\mathit{\lambda }}_i>0$

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

$a(x)=sign(\sum _{i=1}^n{\mathit{\lambda }}_{𝐢}{c}_i{𝐱}_{𝐢}\cdot 𝐱-b)(4)$

При этом суммирование идёт не по всей выборке, а только по опорным векторам, для которых ${\mathit{\lambda }}_{𝐢}\ne 0$.

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

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

$\{\begin{array}{c}\frac{1}{2}\Vert 𝐰{\Vert }^2+C\sum _{i=1}^n{\xi }_i\to \underset{w,b,{\xi }_i}{\min }\\ c_i(𝐰\cdot {𝐱}_{𝐢}-b)\ge 1-{\xi }_i,1\le i\le n\\ {\xi }_i\ge 0,1\le i\le n\end{array}$

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

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

$\{\begin{array}{c}𝐋(𝐰,𝐛,\mathit{\xi };\mathit{\lambda },\mathit{\eta })=\frac{1}{2}\Vert 𝐰{\Vert }^2-\sum _{i=1}^n{\mathit{\lambda }}_{𝐢}(c_i((𝐰\cdot {𝐱}_{𝐢})-b)-1)-\sum _{i=1}^n{\mathit{\xi }}_{𝐢}({\mathit{\lambda }}_{𝐢}+{\mathit{\eta }}_{𝐢}-C)\to \underset{w,b,\xi }{\min }\underset{\lambda ,\eta }{\max }\\ {\mathit{\xi }}_{𝐢}\ge 0,{\mathit{\lambda }}_{𝐢}\ge 0,{\mathit{\eta }}_{𝐢}\ge 0,1\le i\le n\\ [\begin{array}{c}{\mathit{\lambda }}_{𝐢}=0\\ c_i(𝐰\cdot {𝐱}_{𝐢}-b)=1-{\xi }_i,\end{array}1\le i\le n\\ [\begin{array}{c}{\mathit{\eta }}_{𝐢}=0\\ {\mathit{\xi }}_{𝐢}=0,\end{array}1\le i\le n\end{array}$

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

$\{\begin{array}{c}-𝐋(\mathit{\lambda })=-\sum _{i=1}^n{\mathit{\lambda }}_{𝐢}+\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\mathit{\lambda }}_{𝐢}{\mathit{\lambda }}_{𝐣}{c}_i{c}_j({𝐱}_{𝐢}\cdot {𝐱}_{𝐣})\to \underset{\lambda }{\min }\\ 0\le {\mathit{\lambda }}_{𝐢}\le 𝐂,1\le i\le n\\ \sum _{i=1}^n{\mathit{\lambda }}_{𝐢}{c}_i=0\end{array}$

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

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

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

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

Ядра

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

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

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

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

См. также

• Размерность Вапника — Червоненкиса

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

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