Jak SVM może „znaleźć” nieskończoną przestrzeń cech, w której zawsze możliwa jest separacja liniowa?

36

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

użytkownik 36162
źródło
1
Naprawdę nie rozumiem pytania. Czy chcesz wyjaśnić, dlaczego odpowiadająca mu przestrzeń cech jest nieskończona wymiarowo, czy interpretację, co oznacza wynikowa hiperpłaszczyzna?
Marc Claesen,
1
Nie miałbym nic przeciwko słyszeniu obu!
user36162,
5
Myślę, że to interesujące pytanie (+1)

Odpowiedzi:

39

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:

Coś takiego

( Ź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 klasyfikatoraK(x,z)=exp(||xz||2/σ2)(x(1),y(1)),(x(2),y(2)),,(x(n),y(n))y(i)±1

y^(x)=iwiy(i)K(x(i),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 mamywiσ||x(i)x(j)||wi=1y^

y^(x(k))=i=1ny(k)K(x(i),x(k))=y(k)K(x(k),x(k))+iky(i)K(x(i),x(k))=y(k)+ϵ

gdzie jest dowolną niewielką wartością. Wiemy, że jest malutki, ponieważ jest o miliard sigma od jakiegokolwiek innego punktu, więc dla wszystkich mamyϵϵx(k)ik

K(x(i),x(k))=exp(||x(i)x(k)||2/σ2)0.

Ponieważ jest tak mały, zdecydowanie ma taki sam znak jak , a klasyfikator osiąga doskonałą dokładność danych treningowych.ϵy^(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(x(i),x(j))=Φ(x(i)),Φ(x(j))

gdzie jest mapowaniem z przestrzeni danych na przestrzeń cech. Wynika z tego natychmiast, że funkcja jako funkcja liniowa w przestrzeni cech:Φ(x)y^(x)

y^(x)=iwiy(i)Φ(x(i)),Φ(x)=L(Φ(x))

gdzie funkcja liniowa jest zdefiniowana w wektorach przestrzeni cech jakoL(v)v

L(v)=iwiy(i)Φ(x(i)),v

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.vy^(x)=0L(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!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 .Φ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.ΦΦ

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 Φ(x),Φ(y)=K(x,y)VXRfV

f(x)=i=1nαiK(x(i),x)
f
f=i=1nαiKx(i)
gdzie to funkcja dająca „kawałek” jądra w .Kx(y)=K(x,y)x

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

i=1nαiKx(i),j=1nβjKx(j)=i,jαiβjK(x(i),x(j))

Po zdefiniowaniu w ten sposób przestrzeni funkcji jest mapowaniem , przenosząc każdy punkt do „wycinka jądra” w tym punkcie:ΦXVx

Φ(x)=Kx,whereKx(y)=K(x,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!)VK

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.zKz(x)=K(z,x)Kzz

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 .x(1),x(2),,x(n)Φ(x(i))x(n+1)nΦ(x(n+1))nΦ(x(i))

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

Φ(x(n+1))=i=1nαiΦ(x(i))

Teraz weź wewnętrzny produkt po obu stronach za pomocą dowolnego . Poprzez tożsamość , otrzymujemyxΦ(z),Φ(x)=K(z,x)

K(x(n+1),x)=i=1nαiK(x(i),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ć.xx(n+1)x(i)

Paweł
źródło
6
Idealne rozdzielenie jest niemożliwe. Kontrprzykład: (0,0, klasy A), (0,0, klasa B). Powodzenia przy rozdzielaniu tego zestawu danych!
Anony-Mousse,
4
To ... technicznie poprawne, najlepszy rodzaj poprawne! Zyskaj głos. Dodam notatkę w poście.
Paul
3
(Myślę, że twój punkt ma sens, jeśli potrzebujesz minimalnej odległości między próbkami różnych klas. Warto zauważyć, że w tym scenariuszu SVM staje się klasyfikatorem najbliższego sąsiada)
Anony-Mousse
1
Zajmuję się tylko skończonym zestawem treningowym, więc zawsze jest minimalna odległość między punktami, gdy otrzymamy zestaw treningów różnych punktów do pracy. n
Paul
@Paul Odnośnie twojej sekcji 2, mam pytanie. Niech będzie reprezentantem w naszym RKHS dla punktu szkolenia i dla dowolnego nowego punktu , aby to funkcja jakiegoś . Dla mnie jest to jak wersja funkcji znajdująca się w przestrzeni kolumny dla regresji liniowej i tam właśnie pochodzi liniowość. Czy ten opis wydaje się dokładny? Nadal bardzo się uczę tego RKHS. kix(i)kxxy^(x)=iwiy(i)ki,kx=iwiy(i)ki(x)y^=izikiziRy^X
jld
12

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.x1,...,xm1σ

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Φ(x)Φ(x1),...,Φ(xm)||Φ(x)||H²=k(x,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.

fabee
źródło
Nadal tego nie rozumiem, ale i tak zdobyłeś poparcie :)
stmax
Masz na myśli, że nie rozumiesz, dlaczego geometria jest płaska lub dlaczego jest nieskończona? Dziękuję za opinię.
fabee
Jeśli mam 100 przykładów, czy moja przestrzeń cech jest 100-wymiarowa, czy już nieskończenie wymiarowa? Dlaczego mogę dodać nieskończenie wiele przykładów? Czy to nie jest policzalna nieskończoność? Dlaczego policzalne / niepoliczalne ma tutaj znaczenie? Nie próbowałem nawet myśleć o „płaskiej kuli”: D Dziękuję za wyjaśnienia!
stmax,
5
Mam nadzieję, że uwierzysz mi, że każdy nowy przykład jest liniowo niezależny od wszystkich poprzednich (z wyjątkiem tego samego ). W nie możesz tego zrobić: każdy punkt poza musi być liniowo zależny od innych. W przypadku Gaussian RKHS, jeśli masz 100 różnych przykładów, obejmują one 100-wymiarową podprzestrzeń nieskończonej przestrzeni wymiarowej. Rozpiętość jest więc skończona, ale przestrzeń cech, w której żyją, jest nieskończona. Nieskończoność jest niepoliczalna, ponieważ każdy nowy punkt w jest nowym wymiarem i jest niepoliczalnie wiele punktów w . xRnnRnRn
fabee
@fabee: Próbowałem w inny sposób, wydaje się, że dużo o tym wiesz, czy możesz spojrzeć na moją odpowiedź, czy mam mniej więcej „rację”?
5

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 .xiyi{1,+1}α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)=Φ(x)Φ(y)Φ

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Φ

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

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).xiϕi(x)=K(xi,x)ϕiϕiϕiV=span(ϕi,i=1,2,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ściVϕii=1NγiϕiγiV={v=i=1Nγiϕi|(γ1,γ2,γN)RN}

Zauważ, że są współrzędnymi wektora w przestrzeni wektorowej .(γ1,γ2,γN)vV

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.VNϕiϕi(x)=K(xi,x)ϕ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.ϕi(x)=K(xi,x)VN

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

Φ:xiϕi(x)=K(xi,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. Φ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.ΦxiVϕii

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.xiVi=1Nγiϕiγ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)=iyiαiϕi(x)+bf(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)ϕi f(x)=0Vγiγi=αiyi

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.yiαiV

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?

Społeczność
źródło
+1 to jest solidne. Przetłumaczyłem ten materiał na własny styl ekspozycji i dodałem go do mojej odpowiedzi.
Paul,
5

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.

Salvador
źródło