Изменения

Перейти к: навигация, поиск

Метод опорных векторов (SVM)

2843 байта добавлено, 21:39, 2 апреля 2019
Нет описания правки
$\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}
Типизация объектовЗаметим, что $\eta_i \geq 0$, $\lambda_i \geq 0$, $C > 0$, поэтому из последнего ограничения получаем $0 \leq \eta_i \leq C$, $0 \leq \lambda_i \leq C$.  Диапазон значений $\lambda_i$ (которые, как указано выше, соответствуют ограничениям на величину отступа) позволяет нам разделить объекты обучающей выборки на три типа:
# $\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\;$ — опорные объекты-нарушители— лежат внутри разделяющей полосы либо на стороне другого класса
{{Определение
}}
 Двойственная задачаТеперь подставим ограничения, которые мы получили при дифференцировании, в функцию Лагранжа. Получим следующую постановку двойственной задачи, которая зависит только от двойственных переменных $\lambda$:
$\begin{cases}
\end{cases}$
Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\ell$-мерного куба с ребром $C$ и гиперплоскости $\langle \lambda, y \rangle = 0$, что является выпуклым многогранником размерности $\ell-1$. И в этом многограннике нужно найти минимум квадратичного функционала. Существуют различные методы поиска решения: можно воспользоваться универсальным солвером задачи квадратичного программирования (CPLEX, Gurobi), либо алгоритмом, специально заточенным под поставленную задачу (SMO). После того, как мы получили вектор коэффициентов $\vec{\lambda}$, можем выразить решение прямой задачи выражается через решение двойственной:
$\begin{cases}
\end{cases}$
Линейный И для удобства перепишем линейный классификатор, выразив $\vec{w}$ через $\vec{\lambda}$:
$a(x) = sign \left(\sum\limits_{i=1}^\ell \lambda_i y_i \langle \vec{x}_i, \vec{x} \rangle - b\right)$
23
правки

Навигация