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

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

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

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

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

${\displaystyle {\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}}}$

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

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

где – нелинейное отображение исходного пространства в многомерное или бесконечномерное пространство. ${\displaystyle \phi (x)}$

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle 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},}$

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

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

${\displaystyle \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},}$

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

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

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

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

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

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

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

Используя , мы имеем ${\displaystyle y_{i}^{2}=1}$

${\displaystyle \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},}$

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

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

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

с и ${\displaystyle E_{W}={\frac {1}{2}}w^{T}w}$ ${\displaystyle 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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle \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],}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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} )}},}$

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

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

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

${\displaystyle {\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}}.}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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)).}$

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

Рекомендации

1. Суйкенс, JAK; Вандевалле, Дж. (1999) «Наименьшие квадраты поддерживают классификаторы векторных машин», Neural Processing Letters , 9 (3), 293–300.
2. Вапник, В. Природа статистической теории обучения. Спрингер-Верлаг, Нью-Йорк, 1995 г.
3. Маккей, DJC Байесовская интерполяция. Нейронные вычисления, 4 (3): 415–447, май 1992 г.
4. Маккей, DJC. Практическая байесовская структура для сетей обратного распространения ошибки. Нейронные вычисления, 4 (3): 448–472, май 1992 г.
5. Маккей, DJC. Структура доказательств, применяемая к классификационным сетям. Нейронные вычисления, 4 (5): 720–736, сентябрь 1992 г.

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

• Дж. К. Суйкенс, Т. Ван Гестель, Дж. Де Брабантер, Б. Де Мур, Дж. Вандевалле, Машины опорных векторов наименьших квадратов, World Scientific Pub. Co., Сингапур, 2002. ISBN  981-238-151-1.
• Суйкенс Дж. А. К., Вандевалле Дж., Классификаторы векторных машин, поддерживающие метод наименьших квадратов, Neural Processing Letters , vol. 9, нет. 3 июня 1999 г., стр. 293–300.
• Владимир Вапник. Природа статистической теории обучения . Springer-Verlag, 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 метода наименьших квадратов для крупномасштабных наборов данных.