Ядерное обобщение метода опорных векторов

Для метода опорных векторов, как и для гребневой регрессии, существует ядерное обобщение, которое работает по следующему правилу:

1. Найти оптимальные двойственные переменные $\alpha_1^*,...\alpha_N^*$ из решения двойственной оптимизационной задачи

$$\begin{cases} -\frac{1}{2}\sum\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}k(\mathbf{x}_{i},\mathbf{x}_{j})+\sum_{n=1}^{N}\alpha_{n} \to \min_{\boldsymbol{\alpha}} \\ \sum_{n=1}^{N}\alpha_{i}y_{i}=0, \\ 0 \le \alpha_i \le C, \quad i=1,2,...N \end{cases}$$

2. Вычислить $w_0^*$ по объектам $\mathbf{x}_{j}$, для которых $y_{i}(\sum_{i\in SV}\alpha_{i}^{*}y_{i}k(\mathbf{x}_{i},\mathbf{x}_{j})+w_{0}^*)=1$

3. Для новых объектов строить прогноз по правилу

$$\widehat{y}\left(\mathbf{x}\right)=\text{sign}\left(\sum_{i\in SV}\alpha_{i}^{*}y_{i}k(\mathbf{x}_{i},\mathbf{x})+w_{0}\right)$$

где $SV=\{i:\alpha_i^*>0 \}$.

Доказательство для любознательных

Ранее мы получили, что для бинарной классификации $y\in\{+1,-1\}$ прогноз в методе опорных векторов строится по правилу

$$\widehat{y}\left(\mathbf{x}\right)=\text{sign}\left(\mathbf{w}^{T}\mathbf{x}+w_{0}\right),$$

где веса $\mathbf{w},w_0$ находятся из решения оптимизационной задачи:

$$\begin{cases} \frac{1}{2}\mathbf{w}^{T}\mathbf{w}+C\sum_{n=1}^{N}\xi_{n}\to\min_{\mathbf{w},w_{0},\bm{\xi}}\\ y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})\ge1-\xi_{i} & i=1,2,...N\\ \xi_{i}\ge 0 & i=1,2,...N \end{cases}$$

Для обобщения метода через ядра будем решать эту задачу, используя необходимые условия оптимальности Каруша-Куна-Таккера [1], которые также становятся достаточными, поскольку минимизируется выпуклая функция при выпуклых ограничениях [2].

Для этого запишем лагранжиан с двойственными переменными $\alpha_i,\beta_i$ для $i=1,2,...N$:

$$L=\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+C\sum_{i=1}^{N}\xi_{i}-\sum_{i=1}^{N}\alpha_{i}[y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})-1+\xi_{i}]-\sum_{i=1}^{N}\beta_{i}\xi_{i}$$

Согласно условиям Каруша-Куна-Таккера, в оптимуме выполняются следующие условия:

1. Стационарность:

   $$\frac{\partial L}{\partial\mathbf{w}}=\mathbf{0}$$ $$\frac{\partial L}{\partial w_{0}}=0$$

2. Допустимость:

   $$y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})\ge1-\xi_{i}, \quad i=1,2,...N$$ $$\xi_{i}\ge 0, \quad i=1,2,...N$$

3. Дополняющая нежёсткость:

   $$\alpha_{i}[y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})-1+\xi_{i}]=0$$ $$\beta_{i}\xi_{i}=0$$ $$i=1,2,...N.$$

4. Неотрицательность:

   $$\alpha_i\ge 0,\beta_i\ge 0,$$ $$i=1,2,...N.$$

Неинформативные и опорные вектора

Вспомним, что мы называли неинформативными векторами те объекты, для которых выполняется условие

$$y_i(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})>1$$

Эти объекты лежат в глубине своих классов и не оказывают влияния на решение. Из условия дополняющей нежёсткости для таких векторов $\alpha_i=0$. Опорными векторами назывались объекты $\mathbf{x}_{i}$, для которых выполнялось условие

$$y_i(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})\le 1$$

Индексы объектов с $\alpha_i>0$ обозначим $SV$. В общем случае оно будет совпадать с множеством опорных векторов.

Перепишем лагранжиан в эквивалентном виде:

$$L=\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\sum_{i=1}^{N}\xi_{n}\left(C-\alpha_{i}-\beta_{i}\right)-w_{0}\sum_{i=1}^{N}\alpha_{i}y_{i}-\mathbf{w}^{T}\sum_{i=1}^{N}\alpha_{i}y_{i}\mathbf{x}_{i}+\sum_{i=1}^{N}\alpha_{i}$$

Из условий стационарности получаем:

$$\frac{\partial L}{\partial\mathbf{w}}=\mathbf{w}-\sum_{i=1}^{N}\alpha_{i}y_{i}\mathbf{x}_{i}=\mathbf{0}$$$$\frac{\partial L}{\partial w_{0}}=-\sum_{n=1}^{N}\alpha_{i}y_{i}=0$$$$\frac{\partial L}{\partial\xi_{i}}=C-\alpha_{i}-\beta_{i}=0$$

Из последнего условия и условий неотрицательности следует, что $\alpha_i\in[0,C]$ для $i=1,2,...N$.

Подставляя условия стационарности в лагранжиан, получаем, что

$$\begin{aligned} L &= \frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\sum_{i=1}^{N}\xi_{i}\xcancel{\left(C-\alpha_{i}-\beta_{i}\right)}-w_{0}\xcancel{\sum_{i=1}^{N}\alpha_{i}y_{i}}-\mathbf{w}^{T}\sum_{i=1}^{N}\alpha_{i}y_{i}\mathbf{x}_{i}+\sum_{i=1}^{N}\alpha_{i} \\ &= \frac{1}{2}\left(\sum_{i=1}^{N}\alpha_{i}y_{i}\mathbf{x}_{i}\right)^{T}\left(\sum_{j=1}^{N}\alpha_{j}y_{j}\mathbf{x}_{j}\right)-\left(\sum_{i=1}^{N}\alpha_{i}y_{i}\mathbf{x}_{i}\right)^{T}\left(\sum_{j=1}^{N}\alpha_{j}y_{j}\mathbf{x}_{j}\right)+\sum_{i=1}^{N}\alpha_{i} \\ &= \frac{1}{2}\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}\mathbf{x}_{i}^{T}\mathbf{x}_{j}-\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}\mathbf{x}_{i}^{T}\mathbf{x}_{j}+\sum_{n=1}^{N}\alpha_{n} \\ &= -\frac{1}{2}\sum\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}\mathbf{x}_{i}^{T}\mathbf{x}_{j}+\sum_{n=1}^{N}\alpha_{n} \end{aligned}$$

Для исходной оптимизационной задачи выполняются условия Слейтера [2], состоящие в том, что существуют такой набор $(\mathbf{x},\boldsymbol{\xi})$, при котором все ограничения на неравенства становятся строгими неравенствами. Действительно, совмещения условий

$$\begin{cases} y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+w_{0})> 1-\xi_{i} & i=1,2,...N\\ \xi_{i} > 0 & i=1,2,...N \end{cases}$$

легко достичь, рассмотрев достаточно большие $\xi_i, i=1,2,...N$. При выполнении этих условий в задачах выпуклой оптимизации по теореме Слейтера [2] оптимальный набор $\alpha_1,...\alpha_N$ можно найти из решения двойственной задачи:

$$\begin{cases} -\frac{1}{2}\sum\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}\mathbf{x}_{i}^{T}\mathbf{x}_{j}+\sum_{n=1}^{N}\alpha_{n} \to \min_{\boldsymbol{\alpha}} \\ \sum_{n=1}^{N}\alpha_{i}y_{i}=0, \\ 0 \le \alpha_i \le C, \quad i=1,2,...N \end{cases}$$

Ограничение-равенство здесь возникает из условий стационарности Каруша-Куна-Таккера, а ограничение-неравенство возникает также из условий стационарности и условий неотрицательности двойственных переменных $\alpha_i$ и $\beta_i$.

Найдя оптимальные $\alpha_i^*$ из двойственной задачи, мы можем найти оптимальный вектор весов:

$$\mathbf{w}^*=\sum_{i=1}^{N}\alpha_{i}^*y_{i}\mathbf{x}_{i} = \sum_{i\in SV}\alpha_{i}^*y_{i}\mathbf{x}_{i},$$

где $SV$ - множество опорных векторов.

Заметим, что для таких векторов из условия стационарности

Для объектов с индексами $i$, у которых $0<\alpha_i^*<C$ из условий стационарности получаем, что $\beta_i^*>0$, а из условий дополняющей нежёсткости

$$\begin{aligned} \beta_{i}^*\xi_{i}^*=0 \\ \alpha^*_{i}[y_{i}((\mathbf{w^*})^{T}\mathbf{x}_{i}+w_{0}^*)-1+\xi_{i}^*]=0 \end{aligned}$$

следует, что

$$\begin{aligned} \xi_i^*=0 \\ y_{i}((\mathbf{w^*})^{T}\mathbf{x}_{i}+w_{0}^*)-1 = 0 \end{aligned}$$

Из последнего условия можно найти оптимальное значение для $w_0^*$. Из соображений численной устойчивости $w_0^*$ находят не по одному $i$, а из усреднённого значения последнего равенства для всех $i$, у которых $0<\alpha_i^*<C$.

Частный случай

В частном случае ни одного $i$, для которого $0 < \alpha_i^* < C$ может не оказаться. В этом случае оптимальное смещение $w_0^*$ находят через следующим образом:

1. Вычисляют рейтинги объектов:

$$r_j = (\mathbf{w}^*)^\top \mathbf{x}_j=\sum_{i=1}^{N}\alpha_{i}^*y_{i}\mathbf{x}_{i}^T\mathbf{x}_j$$

2. Определяют «наихудший» отрицательный и «наилучший» положительный рейтинг:

$$a = \max_{i: y_i = -1} r_i, \quad b = \min_{i: y_i = +1} r_i$$

3. Смещение устанавливают посередине:

$$w_0^* = -\,\frac{a+b}{2}$$

Как видим, лишь опорные объекты оказывают влияние на оптимальные $\mathbf{w}^*$ и $w_0^*$, а неинформативные - не оказывают.

Прогноз будет строиться по правилу

$$\widehat{y}\left(\mathbf{x}\right)=\text{sign}\left(\mathbf{w}^{T}\mathbf{x}+w_{0}\right)=\text{sign}\left(\sum_{i\in SV}\alpha_{i}^{*}y_{i}\mathbf{x}_{i}^{T}\mathbf{x}+w_{0}\right)$$

Мы описали, как каждый шаг настройки и применения метода опорных векторов можно реализовать, используя только скалярные произведения между объектами, а не напрямую их признаковые описания.

Это позволяет применить обобщение метода через ядра, перейдя от скалярных произведений в исходном пространстве $\mathbf{x}$ к функциям ядра, являющихся скалярными произведениями в новом (спрямляющем) признаковом пространстве $\phi(\mathbf{x})$:

$$\mathbf{x}^{T}\mathbf{x}'=\left<\mathbf{x},\mathbf{x}'\right>\to k(\mathbf{x},\mathbf{x}')=\left<\phi\left(\mathbf{x}\right),\phi\left(\mathbf{x}'\right)\right>$$

Для этого нужно

1. Найти оптимальные двойственные переменные $\alpha_1,...\alpha_N$ из двойственной оптимизационной задачи

$$\begin{cases} -\frac{1}{2}\sum\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}k(\mathbf{x}_{i},\mathbf{x}_{j})+\sum_{n=1}^{N}\alpha_{n} \to \min_{\boldsymbol{\alpha}} \\ \sum_{n=1}^{N}\alpha_{i}y_{i}=0, \\ 0 \le \alpha_i \le C, \quad i=1,2,...N \end{cases}$$

2. Вычислить $w_0^*$ по объектам $\mathbf{x}_{j}$, для которых $y_{i}(\sum_{i\in SV}\alpha_{i}^{*}y_{i}k(\mathbf{x}_{i},\mathbf{x}_{j})+w_{0}^*)=1$

3. Для новых объектов строить прогноз по правилу

$$\widehat{y}\left(\mathbf{x}\right)=\text{sign}\left(\sum_{i\in SV}\alpha_{i}^{*}y_{i}k(\mathbf{x}_{i},\mathbf{x})+w_{0}\right)$$

Из функциональной формы прогноза видно, что

• при линейном ядре получим линейный метод классификации;

• при полиномиальном ядре метод будет строить полиномиальную поверхность, разделяющую классы;

• при RBF-ядре метод будет работать как метрическим метод, поскольку его прогнозы будут определяться близостью $\mathbf{x}$ до опорных векторов.

Литература

1. Википедия: условия Каруша-Куна-Таккера.
2. Выпуклая оптимизация: учебное пособие / Воронцова Е. А., Хильдебранд Р. Ф., Гасников А. В., Стонякин Ф. С. — Москва: МФТИ, 2021. — 364 с. — ISBN 978-5-7417-0776-0.