Машина опорных векторов
Материал из MachineLearning.
Машина опорных векторов — является одной из наиболее популярных методологий обучения по прецедентам, предложенной В. Н. Вапником и известной в англоязычной литературе под названием SVM (Support Vector Machine).
Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin). Случай линейной разделимости. Задача квадратичного программирования. Опорные векторы. Случай отсутствия линейной разделимости. Функции ядра (kernel functions), спрямляющее пространство, теорема Мерсера. Способы построения ядер. Примеры ядер. Сопоставление SVM и нейронной RBF-сети. Обучение SVM методом активных ограничений. SVM-регрессия.
Содержание |
Машина опорных векторов в задачах классификации
Понятие оптимальной разделяющей гиперплоскости
Линейно разделимая выборка
Рассмотрим задачу нахождения наилучшего в некотором смысле разделения множества векторов на два класса с помощью линейной решающей функции. Пусть имеется множество прецедентов , где - обучающая выборка, а - множество меток двух классов и . Требуется по обучающей выборке построить линейную решающую функции, т.е. такую линейную функцию , которая удовлетворяла бы условию
- для всех ,
- для всех .
Без ограничения общности можно считать, что метки классов равны
Тогда поставленную выше задачу можно переформулировать следующим образом. Требуется найти линейную решающую функцию , которая бы удовлетворяла условию
- для всех
Умножая, если нужно функцию на некоторое положительное число нетрудно видеть, что система неравенств (1) равносильна системе
- для всех .
Кроме того, так как линейная функция, то последняя система неравенств примет вид
- ,
Для надежного разделения классов необходимо чтобы расстояние между разделяющими гиперплоскостями было как можно большим, т.е. была как можно меньше. Таким образом, ставится задача нахождения минимума квадратичного функционала (коэффициент 0.5 вводится для удобства дифференцирования) в выпуклом многограннике, задаваемым системой неравенств (2). В выпуклом множестве квадратичный функционал всегда имеет единственный минимум (если это множество не пусто). Из теоремы Куна-Таккера следует, что решение этой оптимизационной задачи равносильно поиску седловой точки лагранжиана
в ортанте по множителям Лагранжа , при условии, что
- .
Последнее условие равносильно тому, что
- или
Из необходимых условий существования седловой точки (полагая ) имеем
Откуда следует, что вектор следует искать в виде
- ,
причем
- .
В силу (3) в сумму (4) с ненулевыми коэффициентами входят только те векторы, для которых . Такие векторы называют опорными, так как это именно те векторы, через которые будут проходить граничные гиперплоскости, разделяющие классы. Для найденного весового вектора смещение можно вычислить как для любого опорного вектора .
Найдем значения множителей Лагранжа, как критических точек лагранжиана. Для этого подставим (4) и (5) в лагранжиан, получим
- .
Таким образом, задача сводится к нахождению критических точек функции
- .
Так как эта функция представляет собой разность линейной и квадратичной функций, причем квадратичная функция отрицательно определена, то требуется найти наибольшее значение функции при условии в области . Существует много алгоритмов (в теории оптимизации) решения этой задачи (например, градиентные методы, метод покоординатного спуска и т.д.).
- Замечания.
- Суммирования в (6) осуществляются не по всем векторам, а только по опорным, которых может быть гораздо меньше, чем обучающих.
- Линейная решающая функция в результате имеет вид , где зависят только и от значений скалярного произведения , причем суммирования осуществляются только по опорным векторам.
- После того, как решающая функция вычислена, вектор следует относить классу , если и классу , если . Вероятность неправильной классификации можно оценить с помощью некоторой непрерывно убывающей функции , удовлетворяющей условиям: , при . Тогда вероятность неправильной классификации вектора будет равна , если (), где : , . То есть , если .
- В такой постановке алгоритм линейный классификации был разработан В. Вапником в 1963 году.
- Пример. Методом опорных векторов разделите классы и , если , , .
- Решение. Положим , , . Тогда функция будет иметь вид
- ,
причем . Тогда . Составим и решим нормальную систему для функции :
Если же , то и , при . Следовательно, , и .
Таким образом, наибольшее значение функции в области при условии достигается в точке . В этом случае,
Таким образом, и . Ширина разделяющей полосы будет равна , а прямые и будут ее границами (см. рис.2).
Линейно неразделимая выборка
В 1992 году в работе Бернарда Бозера (Boser B.), Изабелл Гийон (Guyon I.) и Владимира Вапника был предложен способ адаптации машины опорных векторов для нелинейного разделения классов. В этом случае нужно вложить пространство признаков в пространство большей размерности с помощью отображения . Будем считать, что пространство со скалярным произведением. Тогда, рассматривая алгоритм опорных векторов для образов обучающей выборки, сведем решение задачи к линейно разделимому случаю, т.е. разделяющую функцию будем искать в виде
- , ,
где коэффициенты зависят от и от значения . Таким образом, для нахождения решающей функции нужно знать значения скалярных произведений . Для этого исследуем свойства функции , которая называется ядром. Следующая теорема, известная в теории интегральных операторов и доказанная Джеймсом Мерсером в 1909 году, полностью характеризует ядро.
Теорема 1. Функция является ядром тогда и только тогда, когда она удовлетворяет условиям:
- (симметричность);
- неотрицательно определена, т.е. матрица , является неотрицательно определенной для любых векторов .
Упражнение. Докажите, что следующие функции являются ядрами:
- ;
- ;
- .
Теорема 2. Справедливы следующие свойства ядер:
- сумма ядер – ядро;
- произведение ядер – ядро;
- сумма равномерно сходящегося ряда ядер – ядро;
- композиция ядра и любого отображения (т.е. ) – ядро.
Следствие.
- многочлен с положительными коэффициентами от ядра – ядро;
- экспонента от ядра – ядро;
- функция ядро.
Доказательство. Утверждения 1 и 2 следуют из пунктов 1, 2 и 3 теоремы. Справедливость утверждения 3 вытекает из того, что , а симметричность и положительная определенность функций проверяется непосредственно.
Любые векторов могут быть разделены на любые два класса с помощью мономиального отображения степени не больше . Поэтому, если , такое отображение, то ядро, соответствующее этому отображению можно искать в виде
- .
Таким образом, это ядро гарантирует разделение любых векторов на любые два класса. В этом случае нахождение разделяющих функций осуществляется следующим образом:
1) найдем наибольшее значение функции
при условии в области , получим вектор ;
2) разделяющую функцию ищем в виде
- .
Преимущества и недостатки SVM:
- это наиболее быстрый метод нахождения решающих функций;
- метод сводится к решению задачи квадратичного программирования в выпуклой области, которая всегда имеет единственное решение;
- метод находит разделяющую полосу максимальной ширины, что позволяет в дальнейшем осуществлять более уверенную классификацию;
- метод чувствителен к шумам и стандартизации данных;
- не существует общего подхода к автоматическому выбору ядра (и построению спрямляющего подпространства в целом) в случае линейной неразделимости классов.
Решение. Так как количество векторов обучающей выборки равно трем, то и в качестве ядра возьмем функцию . Тогда
- .
Составим нормальную систему
Можно показать, что в точке будет достигаться наибольшее значение функции при условии в области . Следовательно,
- .
Ядра и спрямляющие пространства
Наиболее распространенные ядра:
- Полиномиальное:
- Полиномиальное:
- Радиальное: , для
Алгоритмы настройки
Машина опорных векторов в задачах регрессии
Программные реализации
Литература
- Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с. (подробнее)
- Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p. (подробнее)