Формулировка простых и двойственных уравнений для SVM
Основная интуиция
Прежде чем мы сможем понять алгоритм, мы должны понять некоторые интересные свойства скалярного произведения двух векторов. Для заданных x, y ∈ Rn скалярное произведение определяется формулой
<x,y> = x_{1}y_{1} + x_{2}y_{2}….. + x_{n}y_{n}
Если мы находимся в евклидовом пространстве и у нас есть линия L, проходящая через начало координат, то ω — единичный вектор, перпендикулярный L (нормаль к линии). Если вы возьмете
любого вектора x, то скалярное произведение положительно, если x находится на той же стороне L, что и ω, и отрицательно в противном случае. Скалярное произведение равно нулю тогда и только тогда, когда x находится точно на линии L, в том числе когда x является нулевым вектором. Это часто используется в качестве правила принятия решения во многих задачах классификации. На рисунке справа мы видим, что x = a + b, и, таким образом, a является проекцией x на ω. Длина a в точности равна скалярному произведению ‹x,ω›.
Формулировка цели оптимизации
Для этого я сгенерировал набор данных, который состоял из двух распределений — одного нормального со средним значением 3 и стандартным отклонением 1, а другого нормального распределения со средним значением 4 и стандартным отклонением 1. Как показано на рисунке слева, где приведены примеры положения.
представлены синим цветом, а отрицательные примеры представлены черными точками. Теперь нам нужна прямая линия между ними. Через них может проходить несколько линий, но мы не хотим, чтобы они были слишком близко к черной или синей точке. Следовательно, нам нужна линия, которая находится в центре минимального расстояния между двумя классами. Представьте, что эта линия является линией, показанной на правом рисунке. Пусть черная прямая и пунктирная линия будут чем-то вроде улицы. И мы хотим, чтобы эта улица была как можно шире. Предположим, что мы берем перпендикуляр к улице ω такой, что (u, ω) › C, где u — любая точка данных, b — константа, или мы можем сказать, что наше решающее правило
Теперь у этой проблемы все еще может быть несколько решений, поэтому теперь нам нужны ограничения. Пусть наши ограничения будут
где x+ — наши положительные обучающие примеры, а x− — наши отрицательные обучающие примеры. Пусть существует переменная отклика y такая, что она равна 1 для всех синих примеров и -1 для всех черных примеров. Мы умножаем уравнения 3 и 4 на нашу переменную отклика y и получаем ограничение
Теперь вернемся к рисунку выше и пусть H1 и H2 будут двумя точками на улице, а d1+d2 — расстоянием между ними. Сначала нужно найти d1+d2. Теперь это просто проекция, поэтому, если мы возьмем разницу между H1 и H2 и умножим на единицу нормали, мы получим ширину улицы, используя уравнение 6.
Теперь это выпуклая задача с линейными ограничениями, которую можно решить с помощью квадратичного программирования (внутренняя точка/градиентная проекция), но мы будем использовать двойственность Лагранжа, как показано ниже. Таким образом, для приведенных выше смоделированных данных у нас есть следующая граница решения с использованием вышеуказанной цели.
Нелинейно разделимый случай: двойственность Лагранжа
Но что, если данные не являются линейно разделимыми? Таким образом, нам, возможно, придется придумать другой способ получить самую широкую улицу. Поскольку наша цель выпуклая, мы можем использовать двойственность Лагранжа, чтобы получить наше решение. Предположим, что в этой оптимизации с ограничениями у нас есть следующая форма основного уравнения. Затем мы используем множители Лагранжа, поэтому находим параметры. Обобщенный лагранжиан имеет вид
где α и β — множители Лагранжа. Возьмем частную производную и этого и найдем значение для ω, α, β. Таким образом, основное уравнение для нашего SVM с использованием выпуклой цели, полученной выше, имеет вид
Теперь мы можем видеть зависимость нашей формулировки от скалярных произведений ‹x_i,x_j›. Нам это нужно, чтобы использовать функции ядра, которые в основном отображают это скалярное произведение в более высокое измерение, где данные линейно разделимы, чтобы мы могли найти самую широкую улицу в этом измерении, а затем сопоставить ее обратно с нашими данными.
Использованная литература:
