23
правки
Изменения
Нет описания правки
$\begin{cases}
\frac{\partial \mathscr{L}}{\partial w} = 0, \quad \frac{\partial \mathscr{L}}{\partial b} = 0, \quad \frac{\partial \mathscr{L}}{\partial \xi} = 0 \\\xi_i \geq 0, \quad \lambda_i \geq 0, \quad \eta_i \geq 0, && i = 1, \ldots, \ell \\\lambda_i = 0 \;\text{либо}\; M_i(\vec{w},b) = 1 - \xi_i, && i = 1, \ldots, \ell \\\eta_i = 0 \;\text{либо}\; \xi_i = 0, && i = 1, \ldots, \ell
\end{cases}$
Необходимые условия седловой точки функции Лагранжа:
$\begin{array}{lcl}
\frac{\partial \mathscr{L}}{\partial w} = \vec{w} - \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i = 0 & \Rightarrow & \vec{w} = \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i \\
\frac{\partial \mathscr{L}}{\partial b} = -\sum\limits_{i=1}^\ell \lambda_i y_i = 0 & \Rightarrow & \sum\limits_{i=1}^\ell \lambda_i y_i = 0 \\
\frac{\partial \mathscr{L}}{\partial \xi_i} = -\lambda_i - \eta_i + C = 0 & \Rightarrow & \eta_i + \lambda_i = C, \quad i = 1, \ldots, \ell
\end{array}$
Типизация объектов:
1. $\lambda_i = 0; \eta_i = C; \xi_i = 0; M_i \geq 1$ — периферийные (неинформативные) объекты
2. $0 < \lambda_i < C; 0 < \eta_i < C; \xi_i = 0; M_i = 1$ — опорные граничные объекты
3. $\lambda_i = С; \eta_i = 0; \xi_i > 0; M_i < 1$ — опорные объекты-нарушители
{{Определение
|definition=
'''Опорный объект''' (опорный вектор, англ. ''support vector'') — объект $\vec{x}_i$, соответствующий которому множитель Лагранжа отличен от нуля: $\lambda_i \neq 0$.
}}
Двойственная задача:
$\begin{cases}
-\mathscr{L}(\lambda) = -\sum\limits_{i=1}^\ell \lambda_i + \frac{1}{2} \sum\limits_{i=1}^\ell \sum\limits_{j=1}^\ell \lambda_i \lambda_j y_i y_j \langle \vec{x}_i, \vec{x}_j \rangle \to \min\limits_\lambda \\
0 \leq \lambda_i \leq C, \quad i = 1, \ldots, \ell \\
\sum\limits_{i=1}^\ell \lambda_i y_i = 0
\end{cases}$
Решение прямой задачи выражается через решение двойственной:
$\begin{cases}
\vec{w} = \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i \\
b = \langle \vec{w}, \vec{x}_i \rangle - y_i, \quad \text{для любого}\; i: \lambda_i > 0, M_i = 1
\end{cases}$
Линейный классификатор:
$a(x) = sign \left(\sum\limits_{i=1}^\ell \lambda_i y_i \langle \vec{x}_i, \vec{x} \rangle - b\right)$
=== Нелинейное обобщение, kernel trick ===
Переход к спрямляющему пространству более высокой размерности: $\psi : X \to H$.
{{Определение
|definition=
'''Ядро''' (англ. ''kernel'') — функция $K: X \times X \to \mathbb{R}$, которая является скалярным произведением в некотором гильбертовом пространстве: $K(\vec{x}_1, \vec{x}_2) = \langle \psi(\vec{x}_1), \psi(\vec{x}_2) \rangle$ при некотором $\psi : X \to H$, где $H$ — гильбертово пространство.
}}
{{Теорема
|id=kernel
|author=
|statement=
Функция $K(\vec{x}_1, \vec{x}_2)$ является ядром тогда и только тогда, когда выполнены условия: <br>
$\begin{cases}K(\vec{x}_1, \vec{x}_2) = K(\vec{x}_2, \vec{x}_1) & \text{(симметричность)} \\[1ex] \forall g: X \to \mathbb{R} \quad \int\limits_X \int\limits_X K(\vec{x}_1, \vec{x}_2) g(\vec{x}_1) g(\vec{x}_2) d \vec{x}_1 d \vec{x}_2 \geq 0 & \text{(неотрицательная определенность)}\end{cases}$
}}
== Метод опорных векторов в задаче регрессии ==
