Метод опорных векторов (SVM) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{в разработке}} '''Метод опорных векторов''' (англ. ''support vector machine'', ''SVM'') — семейство алгори…»)
 
Строка 5: Строка 5:
  
 
== Метод опорных векторов в задаче классификации ==
 
== Метод опорных векторов в задаче классификации ==
Рассмотрим задачу классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, 1\}$.
 
  
Пусть задана обучающая выборка пар "объект-ответ" $X^\ell = (x_i, y_i)_{i=1}^\ell$. Будем строить линейный пороговый классификатор:
+
Рассмотрим задачу бинарной классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, +1\}$.
  
$$a(x) = sign\left(\sum\limits_{j=1}^\ell w_j x^j - w_0\right) = sign(\langle w, x \rangle - w_0)$$
+
Пусть задана обучающая выборка пар "объект-ответ": $X^\ell = (\vec{x}_i, y_i)_{i=1}^\ell$. Необходимо построить алгоритм классификации $a(\vec{x}) : X \to Y$.
 +
 
 +
=== Разделяющая гиперплоскость ===
 +
 
 +
В пространстве $\mathbb{R}^n$ уравнение $\langle \vec{w}, \vec{x} \rangle - b = 0$ при заданных $\vec{w}$ и $b$ определяет гиперплоскость — (n-1)-мерное множество векторов $\vec{x} = (x^1, \ldots, x^n)$. Для $\mathbb{R}^1$ это точка, для $\mathbb{R}^2$ — прямая, для $\mathbb{R}^3$ — плоскость и т.д. Эта гиперплоскость делит $\mathbb{R}^n$ на два полупространства: $\langle \vec{w}, \vec{x} \rangle - b > 0$ и $\langle \vec{w}, \vec{x} \rangle - b < 0$.
 +
 
 +
Говорят, что гиперплоскость разделяет два класса $C_1$ и $C_2$, если выполнено
 +
 
 +
$\begin{cases}\langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_1 \\ \langle \vec{w}, \vec{x} \rangle - b < 0, && \forall x \in C_2\end{cases}$
 +
 
 +
либо
  
где $x = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $w = (w_1, \ldots, w_n)$ и $w_0 \in \mathbb{R}$ — параметры алгоритма.
+
$\begin{cases}\langle \vec{w}, \vec{x} \rangle - b < 0, && \forall x \in C_1 \\ \langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_2\end{cases}$
  
=== Оптимальная разделяющая гиперплоскость ===
+
=== Линейно разделимая выборка ===
  
Пусть выборка линейно разделима, то есть существуют такие значения параметров $w$ и $w_0$, для которых функционал количества ошибок равен нулю.
+
Пусть выборка линейно разделима, то есть существует некоторая гиперплоскость, разделяющая классы $-1$ и $+1$.
  
 
{{Определение
 
{{Определение
Строка 24: Строка 33:
 
}}
 
}}
  
 +
[[Файл:SVM_margin.png|300px|thumb|right]]
 +
 +
Возьмём в качестве алгоритма классификации $a(x) : X \to Y$ линейный пороговый классификатор:
 +
 +
$$a(x) = sign\left(\sum\limits_{j=1}^\ell w_j x^j - w_0\right) = sign(\langle w, x \rangle - w_0)$$
 +
 +
где $x = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $w = (w_1, \ldots, w_n)$ и $w_0 \in \mathbb{R}$ — параметры алгоритма.
  
 
{{Теорема
 
{{Теорема
Строка 51: Строка 67:
 
$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$
 
$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$
  
=== Двойственная задача ===
+
 
  
 
=== Линейно неразделимая выборка ===
 
=== Линейно неразделимая выборка ===

Версия 21:28, 21 марта 2019

Эта статья находится в разработке!


Метод опорных векторов (англ. support vector machine, SVM) — семейство алгоритмов обучения с учителем, использующихся для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки наиболее оптимальным способом.

Метод опорных векторов в задаче классификации

Рассмотрим задачу бинарной классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, +1\}$.

Пусть задана обучающая выборка пар "объект-ответ": $X^\ell = (\vec{x}_i, y_i)_{i=1}^\ell$. Необходимо построить алгоритм классификации $a(\vec{x}) : X \to Y$.

Разделяющая гиперплоскость

В пространстве $\mathbb{R}^n$ уравнение $\langle \vec{w}, \vec{x} \rangle - b = 0$ при заданных $\vec{w}$ и $b$ определяет гиперплоскость — (n-1)-мерное множество векторов $\vec{x} = (x^1, \ldots, x^n)$. Для $\mathbb{R}^1$ это точка, для $\mathbb{R}^2$ — прямая, для $\mathbb{R}^3$ — плоскость и т.д. Эта гиперплоскость делит $\mathbb{R}^n$ на два полупространства: $\langle \vec{w}, \vec{x} \rangle - b > 0$ и $\langle \vec{w}, \vec{x} \rangle - b < 0$.

Говорят, что гиперплоскость разделяет два класса $C_1$ и $C_2$, если выполнено

$\begin{cases}\langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_1 \\ \langle \vec{w}, \vec{x} \rangle - b < 0, && \forall x \in C_2\end{cases}$

либо

$\begin{cases}\langle \vec{w}, \vec{x} \rangle - b < 0, && \forall x \in C_1 \\ \langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_2\end{cases}$

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

Пусть выборка линейно разделима, то есть существует некоторая гиперплоскость, разделяющая классы $-1$ и $+1$.


Определение:
Отступ (англ. margin) — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M(x_i, y_i)$, тем ближе объект подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M(x_i, y_i)$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $x_i$.

Для задачи бинарной классификации: $M(x_i, y_i) = y_i(\langle x_i, w \rangle - w_0)$

Для задачи классификации на несколько классов: $M(x_i, y_i) = \langle x_i, w_{y_i}\rangle - \max\limits_{y \in \mathbb{Y}, y \ne y_i} \langle x_i, w_y\rangle$


SVM margin.png

Возьмём в качестве алгоритма классификации $a(x) : X \to Y$ линейный пороговый классификатор:

$$a(x) = sign\left(\sum\limits_{j=1}^\ell w_j x^j - w_0\right) = sign(\langle w, x \rangle - w_0)$$

где $x = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $w = (w_1, \ldots, w_n)$ и $w_0 \in \mathbb{R}$ — параметры алгоритма.

Теорема (Условия Каруша—Куна—Таккера):
Пусть поставлена задача нелинейного программирования с ограничениями:

$$ \begin{cases} f(x) \to \min\limits_{x \in X} \\ g_i(x) \leq 0,\;i=1\ldots m \\ h_j(x) = 0,\;j=1\ldots k \end{cases} $$

Если $\hat{x} \in \arg\min f$ — решение задачи при наложенных ограничениях, то существуют множители $\mu_i, i = 1\ldots m$, $\lambda_j, j = 1\ldots k$, что для функции Лагранжа $L(x; \mu, \lambda)$ выполняются условия:

$$\begin{cases}\frac{\partial L}{\partial x} = 0 \quad L(x; \mu, \lambda) = f(x) + \sum\limits_{i=1}^m \mu_i g_i(x) + \sum\limits_{j=1}^k \lambda_j h_j(x) \\ g_i(x) \leq 0,\;h_j(x) = 0 \quad \text{(исходные ограничения)} \\ \mu_i \geq 0 \quad \text{(двойственные ограничения)} \\ \mu_i g_i(x) = 0 \quad \text{(условие дополняющей нежёсткости)} \end{cases}$$


В качестве аппроксимации функции потерь возьмём $L(x_i, y_i) = max(0, 1 - M_i(w, w_0))$

Запишем функционал для метода оптимизации эмпирического риска с использованием данной функции потерь и регуляризации:

$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$


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

Метод опорных векторов в задаче регрессии

// TODO

См. также

Примечания


Источники информации