Jaka jest intuicja za tym, że SVM z jądrem gaussowskim ma nieskończoną przestrzeń wymiarową?

Ta odpowiedź wyjaśnia, co następuje:

1. Dlaczego idealna separacja jest zawsze możliwa z wyraźnymi punktami i jądrem Gaussa (o wystarczająco małej przepustowości)
2. Jak ten rozdział można interpretować jako liniowy, ale tylko w abstrakcyjnej przestrzeni cech odrębnej od przestrzeni, w której żyją dane
3. Jak „mapowanie” z przestrzeni danych na przestrzeń cech jest „znalezione”. Spoiler: nie jest wykrywany przez SVM, jest domyślnie zdefiniowany przez wybrane jądro.
4. Dlaczego przestrzeń cech jest nieskończenie wymiarowa.

1. Osiągnięcie idealnej separacji

Idealne rozdzielenie jest zawsze możliwe w przypadku jądra Gaussa (pod warunkiem, że żadne dwa punkty z różnych klas nigdy nie są dokładnie takie same) ze względu na właściwości lokalizacji jądra, które prowadzą do arbitralnie elastycznej granicy decyzji. W przypadku wystarczająco małej przepustowości jądra granica decyzyjna będzie wyglądać tak, jakbyś tylko narysował małe kółka wokół punktów, ilekroć są one potrzebne do oddzielenia pozytywnych i negatywnych przykładów:

( Źródło: internetowy kurs uczenia maszynowego Andrew Ng ).

Dlaczego więc dzieje się to z matematycznego punktu widzenia?

Rozważ standardową konfigurację: masz jądro Gaussa i dane treningowe gdzie wartości wynoszą . Chcemy nauczyć się funkcji klasyfikatora$K(\mathbf{x},\mathbf{z}) = \exp(-||\mathbf{x}-\mathbf{z}||^2 / \sigma^2)$$(\mathbf{x}^{(1)},y^{(1)}), (\mathbf{x}^{(2)},y^{(2)}), \ldots, (\mathbf{x}^{(n)},y^{(n)})$$y^{(i)}$$\pm 1$

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x})$$

Jak teraz przypiszemy wagi ? Czy potrzebujemy nieskończonych przestrzeni wymiarowych i algorytmu programowania kwadratowego? Nie, ponieważ chcę tylko pokazać, że mogę doskonale rozdzielić punkty. Czynię więc miliard razy mniejszą niż najmniejsza separacjapomiędzy dowolnymi dwoma przykładami treningu, a ja właśnie ustawiłem . Oznacza to, że wszystkie punkty treningowe są oddalone o miliard sigmas, jeśli chodzi o jądro, a każdy punkt całkowicie kontroluje znak w jego sąsiedztwie. Formalnie mamy$w_i$$\sigma$$||\mathbf{x}^{(i)} - \mathbf{x}^{(j)}||$$w_i = 1$$\hat{y}$

$$\hat{y}(\mathbf{x}^{(k)}) = \sum_{i=1}^n y^{(k)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} K(\mathbf{x}^{(k)},\mathbf{x}^{(k)}) + \sum_{i \neq k} y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} + \epsilon$$

gdzie jest dowolną niewielką wartością. Wiemy, że jest malutki, ponieważ jest o miliard sigma od jakiegokolwiek innego punktu, więc dla wszystkich mamy$\epsilon$$\epsilon$$\mathbf{x}^{(k)}$$i \neq k$

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = \exp(-||\mathbf{x}^{(i)} - \mathbf{x}^{(k)}||^2 / \sigma^2) \approx 0.$$

Ponieważ jest tak mały, zdecydowanie ma taki sam znak jak , a klasyfikator osiąga doskonałą dokładność danych treningowych.$\epsilon$$\hat{y}(\mathbf{x}^{(k)})$$y^{(k)}$

2. Uczenie się SVM jądra jako separacji liniowej

Fakt, że można to interpretować jako „idealne rozdzielenie liniowe w nieskończonej przestrzeni cech wymiarowych” pochodzi z sztuczki jądra, która pozwala interpretować jądro jako produkt wewnętrzny w przestrzeni cech (potencjalnie nieskończenie wymiarowych):

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(j)}) = \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x}^{(j)})\rangle$$

gdzie jest mapowaniem z przestrzeni danych na przestrzeń cech. Wynika z tego natychmiast, że funkcja jako funkcja liniowa w przestrzeni cech:$\Phi(\mathbf{x})$$\hat{y}(\mathbf{x})$

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x})\rangle = L(\Phi(\mathbf{x}))$$

gdzie funkcja liniowa jest zdefiniowana w wektorach przestrzeni cech jako$L(\mathbf{v})$$\mathbf{v}$

$$L(\mathbf{v}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\mathbf{v}\rangle$$

Ta funkcja jest liniowa w ponieważ jest to po prostu liniowa kombinacja produktów wewnętrznych ze stałymi wektorami. W przestrzeni cech granica decyzji to po prostu , zestaw poziomów funkcji liniowej. To jest właśnie definicja hiperpłaszczyzny w przestrzeni cech.$\mathbf{v}$$\hat{y}(\mathbf{x}) = 0$$L(\mathbf{v}) = 0$

3. Zrozumienie mapowania i przestrzeni obiektów

Uwaga: W tej sekcji notacjaodnosi się do dowolnego zestawupunktów, a nie danych treningowych. To jest czysta matematyka; dane treningowe w ogóle nie mieszczą się w tej sekcji!$\mathbf{x}^{(i)}$$n$

Metody jądra nigdy tak naprawdę nie „ jawnie ” lub „obliczają” przestrzeni cech ani mapowania . Metody uczenia się jądra, takie jak SVM, nie potrzebują ich do działania; Potrzebują one jedynie funkcję jądra .$\Phi$$K$

To powiedziawszy, można zapisać formułę dla . Przestrzeń funkcji, na którą mapuje jest w pewnym sensie abstrakcyjna (i potencjalnie nieskończenie wymiarowa), ale w gruncie rzeczy mapowanie wykorzystuje jądro do wykonania prostej inżynierii cech. Jeśli chodzi o wynik końcowy, model, którego się nauczyłeś, używając jądra, nie różni się od tradycyjnej inżynierii cech popularnie stosowanej w regresji liniowej i modelowaniu GLM, jak zapisywanie logu dodatniej zmiennej predykcyjnej przed wprowadzeniem jej do formuły regresji. Matematyka jest głównie po to, aby upewnić się, że jądro dobrze współpracuje z algorytmem SVM, który ma swoje chwalone zalety rzadkości i skalowania do dużych zestawów danych.$\Phi$$\Phi$

Jeśli nadal jesteś zainteresowany, oto jak to działa. Zasadniczo bierzemy tożsamość, którą chcemy zachować, i skonstruuj produkt przestrzenny i wewnętrzny tak, aby był on zgodny z definicji. Aby to zrobić, definiujemy abstrakcyjną przestrzeń wektora której każdy wektor jest funkcją od przestrzeni, w której żyją dane, , do liczb rzeczywistych . Wektor w jest funkcją utworzoną ze skończonej liniowej kombinacji wycinków jądra: Wygodnie jest pisać bardziej kompaktowo jako $\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \rangle = K(\mathbf{x},\mathbf{y})$$V$$\mathcal{X}$$\mathbb{R}$$f$$V$

$$f(\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$ $f$ $$f = \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}$$ gdzie to funkcja dająca „kawałek” jądra w .$K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y})$$\mathbf{x}$

Produkt wewnętrzny w przestrzeni nie jest zwykłym produktem kropkowym, ale abstrakcyjnym produktem wewnętrznym opartym na jądrze:

$$\langle \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}, \sum_{j=1}^n \beta_j K_{\mathbf{x}^{(j)}} \rangle = \sum_{i,j} \alpha_i \beta_j K(\mathbf{x}^{(i)},\mathbf{x}^{(j)})$$

Po zdefiniowaniu w ten sposób przestrzeni funkcji jest mapowaniem , przenosząc każdy punkt do „wycinka jądra” w tym punkcie:$\Phi$$\mathcal{X} \rightarrow V$$\mathbf{x}$

$$\Phi(\mathbf{x}) = K_\mathbf{x}, \quad \text{where} \quad K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y}).$$

Możesz udowodnić, że jest wewnętrzną przestrzenią produktu, gdy jest dodatnim określonym jądrem. Zobacz ten artykuł, aby uzyskać szczegółowe informacje. (Uznanie dla f coppens za wskazanie tego!)$V$$K$

4. Dlaczego przestrzeń cech jest nieskończenie wymiarowa?

Ta odpowiedź daje ładne wyjaśnienie algebry liniowej, ale oto geometryczna perspektywa, z intuicją i dowodem.

Intuicja

Dla dowolnego punktu stałego mamy funkcję wycinka jądra . Wykres to tylko garb Gaussa wypośrodkowany w . Teraz, gdyby przestrzeń cech była tylko skończona, oznaczałoby to, że moglibyśmy wziąć skończony zestaw wypukłości w ustalonym zestawie punktów i utworzyć dowolną wypukłość Gaussa gdziekolwiek indziej. Ale najwyraźniej nie możemy tego zrobić; nie możesz zrobić nowego guzka ze starych guzów, ponieważ nowy guz może być naprawdę daleko od starych. Bez względu na to, ile mamy wektorów cech (wypukłości), zawsze możemy dodawać nowe wypukłości, a w przestrzeni cech są to nowe niezależne wektory. Zatem przestrzeń cech nie może być skończona; to musi być nieskończone.$\mathbf{z}$$K_\mathbf{z}(\mathbf{x}) = K(\mathbf{z},\mathbf{x})$$K_\mathbf{z}$$\mathbf{z}$

Dowód

Używamy indukcji. Załóżmy, że masz dowolny zestaw punktów tak że wektory są liniowo niezależne w przestrzeni cech. Teraz znajdź punkt różniący się od tych punktów, w rzeczywistości miliard sigmas od nich wszystkich. Twierdzimy, że jest liniowo niezależny od pierwszych wektorów cech .$\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \ldots, \mathbf{x}^{(n)}$$\Phi(\mathbf{x}^{(i)})$$\mathbf{x}^{(n+1)}$$n$$\Phi(\mathbf{x}^{(n+1)})$$n$$\Phi(\mathbf{x}^{(i)})$

Dowód sprzeczności. Załóżmy, że wręcz przeciwnie

$$\Phi(\mathbf{x}^{(n+1)}) = \sum_{i=1}^n \alpha_i \Phi(\mathbf{x}^{(i)})$$

Teraz weź wewnętrzny produkt po obu stronach za pomocą dowolnego . Poprzez tożsamość , otrzymujemy$\mathbf{x}$$\langle \Phi(\mathbf{z}), \Phi(\mathbf{x}) \rangle = K(\mathbf{z},\mathbf{x})$

$$K(\mathbf{x}^{(n+1)},\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$

Tutaj jest zmienną swobodną, ​​więc to równanie jest tożsamością stwierdzającą, że dwie funkcje są takie same. W szczególności mówi, że gaussowski wyśrodkowany w może być reprezentowany jako liniowa kombinacja Gaussian w innych punktach . Geometrycznie oczywiste jest, że nie można stworzyć guussowskiego guza wyśrodkowanego w jednym punkcie ze skończonej kombinacji guussowskich guarów wyśrodkowanych w innych punktach, szczególnie gdy wszystkie te inne guussowskie guzy znajdują się w odległości miliarda sigm. Zatem nasze założenie o liniowej zależności doprowadziło do sprzeczności, jak postanowiliśmy to pokazać.$\mathbf{x}$$\mathbf{x}^{(n+1)}$$\mathbf{x}^{(i)}$

Macierz jądra jądra Gaussa ma zawsze pełną rangę dla odrębnych . Oznacza to, że za każdym razem, gdy dodasz nowy przykład, ranga wzrasta o . Najłatwiej to zobaczyć, jeśli ustawisz bardzo mały. Wtedy macierz jądra jest prawie przekątna.$\mathbf x_1,...,\mathbf x_m$$1$$\sigma$

Fakt, że ranga zawsze wzrasta o jeden oznacza, że ​​wszystkie rzuty w przestrzeni cech są liniowo niezależne (nie ortogonalne, ale niezależne). Dlatego każdy przykład dodaje nowy wymiar do rozpiętości rzutów . Ponieważ możesz dodać niezliczoną liczbę nieskończenie wielu przykładów, przestrzeń cech musi mieć nieskończony wymiar. Co ciekawe, wszystkie rzuty przestrzeni wejściowej do przestrzeni cech leżą na kuli, ponieważ . Niemniej jednak geometria kuli jest płaska. Możesz przeczytać więcej na ten temat w$\Phi(\mathbf x)$$\Phi(\mathbf x_1),...,\Phi(\mathbf x_m)$$||\Phi(\mathbf x)||_{\mathcal H}^²=k(\mathbf x,\mathbf x)=1$

Burges, CJC (1999). Geometria i niezmienność w metodach opartych na jądrze. W B. Schölkopf, CJC Burges i AJ Smola (red.), Advances in Kernel Methods Support Vector Learning (s. 89–116). MIT Naciśnij.

Dla tła i notacji odsyłam do odpowiedzi Jak obliczyć granicę decyzji z wektorów pomocniczych? .

Zatem cechami w „oryginalnej” przestrzeni są wektory , wynik binarny a mnożniki Lagrange'a to .$x_i$$y_i \in \{-1, +1\}$$\alpha_i$

Wiadomo, że jądro można zapisać jako („ ” oznacza produkt wewnętrzny). Gdzie jest (domyślny i nieznany) transformacja do nowej przestrzeni funkcji.$K(x,y)=\Phi(x) \cdot \Phi(y)$$\cdot$$\Phi$

Spróbuję podać „intuicyjne” wyjaśnienie tego , jak wygląda ten , więc ta odpowiedź nie jest formalnym dowodem, chce tylko dać poczucie, jak myślę, że to działa. Nie wahaj się mnie poprawić, jeśli się mylę. Podstawą mojego wyjaśnienia jest sekcja 2.2.1 tego pliku pdf$\Phi$

Muszę „przekształcić” moją przestrzeń cech (czyli mój ) w jakąś „nową” przestrzeń cech, w której zostanie rozwiązana separacja liniowa.$x_i$

Dla każdej obserwacji definiuję funkcje , więc mam funkcję dla każdego elementu mojej próbki treningowej. Te funkcje obejmują przestrzeń wektorową. Przestrzeń wektorowa rozciągnięta przez , zwróć uwagę, że . ( jest wielkością próbki treningowej).$x_i$$\phi_i(x)=K(x_i,x)$$\phi_i$$\phi_i$$\phi_i$$V=span(\phi_{i, i=1,2,\dots N})$$N$

Spróbuję argumentować, że ta przestrzeń wektorowa jest przestrzenią wektorową, w której możliwe będzie rozdzielenie liniowe. $V$ Z definicji zakresu każdy wektor w przestrzeni wektorowej można zapisać jako liniową kombinację , tj .: , gdzie to liczby rzeczywiste. W rzeczywistości$V$$\phi_i$$\sum_{i=1}^N \gamma_i \phi_i$$\gamma_i$$V=\{v=\sum_{i=1}^N \gamma_i \phi_i|(\gamma_1,\gamma_2,\dots\gamma_N) \in \mathbb{R}^N \}$

Zauważ, że są współrzędnymi wektora w przestrzeni wektorowej .$(\gamma_1,\gamma_2,\dots\gamma_N)$$v$$V$

$N$ jest wielkością próbki treningowej, a zatem wymiar przestrzeni wektorowej może wzrosnąć do , w zależności od tego, czy są liniowo niezależne. Ponieważ (patrz wyżej, zdefiniowaliśmy w ten sposób), oznacza to, że wymiar zależy od użytego jądra i może wzrosnąć do wielkości próbki szkoleniowej.$V$$N$$\phi_i$$\phi_i(x)=K(x_i,x)$$\phi$$V$

Jeśli jądro jest „wystarczająco złożone”, wtedy będą wszystkie niezależne, a następnie wymiar będzie , czyli wielkość próbki treningowej.$\phi_i(x)=K(x_i, x)$$V$$N$

Transformacja, która odwzorowuje moją oryginalną przestrzeń obiektów na jest zdefiniowana jako$V$

$\Phi: x_i \to \phi_i(x)=K(x_i, x)$ .

Ta mapa odwzorowuje moją oryginalną przestrzeń obiektów na przestrzeń wektorową, która może mieć wymiar zbliżony do wielkości mojej próbki treningowej. $\Phi$Tak więc mapuje każdą obserwację w mojej próbce treningowej na przestrzeń wektorową, w której wektory są funkcjami. Wektor z mojej próbki treningowej jest „mapowany” na wektor w , mianowicie wektor o współrzędnych równych zeru, z tym wyjątkiem, że -ta współrzędna to 1.$\Phi$$x_i$$V$$\phi_i$$i$

Oczywiście ta transformacja (a) zależy od jądra, (b) zależy od wartości w próbce treningowej i (c) może, w zależności od mojego jądra, mieć wymiar, który idzie w górę do wielkości mojej próbki treningowej i ( d) wektory wyglądają jak , gdzie to liczby rzeczywiste.$x_i$$V$$\sum_{i=1}^N \gamma_i \phi_i$$\gamma_i$

Patrząc na funkcję w Jak obliczyć granicę decyzji z wektorów wsparcia? widać, że . Granica decyzji znaleziona przez SVM wynosi .$f(x)$$f(x)=\sum_i y_i \alpha_i \phi_i(x)+b$$f(x)=0$

Innymi słowy, jest liniową kombinacją a to liniowa hiperpłaszczyzna oddzielająca w przestrzeni : jest to szczególny wybór a mianowicie ! $f(x)$$\phi_i$ $f(x)=0$$V$$\gamma_i$$\gamma_i=\alpha_i y_i$

W są znane z naszych uwag są mnożniki Lagrange'a, że SVM znalazła. Innymi słowy SVM znalezisku, dzięki zastosowaniu jądra i rozwiązując zadania programowania kwadratowego, liniowy separacji w -spave.$y_i$$\alpha_i$$V$

To jest moje intuicyjne zrozumienie, w jaki sposób „sztuczka jądra” pozwala „niejawnie” przekształcić pierwotną przestrzeń cech w nową przestrzeń cech o innym wymiarze. Wymiar ten zależy od używanego jądra, a dla jądra RBF ten wymiar może wzrosnąć do wielkości próbki szkoleniowej. Ponieważ próbki treningowe mogą mieć dowolny rozmiar, może to wzrosnąć do „nieskończoności” . Oczywiście w bardzo dużych przestrzeniach ryzyko nadmiernego dopasowania wzrośnie.$V$

Jądra to technika, która pozwala SVM przekształcić przestrzeń cech. Zobacz także Co sprawia, że ​​jądro Gaussa jest tak magiczne dla PCA i ogólnie?

Niestety wyjaśnienie fcop jest dość niepoprawne. Przede wszystkim mówi: „Wiadomo, że jądro można napisać jako… gdzie… jest (domniemana i nieznana) transformacja do nowej przestrzeni funkcji”. NIE jest nieznane. W rzeczywistości jest to przestrzeń, na którą odwzorowane są cechy i jest to przestrzeń, która może być nieskończona wymiarowo, jak w przypadku RBF. Jądro pobiera wewnętrzny produkt tego transformowanego wektora cech z transformowanym wektorem cech z przykładu szkoleniowego i stosuje pewną funkcję do wyniku. Zatem domyślnie reprezentuje ten wektor cech wyższych wymiarów. Pomyśl na przykład o pisaniu (x + y) ^ 2 zamiast x ^ 2 + 2xy + y ^ 2. Pomyśl teraz, jaka seria nieskończona jest reprezentowana niejawnie przez funkcję wykładniczą ... tam masz swoją nieskończoną przestrzeń cech.

Właściwy sposób myślenia o SVM polega na tym, że odwzorowujesz swoje obiekty na możliwie nieskończoną wymiarową przestrzeń cech, która przypadkowo może być reprezentowana w jeszcze innym skończonym wymiarze przestrzeni cech "Jądro", której wymiar może być tak duży jak rozmiar zestawu treningowego.