Зачем беспокоиться о двойной проблеме при установке SVM?

50

Для заданных точек данных и меток $x_1, \ldots, x_n \in \mathbb{R}^d$ $y_1, \ldots, y_n \in \left \{-1, 1 \right\}$ , основная задача SVM с жестким полем имеет вид

{minimize}_{w, w_{0}} \frac{1}{2} w^{T} w

$\text{minimize}_{w, w_0} \quad \frac{1}{2} w^T w$

улица \forall я : Y_{я} ({вес}^{T} {Икс}_{я} + {вес}_{0}) \geq 1

$\text{s.t.} \quad \forall i: y_i (w^T x_i + w_0) \ge 1$

которая является квадратичной программой с переменными для оптимизации и $d+1$ $i$ ограничениями . Двойственный

{разворачивания}_{α} Σ_{я знак равно 1}^{N} α_{я} - \frac{1}{2} Σ_{я знак равно 1}^{N} Σ_{J знак равно 1}^{N} Y_{я} Y_{J} α_{я} α_{J} {Икс}_{я}^{T} {Икс}_{J}

$\text{maximize}_{\alpha} \quad \sum_{i=1}^{n}{\alpha_i} - \frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{y_i y_j \alpha_i \alpha_j x_i^T x_j}}$

является квадратичной программа с

переменныхкоторые будут оптимизированы для и

неравенств и

равенства ограничений.

улица \forall я : α_{я} \geq 0 \land Σ_{я знак равно 1}^{N} Y_{я} α_{я} знак равно 0

$\text{s.t.} \quad \forall i: \alpha_i \ge 0 \land \sum_{i=1}^{n}{y_i \alpha_i} = 0$

n + 1

$n + 1$

n

$n$

n

$n$

При реализации SVM с жестким запасом, почему бы мне решить двойную проблему вместо основной проблемы? Первичная проблема выглядит для меня более «интуитивно понятной», и мне не нужно беспокоиться о пробеле дуальности, состоянии Куна-Такера и т. Д.

Это имело бы смысл мне решить двойную задачу , если , но я подозреваю , что есть более веские причины. Это тот случай? $d \gg n$

svm blubb
источник

26

Краткий ответ - ядра. Длинный ответ - keeerneeels (-;

Наиболее важной вещью двойной проблемы является введение трюка с ядром, целью которого является отображение исходных данных в пространство с более высокой размерностью.

BigeyeDestroyer

40

На основании лекционных заметок упомянутых в ответе @ user765195 (спасибо!), Наиболее очевидные причины, по-видимому, следующие:

Решая первичную задачу, мы получаем оптимальное , но ничего не знаем о . Чтобы классифицировать точку запроса нам нужно явно вычислить скалярное произведение , что может быть дорого, если $w$ $\alpha_i$ $x$ $w^Tx$ $d$ велико.

Решая двойственную задачу, получаем (где для всех, кроме нескольких точек - опорных векторов). Чтобы классифицировать точку запроса , мы вычисляем $\alpha_i$ $\alpha_i = 0$ $x$

{вес}^{T} Икс + {вес}_{0} знак равно {(Σ_{я знак равно 1}^{N} α_{я} Y_{я} {Икс}_{я})}^{T} Икс + {вес}_{0} знак равно Σ_{я знак равно 1}^{N} α_{я} Y_{я} ⟨ {Икс}_{я}, Икс ⟩ + {вес}_{0}

$w^Tx + w_0 = \left(\sum_{i=1}^{n}{\alpha_i y_i x_i} \right)^T x + w_0 = \sum_{i=1}^{n}{\alpha_i y_i \langle x_i, x \rangle} + w_0$

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

blubb
источник

6

Подожди подожди. Допустим, у вас есть два вспомогательных вектора x1 и x2. Вы не можете иметь меньше двух, верно? Вы говорите, что вычисления <x1, x> и <x2, x> быстрее, чем <w, x>?

Лев

1

@Leo: обратите внимание, что я использую <x1, x>и wTx. Первый используется в качестве символа для оценки ядра K (x1, x), которая проецирует x1 и x в очень многомерное пространство и неявно вычисляет скалярное произведение проецируемых значений. Последнее является нормальным скалярным произведением, поэтому wи xдолжно быть спроецировано явно, а затем скалярное произведение вычисляется явно. В зависимости от выбора ядра, одно явное вычисление может занять гораздо больше вычислений, чем многие оценки ядра.

blubb

1

Как я понимаю первичную проблему,

- множители Лагранжа, так почему же мы не можем решить первичную задачу, чтобы найти

? Я имею в виду, что нам, вероятно, не нужно прибегать к двойной проблеме, чтобы выяснить,

?

α

$\alpha$

α

$\alpha$

α

$\alpha$

авокадо

2

«Кроме того, поскольку теперь у нас есть скалярный продукт, включающий только векторы данных, мы можем применить трюк ядра». - Это также верно в первичной формулировке.

Firebug

2

Если люди хотят получить более подробную информацию о комментарии от @Firebug ... ознакомьтесь с уравнениями 10-12 из lib.kobe-u.ac.jp/repository/90001050.pdf (что является неограниченной версией первичного).

MrDrFenner

13

Прочитайте второй абзац на стр. 13, а обсуждение продолжите в этих заметках:

http://cs229.stanford.edu/notes/cs229-notes3.pdf

user765195
источник

17

Это отличная ссылка и однозначно отвечает на вопрос. Я думаю, что ваш ответ будет лучше оценен, если вы суммируете ответ здесь: это делает эту тему самостоятельной.

whuber

3

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

Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, SS, и Sundararajan, S., «Метод двухкоординатного спуска для линейного SVM большой шкалы», Труды 25-я Международная конференция по машинному обучению, Хельсинки, 2008.

Двойная формулировка включает в себя одно ограничение аффинного равенства и n связанных ограничений.

1. Ограничение аффинного равенства можно «исключить» из двойной формулировки.

Это можно сделать, просто взглянув на ваши данные в R ^ (d + 1) через вложение R ^ d в R ^ (d + 1), повторяя добавление одной координаты «1» к каждой точке данных, то есть R ^ d ----> R ^ (d + 1): (a1, ..., ad) | ---> (a1, ..., ad, 1).

Делая это для всех точек в обучающем наборе, переделывается проблема линейной отделимости в R ^ (d + 1) и устраняется постоянный член w0 из вашего классификатора, что, в свою очередь, устраняет ограничение аффинного равенства из двойственного.

2. По пункту 1 двойственное можно легко привести как выпуклую квадратичную оптимизационную задачу, ограничения которой являются только связанными ограничениями.

3. Теперь двойная задача может быть эффективно решена, т. Е. С помощью алгоритма спуска по двойной координате, который дает эпсилон-оптимальное решение в O (log (1 / epsilon)).

Это сделано, отмечая, что исправление всех альф, кроме одного, приводит к решению в закрытой форме. Затем вы можете циклически перебирать все альфы (например, выбирать один наугад, фиксировать все остальные альфы, вычислять решение в закрытой форме). Можно показать, что таким образом вы получите почти оптимальное решение «довольно быстро» (см. Теорему 1 в вышеупомянутой статье).

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

Вы можете получить хороший обзор вопросов численной оптимизации для SVM из презентации Стивена Райта на семинаре по вычислительному обучению (2009).

PS: я новичок здесь. Извиняюсь за то, что не умею использовать математические обозначения на этом сайте.

расширенная сеть переходов
источник

1

Информация об использовании набора текста по математике находится здесь: math.meta.stackexchange.com/questions/5020/…

Восстановите Монику

-5

По моему мнению, в заметках Эндрю Нг четко упоминалось, что основная задача 1 / || w || - это невыпуклая задача. Двойственное является выпуклой задачей, и всегда легко найти оптимальное значение выпуклой функции.

Авни Кант Рай
источник

1

Первичное SVM, как указано выше, является выпуклым.

Дугал

Зачем беспокоиться о двойной проблеме при установке SVM?

Ответы: