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

Метод опорных векторов (Support Vector Mashine, SVM), предложенный В.Н. Вапником [Vapnik V.N. Statistical Learning Theory. – New York: Wiley; 1998. – 732 p. Vapnik V.N. The nature of statistical learning theory. – New York: Springer-Verlag, 2000. – 332 p. ], относится к группе граничных методов классификации. Он определяет принадлежность объектов к классам с помощью границ областей.

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

Формализуем эту классификацию в рамках модели (1.1).

D — множество документов,

С={1, -1} — множество классов

F - множество представлений документов

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

- отношение на декартовом квадрате СxХ

Метод SVM на множестве Х строит линейный пороговый классификатор f: F→C:

,

где вектор x=(x¹,...,xⁿ) — признаковое описание объекта, вектор w=(w₁,...,w_n) и скалярный порог w₀ — параметры алгоритма.

Уравнение описывает гиперплоскость, разделяющую классы. Заметим, что параметры линейного порогового классификатора определены с точностью до нормировки: значение f(x) не изменится, если w и w₀ одновременно умножить на одну и ту же положительную константу. Т.е. если классы линейно разделимы, разделяющая гиперплоскость не единственна. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделяющей гиперплоскости) объектов х_i из X выполнялись условия :

(3.1)

Метод SVM базируется на таком постулате: наилучшая разделяющая прямая – это та, которая максимально далеко отстоит от ближайших до нее точек обоих классов. То есть задача метода SVM состоит в том, чтобы найти такие вектор w и число w₀, чтобы ширина разделяющей полосы была максимальна. Поскольку чем шире полоса, тем увереннее можно классифицировать документы, соответственно, в методе SVM считается, что самая широкая полоса является наилучшей. Границами полосы являются две параллельные гиперплоскости с направляющим вектором w. Точки, ближайшие к разделяющей гиперплоскости, расположены точно на границах полосы, при этом сама разделяющая гиперплоскость проходит ровно по середине полосы.

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

(3.2)

Эта задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа

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

(3.3)

(3.4)

Из (3.3) следует, что искомый вектор весов w является линейной комбинацией векторов обучающей выборки, причём только тех, для которых λ_i = 0. На этих векторах x_i ограничения-неравенства обращаются в равенства, следовательно, эти векторы находятся на границе разделяющей полосы. Все остальные векторы отстоят дальше от границы, для них λ_i = 0, и они не участвуют в сумме (3.3). Алгоритм Значение классификатора f(x) не изменилось бы, если бы этих векторов вообще не было в обучающей выборке.

Опорным вектором (support vector) называется объект обучающей выборки x_i , находящийся на границе разделяющей полосы, если λ_i > 0

Подставляя (3.3) и (3.4) обратно в Лагранжиан, получим эквивалентную задачу квадратичного программирования, содержащую только вектор λ.

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

Допустим, мы решили эту задачу. Тогда вектор w вычисляется по формуле (3.3). Для определения порога w₀ достаточно взять произвольный опорный вектор x_i и выразить w₀ из равенства (3.1). На практике для повышения численной устойчивости рекомендуется брать в качестве w₀ среднее по всем опорным векторам, а ещё лучше медиану:

w₀=med{<w,x_i>-y_i: λ_i > 0, i=1,...,l}

В итоге алгоритм классификации может быть записан в следующем виде:

(3.5)

Чтобы обобщить SVM на случай линейной неразделимости за отправную точку берется задача (3.2) со следующими модификациями:

• допускается появление ошибок на объектах обучающей выборки, но при этом вводится набор дополнительных переменных ξ_i, характеризующих величину ошибки на объектах x_i;

• в (3.2) смягчаются ограничения-неравенства (3.1);

• в минимизируемый функционал вводится штраф за суммарную ошибку.

Вектор w и скалярный порог w₀ могут быть получены при минимизации функционала:

Положительная константа C является управляющим параметром метода и позволяет находить компромисс между максимизацией разделяющей полосы и минимизацией суммарной ошибки.

Как и в случае линейной разделимости классов, задача минимизации функционала сводится к поиску седловой точки функции Лагранжа и параметры разделяющей поверхности w и w₀ также выражаются только через двойственные переменные λ_i. Таким образом, задача снова сводится к квадратичному программированию относительно двойственных переменных λ_i. Единственное отличие от линейно разделимого случая состоит в появлении ограничения сверху λ_i≥C:

Поскольку гарантировать линейную разделимость выборки в общем случае не представляется возможным, то на практике для построения SVM решают именно эту задачу. Этот вариант алгоритма называют SVM с мягким зазором (soft-margin SVM), тогда как в линейно разделимом случае говорят об SVM с жёстким зазором (hard-margin SVM).

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

Для алгоритма классификации сохраняется формула (3.5), с той лишь разницей, что теперь ненулевыми λ_i обладают не только опорные объекты, но и объекты-нарушители (объекты, лежащие внутри разделяющей полосы, но классифицирующиеся правильно, либо попадающие на границу классов, либо вообще относящиеся к чужому классу. В определённом смысле это недостаток SVM, поскольку нарушителями часто оказываются шумовые выбросы, и построенное на них решающее правило, по сути дела, опирается на шум. Константу C обычно выбирают по критерию скользящего контроля. Это трудоёмкий способ, так как задачу приходится решать заново при каждом значении C. Если есть основания полагать, что выборка почти линейно разделима, и лишь объекты-выбросы классифицируются неверно, то можно применить фильтрацию выбросов. Сначала задача решается при некотором C, и из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки ξ_i. После этого задача решается заново по усечённой выборке. Возможно, придётся проделать несколько таких итераций, пока оставшиеся объекты не окажутся линейно разделимыми.

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

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

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

Для улучшения метода применяется идея расширенного пространства, которая заключается в переходе от исходного пространства признаковых описаний объектов X к новому пространству H с помощью некоторого преобразования ψ: X → H. Если пространство H имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой. Пространство H называют спрямляющим. Если предположить, что признаковыми описаниями объектов являются векторы ψ(x_i ), а не векторы x_i , то построение 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₀, получаем разделяющую гиперплоскость в новом, расширенном, пространстве.

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

Используя функцию ядра, нетрудно показать связь SVM с двухслойными нейронными сетями. Рассмотрим структуру алгоритма классификации f(x) после замены решающем правиле скалярного произведения <x_i, x> ядром K(x_i, x). При этом перенумеруем объекты так, чтобы первые h объектов оказались опорными. Поскольку λ_i = 0 для всех неопорных объектов, i = h+1,...,l:

Следовательно, классификатор f(х) можно рассматривать как двухслойную нейронную сеть, имеющую n входных нейронов и h нейронов в скрытом слое и обладающую следующими особенностями:

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

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

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

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

- на тестах с документальными массивами превосходит другие методы;

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

- итоговое правило выбирается не с помощью экспертных эвристик, а путем оптимизации некоторой целевой функции.

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

- иногда слишком малое количество параметров для настройки: после того как фиксируется ядро, единственным изменяемым параметром остается коэффициент ошибки ;

- нет четких критериев выбора ядра;

- медленное обучение системы классификации.

Как видно из проведенного обзора, на сегодняшний день существует очень большое количество классификаторов. Большинство из рассмотренных методов имеют существенный недостаток – обучение с учителем (supervised learning). В данном случае классификация определяет документы в одну или более предопределённых категорий. В классификации текста новый текстовый документ назначается в один из уже существующих наборов документов класса. Определить новые заранее не известные структуры коллекции документов при таком подходе не представляется возможным.

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