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

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

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

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

${\displaystyle \{(\mathbf {x} _{1},c_{1}),(\mathbf {x} _{2},c_{2}),\ldots ,(\mathbf {x} _{n},c_{n})\}}$

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

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

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

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

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

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

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

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

${\displaystyle \left[{\begin{array}{lcr}\mathbf {w} \cdot \mathbf {x_{i}} -b\geq 1,\ c_{i}=1\mathrm {} \\\mathbf {w} \cdot \mathbf {x_{i}} -b\leq -1,\ c_{i}=-1\mathrm {} \\\end{array}}\right.}$

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

${\displaystyle c_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1,\quad 1\leq i\leq n.\qquad \qquad (1)}$

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

${\displaystyle \left\{{\begin{array}{lcr}\|\mathbf {w} \|^{2}\to \min \\c_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1,\quad 1\leq i\leq n.\\\end{array}}\right.}$

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

${\displaystyle \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}} \geq 0,\quad 1\leq i\leq n\\\end{array}}\right.(2)}

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

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

${\displaystyle \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}} \geq 0,\quad 1\leq i\leq n\\\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}=0\\\end{array}}\right.(3)}$

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

${\displaystyle \mathbf {w} =\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}\mathbf {x_{i}} }$

${\displaystyle \mathbf {b} =\mathbf {w} \cdot \mathbf {x_{i}} -c_{i},\quad \mathbf {\lambda } _{i}>0}$

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

${\displaystyle a(x)=sign\left(\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}\mathbf {x_{i}} \cdot \mathbf {x} -b\right)(4)}$

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

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

${\displaystyle \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)\geq 1-\xi _{i},\quad 1\leq i\leq n\\\xi _{i}\geq 0,\quad 1\leq i\leq n\\\end{array}}\right.}$

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

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

${\displaystyle \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}} )-b)-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}} \geq 0,\mathbf {\lambda _{i}} \geq 0,\mathbf {\eta _{i}} \geq 0,\quad 1\leq i\leq 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\leq i\leq n\\\left[{\begin{array}{lcr}\mathbf {\eta _{i}} =0\\\mathbf {\xi _{i}} =0,\\\end{array}}\right.\quad 1\leq i\leq n\end{array}}\right.}

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

${\displaystyle \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\leq \mathbf {\lambda _{i}} \leq \mathbf {C} ,\quad 1\leq i\leq n\\\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}=0\\\end{array}}\right.}$

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

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

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

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

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

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

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

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

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

• Владимир Вьюгин. Математические основы теории машинного обучения и прогнозирования. — МЦМНО, 2013. — 390 с. — ISBN 978-5-4439-0111-4.
• Nello Cristianini, John Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. — Cambridge University Press, 2000. — ISBN 978-1-139-64363-4.
• Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. A Gentle Introduction to Support Vector Machines in Biomedicine: Theory and methods. — World Scientific, 2011. — ISBN 978-981-4324-38-0.
• Alexey Nefedov. Support Vector Machines: A Simple Tutorial. — 2016.

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