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

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

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

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

Мотивация [ править ]

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

Определение [ править ]

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

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

Приложения [ править ]

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

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

История [ править ]

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

Линейный SVM [ править ]

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

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

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

Hard-margin [ править ]

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

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

а также

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

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

Обратите внимание , что это я -й целевой (то есть, в данном случае, 1 или -1), и это я -й выход.${\displaystyle y_{i}}$${\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},}$

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

Нелинейная классификация [ править ]

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

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

Ядро связано с преобразованием уравнением . Значение w также находится в преобразованном пространстве, причем . Точечные произведения с w для классификации снова можно вычислить с помощью трюка с ядром, т . Е.${\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)}$

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

Primal [ править ]

Минимизацию (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}$

Уловка ядра [ править ]

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

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

Координатный спуск [ править ]

Алгоритмы координатного спуска для 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.}$

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

Минимизация эмпирического риска [ править ]

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

Минимизация рисков [ править ]

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

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

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

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

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

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

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

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

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

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

SVM и потеря петель [ править ]

Напомним, что SVM-классификатор (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}}}$

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

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

Свойства [ править ]

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

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

Выбор параметра [ править ]

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

Проблемы [ править ]

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

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

Расширения [ править ]

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

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

Мультиклассовая SVM [ править ]

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

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

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

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

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

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

${\displaystyle {\mathcal {D}}^{\star }=\{{\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 }$

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

Байесовская SVM [ править ]

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

Реализация [ править ]

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Bennett, Kristin P .; Кэмпбелл, Колин (2000). "Машины опорных векторов: шумиха или аллилуйя?" (PDF) . SIGKDD Исследования . 2 (2): 1–13. DOI : 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. DOI : 10.1002 / 9780470116449.ch6 . ISBN 9780470116449.
• Джеймс, Гарет; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2013). «Машины опорных векторов» (PDF) . Введение в статистическом обучение: с приложениями в R . Нью-Йорк: Спрингер. С. 337–372. ISBN 978-1-4614-7137-0.
• Шёлкопф, Бернхард; Смола, Александр Дж. (2002). Обучение с помощью ядер . Кембридж, Массачусетс: MIT Press. ISBN 0-262-19475-9.
• Стейнварт, Инго; Кристманн, Андреас (2008). Машины опорных векторов . Нью-Йорк: Спрингер. ISBN 978-0-387-77241-7.
• Теодоридис, Сергий; Кутроумбас, Константинос (2009). Распознавание образов (4-е изд.). Академическая пресса. ISBN 978-1-59749-272-0.

Внешние ссылки [ править ]

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