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

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

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

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

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

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

Мотивация

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

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

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

Ядро машины

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

История

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

Линейный SVM

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

Нам дан обучающий набор данных точек вида , где либо 1, либо −1, каждый из которых указывает класс, к которому принадлежит точка. Каждый из них является -мерным вещественным вектором. Мы хотим найти «гиперплоскость с максимальным отступом», которая разделяет группу точек, для которых от группы точек, для которых , которая определяется так, что расстояние между гиперплоскостью и ближайшей точкой из любой группы максимизируется. ${\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=0.}$$

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

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

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

и

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

Геометрически расстояние между этими двумя гиперплоскостями равно , ^[19] поэтому для максимизации расстояния между плоскостями мы хотим минимизировать . Расстояние вычисляется с использованием уравнения расстояния от точки до плоскости . Мы также должны предотвратить попадание точек данных на границу, мы добавляем следующее ограничение: для каждого или или Эти ограничения утверждают, что каждая точка данных должна лежать на правильной стороне границы. ${\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} }}&&{\frac {1}{2}}\|\mathbf {w} \|^{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 \lVert \mathbf {w} \rVert ^{2}+C\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right],}$$

где параметр определяет компромисс между увеличением размера поля и обеспечением того, что лежит на правильной стороне поля (обратите внимание, что мы можем добавить вес к любому члену в уравнении выше). Разложив потерю шарнира, эту задачу оптимизации можно свести к следующему: ${\displaystyle C>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 с жестким запасом, если входные данные линейно классифицируемы, но все равно будет узнавать, является ли правило классификации жизнеспособным или нет. ${\displaystyle C}$

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

Ядро машины

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

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

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

• Полиномиальный (однородный) : . В частности, когда , это становится линейным ядром. ${\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 , a ² + b ² )

Предположим теперь, что мы хотели бы изучить нелинейное правило классификации, которое соответствует линейному правилу классификации для преобразованных точек данных. Более того, нам дана функция ядра , которая удовлетворяет . ${\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 ) могут быть адаптированы, где вместо того, чтобы делать шаг в направлении градиента функции, делается шаг в направлении вектора, выбранного из субградиента функции . Этот подход имеет то преимущество, что для некоторых реализаций количество итераций не масштабируется с , количеством точек данных. ^[22] ${\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}}}$$

Для каждого , итеративно, коэффициент корректируется в направлении . Затем полученный вектор коэффициентов проецируется на ближайший вектор коэффициентов, который удовлетворяет заданным ограничениям. (Обычно используются евклидовы расстояния.) Затем процесс повторяется до тех пор, пока не будет получен почти оптимальный вектор коэффициентов. Полученный алгоритм чрезвычайно быстр на практике, хотя было доказано мало гарантий производительности. ^[23] ${\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 — для линейной классификации эмпирический риск минимизируется любой функцией, границы которой лежат между опорными векторами, и простейшим из них является классификатор с максимальным запасом. ^[24] ${\displaystyle f^{*}}$ ${\displaystyle {\mathcal {R}}}$

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

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

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

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

Эффективность SVM зависит от выбора ядра, параметров ядра и параметра мягкого поля . Обычным выбором является гауссовское ядро, которое имеет один параметр . Лучшая комбинация и часто выбирается с помощью поиска по сетке с экспоненциально растущими последовательностями и , например, ; . Обычно каждая комбинация выбора параметров проверяется с помощью перекрестной проверки , и выбираются параметры с наилучшей точностью перекрестной проверки. В качестве альтернативы недавняя работа по байесовской оптимизации может быть использована для выбора и , часто требуя оценки гораздо меньшего количества комбинаций параметров, чем поиск по сетке. Окончательная модель, которая используется для тестирования и классификации новых данных, затем обучается на всем обучающем наборе с использованием выбранных параметров. ^[27] ${\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.
• Параметры решенной модели трудно интерпретировать.

Расширения

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

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

Доминирующий подход для этого заключается в сведении одной многоклассовой проблемы к нескольким задачам бинарной классификации . ^[28] Распространенные методы такого сведения включают: ^{[28] [29]}

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

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

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

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

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

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

Свернуть (в ) ${\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 расширяет свое применение для обработки общих структурированных выходных меток, например, деревьев синтаксического анализа, классификации с таксономиями, выравнивания последовательностей и многого другого. ^[37]

Регрессия

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

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

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

минимизировать ${\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 допускает байесовскую интерпретацию посредством техники аугментации данных . ^[41] В этом подходе SVM рассматривается как графическая модель (где параметры связаны через распределения вероятностей). Этот расширенный вид позволяет применять байесовские методы к SVM, такие как гибкое моделирование признаков, автоматическая настройка гиперпараметров и предиктивная количественная оценка неопределенности . Недавно Флориан Венцель разработал масштабируемую версию байесовского SVM, что позволило применять байесовские SVM к большим данным . ^[42] Флориан Венцель разработал две разные версии: схему вариационного вывода (VI) для машины опорных векторов байесовского ядра (SVM) и стохастическую версию (SVI) для линейного байесовского SVM. ^[43]

Выполнение

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

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

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

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

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

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

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

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

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

Ссылки

1. Кортес, Коринна ; Вапник, Владимир (1995). "Сети опорных векторов" (PDF) . Машинное обучение . 20 (3): 273–297. CiteSeerX  10.1.1.15.9362 . doi : 10.1007/BF00994018 . S2CID  206787478.
2. Вапник, Владимир Н. (1997). «Метод опорных векторов». В Gerstner, Wulfram; Germond, Alain; Hasler, Martin; Nicoud, Jean-Daniel (ред.). Искусственные нейронные сети — ICANN'97 . Конспект лекций по информатике. Том 1327. Берлин, Гейдельберг: Springer. стр. 261–271. doi :10.1007/BFb0020166. ISBN 978-3-540-69620-9.
3. Авад, Мариетт; Ханна, Рахул (2015). «Опорные векторные машины для классификации». Эффективные обучающие машины . Apress. стр. 39–66. doi : 10.1007/978-1-4302-5990-9_3 . ISBN 978-1-4302-5990-9.
4. Бен-Гур, Аса; Хорн, Дэвид; Зигельманн, Хава; Вапник Владимир Николаевич».«Кластеризация опорных векторов» (2001);». Журнал исследований машинного обучения . 2 : 125–137.
5. "1.4. Метод опорных векторов — документация scikit-learn 0.20.2". Архивировано из оригинала 2017-11-08 . Получено 2017-11-08 .
6. Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2008). Элементы статистического обучения: добыча данных, вывод и прогнозирование (PDF) (Второе изд.). Нью-Йорк: Springer. С. 134.
7. Boser, Bernhard E.; Guyon, Isabelle M.; Vapnik, Vladimir N. (1992). "A training algorithm for optimize margin classifiers". Труды пятого ежегодного семинара по теории вычислительного обучения – COLT '92 . стр. 144. CiteSeerX 10.1.1.21.3818 . doi :10.1145/130385.130401. ISBN  978-0897914970. S2CID  207165665.
8. Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Раздел 16.5. Опорные векторные машины". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8. Архивировано из оригинала 2011-08-11.
9. Йоахимс, Торстен (1998). «Текстовая категоризация с помощью опорных векторных машин: обучение с использованием множества релевантных признаков». Машинное обучение: ECML-98 . Конспект лекций по информатике. Том 1398. Springer. С. 137–142. doi : 10.1007/BFb0026683 . ISBN 978-3-540-64417-0.
10. Прадхан, Самир С. и др. (2 мая 2004 г.). Неглубокий семантический анализ с использованием опорных векторных машин. Труды конференции по технологиям естественного языка североамериканского отделения Ассоциации компьютерной лингвистики: HLT-NAACL 2004. Ассоциация компьютерной лингвистики. стр. 233–240.
11. Вапник, Владимир Н.: Приглашенный докладчик. IPMU Обработка информации и управление 2014).
12. Barghout, Lauren (2015). "Пространственно-таксонные информационные гранулы, используемые в итеративном нечетком принятии решений для сегментации изображений" (PDF) . Гранулярные вычисления и принятие решений . Исследования в области больших данных. Том 10. С. 285–318. doi :10.1007/978-3-319-16829-6_12. ISBN 978-3-319-16828-9. S2CID  4154772. Архивировано из оригинала (PDF) 2018-01-08 . Получено 2018-01-08 .
13. А. Майти (2016). «Контролируемая классификация поляриметрических данных RADARSAT-2 для различных особенностей суши». arXiv : 1608.00501 [cs.CV].
14. ДеКост, Деннис (2002). «Обучение инвариантных опорных векторных машин» (PDF) . Машинное обучение . 46 : 161–190. doi : 10.1023/A:1012454411458 . S2CID  85843.
15. Maitra, DS; Bhattacharya, U.; Parui, SK (август 2015 г.). «Общий подход к распознаванию рукописных символов нескольких шрифтов на основе CNN». 2015 13-я Международная конференция по анализу и распознаванию документов (ICDAR) . стр. 1021–1025. doi :10.1109/ICDAR.2015.7333916. ISBN 978-1-4799-1805-8. S2CID  25739012.
16. Гаонкар, Б.; Даватцикос, К. (2013). «Аналитическая оценка карт статистической значимости для многомерного анализа и классификации изображений на основе машины опорных векторов». NeuroImage . 78 : 270–283. doi :10.1016/j.neuroimage.2013.03.066. PMC 3767485 . PMID  23583748. 
17. Cuingnet, Rémi; Rosso, Charlotte; Chupin, Marie; Lehéricy, Stéphane; Dormont, Didier; Benali, Habib; Samson, Yves; Colliot, Olivier (2011). "Пространственная регуляризация SVM для обнаружения изменений диффузии, связанных с исходом инсульта" (PDF) . Medical Image Analysis . 15 (5): 729–737. doi :10.1016/j.media.2011.05.007. PMID  21752695. Архивировано из оригинала (PDF) 22.12.2018 . Получено 08.01.2018 .
18. Статников, Александр; Хардин, Дуглас; и Алиферис, Константин; (2006); «Использование методов на основе весов SVM для определения причинно-следственных и не причинно-следственных переменных», Sign , 1, 4.
19. "Почему маржа SVM равна 2 ‖ w ‖ {\displaystyle {\frac {2}{\|\mathbf {w} \|}}} ". Mathematics Stack Exchange . 30 мая 2015 г.
20. Айзерман, Марк А.; Браверман, Эммануэль М. и Розоноэр, Лев И. (1964). «Теоретические основы метода потенциальной функции в обучении распознаванию образов». Автоматизация и дистанционное управление . 25 : 821–837.
21. Jin, Chi; Wang, Liwei (2012). Зависящая от размерности граница PAC-Bayes. Достижения в области нейронных систем обработки информации. CiteSeerX 10.1.1.420.3487 . Архивировано из оригинала 2015-04-02. 
22. Шалев-Шварц, Шай; Сингер, Йорам; Сребро, Натан; Коттер, Эндрю (16 октября 2010 г.). «Pegasos: primal estimate sub-gradient resolver for SVM». Математическое программирование . 127 (1): 3–30. CiteSeerX 10.1.1.161.9629 . doi :10.1007/s10107-010-0420-4. ISSN  0025-5610. S2CID  53306004. 
23. Hsieh, Cho-Jui; Chang, Kai-Wei; Lin, Chih-Jen; Keerthi, S. Sathiya; Sundararajan, S. (2008-01-01). "Метод спуска по двойной координате для крупномасштабного линейного SVM". Труды 25-й международной конференции по машинному обучению - ICML '08 . Нью-Йорк, Нью-Йорк, США: ACM. стр. 408–415. CiteSeerX 10.1.1.149.5594 . doi :10.1145/1390156.1390208. ISBN  978-1-60558-205-4. S2CID  7880266.
24. Росаско, Лоренцо; Де Вито, Эрнесто; Капоннетто, Андреа; Пиана, Мишель; Верри, Алессандро (1 мая 2004 г.). «Все ли функции потерь одинаковы?». Нейронные вычисления . 16 (5): 1063–1076. CiteSeerX 10.1.1.109.6786 . дои : 10.1162/089976604773135104. ISSN  0899-7667. PMID  15070510. S2CID  11845688. 
25. Р. Коллобер и С. Бенжио (2004). Связи между персептронами, многослойными перцептронами и опорными векторами. Труды Международной конференции по машинному обучению (ICML).
26. Мейер, Дэвид; Лейш, Фридрих; Хорник, Курт (сентябрь 2003 г.). «Машина опорных векторов в процессе тестирования». Neurocomputing . 55 (1–2): 169–186. doi :10.1016/S0925-2312(03)00431-4.
27. Hsu, Chih-Wei; Chang, Chih-Chung & Lin, Chih-Jen (2003). Практическое руководство по классификации опорных векторов (PDF) (технический отчет). Кафедра компьютерных наук и информационной инженерии, Национальный университет Тайваня. Архивировано (PDF) из оригинала 25.06.2013.
28. Duan, Kai-Bo; Keerthi, S. Sathiya (2005). "Какой метод SVM для нескольких классов является лучшим? Эмпирическое исследование" (PDF) . Системы множественных классификаторов . LNCS . Том 3541. стр. 278–285. CiteSeerX 10.1.1.110.6789 . doi :10.1007/11494683_28. ISBN  978-3-540-26306-7. Архивировано из оригинала (PDF) 2013-05-03 . Получено 2019-07-18 .
29. Hsu, Chih-Wei & Lin, Chih-Jen (2002). "Сравнение методов для многоклассовых опорных векторных машин" (PDF) . IEEE Transactions on Neural Networks . 13 (2): 415–25. doi :10.1109/72.991427. PMID  18244442. Архивировано из оригинала (PDF) 2013-05-03 . Получено 2018-01-08 .
30. Платт, Джон; Кристианини, Нелло ; Шоу-Тейлор, Джон (2000). "DAG с большими полями для многоклассовой классификации" (PDF) . В Солла, Сара А .; Лин, Тодд К.; Мюллер, Клаус-Роберт (ред.). Достижения в области нейронных систем обработки информации . MIT Press. стр. 547–553. Архивировано (PDF) из оригинала 2012-06-16.
31. Дитерих, Томас Г.; Бакири, Гулум (1995). «Решение задач многоклассового обучения с помощью выходных кодов с исправлением ошибок» (PDF) . Журнал исследований искусственного интеллекта . 2 : 263–286. arXiv : cs/9501101 . Bibcode :1995cs........1101D. doi :10.1613/jair.105. S2CID  47109072. Архивировано (PDF) из оригинала 2013-05-09.
32. Краммер, Коби и Сингер, Йорам (2001). «Об алгоритмической реализации векторных машин на основе многоклассового ядра» (PDF) . Журнал исследований машинного обучения . 2 : 265–292. Архивировано (PDF) из оригинала 29-08-2015.
33. Ли, Юнгён; Лин, Йи и Вахба, Грейс (2001). «Многокатегорийные опорные векторные машины» (PDF) . Вычислительная наука и статистика . 33. Архивировано (PDF) из оригинала 2013-06-17.
34. Ли, Юнгён; Лин, Йи; Вахба, Грейс (2004). «Многокатегорийные опорные векторные машины». Журнал Американской статистической ассоциации . 99 (465): 67–81. CiteSeerX 10.1.1.22.1879 . doi :10.1198/016214504000000098. S2CID  7066611. 
35. Ван ден Бург, Геррит Дж. Дж. и Гроенен, Патрик Дж. Ф. (2016). «GenSVM: обобщенная многоклассовая машина опорных векторов» (PDF) . Журнал исследований машинного обучения . 17 (224): 1–42.
36. Йоахимс, Торстен. Трансдуктивный вывод для классификации текста с использованием опорных векторных машин (PDF) . Труды Международной конференции по машинному обучению 1999 года (ICML 1999). стр. 200–209.
37. https://www.cs.cornell.edu/people/tj/publications/tsochantaridis_etal_04a.pdf ^{[ пустой URL-адрес PDF ]}
38. Друкер, Харрис; Берджес, Крайст. К.; Кауфман, Линда; Смола, Александр Дж.; и Вапник, Владимир Н. (1997); «Машины регрессии опорных векторов», в Advances in Neural Information Processing Systems 9, NIPS 1996 , 155–161, MIT Press.
39. Suykens, Johan AK; Vandewalle, Joos PL; «Классификаторы на основе опорных векторных машин наименьших квадратов», Neural Processing Letters , т. 9, № 3, июнь 1999 г., стр. 293–300.
40. Smola, Alex J.; Schölkopf, Bernhard (2004). "Учебник по регрессии опорных векторов" (PDF) . Статистика и вычисления . 14 (3): 199–222. CiteSeerX 10.1.1.41.1452 . doi :10.1023/B:STCO.0000035301.49549.88. S2CID  15475. Архивировано (PDF) из оригинала 2012-01-31. 
41. Полсон, Николас Г.; Скотт, Стивен Л. (2011). «Увеличение данных для опорных векторных машин». Байесовский анализ . 6 (1): 1–23. doi : 10.1214/11-BA601 .
42. Венцель, Флориан; Гали-Фажу, Тео; Дойч, Маттеус; Клофт, Мариус (2017). «Байесовские нелинейные машины опорных векторов для больших данных». Машинное обучение и обнаружение знаний в базах данных . Конспект лекций по информатике. Том 10534. С. 307–322. arXiv : 1707.05532 . Bibcode :2017arXiv170705532W. doi :10.1007/978-3-319-71249-9_19. ISBN 978-3-319-71248-2. S2CID  4018290.
43. Флориан Венцель; Маттеус Дойч; Тео Гали-Фажу; Мариус Клофт; «Масштабируемый приближенный вывод для байесовской нелинейной машины опорных векторов»
44. Ferris, Michael C.; Munson, Todd S. (2002). "Методы внутренних точек для массивных опорных векторных машин" (PDF) . SIAM Journal on Optimization . 13 (3): 783–804. CiteSeerX 10.1.1.216.6893 . doi :10.1137/S1052623400374379. S2CID  13563302. Архивировано (PDF) из оригинала 2008-12-04. 
45. Платт, Джон К. (1998). Последовательная минимальная оптимизация: быстрый алгоритм для обучения опорных векторных машин (PDF) . NIPS. Архивировано (PDF) из оригинала 2015-07-02.
46. Шалев-Шварц, Шай; Сингер, Йорам; Сребро, Натан (2007). Pegasos: Primal Estimated sub-GrAdient SOlver для SVM (PDF) . ICML. Архивировано (PDF) из оригинала 2013-12-15.
47. Фань, Ронг-Эн; Чанг, Кай-Вэй; Хси, Чо-Жуй; Ван, Сян-Руй; Линь, Чи-Джен (2008). "LIBLINEAR: Библиотека для большой линейной классификации" (PDF) . Журнал исследований машинного обучения . 9 : 1871–1874.
48. Аллен Чжу, Цзэюань; Чэнь, Вэйчжу; Ван, Ганг; Чжу, Чэнгуан; Чэнь, Чжэн (2009). P-packSVM: Parallel Primal grAdient desCent Kernel SVM (PDF) . ICDM. Архивировано (PDF) из оригинала 2014-04-07.
49. Фань, Ронг-Эн; Чанг, Кай-Вэй; Сье, Чо-Жуй; Ван, Сян-Руй; Линь, Чи-Джен (2008). «LIBLINEAR: Библиотека для большой линейной классификации». Журнал исследований машинного обучения . 9 (авг): 1871–1874.
50. Мохамад, Исмаил; Усман, Дауда (2013-09-01). «Стандартизация и ее влияние на алгоритм кластеризации K-средних». Research Journal of Applied Sciences, Engineering and Technology . 6 (17): 3299–3303. doi : 10.19026/rjaset.6.3638 .
51. Феннелл, Питер; Цзо, Жия; Лерман, Кристина (2019-12-01). «Прогнозирование и объяснение поведенческих данных с помощью структурированной декомпозиции пространства признаков». EPJ Data Science . 8 . arXiv : 1810.09841 . doi : 10.1140/epjds/s13688-019-0201-0 .

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

• Беннетт, Кристин П.; Кэмпбелл, Колин (2000). «Машины опорных векторов: шумиха или аллилуйя?» (PDF) . Исследования SIGKDD . 2 (2): 1–13. doi :10.1145/380995.380999. S2CID  207753020.
• Кристианини, Нелло; Шоу-Тейлор, Джон (2000). Введение в опорные векторные машины и другие методы обучения на основе ядра . Cambridge University Press. ISBN 0-521-78019-5.
• Фрадкин, Дмитрий; Мучник, Илья (2006). "Машины опорных векторов для классификации" (PDF) . В Abello, J.; Carmode, G. (ред.). Дискретные методы в эпидемиологии . Серия DIMACS в дискретной математике и теоретической информатике. Том 70. С. 13–20.^{[ цитата не найдена ]}
• Йоахимс, Торстен (1998). "Текстовая категоризация с помощью опорных векторных машин: обучение с использованием множества релевантных признаков". В Nédellec, Claire; Rouveirol, Céline (ред.). "Машинное обучение: ECML-98 . Конспект лекций по информатике. Том 1398. Берлин, Гейдельберг: Springer. стр. 137-142. doi :10.1007/BFb0026683. ISBN 978-3-540-64417-0. S2CID  2427083.
• Ivanciuc, Ovidiu (2007). "Применение опорных векторных машин в химии" (PDF) . Обзоры в Computational Chemistry . 23 : 291–400. doi :10.1002/9780470116449.ch6. ISBN 9780470116449.
• Джеймс, Гарет; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2013). «Машины опорных векторов» (PDF) . Введение в статистическое обучение: с приложениями в R. Нью-Йорк: Springer. С. 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-е изд.). Academic Press. ISBN 978-1-59749-272-0.

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

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