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

Вступление

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

Цель этого поста - объяснить концепции Soft Margin Formulation и Kernel Trick, которые SVM используют для классификации линейно неразделимых данных.

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



Машина опорных векторов - Введение в алгоритмы машинного обучения
Модель SVM с нуля в сторонуdatascience.com



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

Прежде чем мы перейдем к концепциям Soft Margin и Kernel трюка, давайте установим необходимость в них. Предположим, у нас есть некоторые данные, которые можно изобразить в 2D-пространстве следующим образом:

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

Формулировка мягкой маржи

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

Мотивация

Давайте кратко рассмотрим мотивацию такой формулировки.

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

Здесь граница решения red идеально разделяет все точки обучения. Однако действительно ли это хорошая идея иметь границу принятия решений с такой меньшей маржой? Как вы думаете, такая граница принятия решений будет хорошо обобщаться на невидимых данных? Ответ: Нет. Граница green принятия решения имеет более широкий запас, который позволил бы ей хорошо обобщать невидимые данные. В этом смысле формулировка мягкой маржи также поможет избежать проблемы переобучения.

Как это работает (математически)?

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

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

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

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

Согласно этой идее, каждая точка данных x_i должна удовлетворять следующему ограничению:

Здесь левую часть неравенства можно рассматривать как достоверность классификации. Оценка достоверности ≥ 1 предполагает, что классификатор правильно классифицировал точку. Однако, если показатель достоверности ξ_i.

Учитывая эти ограничения, наша цель - минимизировать следующую функцию:

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

Мы видим, что в измененной цели лишними являются только ξ_i термины, а все остальное остается таким же.

На заметку: в окончательном решении λ_i, соответствующие точкам, которые находятся ближе всего к краю и на изнаночной стороне поля (т. Е. Имеют ненулевое значение ξ_i), будут отличаться от нуля, поскольку они играют ключевую роль в позиционировании границы принятия решений, по сути делая их опорными векторами.

Трюк с ядром

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

Функции ядра

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

Хитрость"

Давайте посмотрим на целевую функцию для линейно разделимого случая:

Это измененная форма цели в equation 4. Здесь мы подставили оптимальные значения w и b. Эти оптимальные значения могут быть вычислены путем дифференцирования equation 4 по этим параметрам и приравнивания его к 0.

Из equation 5 мы можем наблюдать, что цель зависит от скалярного произведения пар входных векторов (x_i . x_j), которое является не чем иным, как функцией ядра. И вот что хорошо: нам не нужно ограничиваться простой функцией ядра, такой как скалярное произведение. Мы можем использовать любую причудливую функцию ядра вместо скалярного произведения, которая может измерять сходство в более высоких измерениях (где это может быть более точно; подробнее об этом позже), без значительного увеличения вычислительных затрат. По сути, это известно как трюк с ядром.

Как это работает (математически)?

Математически функцию ядра можно записать следующим образом:

Здесь x и y - входные векторы, ϕ - функция преобразования, а < , > - операция скалярного произведения. В случае функции скалярного произведения ϕ просто сопоставляет входной вектор с самим собой.

Функции ядра по сути берут скалярное произведение преобразованных входных векторов.

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

В figure 4 каждая точка P представлена ​​элементами формы (x,y) в 2D-пространстве. Глядя на желаемую границу решения, мы можем определить функцию преобразования ϕ для точки P как ϕ(P) = (x^2, y^2, √2xy) (почему мы придумали такое преобразование, станет ясно через мгновение). Давайте посмотрим, как выглядит функция ядра для этого типа преобразования для двух точек P_1 и P_2.

Если мы наблюдаем окончательный вид функции ядра, то это не что иное, как круг! Это означает, что мы изменили наше представление о подобии: вместо того, чтобы измерять сходство по тому, насколько близко расположены точки (с помощью скалярного произведения), мы измеряем сходство на основе того, находятся ли точки внутри круга. В этом смысле определение такого преобразования позволило нам иметь нелинейную границу решения в 2D-пространстве (она по-прежнему линейна в исходном 3D-пространстве) . Это может быть много вещей, поэтому ниже приводится краткое изложение принятых нами решений:

1 - Each point P is represented by (x,y) coordinates in 2D space.
2 - We project the points to 3D space by transforming their coordinates to (x^2, y^2, √2xy)
3 - Points which have high value of x.y would move upwards along the z-axis (in this case, mostly the red circles). This video provides a good visualization of the same.
4 - We find a hyperplane in 3D space that would perfectly separate the classes.
5 - The form of Kernel function indicates that this hyperplane would form a circle in 2D space, thus giving us a non-linear decision boundary.

И главный вывод:

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

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

Попробуем переписать функцию ядра в equation 7:

Ого! Таким образом, значение функции ядра (таким образом, сходство между точками в трехмерном пространстве) - это просто квадрат скалярного произведения между точками в двухмерном пространстве. Довольно здорово, правда ?! Но как это случилось?

Причина этого в том, что мы мудро выбрали нашу функцию преобразования ϕ. И пока мы продолжаем это делать, мы можем обойти этап преобразования и вычислить значение функции ядра непосредственно из сходства между точками в 2D-пространстве. Это, в свою очередь, также снизит вычислительные затраты. У нас есть много популярных функций ядра, которые обладают этим замечательным свойством и могут использоваться сразу после установки (нам не нужно искать идеальные ϕ).

Заключительные замечания

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

Если вам понравилась эта статья и вы заинтересованы в моих будущих усилиях, подпишитесь на меня в Twitter: https://twitter.com/rishabh_misra_