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