Biorąc pod uwagę punkty danych i etykiety , podstawowym problemem z twardym marginesem SVM jest
który jest programem kwadratowym ze zmiennymi , które należy zoptymalizować dla ograniczeń i . Podwójny
to program kwadratowy z zmiennymi do optymalizacji i nierównościami i ograniczeniami równości.
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?
Odpowiedzi:
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 αi x wTx d
Rozwiązując podwójny problem, otrzymujemy (gdzie dla wszystkich oprócz kilku punktów - wektorów wsparcia). Aby sklasyfikować punkt zapytania , obliczamyα i = 0 xαi αi=0 x
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 .
źródło
<x1, x>
iwTx
. 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, tow
ix
muszą 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.Przeczytaj drugi akapit na stronie 13 i dyskusję kontynuującą go w tych notatkach:
http://cs229.stanford.edu/notes/cs229-notes3.pdf
źródło
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.
źródło
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łą.
źródło