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

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

Во-первых, давайте начнем с напоминания о нашей проблеме: обычно у нас есть набор данных, состоящий из m выборок, каждая выборка содержит вектор характеристик, который мы обозначаем x, и метку y в {0,1} (или {- 1,1}), предположим на данный момент, что вектор x находится в 2D, что позволит нам проиллюстрировать проблему.

Учитывая этот набор данных, мы хотим иметь модель, которая позволит нам автоматически классифицировать эти два класса, другими словами, если мы дадим вектор x в качестве входных данных для модели, она должна быть в состоянии предсказать класс, связанный с ним. Ранее мы видели, что эту проблему можно разделить на две группы: первая — если данные линейно разделимы, то есть мы можем найти гиперплоскость разделения между двумя классами, во второй категории данные не являются линейно разделимыми. сепарабельный, в данном случае граница между двумя классами моделируется более сложной моделью, оба случая проиллюстрированы на рисунке ниже

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

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

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

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

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

Давайте начнем с некоторых основных вычислений. Сначала мы обозначим через H набор точек, принадлежащих разделяющей гиперплоскости, определяемой следующим образом.

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

Поскольку x ^ p принадлежит гиперплоскости, это подтверждает следующее уравнение

Геометрически мы также имеем

а так как d параллелен w, то d= α w.

Теперь из первого уравнения имеем

и наконец

Теперь мы можем вычислить расстояние точки x от гиперплоскости H следующим образом:

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

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

Поэтому мы можем записать приведенное выше уравнение следующим образом

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

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

Обобщенный лагранжиан, связанный с этой проблемой, определяется следующим образом

Предположим, мы хотим максимизировать эту функцию и проанализировать ее поведение

У нас может быть два случая в зависимости от значения w, для значения w, которое удовлетворяет всем неравенствам, функция достигнет своего максимума при f (w) для a = 0, с другой стороны, для значения w, которое удовлетворяет не удовлетворяют всем неравенствам, мы можем найти набор (a, b) такой, что максимальное значение будет +∞.

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

И связанная с этим двойная проблема

Если обозначить решение прямой задачи через p∗, а решение двойственной задачи через d∗, то получим следующее неравенство

Если, кроме того, следующие условия KKT проверяются

Тогда решение прямой задачи равно решению двойственной. Это, следовательно, позволяет нам решить либо основную задачу, либо двойственную задачу, чтобы решить общую проблему.

Применяя все это к задаче оптимизации SVM, легко найти, что лагранжиан равен

Основная задача дается следующим образом

И связанная с этим двойная проблема

Теперь удовлетворим первому и второму условиям ККТ следующим образом

И

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

Таким образом, мы приходим к следующей промежуточной задаче

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

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

from sklearn.svm import SVC
import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets
iris = datasets.load_iris()
X = iris.data[:, :2] 
y = iris.target
y[y==2]=1

Выполнение кода дает следующий рисунок

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

def make_meshgrid(x, y, h=.02):
 x_min, x_max = x.min() - 1, x.max() + 1
 y_min, y_max = y.min() - 1, y.max() + 1
 xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
 return xx, yy
def plot_contours(ax, clf, xx, yy, **params):
  Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
  Z = Z.reshape(xx.shape)
  out = ax.contourf(xx, yy, Z, **params)
  return out
model = svm.SVC(kernel='linear')
clf = model.fit(X, y)
fig, ax = plt.subplots()
title = ('Decision surface of linear SVC ')
X0, X1 = X[:, 0], X[:, 1]
xx, yy = make_meshgrid(X0, X1)
plot_contours(ax, clf, xx, yy, cmap=plt.cm.coolwarm, alpha=0.8)
ax.scatter(X0, X1, c=y, cmap=plt.cm.coolwarm, s=20, edgecolors='k')
ax.set_ylabel('y label here')
ax.set_xlabel('x label here')
ax.set_xticks(())
ax.set_yticks(())
ax.set_title(title)
ax.legend()
plt.show()

Выполнение кода дает следующий рисунок

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

Заключение

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