Изменения

[[Файл:SVM_margin.png|300px|thumb|right|Оптимальная разделяющая гиперплоскость в $\mathbb{R}^2$]]Заметим, что при умножении $\vec{w}$ и $b$ на константу $c \neq 0$ уравнение $\langle c\vec{w}, \vec{x} \rangle - cb = 0$ определяет ту же самую гиперплоскость, что и $\langle \vec{w}, \vec{x} \rangle - b = 0$. Для удобства проведём нормировку: выберем константу $c$ таким образом, чтобы $\min\limits_i M_i(\vec{w}, b) = 1$. При этом в каждом из двух классов найдётся хотя бы один "граничный" объектобучающей выборки, отступ которого равен этому минимуму: иначе можно было бы сместить гиперплоскость в сторону класса с большим отступом, тем самым увеличив минимальное расстояние от гиперплоскости до объектов обучающей выборки. Обозначим любой "граничный" объект из класса $+1$ как $\vec{x}_+$, из класса $-1$ как $\vec{x}_-$. Их отступ равен единице, то есть $\begin{cases}M_+(\vec{w}, b) = (+1)(\langle \vec{w}, \vec{x}_+ \rangle - b) = 1 \\M_-(\vec{w}, b) = (-1)(\langle \vec{w}, \vec{x}_- \rangle - b) = 1\end{cases}$ Нормировка позволяет ограничить разделяющую полосу между классами: $\{x: -1 < \langle \vec{w}, \vec{x}_i \rangle - b < 1\}$. Внутри неё не может лежать ни один объект обучающей выборки. Ширину разделяющей полосы можно выразить как проекцию вектора $\vec{x}_+ - \vec{x}_-$ на нормаль к гиперплоскости $\vec{w}$. Чтобы разделяющая гиперплоскость находилась на наибольшем расстоянии от точек выборки, ширина полосы должна быть максимальной:  $\frac{\langle \vec{x}_+ - \vec{x}_-, \vec{w} \rangle}{\lVert w \rVert} = \frac{\langle \vec{x}_+, \vec{w} \rangle - \langle \vec{x}_-, \vec{w} \rangle - b + b}{\lVert w \rVert} = \frac{(+1)\left(\langle \vec{x}_+, \vec{w} \rangle - b\right) \, + \, (-1)\left(\langle \vec{x}_-, \vec{w} \rangle - b\right)}{\lVert w \rVert} = \\ = \frac{M_+(\vec{w}, b) \, + \, M_-(\vec{w}, b)}{\lVert w \rVert} = \frac{2}{\lVert w \rVert} \to \max \; \Rightarrow \; \lVert w \rVert \to \min$ Это приводит нас к постановке задачи оптимизации в терминах квадратичного программирования: $\begin{cases}\lVert \vec{w} \rVert^2 \to \min\limits_{w,b} \\M_i(\vec{w}, b) \geq 1, \quad i = 1, \ldots, \ell\end{cases}$ === Линейно неразделимая выборка ===

[[ФайлНа практике линейно разделимые выборки практически не встречаются:SVM_margin.png|300px|thumb|right|Оптимальная разделяющая гиперплоскость в $\mathbb{R}^2$]]Нормировка позволяет определить разделяющую полосу данных возможны выбросы и нечёткие границы между классами. В таком случае поставленная выше задача не имеет решений, как множество точеки необходимо ослабить ограничения, расстояние позволив некоторым объектам попадать на "территорию" другого класса. Для каждого объекта отнимем от которых до гиперплоскости меньше отступа некоторую положительную величину $1$: \xi_i$\{x: -1 < \langle \vec{w}, \vec{x}_i \rangle - b < 1\}$но потребуем чтобы эти введённые поправки были минимальны. Это приведёт к следующей постановке задачи:

Если $\hat{x} \in \arg\min f$ — решение задачи точка локального минимума при наложенных ограничениях, то существуют такие множители $\mu_i, i = 1\ldots m$, $\;\lambda_j, j = 1\ldots k$, что для функции Лагранжа $L(x; \mu, \lambda)$ выполняются условия:

$$\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}$$

В качестве аппроксимации функции потерь возьмём $L(x_i\lambda_i$ — переменные, y_i) = max(0, 1 - двойственные к ограничениям $M_i(w, w_0))$ Запишем функционал для метода оптимизации эмпирического риска с использованием данной функции потерь и регуляризации: $\sum\limits_{i=1}^\ell (geq 1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}xi_i$   === Линейно неразделимая выборка ===