Технологии искусственного интеллекта. Метод опорных векторов

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

Смысл критерия качества, используемого в методе опорных векторов, заключается в следующем. Пусть есть некоторая разделяющая гиперплоскость. Ее можно перемещать параллельным переносом (меняя параметр w_N+1) в некоторых пределах так, что она все еще будет разделять классы. Совокупность таких параллельных гиперплоскостей образует полосу определенной ширины.

При изложении метода будем рассматривать только бинарную классификацию, т.е. классификацию только по двум категориям, т.е. С={С₁, С₂}, принимая во внимание то, что этот подход может быть расширен на любое конечное количество категорий. Предположим, что каждый объект классификации является вектором в n-мерном пространстве.

Пусть - множество описаний, построенное по обучающей выборке, каждый элемент множества - вектор .

Уравнение , w= (w ₁, w ₂, …, w_n) описывает гиперплоскость, разделяющую классы. Очевидно, если классы линейно разделимы, разделяющая гиперплоскость не единственна, умножив w и w ₀ одновременно на одну и ту же положительную константу, получим тоже разделяющую гиперплоскость. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов х_i из X выполнялись условия:

Нетрудно доказать, что ширина разделяющей полосы обратно пропорциональна норме вектора w. В этом случае построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при l ограничениях-неравенствах вида относительно n +1 переменных w, w ₀:

Эта задача решается методом неопределенных множителей Лагранжа, для чего составляется лагранжиан:

,

который минимизируется при следующих ограничениях: и для каких-либо опорных векторов. Здесь λ _i – неопределенные множители Лагранжа.

Условный экстремум лагранжиана ищется путем его дифференцирования по w_i и λ _i и приравнивания всех производных нулю. В итоге приведем результат:

, (1)

а w ₀ просто получается из соотношения y_s < w, x_s > =1, записанного для произвольного опорного вектора. Следует также заметить, что множители λ _i отличны от нуля только для опорных векторов. Сами же величины λ _i находится путем минимизации квадратичной функции, получаемой путем подстановки (1) в лагранжиан, при указанных выше ограничениях на значения λ _i.

Не любые два набора точек в признаковом пространстве разделяются гиперплоскостью, а значит, могут быть корректно классифицированы с помощью линейной решающей функции. В этом случае применяется идея расширенного пространства, которая заключается в переходе от исходного пространства признаковых описаний объектов X к новому пространству H с помощью некоторого преобразования ψ: X → H. Если пространство H имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой. Пространство H называют спрямляющим. Если предположить, что признаковыми описаниями объектов являются векторы ψ (xi), а не векторы xi, то построение SVM проводится точно так же, как и ранее. Единственное отличие состоит в том, что скалярное произведение < x, x ′ > в пространстве X всюду заменяется скалярным произведением < ψ (x), ψ (x ′)> в пространстве H. Это возможно с помощью ядра.

Функция K: X × X → R называется ядром (kernel function), если она представима в виде K (x, x ′) = < ψ (x), ψ (x ′)> при некотором отображении ψ: X → H, где H — пространство со скалярным произведением.

В случае линейной неразделимости:

1.Выбирается отображение векторов в новое, расширенное пространство ψ: X → H.

2. Автоматически применяется новая функция скалярного произведения — ядро K (x, z) = < ψ (x), ψ (z)>. На практике обычно выбирают не отображение, а сразу функцию ядра - главный параметр настраивания машины опорных векторов.

3. Определяется разделяющая гиперплоскость в новом пространстве: с помощью функции K (x, z) устанавливается новая матрица коэффициентов для задачи оптимизации. При этом вместо скалярного произведения < x, z > берется значение K (x, z), и решается новая задача оптимизации.

4. Найдя w и w ₀, получаем разделяющую гиперплоскость в новом, расширенном, пространстве.

Ядром может быть не всякая функция, однако класс допустимых ядер достаточно широк. Используя функцию ядра, нетрудно показать связь SVM с двухслойными нейронными сетями: этот можно рассматривать как двухслойную нейронную сеть, имеющую n входных нейронов и l нейронов в скрытом слое и обладающую следующими особенностями:

· число нейронов скрытого слоя определяется автоматически;

· векторы весов у нейронов скрытого слоя совпадают с признаковыми описаниями опорных объектов;

· λ _i — это вес, выражающий степень важности ядра K (x_i, x).