SVM

Ищет гиперплоскость с максимальным зазором между классами; ядровой трюк добавляет нелинейность без явного перехода в новое пространство.

w, b min; \frac{1}{2} ∥ w ∥^{2} + C i \sum ξ_{i}

Что означает каждый компонент

$\frac{1}{2} ∥ w ∥^{2}$ минимизация нормы весов равносильна максимизации ширины зазора (она равна 2/‖w‖)
$C \sum ξ_{i}$ штраф за нарушения зазора. Большое C — почти не прощаем ошибок, малое — широкий зазор ценой ошибок

Ключевые тезисы

Решение определяется только опорными векторами на границе зазора.
Ядра: линейное, полиномиальное, RBF; C и γ управляют компромиссом зазора и ошибок.
Отлично работает на малых выборках высокой размерности, плохо масштабируется по числу объектов.

Подробный разбор

3 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Отступ и максимальный зазор

Что значит «лучшая» разделяющая гиперплоскость.

Разделяющих прямых бесконечно много. SVM выбирает ту, что проходит максимально далеко от обоих классов: чем шире полоса, тем устойчивее классификатор к новым данным.

M_{i} = y_{i} (w^{⊤} x_{i} + b)

Обозначения

$y$ истинное значение целевой переменной
$x$ объект: вектор признаков
$w$ веса модели — то, что подбирается при обучении
$x^{⊤}$ транспонирование: строка вместо столбца

Отступ объекта: положительный — классифицирован верно, отрицательный — ошибка, близкий к нулю — объект у самой границы

w, b min \frac{1}{2} ∥ w ∥^{2} при y_{i} (w^{⊤} x_{i} + b) \geq 1

Обозначения

$y$ истинное значение целевой переменной
$x$ объект: вектор признаков
$w$ веса модели — то, что подбирается при обучении
$∥ \cdot ∥$ норма — длина вектора
$x^{⊤}$ транспонирование: строка вместо столбца

Ширина зазора равна

2/∥ w ∥

, поэтому максимизация зазора = минимизация нормы весов

ширина зазора0.184

опорных векторов1

ошибокнет

Наклон гиперплоскости45°Сдвиг0.00

Крутите наклон и сдвиг: ширина зазора меняется, а опорными оказываются только объекты на его границе

Мягкий зазор и параметр C

Что делать, когда классы пересекаются.

w, b, ξ min \frac{1}{2} ∥ w ∥^{2} + C i = 1 \sum n ξ_{i}, y_{i} (w^{⊤} x_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0

Обозначения

$C$ параметр C: цена нарушения зазора. Большое C — почти не прощаем ошибок
$ξ_{i}$ переменная нарушения зазора: на сколько объект заходит внутрь полосы или за неё
$y$ истинное значение целевой переменной
$x$ объект: вектор признаков
$w$ веса модели — то, что подбирается при обучении
$n$ число объектов в выборке
$\sum$ суммирование по всем перечисленным элементам

Большое $C$ — почти не прощаем ошибок, узкий зазор, риск переобучения.
Малое $C$ — широкий зазор ценой ошибок, сильная регуляризация.
Эквивалентная запись через hinge loss: $\sum_{i} max (0, 1 - M_{i}) + λ ∥ w ∥^{2}$ .

MSE4.00

MAE2.00

Huber1.50

Задача

δ у Huber1.0

Режим «Классификация»: hinge обнуляется, как только отступ больше 1 — объекты вдали от границы перестают влиять

Ядровой трюк

Нелинейная граница без явного перехода в новое пространство.

Если классы разделены окружностью, в исходных признаках линейной границы нет. Но в признаках $(x_{1}^{2}, x_{2}^{2})$ та же выборка становится линейно разделимой — граница превращается в прямую.

K (a, b) = ⟨ φ (a), φ (b)⟩, K_{RBF} (a, b) = exp (- γ ∥ a - b ∥^{2})

Обозначения

$γ$ параметр ядра RBF: радиус влияния объекта
$∥ \cdot ∥$ норма — длина вектора
$⟨ a, b ⟩$ скалярное произведение: мера согласованности векторов
$exp$ экспонента

Ядро считает скалярное произведение в новом пространстве, не вычисляя само преобразование

$γ$ задаёт «радиус влияния» объекта: большое $γ$ — узкие островки вокруг точек, переобучение.
$C$ и $γ$ подбираются вместе, по логарифмической сетке.
Сложность обучения — от $O (n^{2})$ до $O (n^{3})$ : на сотнях тысяч объектов SVM уже неудобен.

Связанные темы

Метрические и ядровые методы

Ключевые тезисы

Подробный разбор

Отступ и максимальный зазор

Мягкий зазор и параметр C

Ядровой трюк

Связанные темы

k-NN65%

k-Means65%

Distance65%

Norm65%

Normalization & Standardization65%

Metric spaces65%