Машина опорных векторов

Материал из MachineLearning.

(Различия между версиями)

Версия 07:20, 23 июля 2008

Машина опорных векторов — является одной из наиболее популярных методологий обучения по прецедентам, предложенной В. Н. Вапником и известной в англоязычной литературе под названием SVM (Support Vector Machine).

Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin). Случай линейной разделимости. Задача квадратичного программирования. Опорные векторы. Случай отсутствия линейной разделимости. Функции ядра (kernel functions), спрямляющее пространство, теорема Мерсера. Способы построения ядер. Примеры ядер. Сопоставление SVM и нейронной RBF-сети. Обучение SVM методом активных ограничений. SVM-регрессия.

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Содержание

1 Машина опорных векторов в задачах классификации
2 Машина опорных векторов в задачах регрессии
3 Программные реализации
4 Литература
5 Ссылки

Машина опорных векторов в задачах классификации

Понятие оптимальной разделяющей гиперплоскости

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

Линейно разделимая выборка

Рассмотрим задачу нахождения наилучшего в некотором смысле разделения множества векторов на два класса с помощью линейной решающей функции. Пусть имеется множество прецедентов $(\Xi ,Y)$ , где $\Xi = \{ {\bf{x}}_1 ,...,{\bf{x}}_N \}$ - обучающая выборка, а $Y = (y_1 ,...,y_N )$ - множество меток двух классов $\omega _1$ и $\omega _2$ . Требуется по обучающей выборке построить линейную решающую функции, т.е. такую линейную функцию $f({\bf{x}})$ , которая удовлетворяла бы условию

                            для всех ,

                            для всех .

Без ограничения общности можно считать, что метки классов равны

Тогда поставленную выше задачу можно переформулировать следующим образом. Требуется найти линейную решающую функцию $f({\bf{x}})$ , которая бы удовлетворяла условию

                         для всех                            (1)

Умножая, если нужно функцию $f$ на некоторое положительное число нетрудно видеть, что система неравенств (1) равносильна системе

                            для всех    .

Кроме того, так как $f({\bf{x}})$ линейная функция, то последняя система неравенств примет вид

                        ,                              (2)

где ${\bf{w}}$ вектор весовых коэффициентов, $b$ некоторое число. Тогда разделяющей два класса гиперплоскостью будет $({\bf{w}},{\bf{x}}) + b = 0$ . Нетрудно видеть, что и все гиперплоскости вида $({\bf{w}},{\bf{x}}) + b' = 0$ , где $b' \in (b - 1,b + 1)$ также будут разделяющими (рис.1). Расстояние между граничными гиперплоскостями $({\bf{w}},{\bf{x}}) + b - 1 = 0$ и $({\bf{w}},{\bf{x}}) + b + 1 = 0$ равно ${{\frac {{2}}{{\left\| {\bf{w}} \right\|}}$ . Действительно, $\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b - 1}}{{\left\| {\bf{w}} \right\|}} = 0$ и $\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b + 1}}{{\left\| {\bf{w}} \right\|}} = 0$ нормальные уравнения этих гиперплоскостей. Тогда $p_1 = \frac{{b - 1}}{{\left\| {\bf{w}} \right\|}}$ и $p_2 = \frac{{b + 1}}{{\left\| {\bf{w}} \right\|}}$ расстояния от этих гиперплоскостей до начала координат и ${{\frac {{2}}{{\left\| {\bf{w}} \right\|}}$ расстояние между гиперплоскостями. На самих граничных плоскостях может находиться некоторое число (не меньше двух) обучающих векторов. Эти векторы называются опорными.

Для надежного разделения классов необходимо чтобы расстояние между разделяющими гиперплоскостями было как можно большим, т.е. $\left\| {\bf{w}} \right\|$ была как можно меньше. Таким образом, ставится задача нахождения минимума квадратичного функционала $0.5({\bf{w}},{\bf{w}})$ (коэффициент 0.5 вводится для удобства дифференцирования) в выпуклом многограннике, задаваемым системой неравенств (2). В выпуклом множестве квадратичный функционал всегда имеет единственный минимум (если это множество не пусто). Из теоремы Куна-Таккера следует, что решение этой оптимизационной задачи равносильно поиску седловой точки лагранжиана

в ортанте по множителям Лагранжа $\lambda _i \ge 0\;\;(i = 1,...,N)$ , при условии, что

Последнее условие равносильно тому, что

                        или                      (3)

Из необходимых условий существования седловой точки (полагая ${\bf{x}}_i = (x_{i1} ,x_{i2} ,...,x_{in} )$ ) имеем

Откуда следует, что вектор ${\bf{w}}$ следует искать в виде

                               ,                                (4)

причем

                                .	                               (5)

В силу (3) в сумму (4) с ненулевыми коэффициентами $\lambda _i$ входят только те векторы, для которых $y_i (({\bf{w}},{\bf{x}}_i ) + b) - 1 = 0$ . Такие векторы называют опорными, так как это именно те векторы, через которые будут проходить граничные гиперплоскости, разделяющие классы. Для найденного весового вектора ${\bf{w}}$ смещение $b$ можно вычислить как $b = {y_s}^{-1} - ({\bf{w}},{\bf{x}}_s )$ для любого опорного вектора ${\bf{x}}_s$ .

Найдем значения множителей Лагранжа, как критических точек лагранжиана. Для этого подставим (4) и (5) в лагранжиан, получим

Таким образом, задача сводится к нахождению критических точек функции

                          .	                         		(6)

Так как эта функция представляет собой разность линейной и квадратичной функций, причем квадратичная функция отрицательно определена, то требуется найти наибольшее значение функции $\Phi ({\bf{\lambda }})$ при условии $\sum\nolimits_{i = 1}^N {\lambda _i y_i } = 0$ в области $\lambda _i \ge 0\;\;(i = 1,...,N)$ . Существует много алгоритмов (в теории оптимизации) решения этой задачи (например, градиентные методы, метод покоординатного спуска и т.д.).

Замечания. 1) Суммирования в (6) осуществляются не по всем векторам, а только по опорным, которых может быть гораздо меньше, чем обучающих.

2) Линейная решающая функция в результате имеет вид

где $\lambda _i$ зависят только $y_i$ и от значений скалярного произведения $({\bf{x}}_i ,{\bf{x}}_j )$ , причем суммирования осуществляются только по опорным векторам.

3) После того, как решающая функция $f({\bf{x}})$ вычислена, вектор ${\bf{x}}$ следует относить классу $\omega _1$ , если $f({\bf{x}}) > 0$ и классу $\omega _2$ , если $f({\bf{x}}) < 0$ . Вероятность неправильной классификации можно оценить с помощью некоторой непрерывно убывающей функции $\varphi (t)$ , удовлетворяющей условиям: $\varphi (0) = 0.5$ , $\varphi (t) \to 0$ при $t \to \infty$ . Тогда вероятность $p({\bf{x}})$ неправильной классификации вектора ${\bf{x}}$ будет равна $\varphi \left( {\rho ({\bf{x}},L_i )} \right)$ , если ${\bf{x}} \in \omega _i$ ( $i = 1,2$ ), где ${L_i}$ : $({\bf{w}},{\bf{x}}) + b + {{\rm sgn}} (\alpha - i) = 0$ , $1 < \alpha < 2$ . То есть $p({\bf{x}}) = \varphi \left( {\left| {\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b + {{\rm sgn}} (\alpha - i)}}{{\left\| {\bf{w}} \right\|}}} \right|} \right)$ , если ${\bf{x}} \in \omega _i$ $(i = 1,2)$ .

4) В такой постановке алгоритм линейный классификации был разработан В. Вапником в 1963 году.

Пример. Методом опорных векторов разделите классы $\omega _1 = \left\{ {{\bf{x}}_1 } \right\}$ и $\omega _2 = \left\{ {{\bf{x}}_2 ,{\bf{x}}_3 } \right\}$ , если ${\bf{x}}_1 = (1,1)^T$ , ${\bf{x}}_2 = (1,2)^T$ , ${\bf{x}}_3 = (2,3)^T$ .

Решение. Положим $y_1 = 1$ , $y_2 = - 1$ , $y_3 = - 1$ . Тогда функция $\Phi ({\bf{\lambda }})$ будет иметь вид

причем $\lambda _1 - \lambda _2 - \lambda _3 = 0 \Rightarrow \lambda _3 = \lambda _1 - \lambda _2$ . Тогда $\Phi (\lambda _1 ,\lambda _2 ) = 2\lambda _1 - 2.5\lambda _1^2 - \lambda _2^2 + 3\lambda _1 \lambda _2$ . Составим и решим нормальную систему для функции $\Phi (\lambda _1 ,\lambda _2 )$ :

Следовательно, $\lambda _1 = 4$ , $\lambda _2 = 6$ , $\lambda _3 = - 2$ . Так как $\lambda _3 < 0$ , то исследуем функцию $\Phi ({\bf{\lambda }})$ на границе области $\lambda _i \ge 0\;\;(i = 1,2,3)$ при условии $\lambda _3 = \lambda _1 - \lambda _2$ . Если $\lambda _1 = 0$ , то $\lambda _3 = - \lambda _2 \Rightarrow \lambda _i^{(1)} = 0\;\;(i = 1,2,3) \Rightarrow \Phi ({\bf{\lambda }}^{(1)} ) = 0$ . Пусть $\lambda _2 = 0$ . Тогда $\lambda _1 = \lambda _3 = \lambda$ и $\Phi (\lambda ) = 2\lambda - 2.5\lambda ^2$ , $\Phi '(\lambda ) = 0$ при $\lambda ^{(2)} = {2/5}$ . Следовательно, $\lambda _1^{(2)} = \lambda _3^{(2)} = {2/5}$ , $\lambda _2^{(2)} = 0$ и $\Phi ({\bf{\lambda }}^{(2)} ) = {2/5}$ .

Если же $\lambda _3 = 0$ , то $\lambda _1 = \lambda _2 = \lambda$ и $\Phi (\lambda ) = 2\lambda - 0.5\lambda ^2$ , $\Phi '(\lambda ) = 0$ при $\lambda ^{(3)} = 2$ . Следовательно, $\lambda _1^{(3)} = \lambda _2^{(3)} = 2$ , $\lambda _3^{(3)} = 0$ и $\Phi ({\bf{\lambda }}^{(3)} ) = 2$ .

Таким образом, наибольшее значение функции $\Phi ({\bf{\lambda }})$ в области $\lambda _i \ge 0$ $(i = 1,2,3)$ при условии $\lambda _3 = \lambda _1 - \lambda _2$ достигается в точке ${\bf{\lambda }}^{(3)} = \left( {2,2,0} \right)^T$ . В этом случае,

Таким образом, $f({\bf{x}}) = ({\bf{w}},{\bf{x}}) + b = - 2x_2 + 3$ и $f({\bf{x}}) = 0 \Leftrightarrow x_2 = 1.5$ . Ширина разделяющей полосы будет равна ${{\frac {{2}}{{\left\| {\bf{w}} \right\|}}$ , а прямые $f({\bf{x}}) + 1 = 0 \Leftrightarrow f({\bf{x}}) = 0 \Leftrightarrow x_2 = 2$ и $f({\bf{x}}) - 1 = 0 \Leftrightarrow x_2 = 1$ будут ее границами (см. рис.2).

Линейно неразделимая выборка

Ядра и спрямляющие пространства

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

Полиномиальное: $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$

Алгоритмы настройки

Машина опорных векторов в задачах регрессии

Программные реализации

Литература

Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с. (подробнее)
Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p. (подробнее)

Ссылки

Машинное обучение (курс лекций, К.В.Воронцов)

Источник — «http://recognition.su/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2»

Категории: Незавершённые статьи | Классификация | Энциклопедия анализа данных

@@ Строка 36: / Строка 36: @@
                          <tex>y_i (({\bf{w}},{\bf{x}}_i ) + b) \ge 1,\quad i = 1,...,N</tex>,                              (2)
-где <tex>{\bf{w}}</tex> вектор весовых коэффициентов, <tex>b</tex> некоторое число. Тогда разделяющей два класса гиперплоскостью будет <tex>({\bf{w}},{\bf{x}}) + b = 0</tex>. Нетрудно видеть, что и все гиперплоскости вида <tex>({\bf{w}},{\bf{x}}) + b' = 0</tex>, где <tex>b' \in (b - 1,b + 1)</tex> также будут разделяющими (рис.1). Расстояние между граничными гиперплоскостями <tex>({\bf{w}},{\bf{x}}) + b - 1 = 0</tex> и <tex>({\bf{w}},{\bf{x}}) + b + 1 = 0</tex> равно <tex>{{\frac {{2}}{{\left\| {\bf{w}} \right\|}} </tex>. Действительно, <tex>\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b - 1}}{{\left\| {\bf{w}} \right\|}} = 0</tex> и <tex>\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b + 1}}{{\left\| {\bf{w}} \right\|}} = 0</tex>   нормальные уравнения этих гиперплоскостей. Тогда <tex>p_1  = \frac{{b - 1}}{{\left\| {\bf{w}} \right\|}}</tex> и <tex>p_2  = \frac{{b + 1}}{{\left\| {\bf{w}} \right\|}}</tex>   расстояния от этих гиперплоскостей до начала координат и <tex>{{\frac {{2}}{{\left\| {\bf{w}} \right\|}} </tex> расстояние между гиперплоскостями. На самих граничных плоскостях может находиться некоторое число (не меньше двух) обучающих векторов. Эти векторы называются ''опорными''.[[Изображение:pic_1.jpg|thumb]]
+где <tex>{\bf{w}}</tex> вектор весовых коэффициентов, <tex>b</tex> некоторое число. Тогда разделяющей два класса гиперплоскостью будет <tex>({\bf{w}},{\bf{x}}) + b = 0</tex>. Нетрудно видеть, что и все гиперплоскости вида <tex>({\bf{w}},{\bf{x}}) + b' = 0</tex>, где <tex>b' \in (b - 1,b + 1)</tex> также будут разделяющими (рис.1). Расстояние между граничными гиперплоскостями <tex>({\bf{w}},{\bf{x}}) + b - 1 = 0</tex> и <tex>({\bf{w}},{\bf{x}}) + b + 1 = 0</tex> равно <tex>{{\frac {{2}}{{\left\| {\bf{w}} \right\|}} </tex>. Действительно, <tex>\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b - 1}}{{\left\| {\bf{w}} \right\|}} = 0</tex> и <tex>\left( {\frac{{\bf{w}}}{{\left\| {\bf{w}} \right\|}},{\bf{x}}} \right) + \frac{{b + 1}}{{\left\| {\bf{w}} \right\|}} = 0</tex>   нормальные уравнения этих гиперплоскостей. Тогда <tex>p_1  = \frac{{b - 1}}{{\left\| {\bf{w}} \right\|}}</tex> и <tex>p_2  = \frac{{b + 1}}{{\left\| {\bf{w}} \right\|}}</tex>   расстояния от этих гиперплоскостей до начала координат и <tex>{{\frac {{2}}{{\left\| {\bf{w}} \right\|}} </tex> расстояние между гиперплоскостями. На самих граничных плоскостях может находиться некоторое число (не меньше двух) обучающих векторов. Эти векторы называются ''опорными''.[[Изображение:pic_l_1.jpg|thumb]]
 Для надежного разделения классов необходимо чтобы расстояние между разделяющими гиперплоскостями было как можно большим, т.е. <tex>\left\| {\bf{w}} \right\|</tex> была как можно меньше. Таким образом, ставится задача нахождения минимума квадратичного функционала <tex>0.5({\bf{w}},{\bf{w}})</tex> (коэффициент 0.5 вводится для удобства дифференцирования) в выпуклом многограннике, задаваемым системой неравенств (2). В выпуклом множестве квадратичный функционал всегда имеет единственный минимум (если это множество не пусто). Из теоремы Куна-Таккера следует, что решение этой оптимизационной задачи равносильно поиску седловой точки лагранжиана