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

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

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

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

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

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

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

Содержание

1 Постановка задачи линейной классификации
2 Описание алгоритма
- 2.1 Понятие оптимальной разделяющей гиперплоскости
- 2.2 Линейно разделимая выборка
3 Вычислительный эксперимент
4 Исходный код
5 Смотри также
6 Литература

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

Рассматривается задача обучения по прецедентам $\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://recognition.su/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»

Категории: Практика и вычислительные эксперименты | Классификация | Линейные классификаторы

@@ Строка 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). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
@@ Строка 10: / Строка 10: @@
 зависимость на всём пространстве <tex>X</tex>.
-Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами<tex>:\ X\ =\ \mathbb{R}^n,\ Y\ =\ \{-1,+1\}</tex>.
+Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами:<tex>\ X\ =\ \mathbb{R}^n,\ Y\ =\ \{-1,+1\}</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>\mathbb{R}^n</tex>.
-Уравнение <tex><w,x>\ =\ w_0</tex> описывает гиперплоскость, разделяющую классы в про-
-странстве <tex>\mathbb{R}^n</tex>.
 == Описание алгоритма ==
 === Понятие оптимальной разделяющей гиперплоскости ===
@@ Строка 26: / Строка 25: @@
 ::<tex>Q(w,w_0)\ =\ \sum_{i=1}^\ell [y_i(<w,x_i>\ -\ w_0)\ <\ 0]</tex>
-принимает нулевое значение. Но тогда разделяющая гиперплоскость не единствен-
+принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.
-на. Можно выбрать другие её положения, реализующие такое же разбиение выборки
-на два класса. Идея метода заключается в том, чтобы разумным образом распоря-
-диться этой свободой выбора.
-Потребуем, чтобы разделяющая
+Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора между классами должна способствовать более надёжной классификации.
-гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих клас-
-сов. Первоначально данный принцип классификации возник из эвристических сооб-
-ражений: вполне естественно полагать, что максимизация зазора (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>.
-Сделать это возможно, поскольку при оптимальном положении разделяющей гипер-
+Сделать это возможно, поскольку при оптимальном положении разделяющей гиперплоскости все пограничные объекты находятся от неё на одинаковом расстоянии.
-плоскости все пограничные объекты находятся от неё на одинаковом расстоянии.
 Остальные объекты находятся дальше. Таким образом, для всех <tex>x_i\  \in\  X^\ell</tex>
 {{eqno|1}}
@@ Строка 65: / Строка 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>. Параметры полосы найдены и можно строить разделяюую полосу.
-== Исследование на устойчивость алгоритма 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 ===
+Опишем алгоритм по которому будем избавляться от выбросов:
+. Проверяем, можно ли разделить все точки исходной выборки на два класса, так чтобы точки первого класса были по одну сторону от прямой, а точки второго класса по другую сторону. Если можем разделить, то строим эту плоскость и заканчиваем алгоритм. Иначе идем в пункт 2.;
+. Выбираем случайным образом по половине точек из каждого класса исходной выборки. Проверяем, можно ли разделить все точки новой выборки на два класса по алгоритму из пункта 1.; Если можем, то получаем параметры новой разделяющей прямой и идем в пункт 3. Иначе повторяем пункт 2.;
+. Находим все неправильно классифицированные точки относительно новой прямой. Все неправильно классифицированные точки ранжируем по расстоянию от них до новой разделяющей прямой. Отбрасываем половину неправильно классифицированных точек из исходной выборки. Идем в пункт 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/]
 == Смотри также ==
@@ Строка 95: / Строка 107: @@
 * [[ SVM для линейно неразделимой выборки (пример) ]]
+== Литература ==
+* Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Статистические проблемы обучения. - Москва, "Наука", 1974.
+* Cortes C., Vapnik V. Support Vector Networks.
-{{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}}
+{{ЗаданиеВыполнено|Алексей Морозов|В.В.Стрижов|28 мая 2010|MORAL|Strijov}}
+[[Категория:Практика и вычислительные эксперименты]]
-[[Категория:Учебные материалы]]
 [[Категория:Классификация]]
 [[Категория:Линейные классификаторы]]