Изменения

На практике линейно разделимые выборки практически не встречаются: в данных возможны выбросы и нечёткие границы между классами. В таком случае поставленная выше задача не имеет решений, и необходимо ослабить ограничения, позволив некоторым объектам попадать на "территорию" другого класса. Для каждого объекта отнимем от отступа некоторую положительную величину $\xi_i$, но потребуем чтобы эти введённые поправки были минимальны. Это приведёт к следующей постановке задачи, называемой также ''SVM с мягким отступом'' (англ. ''soft-margin SVM''):

\frac{1}{2} \lVert \vec{w} \rVert^2 \color{redbrown}{+ C \sum\limits_{i=1}^\ell \xi_i} \to \min\limits_{w, b, \color{redbrown}{\xi}} \\M_i(\vec{w}, b) \geq 1 \color{redbrown}{- \xi_i}, \quad i = 1, \ldots, \ell \\\color{redbrown}{\xi_i \geq 0, \quad i = 1, \ldots, \ell} \\

По теореме Каруша—Куна—Таккера, поставленная нами задача минимизации эквивалентна двойственной задаче для поиска седловой точки функции Лагранжа:

# $\lambda_i = 0 \; \Rightarrow \; \eta_i = C; \; \xi_i = 0; \; M_i \geq 1 \;$ — периферийные (неинформативные) объекты — <br> Эти объекты лежат в своём классе, классифицируются верно и не влияют на выбор разделяющей гиперплоскости (см. ограничение на уравнение для $\vec{w}$)# $0 < \lambda_i < C \; \Rightarrow \; 0 < \eta_i < C; \; \xi_i = 0; \; M_i = 1 \;$ — опорные граничные объекты — <br> Эти объекты лежат ровно на границе разделяющей полосына стороне своего класса# $\lambda_i = C \; \Rightarrow \; \eta_i = 0; \; \xi_i > 0; \; M_i < 1 \;$ — опорные объекты-нарушители — <br> Эти объекты лежат внутри разделяющей полосы либо или на стороне другого чужого класса

Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\ell$-мерного куба с ребром $C$ и гиперплоскости $\langle \lambda, y \rangle = 0$, что является выпуклым многогранником размерности $\ell-1$. И в В этом многограннике нужно найти минимум выпуклого квадратичного функционала. Следовательно, данная задача имеет единственное решение.

Существуют различные методы поиска решения: можно воспользоваться универсальным солвером задачи квадратичного программирования ([[CPLEX]], [[Gurobi]]), либо алгоритмом, специально заточенным под поставленную задачу учитывающим специфические особенности SVM ([[SMO]], [[INCAS]]).

И для удобства перепишем $b = med\{ \langle \vec{w}, \vec{x}_i \rangle - y_i : \lambda_i > 0, M_i = 1, i = 1, \ldots, \ell\}$ Теперь можем переписать наш линейный классификатор, выразив $\vec{w}$ через $\vec{\lambda}$:

Переход Существует ещё один подход к спрямляющему пространству более высокой решению проблемы линейной разделимости, известный как трюк с ядом (kernel trick). Если выборка объектов с признаковым описанием из $X = \mathbb{R}^n$ не является линейно разделимой, мы можем предположить, что существует некоторое пространство $H$, вероятно, большей размерности: , при переходе в которое выборка станет линейно разделимой. Пространство $H$ здесь называют спрямляющим, а функцию перехода $\psi : X \to H$— спрямляющим отображением.Построение SVM в таком случае происходит так же, как и раньше, но в качестве векторов признаковых описаний используются векторы $\psi(\vec{x})$, а не $\vec{x}$. Соответственно, скалярное произведение $\langle \vec{x}_1, \vec{x}_2 \rangle$ в пространстве $X$ везде заменяется скалярным произведением $\langle \psi(\vec{x}_1), \psi(\vec{x}_2) \rangle$ в пространстве $H$. Отсюда следует, что пространство $H$ должно быть гильбертовым, так как в нём должно быть определено скалярное произведение. Обратим внимание на то, что постановка задачи и алгоритм классификации не используют в явном виде признаковое описание и оперируют только скалярными произведениями признаков объектов. Это даёт возможность заменить скалярное произведение в пространстве $X$ на скалярное произведение в $H$:

'''Ядро''' (англ. ''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$ — гильбертово пространствосо скалярным произведением.

|author=Мерсер

Точный алгоритм Проверка неотрицательной определённости является довольно трудоёмкой, поэтому на практике теорема явно не используется. Проблема выбора ядер не описанлучшего ядра на сегодняшний день остаётся открытой, однако существуют исследования в области лучшие из известных на данный момент решений основываются на генетических алгоритмовалгоритмах<ref>[https://www.researchgate.net/publication/221080223_An_Evolutionary_Approach_to_Automatic_Kernel_Construction T.Howley, M.G.Madden — An Evolutionary Approach to Automatic Kernel Construction]</ref>). Обычно в практических реализациях ограничиваются перебором нескольких функций, про которые известно, что они являются ядрами, и выбирают среди них лучшую при помощи кросс-валидации. Кроме того, существуют правила порождения ядер, которые также применяются для расширения пространства перебираемых функций. 

# $K(\vec{x}_1, \vec{x}_2) = K_1(\phi(\vec{x}_1), \phi(\vec{x}_2)) \quad$ (ядро от функций композиция ядра и функции $\phi : X \to X$)

Примеры Существует несколько "стандартных" ядер, которые соответствуют известным алгоритмам классификации:

* Задача выпуклого квадратичного программирования хорошо изучена и имеет единственное решение

* Неустойчивость к шуму: выбросы в исходных данных становятся опорными объектами-нарушителями и напрямую влияют на построение разделяющей гиперплоскости* Нет общих подходов к оптимизации ядра под задачуНе описаны общие методы построения ядер и спрямляющих пространств, наиболее подходящих для конкретной задачи

* Необходимо подбирать константу $C$при помощи кросс-валидации