Название означает - от мягкого поля до линейной машины опорных векторов

Продвинутая часть машины опорных векторов. Я сделал самый простой вывод раньше. Друзья, кто хочет увидеть, нажмите здесьВ «Машины линейных разделимых опорных векторов».

В прошлой статье я вывел основное содержание машин опорных векторов. В том числе, почему предложена машина опорных векторов, как ее предложить, почему она называется этим именем и т. д., а также включает в себя полный математический вывод машины опорных векторов. Но мы столкнемся с проблемой, что все наши выводы основаны на линейно отделимых условиях, поэтому реальность часто не так оптимистична. Поэтому нам необходимо расширить теорию машины опорных векторов, чтобы ее можно было использовать в практических приложениях.

Существующие SVM предлагают два метода решения линейно неразделимой задачи. Во-первых, это введение мягкого интервала, а во-вторых, увеличение размера, чтобы сделать его разделяемым. Может быть, название не простое для понимания, это не имеет значения, давайте обсудим это медленно.

мягкий интервал

Два типа интервалов в предыдущей статье, геометрические интервалы и функциональные интервалы, являются жесткими интервалами. Смысл в том, чтобы убедиться, что все точки выборки разделены правильно. Потом иногда бывает так:

При выводе машины опорных векторов мы обнаружили, что основной рабочий механизм машины опорных векторов заключается в том, чтобы найти точку в категории, ближайшую к линии разделения, и настроить линию разделения, чтобы максимизировать этот интервал. В примере, показанном на рисунке, невозможно найти разделительную линию так, чтобы все точки выборки были разделены правильно. И есть только несколько моментов, которые вызывают это исключение. Затем вводим мягкий интервал. Основное значение мягкого интервала отличается от значения жесткого интервала.Разрешить некоторым точкам выборки не удовлетворять исходному ограничению, интуитивно, т. е. "терпеть” для тех точек, которые не удовлетворяют исходному ограничению.

Конечно, при максимизации интервала должно быть как можно меньше выборок, не удовлетворяющих ограничениям. Мы по-прежнему надеемся получить разделительную линию с хорошей устойчивостью к разбиению за счет небольшого числа точек, не удовлетворяющих ограничениям. Надежность отражается в количестве правильно классифицированных выборок, а эффективность обобщения достаточно высока.

Затем мы проектируем эту линейную машину опорных векторов, используя мягкий запас с математической точки зрения.

На первом этапе мы вводим резервную переменную $\xi$ . То есть "важный показатель" для смягчения жесткого интервала. Линейная неразделимость означает, что некоторые точки не удовлетворяют ограничениям, тогда ограничения с добавленными резервными переменными становятся:

Это условие требует выполнения всех точек.

и для каждой резервной переменной $\xi_i$ , мы должны заплатить определенную цену. Целевая функция принимает вид:

вявляется штрафным параметром.Чем больше, тем больше штрафуется переменная резерва. Мы включаем два значения в минимизацию целевой функции, одно состоит в том, чтобы сделать $\frac{1}{2} ||w^2||$ Как можно меньше, а интервал как можно больше, другой должен иметь как можно меньше ошибочно классифицированных точек.заключается в том, чтобы отрегулировать отношения между ними.

Тогда наша задача с линейным SVM с мягкими отступами выглядит так:

\min_{w,b,\xi} \quad \frac{1}{2}||w^2||+C \sum_{i=1}^N \xi_i

s.t. \qquad y_i(w \cdot x_i +b) \geq 1- \xi_i \quad i=1,2,...,N

Это задача выпуклого квадратичного программирования. понятный $(w,b,\xi)$ существует, доказуемотолько, иЕсть интервал решения. Это также поясняется на рисунке. Наклон постоянный, разделительная линия переводится вверх и вниз с 2-кратным интервалом, и естьинтервал.

Основная проблема выводится из двойственной задачи

Согласно исходной задаче, мы можем записать ее функцию Лагранжа следующим образом:

L(w,b,\xi,\alpha,\mu)= \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad

\frac{1}{2}||w^2||+C\sum_{i=1}^N\xi_i - \sum_{i=1}^N\alpha_i(y_i(w \cdot x_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i

Сначала найдите пару функций $w,b,\xi$ очень мало, дифференцируем его следующим образом:

\nabla_w L(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^N\alpha_iy_ix_i=0

\nabla_b L(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N \alpha_iy_i

\nabla_\xi L(w,b,\xi,\alpha,\mu)=C-\alpha_i-\mu_i

придется:

Подставьте эти выражения в исходную функцию Лагранжа, чтобы найти пару функций Лагранжа $w,b,\xi$ чрезвычайно мал. придется:

\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j)+ \sum_{i=1}^N \alpha_i

спроси об этом $\alpha$ Максимум , мы получаем нашу двойственную задачу:

\max_\alpha \quad -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j)+ \sum_{i=1}^N \alpha_i

\qquad \qquad \alpha_i \geq0 \qquad \mu_i \geq0

использовать $C-\alpha_i-\mu_i=0$ Устранить $\mu$ , оставив только переменную $\alpha$ . потому что мы, наконец, хотим решить w,b только с $\alpha$ Связанный. и запишите ограничения как $0 \leq \alpha_i \leq C$ . Затем преобразуйте целевую функцию от максимума к минимуму, этот процесс предназначен только для решения привычки. Тогда в итоге мы получим двойственную задачу исходной задачи в виде:

\min_\alpha \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j)-\sum_{i=1}^N \alpha_i

s.t. \qquad \sum_{i=1}^N \alpha_i y_i=0 \qquad \quad

\qquad \qquad \qquad \qquad 0 \leq \alpha_i \leq C \quad i=1,2,...,N

Решив эту двойственную задачу, получим $\alpha$ , то имеем следующую теорему: $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$ является решением двойственной задачи, если $\alpha^*$ компонент $\alpha_j^*$ и имеют $0<\alpha_j^*<C$ , то решение исходной задачи w^*,b^* Его можно получить следующим образом:

b^*=y_j -\sum_{i=1}^Ny_i\alpha_i^*(x_i \cdot x_j)

доказывать:

Исходная задача представляет собой выпуклое квадратичное программирование, и решение удовлетворяет условию ККТ, то есть:

\alpha^*(y_i^*(w^* \cdot x_i+b^*)-1+\xi^*)=0

Из этих трех уравнений легко решить начальное w^*,b^* .

Алгоритм машины линейных опорных векторов

Вход: обучающий набор данных,в, $x \in \chi=R^n,y_i \in \lbrace-1,+1 \rbrace \qquad i=1,2,...,N$

Выход: Гиперплоскость разделения и функция решения классификации.

Выберите параметры штрафа, построить и решить задачу выпуклого квадратичного программирования.

$\min_\alpha \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j)- \sum_{i=1}^N \alpha_i$

$s.t. \qquad\sum_{i=1}^N \alpha_i y_i=0 \qquad \quad$

$\qquad \qquad \qquad \qquad 0 \leq \alpha_i \leq C \quad i=1,2,...,N$

найти оптимальное решение $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$

2. Расчет

$w^*= \sum_{i=1}^N\alpha_i^*y_ix_i$

выберите $\alpha^*$ компонент $\alpha_j^*$ подходящие условия $0<\alpha_j^*<C$ , рассчитать:

$b^*=y_j- \sum_{i=1}^Ny_i\alpha_i^*(x_i \cdot y_i)$

Найдите разделяющую гиперплоскость:

$w^* \cdot x +b^* =0$

Отдельная функция принятия решений:

$f(x)=sign(w^* \cdot x+b^*)$

Следует отметить, что для любого $\alpha_j^*$ Удовлетворяя условиям, можно найти b^* , b^* Не уникален в теории, но на практике вам нужно выбрать только один $\alpha_j^*$ Это можно решить по алгоритму.