23
правки
Изменения
Нет описания правки
$\frac{1}{2} \lVert \vec{w} \rVert^2 + C \sum\limits_{i=1}^\ell \left(1 - M_i(\vec{w}, b)\right)_+ \to \min\limits_{w, b}$
Теперь научимся её решать.
{{Теорема
$$\begin{cases}\frac{\partial L}{\partial x} = 0, \quad L(x; \mu, \lambda) = f(x) + \sum\limits_{i=1}^m \mu_i g_i(x) + \sum\limits_{j=1}^k \lambda_j h_j(x) \\ g_i(x) \leq 0,\;h_j(x) = 0 \quad \text{(исходные ограничения)} \\ \mu_i \geq 0 \quad \text{(двойственные ограничения)} \\ \mu_i g_i(x) = 0 \quad \text{(условие дополняющей нежёсткости)} \end{cases}$$
При этом искомая точка является седловой точкой функции Лагранжа: минимумом по $x$ и максимумом по двойственным переменным $\mu$.
}}
$\eta_i$ — переменные, двойственные к ограничениям $\xi_i \geq 0$
Запишем необходимые условия седловой точки функции Лагранжа:
$\begin{cases}
$\begin{array}{lcl}
# $\lambda_i = 0\; \Rightarrow \; \eta_i = C; \; \xi_i = 0; \; M_i \geq 1\;$ — периферийные (неинформативные) объекты— лежат в своём классе, не влияют на выбор разделяющей гиперплоскости (см. ограничение на $\vec{w}$)# $0 < \lambda_i < C\; \Rightarrow \; 0 < \eta_i < C; \; \xi_i = 0; \; M_i = 1\;$ — опорные граничные объекты— лежат ровно на границе разделяющей полосы# $\lambda_i = СC \; \Rightarrow \; \eta_i = 0; \; \xi_i > 0; \; M_i < 1\;$ — опорные объекты-нарушители— лежат внутри разделяющей полосы либо на стороне другого класса
{{Определение
}}
$\begin{cases}
\end{cases}$
Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\ell$-мерного куба с ребром $C$ и гиперплоскости $\langle \lambda, y \rangle = 0$, что является выпуклым многогранником размерности $\ell-1$. И в этом многограннике нужно найти минимум квадратичного функционала. Существуют различные методы поиска решения: можно воспользоваться универсальным солвером задачи квадратичного программирования (CPLEX, Gurobi), либо алгоритмом, специально заточенным под поставленную задачу (SMO). После того, как мы получили вектор коэффициентов $\vec{\lambda}$, можем выразить решение прямой задачи выражается через решение двойственной:
$\begin{cases}
\end{cases}$
$a(x) = sign \left(\sum\limits_{i=1}^\ell \lambda_i y_i \langle \vec{x}_i, \vec{x} \rangle - b\right)$
