SVM для линейно разделимой выборки (пример)
Материал из MachineLearning.
Машина опорных векторов (SVM — support vector machines) — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние междуближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – опорными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
Содержание |
Постановка задачи линейной классификации
Рассматривается задача обучения по прецедентам - , где
- пространство объектов,
- множество ответов,
- целевая зависимость, значения которой известны только на объектах обучающей выборки
. Требуется построить алгоритм
, аппроксимирующий целевую
зависимость на всём пространстве
.
Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами:.
Будем строить линейный пороговый классификатор:
,
где - признаковое описание объекта
; вектор
и скалярный порог
являются параметрами алгоритма.
Уравнение описывает гиперплоскость, разделяющую классы в пространстве
.
Описание алгоритма
Понятие оптимальной разделяющей гиперплоскости
Предположим, что выборка линейно разделима. Тогда существуют значения параметров
, при которых функционал числа ошибок
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.
Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора между классами должна способствовать более надёжной классификации.
Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: алгоритм не изменится, если
и
одновременно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов
из
выполнялись условия ::
.
Сделать это возможно, поскольку при оптимальном положении разделяющей гиперплоскости все пограничные объекты находятся от неё на одинаковом расстоянии.
Остальные объекты находятся дальше. Таким образом, для всех
Условие задаёт полосу, разделяющую классы. Ширина полосы, как не сложно показать, равна
. Она максимальна, когда норма вектора
минимальна.
Линейно разделимая выборка
Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при ограничениях-неравенствах вида (1) относительно
переменных
Используя аппарат функций Лагранжа, перейдем к решению двойственной задаче. Несложно показать эквивалентность этой задачи и следующей:
Вектор весов будем искать в ввиде . Для определения порога
достаточно взять произвольный опорный вектор
и выразить
из равенства
. На практике для повышения численной устойчивости лучше взять в качестве
медиану:
. Параметры полосы найдены и можно строить разделяюую полосу.
Устойчивость
Вычислительный эксперимент
Вычислительный экстперимент разбит на три частей:
- 1. Нормальное распределение выборки; при помощи нормального распределения случайной величины;
- 2. Реализация алгоритма SVM для линейно разделимой выборки;
- 3. Исследование устойчивости алгоритма SVM;зависимостри параметров разделяющей прямой и среднеквадратичного отклонения параметров разделяющей прямой от среднеквадратичного отклонения выборки.
Нормальное распределение выборки
Нормальным случайным распределением генерятся два класса обьектов по 10 обьектов в каждом классе.
Реализация алгоритма SVM для линейно разделимой выборки
В ходе вычислений определяются параметры раздляющей полосы. Классы линейно разделимы и ширина зазора максимальна, как виздно на рисунке снизу.
Но алгоритм не очень хорош тем, что очень чувствителен к выбросам
На случай линейно не разделимой выборки алгоритм оптимизации не работает.
Исследование устойчивости алгоритма SVM
В этой части вычислительного эксперимента исследуется зависимость параметров разделяющей прямой и среднеквадратичного отклонения параметров разделяющей прямой от среднеквадратичного отклонения выборки. Как можем видеть, с увеличением среднеквадратичного отклонения выборки параметры прямой сильно колеблются, что говорит о не точном вычислении параметров разделяющей прямой.
Смотри также
- Машина опорных векторов
- Линейный классификатор
- Численные методы обучения по прецедентам (практика, В.В. Стрижов)
- SVM для линейно неразделимой выборки (пример)
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |