Это вектор? Это машина? ИЛИ это что-то совершенно другое и совершенно волшебное? Ответы на эти и другие вопросы будут представлены в этом блоге, поскольку мы создаем SVM с нуля.

SVM расшифровывается как Support Vector Machines, метод обучения с учителем, разработанный Владимиром Вапником и его коллегами из AT&T Bell Labs.
В основном используется для классификации двух различных типов сущностей на основе Благодаря своим особенностям SVM находят широкое применение, включая сегментацию изображений, распознавание рукописных символов, классификацию белков и множество других.

Тщательное рассмотрение SVM требует математической строгости, поэтому следует МНОГО уравнений и анимаций. Но не пугайтесь, так как все эти уравнения — элементарная линейная алгебра и немного дифференциального исчисления.

Классификация

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

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

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

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

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

Линейно отделимый случай

Мы начинаем с таких данных, которые можно идеально разделить на две области, с «гиперплоскости». (Гиперплоскость — это расширение линии (2D) или плоскости (3D) до общего n-мерного космос.)

Правило принятия решения

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

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

Попробуем теперь сформулировать решающее правило. Сначала мы предполагаем, что существует вектор W, который является нормальным к границе решения. Пусть X — неизвестный вектор. Затем мы замечаем на рисунке ниже, что всякий раз, когда W.X ≥c, мы получаем белые (я буду называть эти образцы положительными) образцы и оранжевые (отрицательные) образцы в противном случае для некоторой определенной константы c.

Перестановка дает следующее уравнение в качестве нашего решающего правила:

Чтобы полностью определить наше решающее правило, нам нужен только вектор W и константа b. Теперь наша задача — определить тот W, для которого «ширина» улицы максимальна.

Уравнения желобов

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

За приведенными ниже уравнениями следуют все положительные и отрицательные обучающие выборки соответственно.

Они отличаются от границы решения из-за наличия 1.
≥1 гарантирует, что положительные образцы лежат на другой стороне положительного желоба, и наоборот.

Мы определяем новую переменную y, следующим образом:

Почему определили эту переменную y? Чтобы математика была удобной. (Поверьте мне, вы хотите этого удобства 😉)

«Это для математического удобства». -Патрик Уинстон

Давайте умножим y на оба условия для обучающего набора, что объединит его в одно условие для всех обучающих данных:

Уравнения желобов возникают, когда возникает равенство в указанном выше условии.

Расчет ширины

Теперь мы вычисляем ширину в единицах W.

Элементарная линейная алгебра говорит нам, что ширину можно вычислить как проекцию X2-X1 на W.

Таким образом, ширину можно определить по следующей формуле:

Подставляя значение W.X из уравнения желобов, мы получаем следующее упрощение:

Это замечательно для нас, так как теперь ширина зависит только от W. Чтобы максимизировать ширину, мы можем минимизировать норму W,что эквивалентно минимизации половины квадрата нормы L2 W. (Мы пытаемся минимизировать это выражение, так как оно, как вы уже догадались, математически удобно.)

Увеличение ширины

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

Определим лагранжиан следующим образом:

Взяв производную от L по в.р.т. W и b дает нам следующие уравнения:

И вуаля! У нас есть выражение для W. Обратите внимание, что W — это линейная комбинация обучающего набора. (Оказывается, α равны нулю для всех векторов, кроме опорных векторов, поэтому W является линейной комбинацией опорных векторов). Наша первоначальная задача была основной задачей квадратичной оптимизации, которую мы теперь можем преобразовать в двойственную, подставив W обратно в лагранжиан.

Чтобы полностью определить W, нам нужно найти α. Чтобы найти α, мы максимизируем L.

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

Неразлучный случай

Что делать, если представленные нам данные не являются линейно-разделимыми, как изображение обложки этого блога? Не бойся! поскольку у SVM есть легендарный трюк в рукаве —
ТРЮК С ЯДРОМ.

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

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

1)Полиномиальное ядро
Используется, когда мы приблизительно знаем степень границы решения.
Сопоставляется с конечными размерностями.

2)Гауссовское ядро ​​RBF
 Наносите объекты со сферической симметрией и, следовательно, круговыми, а сферические границы решений наносятся на график с ядрами RBF.
Сопоставление с бесконечным числом измерений.

3)Ядро Лапласа
Используется для задач обработки изображений, в частности, для обнаружения краев.

Где я должен использовать SVM?

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

Используйте SVM, когда:

  • Существует четкое разделение между классами.
  • Количество точек данных меньше размера точек данных

Не используйте SVM, когда:

  • Набор данных очень большой
  • В наборе данных больше шума

Заключение

Мы подошли к концу нашего обсуждения SVM. Надеюсь, я смог разъяснить вам SVM с теоретической точки зрения. Применение SVM к реальным наборам данных проще, чем его теоретические аспекты (как и любые другие алгоритмы) благодаря библиотекам Python, таким как scikit-learn. Я рекомендую вам прочитать книгу Орельен Жерон по машинному обучению, чтобы взглянуть на то, как применяются SVM.

Рекомендации

Ресурсы

Моя анимация на desmos-



SVM