Машина опорных векторов наименьших квадратов

Машины опорных векторов наименьших квадратов (LS-SVM) для статистики и статистического моделирования представляют собой (SVM) с методом наименьших квадратов версии машин опорных векторов , которые представляют собой набор связанных контролируемых методов обучения, которые анализируют данные и распознают закономерности, и которые используются для классификации и регрессионного анализа . В этой версии решение находится путем решения набора линейных уравнений вместо задачи выпуклого квадратичного программирования (QP) для классических SVM. Классификаторы SVM по методу наименьших квадратов были предложены Йоханом Суйкенсом и Йосом Вандевалле. LS-SVM — это класс методов обучения на основе ядра .

От машины опорных векторов к машине опорных векторов наименьших квадратов

Учитывая обучающий набор $\{x_{i},y_{i}\}_{i=1}^{N}$ с входными данными $x_{i}\in \mathbb {R} ^{n}$ и соответствующие метки двоичных классов $y_{i}\in \{-1,+1\}$, СВМ классификатор, согласно оригинальной формулировке Вапника , удовлетворяет следующим условиям:

Данные спирали: $y_{i}=1$ для синей точки данных, $y_{i}=-1$ для красной точки данных

${\begin{cases}w^{T}\phi (x_{i})+b\geq 1,&{\text{if }}\quad y_{i}=+1,\\w^{T}\phi (x_{i})+b\leq -1,&{\text{if }}\quad y_{i}=-1,\end{cases}}$

что эквивалентно

$y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1,\quad i=1,\ldots ,N,$

где $\phi (x)$ — это нелинейная карта исходного пространства в многомерное или бесконечномерное пространство.

Неотделимые данные

В случае, если такой разделяющей гиперплоскости не существует, вводятся так называемые слабые переменные $\xi _{i}$ такой, что

${\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N.\end{cases}}$

Результат классификатора SVM

В соответствии с принципом минимизации структурного риска граница риска минимизируется с помощью следующей задачи минимизации:

$\min J_{1}(w,\xi )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}\xi _{i},$

${\text{Subject to }}{\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N,\end{cases}}$

Чтобы решить эту проблему, мы могли бы построить функцию Лагранжа :

$L_{1}(w,b,\xi ,\alpha ,\beta )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}{\xi _{i}}-\sum \limits _{i=1}^{N}\alpha _{i}\left\{y_{i}\left[{w^{T}\phi (x_{i})+b}\right]-1+\xi _{i}\right\}-\sum \limits _{i=1}^{N}\beta _{i}\xi _{i},$

где $\alpha _{i}\geq 0,\ \beta _{i}\geq 0\ (i=1,\ldots ,N)$ являются множителями Лагранжа . Оптимальная точка будет находиться в седле функции Лагранжа, и тогда получим

${\begin{cases}{\frac {\partial L_{1}}{\partial w}}=0\quad \to \quad w=\sum \limits _{i=1}^{N}\alpha _{i}y_{i}\phi (x_{i}),\\{\frac {\partial L_{1}}{\partial b}}=0\quad \to \quad \sum \limits _{i=1}^{N}\alpha _{i}y_{i}=0,\\{\frac {\partial L_{1}}{\partial \xi _{i}}}=0\quad \to \quad \alpha _{i}+\beta _{i}=c,\;i=1,\ldots ,N\quad \to \quad 0\leq \alpha _{i}\leq c,\;i=1,\ldots ,N.\end{cases}}$ ( 1 )

Подставив $w$ путем его выражения в лагранжиане, сформированном из соответствующей цели и ограничений, мы получим следующую задачу квадратичного программирования:

$\max Q_{1}(\alpha )=-{\frac {1}{2}}\sum \limits _{i,j=1}^{N}{\alpha _{i}\alpha _{j}y_{i}y_{j}K(x_{i},x_{j})}+\sum \limits _{i=1}^{N}\alpha _{i},$

где $K(x_{i},x_{j})=\left\langle \phi (x_{i}),\phi (x_{j})\right\rangle$ называется функцией ядра . Решая эту задачу QP с учетом ограничений в ( 1 ), мы получим гиперплоскость в многомерном пространстве и, следовательно, классификатор в исходном пространстве.

Формулировка SVM по методу наименьших квадратов

Версия классификатора SVM по методу наименьших квадратов получается путем переформулировки задачи минимизации как

$\min J_{2}(w,b,e)={\frac {\mu }{2}}w^{T}w+{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}e_{i}^{2},$

с учетом ограничений равенства

$y_{i}\left[{w^{T}\phi (x_{i})+b}\right]=1-e_{i},\quad i=1,\ldots ,N.$

Приведенная выше формулировка классификатора SVM наименьших квадратов (LS-SVM) неявно соответствует интерпретации регрессии с двоичными целевыми объектами. $y_{i}=\pm 1$.

С использованием $y_{i}^{2}=1$, у нас есть

$\sum \limits _{i=1}^{N}e_{i}^{2}=\sum \limits _{i=1}^{N}(y_{i}e_{i})^{2}=\sum \limits _{i=1}^{N}e_{i}^{2}=\sum \limits _{i=1}^{N}\left(y_{i}-(w^{T}\phi (x_{i})+b)\right)^{2},$

с $e_{i}=y_{i}-(w^{T}\phi (x_{i})+b).$ Обратите внимание, что эта ошибка также имеет смысл для аппроксимации данных методом наименьших квадратов, так что те же конечные результаты справедливы и для случая регрессии.

Следовательно, формулировка классификатора LS-SVM эквивалентна

$J_{2}(w,b,e)=\mu E_{W}+\zeta E_{D}$

с $E_{W}={\frac {1}{2}}w^{T}w$ и $E_{D}={\frac {1}{2}}\sum \limits _{i=1}^{N}e_{i}^{2}={\frac {1}{2}}\sum \limits _{i=1}^{N}\left(y_{i}-(w^{T}\phi (x_{i})+b)\right)^{2}.$

Результат классификатора LS-SVM

Оба $\mu$ и $\zeta$ следует рассматривать как гиперпараметры для настройки степени регуляризации по сравнению с суммой квадратов ошибок. Решение зависит только от соотношения $\gamma =\zeta /\mu$, поэтому в исходной формулировке используются только $\gamma$ в качестве параметра настройки. Мы используем оба $\mu$ и $\zeta$ в качестве параметров, чтобы обеспечить байесовскую интерпретацию LS-SVM.

Решение регрессора LS-SVM будет получено после построения функции Лагранжа :

${\begin{cases}L_{2}(w,b,e,\alpha )\;=J_{2}(w,e)-\sum \limits _{i=1}^{N}\alpha _{i}\left\{{\left[{w^{T}\phi (x_{i})+b}\right]+e_{i}-y_{i}}\right\},\\\quad \quad \quad \quad \quad \;={\frac {1}{2}}w^{T}w+{\frac {\gamma }{2}}\sum \limits _{i=1}^{N}e_{i}^{2}-\sum \limits _{i=1}^{N}\alpha _{i}\left\{\left[w^{T}\phi (x_{i})+b\right]+e_{i}-y_{i}\right\},\end{cases}}$

где $\alpha _{i}\in \mathbb {R}$ являются множителями Лагранжа. Условия оптимальности таковы.

${\begin{cases}{\frac {\partial L_{2}}{\partial w}}=0\quad \to \quad w=\sum \limits _{i=1}^{N}\alpha _{i}\phi (x_{i}),\\{\frac {\partial L_{2}}{\partial b}}=0\quad \to \quad \sum \limits _{i=1}^{N}\alpha _{i}=0,\\{\frac {\partial L_{2}}{\partial e_{i}}}=0\quad \to \quad \alpha _{i}=\gamma e_{i},\;i=1,\ldots ,N,\\{\frac {\partial L_{2}}{\partial \alpha _{i}}}=0\quad \to \quad y_{i}=w^{T}\phi (x_{i})+b+e_{i},\,i=1,\ldots ,N.\end{cases}}$

Устранение $w$ и $e$ даст линейную систему вместо задачи квадратичного программирования :

$\left[{\begin{matrix}0&1_{N}^{T}\\1_{N}&\Omega +\gamma ^{-1}I_{N}\end{matrix}}\right]\left[{\begin{matrix}b\\\alpha \end{matrix}}\right]=\left[{\begin{matrix}0\\Y\end{matrix}}\right],$

с $Y=[y_{1},\ldots ,y_{N}]^{T}$, $1_{N}=[1,\ldots ,1]^{T}$ и $\alpha =[\alpha _{1},\ldots ,\alpha _{N}]^{T}$. Здесь, $I_{N}$ это $N\times N$ единичная матрица и $\Omega \in \mathbb {R} ^{N\times N}$ - матрица ядра, определенная формулой $\Omega _{ij}=\phi (x_{i})^{T}\phi (x_{j})=K(x_{i},x_{j})$.

Функция ядра K

Для функции ядра K (•, •) обычно есть следующие варианты:

• Линейное ядро: $K(x,x_{i})=x_{i}^{T}x,$
• Полиномиальное ядро ​​степени $d$: $K(x,x_{i})=\left({1+x_{i}^{T}x/c}\right)^{d},$
• Радиальная базисная функция ядра RBF: $K(x,x_{i})=\exp \left({-\left\|{x-x_{i}}\right\|^{2}/\sigma ^{2}}\right),$
• Ядро MLP: $K(x,x_{i})=\tanh \left({k\,x_{i}^{T}x+\theta }\right),$

где $d$, $c$, $\sigma$, $k$ и $\theta$ являются константами. Обратите внимание, что условие Мерсера выполняется для всех $c,\sigma \in \mathbb {R} ^{+}$ и $d\in N$ значения в случае полинома и RBF, но не для всех возможных вариантов выбора $k$ и $\theta$ по делу МЛП. Параметры шкалы $c$, $\sigma$ и $k$ определить масштабирование входных данных в полиномиальной, RBF и функции ядра MLP . Это масштабирование связано с пропускной способностью ядра в статистике , где показано, что пропускная способность является важным параметром поведения обобщения метода ядра.

Байесовская интерпретация LS-SVM

Байесовская интерпретация SVM была предложена Смолой и др. Они показали, что использование разных ядер в SVM можно рассматривать как определение различных априорных распределений вероятностей в функциональном пространстве, а именно: $P[f]\propto \exp \left({-\beta \left\|{{\hat {P}}f}\right\|^{2}}\right)$. Здесь $\beta >0$ является константой и ${\hat {P}}$ – оператор регуляризации, соответствующий выбранному ядру.

Общая байесовская система доказательств была разработана Маккеем. и Маккей использовал его для решения проблемы регрессии, прямой нейронной сети и сети классификации. Предоставленный набор данных $D$, модель $\mathbb {M}$ с вектором параметров $w$ и так называемый гиперпараметр или параметр регуляризации $\lambda$Байесовский вывод строится с тремя уровнями вывода:

• На уровне 1 для заданного значения $\lambda$, первый уровень вывода предполагает апостериорное распределение $w$ по байесовскому правилу

$p(w|D,\lambda ,\mathbb {M} )\propto p(D|w,\mathbb {M} )p(w|\lambda ,\mathbb {M} ).$

• Второй уровень вывода определяет ценность $\lambda$, максимизируя

$p(\lambda |D,\mathbb {M} )\propto p(D|\lambda ,\mathbb {M} )p(\lambda |\mathbb {M} ).$

• Третий уровень вывода в системе фактических данных ранжирует различные модели путем изучения их апостериорных вероятностей.

$p(\mathbb {M} |D)\propto p(D|\mathbb {M} )p(\mathbb {M} ).$

Мы видим, что байесовская структура доказательств представляет собой единую теорию обучения модели и выбора модели.Квок использовал байесовскую структуру доказательств для интерпретации формулировки SVM и выбора модели. И он также применил байесовскую систему доказательств для поддержки векторной регрессии.

Теперь, учитывая данные $\{x_{i},y_{i}\}_{i=1}^{N}$ и гиперпараметры $\mu$ и $\zeta$ модели $\mathbb {M}$, параметры модели $w$ и $b$ оцениваются путем максимизации апостериорного $p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )$. Применяя правило Байеса, получаем

$p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )={\frac {p(D|w,b,\log \mu ,\log \zeta ,\mathbb {M} )p(w,b|\log \mu ,\log \zeta ,\mathbb {M} )}{p(D|\log \mu ,\log \zeta ,\mathbb {M} )}},$

где $p(D|\log \mu ,\log \zeta ,\mathbb {M} )$ — нормирующая константа, такая как интеграл по всем возможным $w$ и $b$ равен 1.Мы предполагаем $w$ и $b$ не зависят от гиперпараметра $\zeta$, и условно независимы, т. е. мы предполагаем

$p(w,b|\log \mu ,\log \zeta ,\mathbb {M} )=p(w|\log \mu ,\mathbb {M} )p(b|\log \sigma _{b},\mathbb {M} ).$

Когда $\sigma _{b}\to \infty$, распределение $b$ будет приближаться к равномерному распределению. Кроме того, мы предполагаем $w$ и $b$ являются гауссовским распределением, поэтому мы получаем априорное распределение $w$ и $b$ с $\sigma _{b}\to \infty$ быть

${\begin{array}{l}p(w,b|\log \mu ,)=\left({\frac {\mu }{2\pi }}\right)^{\frac {n_{f}}{2}}\exp \left({-{\frac {\mu }{2}}w^{T}w}\right){\frac {1}{\sqrt {2\pi \sigma _{b}}}}\exp \left({-{\frac {b^{2}}{2\sigma _{b}}}}\right)\\\quad \quad \quad \quad \quad \quad \quad \propto \left({\frac {\mu }{2\pi }}\right)^{\frac {n_{f}}{2}}\exp \left({-{\frac {\mu }{2}}w^{T}w}\right)\end{array}}.$

Здесь $n_{f}$ - размерность пространства признаков, такая же, как размерность $w$.

Вероятность $p(D|w,b,\log \mu ,\log \zeta ,\mathbb {M} )$ предполагается, что оно зависит только от $w,b,\zeta$ и $\mathbb {M}$. Мы предполагаем, что точки данных независимо одинаково распределены (iid), так что:

$p(D|w,b,\log \zeta ,\mathbb {M} )=\prod \limits _{i=1}^{N}{p(x_{i},y_{i}|w,b,\log \zeta ,\mathbb {M} )}.$

Чтобы получить функцию наименьших квадратов стоимости, предполагается, что вероятность точки данных пропорциональна:

$p(x_{i},y_{i}|w,b,\log \zeta ,\mathbb {M} )\propto p(e_{i}|w,b,\log \zeta ,\mathbb {M} ).$

Для ошибок взято гауссово распределение $e_{i}=y_{i}-(w^{T}\phi (x_{i})+b)$ как:

$p(e_{i}|w,b,\log \zeta ,\mathbb {M} )={\sqrt {\frac {\zeta }{2\pi }}}\exp \left({-{\frac {\zeta e_{i}^{2}}{2}}}\right).$

Предполагается, что $w$ и $b$ определяются таким образом, что центры классов ${\hat {m}}_{-}$ и ${\hat {m}}_{+}$ сопоставляются с целью -1 и +1 соответственно. Прогнозы $w^{T}\phi (x)+b$ элементов класса $\phi (x)$ следовать многомерному распределению Гаусса, которое имеет дисперсию $1/\zeta$.

Объединив предыдущие выражения и пренебрегая всеми константами, правило Байеса принимает вид

$p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )\propto \exp(-{\frac {\mu }{2}}w^{T}w-{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}{e_{i}^{2}})=\exp(-J_{2}(w,b)).$

Максимальные оценки апостериорной плотности $w_{MP}$ и $b_{MP}$ затем получаются минимизацией отрицательного логарифма (26), поэтому мы приходим к (10).

Библиография

• Дж. К. Суйкенс, Т. Ван Гестель, Дж. Де Брабантер, Б. Де Мур, Дж. Вандевалле, Машины опорных векторов наименьших квадратов, World Scientific Pub. Ко., Сингапур, 2002 г. ISBN   981-238-151-1
• Суйкенс Дж. А. К., Вандевалле Дж., Классификаторы векторных машин, поддерживающие метод наименьших квадратов, Neural Processing Letters , vol. 9, нет. 3 июня 1999 г., стр. 293–300.
• Владимир Вапник. Природа статистической теории обучения . Спрингер-Верлаг, 1995. ISBN   0-387-98780-0
• Маккей, DJC, Вероятные сети и правдоподобные предсказания — обзор практических байесовских методов для контролируемых нейронных сетей. Сеть: Вычисления в нейронных системах , вып. 6, 1995, стр. 469–505.

Внешние ссылки

• www.esat.kuleuven.be/sista/lssvmlab/ «Набор инструментов Лаборатории векторных машин с поддержкой наименьших квадратов (LS-SVMlab) содержит реализации Matlab/C для ряда алгоритмов LS-SVM».
• www.kernel-machines.org «Машины опорных векторов и методы на основе ядра (Смола и Шёлкопф)».
• www.gaussianprocess.org «Гауссовы процессы: моделирование данных с использованием априорных значений гауссовского процесса вместо функций регрессии и классификации (Маккей, Уильямс)».
• www.support-vector.net «Машины опорных векторов и методы на основе ядра (Кристианини)».
• dlib : содержит реализацию SVM метода наименьших квадратов для крупномасштабных наборов данных.