Применение метода опорных векторов

Пример использования линейного классификатора

Пример обобщенного метода опорных векторов в случае существования множества классов

Дополнение

Список литературы

Пример использования линейного классификатора

Для простоты, разберем двумерный случай с линейным разделением точек. Имеются данные о типах ириса.

По длине стебля и ширине цветка необходимо определить тип ириса. 

Структура данных представлена на рисунке.

Переменные

SLENGTH	Длина стебля
PWIDTH	Ширина цветка
FLOWER	Тип ириса

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

В результате анализа было найдено 18 векторов (по 9 для каждого класса).

Максимальная маржа составила 1,722

Пример обобщенного метода опорных векторов в случае существования множества классов

Данные о трех типах цветков представлены в виде таблице в файле Irisdat.sta из папки примеров STATISTICA.

В качестве непрерывных переменных выступают:

SEPALLEN	Длина чашелистика
SEPALWID	Ширина чашелистика
PETALWID	Ширина лепестка
PETALLEN	Длина лепестка

В качестве категориальной переменной Iristype (тип ириса). 

Выберем переменные для анализа как показано на рисунке ниже

В качестве зависимой переменной выступает категориальная переменная – тип ириса. В качестве независимых – все остальные. 

Включим поиск по сетке констант как в пункте Регрессия. 

Результаты

Количество опорных векторов 40 (1 на границе). 

Cross-validation accuracy (Точность кросс-проверки) - 97,3%. 

Точность классификации на всей выборке 98,67%. 

Support vectors per class (количество векторов в каждом классе) 

Class. accuracy (точность)

Confidence (уровень доверия) 

Построим диаграммы рассеяния контрольной выборке, по оси X – независимая переменная, по оси Y –SETOSA, VERSICOL, VIRGIN.

На контрольной выборке метод опорных векторов проявил себя великолепно – 100% точность!

Дополнение

Начальная форма 

Задачу оптимизации, представленную в предыдущем разделе, трудно решить, так как норма w включает в себя квадратный корень. К счастью, это можно упростить, заменив на  (коэффициент от 1/2 используются для математического удобства) без изменения решение (не менее оригинальные и модифицированные уравнения имеют одинаковый w и b) . Это квадратичная задача оптимизации программирования. Более четко:

Путем введения множителей Лагранжа, предыдущая задача с ограничениями может быть выражена так:

Находится седловая точка. При этом все точки, которые могут быть отделены  не имеют значения, поскольку мы должны установить соответствующее нулю.

Проблема может быть решена, используя техники квадратичного программирования. «Стационарность» по Куна-Такеру означает, что решение может быть выражено как линейная комбинация обучающих векторов:

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

Последнее позволяет определить смещение b. На практике, более надежно усреднение  по всем опорным векторам:

Вторая форма линейного классификатора

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

Используя факт  и подставляя , можно показать, что вторая форма метода опорных векторов позволяет решить проблему оптимизации: 

Максимизировав по :

Ограничение от минимизации для b

Ядро определено как 

W может быть вычислено благодаря условиям:

Объективные и необъективные гиперплоскости 

Для простоты, иногда требуется, чтобы гиперплоскость проходит через начало системы координат. Такие гиперплоскости называются объективными. 

Гиперплоскости, не обязательно проходящими через начало координат, называют предвзятыми. 

Объективная гиперплоскость может быть обеспечено путем подстановки b=0 в ограничение задачи оптимизации. 

Соответствующая вторая форма совпадает с формой, приведенной выше, без ограничения равенства:

Вторая форма аналогична примеру выше. 

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

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

Список литературы

1. C. Apte, F. Damerau, and S. Weiss. Towards language independent automated learning of text categorization models.In Proceedings of the 17th Annual ACM/SIGIR conference,1994. 
2. C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:273297, 1995.
3. Thorsten Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. In European Conference on Machine Learning (ECML), 1998. 
4. Osuna, R. Freund, and F. Girosi. Support vector machines: Training and applications. In A.I. Memo. MIT A.I. Lab, 1996 
5. J. Platt. Sequetial minimal optimization: A fast algorithm for training support vector machines. In Technical Report MST-TR-98-14. Microsoft Research, 1998 
6. V. Vapnic. The Nature of Statistical Learning Theory. Springer, New York, 1995. 
7. Y. Yang. Expert network: Effective and efficient learning from human decisions in text categorization and retrieval. In17th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'94), pages 13{22, 1994.

В начало