Глубокое понимание SVM, мягкого интервала и двойных задач

СегодняТемы машинного обученияВ 33-й статье мы продолжаем рассказывать о модели SVM.

В предыдущей статье мы подтолкнули к выводу формулы модели SVM в линейно разделимой задаче и в итоге пришли к выводу, что это квадратичный член с неравенством:

Для студентов, которые хотят понять конкретный процесс деривации, вы можете обратиться к моей предыдущей статье:

Машинное обучение | Подробный принцип SVM и построение модели (1)

На самом деле в предыдущей статье осталась проблема, то есть мы надеемся получить$||\omega||$Минимум, почему бы напрямую не попросить$||\omega||$Минимум, не требуется$||\omega||^2$Самый маленький? Причина заключается в его решении, потому что мы должны преобразовать его вЗадача выпуклого квадратичного программирования(квадратичное программирование). Проблема QP также является очень важной областью компьютерных наук, и это также более сложная область, поскольку она требует глубоких знаний компьютеров и математики.

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

Процесс решения

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

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

Давайте посмотрим на процесс использования метода множителей Лагранжа, учитывая проблему ограничения неравенства:

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

$L(x, \alpha, \beta)=f(x) + \sum_{i=1}^k \alpha_ig_i(x)+\sum_{j=1}^m \beta_jh_j(x), \quad \alpha_i \ge 0$

Эта формула выглядит проще, чем приведенная выше система уравнений, но какой от нее толк? Мы просто проанализируем его, мы найдем$L \le f(x)$. так как$\alpha_i \ge 0$,и$g_i(x) \le 0$. Итак, сложив два вместе,$L \le f(x)$,когда$\alpha_i = 0$Когда L может принимать максимальное значение, то$L = f(x)$. Итак, о чем мы просим$\max L(x, \alpha, \beta)$.

А так как цель нашего запроса$f(x)$минимальное значение , наша конечная цель$\min_{x} \max_{\alpha_i \ge 0} L(x, \alpha, \beta)$.

двойная проблема

Далее мы поговорим о знаменитомдвойная проблемаИтак, так называемая проблема двойственности — это по существу обратный порядок неравенств уравнения с двумя неравенствами. Пучок$\min \max L$превратиться в$\max \min L$, но проблема в том, что положение знака неравенства заведомо важно, а порядок нельзя изменить произвольно, поэтому нам нужно доказать, что это изменение верно.

Для удобства запишем исходную задачу в виде$\theta_P(x)=\min_x \max_{\alpha, \beta}L(x, \alpha, \beta)$, мы определяем$\alpha$и$\beta$Связанные уравнения:$\theta_D(\alpha, \beta) = \min_{x}L(x, \alpha, \beta)$. Правая часть этого уравнения представляет собой минимизацию функции Лагранжа, потому что после определения x результат уравнения будет таким же, как и$\alpha$а также$\beta$связаны, так что это$\alpha$и$\beta$Функция.

Максимизируем эту функцию:

$\max_{\alpha_i \ge 0} \theta_D(\alpha, \beta) = \max_{\alpha_i \ge 0} \min_{x} L(x, \alpha, \beta)$

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

$\theta_D(\alpha, \beta) = \max_{\alpha_i \ge 0} \min_x L(x, \alpha, \beta) \le \min_x \max_{\alpha_i \ge 0} L(x, \alpha, \beta) = \theta_P(x)$

Мы можем легко доказать эту формулу, переопределив уравнение Лагранжа:

$\min_x L(x, \alpha, \beta) \le L(x, \alpha, \beta) \le \max_{\alpha_i \ge 0} L(x, \alpha, \beta)$

Если мы хотим заменить исходную задачу на двойственную, нам нужно взять указанный выше знак неравенства. Математики уже строго доказали равенство условий уравнения Лагранжа, и нужно только удовлетворитьУсловие Каруша-Куна-Таккера(называемое состоянием КТТ). Условный вывод КТТ тоже очень сложный процесс, нам не нужно делать глубоких исследований, нужно только знать о его существовании.

Условий КТТ так много, кажется, что многие не сложные.

Сравниваем условия КТТ для решения$\theta_P(x)$Минимальное значение , это часть средней школы математики. Сначала упростим исходную формулу:

Правильно снова$\omega$и$b$Сделайте вывод:

Получаем путем вывода$\omega$и$\alpha$отношения, то есть до тех пор, пока мы определяем$\alpha$Это уж точно$\omega$, и мы можем волшебным образом обнаружить, что в приведенной выше формуле нет b, что указывает на то, что b было исключено нами. Когда мы берем экстремальное значение, полученное из приведенного выше вывода,$\omega$и$b$Подставить в исходную формулу, исключить$\omega$и$b$, вы можете получить:

Если мы будем соблюдать эту формулу, мы найдемОба x и y являются фиксированными значениямиОпределяется выборкой, единственной переменной является только$\alpha$. Что нам нужно, так это максимальное значение приведенной выше формулы, единственная переменная$\alpha$, просить$\alpha$можно вывести в соответствии с$\omega$и б.

тогда это$\alpha$Как попросить об этом? Мы поместим соответствующий контент в следующую статью.

Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).

Оригинальная ссылка, обратите внимание