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

В машинном обучении поддержка векторных машин ( SVM) , также поддержка векторных сетей. ) — это контролируемые модели максимальной прибыли с соответствующими алгоритмами обучения , которые анализируют данные для классификации и регрессионного анализа . Разработан в AT&T Bell Laboratories Владимиром Вапником с коллегами (Boser et al., 1992, Guyon et al., 1993, Cortes and Vapnik , 1995, Вапник и др., 1997. ) SVM являются одной из наиболее изученных моделей, основанных на статистических основах обучения теории венчурного капитала, предложенных Вапником (1982, 1995) и Червоненкисом (1974).

Помимо выполнения линейной классификации , SVM могут эффективно выполнять нелинейную классификацию, используя так называемый трюк ядра , представляя данные только через набор попарных сравнений сходства между исходными точками данных с использованием функции ядра, которая преобразует их в координаты. в многомерном пространстве признаков . Таким образом, SVM используют трюк с ядром для неявного отображения своих входных данных в многомерные пространства признаков, где можно выполнить линейную классификацию. Будучи моделями с максимальной прибылью, SVM устойчивы к зашумленным данным (например, неправильно классифицированным примерам). SVM также можно использовать для задач регрессии , где целью становится $\epsilon$-чувствительный.

Кластеризация опорных векторов Алгоритм, созданный Хавой Зигельманном и Владимиром Вапником , применяет статистику опорных векторов, разработанную в алгоритме машин опорных векторов, для категоризации неразмеченных данных. Эти наборы данных требуют подходов к обучению без учителя , которые пытаются найти естественную кластеризацию данных по группам, а затем сопоставить новые данные в соответствии с этими кластерами.

Популярность SVM, вероятно, обусловлена ​​их поддающимися теоретическому анализу, их гибкостью в применении к широкому кругу задач, включая задачи структурированного прогнозирования . Неясно, обладают ли SVM лучшими прогностическими характеристиками, чем другие линейные модели, такие как логистическая регрессия и линейная регрессия .

Мотивация

H ₁ не разделяет классы. H ₂ делает, но лишь с небольшим запасом. H ₃ разделяет их с максимальным отрывом.

Классификация данных — распространенная задача в машинном обучении .Предположим, каждая из заданных точек данных принадлежит к одному из двух классов, и цель состоит в том, чтобы решить, в каком классе будет находиться новая точка данных . В случае машин опорных векторов точка данных рассматривается как $p$-мерный вектор (список $p$ числа), и мы хотим знать, сможем ли мы разделить такие точки с помощью $(p-1)$-мерная гиперплоскость . Это называется линейным классификатором . Существует множество гиперплоскостей, которые могут классифицировать данные. Разумным выбором в качестве лучшей гиперплоскости является та, которая представляет собой наибольшее расстояние или границу между двумя классами. Поэтому мы выбираем гиперплоскость так, чтобы расстояние от нее до ближайшей точки данных на каждой стороне было максимальным. Если такая гиперплоскость существует, она называется гиперплоскостью с максимальным запасом , а линейный классификатор, который она определяет, известен как классификатор с максимальным запасом ; или, что то же самое, перцептрон оптимальной стабильности .

Более формально, машина опорных векторов создает гиперплоскость или набор гиперплоскостей в многомерном или бесконечномерном пространстве, которые можно использовать для классификации , регрессии или других задач, таких как обнаружение выбросов. Интуитивно понятно, что хорошее разделение достигается с помощью гиперплоскости, которая имеет наибольшее расстояние до ближайшей точки обучающих данных любого класса (так называемый функциональный запас), поскольку, как правило, чем больше запас, тем ниже ошибка обобщения классификатора. Меньшая ошибка обобщения означает, что разработчик с меньшей вероятностью столкнется с переоснащением .

Ядро машины

Хотя исходная задача может быть сформулирована в конечномерном пространстве, часто случается, что дискриминируемые множества не являются линейно разделимыми в этом пространстве. По этой причине было предложено что исходное конечномерное пространство отображается в пространство гораздо более высокой размерности, что, по-видимому, облегчает разделение в этом пространстве. Чтобы поддерживать разумную вычислительную нагрузку, отображения, используемые схемами SVM, разработаны таким образом, чтобы гарантировать, что скалярные произведения пар векторов входных данных могут быть легко вычислены в терминах переменных в исходном пространстве, определяя их в терминах функции ядра. $k(x,y)$ выбранный для решения проблемы. Гиперплоскости в многомерном пространстве определяются как набор точек, скалярное произведение которых с вектором в этом пространстве является постоянным, причем такой набор векторов представляет собой ортогональный (и, следовательно, минимальный) набор векторов, определяющий гиперплоскость. Векторы, определяющие гиперплоскости, можно выбрать как линейные комбинации с параметрами $\alpha _{i}$ изображений векторов признаков $x_{i}$ которые происходят в базе данных. При таком выборе гиперплоскости точки $x$ в пространстве признаков , отображаемых в гиперплоскость, определяются соотношением $\textstyle \sum _{i}\alpha _{i}k(x_{i},x)={\text{constant}}.$ Обратите внимание, что если $k(x,y)$ становится маленьким, так как $y$ растет дальше от $x$, каждое слагаемое суммы измеряет степень близости контрольной точки $x$ в соответствующую точку базы данных $x_{i}$. Таким образом, сумму ядер, приведенную выше, можно использовать для измерения относительной близости каждой контрольной точки к точкам данных, происходящим из одного или другого из наборов, подлежащих различению. Обратите внимание на то, что множество точек $x$ отображенные в любую гиперплоскость, в результате могут быть весьма запутанными, что позволяет гораздо более сложно различать множества, которые вообще не являются выпуклыми в исходном пространстве.

Приложения

SVM можно использовать для решения различных реальных задач:

• SVM полезны при категоризации текста и гипертекста , поскольку их применение может значительно снизить потребность в помеченных обучающих примерах как в стандартных индуктивных, так и в трансдуктивных настройках. Некоторые методы поверхностного семантического анализа основаны на машинах опорных векторов.
• Классификацию изображений также можно выполнить с помощью SVM. Результаты экспериментов показывают, что SVM достигают значительно более высокой точности поиска, чем традиционные схемы уточнения запроса, уже после трех-четырех раундов обратной связи по релевантности. Это также верно для систем сегментации изображений , в том числе использующих модифицированную версию SVM, использующую привилегированный подход, предложенный Вапником.
• Классификация спутниковых данных, таких как данные SAR, с использованием контролируемого SVM.
• Рукописные символы можно распознать с помощью SVM.
• Алгоритм SVM широко применяется в биологических и других науках. Они использовались для классификации белков, при этом до 90% соединений были классифицированы правильно. Тесты перестановок, основанные на весах SVM, были предложены в качестве механизма интерпретации моделей SVM. Машинные веса опорных векторов также использовались для интерпретации моделей SVM в прошлом. Постфокальная интерпретация машинных моделей опорных векторов с целью выявления особенностей, используемых моделью для прогнозирования, является относительно новой областью исследований, имеющей особое значение в биологических науках.

История

Оригинальный алгоритм SVM был изобретен Владимиром Н. Вапником и Алексеем Я. Червоненкиса в 1964 году. В 1992 году Бернхард Бозер, Изабель Гийон и Владимир Вапник предложили способ создания нелинейных классификаторов, применив трюк с ядром к гиперплоскостям с максимальным запасом. Вариант «мягкой маржи», обычно используемый в пакетах программного обеспечения, был предложен Коринной Кортес и Вапником в 1993 году и опубликован в 1995 году.

Линейная СВМ

Гиперплоскость с максимальным запасом и запасы для SVM, обученного на образцах из двух классов. Выборки на границе называются опорными векторами.

Нам дан набор обучающих данных $n$ точки формы $$(\mathbf {x} _{1},y_{1}),\ldots ,(\mathbf {x} _{n},y_{n}),$$где $y_{i}$ равны либо 1, либо −1, каждый из которых указывает на класс, к которому относится точка. $\mathbf {x} _{i}$ принадлежит. Каждый $\mathbf {x} _{i}$ это $p$-мерный действительный вектор. Мы хотим найти «гиперплоскость с максимальным запасом», разделяющую группу точек. $\mathbf {x} _{i}$ для чего $y_{i}=1$ из группы точек, для которых $y_{i}=-1$, который определяется так, что расстояние между гиперплоскостью и ближайшей точкой $\mathbf {x} _{i}$ из любой группы максимизируется.

Любую гиперплоскость можно записать как множество точек $\mathbf {x}$ удовлетворяющий $$\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=0,$$где $\mathbf {w}$ — (не обязательно нормированный) вектор нормали к гиперплоскости. Это очень похоже на нормальную форму Гессена , за исключением того, что $\mathbf {w}$ не обязательно является единичным вектором. Параметр ${\tfrac {b}{\|\mathbf {w} \|}}$ определяет смещение гиперплоскости от начала координат вдоль вектора нормали. Не удалось проанализировать (SVG (MathML можно включить через плагин браузера): неверный ответ («Расширение Math не может подключиться к Restbase.») от сервера «http://localhost: 6011/en.wikipedia.org/v1/":): {\displaystyle \mathbf{w}} .

Жесткая маржа

Если обучающие данные линейно разделимы , мы можем выбрать две параллельные гиперплоскости, разделяющие два класса данных, так, чтобы расстояние между ними было как можно большим. Область, ограниченная этими двумя гиперплоскостями, называется «полем», а гиперплоскость с максимальным запасом — это гиперплоскость, лежащая на полпути между ними. С помощью нормализованного или стандартизированного набора данных эти гиперплоскости можно описать уравнениями

$\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=1$ (все, что находится на этой границе или выше, относится к одному классу с меткой 1)

и

$\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=-1$ (все, что находится на этой границе или ниже, относится к другому классу с меткой −1).

Геометрически расстояние между этими двумя гиперплоскостями равно ${\tfrac {2}{\|\mathbf {w} \|}}$, поэтому, чтобы максимизировать расстояние между плоскостями, мы хотим минимизировать $\|\mathbf {w} \|$. Расстояние вычисляется с использованием уравнения расстояния от точки до плоскости . Нам также необходимо предотвратить попадание точек данных в пределы поля. Мы добавляем следующее ограничение: для каждого $i$ или $$\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\geq 1\,,{\text{ if }}y_{i}=1,$$или $$\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\leq -1\,,{\text{ if }}y_{i}=-1.$$Эти ограничения гласят, что каждая точка данных должна лежать на правильной стороне поля.

Это можно переписать как

$$y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\geq 1,\quad {\text{ for all }}1\leq i\leq n.$$ ( 1 )

Мы можем объединить это, чтобы получить задачу оптимизации:

${\begin{aligned}&{\underset {\mathbf {w} ,\;b}{\operatorname {minimize} }}&&\|\mathbf {w} \|_{2}^{2}\\&{\text{subject to}}&&y_{i}(\mathbf {w} ^{\top }\mathbf {x} _{i}-b)\geq 1\quad \forall i\in \{1,\dots ,n\}\end{aligned}}$

The $\mathbf {w}$ и $b$ которые решают эту задачу, определяют окончательный классификатор, $\mathbf {x} \mapsto \operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b)$, где $\operatorname {sgn}(\cdot )$ это знаковая функция .

Важным следствием этого геометрического описания является то, что гиперплоскость с максимальным запасом полностью определяется теми $\mathbf {x} _{i}$ которые лежат ближе всего к нему (поясняется ниже). Эти $\mathbf {x} _{i}$ называются опорными векторами .

Мягкая маржа

Чтобы расширить SVM на случаи, когда данные не являются линейно разделимыми, шарнирных потерь полезна функция . $$\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right).$$

Обратите внимание, что $y_{i}$ - i -я цель (т. е. в данном случае 1 или -1), и $\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b$ это i -й выход.

Эта функция равна нулю, если выполнено ограничение в (1) , другими словами, если $\mathbf {x} _{i}$ лежит на правильной стороне поля. Для данных на неправильной стороне поля значение функции пропорционально расстоянию от поля.

Целью оптимизации является минимизация:

$$\lVert \mathbf {w} \rVert ^{2}+C\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right],$$

где параметр $C>0$ определяет компромисс между увеличением размера маржи и обеспечением того, чтобы $\mathbf {x} _{i}$ лежат на правильной стороне поля (обратите внимание, что мы можем добавить вес к любому члену в приведенном выше уравнении). Путем деконструкции шарнирных потерь эту проблему оптимизации можно свести к следующему:

$${\begin{aligned}&{\underset {\mathbf {w} ,\;b,\;\mathbf {\zeta } }{\operatorname {minimize} }}&&\|\mathbf {w} \|_{2}^{2}+C\sum _{i=1}^{n}\zeta _{i}\\&{\text{subject to}}&&y_{i}(\mathbf {w} ^{\top }\mathbf {x} _{i}-b)\geq 1-\zeta _{i},\quad \zeta _{i}\geq 0\quad \forall i\in \{1,\dots ,n\}\end{aligned}}$$

Таким образом, при больших значениях $C$, он будет вести себя аналогично SVM с жесткой маржой, если входные данные поддаются линейной классификации, но все равно узнает, жизнеспособно ли правило классификации или нет.

Нелинейные ядра

Ядро машины

Оригинальный алгоритм гиперплоскости с максимальным запасом, предложенный Вапником в 1963 году, построил линейный классификатор . Однако в 1992 году Бернхард Бозер , Изабель Гийон и Владимир Вапник предложили способ создания нелинейных классификаторов, применив трюк с ядром (первоначально предложенный Айзерманом и др. ) к гиперплоскостям с максимальным запасом. Трюк с ядром, когда скалярные произведения заменяются ядрами, легко выводится в двойственном представлении проблемы SVM. Это позволяет алгоритму вписать гиперплоскость с максимальным запасом в преобразованное пространство признаков . Преобразование может быть нелинейным, а преобразованное пространство — многомерным; хотя классификатор представляет собой гиперплоскость в преобразованном пространстве признаков, он может быть нелинейным в исходном входном пространстве.

Примечательно, что работа в многомерном пространстве признаков увеличивает ошибку обобщения машин опорных векторов, хотя при достаточном количестве выборок алгоритм по-прежнему работает хорошо.

Некоторые распространенные ядра включают в себя:

• Полиномиальный (однородный) : $k(\mathbf {x} _{i},\mathbf {x} _{j})=(\mathbf {x} _{i}\cdot \mathbf {x} _{j})^{d}$. В частности, когда $d=1$, это становится линейным ядром.
• Полиномиальный (неоднородный): $k(\mathbf {x} _{i},\mathbf {x} _{j})=(\mathbf {x} _{i}\cdot \mathbf {x} _{j}+r)^{d}$.
• Гауссова радиальная базисная функция : $k(\mathbf {x} _{i},\mathbf {x} _{j})=\exp \left(-\gamma \left\|\mathbf {x} _{i}-\mathbf {x} _{j}\right\|^{2}\right)$ для $\gamma >0$. Иногда параметризуется с использованием $\gamma =1/(2\sigma ^{2})$.
• Сигмовидная функция ( Гиперболический тангенс ): $k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\tanh(\kappa \mathbf {x} _{i}\cdot \mathbf {x} _{j}+c)$ для некоторых (не для всех) $\kappa >0$ и $c<0$.

Ядро связано с преобразованием $\varphi (\mathbf {x} _{i})$ по уравнению $k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x_{j}} )$. Значение w также находится в преобразованном пространстве, причем ${\textstyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\varphi (\mathbf {x} _{i})}$. Скалярные произведения с w для классификации снова можно вычислить с помощью трюка с ядром, т.е. ${\textstyle \mathbf {w} \cdot \varphi (\mathbf {x} )=\sum _{i}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )}$.

Вычисление классификатора SVM

Вычисление классификатора SVM (с мягким пределом) сводится к минимизации выражения формы

$$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.$$ ( 2 )

Мы сосредоточимся на классификаторе мягкой маржи, поскольку, как отмечалось выше, выбор достаточно малого значения для $\lambda$ дает классификатор с жесткой маржой для линейно классифицируемых входных данных. Классический подход, предполагающий сведение (2) к задаче квадратичного программирования , подробно описан ниже. Затем будут обсуждаться более современные подходы, такие как субградиентный спуск и координатный спуск.

Первобытный

Минимизацию (2) можно переписать как задачу оптимизации с ограничениями и дифференцируемой целевой функцией следующим образом.

Для каждого $i\in \{1,\,\ldots ,\,n\}$ мы вводим переменную $\zeta _{i}=\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)$. Обратите внимание, что $\zeta _{i}$ - наименьшее неотрицательное число, удовлетворяющее $y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}.$

Таким образом, мы можем переписать задачу оптимизации следующим образом:

$${\begin{aligned}&{\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|\mathbf {w} \|^{2}\\[0.5ex]&{\text{subject to }}y_{i}\left(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\right)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{for all }}i.\end{aligned}}$$

Это называется первичной проблемой.

Двойной

Решая лагранжеву двойственную вышеприведенную задачу, можно получить упрощенную задачу

$${\begin{aligned}&{\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\mathbf {x} _{i}^{\mathsf {T}}\mathbf {x} _{j})y_{j}c_{j},\\&{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}$$

Это называется двойной проблемой. Поскольку задача двойной максимизации является квадратичной функцией $c_{i}$ при наличии линейных ограничений она эффективно решается с помощью алгоритмов квадратичного программирования .

Здесь переменные $c_{i}$ определены так, что

$$\mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\mathbf {x} _{i}.$$

Более того, $c_{i}=0$ именно когда $\mathbf {x} _{i}$ лежит на правильной стороне поля, и $0<c_{i}<(2n\lambda )^{-1}$ когда $\mathbf {x} _{i}$ лежит на границе границы. Отсюда следует, что $\mathbf {w}$ можно записать как линейную комбинацию опорных векторов.

Смещение, $b$, можно восстановить, найдя $\mathbf {x} _{i}$ на границе поля и решение $$y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-y_{i}.$$

(Обратите внимание, что $y_{i}^{-1}=y_{i}$ с $y_{i}=\pm 1$.)

Трюк с ядром

Основная статья: Метод ядра

Обучающий пример SVM с ядром, заданным формулой φ(( a , b )) = ( a , b , a ² + б ² )

Предположим теперь, что мы хотели бы изучить правило нелинейной классификации, которое соответствует правилу линейной классификации для преобразованных точек данных. $\varphi (\mathbf {x} _{i}).$ Более того, нам дана функция ядра $k$ который удовлетворяет $k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j})$.

Мы знаем вектор классификации $\mathbf {w}$ в преобразованном пространстве удовлетворяет

$$\mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\varphi (\mathbf {x} _{i}),$$

где, $c_{i}$ получаются решением оптимизационной задачи

$${\begin{aligned}{\text{maximize}}\,\,f(c_{1}\ldots c_{n})&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j}))y_{j}c_{j}\\&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}k(\mathbf {x} _{i},\mathbf {x} _{j})y_{j}c_{j}\\{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}&=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}$$

Коэффициенты $c_{i}$ можно решить с помощью квадратичного программирования, как и раньше. Опять же, мы можем найти некоторый индекс $i$ такой, что $0<c_{i}<(2n\lambda )^{-1}$, так что $\varphi (\mathbf {x} _{i})$ лежит на границе поля в преобразованном пространстве, а затем решить

$${\begin{aligned}b=\mathbf {w} ^{\mathsf {T}}\varphi (\mathbf {x} _{i})-y_{i}&=\left[\sum _{j=1}^{n}c_{j}y_{j}\varphi (\mathbf {x} _{j})\cdot \varphi (\mathbf {x} _{i})\right]-y_{i}\\&=\left[\sum _{j=1}^{n}c_{j}y_{j}k(\mathbf {x} _{j},\mathbf {x} _{i})\right]-y_{i}.\end{aligned}}$$

Окончательно,

$$\mathbf {z} \mapsto \operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\varphi (\mathbf {z} )-b)=\operatorname {sgn} \left(\left[\sum _{i=1}^{n}c_{i}y_{i}k(\mathbf {x} _{i},\mathbf {z} )\right]-b\right).$$

Современные методы

Последние алгоритмы поиска классификатора SVM включают субградиентный спуск и координатный спуск. Оба метода доказали, что они предлагают значительные преимущества по сравнению с традиционным подходом при работе с большими, разреженными наборами данных: субградиентные методы особенно эффективны, когда имеется много обучающих примеров, и координирующий спуск, когда размерность пространства признаков высока.

Субградиентный спуск

Алгоритмы субградиентного спуска для SVM работают непосредственно с выражением

$$f(\mathbf {w} ,b)=\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.$$

Обратите внимание, что $f$ является выпуклой функцией $\mathbf {w}$ и $b$. Таким образом, можно адаптировать традиционные методы градиентного спуска (или SGD ), где вместо шага в направлении градиента функции делается шаг в направлении вектора, выбранного из субградиента функции . Преимущество этого подхода заключается в том, что для некоторых реализаций количество итераций не масштабируется с ростом числа итераций. $n$, количество точек данных.

Координатный спуск

Алгоритмы координатного спуска для SVM работают на основе двойственной задачи.

$${\begin{aligned}&{\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},\\&{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}$$

Для каждого $i\in \{1,\,\ldots ,\,n\}$, итеративно, коэффициент $c_{i}$ корректируется в направлении $\partial f/\partial c_{i}$. Тогда результирующий вектор коэффициентов $(c_{1}',\,\ldots ,\,c_{n}')$ проецируется на ближайший вектор коэффициентов, удовлетворяющий заданным ограничениям. (Обычно используются евклидовы расстояния.) Затем процесс повторяется до тех пор, пока не будет получен почти оптимальный вектор коэффициентов. Полученный алгоритм на практике чрезвычайно быстр, хотя было доказано мало гарантий производительности.

Минимизация эмпирического риска

Описанная выше машина опорных векторов мягкой маржи является примером алгоритма минимизации эмпирического риска (ERM) для потерь шарнира . С этой точки зрения машины опорных векторов принадлежат к естественному классу алгоритмов статистического вывода, и многие из его уникальных особенностей обусловлены поведением потерь шарнира. Эта перспектива может дать дальнейшее понимание того, как и почему работают SVM, и позволит нам лучше анализировать их статистические свойства.

Минимизация рисков

При контролируемом обучении каждому дается набор обучающих примеров. $X_{1}\ldots X_{n}$ с этикетками $y_{1}\ldots y_{n}$и желает предсказать $y_{n+1}$ данный $X_{n+1}$. Для этого формируют гипотезу , $f$, такой, что $f(X_{n+1})$ является «хорошим» приближением $y_{n+1}$. «Хорошее» приближение обычно определяется с помощью функции потерь : $\ell (y,z)$, что характеризует, насколько плохо $z$ это как предсказание $y$. Затем мы хотели бы выбрать гипотезу, которая минимизирует ожидаемый риск :

$$\varepsilon (f)=\mathbb {E} \left[\ell (y_{n+1},f(X_{n+1}))\right].$$

В большинстве случаев мы не знаем совместного распределения $X_{n+1},\,y_{n+1}$ прямо. В этих случаях общей стратегией является выбор гипотезы, которая минимизирует эмпирический риск:

$${\hat {\varepsilon }}(f)={\frac {1}{n}}\sum _{k=1}^{n}\ell (y_{k},f(X_{k})).$$

При некоторых предположениях о последовательности случайных величин $X_{k},\,y_{k}$ (например, что они генерируются конечным марковским процессом), если набор рассматриваемых гипотез достаточно мал, минимизатор эмпирического риска будет близко приближаться к минимизатору ожидаемого риска как $n$ вырастает большим. Этот подход называется минимизацией эмпирического риска или ERM.

Регуляризация и стабильность

Чтобы задача минимизации имела четко определенное решение, мы должны наложить ограничения на множество ${\mathcal {H}}$ рассматриваемых гипотез. Если ${\mathcal {H}}$ является нормированным пространством (как и в случае с SVM), особенно эффективным методом является рассмотрение только тех гипотез, $f$ для чего $\lVert f\rVert _{\mathcal {H}}<k$ . Это эквивалентно наложению штрафа за регуляризацию. ${\mathcal {R}}(f)=\lambda _{k}\lVert f\rVert _{\mathcal {H}}$и решение новой задачи оптимизации

$${\hat {f}}=\mathrm {arg} \min _{f\in {\mathcal {H}}}{\hat {\varepsilon }}(f)+{\mathcal {R}}(f).$$

Этот подход называется регуляризацией Тихонова .

В более общем смысле, ${\mathcal {R}}(f)$ может быть некоторой мерой сложности гипотезы $f$, поэтому предпочтение отдается более простым гипотезам.

SVM и потеря шарнира

Напомним, что классификатор SVM (мягкая маржа) ${\hat {\mathbf {w} }},b:\mathbf {x} \mapsto \operatorname {sgn}({\hat {\mathbf {w} }}^{\mathsf {T}}\mathbf {x} -b)$ выбран так, чтобы минимизировать следующее выражение:

$$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.$$

В свете вышеизложенного мы видим, что метод SVM эквивалентен эмпирической минимизации риска с регуляризацией Тихонова, где в этом случае функцией потерь является шарнирная потеря

$$\ell (y,z)=\max \left(0,1-yz\right).$$

С этой точки зрения SVM тесно связан с другими фундаментальными алгоритмами классификации, такими как регуляризованный метод наименьших квадратов и логистическая регрессия . Разница между этими тремя заключается в выборе функции потерь: регуляризованный метод наименьших квадратов представляет собой эмпирическую минимизацию риска с квадратичными потерями , $\ell _{sq}(y,z)=(y-z)^{2}$; логистическая регрессия использует логарифм потерь ,

$$\ell _{\log }(y,z)=\ln(1+e^{-yz}).$$

Целевые функции

Разницу между шарнирными потерями и другими функциями потерь лучше всего выразить с точки зрения целевых функций — функции, которая минимизирует ожидаемый риск для данной пары случайных величин. $X,\,y$.

В частности, пусть $y_{x}$ обозначать $y$ при условии, что $X=x$. В настройке классификации мы имеем:

$$y_{x}={\begin{cases}1&{\text{with probability }}p_{x}\\-1&{\text{with probability }}1-p_{x}\end{cases}}$$

Таким образом, оптимальный классификатор:

$$f^{*}(x)={\begin{cases}1&{\text{if }}p_{x}\geq 1/2\\-1&{\text{otherwise}}\end{cases}}$$

Для квадрата потерь целевой функцией является функция условного ожидания, $f_{sq}(x)=\mathbb {E} \left[y_{x}\right]$; Для логистических потерь это функция логита, $f_{\log }(x)=\ln \left(p_{x}/({1-p_{x}})\right)$. Хотя обе эти целевые функции дают правильный классификатор, как $\operatorname {sgn}(f_{sq})=\operatorname {sgn}(f_{\log })=f^{*}$, они дают нам больше информации, чем нам нужно. Фактически, они дают нам достаточно информации, чтобы полностью описать распространение $y_{x}$.

С другой стороны, можно проверить, что целевая функция шарнирных потерь в точности равна $f^{*}$. Таким образом, в достаточно богатом пространстве гипотез (или, что то же самое, при правильно выбранном ядре) классификатор SVM будет сходиться к простейшей функции (в терминах ${\mathcal {R}}$), который правильно классифицирует данные. Это расширяет геометрическую интерпретацию SVM: для линейной классификации эмпирический риск минимизируется любой функцией, границы которой лежат между опорными векторами, и самым простым из них является классификатор максимальной маржи.

Характеристики

SVM принадлежат к семейству обобщенных линейных классификаторов и могут интерпретироваться как расширение перцептрона . Их также можно считать частным случаем тихоновской регуляризации . Особым свойством является то, что они одновременно минимизируют ошибку эмпирической классификации и максимизируют геометрическую границу ; следовательно, они также известны как классификаторы максимальной маржи .

Сравнение SVM с другими классификаторами было проведено Мейером, Лейшем и Хорником.

Выбор параметров

Эффективность SVM зависит от выбора ядра, параметров ядра и параметра мягкой маржи. $\lambda$.Распространенным выбором является ядро ​​Гаусса, которое имеет единственный параметр $\gamma$. Лучшее сочетание $\lambda$ и $\gamma$ часто выбирается путем поиска по сетке с экспоненциально растущими последовательностями $\lambda$ и $\gamma$, например, $\lambda \in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}$; $\gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}$. Обычно каждая комбинация выбранных параметров проверяется с помощью перекрестной проверки , и выбираются параметры с наилучшей точностью перекрестной проверки. Альтернативно, недавнюю работу по байесовской оптимизации. для выбора можно использовать $\lambda$ и $\gamma$ , часто требующий оценки гораздо меньшего количества комбинаций параметров, чем поиск по сетке. Окончательная модель, которая используется для тестирования и классификации новых данных, затем обучается на всей обучающей выборке с использованием выбранных параметров.

Проблемы

К потенциальным недостаткам SVM можно отнести следующие аспекты:

• Требуется полная маркировка входных данных.
• Некалиброванные вероятности членства в классе. SVM вытекает из теории Вапника, которая избегает оценки вероятностей на конечных данных.
• SVM напрямую применим только для задач двух классов. Следовательно, необходимо применять алгоритмы, которые сводят многоклассовую задачу к нескольким бинарным задачам; см. раздел многоклассовой SVM .
• Параметры решенной модели сложно интерпретировать.

Расширения

Мультиклассовая SVM

Мультиклассовая SVM направлена ​​на присвоение меток экземплярам с помощью машин опорных векторов, где метки рисуются из конечного набора из нескольких элементов.

Преобладающий подход для этого — свести одну задачу мультикласса к нескольким задачам двоичной классификации . Общие методы такого снижения включают:

• Построение бинарных классификаторов, различающих одну из меток от остальных ( один против всех ) или между каждой парой классов ( один против одного ). Классификация новых экземпляров для случая «один против всех» осуществляется с помощью стратегии «победитель получает все», при которой классификатор с функцией с наибольшим выходом назначает класс (важно, чтобы выходные функции были откалиброваны для получения сопоставимых оценок). ). При подходе «один против одного» классификация осуществляется с помощью стратегии голосования с максимальным выигрышем, при которой каждый классификатор присваивает экземпляр одному из двух классов, затем число голосов за назначенный класс увеличивается на один голос, и, наконец, число голосов за назначенный класс увеличивается на один голос. класс, набравший наибольшее количество голосов, определяет классификацию экземпляра.
• Ориентированный ациклический граф SVM (DAGSVM)
• Выходные коды с коррекцией ошибок

Краммер и Сингер предложили многоклассовый метод SVM, который объединяет проблему многоклассовой классификации в одну задачу оптимизации, а не разбивает ее на несколько задач двоичной классификации. См. также Ли, Лин и Вахба. и Ван ден Бург и Гроенен.

Трансдуктивные опорные векторные машины

Машины трансдуктивных опорных векторов расширяют SVM, поскольку они также могут обрабатывать частично помеченные данные в полуконтролируемом обучении , следуя принципам трансдукции . Здесь, помимо обучающего набора ${\mathcal {D}}$, обучаемому также дается набор

$${\mathcal {D}}^{\star }=\{\mathbf {x} _{i}^{\star }\mid \mathbf {x} _{i}^{\star }\in \mathbb {R} ^{p}\}_{i=1}^{k}$$

тестовых примеров, подлежащих классификации. Формально машина трансдуктивных опорных векторов определяется следующей основной задачей оптимизации:

Минимизировать (в $\mathbf {w} ,b,\mathbf {y} ^{\star }$)

$${\frac {1}{2}}\|\mathbf {w} \|^{2}$$

при условии (для любого $i=1,\dots ,n$ и любой $j=1,\dots ,k$)

$${\begin{aligned}&y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\\&y_{j}^{\star }(\mathbf {w} \cdot \mathbf {x} _{j}^{\star }-b)\geq 1,\end{aligned}}$$

и

$$y_{j}^{\star }\in \{-1,1\}.$$

Трансдуктивные машины опорных векторов были представлены Владимиром Н. Вапником в 1998 году.

Структурированная SVM

Основная статья: структурированная SVM

Структурированная машина опорных векторов является расширением традиционной модели SVM. В то время как модель SVM в первую очередь предназначена для двоичной классификации, мультиклассовой классификации и задач регрессии, структурированная SVM расширяет свое применение для обработки общих структурированных выходных меток, например деревьев синтаксического анализа, классификации с таксономиями, выравнивания последовательностей и многого другого.

Регрессия

Опорная векторная регрессия (прогнозирование) с различными порогами ε . По мере увеличения ε прогноз становится менее чувствительным к ошибкам.

Версия SVM для регрессии была предложена в 1996 году Владимиром Н. Вапником , Харрисом Друкером, Кристофером Дж. К. Берджесом, Линдой Кауфман и Александром Дж. Смолой. Этот метод называется регрессией опорного вектора (SVR). Модель, созданная с помощью классификации опорных векторов (как описано выше), зависит только от подмножества обучающих данных, поскольку функция стоимости построения модели не заботится о точках обучения, которые лежат за пределами поля. Аналогично, модель, созданная SVR, зависит только от подмножества обучающих данных, поскольку функция стоимости построения модели игнорирует любые обучающие данные, близкие к предсказанию модели. Другая версия SVM, известная как машина опорных векторов наименьших квадратов (LS-SVM), была предложена Суйкенсом и Вандевалле.

Обучение исходного SVR означает решение

минимизировать ${\tfrac {1}{2}}\|w\|^{2}$

при условии $|y_{i}-\langle w,x_{i}\rangle -b|\leq \varepsilon$

где $x_{i}$ это обучающая выборка с целевым значением $y_{i}$. Внутренний продукт плюс перехват $\langle w,x_{i}\rangle +b$ - это прогноз для этой выборки, и $\varepsilon$ — это свободный параметр, служащий порогом: все прогнозы должны находиться в пределах $\varepsilon$ диапазон истинных предсказаний. К вышесказанному обычно добавляются слабые переменные, чтобы учесть ошибки и обеспечить аппроксимацию в случае, если вышеуказанная проблема невозможна.

Байесовский SVM

В 2011 году Полсон и Скотт показали, что SVM допускает байесовскую интерпретацию посредством техники увеличения данных . В этом подходе SVM рассматривается как графическая модель (где параметры связаны через распределения вероятностей). Это расширенное представление позволяет применять к SVM байесовские методы, такие как гибкое моделирование функций, автоматическую настройку гиперпараметров и количественную оценку прогнозируемой неопределенности . была разработана масштабируемая версия байесовской SVM Недавно Флорианом Вензелем , позволяющая применять байесовские SVM к большим данным . Флориан Венцель разработал две разные версии: схему вариационного вывода (VI) для байесовской машины опорных векторов ядра (SVM) и стохастическую версию (SVI) для линейной байесовской SVM.

Выполнение

Параметры гиперплоскости с максимальным запасом определяются путем решения оптимизации. Существует несколько специализированных алгоритмов для быстрого решения задачи квадратичного программирования (QP), возникающей из SVM, которые в основном полагаются на эвристику для разбиения задачи на более мелкие и более управляемые части.

Другой подход заключается в использовании метода внутренней точки , который использует итерации типа Ньютона для поиска решения условий Каруша – Куна – Такера для основной и двойственной задач. Вместо решения последовательности разрозненных задач этот подход решает проблему целиком. Чтобы избежать решения линейной системы, включающей большую матрицу ядра, в трюке с ядром часто используется аппроксимация матрицы низкого ранга.

(SMO) Платта Другим распространенным методом является алгоритм последовательной минимальной оптимизации , который разбивает проблему на двумерные подзадачи, которые решаются аналитически, устраняя необходимость в алгоритме числовой оптимизации и хранении матриц. Этот алгоритм концептуально прост, его легко реализовать, он обычно быстрее и имеет лучшие свойства масштабирования для сложных задач SVM.

Особый случай линейных машин опорных векторов может быть решен более эффективно с помощью тех же алгоритмов, которые используются для оптимизации его близкого родственника, логистической регрессии ; этот класс алгоритмов включает субградиентный спуск (например, PEGASOS ) и координатный спуск (например, LIBLINEAR ). LIBLINEAR имеет несколько привлекательных свойств во время обучения. Каждая итерация сходимости занимает время, линейное по времени, необходимое для чтения данных поезда, и итерации также обладают свойством Q-линейной сходимости , что делает алгоритм чрезвычайно быстрым.

Общие SVM ядра также можно решить более эффективно, используя субградиентный спуск (например, P-packSVM ), особенно когда распараллеливание разрешено .

SVM ядра доступны во многих наборах инструментов машинного обучения, включая LIBSVM , MATLAB , SAS , SVMlight, kernlab , scikit-learn , Shogun , Weka , Shark , JKernelMachines , OpenCV и других.

Предварительная обработка данных (стандартизация) настоятельно рекомендуется для повышения точности классификации. Существует несколько методов стандартизации, таких как мин-макс, нормализация по десятичному масштабированию, Z-оценка. Для SVM обычно используется вычитание среднего значения и деление на дисперсию каждого признака.

См. также

• Адаптивное табулирование на месте
• Ядро машин
• Ядро Фишера
• Платтовское масштабирование
• Полиномиальное ядро
• Прогнозная аналитика
• Перспективы регуляризации машин опорных векторов
• Машина векторов релевантности — вероятностная модель с разреженным ядром, идентичная по функциональной форме SVM.
• Последовательная минимальная оптимизация
• Картографирование пространства
• Винноу (алгоритм)

Дальнейшее чтение

• Беннетт, Кристин П.; Кэмпбелл, Колин (2000). «Машины опорных векторов: шумиха или аллилуйя?» (PDF) . Исследования SIGKDD . 2 (2): 1–13. дои : 10.1145/380995.380999 . S2CID   207753020 .
• Кристианини, Нелло; Шоу-Тейлор, Джон (2000). Введение в машины опорных векторов и другие методы обучения на основе ядра . Издательство Кембриджского университета. ISBN  0-521-78019-5 .
• Фрадкин, Дмитрий; Мучник, Илья (2006). «Машины опорных векторов для классификации» (PDF) . В Абелло, Дж.; Кармод, Г. (ред.). Дискретные методы в эпидемиологии . Серия DIMACS по дискретной математике и теоретической информатике. Том. 70. стр. 13–20.
• Иоахимс, Торстен (1998). «Категоризация текста с помощью машин опорных векторов: обучение со многими соответствующими функциями». В Неделлеке, Клэр; Рувейроль, Селин (ред.). «Машинное обучение: ECML-98 . Конспекты лекций по информатике. Том 1398. Берлин, Гейдельберг: Springer. стр. 137-142. doi : 10.1007/BFb0026683 . ISBN  978-3-540-64417-0 . S2CID   2427083 .
• Иванчук, Овидиу (2007). «Применение машин опорных векторов в химии» (PDF) . Обзоры по вычислительной химии . 23 : 291–400. дои : 10.1002/9780470116449.ch6 . ISBN  9780470116449 .
• Джеймс, Гарет; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2013). «Машины опорных векторов» (PDF) . Введение в статистическое обучение: с приложениями на R. Нью-Йорк: Спрингер. стр. 337–372. ISBN  978-1-4614-7137-0 .
• Шёлкопф, Бернхард; Смола, Александр Дж. (2002). Обучение с помощью ядер . Кембридж, Массачусетс: MIT Press. ISBN  0-262-19475-9 .
• Стейнварт, Инго; Кристманн, Андреас (2008). Машины опорных векторов . Нью-Йорк: Спрингер. ISBN  978-0-387-77241-7 .
• Теодоридис, Сергий; Кутрумбас, Константинос (2009). Распознавание образов (4-е изд.). Академическая пресса. ISBN  978-1-59749-272-0 .

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

• libsvm , LIBSVM — популярная библиотека среди изучающих SVM.
• liblinear — библиотека для большой линейной классификации, включая некоторые SVM.
• SVM Light — это набор программных инструментов для обучения и классификации с использованием SVM.
• Живая демонстрация SVMJS. Архивировано 5 мая 2013 г. на Wayback Machine. Это демонстрация графического интерфейса для JavaScript . реализации SVM на