SVM
Support Vector Machine
- Для задач классификации
Идея: давайте искать такую гиперплоскость, которая ма$\xi$мизирует отступ до всех точек.
Вывод:
Для простоты вычтем свободный член, так разделяющая гиперплоскость проходит через 0.
Если классы линейно разделимы, то справедливо:
(неравенства 1 и 2)
(для всех точек положительного класса расстояние со знаком от разделяющей гиперплоскости больше 1, а для точек отрицательного класса меньше -1)
Справедливо, потому что $\omega$ и $\omega_0$ обучаются (подбираются при обучении), мы можем подобрать такие значения, чтобы это неравенство выполнялось при линейно разделимых классах.
Домножим неравенство 2 на -1, тогда получим margin отрицательного класса больше либо равен 1, а в неравенстве 1 margin положительного класса больше либо равен 1. Далее сложим неравнества, получим:
норма $\omega$ получилась из: возьмем числитель дроби, он зависим от $\omega$, перенормируем $\omega$ в единичный вектор, для этого поделим на норму вектора $\omega$.
$x_+ - x_-$ — это расстояние по нормали между ближайшим x+ и x-
Ма$\xi$мизируем полученную функцию.
Так как здесь скалярное произведение векторов, то тут Вторая норма вектора. Если ма$\xi$мизируем 1 делить на вторую норму, то мы минимизируем вторую норму.
Необходимо, чтобы все отступы были ≥ 1, и минимизировать вторую норму векторов. Получается двойственная задача, можем использовать методы решения двойственных задач.
Если выборка линейно не разделима, то за каждый объект, который нарушает это ограничение, будем добавлять штраф:
Почему берем линейный штраф: мы меньше, чем на 1 сидим внутри класса, расстояние линейно суммируется, поэтому логично взять линейный штраф.
Как решать?
$\xi$ меньше 0 нам не нужна (это значит, что margin еще более больше, чем 1, а нам это не нужно, мы на это ограничение не накладываем), также из (2) $\xi$ ≥ 1 - margin, а margin больше 1 нас не особо интересует. Тогда можно переписать все в формулу из нижней части скрина. 1 - margin — это по сути нижняя оценка на $\xi$. C здесь гиперпараметр для указания насколько ширина полосы важнее ошибок.
$(1 - M)_+$ — это Hinge loss, как мы это получили? Нужно понять, как $\xi$ связаны с нарушением условий margin ≥ 1, получим:
- Если $y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1$ , то $\xi_i = 0$ (условие выполняется, штраф отсутствует).
- Если $y_i (\mathbf{w} \cdot \mathbf{x}_i + b) < 1$ , то $\xi_i = 1 - y_i (\mathbf{w} \cdot \mathbf{x}_i + b)$
Это позволяет заменить $\xi_i$ выражением:
$\xi_i = \max(0, 1 - y_i (\mathbf{w} \cdot \mathbf{x}_i + b))$.
Ширина полосы это расстояние между ближайшими к разделяющей гиперплоскости объектам одного класса и другого класса (проекция вектора между ближайшими объектами классов на нормаль). Из итоговой формулы за ширину отвечает регуляризационный член, чем меньше C, тем сильнее регуляризация, тем шире полоса.
support vectors — это точки для которых $y_i (\mathbf{w} \cdot \mathbf{x}_i + b) = 1$ или (margin = 1), они лежат на границе margin