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

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

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

Изначально алгоритм позволял строить линейный классификатор с помощью минимизации ширины полосы раздела классов. Позднее были предложены методы обобщения алгоритма на случай линейно неразделимой выборки(например, введения штрафа за ошибки в функционал качества).

В данной статье приведен пример решения этой задачи для линейно неразделимой выборки с использованием функции ядра (в англоязычной литературе приём носит название kernel trick).

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

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

Задана выборка , где -признаковое описание i-го объекта, - идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что (это позволяет пользоваться функцией sgn в описании классификатора).

Требуется построить классификатор вида , где - скалярное произведение, а - вектор и число, характеризующий данный классификатор. Можно говорить о том, что -веса признаков, - порог принятия решения.

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

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

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

Отнормируем вектор нормали к разделяющей гиперплоскости и порог принятия решения так, чтобы выполнялось условие . Это всегда можно сделать, поскольку, во-первых, умножение на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов.

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

Для линейно неразделимой выборки данная оптимизационная задача не будет иметь решения. Не отказываясь от принципа максимальности зазора, можно видоизменить задачу следующим образом. Разрешим существование неправильно классифицированных объектов, но за каждвый такой объект будем штрафовать:

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