SVM для линейно разделимой выборки (пример)
Материал из MachineLearning.
(Содержимое страницы заменено на « {{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}} [[Категория:Учебные матер...») |
|||
Строка 1: | Строка 1: | ||
+ | '''[[Машина опорных векторов]] (SVM — support vector machines)''' — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние междуближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – оперными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов. | ||
+ | |||
+ | |||
+ | В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной. | ||
+ | |||
+ | == Постановка задачи линейной классификации == | ||
+ | |||
+ | Рассматривается задача обучения по прецедентам <tex>\left \langle X,\ Y,\ y*,\ X^\ell \right \rangle</tex> - , где <tex>X</tex> - пространство объектов, <tex>Y</tex> - множество ответов, <tex>y*:\ X \rightarrow Y</tex> - целевая зависимость, значения которой известны только на объектах обучающей выборки <tex>X=\(x_i,y_i\)_{i=1}^\ell\ ,\ y_i = y*(x_i)</tex>. Требуется построить алгоритм <tex>a:\ X \rightarrow Y</tex>, аппроксимирующий целевую | ||
+ | зависимость на всём пространстве <tex>X</tex>. | ||
+ | |||
+ | Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами<tex>:\ X\ =\ \mathbb{R}^n,\ Y\ =\ \{-1,+1\}</tex>. | ||
+ | |||
+ | Будем строить линейный пороговый классификатор: | ||
+ | ::<tex>a(x)\ =\ sign(\sum_{j=1}^n w_jx^j\ -\ w_0)\ =\ sign(<w,x>\ -\ w_0)</tex>, | ||
+ | где <tex>x\ =\ (x^1,...,x^n)</tex> - признаковое описание объекта <tex>x</tex>; вектор <tex>w\ =\ (w^1,...,w^n)\ \in\ \mathbb{R}</tex> и скалярный порог <tex>w_0\ in\ \mathbb{R}</tex> являются параметрами алгоритма. | ||
+ | |||
+ | Уравнение <tex><w,x>\ =\ w_0</tex> описывает гиперплоскость, разделяющую классы в про- | ||
+ | странстве <tex>\mathbb{R}^n</tex>. | ||
+ | |||
+ | == Описание алгоритма == | ||
+ | === Понятие оптимальной разделяющей гиперплоскости === | ||
+ | |||
+ | |||
+ | Предположим, что выборка <tex>X=\(x_i,y_i\)_{i=1}^\ell\</tex> линейно разделима. Тогда существуют значения параметров <tex>w,\ w_0</tex>, при которых функционал числа ошибок | ||
+ | ::<tex>Q(w,w_0)\ =\ \sum_{i=1}^\ell [y_i(<w,x_i>\ -\ w_0)\ <\ 0]</tex> | ||
+ | |||
+ | принимает нулевое значение. Но тогда разделяющая гиперплоскость не единствен- | ||
+ | на. Можно выбрать другие её положения, реализующие такое же разбиение выборки | ||
+ | на два класса. Идея метода заключается в том, чтобы разумным образом распоря- | ||
+ | диться этой свободой выбора. | ||
+ | |||
+ | Потребуем, чтобы разделяющая | ||
+ | гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих клас- | ||
+ | сов. Первоначально данный принцип классификации возник из эвристических сооб- | ||
+ | ражений: вполне естественно полагать, что максимизация зазора (margin) между | ||
+ | классами должна способствовать более надёжной классификации. | ||
+ | |||
+ | Заметим, что параметры линейного порогового классификатора опре- | ||
+ | делены с точностью до нормировки: алгоритм <tex>a(x)</tex> не изменится, если <tex>w</tex> и <tex>w_0</tex> одно- | ||
+ | временно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделя- | ||
+ | ющей гиперплоскости) объектов <tex>x_i</tex> из <tex>X^\ell</tex> выполнялись условия | ||
+ | ::<tex><w,x_i>\ -\ w_0\ =\ y_i</tex>. | ||
+ | |||
+ | Сделать это возможно, поскольку при оптимальном положении разделяющей гипер- | ||
+ | плоскости все пограничные объекты находятся от неё на одинаковом расстоянии. | ||
+ | Остальные объекты находятся дальше. Таким образом, для всех <tex>x_i\ \in\ X^\ell</tex> | ||
+ | {{eqno|1}} | ||
+ | <tex><w,x_i> - w_0 | ||
+ | \begin{cases} | ||
+ | \le -1, & \mbox{if }y_i=-1; \\ | ||
+ | \ge 1, & \mbox{if }y_i=+1. | ||
+ | \end{cases} | ||
+ | </tex> | ||
+ | |||
+ | Условие <tex>-1\ <\ \left \Big\langle w,x \right \Big\rangle -w_0<\ 1\ </tex> задаёт полосу, разделяющую классы. Ширина полосы, как не сложно показать, равна <tex>\frac{2}{||w||}</tex>. Она максимальна, когда норма вектора <tex>w</tex> минимальна. | ||
+ | |||
+ | === Линейно разделимая выборка === | ||
+ | Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при <tex>\ell</tex> ограничениях-неравенствах вида {{eqref|1}} относительно <tex>n+1</tex> переменных <tex>w,\ w_0:</tex> | ||
+ | ::<tex>\left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,\ell\\ \right.</tex> | ||
+ | |||
+ | Используя аппарат функций Лагранжа, перейдем к решению двойственной задаче. Несложно показать эквивалентность этой задачи и следующей: | ||
+ | ::<tex>\left{-\mathcal{L}(\lambda)=-\sum\limits_{i=1}^\ell\lambda_i+\frac{1}{2}\sum\limits_{i=1}^\ell\sum\limits_{j=1}^\ell\lambda_i\lambda_jy_iy_j(<x_i,x_j>)\rightarrow \min\limits_\lambda \\ \lambda_i\ge 0\quad, i=1,...,\ell\\ \sum\limits_{i=1}^\ell\lambda_iy_i=0\quad\right. </tex> | ||
+ | |||
+ | Вектор весов будем искать в ввиде <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i</tex>. Для определения порога <tex>w_0</tex> достаточно взять произвольный опорный вектор <tex>x_i</tex> и выразить <tex>w_0</tex> из равенства <tex>w_0=<w,x_i>-y_i</tex>. На практике для повышения численной устойчивости лучше взять в качестве <tex>w_0</tex> медиану: <tex>w_0=med\{<w_i,x_i>-y_i:\ \lambda_i>0,\ i=1,...,\ell\}</tex>. Параметры полосы найдены и можно строить разделяюую полосу. | ||
+ | |||
+ | == Устойчивость алгоритма SVM для линейно разделимой выборки == | ||
+ | |||
+ | Предположим что дана выбрка | ||
+ | ::<tex>\{ \mathbf{x}_0 = \mathbf{0},\mathbf{x}_1 = \sigma \mathbf{e}_1,...,\mathbf{x}_m = \sigma \mathbf{e}_m\} \in \mathbb{R}^m </tex> | ||
+ | ::<tex>\{ y_0 = -1,y_1 = 1,...,y_m = 1\}</tex> | ||
+ | В этом случае задача SVM сводится к задаче | ||
+ | ::<tex>\frac{1}{2}\sum\limits_{i=1}^m\alpha_i^2\sigma_i^2-2\sum\limits_i\alpha_i \rightarrow min\limits_\alpha </tex> | ||
+ | |||
+ | где <tex> \alpha_0=\sum\limits_{i=1}^m\alpha_i </tex>. | ||
+ | |||
+ | |||
+ | |||
+ | == Вычислительный эксперимент == | ||
+ | |||
+ | == Смотри также == | ||
+ | * [[ Машина опорных векторов ]] | ||
+ | * [[ Линейный классификатор ]] | ||
+ | * [[ Численные методы обучения по прецедентам (практика, В.В. Стрижов) ]] | ||
+ | * [[ SVM для линейно неразделимой выборки (пример) ]] | ||
+ | |||
{{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}} | {{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}} |
Версия 07:28, 28 апреля 2010
Машина опорных векторов (SVM — support vector machines) — группа алгоритмов классификации, основанных на обучении с учителем, использующих линейное разделение объектов в пространстве признаков с помощью гиперплоскости. Метод применяется для решения задачи бинарной классификации. Основной проблемой метода является выбор оптимальной гиперплоскости, которая позволяет разделить классы с максимальной точностью. Для этого разделяющая гиперплоскость должна быть выбрана таким образом, чтобы расстояние междуближайшими точками, расположенными по разные стороны от нее, было бы максимальным. Данное расстояние называется зазором (margin), а сами точки – оперными векторами (support vectors). Тогда разделяющая гиперплоскость должна быть выбрана таким образом, чтобы максимизировать зазор, что обеспечит более уверенное разделение классов.
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
Содержание |
Постановка задачи линейной классификации
Рассматривается задача обучения по прецедентам - , где
- пространство объектов,
- множество ответов,
- целевая зависимость, значения которой известны только на объектах обучающей выборки
. Требуется построить алгоритм
, аппроксимирующий целевую
зависимость на всём пространстве
.
Требуется построить задачу классификации на два непересекающихся класса, в которой объекты описываются n-мерными вещественными векторами.
Будем строить линейный пороговый классификатор:
,
где - признаковое описание объекта
; вектор
и скалярный порог
являются параметрами алгоритма.
Уравнение описывает гиперплоскость, разделяющую классы в про-
странстве
.
Описание алгоритма
Понятие оптимальной разделяющей гиперплоскости
Предположим, что выборка линейно разделима. Тогда существуют значения параметров
, при которых функционал числа ошибок
принимает нулевое значение. Но тогда разделяющая гиперплоскость не единствен- на. Можно выбрать другие её положения, реализующие такое же разбиение выборки на два класса. Идея метода заключается в том, чтобы разумным образом распоря- диться этой свободой выбора.
Потребуем, чтобы разделяющая гиперплоскость максимально далеко отстояла от ближайших к ней точек обоих клас- сов. Первоначально данный принцип классификации возник из эвристических сооб- ражений: вполне естественно полагать, что максимизация зазора (margin) между классами должна способствовать более надёжной классификации.
Заметим, что параметры линейного порогового классификатора опре-
делены с точностью до нормировки: алгоритм не изменится, если
и
одно-
временно умножить на одну и ту же положительную константу. Удобно выбрать эту константу таким образом, чтобы для всех пограничных (т. е. ближайших к разделя-
ющей гиперплоскости) объектов
из
выполнялись условия
.
Сделать это возможно, поскольку при оптимальном положении разделяющей гипер-
плоскости все пограничные объекты находятся от неё на одинаковом расстоянии.
Остальные объекты находятся дальше. Таким образом, для всех
Условие задаёт полосу, разделяющую классы. Ширина полосы, как не сложно показать, равна
. Она максимальна, когда норма вектора
минимальна.
Линейно разделимая выборка
Построение оптимальной разделяющей гиперплоскости сводится к минимизации квадратичной формы при ограничениях-неравенствах вида (1) относительно
переменных
Используя аппарат функций Лагранжа, перейдем к решению двойственной задаче. Несложно показать эквивалентность этой задачи и следующей:
Вектор весов будем искать в ввиде . Для определения порога
достаточно взять произвольный опорный вектор
и выразить
из равенства
. На практике для повышения численной устойчивости лучше взять в качестве
медиану:
. Параметры полосы найдены и можно строить разделяюую полосу.
Устойчивость алгоритма SVM для линейно разделимой выборки
Предположим что дана выбрка
В этом случае задача SVM сводится к задаче
где .
Вычислительный эксперимент
Смотри также
- Машина опорных векторов
- Линейный классификатор
- Численные методы обучения по прецедентам (практика, В.В. Стрижов)
- SVM для линейно неразделимой выборки (пример)
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |