23
правки
Изменения
Нет описания правки
== Метод опорных векторов в задаче классификации ==
Пусть задана обучающая выборка пар "объект-ответ": $X^\ell = (\vec{x}_i, y_i)_{i=1}^\ell$. Необходимо построить алгоритм классификации $a(\vec{x}) : X \to Y$. === signРазделяющая гиперплоскость === В пространстве $\mathbb{R}^n$ уравнение $\left(langle \sumvec{w}, \limits_vec{jx} \rangle - b =0$ при заданных $\vec{w}$ и $b$ определяет гиперплоскость — (n-1)-мерное множество векторов $\vec{x}= (x^1, \ell w_j ldots, x^j n)$. Для $\mathbb{R}^1$ это точка, для $\mathbb{R}^2$ — прямая, для $\mathbb{R}^3$ — плоскость и т.д. Эта гиперплоскость делит $\mathbb{R}^n$ на два полупространства: $\langle \vec{w}, \vec{x} \rangle - w_0b > 0$ и $\langle \vec{w}, \vec{x} \rangle - b < 0$. Говорят, что гиперплоскость разделяет два класса $C_1$ и $C_2$, если выполнено $\begin{cases}\langle \vec{w}, \vec{x} \rangle - b > 0, && \forall x \in C_1 \\right) = sign(\langle \vec{w}, \vec{x } \rangle - w_0)$b < 0, && \forall x \in C_2\end{cases}$ либо
=== Оптимальная разделяющая гиперплоскость Линейно разделимая выборка ===
Пусть выборка линейно разделима, то есть существуют такие значения параметров существует некоторая гиперплоскость, разделяющая классы $w-1$ и $w_0+1$, для которых функционал количества ошибок равен нулю.
{{Определение
}}
[[Файл:SVM_margin.png|300px|thumb|right]]
Возьмём в качестве алгоритма классификации $a(x) : X \to Y$ линейный пороговый классификатор:
$$a(x) = sign\left(\sum\limits_{j=1}^\ell w_j x^j - w_0\right) = sign(\langle w, x \rangle - w_0)$$
где $x = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $w = (w_1, \ldots, w_n)$ и $w_0 \in \mathbb{R}$ — параметры алгоритма.
{{Теорема
$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$
=== Линейно неразделимая выборка ===
