Машины опорных векторов, объяснение с кодом

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

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

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

Итак, пристегните ремни и приготовьтесь погрузиться в захватывающий мир машин опорных векторов!

Общая идея

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

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

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

Как это работает

Общая идея такова: для обучения модели SVM нам сначала нужно ввести точки данных и убедиться, что они назначены соответствующим классам. Затем во время обучения SVM будет искать гиперплоскость, которая лучше всего разделяет классы. Разделение выбирается путем максимального расстояния между ближайшими точками каждого класса, которые известны как «векторы поддержки».

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

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

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

Уловка ядра

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

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

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

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

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

Математика позади

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

Для начала предположим, что у нас есть набор данных с бинарным классом, и мы хотим найти границу, которая лучше всего разделяет их с помощью SVM. Предположим, что мы работаем с двумя функциями (x1, x2 или x=[x1, x2]ᵀ), и мы должны иметь в виду, что для SVM целевой класс будет представлен как 1 и -1, а не как 0 и 1, как обычно (мы увидим, зачем нам это нужно). Кроме того, предположим, что у нас есть гиперплоскость, разделяющая оба класса в виде

wᵀx + b = 0

Где ᵀ означает транспонирование, w – вектор весов, который можно интерпретировать как вклад векторов поддержки, а x – вектор признаков. Итак, мы можем рассматривать представление данных следующим образом

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

wᵀxᵢ + b > 0 ⟶ yᵢ = 1
wᵀxᵢ + b < 0 ⟶ yᵢ = -1

Такое поведение можно получить, просто используя функцию знака, такую, что
yᵢ = sign(wᵀxᵢ + b)

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

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

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

Итак, давайте рассмотрим некоторые детали изображения, которые помогут нам лучше понять общую математику SVM. Во-первых, мы сказали, что расстояние от каждой ближайшей точки до границы равно ɣ, поэтому, поскольку мы рассматриваем обе стороны, мы можем сказать, что расстояние по перпендикуляру от каждой точки равно 2ɣ. Теперь мы также можем выразить это расстояние как разницу между x1 и x2, и поскольку мы сказали, что вектор w является представлением веса или вклада каждого опорного вектора, мы можем рассмотреть возможность умножения выражение x1-x2 через wᵀ (транспонирование дает размеры векторов), но это даст нам расстояние, а не перпендикулярное расстояние до гиперплоскости. Итак, как мы можем это сделать? Что ж, нам нужно вспомнить некоторые основы линейной алгебры. Для этой задачи нам поможет норма . Форма вектора представляет собой его длину, поэтому, если мы разделим скалярное произведение w на (x1-x2) на норму w, мы в основном проецируем расстояние между x1 и x2 в перпендикулярном направлении.

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

Итак, наша гиперплоскость или граница определяется как:

Где ||w|| является нормой вектора w. А учитывая, что наши точки определяются как:

wᵀx₁ + b = 1
wᵀx₂ + b = -1

Если мы вычтем оба выражения, мы получим:

wᵀx₁ + b — (wᵀx₂+ b) = 1 — (-1)
=> wᵀx₁ + b — wᵀx₂ — b = 1 + 1
=> wᵀx₁ — wᵀx₂ = 2
=> wᵀ(x₁ —x₂) = 2

Итак, теперь мы можем подставить только что найденное выражение в предыдущее уравнение о 2ɣ. Что приведет нас к следующему выражению маржи ɣ:

2ɣ = 2/||w|| # Делим обе части на 2
=› ɣ = 1/||w||

Однако есть ограничения, которые мы должны соблюдать. Помните наши решающие функции

wᵀx₁ + b = 1
wᵀx₂ + b = -1

Таким образом, вектор w должен быть выбран так, чтобы удовлетворять следующим

wᵀxᵢ + b ≥ 1 # Для всех баллов класса 1
wᵀxᵢ + b ≤ -1 # Для всех точек класса -1

Тогда мы можем выразить это ограничение в следующем виде:

yᵢ(wᵀxᵢ + b) ≥ 1

Теперь наша задача состоит в том, чтобы максимизировать маржу (ɣ), которая, как мы сказали, равна 1/||w||, и что она будет ограничена N ограничениями, где N — количество точек в наборе данных. Следовательно, поскольку мы хотим максимизировать 1/||w|| было бы равно минимизации ||w||, поскольку минимизация величины вектора весов, естественно, максимизирует маржу.

Как упоминают Роджерс и Джиролами в своей книге «Первый курс машинного обучения».

На самом деле будет проще минимизировать 1/2 ||w||², поэтому вместо этого мы сделаем это.

Итак, чтобы еще больше упростить задачу, мы можем использовать свойство, согласно которому квадрат величины вектора всегда неотрицательен. Следовательно, минимизация ||w||² эквивалентна минимизации ||w||, и мы можем переписать это как минимизацию 1/2 ||w||². Обратите внимание, что коэффициент 1/2 включен для упрощения вычислений и для математической убедительности, поскольку он аннулируется, когда берется производная целевой функции; и этот фактор не влияет на положение минимума или максимума, так как является константой. Следовательно, минимизация 1/2 ||w||² эквивалентна максимизации 1/||w||.

Итак, теперь наша задача оптимизации выглядит следующим образом:

минимизировать 1/2 ||w||²

при условии yᵢ(wᵀxᵢ + b) ›= 1 для i= 1, 2, …, N

Где yᵢ — целевой результат (т. е. +1 или -1) для i-го обучающего примера, xᵢ — входной вектор, b — смещение, а N — количество обучающих примеров.

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

Функция Лагранжа для граничного уравнения SVM:

L(w, b, α) = — сумма(αᵢ * (yᵢ(wᵀxᵢ + b)— 1))

Итак, наша новая целевая функция:

минимизировать (1/2) wᵀ w — sum(αᵢ * (yᵢ(wᵀxᵢ + b)— 1))
при условии αᵢ›0, для всех n

Где αᵢ — множитель Лагранжа для i-го ограничения.

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

∂/∂w = w - сумма (αᵢ* yᵢ * xᵢ) = 0

∂/∂b = сумма (αᵢ * yᵢ) = 0

Решение этих уравнений дает нам:

сумма (αᵢ * yᵢ * xᵢ) = w
сумма (αᵢ * yᵢ) = 0

Если мы подставим эти значения обратно в функцию Лагранжа, мы получим следующую двойственную форму задачи:

sum(αᵢ) — (1/2) sum(αᵢ * αⱼ * yᵢ* yⱼ* (xᵢᵀ xⱼ))
при условии: αᵢ ›= 0 для всех i sum(αᵢ * yᵢ) = 0

(ПРИМЕЧАНИЕ: если вы хотите проверить, как выполняются все подстановки, вы можете проверить главу 5 книги Роджерса и Джиролами — Первый курс машинного обучения)

Эту окончательную форму легче решить, поскольку она учитывает только значения αᵢ, которые меньше, чем исходные переменные w и b. Можно решить проблему, используя методы квадратичного программирования, такие как SMO, чтобы найти оптимальные значения αᵢ.

Стоит отметить, что первый член уравнения способствует тому, чтобы множители Лагранжа были как можно больше, поэтому мы можем иметь более широкий разрыв между границей решения и опорными векторами. Второй термин наказывает большие значения αᵢ и αⱼ, которые приводят к неправильной классификации или меньшему запасу.

После того, как мы решим задачу оптимизации, которая максимизирует значения альфа, мы найдем значения множителей Лагранжа (αᵢ), которые максимизируют запас в SVM. Наконец, мы можем вычислить весовой вектор w и член смещения b, используя уравнения, которые мы получили ранее при работе с частной производной.

Приближение к версии с лучшим обобщением

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

Это еще один пример переобучения — мы позволяем данным иметь слишком большое влияние.

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

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

yᵢ(wᵀ)xᵢ + b ≥ 1 — ξ

И проблема оптимизации становится:

минимизировать 1/2 ||w||² + C sum(ξᵢ)
при условии yᵢ(wᵀ xᵢ + b) ›= 1 — ξᵢ, для всех i ξᵢ ›= 0, для всех i

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

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

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

Вернуться к трюку с ядром

Давайте кратко повторим наше предыдущее обсуждение трюка с ядром. Трюк с ядром помогает нам работать с нелинейно разделимыми данными, отображая исходные функции в многомерное пространство, где данные являются разделимыми. Важная и элегантная часть этого заключается в том, что нам не нужно преобразовывать функции, а только операцию, которую они выполняют, в данном случае скалярное произведение (xiᵀ xj). Итак, мы можем заменить скалярное произведение в функции Лагранжа функцией ядра (K(xi, xj)), которая вычисляет сходство между двумя точками в пространстве признаков. Остальная часть проблемы оптимизации остается прежней, но теперь мы работаем с функциями ядра, а не с скалярным произведением.

Давайте Код!

Теперь, когда мы изучили тонкости SVM, пришло время реализовать нашу собственную версию на Python, прежде чем полагаться на мощные библиотеки, такие как Scikit-Learn. Почему мы предпочитаем кодировать нашу собственную реализацию, а не напрямую использовать библиотеку? Что ж, это не только позволит нам глубже понять алгоритм, но также даст возможность усилить определенные шаги, которые, возможно, не были полностью ясны в текстовом объяснении.

Прежде чем начать, мы должны иметь в виду то, что было сказано ранее. После включения множителей Лагранжа и вывода новой задачи оптимизации ее можно решить с помощью метода квадратичного программирования, такого как Последовательная минимальная оптимизация (SMO). Имея это в виду, я буду следовать этому удивительному псевдокоду из курса Стэнфордского университета CS 229. Также вы можете рассмотреть более простую версию, предоставленную Тимчишин, Виталий и Хлевнюк, Андрей. (2020).

Код можно найти и в моем аккаунте на GitHub, здесь.

Это много кода, так что теперь, когда мы увидели, как сделать это самостоятельно. Теперь давайте посмотрим, насколько простой и мощный Scikit-Learn делает это так же, как:

from sklearn.svm import SVC

# Assume that the data has been already prepared, and 
#  separated in train and test

# Instance model with parameters
#  C = 1.0
#  kernel = rbf (it could be linear, poly, rbf, sigmoid or a function (callable)
#  degree = 3
#  gamma = scale (it could be scale or auto
#  coef0 = 0
#  tol = 1e-3
#  max_iter = -1 --> no limit
model_svm = SVC(C=1.0, kernel='rbf', degree=3, gamma='scale', tol=1e-3, max_iter=-1)

# Fit the model
model_svm.fit(X_train, y_train)

# Predict labels
y_pred = model_svm.predict(y_test)

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

Наконец, стоит упомянуть, что SVM также имеет регрессионную версию. В Scikit-learn вам потребуется использовать SVR (регрессор опорных векторов) вместо SVC (классификатор опорных векторов). Вы можете прочитать больше об этом здесь".

Заключение

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