Глубокое понимание SVM, подробное объяснение алгоритма SMO

СегодняТемы машинного обученияВ 35-й статье мы продолжим принцип модели SVM, а сегодня объясним алгоритм SMO.

Обзор формулы

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

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

Условия КТТ, которым он должен удовлетворять, следующие:

То есть нам нужно решить экстремальное значение (1) в этих условиях.В случае этого ограничения, хотя мы упростили формулу, чтобы иметь только один параметр$\alpha$, но как получить это экстремальное значение? Для решения этой задачи нам необходимо ввести новый алгоритм, что и является основным содержанием сегодняшней статьи -Алгоритм SMO.

Введение в алгоритм SMO

Полное написание SMO — это Sequential Minimal Optimization, что переводится в алгоритм минимальной оптимизации последовательности. Основная идея алгоритма заключается в том, что нам нужно найти ряд$\alpha$такое, что (1) принимает экстремальное значение, но проблемаНам сложно одновременно оптимизировать этот ряд значений. Итак, алгоритм SMO придумал очень оригинальный способ объединить эту серию$\alpha$Два из них считаются переменными, а все остальные фиксированные значения считаются константами.

Вопрос в том, почему мы выбираем два$\alpha$Рассматривать это как переменную и не выбирать одну? Не проще ли выбрать один? Поскольку одним из наших ограничений является$\sum y_i\alpha_i=0$, так что если мы выберем только один$\alpha$Если скорректировать, то очевиднонарушит это ограничение. Итак, мы выбираем два, один из них меняется, а другой меняется вместе с ним, чтобы гарантировать, что ограничения не будут нарушены.

Для удобства описания по умолчанию выбираем два$\alpha$соответственно$\alpha_1, \alpha_2$. Кроме того, поскольку мы участвуем в$x_i^Tx_j$операция, мы делаем$K_{ij}=x_i^Tx_j$. Таким образом, вышеприведенная формула (1) может быть записана как:

из них за счет$y_1 = \pm 1$,так$y_i^2 = 1$, указанная выше Константа означает, что в дополнение к$\alpha_1, \alpha_2$другие константы. мы предполагаем, что$\alpha_1y_1 + \alpha_2y_2 = k$,в$\alpha_1, \alpha_2 \in [0, C]$,так как$y_i$Есть только два варианта, 1 или -1, поэтому мы можем обсудить это в каждом конкретном случае.

Обсуждайте в каждом конкретном случае

Сначала мы обсудим$y_1$и$y_2$Когда числа разные, типов не более двух.Первый случай$\alpha_1 - \alpha_2 = k$, это,$\alpha_2 = \alpha_1 - k$, будем считать, что k > 0 в этот момент, второй случай$\alpha_2 = \alpha_1 + k$, мы предполагаем, что k 0, это фактически первый случай. это становитсяЗадача линейного программирования, мы можем нарисовать картину очень четко.

Для первого случая мы видим, что$\alpha_2$Диапазон$(0, C - \alpha_2 + \alpha_1)$, диапазон второго случая$(\alpha_2 - \alpha_1, C)$. Здесь мы снова обозначаем k$\alpha_1,\alpha_2$, так как мы хотим оптимизировать итерационным методом$\alpha_1,\alpha_2$Значение , поэтому мы делаем предыдущий раунд$\alpha_1, \alpha_2$соответственно$\alpha_{1o}, \alpha_{2o}$. О здесь относится к старому значению.$\alpha_2$Нижняя граница L для следующего раунда равна$\max(0, \alpha_{2o} - \alpha_{1o})$, верхняя граница H равна$\min(C+\alpha_{2o} - \alpha_{1o}, C)$.

Аналогично рисуем$\alpha_1, \alpha_2$В случае одного и того же знака также есть k > 0 и k

Первый случай$y_1 = y_2 = 1$, тогда$\alpha_1 + \alpha_2 = k$, при k > 0 соответствующие$\alpha_2$Значение$(0, \alpha_{1o} + \alpha_{2o})$. Когда k > C, на этот раз также имеет место 1' в правом верхнем углу. В это время после пунктирной линии посередине$\alpha_2$Диапазон$(\alpha_{1o} + \alpha_{2o} - C, C)$.

Второй случай$y_1 = y_2 = -1$,В настоящее время$\alpha_1 + \alpha_2 = k$, в этот момент k $0\le \alpha_1, \alpha_2 \le C$, поэтому на данный момент решения нет. Комбинируя эти два случая, можно получить, что нижняя граница L равна$\max(0, \alpha_{1o} + \alpha_{2o} - C)$, последний H был$\min(\alpha_{1o} + \alpha{2o}, C)$.

Мы предполагаем, что получаем следующий раунд после перебора$\alpha_2$да$\alpha_{2new, unc}$,здесьunc означает неограниченный. Затем мы добавляем ограничения прямо сейчас, мы можем получить:

здесь$\alpha_{2new,unc}$когда мы используем вывод, чтобы получить экстремальное значение$\alpha_2$, но проблема в том, что это значение может быть недоступно из-за ограничений. Следовательно, приведенный выше ряд операций заключается в исследовании экстремальных значений, которые мы можем получить при наличии ограничений. Не имеет значения, если вы не понимаете процесс вывода, по крайней мере, этот вывод нужно понять.

Устранение замены

Теперь у нас есть новый после следующей итерации$\alpha_2$Диапазон значений , следующее, что нужно сделать, это решить проблему, которая минимизирует функцию потерь, такую ​​​​как градиентный спуск.$\alpha_1$и$\alpha_2$значение, так как$\alpha_1 + \alpha_2$Значение определено, поэтому мы можем решить одну из них.

мы заказываем$\alpha_1y_1 + \alpha_2y_2 = \xi$, то мы можем заменить$\alpha_1 = y_1(\xi - \alpha_2y_2)$

Подставляем эту формулу в исходную формулу, а полученную формулу можно исключить$\alpha_1$, так что мы получаемсодержит только$\alpha_2$формула. Мы можем думать об этом как о$\alpha_2$функцию, для дальнейшего упрощения сделаем$v_i = \sum_{j=3}^my_j \alpha_j K{i, j} , E_i = f(x_i ) - y_i = \sum_{j=1}^m \alpha_jy_jK_{i, j} + b - y_i$

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

$f(\alpha_2) = \frac12 K_{11}(\xi - \alpha_2y_2) + \frac12K_{22}\alpha_2^2 + y_2K_{12}(\xi- \alpha_2y_2)\alpha_2 - (\xi - \alpha_2y_2)y_1 - \alpha_2 + (\xi - \alpha_2y_2)v_1 + y_2\alpha_2v_2$

Далее нужно сделать эту формулуВывод и экстремальное значение, является содержанием средней школы математики.

$\frac {\partial W}{\partial\alpha_2}=K_{11}\alpha_2 + K_{22}\alpha_2 - 2K_{12}\alpha_2 - K{11}\xi y_2+K{12}\xi y_2 + y_1y_2 -1 - v_1y_2 + y_2v_2 = 0$

Решаем эту формулу и окончательно получаем:

$\alpha_{2new, unc} = \alpha_{2o} + \frac{y_2(E_1 - E_2)}{K_{11}+K_{22} - 2 K_{12}}$

Из этой формулы мы можем найти$\alpha_2$Значение после очередного раунда итераций, после того, как значение получено, мы можем сравнить его с верхней и нижней границей ограничения, и тогда мы можем получить наилучшее значение, которое можно получить при условии выполнения ограничения. Наконец, мы положили$\alpha_2$Подставить в формулу для решения$\alpha_1$. так что мы будемТакже оптимизирована пара$\alpha$параметр, алгоритм SMO на самом делеПовторно используйте описанный выше метод оптимизации, чтобы постоянно выбирать два параметра для оптимизации., пока не будет достигнуто количество итераций, или новые улучшения не могут быть внесены.

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

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

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