Машина опорных векторов или SVM — это один из самых популярных алгоритмов обучения с учителем, который используется как для задач классификации, так и для задач регрессии. Однако в первую очередь он используется для задач классификации в машинном обучении.
Цель алгоритма SVM — найти наилучшую линию/гиперплоскость/границу решения в n-мерном пространстве, которое четко классифицирует точки данных.
Чтобы разделить два класса точек данных, можно выбрать множество возможных гиперплоскостей. Наша цель — найти плоскость с максимальным запасом, то есть максимальным расстоянием между точками данных обоих классов.
Увеличение предельного расстояния дает некоторое усиление, чтобы будущие точки данных можно было классифицировать с большей уверенностью.
Мы всегда создаем гиперплоскость с максимальным запасом, что означает максимальное расстояние между точками данных.
Мы видим, что есть три гиперплоскости:
- Гиперплоскость, касающаяся точек положительного класса, называется положительной гиперплоскостью.
- Гиперплоскость, которая касается точек отрицательного класса, называется отрицательной гиперплоскостью.
- Гиперплоскость, расположенная между положительным и отрицательным классами, называется разделяющей гиперплоскостью.
- Все эти три гиперплоскости параллельны друг другу.
Векторы поддержки:
Точки данных или векторы, которые находятся ближе всего к гиперплоскости и влияют на положение гиперплоскости, называются опорными векторами. Поскольку эти векторы поддерживают гиперплоскость, они называются опорными векторами.
Альтернативная геометрическая интуиция о SVM
мы будем использовать концепцию "выпуклой оболочки", чтобы найти гиперплоскость, максимизирующую маржу.
Выпуклая оболочка может быть определена как наименьший выпуклый многоугольник, все точки которого находятся либо внутри многоугольника, либо на многоугольнике.
Выпуклый многоугольник в основном представляет собой такой многоугольник, что все точки на кратчайшей линии, соединяющей любые две точки (расположенные внутри или на многоугольнике), лежат внутри или на многоугольнике.
Чтобы найти гиперплоскость, максимизирующую запас, используя концепцию выпуклой оболочки, мы будем использовать следующие шаги:
- Сначала нарисуйте выпуклую оболочку для положительных точек данных и для отрицательных точек данных отдельно.
2. Найдите кратчайшую линию или гиперплоскость, соединяющую корпуса.
3. Наконец, нарисуйте линию или гиперплоскость, которая делит пополам линию или гиперплоскость (нарисованную на шаге 2). Полученная линия или гиперплоскость называется «гиперплоскостью, максимизирующей поля» .
Математическая формулировка SVM:
Будем считать, что положительная и отрицательная гиперплоскости находятся на единичном расстоянии от разделяющей гиперплоскости.
SVM с жесткой маржой:
Пусть уравнение разделяющей гиперплоскости будет:
π : w^T x + b = 0
если π+ — уравнение положительной гиперплоскости
π+ : w^T x + b = 1
если π- — уравнение отрицательной гиперплоскости
π- : w^T x + b = -1
Тогда Margin =2 /||w||
Для SVM мы можем написать задачу оптимизации ограничений как
w*, b* = argmax w,b (2/||w||)
такое, что ∀i, Yi(W^T xi + b) ≥ 1
Применимо, если данные линейно разделимы, все положительные точки лежат по одну сторону от π, а все отрицательные точки лежат по другую сторону от π и между π+ и π- нет точек данных. Равен 1 для опорных векторов.
SVM с мягкой маржой:
Пусть уравнение разделяющей гиперплоскости будет:
π : w^T x + b = 0
если π+ — уравнение положительной гиперплоскости
π+ : w^T x + b = 1
если π- — уравнение отрицательной гиперплоскости
π- : w^T x + b = -1
Тогда Margin =2 /||w||
Для SVM мы можем написать задачу оптимизации ограничений как
w*, b* = argmin w,b (||w|| / 2) + C * (1/n) Σ{i = от 1 до n} ζi ____(1)
такое, что ∀i , Yi(W^T xi + b) ≥1-ζi,ζi ≥ 0
ζ =несколько единиц расстояния от правильной гиперплоскости в неправильном направлении.
Для правильно классифицированных точек ζi = 0.т. е. если Yi(W^T xi + b) ≥ 1
Для неправильно классифицированных точек ζi › 0.
Равен 1 для опорных векторов.
В уравнении (1) первая часть уравнения перед знаком «+» называется «регуляризацией», а вторая часть называется «Потерей шарнира».
C — это гиперпараметр, который всегда имеет положительное значение.
Если «C» увеличивается, то переоснащение увеличивается
Если «C» уменьшается, то недообучение увеличивается.
Для больших значений C оптимизация выберет гиперплоскость с меньшим запасом, если эта гиперплоскость лучше справляется с правильной классификацией всех обучающих точек.
И наоборот, очень маленькое значение C заставит оптимизатор искать разделяющую гиперплоскость с большим запасом, даже если эта гиперплоскость неправильно классифицирует больше точек.
Почему мы используем +1 и -1 для плоскостей опорных векторов:
π+ : w^T x + b = k
π- : w^T x + b = -k
Нет необходимости всегда выбирать +1 и -1. Итак, давайте выберем здесь любое произвольное значение k. Единственным ограничением является то, что он должен быть больше 0.
Мы не можем выбрать разные значения для наших плоскостей, то есть мы не можем взять +k1 и -k2, так как мы хотим, чтобы наши положительные и отрицательные плоскости были одинаково удалены от нашей плоскости π.
Теперь наша обновленная маржа:
2*k / ||W||
для k = 5 получаем 10/||W||
Итак, теперь мы будем использовать 10/||W|| вместо 2/||W|| это единственное отличие, и, поскольку k здесь является константой, поэтому на самом деле не имеет значения, какое значение мы выбираем, поскольку оно не повлияет на нашу задачу оптимизации.
Поэтому мы используем +1 и -1 для упрощения математических расчетов.
Функция потери:
Функция потерь, используемая в SVM, называется Потери шарнира. Проще говоря, мы можем понимать потерю шарнира как функцию, значение которой не равно нулю до определенной точки, скажем, «z», а после этой точки «z» оно равно нулю.
Ось Y относится к потере шарнира, а ось X может быть записана как:
Yi(W^T xi + b) = Zi ___(1)
Из рисунка мы можем определить потери шарнира как:
если Zi ≥ 1; потеря шарнира = 0
Зи ‹ 1; потеря шарнира = 1 - Zi
Из приведенных выше двух уравнений мы можем записать потери на петлях в более кратком формате следующим образом:
потеря шарнира = max (0, 1 - Zi)
Случай 1: Zi ≥ 1 ⇒ 1 — Zi является отрицательным значением ⇒ max(0, 1 — Zi) = 0
Случай 2:Zi ‹ 1 ⇒ 1 — Zi является положительным значением ⇒ max(0, 1 — Zi) = 1 — Zi
Для мягкого SVM мы знаем, что ζi = 0 для правильно классифицированных точек.
Расстояние неправильно классифицированной точки от правильной гиперплоскости можно записать как:
di = 1 - Yi(W ^ T xi + b) = 1 - Zi __из уравнения (1)
из определения ζi, мы можем записать как
ζi = 1 - Zi, для неправильно классифицированных точек.
Поскольку нам нужно минимизировать потери, задачу оптимизации можно записать в виде:
W*, b* = min w,b ∑{i = от 1 до n}(0,1-Yi(W^T xi + b)) + λ||w||²
λ = гиперпараметр. Если λувеличивается, недообученность увеличивается
Если λуменьшается, переобучение увеличивается
Примечание. Можно доказать, что уравнение оптимизации, полученное в этом разделе, и уравнение оптимизации, полученное в предыдущем разделе, совпадают. Только C и λ обратно пропорциональны друг другу, т.е.
C = 1/ λ
Двойная форма состава SVM:
Для SVM с мягкой маржой мы записываем задачу оптимизации ограничений как
w*, b* = argmin w,b (||w|| / 2) + C * (1/n) Σ{i = от 1 до n} ζi ____(1)
такое, что ∀i , Yi(W^T xi + b) ≥1-ζi,ζi ≥ 0
ζ =несколько единиц расстояния от правильной гиперплоскости в неправильном направлении.
Для правильно классифицированных точек ζi = 0.т. е. если Yi(W^T xi + b) ≥ 1
Для неправильно классифицированных точек ζi › 0.
Равен 1 для опорных векторов.
Уравнение (1) можно эквивалентно записать как:
α* = max αi ∑{i = от i до n} αi - (1/2) ∑{i = от 1 до n} ∑{j = от 1 до n} αi αj Yi Yj xi^T xj____(2)
такое, что αi ≥ 0и ∑{i = от 1 до n}αi Yi = 0
Уравнение (1) известно как Основная форма SVM.
Уравнение (2) известно как Двойная форма SVM
Оба уравнения эквивалентны друг другу
Xi^T Xj можно заменить любым типом функции подобия (например, косинусным сходством), а также заменить любым типом функций ядра.
Примечание.
Если αi›0, то Xi является опорным вектором, а когда αi=0, то Xi не является опорным вектором.
Наблюдение:
- Чтобы решить реальную проблему, нам не требуется фактическая точка данных, вместо этого может быть достаточно скалярного произведения между каждой парой вектора.
- Для вычисления смещенной константы «b» нам требуется только скалярное произведение.
- Основное преимущество двойной формы SVM по сравнению с формулировкой Лагранжа заключается в том, что она зависит только от α.
Трюк с ядром в SVM:
Что касается основной части SVM, которой она наиболее известна, то это хитрость ядра. Ядро — это способ вычисления скалярного произведения двух векторов x и y в некотором (очень многомерном) пространстве признаков, поэтому функции ядра иногда называют «обобщенными». скалярное произведение".
Применение трюка с ядром означает просто замену скалярного произведения двух векторов функцией ядра.
Типы ядер:
- линейное ядро
- полиномиальное ядро
- Ядро радиальной базисной функции (RBF)/ядро Гаусса
Мы сосредоточимся на многочлене и ядре Гаусса, поскольку они наиболее часто используются.
Полиномиальное ядро:
В общем случае ядро полинома определяется как:
b = степень ядра и a = постоянный член.
в полиномиальном ядре мы просто вычисляем скалярное произведение, увеличивая мощность ядра.
Пример:
Предположим, что изначально пространство X двумерно, так что
Xa = (a1 ,a2)
Xb = (b1 ,b2)
теперь, если мы хотим отобразить наши данные в более высоком измерении, скажем, в пространстве Z, которое является шестимерным, это может показаться
Чтобы решить эту двойную SVM, нам потребуется скалярное произведение (транспонирование) Za ^T и Zb.
Способ 1:
традиционно мы решили бы это:
что займет много времени, так как нам придется выполнять скалярное произведение для каждой точки данных, а затем для вычисления скалярного произведения нам может потребоваться выполнить умножение. Представьте, что мы делаем это для тысячи точек данных….
Или же мы могли бы просто использовать
Способ 2:
используя трюк ядра:
В этом методе мы можем просто вычислить скалярное произведение, увеличив значение мощности.
Теорема Мерсера
Помимо этих предопределенных ядер, какие условия определяют, какие функции можно считать ядрами? Это дается теоремой Мерсера.
Первое условие довольно тривиально, т. е. Функция ядра должна быть симметричной. Поскольку функция ядра представляет собой точечный продукт (скалярный продукт) функции отображения, мы можно написать, как показано ниже:
Теорема Мерсера подводит нас к необходимому и достаточному условию, чтобы функция была функцией ядра.
(Ссылка: https://people.eecs.berkeley.edu/~jordan/courses/)
Ядро радиальной базисной функции (RBF):
Ядра RBF являются наиболее обобщенной формой ядра и одним из наиболее широко используемых ядер из-за его сходства с распределением Гаусса. Функция ядра RBF для двух точек X₁ и X₂ вычисляет сходство или насколько они близки друг к другу. Это ядро можно математически представить следующим образом:
где,
1. «σ» — это дисперсия и наш гиперпараметр
2. ||X₁ — X₂|| — евклидово (L₂-норма) расстояние между двумя точками X₁ и X₂
Пусть d₁₂ будет расстоянием между двумя точками X₁ и X₂, теперь мы можем представить d₁₂ следующим образом:
Рис. 2. Расстояние между двумя точками в пространстве [Изображение автора]
Уравнение ядра можно переписать следующим образом:
Максимальное значение, которое может иметь ядро RBF, равно 1 и возникает, когда d₁₂ равно 0, то есть когда точки совпадают, т. е. X₁ = X₂.
- Когда точки одинаковы, между ними нет расстояния, и поэтому они очень похожи.
- Когда точки разделены большим расстоянием, значение ядра меньше 1 и близко к 0, что означает, что точки не похожи.
Расстояние можно рассматривать как эквивалент несходства, потому что мы можем заметить, что когда расстояние между точками увеличивается, они становятся менее похожими.
Важно найти правильное значение «σ», чтобы решить, какие точки следует считать похожими, и это можно продемонстрировать в каждом конкретном случае.
a] σ = 1
Когда σ = 1, σ² = 1 и математическое уравнение ядра RBF будет следующим:
Кривая для этого уравнения приведена ниже, и мы можем заметить, что по мере увеличения расстояния ядро RBF уменьшается экспоненциально и равно 0 для расстояний больше 4.
Мы можем заметить, что когда d₁₂ = 0, сходство равно 1, а когда d₁₂ превышает 4 единицы, сходство равно 0.
- Из графика видно, что если расстояние меньше 4, то точки можно считать похожими, а если расстояние больше 4, то точки неподобны.
b] σ = 0.1
Когда σ = 0,1, σ² = 0,01 и математическое уравнение ядра RBF будет следующим:
Ширина области подобия минимальна при σ = 0,1 и, следовательно, только если точки очень близки, они считаются подобными.
- Мы видим, что кривая чрезвычайно остроконечная и равна 0 для расстояний больше 0,2.
- Точки считаются похожими, только если расстояние меньше или равно 0,2
b] σ = 10
Когда σ = 10, σ² = 100 и математическое уравнение ядра RBF будет следующим:
Ширина области подобия велика для σ = 100, из-за чего более удаленные точки можно считать подобными.
- Ширина кривой большая
- Точки считаются похожими на расстояниях до 10 единиц, а дальше 10 единиц они неодинаковы.
Из приведенных выше случаев видно, что ширина области сходства изменяется по мере изменения σ.
Важно найти правильное значение σ для заданного набора данных, и это можно сделать с помощью методы настройки гиперпараметров, такие как перекрестная проверка поиска в сетке и перекрестная проверка случайного поиска.
Ядро RBF популярно из-за его сходства с алгоритмом K-ближайшего соседства. Он обладает преимуществами K-NN и решает проблему пространственной сложности, поскольку машинам опорных векторов ядра RBF нужно просто хранить опорные векторы во время обучения, а не весь набор данных.
Машины опорных векторов ядра RBF реализованы в библиотеке scikit-learn и имеют два связанных с ней гиперпараметра: «C» для SVM и «γ» для ядра RBF. Здесь γ обратно пропорционально σ.
Сложности обучения и выполнения SVM:
Сложность времени обучения SVM составляет примерно O (n²).
Если n очень велико, то O(n²) также очень велико.
Таким образом, SVM не используются в приложениях с малой задержкой.
Сложность выполнения составляет примерно O (k.d)
где k = количество опорных векторов
d = Размерность данных
Машины опорных векторов — регрессия (SVR)
Метод опорных векторов также можно использовать как метод регрессии, сохраняя все основные признаки, характеризующие алгоритм (максимальный запас). Регрессия опорных векторов (SVR) использует для классификации те же принципы, что и SVM, с небольшими отличиями. Прежде всего, поскольку выход представляет собой действительное число, становится очень трудно предсказать имеющуюся информацию, которая имеет бесконечные возможности. В случае регрессии предел допуска (эпсилон) устанавливается в приближении к SVM, который уже был запрошен из задачи. Но кроме этого факта есть и более сложная причина, алгоритм более сложный, поэтому нужно учитывать. Однако основная идея всегда одна и та же: свести к минимуму ошибку, индивидуализировав гиперплоскость, которая максимизирует запас, помня о том, что часть ошибки допустима.
Плюсы:
- Он работает очень хорошо с четким запасом разделения
- Он эффективен в пространствах большой размерности.
- Он эффективен в тех случаях, когда количество измерений больше, чем количество выборок.
- Он использует подмножество точек обучения в функции принятия решений (называемых опорными векторами), поэтому он также эффективно использует память.
Минусы:
- Он не работает хорошо, когда у нас большой набор данных, потому что требуемое время обучения выше.
- Он также не очень хорошо работает, когда в наборе данных больше шума, т. е. целевые классы перекрываются.
- SVM не дает оценок вероятности напрямую, они рассчитываются с использованием дорогостоящей пятикратной перекрестной проверки. Он включен в соответствующий метод SVC библиотеки Python scikit-learn.
Ссылки:
Javapoint
Компьютерщики для компьютерщиков
Analyticsvidhya
На пути к науке о данных
