193
правки
Изменения
→Метод опорных векторов
К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\xi_i$, но требуется, чтобы введенные поправки были минимальны. В итоге постановка задачи ''SVM с мягким отступом'' (англ. ''soft-margin SVM'') выглядит следующим образом:
$\begin{cases}
\frac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^\ell l \xi_i \to \min\limits_{w, b, \xi} \\M_i(w, b) \geq 1 - \xi_i, \quad i = 1, \ldots, \ell l \\\xi_i \geq 0, \quad i = 1, \ldots, \ell l \\
\end{cases}$
Как показано в соответствующем данному алгоритму разделе, эквивалентной задачей безусловной минимизации является:
$Q(w, b) = \frac{1}{2C} \lVert w \rVert^2 + \sum\limits_{i=1}^\ell l \left(1 - M_i(w, b)\right)_+ \to \min\limits_{w, b}$
В силу неравенства $[M_{i} < 0] \leq (1 - M_{i})_{+}$, функционал $Q(w, b)$ можно рассматривать как верхнюю оценку эмпирического риска, к которому добавлен регуляризатор $\frac{1}{2C} \|w\|^2$.
