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(-\frac{||x-y||^2)}{2\sigma^2})$

Dla dowolnego zestawu wektorów macierz = jest dodatnim półfinałem. $x_1, x_2, ..., x_n$ $K(x_1, x_2, ..., x_n)$ $(k(x_i, x_j))_{n \times n}$
Można przedstawić mapowanie takie jak = . $\Phi$ $k(x, y)$ $\langle\Phi(x), \Phi(y)\rangle$

Jakaś pomoc?

svm kernel-trick

— 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.

L_{2}

$L_2$

— Dougal,

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 wymiarze $x$ $x$ $L^2$

\int_{- \infty}^{\infty} \frac{\exp [- (x - z)^{2)} / (2) σ^{2)})]}{\sqrt{2) π} σ} \frac{\exp [- (y - z)^{2)} / (2) σ^{2)})}{\sqrt{2) π} σ} re z = \frac{\exp [- (x - y)^{2)} / (4 σ^{2)})]}{2) \sqrt{π} σ} .

$\int_{-\infty}^\infty \frac{\exp[-(x-z)^2/(2\sigma^2)]}{\sqrt{2 \pi} \sigma} \frac{\exp[-(y-z)^2/(2 \sigma^2)}{\sqrt{2 \pi} \sigma} dz = \frac{\exp [-(x-y)^2/(4 \sigma^2)]}{2 \sqrt \pi \sigma}.$

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 . $\sigma/\sqrt 2$ $k(x,y) = \langle \Phi(x), \Phi(y)\rangle$ $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ć. $x,y$ $k(x,y)=\exp(-(x-y)^2/2\sigma^2)$

Bez utraty ogólności załóżmy, że . $\sigma^2=1$

Napisz , gdzie jest funkcją charakterystyczną zmiennej losowej o rozkładzie . $k(x,y)=h(x-y)$

h (t) = \exp (- \frac{t^{2)}}{2)}) = mi [{mi}^{ja t Z}]

$h(t)=\exp\left(-\frac{t^2}{2}\right)=\mathrm{E}\left[e^{itZ}\right]$

Z

$Z$

N (0, 1)

$N(0,1)$

Dla liczb rzeczywistych i mamy co oznacza, że jest dodatnią funkcją półfinałową, czyli jądrem. $x_1,\dots,x_n$ $a_1,\dots,a_n$

\sum_{jot, k = 1}^{n} {za}_{jot} {za}_{k} h (x_{jot} - x_{k}) = \sum_{jot, k = 1}^{n} {za}_{jot} {za}_{k} mi [{mi}^{ja (x_{jot} - x_{k}) Z}] = mi [\sum_{jot, k = 1}^{n} {za}_{jot} {mi}^{ja x_{jot} Z} {za}_{k} {mi}^{- ja x_{k} Z}] = mi [{| \sum_{jot = 1}^{n} {za}_{jot} {mi}^{ja x_{jot} Z} |}^{2)}] \geq 0,

$\sum_{j,k=1}^n a_j\,a_k\,h(x_j-x_k) = \sum_{j,k=1}^n a_j\,a_k\,\mathrm{E} \left[ e^{i(x_j-x_k)Z}\right] = \mathrm{E} \left[ \sum_{j,k=1}^n a_j\,e^{i x_j Z}\,a_k\,e^{-i x_k Z}\right] = \mathrm{E}\left[ \left| \sum_{j=1}^n a_j\,e^{i x_j Z}\right|^2\right] \geq 0 \, ,$

k

$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

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. :-)

h (t)

$h(t)$

x

$x$

y

$y$

— 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

$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 map fabularnych. $\mathcal X$ $\varphi$

Skalowanie: Jeśli jest jądrem pd, to także dla dowolnej stałej . $\kappa$ $\gamma \kappa$ $\gamma > 0$

Dowód: jeśli jest mapą funkcji dla , jest prawidłową mapą funkcji dla . $\varphi$ $\kappa$ $\sqrt\gamma \varphi$ $\gamma \kappa$
Sumy: Jeśli i są jądrami pd, podobnie jest z . $\kappa_1$ $\kappa_2$ $\kappa_1 + \kappa_2$

Dowód: Połącz mapy obiektów i , aby uzyskać . $\varphi_1$ $\varphi_2$ $x \mapsto \begin{bmatrix}\varphi_1(x) \\ \varphi_2(x)\end{bmatrix}$
Limity: Jeśli są jądrami pd, a istnieje dla wszystkich , to to pd. $\kappa_1, \kappa_2, \dots$ $\kappa(x, y) := \lim_{n \to \infty} \kappa_n(x, y)$ $x, y$ $\kappa$

Dowód: Dla każdego i każdego mamy to . Przyjmowanie limitu jako daje tę samą właściwość dla . $m, n \ge 1$ $\{ (x_i, c_i) \}_{i=1}^m \subseteq \mathcal{X} \times \mathbb R$ $\sum_{i=1}^m c_i \kappa_n(x_i, x_j) c_j \ge 0$ $n \to \infty$ $\kappa$
Produkty: Jeśli i są jądrami pd, to też . $\kappa_1$ $\kappa_2$ $g(x, y) = \kappa_1(x, y) \, \kappa_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.
$({V.}_{1}, \dots, {V.}_{m}) \sim N. (0, {[κ_{1} (x_{ja}, x_{jot})]}_{ja jot}) ({W.}_{1}, \dots, {W.}_{m}) \sim N. (0, {[κ_{2)} (x_{ja}, x_{jot})]}_{ja jot})$ $(V_1, \dots, V_m) \sim \mathcal{N}\left( 0, \left[ \kappa_1(x_i, x_j) \right]_{ij} \right) \\ (W_1, \dots, W_m) \sim \mathcal{N}\left( 0, \left[ \kappa_2(x_i, x_j) \right]_{ij} \right)$ $do o przeciwko ({V.}_{ja} {W.}_{ja}, {V.}_{jot} {W.}_{jot}) = do o przeciwko ({V.}_{ja}, {V.}_{jot}) do o przeciwko ({W.}_{ja}, {W.}_{jot}) = κ_{1} (x_{ja}, x_{jot}) κ_{2)} (x_{ja}, x_{jot}) .$ $\mathrm{Cov}(V_i W_i, V_j W_j) = \mathrm{Cov}(V_i, V_j) \,\mathrm{Cov}(W_i, W_j) = \kappa_1(x_i, x_j) \kappa_2(x_i, x_j).$ $(V_1 W_1, \dots, V_n W_n)$
Uprawnienia: Jeśli jest jądrem pd, podobnie jest dla dowolnej dodatniej liczby całkowitej . $\kappa$ $\kappa^n(x, y) := \kappa(x, y)^n$ $n$

Dowód: bezpośrednio z właściwości „produktów”.
Wykładniki: Jeśli jest jądrem pd, podobnie jak . $\kappa$ $e^\kappa(x, y) := \exp(\kappa(x, y))$

Dowód: Mamy ; użyj właściwości „potęgi”, „skalowania”, „sum” i „limitów”. $e^\kappa(x, y) = \lim_{N \to \infty} \sum_{n=0}^N \frac{1}{n!} \kappa(x, y)^n$
Funkcje: Jeśli jest jądrem pd, a także , . $\kappa$ $f : \mathcal X \to \mathbb R$ $g(x, y) := f(x) \kappa(x, y) f(y)$

Dowód: użyj mapy funkcji . $x \mapsto f(x) \varphi(x)$

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

\begin{aligned} k (x, y) & = \exp (- \frac{1}{2) σ^{2)}} ‖ x - y ‖^{2)}) \\ = \exp (- \frac{1}{2) σ^{2)}} ‖ x ‖^{2)}) \exp (\frac{1}{σ^{2)}} x^{T.} y) \exp (- \frac{1}{2) σ^{2)}} ‖ y ‖^{2)}) . \end{aligned}

$\begin{align*} k(x, y) &= \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x - y \rVert^2 \right) \\&= \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x \rVert^2 \right) \exp\left( \tfrac{1}{\sigma^2} x^T y \right) \exp\left( - \tfrac{1}{2 \sigma^2} \lVert y \rVert^2 \right) .\end{align*}$

κ (x, y) = x^{T} y

$\kappa(x, y) = x^T y$

\frac{1}{σ^{2}}

$\frac{1}{\sigma^2}$

x \mapsto \exp (- \frac{1}{2 σ^{2}} ‖ x ‖^{2})

$x \mapsto \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x \rVert^2 \right)$

— Dougal
źródło