В этой статье описывается прибытие к проблеме двойственной формы с учетом задачи условной оптимизации SVM через функцию Лагранжа.
Зачем поддерживать векторную машину?
Рассмотрим бинарную классификацию в 2D, где у нас есть положительные и отрицательные точки, и мы должны определить линию, чтобы разделить положительные и отрицательные точки. Хотя мы идентифицируем одну линию, будет много линий, по которым можно классифицировать точки, и вопрос заключается в том, какая из всех возможных линий является лучшей, и решение дается с помощью машины опорных векторов, и ответ таков: линии, которые имеют максимальную маржу. Теория о том, как получить целевую функцию SVM и ограничение, не описывается, поскольку мы собираемся сосредоточиться только на двойной формулировке.
SVM выбирает наилучшую линию (гиперплоскость) таким образом, что если мы получаем новую точку данных во время теста/прогноза, она очень близка к линии классификации, она должна быть правильно классифицирована, поэтому линия имеет хороший запас между двумя разными точками данных.
Двойная формулировка
Чтобы найти такую гиперплоскость с максимальным запасом, нам нужно решить приведенную ниже задачу оптимизации SVM с ограничениями.
который можно переписать как
Идея решения проблемы A состоит в том, чтобы преобразовать приведенное выше в функцию Лагранжа.
Лагранжев метод
Одним из способов решения задачи оптимизации ограничений является использование множителя Лагранжа. Идея состоит в том, чтобы добавить еще одну переменную (называемую множителем Лагранжа) для каждого ограничения и решить ее.
Мы можем подумать, что это станет более неразрешимой проблемой, когда мы добавим новую переменную, но добавляемая нами переменная в основном связывает ограничения с функцией оптимизации.
Чтобы получить представление о функции Лагранжа на высоком уровне, мы можем описать функцию Лагранжа как
L=(OPTIMIZATION_FUNCTION) -for_each_constraint(VARIABLE *(CONSTRAINT))
Переменная здесь — это то, что мы называем МНОЖИТЕЛЕМ ЛАГРАНЖА, обычно обозначаемым буквой α.
Мы берем функцию оптимизации и вычитаем ее из суммы всех ограничений, умноженных на множитель Лагранжа. Каждое ограничение будет иметь свой собственный множитель Лангранжа.
L=(OPTIMIZATION_FUNCTION) - Σ α *(ОГРАНИЧЕНИЕ)
В нашем случае лагранжиан определяется как
Шаги для решения
- Задайте функцию Лангранжа
- Решите приведенный ниже набор уравнений
3. Решение приведенных выше уравнений даст значение w, которое можно подставить в уравнение Лагранжа C.
4. Замените D на C.
ВC у нас есть |w|², что является не чем иным, как скалярным произведением w и w, т.е. w.w
5. Перестановка терминов
Умножение второго члена на yi, а также на минус единицу
Объединение похожих терминов вместе и умножение отрицательного значения на «b».
Третий член равен нулю в соответствии с уравнением E, а первые два члена имеют форму 1/2(что-то) - 1(что-то) = -1/2(что-то)
написано как
Это двойная форма SVM, мы можем наблюдать скалярное произведение xi и xj, которое является аналогичным значением между функцией i и функцией j. Если мы решим приведенную выше задачу оптимизации, мы получим значения для альфа, и альфа будет равна нулю для других областей, но не будет равна нулю для точек опорного вектора.
Итак, на данный момент у нас есть альфа, x(признак) y(метки), и это можно подставить в уравнение D, чтобы получить векторы весов.
Преимущества двойной задачи
Преимущество двойственной задачи заключается в существовании матрицы подобия функций, представленных как xi и xj, которая полезна при кернализации, помогая легко решить задачу оптимизации.
Кредиты
Изображение баннера из: https://www.vectorstock.com/royalty-free-vector/svm-support-graph-statistic-vector-4724676
Для дальнейшего изучения есть много онлайн-ресурсов, которые можно узнать о KKT Conditions, трюках Kernal и т. д.
