Повна версія

Головна arrow Інформатика arrow Моделирование сложных сетей

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Метод опорных векторов

Метод опорных векторов (Support Vector Mashine, SVM), предложенный В.Н. Вапником, относится к группе граничных методов классификации. Он определяет принадлежность объектов к классам с помощью границ областей.

Рассматривается бинарная классификация, т.е. только по двум категориям С и С (принимается во внимание то, что этот подход может быть расширен на любое конечное количество категорий). Кроме того предполагается, что каждый объект классификации является вектором в N-мерном пространстве. Каждая координата вектора - это некоторый признак, количественно тем больший, чем больше этот признак выражен в данном объекте.

SVM - Support Vector Mashine

Vapnik V.N. Statistical Learning Theory. - NY: John Wiley, 1998.

Предполагается, что существует учебная коллекция – это множество векторов

и чисел

Число yi равно 1 в случае принадлежности соответствующего вектора х{ категории с, и - 1 - в противном случае.

Как было показано выше, линейный классификатор - это один из простейших способов решения задачи классификации. В этом случае ищется прямая (гиперплоскость в N-мерном пространстве), отделяющая все точки одного класса от точек другого класса. Если удается найти такую прямую, то задача классификации сводится к определению взаимного расположения точки и прямой: если новая точка лежит с одной стороны прямой (гиперплоскости), то она принадлежит классу с, если с другой - классу с .

Формализуем эту классификацию: необходимо найти вектор V? такой, что для некоторого предельного значения b и новой точки х выполняется:

где ш хІ - скалярное произведение векторов ш и хІ:

Уравнение ш хІ = Ь описывает гиперплоскость, которая разделяет классы. То есть, если скалярное произведение вектора ш на хІ не меньше значения Ь, то новая точка принадлежит первому классу, если меньше - ко второму. Известно, что вектор ш перпендикулярен искомой разделяющей прямой, а значение Ь зависит от кратчайшего расстояния между разделяющей прямой и началом координат. Очевидно, если существует одна разделяющая прямая, то она не единственная. Возникает вопрос, какая из прямых разделяет классы лучше всего?

Метод БУМ базируется на таком постулате: наилучшая разделяющая прямая - это та, которая максимально далеко отстоит от ближайших до нее точек обоих классов. То есть задача БУМ состоит в том, чтобы найти такие вектор ш и число Ь, чтобы для некоторого е > 0 (половина ширины разделяющей поверхности) выполнялось:

Умножим после этого обе части неравенства на и, не ограничивая общности, выберем е равным единице. Таким образом, для всех векторов х1 из учебной коллекции будет справедливо:

Условие —1 < ш• х1 — Ь < 1 задает полосу, которая разделяет классы. Границами полосы являются две параллельные гиперплоскости с направляющим вектором ш. Точки, ближайшие к разделяющей гиперплоскости, расположены точно на границах полосы.

Чем шире полоса, тем увереннее можно классифицировать документы, соответственно, в

методе БУМ предполагается, что самая широкая полоса является наилучшей.

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

(так переписывается система уравнений, исходя из того, что

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

Из геометрических соображений известно, что ширина разделяющей полосы равна

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

Это известная задача квадратичной оптимизации при линейных ограничениях.

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

характеризующих величину ошибок на объектах

Это позволяет смягчить ограничения:

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

Задачу поиска оптимальной разделяющей полосы можно в этом случае переформулировать следующим образом: при определенных ограничениях минимизировать сумму:

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

По известной теореме Куна-Такера такая задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа:

Необходимым условием метода Лагранжа является равенство нулю производных лагранжиана по переменным ш и Ь , откуда получаем:

т.е. искомый вектор - это линейная комбинация учебных векторов, для которых Я1Ф 0. Если Л1> 0, то документ обучающей коллекции называется опорным вектором.

Таким образом, уравнение разделяющей плоскости имеет вид:

Приравняв производную лагранжиана по Ь нулю, получим:

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

При этом очень важно, что целевая функция зависит не от конкретных значений xt, а от скалярных произведений между ними.

Следует отметить, что целевая функция является выпуклой, поэтому любой ее локальный минимум является глобальным.

Метод классификации разделяющей полосой имеет два недостатка:

  • - при поиске разделяющей полосы важное значение имеют только пограничные точки;
  • - во многих случаях найти оптимальную разделяющую полосу невозможно.

Для улучшения метода применяется идея расширенного пространства, для чего:

  • 1. Выбирается отображение f(x) векторов x в новое, расширенное пространство.
  • 2. Автоматически применяется новая функция скалярного произведения, которая применяется при решении задачи квадратичного программирования, так называемую функцию ядра (kernel function) как функцию:

Приведем пример функции ядра, отображающего двух мерное пространство в трехмерное:

Тогда ядром функции будет:

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

Функция ядра - главный параметр настраивания машины опорных векторов.

  • 3. Находим разделяющую гиперплоскость в новом пространстве: с помощью функции устанавливается новая матрица коэффициентов для задачи оптимизации. При этом вместо подставляются значение , и решается новая задача оптимизации.
  • 4. Найдя ш и Ь, получаем поверхность, которая

классифицирует, в новом, расширенном пространстве.

Приведем более строгое определение функции ядра.

Функция называется ядром, если она представима в виде

при некотором отображении где Н — пространство со скалярным

произведением.

Ядром может быть не всякая функция, однако класс допустимых ядер достаточно широк. Известна теорема Мерсера о том, что функция К(х, у) является ядром тогда и только тогда, когда она симметрична и неотрицательно определена, т.е. когда

для любой функции

Рассмотрим некоторые свойства функций ядра, которые позволяют строить их в практических задачах:

  • 1. Любое скалярное произведение является ядром.
  • 2. Тождественная единица

является ядром.

  • 3. Произведение ядер является ядром.
  • 4. Для любой функции произведение является ядром.
  • 5. Линейная комбинация ядер с неотрицательными коэффициентами является ядром.
  • 6. Композиция произвольной функции и ядра

является ядром.

7. Если симметричная интегрируемая функция, то

является ядром.

  • 8. Предел локально-равномерно сходящейся последовательности ядер является ядром.
  • 9. Композиция произвольного ядра и произвольной функции представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами

является ядром. В частности, ядрами являются функции

от ядра.

Например, в системе классификации новостного контента с применением известного пакета LibSVM (csie.ntu.edu.tw/~cjlin/libsvm) в качестве функции ядра рекомендуется использовать радиальную базисную функцию:

Где настраиваемый параметр.

Рассмотрим наглядный пример перехода к расширенному пространству, изображенный на рис. 2.4.1. По всей видимости, круглые и квадратные фигуры не разделяются линейной полосой. Если же "изогнуть" пространство, перейдя к третьему измерению, то эти фигуры можно разделить плоскостью, которая отрезает часть поверхности с квадратными точками. Таким образом, выгнув пространство с помощью отображения Ф(х) можно найти разделяющую гиперплоскость.

Метод SVM обладает такими преимуществами:

  • — на тестах с документальными массивами превосходит другие методы;
  • — при выборах разных ядер позволяет эмулировать другие подходы. Например, большой класс нейронных сетей можно представить с помощью БУМ с определенными ядрами;
  • — итоговое правило выбирается не с помощью некоторых эвристик, а путем оптимизации некоторой целевой функции.

Пример перехода к расширенному пространству

Рис. 2.4.1 - Пример перехода к расширенному пространству

К недостаткам можно отнести:

- мало параметров для настройки: после того как фиксируется ядро, единственным параметром, который

варьируется, остается коэффициент ошибки С ;

  • - нет четких критериев выбора ядра;
  • - довольно медленное обучение системы классификации.
 
<<   ЗМІСТ   >>