Dlaczego ludzie używają technik programowania kwadratowego (takich jak SMO) podczas obsługi SVM z jądrem? Co jest nie tak z Gradient Descent? Czy nie jest możliwe używanie go z jądrem, czy jest to po prostu zbyt wolne (i dlaczego?).
Oto nieco więcej kontekstu: starając się lepiej zrozumieć SVM, użyłem Gradient Descent do wyszkolenia liniowego klasyfikatora SVM za pomocą następującej funkcji kosztu:
Używam następujących notacji:
- to wagi cech modelu, ato parametr odchylenia.
- i th jest wektorem funkcji instancji szkoleniowej .
- i th to klasa docelowa (-1 lub 1) dla instancji .
- jest liczbą instancji treningowych.
- to hiperparametr regularyzacji.
Z tego równania wyprowadziłem (pod) wektor gradientu (w odniesieniu do i ), a zejście gradientu działało dobrze.
Teraz chciałbym rozwiązać problemy nieliniowe. Można po prostu zastąpić wszystkich iloczyn skalarny z w funkcji kosztu, gdzie jest funkcją jądra (na przykład Gaussa RBF, ), a następnie użyj rachunku różniczkowego do uzyskania wektora (pod) gradientu i kontynuuj z gradientem opadania?
Jeśli jest za wolny, dlaczego? Czy funkcja kosztu nie jest wypukła? A może dlatego, że gradient zmienia się zbyt szybko (nie jest ciągły w skali Lipschitza), więc algorytm przeskakuje przez doliny podczas zniżania, więc zbiega się bardzo wolno? Ale nawet wtedy, jak może być gorzej niż złożoność czasowa programowania kwadratowego, którą jest ? Jeśli jest to kwestia lokalnych minimów, czy Stochastic GD z symulowanym wyżarzaniem nie może ich pokonać?
źródło
Jeśli zastosujemy transformację do wszystkich wektorów masy wejściowej ( x ( i ) ), otrzymamy następującą funkcję kosztu:ϕ x(i)
Sztuczka jądra zastępuje przez K ( u , v ) . Ponieważ wektor wagi w niejesttransformowany,sztuczka jądra nie może być zastosowana do powyższej funkcji kosztu.ϕ(u)t⋅ϕ(v) K(u,v) w
Powyższa funkcja kosztu odpowiada pierwotnej formie celu SVM:
z zastrzeżeniem i ζ ( i ) ≥ 0 dla i = 1 , ⋯ , my(i)(wt⋅ϕ(x(i))+b)≥1−ζ(i)) ζ(i)≥0 i=1,⋯,m
Forma podwójna to:
Zatem sztuczka jądra może być używana tylko w przypadku podwójnej postaci problemu SVM (plus niektóre inne algorytmy, takie jak regresja logistyczna).
Teraz możesz użyć gotowych bibliotek programowania kwadratowego, aby rozwiązać ten problem, lub użyć mnożników Lagrangian, aby uzyskać funkcję nieograniczoną (funkcja podwójnego kosztu), a następnie wyszukać minimum za pomocą spadku gradientu lub innej techniki optymalizacji. Jednym z najbardziej wydajnych podejść wydaje się być algorytm SMO implementowany przez
libsvm
bibliotekę (dla jądra SVM).źródło
Mogę się mylić, ale nie widzę, jak moglibyśmy zastąpić produkty kropkowe jądrem bez przekształcania go w podwójny problem.
Jądra odwzorowują dane wejściowe pośrednio na pewną przestrzeń cech, w którejx staje się ϕ ( x ) , wówczas funkcja utraty staje się
jot( w , b ) = C∑i = 1mm a x ( 0 , 1 - y( i )( wt⋅ ϕ ( x( i )) + b ) )+12)wt⋅ w ϕ ( x( i )) będą miały wymiary ifinite, podobnie będzie w .
Jeśli zastosowane jest jądro Gaussa,
Trudno jest zoptymalizować wektor o nieskończonych wymiarach przy użyciu bezpośredniego spadku gradientu.
Zaktualizuj
odpowiedź Firebug daje sposób na zastąpienie produktów kropkowych jądrem w pierwotnym sformułowaniu.
źródło