В конце статьи Пошаговая математическая формулировка SVM с жесткой маржой была получена компактная функция стоимости, которую нужно было максимизировать. Для решения этой задачи максимизации можно использовать метод градиентного восхождения, реализация которого была рассмотрена в этой статье. Существует второе решение, которое преобразует задачу максимизации в задачу минимизации и решает ее с помощью квадратичного программирования.
Квадратичное программирование, грубо говоря, представляет собой метод решения квадратных уравнений относительно. некоторые условия.
Существует программный пакет на Python, предназначенный для решения задач выпуклой оптимизации, который называется «cvxopt». Один тип — это задачи квадратичного программирования. «cvxopt» предоставляет интерфейс под названием «cvxopt.solvers» для решения каждой из включенных выпуклых задач. Решатель cvxopt.solvers.qp(*args) обрабатывает задачи квадратичного программирования, «как следует из названия». Этот решатель реализован для решения задач квадратичной минимизации в следующем формате:
Следовательно, перед использованием cvxopt.solvers.qp(*args) задачи минимизации следует переставить в соответствии с приведенным выше стандартным форматом.
SVM с жесткой маржой можно сформулировать как задачу минимизации путем минимизации отрицательного значения функции стоимости, которую изначально предполагалось максимизировать.
Форма максимизации SVM с жесткой маржой:
Умножение J(α) на -1 и минимизация ⇒
До сих пор, сравнивая форму минимизации SVM с жестким запасом и стандартный формат решателя квадратичного программирования из пакета cvxopt:
Получаем следующие равенства:
Прежде чем передать условия задачи минимизации SVM в cvxopt.solvers.qp(*args), их следует преобразовать в специальный объект, называемый «матрицей», который также предоставляется cvxopt. Кроме того, термины передаются как позиционные аргументы (они должны передаваться в следующем порядке):
cvxopt.solvers.qp(P, q, G, h, A, b)
Вывод приведенного выше кода — это словарь, содержащий решение в ключе «x» вместе с другой ключевой информацией о решении. И последнее, но не менее важное: cvxopt никогда не обнуляет значения элементов решения; они приближаются, но почти никогда не достигают нуля, насколько мне известно. Поскольку мы знаем, что только несколько α отличны от нуля, следует использовать порог, чтобы обнулить любое значение, которое меньше этого значения.
Теперь, когда у нас есть все элементы, необходимые для построения решения квадратичного программирования SVM с жесткими границами, модель ООП может выглядеть так:
Попробуем это решение на тех же примерах, которые мы использовали в реализации решения градиентного восхождения.
Код идентичен предыдущей статье, за исключением того, что вместо HardMarginSVM используются экземпляры класса HardMarginSVMcvxopt. Тогда визуализация результатов будет выглядеть следующим образом.
Пример синтетических данных
Пример индивидуального набора данных Iris
