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

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

Перейти к: навигация, поиск

SVM (Support Vector Machine, машина опорных векторов) - алгоритм машинного обучения, предложенный В. Н. Вапником. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, "опорных векторов", по которым и строится опорная гиперплоскость.

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

Содержание

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

Основная статья: Линейный классификатор

Задана выборка X=\{(x_i,y_i)\}_{i=1}^l, где x_i-признаковое описание i-го объекта, y_i - идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что y_i\in\{-1,1\} (это позволяет пользоваться функцией sgn в описании классификатора).

Требуется построить классификатор вида a(x)=sign(<w,x>-w_0), где <w,x> - скалярное произведение, а w,w_0 - вектор и число, характеризующий данный классификатор. Можно говорить о том, что w_i-веса признаков, w_0 - порог принятия решения.

Если для данной выборки существуют w,w_0 такие, что a(x) не ошибается на обучающей выборке, то она называется линейно разделимой. В противном случае, выборка называется линейно неразделимой.

Описание алгоритма

Линейно разделимая выборка

Если выборка линейно разделима, то существует бесконечно много линейных классификаторов, не ошибающихся на ней. В алгоритме SVM максимизируется расстояние от опорной гиперплоскости до обоих классов.

Отнормируем вектор нормали к разделяющей гиперплоскости w и порог принятия решения w_0 так, чтобы выполнялось условие \min\limits_{i=1,l} y_i(<w,x_i>-w_0)=1. Это всегда можно сделать, поскольку, во-первых, умножение w,w_0 на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов.

Нетрудно показать, что при такой нормировке ширина разделяющей полосы может быть представлена в виде: \frac{2}{||w||}. Максимизация этой величины равносильна минимизации нормы вектора нормали. Таким образом, параметры линейного классификатора определяются из задачи квадратичного программирования:

\left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,l\\ \right.

Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей:

(1)
\left{-\sum\limits_{i=1}^l\lambda_i+\frac{1}{2}\sum\limits_{i=1}^l\sum\limits_{j=1}^l\lambda_i\lambda_jy_iy_j<x_i,x_j>\rightarrow \min\limits_\lambda \\ \lambda_i\ge 0\quad i=1,...,l\\ \sum\limits_{i=1}^l\lambda_iy_i=0\quad\right.

Таким образом, решив оптимизационную задачу (1), то есть, найдя вектор \lambda, вычислим w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i,\lambda_i>0, i=1,...,l\}. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.

Смотри также

Литература

  • Воронцов К.В. Лекции по линейным алгоритмам классификации


Данная статья является непроверенным учебным заданием.
Студент: Участник:Алексей Морозов
Преподаватель: Участник:В.В.Стрижов
Срок: 28 мая 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://poligon.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»