SVM для линейно разделимой выборки (пример)
Материал из MachineLearning.
SVM (Support Vector Machine, машина опорных векторов) - алгоритм машинного обучения, предложенный В. Н. Вапником. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, "опорных векторов", по которым и строится опорная гиперплоскость.
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
Содержание |
Постановка задачи линейной классификации
Задана выборка , где -признаковое описание i-го объекта, - идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что (это позволяет пользоваться функцией sgn в описании классификатора).
Требуется построить классификатор вида , где - скалярное произведение, а - вектор и число, характеризующий данный классификатор. Можно говорить о том, что -веса признаков, - порог принятия решения.
Если для данной выборки существуют такие, что не ошибается на обучающей выборке, то она называется линейно разделимой. В противном случае, выборка называется линейно неразделимой.
Описание алгоритма
Линейно разделимая выборка
Если выборка линейно разделима, то существует бесконечно много линейных классификаторов, не ошибающихся на ней. В алгоритме SVM максимизируется расстояние от опорной гиперплоскости до обоих классов.
Отнормируем вектор нормали к разделяющей гиперплоскости и порог принятия решения так, чтобы выполнялось условие . Это всегда можно сделать, поскольку, во-первых, умножение на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов.
Нетрудно показать, что при такой нормировке ширина разделяющей полосы может быть представлена в виде: . Максимизация этой величины равносильна минимизации нормы вектора нормали. Таким образом, параметры линейного классификатора определяются из задачи квадратичного программирования:
Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей:
Таким образом, решив оптимизационную задачу (1), то есть, найдя вектор , вычислим . Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.
Смотри также
- Машина опорных векторов
- Линейный классификатор
- Численные методы обучения по прецедентам (практика, В.В. Стрижов)
- SVM для линейно неразделимой выборки (пример)
Литература
- Воронцов К.В. Лекции по линейным алгоритмам классификации
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |