Метод опорных векторов (SVM)
Метод опорных векторов(SVM - support vector machine) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как специальный случай регуляризации по Тихонову.
SVM используется как для линейно разделяемых данных, так и для нелинейных разделяемых данных.
Для нелинейных данных используются функции ядра.
Давайте узнаем о SVC (классификатор опорных векторов) в линейных разделяемых данных, который используется для задач классификации в этой статье.
Темы, затронутые в статье.
Линейно разделяемые данные
- SVM в линейно разделимых данных
- Что такое гиперплоскость?
- Что делает SVM?
- Важные термины, используемые в SVM
- Почему он назван машинами опорных векторов?
- Математика SVM
- Как найти лучшую гиперплоскость?
Линейно разделяемые данные
1. Одномерное пространство
Предположим, у нас есть два класса, красный и зеленый, и если мы можем найти границу, которая разделяет два класса, это называется линейно разделяемыми данными.
Здесь мы могли бы выделить одну точку, которая действует как граница между двумя классами. Точки данных ниже конкретной точки относятся к красному классу, а выше этой конкретной точки относятся к зеленому классу.
2. Двумерное пространство
Точно так же в двухмерном пространстве мы можем нарисовать линию, которая действует как граница между двумя классами.
Здесь точки данных так же линейно разделяются в данном измерении.
Основная идея метода — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей классы. Разделяющей гиперплоскостью будет гиперплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора.
Гиперплоскости - это границы решений, которые классифицируют данные
Постановка задачи
Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представляется как вектор (точка) в p-мерном пространстве (упорядоченный набор p чисел). Каждая из этих точек принадлежит только одному из двух классов. Вопрос состоит в том, можно ли разделить точки гиперплоскостью размерности ). Это — типичный случай линейной разделимости. Искомых гиперплоскостей может быть много, поэтому полагают, что максимизация зазора между классами способствует более уверенной классификации. То есть, можно ли найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это эквивалентно тому, что сумма расстояний до гиперплоскости от двух ближайших к ней точек, лежащих по разные стороны от неё, максимальна. Если такая гиперплоскость существует, она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.
Что делает SVM?
Алгоритм SVM находит лучшую гиперплоскость, которая находится посередине двух классов с максимальным отсупом с обеих сторон.
Опорные векторы
Точки данных, ближайшие к гиперплоскости в обоих классах, известны как опорные векторы.
Если точка данных, которая является опорным вектором, удаляется, положение гиперплоскости изменяется.
Если точка данных, не являющаяся опорным вектором, удаляется, это не влияет на модель.
Почему метод назван метод опорных векторов?
Гиперплоскость определяется опорными векторами. Если мы удалим точки данных, кроме опорных векторов, гиперплоскость не изменится. Если точка данных, которая является опорным вектором, удаляется, положение гиперплоскости изменяется.
Теперь перейдем к важным моментам.
Как найти лучшую гиперплоскость?
Как нам увеличить маржу?
Сначала давайте разберемся с математикой, лежащей в основе SVM, а затем мы перейдем к двум приведенным выше вопросам.
Математика SVM
Основной принцип SVM заключается в том, что мы хотим нарисовать гиперплоскость с максимальным отступом, разделяющим два класса. Предположим, мы хотим разделить два класса C1 и C2 с помощью SVC в двумерном пространстве. Затем мы хотим предсказать класс неизвестного вектора признаков X как класс C1 или класс C2.
Мы можем использовать линейное уравнение
w → обозначает вектор веса, перпендикулярный гиперплоскости. Он представляет ориентацию гиперплоскости в d-мерном пространстве, где d - размерность вектора признаков.
b → Он представляет положение гиперплоскости в d-мерном пространстве.
Это линейное уравнение в двух измерениях представляет собой прямую линию. Оно представляет собой плоскость в трехмерном пространстве и гиперплоскость в более чем трех измерениях.
Переходя к проблеме классификации. Для каждого вектора признаков мы должны вычислить линейную функцию таким образом, чтобы
1 Если вектор признаков лежит на положительной стороне гиперплоскости,
2. Если вектор признаков лежит на отрицательной стороне гиперплоскости,
Правило классификации:
Пример:
Давайте возьмем несколько точек данных, нарисуем гиперплоскость и вычислим значение wx + b для всех точек данных.
Вычислим линейную функцию
Для данной гиперплоскости W = -1 и b = 5
Наклон(Slope) = Изменение в Y /Изменение в X
Возьмите две точки данных на гиперплоскости (прямая линия) и найдите наклон
Две точки данных → (2,3), (1,4)
Наклон = (y1-y2) / x1-x2)
Наклон = 3–4 / 2–1 = -1
b = 5 [значение y при x = 0]
Точка лежит на гиперплоскости
(1,4) → Вектор признаков лежит на гиперплоскости.
g (X) = wX + b
g (X) = (- 1) (1,4) +5 => (-1) (1) + (- 1) (4) +5
g (X) = -1–4 + 5 = 0
г (Х) = 0
2. Вектор поддержки принадлежит метке +
(2,2) → опорный вектор принадлежит + label
g (X) = (- 1) (2,2) +5 => (- 1) (2) + (- 1) (2) +5
g (X) = - 2–2 + 5 = 1
г (Х) = 1
3. Вектор поддержки принадлежит -label
(3,3) → опорный вектор принадлежит -label
g (x) = (- 1) (3,3) +5 = (- 1) (3) + (- 1) (3) +5
g (x) = - 3–3 + 5 = -1
г (х) = - 1
4. Точка данных принадлежит отрицательной стороне гиперплоскости.
(3,4) → вектор признаков принадлежит отрицательной стороне гиперплоскости
g (x) = (- 1) (3,4) = (- 1) (3) + (- 1) (4) +5
g (x) = - 3–4 + 5 = -2
g (x) = - 2, удовлетворяющее условию g (x) <- 1
5. Точка данных принадлежит положительной стороне гиперплоскости.
(1,2) → Вектор признаков принадлежит положительной стороне гиперплоскости
g (x) = (- 1) (1,2) +5 = (- 1) (1) + (- 1) (2) +5
g (x) = - 1–2 + 5 = 3
g (x) = 3, что удовлетворяет условию g (x)> 1
Как предсказать значение неизвестного вектора признаков?
На этапе обучения SVM находит лучшую гиперплоскость и вычисляет w и b для этой гиперплоскости. Если мы хотим найти класс неизвестного вектора признаков, SVM прогнозирует, применяя значение этого вектора в уравнении.
Если значение отрицательное, оно принадлежит классу C2 [отрицательная метка], а если значение положительное, оно принадлежит классу C1 [положительная метка]
Как найти лучшую гиперплоскость?
На этапе обучения метод запускается с какой-то случайной гиперплоскости и проверяет, нет ли ошибки. Если точка данных, принадлежащая классу C1, прогнозируется как означает класс C2, тогда она изменит значение m и повернет гиперплоскость таким образом, чтобы точка данных ошибки вернулась в правильную сторону. На этапе обучения модель найдет правильные m и b, которые дают нулевую ошибку обучения.
Давайте разберемся, как он изменяет гиперплоскость, с помощью векторного исчисления.
В нарисованной случайной гиперплоскости мы получаем одну точку ошибки. Нарисуем вектор наклона m ⃗, перпендикулярный гиперплоскости. От начала вектора наклона проведите вектор к точке ошибки v
Здесь мы должны переместить точку ошибки ниже гиперплоскости. Чтобы подтолкнуть точку данных ниже линии, мы должны увеличить угол между вектором наклона и вектором данных.
Если вычесть оба вектора, угол между ними увеличится.
Во-первых, нам нужно изменить направление вектора данных, поэтому мы получим -v ⃗
Теперь добавьте этот вектор и вектор наклона.
Результирующий вектор будет новым вектором наклона. Затем нарисуйте гиперплоскость, перпендикулярную этому новому вектору уклона. Линия повернута на вектор наклона. Теперь точка ошибки находится ниже новой гиперплоскости.
Аналогичным образом SVM вычислит новый наклон для всех точек ошибки и найдет гиперплоскость, разделяющую оба класса.
Как нам увеличить отступы?
После нахождения всех возможных гиперплоскостей, разделяющих два класса, мы вычислим w и d для каждой гиперплоскости. w указывает вектор наклона гиперплоскости.
d представляет собой расстояние от ближайшей точки данных от гиперплоскости.
После сортировки значения d мы выберем гиперплоскость, которая имеет максимальное расстояние от ближайшей точки данных из обоих классов.
Реализация алгоритма SVM на наборе данных Iris.
Ссылка на GitHub → https://github.com/IndhumathyChelliah/MachineLearningAlgorithms/tree/master/SVM
Вывод
SVM используется для задач классификации и регрессии. В этой статье мы узнали, как SVM решает проблемы классификации линейно разделяемых данных. SVM также поддерживает нелинейно разделяемые данные.
Я надеюсь, что эта статья оказалась для вас полезной. Спасибо за прочтение!