Czy możliwe jest zejście gradientu dla SVM w jądrze (jeśli tak, to dlaczego ludzie używają programowania kwadratowego)?

21

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:

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \mathbf{x}^{(i)} + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$

Używam następujących notacji:

$\mathbf{w}$ to wagi cech modelu, ato parametr odchylenia. $b$
$\mathbf{x}^{(i)}$ jest wektorem funkcji instancji szkoleniowej . $i^\text{th}$
$y^{(i)}$ to klasa docelowa (-1 lub 1) dla instancji . $i^\text{th}$
$m$ jest liczbą instancji treningowych.
$C$ to hiperparametr regularyzacji.

Z tego równania wyprowadziłem (pod) wektor gradientu (w odniesieniu do $\mathbf{w}$ i $b$ ), a zejście gradientu działało dobrze.

Teraz chciałbym rozwiązać problemy nieliniowe. Można po prostu zastąpić wszystkich iloczyn skalarny $\mathbf{u}^t \cdot \mathbf{v}$ z $K(\mathbf{u}, \mathbf{v})$ w funkcji kosztu, gdzie $K$ jest funkcją jądra (na przykład Gaussa RBF, $K(\mathbf{u}, \mathbf{v}) = e^{-\gamma \|\mathbf{u} - \mathbf{v}\|^2}$ ), 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 $O({n_\text{samples}}^2 \times n_\text{features})$ ? Jeśli jest to kwestia lokalnych minimów, czy Stochastic GD z symulowanym wyżarzaniem nie może ich pokonać?

svm kernel-trick gradient-descent

— MiniQuark
źródło

6

Ustaw tak, aby i , z , gdzie jest odwzorowaniem oryginalnej macierzy wejściowej, $\mathbf w = \phi(\mathbf x)\cdot \mathbf u$ $\mathbf w^t \phi(\mathbf x)=\mathbf u^t \cdot \mathbf K$ $\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$ $\mathbf K = \phi(\mathbf x)^t\phi(\mathbf x)$ $\phi(x)$ $\mathbf x$ . Pozwala to na rozwiązanie SVM poprzez pierwotne sformułowanie. Używając notacji do utraty:

J (w, b) = C \sum_{i = 1}^{m} m a x (0, 1 - y^{(i)} (u^{t} \cdot K^{(i)} + b)) + \frac{1}{2} u^{t} \cdot K \cdot u

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{u}^t \cdot \mathbf{K}^{(i)} + b)\right)} + \dfrac{1}{2} \mathbf{u}^t \cdot \mathbf{K} \cdot \mathbf{u}$

jestmacierzą , a jestmacierzą . Żadne nie jest nieskończone. $\mathbf{K}$ $m \times m$ $\mathbf{u}$ $m \times 1$

Rzeczywiście, dual jest zwykle szybszy do rozwiązania, ale pierwotny ma również swoje zalety, takie jak przybliżone rozwiązania (które nie są gwarantowane w podwójnym sformułowaniu).

Dlaczego podwójny jest o wiele bardziej widoczny, wcale nie jest oczywisty: [1]

Historyczne powody, dla których większość badań w ostatniej dekadzie dotyczyła podwójnej optymalizacji, są niejasne . Uważamy, że dzieje się tak, ponieważ maszyny SVM zostały po raz pierwszy wprowadzone w formułowaniu twardego marginesu [Boser i in., 1992], dla których podwójna optymalizacja (z powodu ograniczeń) wydaje się bardziej naturalna. Zasadniczo jednak preferowane powinny być maszyny SVM z miękkim marginesem, nawet jeśli dane szkoleniowe są rozdzielne: granica decyzji jest bardziej solidna, ponieważ bierze się pod uwagę więcej punktów szkoleniowych [Chapelle i in., 2000]

Chapelle (2007) twierdzi, że złożoność czasowa optymalizacji zarówno pierwotnej, jak i podwójnej wynosi , najgorszym przypadkiem jest , ale przeanalizowali kwadratowe i przybliżone straty zawiasów, więc nie jest to właściwe utrata zawiasu, ponieważ nie można go rozróżnić przy użyciu metody Newtona. $\mathcal{O}\left(nn_{sv} + n_{sv}^3\right)$ $\mathcal{O}\left(n^3\right)$

_{[1] Chapelle, O. (2007). Trenowanie maszyny wektora podporowego w pierwotnej postaci. Obliczenia neuronowe, 19 (5), 1155-1178.}

— Firebug
źródło

1

+1 Czy możesz rozszerzyć także złożoność czasu

— seanv507

@ seanv507 dzięki, rzeczywiście powinienem był to rozwiązać, wkrótce zaktualizuję tę odpowiedź.

— Firebug,

4

Jeśli zastosujemy transformację do wszystkich wektorów masy wejściowej ( ), otrzymamy następującą funkcję kosztu: $\phi$ $\mathbf{x}^{(i)}$

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$

Sztuczka jądra zastępuje przez . Ponieważ wektor wagi niejesttransformowany,sztuczka jądra nie może być zastosowana do powyższej funkcji kosztu. $\phi(\mathbf{u})^t \cdot \phi(\mathbf{v})$ $K(\mathbf{u}, \mathbf{v})$ $\mathbf{w}$

Powyższa funkcja kosztu odpowiada pierwotnej formie celu SVM:

$\underset{\mathbf{w}, b, \mathbf{\zeta}}\min{C \sum\limits_{i=1}^m{\zeta^{(i)}} + \dfrac{1}{2}\mathbf{w}^t \cdot \mathbf{w}}$

z zastrzeżeniem i dla $y^{(i)}(\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b) \ge 1 - \zeta^{(i)})$ $\zeta^{(i)} \ge 0$ $i=1, \cdots, m$

Forma podwójna to:

$\underset{\mathbf{\alpha}}\min{\dfrac{1}{2}\mathbf{\alpha}^t \cdot \mathbf{Q} \cdot \mathbf{\alpha} - \mathbf{1}^t \cdot \mathbf{\alpha}}$

$\mathbf{y}^t \cdot \mathbf{\alpha} = 0$ $0 \le \alpha_i \le C$ $i = 1, 2, \cdots, m$

$\mathbf{1}$ $\mathbf{Q}$ $m \times m$ $Q_{ij} = y^{(i)} y^{(j)} \phi(\mathbf{x}^{(i)})^t \cdot \phi(\mathbf{x}^{(j)})$

$Q_{ij}$

$Q_{ij} = y^{(i)} y^{(j)} K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$

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 libsvmbibliotekę (dla jądra SVM).

— MiniQuark
źródło

1

Nie jestem pewien, dlaczego zaznaczyłeś swoją odpowiedź Community Wiki. To wydaje się być poprawną odpowiedzią na twoje pytanie.

— Sycorax mówi Przywróć Monikę

Dzięki @GeneralAbrial. Oznacziłem swoją odpowiedź jako Wiki Wiki, aby uniknąć podejrzeń, że znałem odpowiedź przed zadaniem pytania.

— MiniQuark,

1

Zawsze powinieneś robić to, co uważasz za słuszne, ale zadawanie pytań i odpowiadanie na własne pytanie jest całkowicie koszerne.

— Sycorax mówi Przywróć Monikę

Czekaj, czy nie możesz przekształcić wektora ciężaru w

w = ϕ (x) \cdot u

$\mathbf w = \phi(x)\cdot \mathbf u$ po to aby

w^{t} ϕ (x) = u \cdot K

$\mathbf w^t \phi(x)=\mathbf u \cdot \mathbf K$ i

w^{t} w = u^{t} K u

$\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$ , z

K = ϕ^{t} ϕ

$\mathbf K = \phi^t\phi$ , a następnie zoptymalizuj wagi próbek

u

$\mathbf u$ ?

— Firebug,

2

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órej $x$ staje się $\phi(x)$ , wówczas funkcja utraty staje się
$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$
Jeśli zastosowane jest jądro Gaussa, $\phi(\mathbf{x}^{(i)})$ będą miały wymiary ifinite, podobnie będzie $\mathbf{w}$ .

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.

— dontloo
źródło