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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Понятие оптимальной разделяющей гиперплоскости)
(→Исходный код)
 
(39 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
[[Изображение:SVMsample.gif|thumb]]
+
[[Изображение:Svm_with_margin.png|thumb|right|Пример разделения двух классов полосой максимальной ширины.]]
-
'''[[Машина опорных векторов]] (SVM — support vector machines)''' — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние междуближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – опорными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
+
'''[[Машина опорных векторов]] (SVM — support vector machines)''' — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние между ближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – опорными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
Строка 14: Строка 14:
Будем строить линейный пороговый классификатор:
Будем строить линейный пороговый классификатор:
::<tex>a(x)\ =\ sign(\sum_{j=1}^n w_jx^j\ -\ w_0)\ =\ sign(<w,x>\ -\ w_0)</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>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><w,x>\ =\ w_0</tex> описывает гиперплоскость, разделяющую классы в пространстве <tex>\mathbb{R}^n</tex>.
-
странстве <tex>\mathbb{R}^n</tex>.
+
== Описание алгоритма ==
== Описание алгоритма ==
Строка 28: Строка 27:
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.
-
Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора (margin) между классами должна способствовать более надёжной классификации.
+
Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора между классами должна способствовать более надёжной классификации.
Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: алгоритм <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>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>.
Строка 53: Строка 52:
Вектор весов будем искать в ввиде <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>. Параметры полосы найдены и можно строить разделяюую полосу.
Вектор весов будем искать в ввиде <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>. Параметры полосы найдены и можно строить разделяюую полосу.
-
== Исследование на устойчивость алгоритма SVM для линейно разделимой выборки ==
 
-
SVM алгоритм используем матрицу <tex>\mathbf{x}^T\mathbf{x}</tex>. Проверим, устойчив ли SVM алгоритм?
 
-
Предположим что дана выбрка
 
-
::<tex>\{ \mathbf{x}_0 = \mathbf{0},\mathbf{x}_1 = \sigma \mathbf{e}_1,...,\mathbf{x}_m = \sigma \mathbf{e}_m\} \in \mathbb{R}^m </tex>
 
-
::<tex>\{ y_0 = -1,y_1 = 1,...,y_m = 1\}</tex>
 
-
В этом случае задача SVM сводится к задаче
 
-
::<tex>\left{\frac{1}{2}\sum\limits_{i=1}^m\alpha_i^2\sigma_i^2-2\sum\limits_i\alpha_i \rightarrow \min\limits_\alpha \\\alpha_i\ge 0,i=1,...,m</tex>
 
 +
== Вычислительный эксперимент ==
-
где <tex> \alpha_0=\sum\limits_{i=1}^m\alpha_i </tex>.
+
Вычислительный экстперимент разбит на три частей:
 +
::1. Нормальное распределение выборки;
 +
::2. Реализация алгоритма SVM для линейно разделимой выборки;
 +
::3. Исследование устойчивости алгоритма SVM;
-
Приведенная задачи имеет решение <tex>\left ( \alpha_0^*, \frac{2}{\sigma_1^2},...,\frac{2}{\sigma_m^2} \right )</tex>
+
=== Нормальное распределение выборки ===
-
где <tex>\alpha_0^*=\sum\limits_{i=1}^m\frac{2}{\sigma_i^2},\mathbf{w}=\left ( \frac{2}{\sigma_1^2},...,\frac{2}{\sigma_m^2} \right ), </tex> и <tex>b=1.</tex>
+
Нормальным случайным распределением генерируются два класса обьектов по 10 обьектов в каждом классе.
 +
[[Изображение:Normal distribution.png|1000px]]
-
Теперь пусть <tex>\sigma_i=2^{-i},\ i=1,...,80</tex>. В этом случае решение задается формулами <tex>\alpha_0^*=2\sum\limits_{i=1}^{80}{(2^i)}^2</tex> и <tex>\alpha_i^*=2{(2^i)}^2,\ i=1,...,80</tex>, где <tex>\mathbf{w}=2(2^1,...,2^{80})</tex> и <tex>b=1</tex>
+
=== Реализация алгоритма SVM для линейно разделимой выборки ===
 +
В ходе вычислений определяются параметры раздляющей полосы. Классы линейно разделимы и ширина зазора максимальна, как видно на рисунке снизу.
-
На самом деле, <tex>\alpha_0^*=2\sum\limits_{i=1}^m\alpha_i^*</tex> накладывает ограничения на точность результатов.
+
[[Изображение:Classified classes example.png|1000px]]
-
SVM алгоритм <tex>\mathbf{x}^T\mathbf{x}</tex> численно нестабилен.
+
Но алгоритм не очень хорош тем, что очень чувствителен к выбросам
 +
[[Изображение: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/]
== Смотри также ==
== Смотри также ==
Строка 83: Строка 107:
* [[ SVM для линейно неразделимой выборки (пример) ]]
* [[ SVM для линейно неразделимой выборки (пример) ]]
 +
== Литература ==
 +
* Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Статистические проблемы обучения. - Москва, "Наука", 1974.
 +
* Cortes C., Vapnik V. Support Vector Networks.
-
{{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}}
+
{{ЗаданиеВыполнено|Алексей Морозов|В.В.Стрижов|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 в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=SVM_%D0%B4%D0%BB%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE_%D1%80%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D0%B9_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BA%D0%B8_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»
Личные инструменты