Методы опорных векторов (SVM)

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

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

Ключевые термины

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

В 2D для точки данных это уравнение линии.

В 2D для набора точек данных он принимает форму

• Положительные и отрицательные гиперплоскости: гиперплоскости, проходящие через опорные векторы.

Прежде чем мы попытаемся понять SVM, давайте освежим некоторые концепции векторов.

Векторы

Векторы — это все, что имеет величину и направление.

Длина вектора

Длина вектора U называется его нормой, которая записывается как ||U||.

Направление вектора

Направление вектора U записывается как w и определяется как.

Сумма двух векторов

Для двух векторов, u(u1, u2) и v(v1, v2), сумма векторов определяется выражением.

Скалярное произведение

Произведение величин двух векторов и косинуса угла между двумя векторами.

Скалярное произведение говорит нам, какая часть одного вектора идет в направлении другого.

or

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

Концепции

В основе SVM лежат две концепции: линейная и нелинейная разделимость.

Линейная разделимость

Где данные могут быть линейно разделены точкой, линией, плоскостью или гиперплоскостью.

Линейная разделимость — одна из важных концепций SVM. Хотя на практике данные могут не быть линейно разделимыми, мы начнем с линейно разделимых случаев (поскольку их легко понять и с ними работать), а затем выведем нелинейно разделимые случаи.

Нелинейная разделимость

Где данные не могут быть линейно разделены точкой, линией, плоскостью или гиперплоскостью.

Гиперпланы

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

Гиперплоскость является обобщением плоскости:

• В двух измерениях это линия.
• В трех измерениях это самолет.
• В большем измерении это можно назвать гиперплоскостью.

Понимание уравнения гиперплоскости

Два измерения

В двухмерном режиме данные могут быть разделены линией. Мы уже знаем уравнение прямой.

Для любых заданных данных (x1, y1) уравнение линии будет таким:

Or,

В матричной форме мы можем представить это как,

Высшее измерение

Читая о гиперплоскости, мы часто обнаруживаем, что уравнение гиперплоскости для более чем двумерного измерения определяется как.

Причина, по которой гиперплоскость в более чем двумерном пространстве представлена ​​таким образом, заключается в том, что трудно четко представить уравнение в более высоком измерении.

Позже мы узнаем, как соотносятся эти два уравнения гиперплоскости.

Как связаны эти две формы?

В нашем уравнении гиперплоскости w и x являются векторами. Более того, именно так мы вычисляем скалярное произведение двух векторов, а если вспомнить, то скалярное произведение — это просто другое название скалярного произведения.

Обратите внимание, что,

Это то же самое, что и

Учитывая два вектора,

Мы получаем,

Итак, два уравнения — это просто разные способы выражения одного и того же. Просто один способ лучше другого в представлении более высоких измерений.

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

Как работает SVM?

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

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

Ранее мы видели, как эти гиперплоскости выглядят в другом измерении.

Теперь, когда приходят новые данные, скажем, X, SVM пытается определить, к какому классу принадлежат эти новые данные. Для этого выполните следующие шаги.

Здесь,

X: неклассифицированная точка данных
x: расстояние X от (0, 0)
c: расстояние Максимальная гиперплоскость из (0, 0)
w: проекция x на c, также известная как скалярное произведение. w = x . в

Если x*w = c, то точка X лежит на Максимальной гиперплоскости.

Если x*w › c, то точка X лежит на отрицательной гиперплоскости.

Если x*w ‹ c, то точка X лежит на положительной гиперплоскости.

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

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

Чтобы сделать это возможным, предположим, что запас для позитивной и негативной плоскостей равен 1 каждая. И с учетом этого будет новое уравнение.

Для негативной гиперплоскости.

Если значение равно True, данные лежат в отрицательной гиперплоскости.

Для позитивной гиперплоскости.

Если значение равно True, данные лежат в положительной гиперплоскости.

Оптимизация

Цель оптимизации в SVM — максимизировать запас, чтобы положительная и отрицательная гиперплоскости были четко разделены. Это, в свою очередь, помогает SVM четко классифицировать данные.

Из приведенного выше уравнения для положительной и отрицательной гиперплоскости мы можем вычислить разницу между этими двумя плоскостями.

Разделите обе части на ||w||

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

Чтобы максимизировать эту маржу, нам нужно обновить (w, C) таким образом, чтобы

В упрощенном виде мы можем записать уравнение как,

Регуляризация

Обратная функция оптимизации даст нам функцию регуляризации. Это все еще подвергается условию выше.

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

Итак, наша функция регуляризации будет такой:

Обновите (w, C) в пределах границ приведенного ниже уравнения,

Пример

Здесь у нас есть две ошибочно классифицированные точки данных, и расчетная ошибка для каждой из этих точек данных равна E1 и E2.

Предположим,

Функция регуляризации будет выглядеть так:

Формула Лагранжа

Вы можете проверить эту ссылку, чтобы понять, как работает Лагранж.

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

Когда у нас есть проблема оптимизации при некоторых условиях или ограничениях, мы используем Лагранжа. Это дает нам новое уравнение оптимизации с новыми условиями или ограничениями.

Предположим, у нас есть функция,

При заданном условии или ограничении

Чтобы решить эту проблему с помощью Лагранжа, давайте введем новый параметр лямбда, множитель Лагранжа.

Один из способов решить эту проблему — определить новую функцию F, такую, что

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

Применить Лагранжа

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

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

Регуляризация

Ограничение

Здесь мы оптимизируем квадратное уравнение с линейным ограничением. Теперь это приводит нас к решению двойной задачи.

В оптимизации принцип двойственности гласит, что задачи оптимизации можно рассматривать с разных точек зрения: основная задача и двойственная задача. Решение двойственной задачи обеспечивает нижнюю границу решения основной задачи (минимизации).

Чтобы решить приведенную выше квадратичную задачу с линейными ограничениями, мы можем использовать метод Лагранжа.

Функция Лагранжа представлена ​​в виде

Применяя его к нашей функции регуляризации, мы получаем,

Это уравнение является основной формулировкой.

Для решения основного уравнения зададим следующие условия:

Применяя эти производные, получаем,

Теперь применим Условия Каруша-Куна-Таккера (ККТ).

Это условие утверждает, что для данной функции с множителем Лагранжа.

If,

Затем,

Для простоты предположим, что ошибка = 0,

Применив ККТ получим,

Несколько других важных условий, связанных с множителем Ларгарна,

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

Давайте подключим уравнения производных к нашей основной функции.

Подставив все эти значения в нашу основную функцию, мы получим следующую формулировку, также называемую Двойной формулировкой.

Теперь SVM максимизирует приведенное выше уравнение при следующих условиях:

И,

Вот как SVM использует функцию Лагранжа для оптимизации модели.

Трюк с ядром

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

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

Давайте разберемся с этим на нескольких простых примерах.

Преобразование 2D в 3D — один вектор

Здесь у нас есть вектор u, заданный координатами (x, y).

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

Итак, теперь мы можем представить наш вектор u в трехмерном пространстве как

Преобразование 2D в 3D — два вектора

Теперь предположим, что у нас есть 2 двумерных вектора u и v, и мы хотим преобразовать оба в трехмерные векторы.

Как мы видели выше, третье измерение определяется выражением

Мы можем представить u и v в третьем измерении как,

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

Еще более высокие параметры

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

Используя описанный выше метод, эти векторы в девяти измерениях будут выглядеть так:

Скалярный продукт этих векторов может быть задан как

В общем виде мы можем представить скалярный продукт как,

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

Так как же SVM может добиться этого без ущерба для производительности?

Вот хитрость: SVM не нужны все эти новые измерения, чтобы творить чудеса — на самом деле он может обойтись только скалярными произведениями между исходными векторами в исходном измерении.

Вот тут-то и появляется трюк с ядром. Он позволяет нам работать в исходном пространстве признаков, не вычисляя координаты данных в пространстве более высокого измерения. Другими словами, мы можем просто вычислить скалярное произведение u — транспонировать и v в исходном измерении.

Функция ядра обозначается k(x, y). Скалярное произведение u — транспонировать и v приведено ниже. Сложность вычислений в этом случае составляет O(n).

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

Типы функций ядра

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

Он популярен в обработке изображений.

d — степень полинома.

Ядро Гаусса

Это ядро ​​общего назначения; используется, когда нет никаких предварительных знаний о данных.

σ — это дисперсия и наш гиперпараметр.

Радиальная базисная функция Гаусса (RBF)

Это ядро ​​общего назначения; используется, когда нет никаких предварительных знаний о данных.

Ядро RBF Лапласа

Это ядро ​​общего назначения; используется, когда нет никаких предварительных знаний о данных.

σ — это дисперсия и наш гиперпараметр.

Сигмовидное ядро

Мы можем использовать его как прокси для нейронных сетей. Уравнение:

alpha – это наклон, а c – точка пересечения.

Преимущества

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

Недостатки

• Выбрать «хорошую» функцию ядра непросто.
• Длительное время обучения для больших наборов данных.
• Трудно понять и интерпретировать окончательную модель, переменные веса и индивидуальное влияние.
• Сложно настроить гиперпараметры, гамму SVM.

Я надеюсь, что эта статья даст вам хорошее представление о машинах опорных векторов.

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

Спасибо!