SVM для линейно разделимой выборки (пример)
Материал из MachineLearning.
(→Исследование на устойчивость алгоритма SVM для линейно разделимой выборки) |
(→Постановка задачи линейной классификации) |
||
Строка 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>\mathbb{R}^n</tex>. | Уравнение <tex><w,x>\ =\ w_0</tex> описывает гиперплоскость, разделяющую классы в пространстве <tex>\mathbb{R}^n</tex>. |
Версия 17:06, 28 апреля 2010
Машина опорных векторов (SVM — support vector machines) — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние междуближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – опорными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
Содержание |
Постановка задачи линейной классификации
Рассматривается задача обучения по прецедентам - , где - пространство объектов, - множество ответов, - целевая зависимость, значения которой известны только на объектах обучающей выборки . Требуется построить алгоритм , аппроксимирующий целевую зависимость на всём пространстве .
Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами:.
Будем строить линейный пороговый классификатор:
- ,
где - признаковое описание объекта ; вектор и скалярный порог являются параметрами алгоритма.
Уравнение описывает гиперплоскость, разделяющую классы в пространстве .
Описание алгоритма
Понятие оптимальной разделяющей гиперплоскости
Предположим, что выборка линейно разделима. Тогда существуют значения параметров , при которых функционал числа ошибок
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единственна. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распорядиться этой свободой выбора.
Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих классов. Первоначально данный принцип классификации возник из эвристических соображений: вполне естественно полагать, что максимизация зазора (margin) между классами должна способствовать более надёжной классификации.
Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: алгоритм не изменится, если и одновременно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов из выполнялись условия ::.
Сделать это возможно, поскольку при оптимальном положении разделяющей гиперплоскости все пограничные объекты находятся от неё на одинаковом расстоянии. Остальные объекты находятся дальше. Таким образом, для всех
Условие задаёт полосу, разделяющую классы. Ширина полосы, как не сложно показать, равна . Она максимальна, когда норма вектора минимальна.
Линейно разделимая выборка
Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при ограничениях-неравенствах вида (1) относительно переменных
Используя аппарат функций Лагранжа, перейдем к решению двойственной задаче. Несложно показать эквивалентность этой задачи и следующей:
Вектор весов будем искать в ввиде . Для определения порога достаточно взять произвольный опорный вектор и выразить из равенства . На практике для повышения численной устойчивости лучше взять в качестве медиану: . Параметры полосы найдены и можно строить разделяюую полосу.
Устойчивость
Вычислительный эксперимент
Смотри также
- Машина опорных векторов
- Линейный классификатор
- Численные методы обучения по прецедентам (практика, В.В. Стрижов)
- SVM для линейно неразделимой выборки (пример)
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |