min ½||w||²+CΣξᵢ; dual max Σαᵢ−½Σαᵢαⱼyᵢyⱼ⟨xᵢ,xⱼ⟩
Условие
Выпишите прямую и двойственную задачу метода опорных векторов в исходном пространстве.
Прямая задача источника
Для yᵢ∈{−1,+1}:
min_{w,b,ξ} ½||w||² + CΣᵢξᵢ
при
yᵢ(⟨w,xᵢ⟩+b) ≥ 1−ξᵢ, ξᵢ≥0.
Двойственная задача источника
max_α Σᵢαᵢ − ½Σᵢⱼ αᵢαⱼyᵢyⱼ⟨xᵢ,xⱼ⟩
при 0≤αᵢ≤C и Σᵢαᵢyᵢ=0.
Откуда берутся ограничения dual
Условие по b даёт Σαᵢyᵢ=0. Минимизация лагранжиана по ξ вместе с неотрицательностью slack приводит к верхней границе αᵢ≤C. Условие по w даёт
w=Σᵢαᵢyᵢxᵢ.
После подстановки w остаются только скалярные произведения объектов.
Опорные векторы
По условиям KKT наблюдения с αᵢ>0 влияют на w и являются опорными. При 0<αᵢ<C для типичного невырожденного случая точка лежит на margin; αᵢ=C часто соответствует объекту внутри полосы или с ошибкой.
Переход к ядрам
Именно появление данных только через ⟨xᵢ,xⱼ⟩ позволяет заменить его положительно полуопределённым K(xᵢ,xⱼ), не выписывая координаты feature space явно.
Борис Демешев и участники · mlearn_pro, задача 68 · CC BY 4.0. Обе формулировки источника сохранены; связь через KKT добавлена.