SVM для линейно неразделимой выборки (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 51: Строка 51:
Важно отметить также, что решение двойственной задачи квадратичного программирования единственно, т.к. функционал является выпуклым и множество ограничений является выпуклым.
Важно отметить также, что решение двойственной задачи квадратичного программирования единственно, т.к. функционал является выпуклым и множество ограничений является выпуклым.
-
Таким образом, решив задачу {{eqref|1}}, вычислим <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i:\lambda_i>0,\xi_i=0, i=1,...,l\}</tex>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны.
+
Таким образом, решив задачу {{eqref|1}}, вычислим <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i:\lambda_i>0,\xi_i=0, i=1,...,l\}</tex>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.
 +
 
=== Спрямляющее пространство и функции ядра ===
=== Спрямляющее пространство и функции ядра ===
 +
Описание объекта никогда не может считаться полным, если мы работаем с задачами реального мира. Перейдём к новому описанию выборки, основываясь на её данном признаковом представлении, и в этом новом описании будем вычислять скалярное произведение. В новом пространстве (называемом ''спрямляющим пространством''), если оно большей размерности, выборка может оказаться линейно разделимой. Вычисление разделяющей гиперплоскости в спрямляющем пространстве может привести к удовлетворительному результату в исходном представлении. Однако, этого никто гарантировать не может, и более того, выбор ядра для данной практической задачи является нерешенной теоретической проблемой.
 +
 +
Приведенные рассуждения можно записать формальным образом:
 +
<tex>\psi:X\rightarrow H</tex>, где X - исходное пространство, а H - гильбертово пространство. Описание <tex>x_i</tex> заменяется <tex>\psi(x_i)</tex>. Скалярное произведение <tex><x_i,x_j>_X</tex> новым скалярным произведением <tex><\psi(x_i),\psi(x_j)>_H</tex>.
 +
Однако заметим, что параметры задачи {{eqref|1}} (которую мы и хотим решить) зависят только от попарных скалярных произведений описаний объектов выборки. Это означает, что нам не требуется знать новые описания объектов, а только вычислять скалярное произведение между ними.
 +
 +
Функция <tex>K(x,y):X\times X\rightarrow \mathbb{R}</tex> называется ''ядром'', если существует такое преобразование <tex>\psi:X\rightarrow H</tex> и <tex>K(x,y)=<\psi(x),\psi(y)>_H - ядро</tex>. В качестве ядра, конечно, подойдёт не любая функция, на вопрос о требованиях к ней отвечает
 +
====[[Теорема Мерсера]]====
 +
== Вычислительный эксперимент ==
== Вычислительный эксперимент ==

Версия 19:44, 21 апреля 2010

SVM (Support Vector Machine, машина опорных векторов) - алгоритм машинного обучения, предложенный В. Н. Вапником. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, "опорных векторов", по которым и строится опорная гиперплоскость.

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

В данной статье приведен пример решения этой задачи для линейно неразделимой выборки с использованием функции ядра (в англоязычной литературе приём носит название kernel trick).

Содержание

Постановка задачи линейной классификации

Задана выборка X=\{(x_i,y_i)\}_{i=1}^l, где x_i-признаковое описание i-го объекта, y_i - идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что y_i\in\{-1,1\} (это позволяет пользоваться функцией sgn в описании классификатора).

Требуется построить классификатор вида a(x)=sign(<w,x>-w_0), где <w,x> - скалярное произведение, а w,w_0 - вектор и число, характеризующий данный классификатор. Можно говорить о том, что w_i-веса признаков, w_0 - порог принятия решения.

Если для данной выборки существуют w,w_0 такие, что a(x) не ошибается на обучающей выборке, то она называется линейно разделимой. В противном случае, выборка называется линейно неразделимой.

Описание алгоритма

Линейно разделимая выборка

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

Отнормируем вектор нормали к разделяющей гиперплоскости w и порог принятия решения w_0 так, чтобы выполнялось условие \min\limits_{i=1,l} y_i(<w,x_i>-w_0)=1. Это всегда можно сделать, поскольку, во-первых, умножение w,w_0 на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов.

Нетрудно показать, что при такой нормировке ширина разделяющей полосы может быть представлена в виде: \frac{2}{||w||}. Максимизация этой величины равносильна минимизации нормы вектора нормали. Таким образом, параметры линейного классификатора определяются из задачи квадратичного программирования: \left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,l\\ \right.

Линейно неразделимая выборка

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

\left{\frac{1}{2}<w,w>+C\sum\limits_{i=1}^l\xi_i\rightarrow min\\y_i(<w,x_i>-w_0)\ge1-\xi_i,\qquad i=1,...,l\\ \xi_i\ge0,\qquad i=1,...,l\right.

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

(1)
\left{-\sum\limits_{i=1}^l\lambda_i+\frac{1}{2}\sum\limits_{i=1}^l\sum\limits_{j=1}^l\lambda_i\lambda_jy_iy_j<x_i,x_j>\rightarrow \min\limits_\lambda \\ 0\le\lambda_i\le C\\ \sum\limits_{i=1}^l\lambda_iy_i=0\right.

При это выполняются соотношения w = \sum\limits_{i=1}^l\lambda_ix_iy_i,\qquad\eta_i+\lambda_i=C,\qquad \lambda_i(1-\xi_i)=0, \qquad \xi_i\eta_i=0.

Решив эту оптимизационную задачу, то есть, найдя вектор \lambda, можно классифицировать объекты следующим образом:

  • \lambda_i=0, \eta_i=C, \xi_i=0.
Эти параметры означают, что объект x_i классифицируется правильно(т.к. \xi_i=0). Но, что важнее - вектор опорной гиперплоскости не зависит от данного объекта. Данный объект можно исключить из выборки и SVM построит тот же самый алгоритм классификации - разделяющую гиперплоскость. Такие объекты называются периферийными.
  • 0<\lambda_i<C, 0<\eta_i<C, \xi_i=0.
Объект x_i классифицируется правильно и лежит точно на границе разделяющей полосы. Данные объекты называются опорными граничными.
  • \lambda_i=C, \eta_i=0, \xi_i>0.
Данный объект может находить как в граничной полосе со стороны своего класса, так и классифицироваться неправильно. Данные объекты называются опорными нарушителями.

Объекты последних двух типов и называются опорными векторами. Разделяющая гиперплоскость зависит только от них, что является одним из главных преимуществ SVM. Можно ожидать, что этих векторов будет не очень много, и оставит только их в памяти, алгоритм классификации ничуть не изменится.

Заметим, что на практике оптимизационная задача решается не абсолютно точно. В следствии чего периферийные объекты (представляющие собой вырожденный случай распределения параметров) почти не встречаются. Для каждого объекта вычисляется \lambda_i не равное нулю, но для большинства объектов их значение мало "в среднем". Поэтому не составляет труда отсеять периферийные объекты.

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

Таким образом, решив задачу (1), вычислим w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i:\lambda_i>0,\xi_i=0, i=1,...,l\}. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.

Спрямляющее пространство и функции ядра

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

Приведенные рассуждения можно записать формальным образом: \psi:X\rightarrow H, где X - исходное пространство, а H - гильбертово пространство. Описание x_i заменяется \psi(x_i). Скалярное произведение <x_i,x_j>_X новым скалярным произведением <\psi(x_i),\psi(x_j)>_H. Однако заметим, что параметры задачи (1) (которую мы и хотим решить) зависят только от попарных скалярных произведений описаний объектов выборки. Это означает, что нам не требуется знать новые описания объектов, а только вычислять скалярное произведение между ними.

Функция K(x,y):X\times X\rightarrow \mathbb{R} называется ядром, если существует такое преобразование \psi:X\rightarrow H и K(x,y)=<\psi(x),\psi(y)>_H - ядро. В качестве ядра, конечно, подойдёт не любая функция, на вопрос о требованиях к ней отвечает

Теорема Мерсера

Вычислительный эксперимент

Источник — «http://machinelearning.ru/wiki/index.php?title=SVM_%D0%B4%D0%BB%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D0%B9_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BA%D0%B8_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»
Личные инструменты