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

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

Начнем с определения гиперплоскости.

Что такое гиперплоскость?

В p-мерном пространстве гиперплоскость (H) - это плоское аффинное подпространство размерности p-1. Другими словами, если V - p-мерное векторное пространство, то H - (p-1) -мерное подпространство. Примерами двухмерных гиперплоскостей являются любые прямые, проходящие через начало координат. В 3-х измерениях любая плоскость, содержащая начало координат.

Упомянутая выше гиперплоскость делит p-мерное пространство на две половины. В зависимости от того, имеет ли уравнение ›0 или‹ 0, точка X лежит по обе стороны от гиперплоскости.

Классификация с использованием разделяющей гиперплоскости

Теперь, когда мы поняли, что такое гиперплоскость, давайте сделаем еще один шаг вперед к созданию классификатора на основе разделяющей гиперплоскости. Если существует такая гиперплоскость, которая может разделить наши обучающие наблюдения на два класса, а именно y_i = 1 и y_i = -1, тогда гиперплоскость имеет следующие свойства;

Де-факто это можно записать в одном уравнении как;

Таких гиперплоскостей может быть бесконечное количество. На рисунке ниже показаны три таких гиперплоскости;

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

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

Классификатор максимальной маржи

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

Помните, что если p велико, классификатор максимальной маржи также может привести к переопределению.

На рисунке 3 показаны 3 наблюдения, которые расположены на пунктирной линии (поле). Эти наблюдения известны как «опорные векторы», поскольку они поддерживают гиперплоскость максимального поля в том смысле, что если они сдвинутся хотя бы незначительно, гиперплоскость тоже сдвинется.

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

Задачу оптимизации поиска гиперплоскости с максимальным запасом математически можно записать как:

Здесь M представляет собой границу гиперплоскости, и задача оптимизации выбирает ßs, которые максимизируют M. Фактически, для того, чтобы каждое наблюдение находилось на правильной стороне гиперплоскости, нам нужно, чтобы второе ограничение было ›0, но мы хотим, чтобы наблюдение было в правой части поля, поэтому мы требуем, чтобы оно было ≥M. Это ограничение гарантирует, что каждое наблюдение будет правильным, если M положительно.

Классификатор максимального запаса - очень естественный подход, если существует разделяющая гиперплоскость. Однако во многих случаях разделяющая гиперплоскость отсутствует, и поэтому нет классификатора максимального поля. В этом случае вышеупомянутая оптимизационная проблема не имеет решения с M> 0. Как вы можете видеть на рисунке 4 ниже, мы не можем точно разделить наблюдения на два класса. Для подобных сценариев мы можем найти гиперплоскость, которая «почти» разделяет классы.

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

Классификатор опорных векторов

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

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

M - это ширина поля, и мы стремимся сделать это количество как можно большим. ε_1,. . . , ε_n известны как резервные переменные, которые говорят нам, где находится каждое наблюдение . Если ε_i = 0, i-е наблюдение находится на правильной стороне поля. Если εi ›0, то i-е наблюдение находится не на той стороне поля. Если εi ›1, то он находится не на той стороне гиперплоскости. Как и в предыдущих разделах, мы относим наблюдения к определенному классу на основе знака;

Давайте теперь обсудим параметр настройки C более подробно. C устанавливает верхнюю границу суммы ε_i и, следовательно, определяет количество допустимых нарушений границы и гиперплоскости. Если C = 0, то нет места для нарушений и ε1 =… = εn = 0, и в этом случае это просто становится задачей оптимизации гиперплоскости с максимальным запасом. Если C ›0, не более C наблюдений может быть на неправильной стороне гиперплоскости (потому что тогда ε_i› 1 и нам требуется ∑ε_i≤C). По мере увеличения C мы допускаем больше нарушений для поля, и поэтому поле будет расширяться, и наоборот.

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

Классификатор опорных векторов является естественным подходом для классификации, если граница между двумя классами является линейной. Однако в реальных жизненных ситуациях мы иногда сталкиваемся с нелинейными границами классов.

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

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

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

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

Ядро - это функция, которая количественно определяет сходство двух наблюдений. Он представлен как;

Например, показанное здесь ядро ​​является линейным ядром;

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

Также можно использовать другие ядра, которые преобразуют пространство ввода в более высокие измерения, такие как Полиномиальное ядро ​​ или Радиальное ядро ​​. Это широко известно как трюк с ядром.

Полиномиальное ядро:

Это называется полиномиальным ядром степени d. Это равносильно подгонке классификатора опорных векторов в многомерное пространство, включающее полиномы степени d, а не в исходное пространство, что приводит к гораздо более гибкой границе решения. Если d = 1 в приведенном выше уравнении, он сводится к классификатору опорных векторов, рассмотренному ранее.

Радиальное ядро:

Здесь γ - положительная постоянная. В случае радиального ядра, если тестовое наблюдение (x) далеко от обучающего наблюдения x_i, то член суммирования в приведенном выше выражении велик, и поэтому функция ядра будет очень маленькой. Таким образом, это конкретное обучающее наблюдение не будет играть роли в прогнозировании класса для тестового наблюдения x. В более общем плане обучающие наблюдения, далекие от x, по существу не будут играть никакой роли в предсказании метки класса для x.

Реализация в R

Давайте начнем с создания двухмерных данных и немного разделим их. Постройте матрицу x с 20 наблюдениями в 2 классах по 2 переменным. Затем создайте переменную y, которая будет равна -1 или 1, по 10 в каждом классе. Построение графика данных поможет вам визуализировать набор данных, имеющий два класса - красный и синий.

set.seed(10111) 
x=matrix(rnorm(40), 20, 2) 
y=rep(c(-1, 1), c(10, 10)) 
x[y==1,]=x[y==1,] + 1 
plot(x,col=y + 3,pch=19)

Мы будем использовать функцию svm () в библиотеке «e1071». Мы создаем фрейм данных из данных и кодируем переменную y как факторную переменную. Аргумент scale = FALSE указывает функции svm () не масштабировать каждую функцию так, чтобы она имела нулевое среднее значение или единичное стандартное отклонение.

dat=data.frame(x,y=as.factor(y))
library(e1071)
svmfit=svm(y ~ .,data=dat,kernel="linear",cost=10,scale=FALSE)
print(svmfit)
plot(svmfit,dat)

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

Теперь вы можете попробовать реализовать SVM в R с использованием разных ядер, изменяя параметр ядра в функции svm ().

Заключение и ссылки

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

Использованные ссылки;

Спасибо.