Метод опорных векторов (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

См. также

• Обзор библиотек для машинного обучения на Python
• Общие понятия

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

• machinelearning.ru — Машина опорных векторов
• Лекция "Линейные методы классификации: метод опорных векторов" — К.В. Воронцов, курс "Машинное обучение" 2014
• Wikipedia — Метод опорных векторов
• Alexey Nefedov — Support Vector Machines: A Simple Tutorial
• John Platt — Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines