Заметки о машинном обучении Python (6): проблема преобразования машин опорных векторов

Это второй день моего участия в августовском испытании обновлений, подробности о мероприятии:Испытание августовского обновления

6.1 Первичные и двойственные проблемы

6.1.1 Двойственная проблема

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

\begin{cases} min_w f(w)\\ s.t.{\quad}g_i(w) \le0 {\quad}i=1...k\\ s.t. {\quad}h_j(w) =0{\quad}j=1...m\\ \end{cases} \tag2

Это максимальная задача с ограничениями равенства и неравенства, мы сначала определяем две функции:

\begin{aligned} L(w,\alpha,\beta) &= f(w) + \sum^{k}_{i =1}{\alpha g_i(w)}+\sum^{m}_{j=1}{\beta h_j(w)}\\ \theta(\alpha,\beta) &= min_{w}L(w,\alpha,\beta) \end{aligned} \tag3

Затем определим двойственную задачу исходной задачи (2) как:

\begin{cases} max_{\alpha,\beta}\theta(\alpha,\beta)\\ s.t.{\quad}\alpha_i \ge 0{\quad}i=1...k \end{cases} \tag4

Отсюда делаем первый вывод: если $w^*$ есть решение исходной задачи ( $\alpha^*,\beta^*$ ) является решением двойственной задачи, то $f(w^*) \ge\theta(\alpha^*,\beta^*)$ .

Доказательство следующее:

\begin{aligned} \theta(\alpha^*,\beta^*)&=min_wL(w,\alpha^*,\beta^*)\\ &\le L(w^*,\alpha^*,\beta^*)\\ &=f(w^*) + \sum^{k}_{i =1}{\alpha^* g_i(w^*)}+\sum^{m}_{j =1}{\beta^* h_j(w^*)} \end{aligned}

так как $w^*$ есть решение исходной задачи, удовлетворяющее ограничениям исходной задачи: $g_i(w^*) \le 0, h_i(w^*)=0$ , $\alpha_i$ является решением двойственной задачи, удовлетворяющим ограничениям двойственной задачи $\alpha_i^*\ge 0$ , поэтому мы можем получить:

\begin{aligned} \sum^{k}_{i =1}{\alpha^* g_i(w^*)} & \le 0\\ \sum^{m}_{j =1}{\beta^* h_j(w^*)} & =0 \end{aligned}

завершить $f(w^*) \ge\theta(\alpha^*,\beta^*)$ .

6.1.2 Сильная теорема двойственности

Мы видим, что основная задача и двойственная задача не всегда равны, и когда соблюдается знак равенства, это называетсясильная двойственность(strong duality), когда устанавливается знак равенства? Затем нам нужно ввести сильную теорему двойственности:

Если g(w)=Aw+b, h(w) = cw+d и f(w) — выпуклая функция, то f(w^*) =\theta(\alpha^*,\beta^*)

Проще говоря, если исходная проблемавыпуклая функция, а ограниченияЛинейная функция, решение исходной задачи $f(w^*)$ равно решению двойственной функции $\theta(\alpha^*,\beta^*)$ , из-за ограниченных возможностей здесь невозможно привести подробное доказательство, если вы хотите узнать больше, вы можете обратиться к МООККурс машинного обучения профессора Ху Хаоджи из Чжэцзянского университета.

А по сильной теореме двойственности можно доказать, что для любого $i$ = 1 к k имеют $\alpha_ig_i(w)=0$ (т.е. состояние ККТ). Доказательство следующее:

\begin{aligned} f(w^*)&=\theta(\alpha^*,\beta^*)\\ &=min_wL(w,\alpha^*,\beta^*)\\ &\le L(w^*,\alpha^*,\beta^*)\\ &=f(w^*) + \sum^{k}_{i =1}{\alpha_i^* g_i(w^*)}+\sum^{m}_{j =1}{\beta_j^* h_j(w^*)} \end{aligned}

так как $w^*$ есть решение исходной задачи, удовлетворяющее ограничениям исходной задачи: $g_i(w^*) \le 0,h_i(w^*)=0$ , $\alpha_i$ является решением двойственной задачи, удовлетворяющим ограничениям двойственной задачи $\alpha_i^*\ge 0$ , поэтому мы можем получить: $\alpha_ig_i(w)=0$

6.1.3 Резюме

Комбинируя вышеизложенное, мы получаем основную проблему и двойную проблему:

Оригинальный вопрос:

\begin{cases} min_w f(w)\\ s.t.{\quad}g_i(w) \le0 {\quad}i=1...k\\ s.t. {\quad}h_j(w) =0{\quad}j=1...m\\ \end{cases}

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

\begin{cases} max_{\alpha,\beta}\theta(\alpha,\beta)\\ s.t.{\quad}\alpha_i \ge 0{\quad}i=1...k \end{cases}

\begin{aligned} \theta(\alpha,\beta) &= min_{w}L(w,\alpha,\beta)\\ L(w,\alpha,\beta) &= f(w) + \sum^{k}_{i =1}{\alpha_i g_i(w)}+\sum^{m}_{j=1}{\beta_j h_j(w)}\\ \end{aligned}

Оптимальное решение прямой задачи, удовлетворяющее сильной теореме двойственности, совпадает с оптимальным решением двойственной задачи и имеет $\alpha_ig_i(w) = 0$ .

Далее мы расскажем, как преобразовать svm в соответствующее решение двойной задачи.

6.2 Преобразование SVM в двойные задачи

Сначала мы деформируем задачу SVM, полученную в предыдущем разделе, чтобы привести ее в соответствие с формой исходной задачи (2).

\begin{cases} min_{w,b} \frac {||w||^2}{2}\\ s.t.{\quad} 1-y_i(w^Tx+b) \le 0 \end{cases}

Обратите внимание, что исходная задача svm имеет две переменные $w$ и $b$ , хотя выражение имеет только $w$ ,но $b$ Неявно ограничено ограничениями $w$ , так что здесь две переменные, а не одна.

По формуле (3) запишем соответствующую функцию от svm:

\begin{aligned} L(w,b,\alpha) &= \frac {||w||^2}{2} + \sum^{m}_{i =1}{\alpha_i (1-y_i(w^Tx+b))} \\ \theta(\alpha) &= min_{w,b}L(w,b,\alpha) \end{aligned} \tag5

Обратите внимание на разницу между (3) и (5).Поскольку исходная задача svm не имеет ограничений равенства, нет $h(w)$ и $\beta$ , наша исходная задача имеет две переменные $w$ и $b$ , $w$ вектор, $b$ является скаляром. Двойная проблема, которую мы, наконец, задаем:

\begin{cases} max_{\alpha}\theta(\alpha)\\ s.t.{\quad}\alpha_i \ge 0{\quad}i=1...m \end{cases}

Мы видим, что последняя проблема не $w$ и $b$ , поэтому сначала ставим $\theta(\alpha)$ выпишите выражение. Видно, что это всего лишь задача нахождения максимального значения, которая обычно решается с помощью производной, равной 0:

\begin{aligned} \frac{\partial L}{\partial w}&=w-\sum^{m}_{i =1}\alpha_iy_ix_i=0\\ \frac{\partial L}{\partial b}&=-\sum^{m}_{i =1}\alpha_iy_i=0 \end{aligned}

После сортировки получаем:

\begin{aligned} \sum^{m}_{i =1}\alpha_iy_ix_i&=w\\ \sum^{m}_{i =1}\alpha_iy_i&=0 \end{aligned} \tag6

Приведение (6) к (5) дает:

\theta(\alpha) = \sum^{m}_{i =1}\alpha_i - \frac{1}{2}\sum^{m}_{i =1}\sum^{m}_{j =1}\alpha_i\alpha_jy_iy_jx_i^Tx_j \tag7

Подробный процесс подробно не объясняется, обратите внимание $||w||^2 = w^Tw$ . В дополнение к полученным ранее ограничениям и условию ККТ окончательная форма двойственной задачи может быть получена как:

\begin{cases} max_\alpha (\sum^{m}_{i =1}\alpha_i - \frac{1}{2}\sum^{m}_{i =1}\sum^{m}_{j =1}\alpha_i\alpha_jy_iy_jx_i^Tx_j)\\ s.t.{\quad}\sum^{m}_{i =1}\alpha_iy_i=0\\ s.t.{\quad}\alpha_i(y_i(w^Tx_i+b)-1)=0\\ s.t.{\quad}y_i(w^Tx_i+b) \ge 0\\ s.t.{\quad} \alpha_i \ge 0 \end{cases} \tag8

Зависит от $\alpha_i(y_i(w^Tx+b)-1)=0$ Это одно условие, которое мы знаем, что либо $\alpha_i = 0$ из-за либо $(y_i(w^Tx+b)-1)=0$ .

когда $\alpha_i = 0$ когда, по $\sum^{m}_{i =1}\alpha_iy_ix_i=w$ знать $\alpha_i$ соответствующий образец $x_i$ правильно $w$ ценностьнет эффекта.

когда $y_i(w^Tx_i+b)-1=0$ время представляет образец $x_i$ заопорный вектор.

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

(8) является квадратичной задачей программирования, то есть целевая функция является квадратичной функцией, а ограничение является линейной функцией.Такая задача либо имеет единственное решение, либо не имеет решения.Для этой задачи она может быть решена квадратичным Алгоритм программирования Эффективные решения, такие как последовательная минимальная оптимизация (SMO), также могут быть разработаны в соответствии с характеристиками самой проблемы.

найти решение двойной проблемы $\alpha^*$ После этого мы можем пройти $\sum^{m}_{i =1}\alpha_iy_ix_i=w$ получить $w$ , а поскольку опорный вектор $x_i$ удовлетворить $y_i(w^Tx_i+b)=1$ доступный $b$ .

Таким образом, мы получаем классификационную гиперплоскость, когда выборки линейно разделимы:

f(x) = w^Tx +b

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

использованная литература

«Машинное обучение», Чжоу Чжихуа, издательство Университета Цинхуа

«Подробное объяснение формул машинного обучения», авторы Се Вэньруй, Цинь Чжоу, издательство People's Posts and Tele Communications Publishing House

Курс машинного обучения преподавателя Ху Хаоджи из Чжэцзянского университета в МООК