Jak udowodnić, że podstawową funkcją radialną jest jądro?

35

Jak udowodnić, że podstawowa funkcja radialna jest jądrem? O ile rozumiem, aby to udowodnić, musimy udowodnić jedno z poniższych:k(x,y)=exp(||xy||2)2σ2)

  1. Dla dowolnego zestawu wektorów macierz = jest dodatnim półfinałem.x1,x2,...,xnK(x1,x2,...,xn)(k(xi,xj))n×n

  2. Można przedstawić mapowanie takie jak = .Φk(x,y)Φ(x),Φ(y)

Jakaś pomoc?

Lew
źródło
1
Żeby połączyć to w bardziej oczywisty sposób: mapa funkcji jest również omawiana w tym pytaniu , w szczególności odpowiedź Marca Claesena oparta na serii Taylor i mojej, która omawia zarówno RKHS, jak i ogólną wersję osadzania podaną przez Douglasa poniżej. L2)
Dougal,

Odpowiedzi:

26

Zen zastosowana metoda 1. Oto metoda 2: Odwzoruj na sferycznie symetryczny rozkład Gaussa wyśrodkowany na w przestrzeni Hilberta . Odchylenie standardowe i stały współczynnik muszą zostać zmienione, aby działało dokładnie. Na przykład w jednym wymiarzexxL.2)

-exp[-(x-z)2)/(2)σ2))]2)πσexp[-(y-z)2)/(2)σ2))2)πσrez=exp[-(x-y)2)/(4σ2))]2)πσ.

Zatem użyj standardowego odchylenia i przeskaluj rozkład Gaussa, aby uzyskać . To ostatnie przeskalowanie występuje, ponieważ norma rozkładu normalnego nie jest ogólnie . k(x,y)=Φ(x),Φ(y)L21σ/2)k(x,y)=Φ(x),Φ(y)L.2)1

Douglas Zare
źródło
2
@Zen, Douglas Zare: dziękuję za wspaniałe odpowiedzi. Jak mam teraz wybrać oficjalną odpowiedź?
Leo
23

Będę używał metody 1. Sprawdź odpowiedź Douglasa Zarea, aby uzyskać dowód przy użyciu metody 2.

Udowodnię przypadek, gdy są liczbami rzeczywistymi, więc . Ogólny przypadek wynika mutatis mutandis z tego samego argumentu i warto go zrobić.k ( x , y ) = exp ( - ( x - y ) 2 / 2 σ 2 )x,yk(x,y)=exp(-(x-y)2)/2)σ2))

Bez utraty ogólności załóżmy, że .σ2)=1

Napisz , gdzie jest funkcją charakterystyczną zmiennej losowej o rozkładzie .h ( t ) = exp ( - t 2k(x,y)=h(x-y)ZN(0,1)

h(t)=exp(-t2)2))=mi[mijatZ]
ZN.(0,1)

Dla liczb rzeczywistych i 1 , ... , N mamy co oznacza, że jest dodatnią funkcją półfinałową, czyli jądrem.x1,,xnza1,,zank

jot,k=1nzajotzakh(xjot-xk)=jot,k=1nzajotzakmi[mija(xjot-xk)Z]=mi[jot,k=1nzajotmijaxjotZzakmi-jaxkZ]=mi[|jot=1nzajotmijaxjotZ|2)]0,
k

Aby zrozumieć ten wynik w większej ogólności, sprawdź Twierdzenie Bochnera: http://en.wikipedia.org/wiki/Positive-definite_function

Zen
źródło
2
Jest to dobry początek, we właściwym kierunku, z dwoma zastrzeżeniami: (a) nie jest równe przedstawionemu oczekiwaniu (sprawdź znak w potędze wykładniczej) i (b) wydaje się, że ogranicza to uwagę na przypadek, w którym i y są skalarne i nie wektorów. W międzyczasie głosowałem, ponieważ ekspozycja jest ładna i czysta i jestem pewien, że szybko usuniesz te małe luki. :-)xh(t)xy
kardynał
1
Tks! Spieszy mi się tutaj. :-)
Zen.
1
Przepraszam, naprawdę nie rozumiem, jak radzicie sobie mutatis mutandis tutaj. Jeśli opracujesz normę przed przejściem do formularza , otrzymasz produkty i nie możesz zamienić produktów i sum. I po prostu nie widzę, jak rozwinąć normę po przejściu do formularza h, aby uzyskać ładny wyraz. Czy możesz mnie tam trochę poprowadzić? :)h
Alburkerk
23

Dodam trzecią metodę, dla urozmaicenia: budowanie jądra z sekwencji ogólnych kroków znanych z tworzenia jąder pd. Niech oznaczają domenę ziaren poniżej i cp map fabularnych.Xφ

  • Skalowanie: Jeśli jest jądrem pd, to także γ κ dla dowolnej stałej γ > 0 .κγκγ>0

    Dowód: jeśli jest mapą funkcji dla , jest prawidłową mapą funkcji dla .φκγκγφγκ

  • Sumy: Jeśli i są jądrami pd, podobnie jest z .κ 2 κ 1 + κ 2κ1κ2κ1+κ2

    Dowód: Połącz mapy obiektów i , aby uzyskać .φ 2 x [ φ 1 ( x ) φ 2 ( x ) ]φ1φ2x[φ1(x)φ2(x)]

  • Limity: Jeśli są jądrami pd, a istnieje dla wszystkich , to to pd.κ ( x , y ) : = lim n κ n ( x , y ) x , y κκ1,κ2,κ(x,y):=limnκn(x,y)x,yκ

    Dowód: Dla każdego i każdego mamy to . Przyjmowanie limitu jako daje tę samą właściwość dla .{ ( x i , c i ) } m i = 1X × R m i = 1 c i κ n ( x i , x j ) c j0 n κm,n1{(xi,ci)}i=1mX×Ri=1mciκn(xi,xj)cj0nκ

  • Produkty: Jeśli i są jądrami pd, to też .κ 2 g ( x , y ) = κ 1 ( x , y )κ1κ2g(x,y)=κ1(x,y)κ2(x,y)

    Dowód: bezpośrednio wynika z twierdzenia o produkcie Schur , ale Schölkopf i Smola (2002) dają następujący ładny, elementarny dowód. Niech bądź niezależny. Zatem Macierze kowariancji muszą być psd, więc biorąc pod uwagę macierz kowariancji to potwierdza. C o v ( V i W i , V j W j ) = C o v ( V i , V j )

    (V.1,,V.m)N.(0,[κ1(xja,xjot)]jajot)(W.1,,W.m)N.(0,[κ2)(xja,xjot)]jajot)
    ( V 1 W 1 , , V n W n )
    dooprzeciwko(V.jaW.ja,V.jotW.jot)=dooprzeciwko(V.ja,V.jot)dooprzeciwko(W.ja,W.jot)=κ1(xja,xjot)κ2)(xja,xjot).
    (V.1W.1,,V.nW.n)
  • Uprawnienia: Jeśli jest jądrem pd, podobnie jest dla dowolnej dodatniej liczby całkowitej .κ n ( x , y ) : = κ ( x , y ) n nκκn(x,y): =κ(x,y)nn

    Dowód: bezpośrednio z właściwości „produktów”.

  • Wykładniki: Jeśli jest jądrem pd, podobnie jak .e κ ( x , y ) : = exp ( κ ( x , y ) )κmiκ(x,y): =exp(κ(x,y))

    Dowód: Mamy ; użyj właściwości „potęgi”, „skalowania”, „sum” i „limitów”.miκ(x,y)=limN.n=0N.1n!κ(x,y)n

  • Funkcje: Jeśli jest jądrem pd, a także , .f : XR g ( x , y ) : = f ( x ) κ ( x , y ) f ( y )κfa:XRsol(x,y): =fa(x)κ(x,y)fa(y)

    Dowód: użyj mapy funkcji .xfa(x)φ(x)

Teraz zauważ, że Rozpocznij od jądra liniowego , zastosuj „skalowanie” za pomocą , zastosuj „wykładniki” i zastosuj „funkcje” za pomocą .

k(x,y)=exp(-12)σ2)x-y2))=exp(-12)σ2)x2))exp(1σ2)xT.y)exp(-12)σ2)y2)).
κ(x,y)=xT.y1σ2)xexp(-12)σ2)x2))
Dougal
źródło