SVM для линейно разделимой выборки (пример)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Литература: категория)
(Исходный код)
 
(57 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''SVM (Support Vector Machine, [[машина опорных векторов]])''' - алгоритм машинного обучения, предложенный [[Вапник, Владимир Наумович|{{S|В. Н. Вапником}}]]. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, "опорных векторов", по которым и строится опорная гиперплоскость.
+
[[Изображение:Svm_with_margin.png|thumb|right|Пример разделения двух классов полосой максимальной ширины.]]
 +
'''[[Машина опорных векторов]] (SVM — support vector machines)''' — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние между ближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – опорными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
 +
 
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
== Постановка задачи линейной классификации ==
== Постановка задачи линейной классификации ==
-
{{Main|Линейный классификатор}}
 
-
Задана выборка <tex>X=\{(x_i,y_i)\}_{i=1}^l</tex>, где <tex>x_i</tex>-признаковое описание i-го объекта, <tex>y_i</tex> - идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что <tex>y_i\in\{-1,1\}</tex> (это позволяет пользоваться функцией sgn в описании классификатора).
+
Рассматривается задача обучения по прецедентам <tex>\left \langle X,\ Y,\ y*,\ X^\ell \right \rangle</tex> - , где <tex>X</tex> - пространство объектов, <tex>Y</tex> - множество ответов, <tex>y*:\ X \rightarrow Y</tex> - целевая зависимость, значения которой известны только на объектах обучающей выборки <tex>X=\(x_i,y_i\)_{i=1}^\ell\ ,\ y_i = y*(x_i)</tex>. Требуется построить алгоритм <tex>a:\ X \rightarrow Y</tex>, аппроксимирующий целевую
 +
зависимость на всём пространстве <tex>X</tex>.
-
Требуется построить классификатор вида <tex>a(x)=sign(<w,x>-w_0)</tex>, где <tex><w,x></tex> - скалярное произведение, а <tex>w,w_0</tex> - вектор и число, характеризующий данный классификатор. Можно говорить о том, что <tex>w_i</tex>-веса признаков, <tex>w_0</tex> - порог принятия решения.
+
Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами:<tex>\ X\ =\ \mathbb{R}^n,\ Y\ =\ \{-1,+1\}</tex>.
-
Если для данной выборки существуют <tex>w,w_0</tex> такие, что <tex>a(x)</tex> не ошибается на обучающей выборке, то она называется ''линейно разделимой''. В противном случае, выборка называется ''линейно неразделимой''.
+
Будем строить линейный пороговый классификатор:
 +
::<tex>a(x)\ =\ sign(\sum_{j=1}^n w_jx^j\ -\ w_0)\ =\ sign(<w,x>\ -\ w_0)</tex>,
 +
где <tex>x\ =\ (x^1,...,x^n)</tex> - признаковое описание объекта <tex>x</tex>; вектор <tex>w\ =\ (w^1,...,w^n)\ \in\ \mathbb{R}</tex> и скалярный порог <tex>w_0\ \in\ \mathbb{R}</tex> являются параметрами алгоритма.
 +
 
 +
Уравнение <tex><w,x>\ =\ w_0</tex> описывает гиперплоскость, разделяющую классы в пространстве <tex>\mathbb{R}^n</tex>.
== Описание алгоритма ==
== Описание алгоритма ==
-
=== Линейно разделимая выборка ===
+
=== Понятие оптимальной разделяющей гиперплоскости ===
-
Если выборка линейно разделима, то существует бесконечно много линейных классификаторов, не ошибающихся на ней.
+
-
В алгоритме SVM минимизируется расстояние от опорной гиперплоскости до обоих классов.
+
-
Отнормируем вектор нормали к разделяющей гиперплоскости <tex>w</tex> и порог принятия решения <tex>w_0</tex> так, чтобы
 
-
выполнялось условие <tex>\min\limits_{i=1,l} y_i(<w,x_i>-w_0)=1</tex>. Это всегда можно сделать, поскольку, во-первых, умножение <tex>w,w_0</tex> на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов.
 
-
Нетрудно показать, что при такой нормировке ширина разделяющей полосы может быть представлена в виде: <tex>\frac{2}{||w||}</tex>. Максимизация этой величины равносильна минимизации нормы вектора нормали. Таким образом, параметры линейного классификатора определяются из задачи квадратичного программирования:
+
Предположим, что выборка <tex>X=\(x_i,y_i\)_{i=1}^\ell\</tex> линейно разделима. Тогда существуют значения параметров <tex>w,\ w_0</tex>, при которых функционал числа ошибок
-
::<tex>\left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,l\\ \right.</tex>
+
::<tex>Q(w,w_0)\ =\ \sum_{i=1}^\ell [y_i(<w,x_i>\ -\ w_0)\ <\ 0]</tex>
-
Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей:
+
 
 +
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.
 +
 
 +
Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора между классами должна способствовать более надёжной классификации.
 +
 
 +
Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: алгоритм <tex>a(x)</tex> не изменится, если <tex>w</tex> и <tex>w_0</tex> одновременно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов <tex>x_i</tex> из <tex>X^\ell</tex> выполнялись условия ::<tex><w,x_i>\ -\ w_0\ =\ y_i</tex>.
 +
 
 +
Сделать это возможно, поскольку при оптимальном положении разделяющей гиперплоскости все пограничные объекты находятся от неё на одинаковом расстоянии.
 +
Остальные объекты находятся дальше. Таким образом, для всех <tex>x_i\ \in\ X^\ell</tex>
{{eqno|1}}
{{eqno|1}}
-
::<tex>\left{-\sum\limits_{i=1}^l\lambda_i+\frac{1}{2}\sum\limits_{i=1}^l\sum\limits_{j=1}^l\lambda_i\lambda_jy_iy_j<x_i,x_j>\rightarrow \min\limits_\lambda \\ \lambda_i\ge 0\quad i=1,...,l\\ \sum\limits_{i=1}^l\lambda_iy_i=0\quad\right. </tex>
+
<tex><w,x_i> - w_0
 +
\begin{cases}
 +
\le -1, & \mbox{if }y_i=-1; \\
 +
\ge 1, & \mbox{if }y_i=+1.
 +
\end{cases}
 +
</tex>
-
Таким образом, решив оптимизационную задачу {{eqref|1}}, то есть, найдя вектор <tex>\lambda</tex>, вычислим <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i,\lambda_i>0, i=1,...,l\}</tex>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.
+
Условие <tex>-1\ <\ \left \Big\langle w,x \right \Big\rangle -w_0<\ 1\ </tex> задаёт полосу, разделяющую классы. Ширина полосы, как не сложно показать, равна <tex>\frac{2}{||w||}</tex>. Она максимальна, когда норма вектора <tex>w</tex> минимальна.
 +
 
 +
=== Линейно разделимая выборка ===
 +
Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при <tex>\ell</tex> ограничениях-неравенствах вида {{eqref|1}} относительно <tex>n+1</tex> переменных <tex>w,\ w_0:</tex>
 +
::<tex>\left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,\ell\\ \right.</tex>
 +
 
 +
Используя аппарат функций Лагранжа, перейдем к решению двойственной задаче. Несложно показать эквивалентность этой задачи и следующей:
 +
::<tex>\left{-\mathcal{L}(\lambda)=-\sum\limits_{i=1}^\ell\lambda_i+\frac{1}{2}\sum\limits_{i=1}^\ell\sum\limits_{j=1}^\ell\lambda_i\lambda_jy_iy_j(<x_i,x_j>)\rightarrow \min\limits_\lambda \\ \lambda_i\ge 0\quad, i=1,...,\ell\\ \sum\limits_{i=1}^\ell\lambda_iy_i=0\quad\right. </tex>
 +
 
 +
Вектор весов будем искать в ввиде <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i</tex>. Для определения порога <tex>w_0</tex> достаточно взять произвольный опорный вектор <tex>x_i</tex> и выразить <tex>w_0</tex> из равенства <tex>w_0=<w,x_i>-y_i</tex>. На практике для повышения численной устойчивости лучше взять в качестве <tex>w_0</tex> медиану: <tex>w_0=med\{<w_i,x_i>-y_i:\ \lambda_i>0,\ i=1,...,\ell\}</tex>. Параметры полосы найдены и можно строить разделяюую полосу.
 +
 
 +
 
 +
 
 +
== Вычислительный эксперимент ==
 +
 
 +
Вычислительный экстперимент разбит на три частей:
 +
::1. Нормальное распределение выборки;
 +
::2. Реализация алгоритма SVM для линейно разделимой выборки;
 +
::3. Исследование устойчивости алгоритма SVM;
 +
 
 +
=== Нормальное распределение выборки ===
 +
 
 +
Нормальным случайным распределением генерируются два класса обьектов по 10 обьектов в каждом классе.
 +
[[Изображение:Normal distribution.png|1000px]]
 +
 
 +
=== Реализация алгоритма SVM для линейно разделимой выборки ===
 +
В ходе вычислений определяются параметры раздляющей полосы. Классы линейно разделимы и ширина зазора максимальна, как видно на рисунке снизу.
 +
 
 +
[[Изображение:Classified classes example.png|1000px]]
 +
 
 +
Но алгоритм не очень хорош тем, что очень чувствителен к выбросам
 +
[[Изображение:Outlier example.png|1000px]]
 +
 
 +
=== Исследование устойчивости алгоритма SVM ===
 +
В этой части вычислительного эксперимента исследуется зависимость параметров разделяющей прямой и среднеквадратичного отклонения параметров разделяющей прямой от среднеквадратичного отклонения выборки. Параметры разделяющей гипперплоскости на графике w_0,w_1 и w_2. Как можем видеть, с увеличением среднеквадратичного отклонения выборки параметры прямой сильно колеблются.
 +
[[Изображение:Stability of SVM.png|1000px]]
 +
 
 +
=== Удаление шумовых выбросов алгоритма SVM ===
 +
Опишем алгоритм по которому будем избавляться от выбросов:
 +
 
 +
1. Проверяем, можно ли разделить все точки исходной выборки на два класса, так чтобы точки первого класса были по одну сторону от прямой, а точки второго класса по другую сторону. Если можем разделить, то строим эту плоскость и заканчиваем алгоритм. Иначе идем в пункт 2.;
 +
 
 +
2. Выбираем случайным образом по половине точек из каждого класса исходной выборки. Проверяем, можно ли разделить все точки новой выборки на два класса по алгоритму из пункта 1.; Если можем, то получаем параметры новой разделяющей прямой и идем в пункт 3. Иначе повторяем пункт 2.;
 +
 
 +
3. Находим все неправильно классифицированные точки относительно новой прямой. Все неправильно классифицированные точки ранжируем по расстоянию от них до новой разделяющей прямой. Отбрасываем половину неправильно классифицированных точек из исходной выборки. Идем в пункт 1.
 +
 
 +
 
 +
 
 +
Сгенерировали случайную выборку из двух классов. Видно что линейно она неразделимая.
 +
[[Изображение:Training_sample.png|1000px]]
 +
 
 +
Использовав алгоритм удаления выбросов получаем линейно разделимую выборку.
 +
[[Изображение:Classified_sample.png|1000px]]
 +
 
 +
Математические ожидания обоих классов равны (1,1) и (4,4) соответственно. Среднеквадратичное отклонение обоих классов равно (3,3).
 +
Из графика видно что, классы разделены качественно.
 +
 
 +
== Исходный код ==
 +
Код MATLAB можно скачать здесь: [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Morozov2010SVMLinear/]
== Смотри также ==
== Смотри также ==
Строка 33: Строка 106:
* [[ Численные методы обучения по прецедентам (практика, В.В. Стрижов) ]]
* [[ Численные методы обучения по прецедентам (практика, В.В. Стрижов) ]]
* [[ SVM для линейно неразделимой выборки (пример) ]]
* [[ SVM для линейно неразделимой выборки (пример) ]]
 +
== Литература ==
== Литература ==
-
* Воронцов К.В. Лекции по линейным алгоритмам классификации
+
* Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Статистические проблемы обучения. - Москва, "Наука", 1974.
 +
* Cortes C., Vapnik V. Support Vector Networks.
 +
{{ЗаданиеВыполнено|Алексей Морозов|В.В.Стрижов|28 мая 2010|MORAL|Strijov}}
 +
[[Категория:Практика и вычислительные эксперименты]]
[[Категория:Классификация]]
[[Категория:Классификация]]
-
[[Категория:Энциклопедия анализа данных]]
 
[[Категория:Линейные классификаторы]]
[[Категория:Линейные классификаторы]]

Текущая версия

Пример разделения двух классов полосой максимальной ширины.
Пример разделения двух классов полосой максимальной ширины.

Машина опорных векторов (SVM — support vector machines) — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние между ближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – опорными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.


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

Содержание

Постановка задачи линейной классификации

Рассматривается задача обучения по прецедентам \left \langle X,\ Y,\ y*,\ X^\ell \right \rangle - , где X - пространство объектов, Y - множество ответов, y*:\ X \rightarrow Y - целевая зависимость, значения которой известны только на объектах обучающей выборки X=\(x_i,y_i\)_{i=1}^\ell\ ,\ y_i = y*(x_i). Требуется построить алгоритм a:\ X \rightarrow Y, аппроксимирующий целевую зависимость на всём пространстве X.

Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами:\ X\ =\ \mathbb{R}^n,\ Y\ =\ \{-1,+1\}.

Будем строить линейный пороговый классификатор:

a(x)\ =\ sign(\sum_{j=1}^n w_jx^j\ -\ w_0)\ =\ sign(<w,x>\ -\ w_0),

где x\ =\ (x^1,...,x^n) - признаковое описание объекта x; вектор w\ =\ (w^1,...,w^n)\ \in\ \mathbb{R} и скалярный порог w_0\ \in\ \mathbb{R} являются параметрами алгоритма.

Уравнение <w,x>\ =\ w_0 описывает гиперплоскость, разделяющую классы в пространстве \mathbb{R}^n.

Описание алгоритма

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

Предположим, что выборка X=\(x_i,y_i\)_{i=1}^\ell\ линейно разделима. Тогда существуют значения параметров w,\ w_0, при которых функционал числа ошибок

Q(w,w_0)\ =\ \sum_{i=1}^\ell [y_i(<w,x_i>\ -\ w_0)\ <\ 0]

принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.

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

Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: алгоритм a(x) не изменится, если w и w_0 одновременно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов x_i из X^\ell выполнялись условия ::<w,x_i>\ -\ w_0\ =\ y_i.

Сделать это возможно, поскольку при оптимальном положении разделяющей гиперплоскости все пограничные объекты находятся от неё на одинаковом расстоянии. Остальные объекты находятся дальше. Таким образом, для всех x_i\  \in\  X^\ell

(1)

<w,x_i> - w_0
\begin{cases} 
\le -1, & \mbox{if }y_i=-1; \\
\ge 1, & \mbox{if }y_i=+1.
\end{cases}

Условие -1\ <\ \left \Big\langle w,x \right \Big\rangle -w_0<\ 1\ задаёт полосу, разделяющую классы. Ширина полосы, как не сложно показать, равна \frac{2}{||w||}. Она максимальна, когда норма вектора w минимальна.

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

Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при \ell ограничениях-неравенствах вида (1) относительно n+1 переменных w,\ w_0:

\left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,\ell\\ \right.

Используя аппарат функций Лагранжа, перейдем к решению двойственной задаче. Несложно показать эквивалентность этой задачи и следующей:

\left{-\mathcal{L}(\lambda)=-\sum\limits_{i=1}^\ell\lambda_i+\frac{1}{2}\sum\limits_{i=1}^\ell\sum\limits_{j=1}^\ell\lambda_i\lambda_jy_iy_j(<x_i,x_j>)\rightarrow \min\limits_\lambda \\ \lambda_i\ge 0\quad, i=1,...,\ell\\ \sum\limits_{i=1}^\ell\lambda_iy_i=0\quad\right.

Вектор весов будем искать в ввиде w = \sum\limits_{i=1}^l\lambda_ix_iy_i. Для определения порога w_0 достаточно взять произвольный опорный вектор x_i и выразить w_0 из равенства w_0=<w,x_i>-y_i. На практике для повышения численной устойчивости лучше взять в качестве w_0 медиану: w_0=med\{<w_i,x_i>-y_i:\ \lambda_i>0,\ i=1,...,\ell\}. Параметры полосы найдены и можно строить разделяюую полосу.


Вычислительный эксперимент

Вычислительный экстперимент разбит на три частей:

1. Нормальное распределение выборки;
2. Реализация алгоритма SVM для линейно разделимой выборки;
3. Исследование устойчивости алгоритма SVM;

Нормальное распределение выборки

Нормальным случайным распределением генерируются два класса обьектов по 10 обьектов в каждом классе.

Реализация алгоритма SVM для линейно разделимой выборки

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

Но алгоритм не очень хорош тем, что очень чувствителен к выбросам

Исследование устойчивости алгоритма SVM

В этой части вычислительного эксперимента исследуется зависимость параметров разделяющей прямой и среднеквадратичного отклонения параметров разделяющей прямой от среднеквадратичного отклонения выборки. Параметры разделяющей гипперплоскости на графике w_0,w_1 и w_2. Как можем видеть, с увеличением среднеквадратичного отклонения выборки параметры прямой сильно колеблются.

Удаление шумовых выбросов алгоритма SVM

Опишем алгоритм по которому будем избавляться от выбросов:

1. Проверяем, можно ли разделить все точки исходной выборки на два класса, так чтобы точки первого класса были по одну сторону от прямой, а точки второго класса по другую сторону. Если можем разделить, то строим эту плоскость и заканчиваем алгоритм. Иначе идем в пункт 2.;

2. Выбираем случайным образом по половине точек из каждого класса исходной выборки. Проверяем, можно ли разделить все точки новой выборки на два класса по алгоритму из пункта 1.; Если можем, то получаем параметры новой разделяющей прямой и идем в пункт 3. Иначе повторяем пункт 2.;

3. Находим все неправильно классифицированные точки относительно новой прямой. Все неправильно классифицированные точки ранжируем по расстоянию от них до новой разделяющей прямой. Отбрасываем половину неправильно классифицированных точек из исходной выборки. Идем в пункт 1.


Сгенерировали случайную выборку из двух классов. Видно что линейно она неразделимая.

Использовав алгоритм удаления выбросов получаем линейно разделимую выборку.

Математические ожидания обоих классов равны (1,1) и (4,4) соответственно. Среднеквадратичное отклонение обоих классов равно (3,3). Из графика видно что, классы разделены качественно.

Исходный код

Код MATLAB можно скачать здесь: [1]

Смотри также

Литература

  • Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Статистические проблемы обучения. - Москва, "Наука", 1974.
  • Cortes C., Vapnik V. Support Vector Networks.


Данная статья была создана в рамках учебного задания.
Студент: Алексей Морозов
Преподаватель: В.В.Стрижов
Срок: 28 мая 2010


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Личные инструменты