Метод опорных векторов (SVM)

Материал из Викиконспекты
Версия от 19:41, 21 марта 2019; Egormkn (обсуждение | вклад) (Новая страница: «{{в разработке}} '''Метод опорных векторов''' (англ. ''support vector machine'', ''SVM'') — семейство алгори…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!


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

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

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

Пусть задана обучающая выборка пар "объект-ответ" $X^\ell = (x_i, y_i)_{i=1}^\ell$. Будем строить линейный пороговый классификатор:

$$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}$ — параметры алгоритма.

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

Пусть выборка линейно разделима, то есть существуют такие значения параметров $w$ и $w_0$, для которых функционал количества ошибок равен нулю.


Определение:
Отступ (англ. 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$


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

$$ \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

См. также

Примечания


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