Feature Map für den Gaußschen Kernel

24

In SVM ist der Gaußsche Kern wie folgt definiert: wobei . Ich kenne die explizite Gleichung von . Ich will es wissen.

K (x, y) = \exp (- \frac{‖ x - y ‖_{2}^{2}}{2 σ^{2}}) = ϕ (x)^{T} ϕ (y)

$K(x,y)=\exp\left({-\frac{\|x-y\|_2^2}{2\sigma^2}}\right)=\phi(x)^T\phi(y)$

x, y \in R^{n}

$x, y\in \mathbb{R^n}$

ϕ

$\phi$

Ich möchte auch wissen, ob

\sum_{i} c_{i} ϕ (x_{i}) = ϕ (\sum_{i} c_{i} x_{i})

$\sum_ic_i\phi(x_i)=\phi \left(\sum_ic_ix_i \right)$ wobei

c_{i} \in R

$c_i\in \mathbb R$ . Jetzt denke ich, dass es nicht gleich ist, weil die Verwendung eines Kernels die Situation handhabt, in der der lineare Klassiker nicht funktioniert. Ich kenne

ϕ

$\phi$ Projekte x zu einem unendlichen Raum. Also, wenn es immer noch linear bleibt, egal wie viele Dimensionen es sind, kann svm immer noch keine gute Klassifizierung vornehmen.

machine-learning svm kernel-trick Vivian
quelle

Warum impliziert dieser Kernel eine Transformation? Oder beziehen Sie sich auf den zugehörigen Funktionsbereich?

Placidia

Ja, was ist der Merkmalsraum

ϕ (\cdot)

$\phi(\cdot)$ so dass

ϕ^{T} (x) ϕ (x^{^{'}}) = e x p (- \frac{1}{2 σ^{2}} ‖ x - x^{^{'}} ‖^{2})

$\phi^T(x)\phi(x^{'}) = exp(-\frac{1}{2\sigma^2}\|x-x^{'}\|^2)$

user27886

20

Sie können die explizite Gleichung von $\phi$ für den Gaußschen Kernel über die Erweiterung der Tailor-Reihe von $e^x$ . Nehmen Sie zur Vereinfachung der Notation an, dass $x\in \mathbb{R}^1$ :

ϕ (x) = e^{- x^{2} / 2 σ^{2}} [1, \sqrt{\frac{1}{1! σ^{2}}} x, \sqrt{\frac{1}{2! σ^{4}}} x^{2}, \sqrt{\frac{1}{3! σ^{6}}} x^{3}, \dots]^{T}

$\phi(x) = e^{-x^2/2\sigma^2} \Big[ 1, \sqrt{\frac{1}{1!\sigma^2}}x,\sqrt{\frac{1}{2!\sigma^4}}x^2,\sqrt{\frac{1}{3!\sigma^6}}x^3,\ldots\Big]^T$

Dies wird auch in diesen Folien von Chih-Jen Lin von NTU (Folie 11 speziell) ausführlicher erörtert . Beachten Sie, dass in den Folien als Kernelparameter verwendet wird. $\gamma=\frac{1}{2\sigma^2}$

Die Gleichung im OP gilt nur für den linearen Kernel.

Marc Claesen
quelle

2

Hallo, aber diese Gleichung passt nur zu einer Dimension.

Vivian

Also, hier ist der reproduzierende Kernel-Hilbert-Raum ein Unterraum von , richtig?

ℓ^{2}

$\ell^2$

The_Anomaly

Gibt es auch eine explizite Darstellung des Laplace-Kernels?

Felix Crazzolara

13

Für jeden gültigen psd kernel , es existiert eine Merkmalskarte , so daß . Der Raum und die Einbettung in der Tat nicht eindeutig sein, aber es gibt ein wichtiges eindeutiges Paar das als reproduzierender Kernel-Hilbert-Raum (RKHS) bekannt ist. $k : \mathcal X \times \mathcal X \to \mathbb R$ $\varphi : \mathcal X \to \mathcal H$ $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$ $\mathcal H$ $\varphi$ $(\mathcal H, \varphi)$

Das RKHS wird diskutiert von: Steinwart, Hush and Scovel, Eine explizite Beschreibung des reproduzierenden Kerns Hilbert-Räume von Gaußschen RBF-Kerns , IEEE-Transaktionen zur Informationstheorie 2006 ( doi , free citeseer pdf ).

Es ist etwas kompliziert, aber es läuft darauf hinaus: Definiere als $e_n : \mathbb C \to \mathbb C$

e_{n} (z) := \sqrt{\frac{(2 σ^{2})^{n}}{n!}} z^{n} e^{- σ^{2} z^{2}} .

$e_n(z) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} z^n e^{-\sigma^2 z^2} .$

Sei eine Folge, die sich über alle Tupel nichtnegativer Ganzzahlen erstreckt; wenn , vielleicht , , und so weiter. Bezeichne die te Komponente des ten Tupels mit . $n : \mathbb{N}_0 \to \mathbb{N}_0^d$ $d$ $d = 3$ $n(0) = (0, 0, 0)$ $n(1) = (0, 0, 1)$ $n(2) = (0, 1, 1)$ $j$ $i$ $n_{ij}$

Dann wird der - ten Komponente von ist . Also bildet Vektoren in auf unendlich dimensionale komplexe Vektoren ab. $i$ $\varphi(x)$ $\prod_{j=1}^d e_{n_{ij}}(x_j)$ $\varphi$ $\mathbb R^d$

Der Haken dabei ist, dass wir für diese unendlichdimensionalen komplexen Vektoren in besonderer Weise Normen definieren müssen; Einzelheiten finden Sie auf dem Papier.

Steinwart et al. Geben Sie auch eine (meiner nach) Einbettung in , den Hilbert-Raum der quadratintegrierbaren Funktionen von : Beachten Sie, dass selbst eine Funktion von bis . Es ist im Grunde die Dichte eines dimensionalen Gaußschen mit Mittelwert und Kovarianz ; nur die normalisierende Konstante ist anders. Also wenn wir nehmen $L_2(\mathbb R^d)$ $\mathbb R^d \to \mathbb R$

Φ_{σ} (x) = \frac{(2 σ)^{\frac{d}{2}}}{π^{\frac{d}{4}}} e^{- 2 σ^{2} ‖ x - \cdot ‖_{2}^{2}} .

$\Phi_\sigma(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$

Φ_{σ} (x)

$\Phi_\sigma(x)$

R^{d}

$\mathbb R^d$

R

$\mathbb R$

d

$d$

x

$x$

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

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

⟨ Φ (x), Φ (y) ⟩_{L_{2}} = \int [Φ (x)] (t) [Φ (y)] (t) d t,

$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$ wir nehmen das Produkt der Gaußschen Dichtefunktionen , die selbst eine gewisse Konstante mal einer Gaußschen Dichtefunktionen ist. Wenn Sie dieses Integral durch ausführen, ist die Konstante, die herausfällt, genau .

t

$t$

k (x, y)

$k(x, y)$

Dies sind nicht die einzigen Einbettungen, die funktionieren.

Ein anderes basiert auf der Fourier-Transformation, die sich dem berühmten Artikel von Rahimi und Recht ( Random Features for Large-Scale Kernel Machines , NIPS 2007) sehr gut annähert.

Sie können dies auch mit Taylor-Reihen tun: effektiv die unendliche Version von Cotter, Keshet und Srebro, Explicit Approximations of the Gaussian Kernel , arXiv: 1109.4603 .

Dougal
quelle

1

Douglas Zare gab eine 1d-Version der "direkteren" Einbettung in einen interessanten Thread an .

Dougal

Hier finden Sie eine 'intuitivere' Erklärung dafür, dass das auf eine Dimension abgebildet werden kann, die der Größe des Trainingsmusters entspricht, auch für ein unbegrenztes Trainingsmuster: stats.stackexchange.com/questions/80398/…

Φ

$\Phi$

6

Es scheint mir, dass Ihre zweite Gleichung nur dann wahr sein wird, wenn eine lineare Abbildung ist (und daher ein linearer Kern ist). Da der Gauß'sche Kern nicht linear ist, wird die Gleichheit nicht gelten (außer vielleicht in der Grenze, wenn auf Null geht). $\phi$ $K$ $\sigma$

Dikran Beuteltier
quelle

Vielen Dank für Ihre Antwort. Wenn , vergrößert sich die Dimension der Gaußschen Kernelprojekte. Und von Ihrer Inspiration halte ich es jetzt nicht für gleich. Weil die Verwendung des Kernels nur die Situation handhabt, dass die lineare Klassifizierung nicht funktioniert.

σ \to 0

$\sigma\rightarrow 0$

Vivian

Feature Map für den Gaußschen Kernel

Antworten: