Решите и внедрите метод опорных векторов (Часть 2

Оглавление:
1. Введение
2. Найти решение для SVM Soft margin
3. Реализовать на Python
4. Оценка

1. Введение

В предыдущей части мы рассмотрели случай, когда данные полностью разделимы. Если рядом с оптимальной гиперплоскостью находятся выбросы (рис. 1.1), запас будет меньше. Поэтому предыдущий подход чувствителен к шуму.

Если есть некоторые точки данных, расположенные в направлениях, противоположных истинным классам (рис. 1.2), основная задача будет неразрешимой; следовательно, она не имеет решения.

Для решения этих проблем введем переменную ξ. Рассмотрим точки данных за пределами линий, определяющих границу. ξ — расстояние от этих точек данных до линий, определяющих границу (рисунок 1.3).

Основная проблема становится:

ξ равно нулю соответствует точкам данных, правильно классифицированным и помещенным на полях или за пределами пунктирных линий(p1, p2, p3, p4 - рисунок 1.3).
ξ больше нуля и меньше или равно единице соответствует точкам данных, правильно классифицированным и размещенным между пунктирными линиями и оптимальной гиперплоскостью(p5, p6).
ξ больше единицы соответствует точкам данных, неправильно классифицированным и расположенным на противоположной стороне гиперплоскость (p7, p8).

Ширина поля управляется константой C.
Когда C маленькое, оно фокусируется на максимизации поля, поэтому поле большое .
Когда C велико, он фокусируется на минимизации суммы ξ, поэтому поле мало.
Поскольку поле гибкий, этот подход также называется SVM SVM.

2. Найдите решение для SVM с мягкой маржой

Вспомним основную задачу:

Целевая функция является выпуклой функцией, поскольку норма является выпуклой функцией, а сумма ξ также выпукла.
Обратите внимание, что мы всегда можем найти ξi больше или равно нулю, так что:

Значит, условие Слейтера выполнено, имеет место сильная двойственность. Решение двойственной задачи является также решением основной задачи, и это решение единственно.

Функция Лагранжа:

Двойная функция:

Рассмотрим условия Каруша-Куна-Таккера:

Стационарность:

Основная осуществимость:

Двойная осуществимость:

Дополнительная нежесткость:

Заменим условия стационарности на функцию Лагранжа:

Обратите внимание, что из третьего условия стационарности и двойного условия допустимости мы имеем:

Двойственная задача Лагранжа:

3. Реализовать на Python

Мы создаем класс для SVM, этот класс наследует класс BaseModel, который предоставляет два абстрактных метода train() и predict().
В функции train() находим решение для w и b с помощью библиотеки квадратичного программирования cvxopt. Вспомним двойственную задачу Лагранжа и стандартную форму квадратичного программирования, предоставляемую cvxopt:

Параметры P, q, G, h, A, b:

Вводим эти параметры и в конце получаем лямбду:

n_samples, _ = X.shape
# вычислить входные данные для решателя cvxopt
K = (X * y[:, np.newaxis]).T
P = cvxopt.matrix( K.T.dot(K)) # P имеет форму n*n
q = cvxopt.matrix(-1 * np.ones(n_samples)) # q имеет форму n*1
G = cvxopt.matrix( np.concatenate((-1*np.identity(n_samples), np.identity(n_samples)), axis=0))
h = cvxopt.matrix(np.concatenate((np.zeros(n_samples), C*np.ones(n_samples)), axis=0))
A = cvxopt.matrix(1.0 * y, (1, n_samples))
b = cvxopt.matrix(0.0)
# решить квадратичное программирование
cvxopt.solvers.options['show_progress'] = False
solution = cvxopt.solvers.qp(P, q, G, h, A, b)
_lambda = np.ravel(решение['x'])

Вспомним условия для вычисления w и b:

S = np.where((_lambda › 1e-10) & (_lambda ‹= C))[0]
self._w = K[:, S].dot(_lambda[S])< br /> M = np.where((_lambda › 1e-10) & (_lambda ‹ C))[0]
self._b = np.mean(y[M] — X[M, :]. точка(self._w))

Для функции predict() мы вычисляем внутреннее произведение w, x, затем + b и берем знак уравнения: