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

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

Odpowiedzi: