Евгений Борисов
Среда, 26 Июня 2013 г.
В этой статье мы поговорим о модели, которая носит название машина опорных векторов (support vector machines, SVM) [ 1 ] , этот метод также называют - классификатор с максимальным зазором. Рассмотрим сам классификатор и метод его обучения – sequential minimal optimization (SMO).
SVM-классификатор реализует бинарную классификацию, т.е. разделяет множество входных векторов на две части: положительный-отрицательный, свои-чужие, да-нет и т.п.
Прежде чем классификатор начнёт работать его необходимо обучить на множестве специально подобранных учебных примеров, которое состоит из двух частей - положительные (условно) примеры и отрицательные примеры. В данном случае применяется подход "обучение с учителем т.е. каждый учебный пример представляет собой пару <учебный вход, правильный ответ> . Применяется алгоритм обучения (о нём мы поговорим ниже), который изменяет параметры SVM, подстраиваясь под учебный набор.
Неформально работу алгоритма обучения SVM можно писать следующим образом. Алгоритм обучения находит среди элементов учебного множества точки, лежащие на границе двух подмножеств (положительного и отрицательного) и строит между этими точками разделяющую поверхность. В терминах SVM такие точки называются опорными векторами.
|
SVM, помимо всего прочего, обладает интересной особенностью, эта система модульная, она содержит в себе т.н. функцию ядра, заменяя которую можно менять характеристики классификатора.
Классификатор описывается следующими соотношениями
где w 0 – порог (свободный член); λ i – коэффициент; x i ,y i – пара из учебного набора, (векторы x i , для которых λ i > 0 называются опорными); K ( x i ,x ) – функция ядра
Машина опорных векторов отображает входной вектор в пространство более высокой размерности и находит разделяющую гиперплоскость с максимальным зазором между точками разных классов. Отображение это осуществляется с помощью функции ядра.
Изначально SVM это линейный классификатор, т.е. он может решать только линейно разделимые задачи. Однако, применяя нелинейное ядро, можно отобразить исходные данные в пространство большей размерности, где уже может существовать оптимальная разделяющая гиперплоскость.
|
|
Функция ядра должна удовлетворять специальным условиям [ 2 ] , примеры таких функций приведены ниже.
Обучение SVM сводится к нахождению коэффициентов λ (множителей Лангранжа) и w 0 . Найти их можно решив следующую задачу квадратичной оптимизации.
Для решения этой задачи можно применять разные методы, ниже мы рассмотрим алгоритм sequential minimal optimization (SMO) [ 3 ] .
Есть три составляющих SMO:
выполнить процедуру обработки учебного примера (разд. 3.3 ),
сдвинуть очередь
выполнить процедуру обработки учебного примера (разд. 3.3 ),
сдвинуть очередь
если
∨
то
переход на следующий пункт
иначе
переход на п.
5
если
параметры изменились
то
переход на п.
13
иначе
переход на следующий пункт
выполнить процедуру оптимизации для λ j ,λ i (разд. 3.5 )
сдвинуть очередь
если
параметры изменились
то
переход на п.
13
иначе
переход на следующий пункт
выполнить процедуру оптимизации для λ j ,λ i (разд. 3.5 )
сдвинуть очередь
если
y
i
=
y
j
то
иначе
если
η <
0
то
иначе
сдвинуть очередь
Пример работы SVM с линейно разделимым набором данных, используется линейное ядро.
|
|
|
Пример работы SVM с линейно неразделимым набором данных, в качестве функции ядра используется Gaussian kernel.
|
|
|
Реализация в системе Octave [ здесь ].
[1] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979
[2] Воронцов К.В. Метод опорных векторов
[3] John C. Platt Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines // Microsoft Research, Technical Report MSR-TR-98-14, April 21, 1998