Po co zawracać sobie głowę podwójnym problemem przy montażu SVM?

50

Biorąc pod uwagę punkty danych i etykiety , podstawowym problemem z twardym marginesem SVM jest $x_1, \ldots, x_n \in \mathbb{R}^d$ $y_1, \ldots, y_n \in \left \{-1, 1 \right\}$

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

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

s.t. \forall i : y_{i} (w^{T} x_{i} + w_{0}) \geq 1

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

który jest programem kwadratowym ze zmiennymi , które należy zoptymalizować dla ograniczeń i . Podwójny $d+1$ $i$

{maximize}_{α} \sum_{i = 1}^{n} α_{i} - \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} y_{i} y_{j} α_{i} α_{j} x_{i}^{T} x_{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}}$

s.t. \forall i : α_{i} \geq 0 \land \sum_{i = 1}^{n} y_{i} α_{i} = 0

$\text{s.t.} \quad \forall i: \alpha_i \ge 0 \land \sum_{i=1}^{n}{y_i \alpha_i} = 0$ to program kwadratowy z zmiennymi do optymalizacji i nierównościami i ograniczeniami równości.

n + 1

$n + 1$

n

$n$

n

$n$

Kiedy wdrażam SVM z twardym marginesem, dlaczego miałbym rozwiązać podwójny problem zamiast pierwotnego? Pierwotny problem wydaje mi się bardziej „intuicyjny” i nie muszę się martwić luką w dualności, stanem Kuhna-Tuckera itp.

Rozsądne byłoby rozwiązanie podwójnego problemu, jeśli , ale podejrzewam, że istnieją lepsze powody. Czy tak jest w przypadku? $d \gg n$

svm

— blubb
źródło

26

Krótka odpowiedź to jądra. Długa odpowiedź to keeerneeels (-;

Najważniejszą kwestią podwójnego problemu jest wprowadzenie sztuczki jądra, która ma na celu zmapowanie oryginalnych danych w przestrzeń o większym wymiarze.

— BigeyeDestroyer

40

Na podstawie notatek z wykładu, o których mowa w odpowiedzi @ user765195 (dzięki!), Najbardziej widocznymi przyczynami wydają się:

Rozwiązując pierwotny problem, uzyskujemy optymalne , ale nic nie wiemy o . Aby sklasyfikować punkt zapytania , musimy jawnie obliczyć iloczyn skalarny , co może być kosztowne, jeśli jest duże. $w$ $\alpha_i$ $x$ $w^Tx$ $d$

Rozwiązując podwójny problem, otrzymujemy (gdzie dla wszystkich oprócz kilku punktów - wektorów wsparcia). Aby sklasyfikować punkt zapytania , obliczamy $\alpha_i$ $\alpha_i = 0$ $x$

w^{T} x + w_{0} = {(\sum_{i = 1}^{n} α_{i} y_{i} x_{i})}^{T} x + w_{0} = \sum_{i = 1}^{n} α_{i} y_{i} ⟨ x_{i}, x ⟩ + w_{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$

Ten termin jest bardzo skutecznie obliczany, jeśli istnieje tylko kilka wektorów pomocniczych. Ponadto, ponieważ teraz mamy produkt skalarny obejmujący wyłącznie wektory danych , możemy zastosować sztuczkę jądra .

— blubb
źródło

6

Poczekaj poczekaj. Załóżmy, że masz dwa wektory pomocnicze x1 i x2. Nie możesz mieć mniej niż dwóch, prawda? Czy mówisz, że obliczenia <x1, x> i <x2, x> są szybsze niż <w, x>?

— Leo

1

@Leo: Pamiętaj, że używam <x1, x>i wTx. Pierwszy z nich jest używany jako symbol oceny K (x1, x) jądra, która rzutuje x1 i x na przestrzeń o bardzo dużych wymiarach i domyślnie oblicza iloczyn skalarny rzutowanych wartości. To ostatnie jest to normalny iloczyn skalarny, to wi xmuszą być rzutowany bezpośrednio, a następnie oblicza się iloczyn skalarny wyraźnie. W zależności od wyboru jądra, jedno jawne obliczenie może wymagać znacznie więcej obliczeń niż wiele ocen jądra.

— blubb

1

Jak rozumiem pierwotny problem, to mnożniki Lagrange'a, więc dlaczego nie możemy rozwiązać pierwotnego problemu, aby znaleźć ? To znaczy, że prawdopodobnie nie trzeba uciekać się do dualnego, aby dowiedzieć się „s, prawda?

α

$\alpha$

α

$\alpha$

α

$\alpha$

— awokado

2

„Ponadto, ponieważ obecnie mamy produkt skalarny obejmujący wyłącznie wektory danych, możemy zastosować sztuczkę jądra”. - Dotyczy to również pierwotnego sformułowania.

— Firebug

2

Jeśli ludzie chcą więcej szczegółów na temat komentarza z @Firebug ... sprawdź równania 10-12 lib.kobe-u.ac.jp/repository/90001050.pdf (która jest nieograniczoną wersją pierwotną).

— MrDrFenner

13

Przeczytaj drugi akapit na stronie 13 i dyskusję kontynuującą go w tych notatkach:

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

— użytkownik765195
źródło

17

To świetne odniesienie i jasno odpowiada na pytanie. Myślę, że twoja odpowiedź będzie bardziej doceniona, jeśli możesz streścić odpowiedź tutaj: to sprawia, że ten wątek jest samodzielny.

— whuber

3

Oto jeden z powodów, dla których podwójne sformułowanie jest atrakcyjne z punktu widzenia optymalizacji numerycznej. Szczegóły można znaleźć w następującym artykule :

Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, SS i Sundararajan, S., „Metoda zejścia z podwójną współrzędną dla SVM o dużej skali” 25. międzynarodowa konferencja nt. Uczenia maszynowego, Helsinki, 2008.

Podwójne sformułowanie obejmuje jedno ograniczenie równości afinicznej i n ograniczenia.

1. Ograniczenie równości afinicznej można „wyeliminować” z podwójnego sformułowania.

Można to zrobić po prostu patrząc na swoje dane w R ^ (d + 1) poprzez osadzenie R ^ d w R ^ (d + 1), rezygnując z dodania pojedynczej współrzędnej „1” do każdego punktu danych, tj. R ^ d ----> R ^ (d + 1): (a1, ..., reklama) | ---> (a1, ..., reklama, 1).

Wykonanie tego dla wszystkich punktów w zestawie treningowym przekształca problem liniowej separowalności w R ^ (d + 1) i eliminuje stały składnik w0 z twojego klasyfikatora, co z kolei eliminuje ograniczenie równości afinicznej z podwójnego.

2. W punkcie 1, dual można łatwo rzutować jako wypukły kwadratowy problem optymalizacji, którego ograniczenia są tylko ograniczeniami związanymi.

3. Podwójny problem można teraz skutecznie rozwiązać, tj. Za pomocą algorytmu podwójnego współrzędnego opadania, który daje optymalne dla epsilonu rozwiązanie w O (log (1 / epsilon)).

Odbywa się to poprzez zauważenie, że naprawienie wszystkich alf z wyjątkiem jednego daje rozwiązanie w formie zamkniętej. Następnie możesz kolejno przełączać wszystkie alfy (np. Wybierając jedną losowo, naprawiając wszystkie pozostałe alfy, obliczając rozwiązanie formy zamkniętej). Można pokazać, że w ten sposób uzyskasz prawie optymalne rozwiązanie „dość szybko” (patrz Twierdzenie 1 we wspomnianym artykule).

Istnieje wiele innych powodów, dla których podwójny problem jest atrakcyjny z punktu widzenia optymalizacji, niektóre z nich wykorzystują fakt, że ma tylko jedno ograniczenie równości afinicznej (wszystkie pozostałe ograniczenia są ograniczeniami związanymi), podczas gdy inne wykorzystują obserwację, że w rozwiązaniu podwójnego problemu „często większość alf” ma wartość zero (niezerowe alfy odpowiadające wektorom wspierającym).

Dobry przegląd zagadnień optymalizacji numerycznej dla maszyn SVM można znaleźć w prezentacji Stephena Wrighta w Computational Learning Workshop (2009).

PS: Jestem tu nowy. Przepraszamy za niedostateczne wykorzystanie notacji matematycznej na tej stronie.

— aTn
źródło

1

Informacje na temat korzystania z składu matematycznego znajdują się tutaj: math.meta.stackexchange.com/questions/5020/…

— Przywróć Monikę

-5

Moim zdaniem w notatkach z wykładu Andrew ng wyraźnie zaznaczono, że pierwotny problem 1 / || w || jest problemem niewypukłym. Podwójny jest problemem wypukłym i zawsze łatwo jest znaleźć optymalną funkcję wypukłą.

— Avni Kant Rai
źródło

1

Pierwotna SVM, jak podano powyżej, jest wypukła.

— Dougal