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

Набор методов контролируемого статистического обучения

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

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

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

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

Мотивация

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

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

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

Ядро машины

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

Приложения

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

• SVM полезны при категоризации текста и гипертекста , поскольку их применение может значительно снизить потребность в помеченных обучающих примерах как в стандартных индуктивных, так и в трансдуктивных настройках. ^[7] Некоторые методы поверхностного семантического анализа основаны на машинах опорных векторов. ^[8]
• Классификацию изображений также можно выполнить с помощью SVM. Результаты экспериментов показывают, что SVM достигают значительно более высокой точности поиска, чем традиционные схемы уточнения запроса, уже после трех-четырех раундов обратной связи по релевантности. Это также верно для систем сегментации изображений , в том числе использующих модифицированную версию SVM, использующую привилегированный подход, предложенный Вапником. ^{[9] [10]}
• Классификация спутниковых данных, таких как данные SAR , с использованием контролируемого SVM. ^[11]
• Рукописные символы можно распознать с помощью SVM. ^{[12] [13]}
• Алгоритм SVM широко применяется в биологических и других науках. Они использовались для классификации белков, при этом до 90% соединений были классифицированы правильно. Тесты перестановок , основанные на весах SVM, были предложены в качестве механизма интерпретации моделей SVM. ^{[14] [15]} Машинные веса опорных векторов также использовались для интерпретации моделей SVM в прошлом. ^[16] Постфокальная интерпретация машинных моделей опорных векторов с целью выявления особенностей, используемых моделью для прогнозирования, является относительно новой областью исследований, имеющей особое значение в биологических науках.

История

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

Линейная СВМ

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

Комментарий: показанный график неверен! Поверните все содержимое графика на 90 градусов по часовой стрелке и переверните w так, чтобы оно указывало внутрь.

Нам дан обучающий набор данных точек вида ${\displaystyle n}$

$${\displaystyle (\mathbf {x} _{1},y_{1}),\ldots ,(\mathbf {x} _{n},y_{n}),}$$

действительный ${\displaystyle y_{i}}$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle p}$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle y_{i}=1}$ ${\displaystyle y_{i}=-1}$ ${\displaystyle \mathbf {x} _{i}}$

Любую гиперплоскость можно записать как набор точек, удовлетворяющих ${\displaystyle \mathbf {x} }$

$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=0,}$$

вектор нормалинормальную форму Гессе ${\displaystyle \mathbf {w} }$ ${\displaystyle \mathbf {w} }$ ${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$ ${\displaystyle \mathbf {w} }$

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

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

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

и

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

Геометрически расстояние между этими двумя гиперплоскостями равно , ^[17], поэтому, чтобы максимизировать расстояние между плоскостями, мы хотим минимизировать . Расстояние вычисляется с использованием уравнения расстояния от точки до плоскости . Нам также необходимо предотвратить попадание точек данных в пределы поля. Мы добавляем следующее ограничение: для каждого либо ${\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}}$ ${\displaystyle \|\mathbf {w} \|}$ ${\displaystyle i}$

$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\geq 1\,,{\text{ if }}y_{i}=1,}$$

$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\leq -1\,,{\text{ if }}y_{i}=-1.}$$

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

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

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

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

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

Мягкая маржа

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

$${\displaystyle \max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right).}$$

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

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

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

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

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

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

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

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

Ядро машины

Оригинальный алгоритм гиперплоскости с максимальным запасом, предложенный Вапником в 1963 году, построил линейный классификатор . Однако в 1992 году Бернхард Бозер, Изабель Гийон и Владимир Вапник предложили способ создания нелинейных классификаторов путем применения трюка с ядром (первоначально предложенного Айзерманом и др. ^[18] ) к гиперплоскостям с максимальным запасом. ^[5] Полученный алгоритм формально аналогичен, за исключением того, что каждое скалярное произведение ^{[ требуется дальнейшее объяснение ]} заменяется нелинейной функцией ядра . ^{[ требуется дальнейшее объяснение ]} Это позволяет алгоритму вписать гиперплоскость с максимальным запасом в преобразованное пространство признаков . Преобразование может быть нелинейным, а преобразованное пространство — многомерным; хотя классификатор представляет собой гиперплоскость в преобразованном пространстве признаков, он может быть нелинейным в исходном входном пространстве.

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

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

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

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

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

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

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

Первобытный

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

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

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

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

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

Двойной

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

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

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

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

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

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

Смещение , можно восстановить, найдя на границе поля и решив ${\displaystyle b}$ ${\displaystyle \mathbf {x} _{i}}$

$${\displaystyle y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-y_{i}.}$$

(Обратите внимание, поскольку .) ${\displaystyle y_{i}^{-1}=y_{i}}$ ${\displaystyle y_{i}=\pm 1}$

Трюк с ядром

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

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

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

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

где получены в результате решения оптимизационной задачи ${\displaystyle c_{i}}$

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

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

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

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

$${\displaystyle \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 работают непосредственно с выражением

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$${\displaystyle \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 эквивалентен эмпирической минимизации риска с регуляризацией Тихонова, где в этом случае функция потерь представляет собой шарнирную потерю

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы

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

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

Расширения

Поддержка векторной кластеризации (SVC)

SVC — аналогичный метод, который также основан на функциях ядра, но подходит для обучения без учителя. ^{[ нужна цитата ]}

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

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

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

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

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

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

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

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

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

Свернуть (в ) ${\displaystyle \mathbf {w} ,b,\mathbf {y} ^{\star }}$

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

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

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

и

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

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

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

SVM были обобщены до структурированных SVM , где пространство меток структурировано и, возможно, имеет бесконечный размер.

Регрессия

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

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

Обучение оригинального СВР означает решение ^[36]

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

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

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

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

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

Выполнение

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

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

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

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

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

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

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

Смотрите также

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

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

1. Кортес, Коринна ; Вапник, Владимир (1995). «Сети опорных векторов» (PDF) . Машинное обучение . 20 (3): 273–297. CiteSeerX  10.1.1.15.9362 . дои : 10.1007/BF00994018 . S2CID  206787478.
2. Бен-Гур, Аса; Хорн, Дэвид; Зигельманн, Хава; Вапник Владимир Николаевич».«Кластеризация опорных векторов» (2001);». Журнал исследований машинного обучения . 2 : 125–137.
3. «1.4. Машины опорных векторов — документация scikit-learn 0.20.2» . Архивировано из оригинала 08.11.2017 . Проверено 8 ноября 2017 г.
4. Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2008). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование (PDF) (второе изд.). Нью-Йорк: Спрингер. п. 134.
5. Boser, Бернхард Э.; Гийон, Изабель М.; Вапник, Владимир Н. (1992). «Алгоритм обучения оптимальных классификаторов маржи». Материалы пятого ежегодного семинара по теории вычислительного обучения – COLT '92 . п. 144. CiteSeerX 10.1.1.21.3818 . дои : 10.1145/130385.130401. ISBN  978-0897914970. S2CID  207165665.
6. Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. (2007). «Раздел 16.5. Машины опорных векторов». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8. Архивировано из оригинала 11 августа 2011 г.
7. Иоахимс, Торстен (1998). «Категоризация текста с помощью машин опорных векторов: обучение со многими соответствующими функциями». Машинное обучение: ECML-98 . Конспекты лекций по информатике. Том. 1398. Спрингер. стр. 137–142. дои : 10.1007/BFb0026683 . ISBN 978-3-540-64417-0.
8. Прадхан, Самир С.; и другие. (2 мая 2004 г.). Неглубокий семантический анализ с использованием машин опорных векторов. Материалы конференции по технологиям человеческого языка Североамериканского отделения Ассоциации компьютерной лингвистики: HLT-NAACL 2004. Ассоциация компьютерной лингвистики. стр. 233–240.
9. Вапник, Владимир Н.: Приглашенный докладчик. ИПМУ «Обработка информации и управление», 2014).
10. Баргут, Лорен (2015). «Гранули пространственно-таксоновой информации, используемые при итеративном принятии нечетких решений для сегментации изображений» (PDF) . Гранулярные вычисления и принятие решений . Исследования в области больших данных. Том. 10. С. 285–318. дои : 10.1007/978-3-319-16829-6_12. ISBN 978-3-319-16828-9. S2CID  4154772. Архивировано из оригинала (PDF) 8 января 2018 г. Проверено 8 января 2018 г.
11. А. Майти (2016). «Контролируемая классификация поляриметрических данных RADARSAT-2 для различных объектов суши». arXiv : 1608.00501 [cs.CV].
12. ДеКосте, Деннис (2002). «Обучение машин инвариантных опорных векторов» (PDF) . Машинное обучение . 46 : 161–190. дои : 10.1023/А:1012454411458 . S2CID  85843.
13. Майтра, Д.С.; Бхаттачарья, У.; Паруи, СК (август 2015 г.). «Общий подход на основе CNN к распознаванию рукописных символов в нескольких сценариях». 2015 13-я Международная конференция по анализу и распознаванию документов (ICDAR) . стр. 1021–1025. дои : 10.1109/ICDAR.2015.7333916. ISBN 978-1-4799-1805-8. S2CID  25739012.
14. Гаонкар, Б.; Давацикос, К. (2013). «Аналитическая оценка карт статистической значимости для машинного многомерного анализа и классификации изображений на основе опорных векторов». НейроИмидж . 78 : 270–283. doi :10.1016/j.neuroimage.2013.03.066. ПМЦ 3767485 . ПМИД  23583748. 
15. Куэнье, Реми; Россо, Шарлотта; Чупен, Мари; Леэриси, Стефан; Дормон, Дидье; Бенали, Хабиб; Самсон, Ив; Коллио, Оливье (2011). «Пространственная регуляризация SVM для обнаружения диффузных изменений, связанных с исходом инсульта» (PDF) . Анализ медицинских изображений . 15 (5): 729–737. дои : 10.1016/j.media.2011.05.007. PMID  21752695. Архивировано из оригинала (PDF) 22 декабря 2018 г. Проверено 8 января 2018 г.
16. Статников, Александр; Хардин, Дуглас; И Алиферис, Константин; (2006); «Использование весовых методов SVM для выявления причинно-значимых и непричинно-значимых переменных», Sign , 1, 4.
17. "Почему запас SVM равен 2 ‖ w ‖ {\displaystyle {\frac {2}{\|\mathbf {w} \|}}} ". Математический обмен стеками . 30 мая 2015 г.
18. Айзерман, Марк А.; Браверман, Эммануэль М. и Розоноер, Лев И. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и дистанционное управление . 25 : 821–837.
19. Джин, Чи; Ван, Ливэй (2012). Зависящая от размерности граница PAC-Bayes. Достижения в области нейронных систем обработки информации. CiteSeerX 10.1.1.420.3487 . Архивировано из оригинала 02 апреля 2015 г. 
20. Шалев-Шварц, Шай; Певец Йорам; Сребро, Натан; Коттер, Эндрю (16 октября 2010 г.). «Pegasos: первичный расчетный решатель субградиентов для SVM». Математическое программирование . 127 (1): 3–30. CiteSeerX 10.1.1.161.9629 . дои : 10.1007/s10107-010-0420-4. ISSN  0025-5610. S2CID  53306004. 
21. Се, Чо-Джуй; Чанг, Кай-Вэй; Лин, Чи-Джен; Кирти, С. Сатья; Сундарараджан, С. (1 января 2008 г.). «Метод спуска по двойным координатам для крупномасштабной линейной SVM». Материалы 25-й международной конференции по машинному обучению ICML '08 . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 408–415. CiteSeerX 10.1.1.149.5594 . дои : 10.1145/1390156.1390208. ISBN  978-1-60558-205-4. S2CID  7880266.
22. Росаско, Лоренцо; Де Вито, Эрнесто; Капоннетто, Андреа; Пиана, Мишель; Верри, Алессандро (1 мая 2004 г.). «Все ли функции потерь одинаковы?». Нейронные вычисления . 16 (5): 1063–1076. CiteSeerX 10.1.1.109.6786 . дои : 10.1162/089976604773135104. ISSN  0899-7667. PMID  15070510. S2CID  11845688. 
23. Мейер, Дэвид; Лейш, Фридрих; Хорник, Курт (сентябрь 2003 г.). «Тестируемая машина опорных векторов». Нейрокомпьютинг . 55 (1–2): 169–186. дои : 10.1016/S0925-2312(03)00431-4.
24. Сюй, Чи-Вэй; Чанг, Чи-Чунг и Лин, Чи-Джен (2003). Практическое руководство по классификации опорных векторов (PDF) (технический отчет). Департамент компьютерных наук и информационной инженерии, Национальный Тайваньский университет. Архивировано (PDF) из оригинала 25 июня 2013 г.
25. Дуан, Кай-Бо; Кирти, С. Сатья (2005). «Какой многоклассовый метод SVM лучше всего? Эмпирическое исследование» (PDF) . Множественные системы классификаторов . ЛНКС . Том. 3541. стр. 278–285. CiteSeerX 10.1.1.110.6789 . дои : 10.1007/11494683_28. ISBN  978-3-540-26306-7. Архивировано из оригинала (PDF) 3 мая 2013 г. Проверено 18 июля 2019 г.
26. Сюй, Чи-Вэй и Линь, Чи-Джен (2002). «Сравнение методов для многоклассовых машин опорных векторов» (PDF) . Транзакции IEEE в нейронных сетях . 13 (2): 415–25. дои : 10.1109/72.991427. PMID  18244442. Архивировано из оригинала (PDF) 3 мая 2013 г. Проверено 8 января 2018 г.
27. Платт, Джон; Кристианини, Нелло ; Шоу-Тейлор, Джон (2000). «Группы DAG с большой маржой для многоклассовой классификации» (PDF) . В Солле, Сара А .; Лин, Тодд К.; Мюллер, Клаус-Роберт (ред.). Достижения в области нейронных систем обработки информации . МТИ Пресс. стр. 547–553. Архивировано (PDF) из оригинала 16 июня 2012 г.
28. Дитерих, Томас Г.; Бакири, Гулум (1995). «Решение задач многоклассового обучения с помощью выходных кодов с коррекцией ошибок» (PDF) . Журнал исследований искусственного интеллекта . 2 : 263–286. arXiv : cs/9501101 . Бибкод : 1995cs........1101D. дои : 10.1613/jair.105. S2CID  47109072. Архивировано (PDF) из оригинала 9 мая 2013 г.
29. Краммер, Коби и Сингер, Йорам (2001). «Об алгоритмической реализации многоклассовых векторных машин на основе ядра» (PDF) . Журнал исследований машинного обучения . 2 : 265–292. Архивировано (PDF) из оригинала 29 августа 2015 г.
30. Ли, Юнкён; Лин, Йи и Вахба, Грейс (2001). «Многокатегорийные машины опорных векторов» (PDF) . Информатика и статистика . 33 . Архивировано (PDF) из оригинала 17 июня 2013 г.
31. Ли, Юнкён; Лин, Йи; Вахба, Грейс (2004). «Многокатегорийные машины опорных векторов». Журнал Американской статистической ассоциации . 99 (465): 67–81. CiteSeerX 10.1.1.22.1879 . дои : 10.1198/016214504000000098. S2CID  7066611. 
32. Ван ден Бург, Геррит Дж. Дж. и Гроенен, Патрик Дж. Ф. (2016). «GenSVM: обобщенная многоклассовая машина опорных векторов» (PDF) . Журнал исследований машинного обучения . 17 (224): 1–42.
33. Иоахимс, Торстен. Трансдуктивный вывод для классификации текста с использованием машин опорных векторов (PDF) . Материалы Международной конференции по машинному обучению 1999 г. (ICML 1999). стр. 200–209.
34. Друкер, Харрис; Берджес, Боже. С.; Кауфман, Линда; Смола, Александр Дж.; и Вапник, Владимир Н. (1997); «Машины регрессии опорных векторов», в журнале «Достижения в области нейронных систем обработки информации» 9, NIPS 1996 , 155–161, MIT Press.
35. Суйкенс, Йохан АК; Вандевалле, Йоос П.Л.; «Метод наименьших квадратов поддерживает векторные машинные классификаторы», Neural Processing Letters , vol. 9, нет. 3 июня 1999 г., стр. 293–300.
36. Смола, Алекс Дж.; Шёлкопф, Бернхард (2004). «Учебное пособие по регрессии опорных векторов» (PDF) . Статистика и вычисления . 14 (3): 199–222. CiteSeerX 10.1.1.41.1452 . doi :10.1023/B:STCO.0000035301.49549.88. S2CID  15475. Архивировано (PDF) из оригинала 31 января 2012 г. 
37. Полсон, Николас Г.; Скотт, Стивен Л. (2011). «Увеличение данных для машин опорных векторов». Байесовский анализ . 6 (1): 1–23. дои : 10.1214/11-BA601 .
38. Венцель, Флориан; Гали-Фажу, Тео; Дойч, Маттеус; Клофт, Мариус (2017). «Байесовские нелинейные машины опорных векторов для больших данных». Машинное обучение и обнаружение знаний в базах данных . Конспекты лекций по информатике. Том. 10534. стр. 307–322. arXiv : 1707.05532 . Бибкод : 2017arXiv170705532W. дои : 10.1007/978-3-319-71249-9_19. ISBN 978-3-319-71248-2. S2CID  4018290.
39. Флориан Венцель; Маттеус Дойч; Тео Гали-Фажу; Мариус Клофт; «Масштабируемый приближенный вывод для байесовской нелинейной машины опорных векторов»
40. Феррис, Майкл С.; Мансон, Тодд С. (2002). «Методы внутренней точки для машин с массивными опорными векторами» (PDF) . SIAM Journal по оптимизации . 13 (3): 783–804. CiteSeerX 10.1.1.216.6893 . дои : 10.1137/S1052623400374379. S2CID  13563302. Архивировано (PDF) из оригинала 4 декабря 2008 г. 
41. Платт, Джон К. (1998). Последовательная минимальная оптимизация: быстрый алгоритм обучения машин опорных векторов (PDF) . НИПС. Архивировано (PDF) из оригинала 02 июля 2015 г.
42. Шалев-Шварц, Шай; Певец Йорам; Сребро, Натан (2007). Pegasos: Primal Estimated SubGrAdient SOLver для SVM (PDF) . ИКМЛ. Архивировано (PDF) из оригинала 15 декабря 2013 г.
43. Фан, Ронг-Эн; Чанг, Кай-Вэй; Се, Чо-Джуи; Ван, Сян-Жуй; Линь, Чи-Джен (2008). «LIBLINEAR: библиотека для большой линейной классификации» (PDF) . Журнал исследований машинного обучения . 9 : 1871–1874.
44. Аллен Чжу, Цзэюань; Чен, Вэйчжу; Ван, Банда; Чжу, Чэньгуан; Чен, Чжэн (2009). P-packSVM: SVM параллельного первичного градиента ядра (PDF) . ИКДМ. Архивировано (PDF) из оригинала 7 апреля 2014 г.
45. Фан, Ронг-Эн; Чанг, Кай-Вэй; Се, Чо-Джуи; Ван, Сян-Жуй; Линь, Чи-Джен (2008). «LIBLINEAR: библиотека для большой линейной классификации». Журнал исследований машинного обучения . 9 (августа): 1871–1874 гг.
46. Мохамад, Исмаил; Усман, Дауда (1 сентября 2013 г.). «Стандартизация и ее влияние на алгоритм кластеризации K-средних». Научно-исследовательский журнал прикладных наук, техники и технологий . 6 (17): 3299–3303. дои : 10.19026/rjaset.6.3638 .
47. Феннелл, Питер; Цзо, Жия; Лерман, Кристина (01 декабря 2019 г.). «Прогнозирование и объяснение поведенческих данных с помощью структурированной декомпозиции пространства признаков». EPJ Наука о данных . 8 . arXiv : 1810.09841 . дои : 10.1140/epjds/s13688-019-0201-0 .

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

• Беннетт, Кристин П.; Кэмпбелл, Колин (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 . Это демонстрация графического интерфейса для реализации SVM на JavaScript .