Машина опорных векторов - Support vector machine

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

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

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

Мотивация

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

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

Определение

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

Машина ядра

В то время как исходная проблема может быть сформулирована в конечномерном пространстве, часто бывает, что множества для различения не линейно отделимый в этом пространстве. По этой причине было предложено^{[кем? ]} чтобы исходное конечномерное пространство было отображено в гораздо более многомерное пространство, что, вероятно, облегчило разделение в этом пространстве. Чтобы поддерживать разумную вычислительную нагрузку, отображения, используемые схемами SVM, предназначены для обеспечения того, чтобы точечные продукты пар векторов входных данных можно легко вычислить в терминах переменных в исходном пространстве, определяя их в терминах функция ядра ${\displaystyle k(x,y)}$ выбран в соответствии с проблемой.^[5] Гиперплоскости в многомерном пространстве определяются как набор точек, скалярное произведение которых с вектором в этом пространстве является постоянным, где такой набор векторов является ортогональным (и, следовательно, минимальным) набором векторов, который определяет гиперплоскость. Векторы, определяющие гиперплоскости, могут быть выбраны как линейные комбинации с параметрами ${\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 полезны в категоризация текста и гипертекста, поскольку их применение может значительно снизить потребность в помеченных обучающих примерах как в стандартном индуктивном, так и в трансдуктивный настройки.^[6] Некоторые методы для неглубокий семантический анализ основаны на машинах опорных векторов.^[7]
• Классификация изображений также может выполняться с использованием SVM. Экспериментальные результаты показывают, что SVM достигают значительно более высокой точности поиска, чем традиционные схемы уточнения запросов, всего после трех-четырех раундов обратной связи по релевантности. Это также верно для сегментация изображений системы, в том числе те, которые используют модифицированную версию SVM, которая использует привилегированный подход, предложенный Vapnik.^[8][9]
• Классификация спутниковых данных по типу SAR данные с использованием управляемой SVM.^[10]
• Рукописные символы могут быть признанный используя SVM.^[11][12]
• Алгоритм SVM широко применяется в биологических и других науках. Они использовались для классификации белков до 90% правильно классифицированных соединений. Перестановочные тесты основанные на весах SVM были предложены в качестве механизма интерпретации моделей SVM.^[13][14] Машинные веса опорных векторов также использовались для интерпретации моделей SVM в прошлом.^[15] Постфактумная интерпретация машинных моделей опорных векторов с целью выявления функций, используемых моделью для прогнозирования, является относительно новой областью исследований, имеющей особое значение в биологических науках.

История

Оригинальный алгоритм SVM был изобретен Владимир Николаевич Вапник и Алексей Я. Червоненкис в 1963 году. В 1992 году Бернхард Бозер, Изабель Гийон и Владимир Вапник предложил способ создания нелинейных классификаторов, применяя трюк с ядром до гиперплоскостей с максимальным запасом.^[16] Действующий стандарт^{[согласно кому? ]} воплощение (soft margin) было предложено Коринна Кортес и Vapnik в 1993 г. и опубликованы в 1995 г.^[1]

Линейный SVM

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

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

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

где ${\displaystyle y_{i}}$ равны 1 или −1, каждый из которых указывает класс, к которому точка ${\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} ^{T}\mathbf {x} -b=0,}$

куда ${\displaystyle \mathbf {w} }$ является (не обязательно нормализованным) нормальный вектор в гиперплоскость. Это очень похоже на Нормальная форма Гессена, Кроме этого ${\displaystyle \mathbf {w} }$ не обязательно является единичным вектором. Параметр ${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$ определяет смещение гиперплоскости от начала координат вдоль вектора нормали ${\displaystyle \mathbf {w} }$.

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

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

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

и

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

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

${\displaystyle \mathbf {w} ^{T}\mathbf {x} _{i}-b\geq 1}$, если ${\displaystyle y_{i}=1}$,

или же

${\displaystyle \mathbf {w} ^{T}\mathbf {x} _{i}-b\leq -1}$, если ${\displaystyle y_{i}=-1}$.

Эти ограничения гласят, что каждая точка данных должна лежать на правильной стороне поля.

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

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

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

"Свести к минимуму ${\displaystyle \|\mathbf {w} \|}$ при условии ${\displaystyle y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1}$ за ${\displaystyle i=1,\ldots ,n}$."

В ${\displaystyle \mathbf {w} }$ и ${\displaystyle b}$ которые решают эту проблему, определяют наш классификатор, ${\displaystyle \mathbf {x} \mapsto \operatorname {sgn}(\mathbf {w} ^{T}\mathbf {x} -b)}$ куда ${\displaystyle \operatorname {sgn}(\cdot )}$ это функция знака.

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

Мягкая маржа

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

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

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

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

Таким образом, цель оптимизации - минимизировать

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

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

Нелинейная классификация

Машина ядра

Первоначальный алгоритм гиперплоскости с максимальным запасом, предложенный Вапником в 1963 году, построил линейный классификатор. Однако в 1992 г. Бернхард Бозер, Изабель Гийон и Владимир Вапник предложил способ создания нелинейных классификаторов, применяя трюк с ядром (первоначально предложено Aizerman et al.^[18]) до гиперплоскостей с максимальным запасом.^[16] Результирующий алгоритм формально аналогичен, за исключением того, что каждый скалярное произведение заменяется нелинейным ядро функция. Это позволяет алгоритму соответствовать гиперплоскости с максимальным запасом в преобразованном пространство функций. Преобразование может быть нелинейным, а преобразованное пространство - многомерным; Хотя классификатор является гиперплоскостью в преобразованном пространстве признаков, он может быть нелинейным в исходном пространстве ввода.

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

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

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

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

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

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

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

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

Изначальный

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

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

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

${\displaystyle {\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|\mathbf {w} \|^{2}}$

${\displaystyle {\text{subject to }}y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{for all }}i.}$

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

Двойной

Решая для Лагранжев двойственный из указанной выше задачи получается упрощенная задача

${\displaystyle {\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}^{T}\mathbf {x} _{j})y_{j}c_{j},}$

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

Это называется двойной проблема. Поскольку двойственная задача максимизации является квадратичной функцией ${\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} ^{T}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{T}\mathbf {x} _{i}-y_{i}.}$

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

Уловка ядра

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

Предположим теперь, что мы хотели бы изучить правило нелинейной классификации, которое соответствует правилу линейной классификации для преобразованных точек данных. ${\displaystyle \varphi ({\vec {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}\\\end{aligned}}}$

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

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

${\displaystyle {\begin{aligned}b=\mathbf {w} ^{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} ^{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} ^{T}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.}$

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

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

Координатный спуск алгоритмы работы SVM из двойной задачи

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

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

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

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

Описанный выше вектор поддержки с мягким запасом является примером минимизация эмпирического риска (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})).}$

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

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

Чтобы задача минимизации имела четко определенное решение, мы должны наложить ограничения на множество ${\displaystyle {\mathcal {H}}}$ рассматриваемых гипотез. Если ${\displaystyle {\mathcal {H}}}$ это нормированное пространство (как и в случае с SVM), особенно эффективным методом является рассмотрение только этих гипотез. ${\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 (soft-margin) ${\displaystyle {\hat {\mathbf {w} }},b:\mathbf {x} \mapsto \operatorname {sgn}({\hat {\mathbf {w} }}^{T}\mathbf {x} -b)}$ выбрано, чтобы минимизировать следующее выражение:

${\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{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}}$.

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

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

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

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

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

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

вопросы

Возможные недостатки SVM включают следующие аспекты:

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

Расширения

Кластеризация опорных векторов (SVC)

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\geq 1,}$

${\displaystyle y_{j}^{\star }({\vec {w}}\cdot {\vec {x_{j}^{\star }}}-b)\geq 1,}$

и

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

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

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

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

Регресс

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

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

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

свести к минимуму ${\displaystyle {\frac {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 }$ диапазон верных предсказаний. Переменные Slack обычно добавляются в приведенное выше, чтобы учесть ошибки и позволить приближение в случае, если указанная выше проблема невозможна.

Байесовский 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, Сёгун, Weka, Акула, JKernelMachines, OpenCV и другие.

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

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

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

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". В архиве из оригинала на 2017-11-08. Получено 2017-11-08.
4. Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2008). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование (PDF) (Второе изд.). Нью-Йорк: Спрингер. п. 134.
5. Press, William H .; Teukolsky, Saul A .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (2007). «Раздел 16.5. Машины опорных векторов». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8. В архиве из оригинала 11.08.2011.
6. Иоахимс, Торстен (1998). «Категоризация текста с помощью машин опорных векторов: обучение с множеством важных функций». Машинное обучение: ECML-98. Конспект лекций по информатике. Springer. 1398: 137–142. Дои:10.1007 / BFb0026683. ISBN  978-3-540-64417-0.
7. Прадхан, Самир С. и др. "Неглубокий семантический анализ с использованием машин опорных векторов. "Труды конференции по технологиям человеческого языка Североамериканского отделения Ассоциации компьютерной лингвистики: HLT-NAACL 2004. 2004.
8. Вапник Владимир Н .: Приглашенный спикер. Обработка информации и управление ИПМУ 2014).
9. Баргоут, Лорен. "Гранулы информации о пространственных таксонах, используемые в итеративном нечетком процессе принятия решений для сегментации изображений ". Гранулярные вычисления и принятие решений. Springer International Publishing, 2015. 285–318.
10. А. Мэйти (2016). «Контролируемая классификация поляриметрических данных RADARSAT-2 для различных особенностей суши». arXiv:1608.00501 [cs.CV ].
11. ДеКост, Деннис (2002). "Обучение инвариантных опорных векторных машин" (PDF). Машинное обучение. 46: 161–190. Дои:10.1023 / А: 1012454411458. S2CID  85843.
12. Maitra, D. S .; Bhattacharya, U .; Паруи, С. К. (август 2015 г.). «Общий подход на основе CNN к распознаванию рукописных символов нескольких сценариев». 2015 13-я Международная конференция по анализу и распознаванию документов (ICDAR): 1021–1025. Дои:10.1109 / ICDAR.2015.7333916.
13. Гаонкар, Билвадж; Давацикос, Христос; «Аналитическая оценка карт статистической значимости для многомерного анализа и классификации изображений на основе опорных векторов».
14. Куингне, Реми; Россо, Шарлотта; Чупин, Мари; Лехериси, Стефан; Дормон, Дидье; Бенали, Хабиб; Самсон, Ив; и Коллио, Оливье; «Пространственная регуляризация SVM для обнаружения диффузных изменений, связанных с исходом инсульта», Анализ медицинских изображений, 2011, 15 (5): 729–737.
15. Статников, Александр; Хардин, Дуглас; И Алиферис, Константин; (2006); «Использование весовых методов SVM для выявления причинно-значимых и не связанных с причинно-следственной связью переменных», Знак, 1, 4.
16. Boser, Bernhard E .; Guyon, Isabelle M .; Вапник, Владимир Н. (1992). «Алгоритм обучения оптимальных классификаторов маржи». Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92. п. 144. CiteSeerX  10.1.1.21.3818. Дои:10.1145/130385.130401. ISBN  978-0897914970. S2CID  207165665.
17. "Почему маржа SVM равна ${\displaystyle {\frac {2}{\|\mathbf {w} \|}}}$". Обмен стеками математики. 30 мая 2015 года.
18. Aizerman, Mark A .; Браверман, Эммануэль М. и Розоноэр, Лев I. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и дистанционное управление. 25: 821–837.
19. Джин, Чи; Ван, Ливэй (2012). Граница маржи PAC-Байеса, зависящая от размерности. Достижения в системах обработки нейронной информации. CiteSeerX  10.1.1.420.3487. В архиве из оригинала от 02.04.2015.
20. Шалев-Шварц, Шай; Певец Йорам; Сребро, Натан; Коттер, Эндрю (16.10.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. Се, Чо-Джуй; Чанг, Кай-Вэй; Линь, Чи-Джен; Кирти, С. Сатья; Сундарараджан, С. (01.01.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. Росаско, Лоренцо; Де Вито, Эрнесто; Капоннетто, Андреа; Пиана, Микеле; Верри, Алессандро (2004-05-01). «Все ли функции потерь одинаковы?». Нейронные вычисления. 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.06.2013.
25. Дуань, Кай-Бо; Кирти, С. Сатья (2005). «Какой метод мультиклассовой SVM является лучшим? Эмпирическое исследование» (PDF). Системы с несколькими классификаторами. LNCS. 3541. С. 278–285. CiteSeerX  10.1.1.110.6789. Дои:10.1007/11494683_28. ISBN  978-3-540-26306-7.
26. Сюй, Чжи-Вэй и Линь, Чжи-Джен (2002). «Сравнение методов для мультиклассовых машин опорных векторов» (PDF). IEEE-транзакции в нейронных сетях. 13 (2): 415–25. Дои:10.1109/72.991427. PMID  18244442.
27. Платт, Джон; Кристианини, Нелло; Шоу-Тейлор, Джон (2000). «Группы DAG с большим запасом для мультиклассовой классификации» (PDF). В Solla, Sara A .; Лин, Тодд К .; Мюллер, Клаус-Роберт (ред.). Достижения в системах обработки нейронной информации. MIT Press. С. 547–553. В архиве (PDF) из оригинала от 16.06.2012.
28. Dietterich, Thomas G .; Бакири, Гулум (1995). «Решение проблем многоклассового обучения с помощью кодов вывода с исправлением ошибок» (PDF). Журнал исследований искусственного интеллекта. 2: 263–286. arXiv:cs / 9501101. Bibcode:1995cs ........ 1101D. Дои:10.1613 / jair.105. S2CID  47109072. В архиве (PDF) из оригинала от 09.05.2013.
29. Краммер, Коби и Сингер, Йорам (2001). «Об алгоритмической реализации векторных машин на основе мультиклассового ядра» (PDF). Журнал исследований в области машинного обучения. 2: 265–292. В архиве (PDF) из оригинала от 29.08.2015.
30. Ли, Юнкён; Лин, Йи и Вахба, Грейс (2001). «Множественные машины опорных векторов» (PDF). Вычислительная техника и статистика. 33. В архиве (PDF) из оригинала от 17.06.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. Иоахим, Торстен; "Трансдуктивный вывод для классификации текста с использованием машин опорных векторов ", Материалы Международной конференции по машинному обучению 1999 г. (ICML 1999)С. 200–209.
34. Друкер, Харрис; Берджес, Христос. C .; Кауфман, Линда; Смола, Александр Дж .; и Вапник, Владимир Н. (1997); "Машины регрессии опорных векторов ", в Достижения в системах обработки нейронной информации 9, NIPS 1996, 155–161, MIT Press.
35. Suykens, Johan A. K .; Vandewalle, Joos P. L .; "Метод наименьших квадратов поддерживает векторные машинные классификаторы ", Письма нейронной обработки, т. 9, вып. 3, июнь 1999 г., стр. 293–300.
36. Смола, Алекс Дж .; Шёлкопф, Бернхард (2004). «Учебник по поддержки векторной регрессии» (PDF). Статистика и вычисления. 14 (3): 199–222. CiteSeerX  10.1.1.41.1452. Дои:10.1023 / B: STCO.0000035301.49549.88. S2CID  15475. В архиве (PDF) из оригинала 31.01.2012.
37. Polson, Nicholas G .; Скотт, Стивен Л. (2011). «Расширение данных для машин с опорными векторами». Байесовский анализ. 6 (1): 1–23. Дои:10.1214 / 11-BA601.
38. Венцель, Флориан; Гали-Фаджу, Тео; Deutsch, Matthäus; Клофт, Мариус (2017). "Байесовские нелинейные машины опорных векторов для больших данных". Машинное обучение и обнаружение знаний в базах данных (ECML PKDD). Конспект лекций по информатике. 10534: 307–322. arXiv:1707.05532. Bibcode: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. В архиве (PDF) из оригинала от 04.12.2008.
41. Платт, Джон С. (1998). Последовательная минимальная оптимизация: быстрый алгоритм для обучения машин опорных векторов (PDF). НИПС. В архиве (PDF) из оригинала от 02.07.2015.
42. Шалев-Шварц, Шай; Певец Йорам; Сребро, Натан (2007). Pegasos: первичная оценка суб-GrAdient SOlver для SVM (PDF). ICML. В архиве (PDF) из оригинала от 15.12.2013.
43. Фан, Ронг-Эн; Чанг, Кай-Вэй; Се, Чо-Джуй; Ван, Сян-Жуй; Лин, Чи-Джен (2008). «LIBLINEAR: библиотека для большой линейной классификации» (PDF). Журнал исследований в области машинного обучения. 9: 1871–1874.
44. Аллен Чжу, Zeyuan; Чен, Вэйчжу; Ванга, банда; Чжу, Чэнгуан; Чен, Чжэн (2009). P-packSVM: Параллельный первичный запуск GRADIENT SVM ядра (PDF). ICDM. В архиве (PDF) из оригинала от 07.04.2014.

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

• Bennett, Kristin P .; Кэмпбелл, Колин (2000). "Машины опорных векторов: шумиха или аллилуйя?" (PDF). SIGKDD Исследования. 2 (2): 1–13. Дои:10.1145/380995.380999. S2CID  207753020.
• Кристианини, Нелло; Шоу-Тейлор, Джон (2000). Введение в опорные векторные машины и другие методы обучения на основе ядра. Издательство Кембриджского университета. ISBN  0-521-78019-5.
• Фрадкин, Дмитрий; Мучник, Илья (2006). «Машины опорных векторов для классификации» (PDF). В Abello, J .; Кармод, Г. (ред.). Дискретные методы в эпидемиологии. Серия DIMACS по дискретной математике и теоретической информатике. 70. С. 13–20.
• Иванчук, Овидиу (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
• Живая демонстрация SVMJS это демонстрация графического интерфейса для JavaScript реализация SVM