Mapa de características para el núcleo gaussiano

Question

En la SVM, el núcleo gaussiano se define como $$K(x,y)=\exp\left({-\frac{\|x-y\|_2^2}{2\sigma^2}}\right)=\phi(x)^T\phi(y)$$ donde $x, y\in \mathbb{R^n}$ . No conozco la ecuación explícita de $\phi$ . Quiero saberlo.

También quiero saber si $$\sum_ic_i\phi(x_i)=\phi \left(\sum_ic_ix_i \right)$$ donde $c_i\in \mathbb R$ . Ahora, creo que no es igual, porque el uso de un núcleo maneja la situación en la que el clasificador lineal no funciona. Sé que $\phi$ proyecta x a un espacio infinito. Así que si sigue siendo lineal, no importa cuántas dimensiones tenga, svm todavía no puede hacer una buena clasificación.

Answer 1

Se puede obtener la ecuación explícita de $\phi$ para el núcleo gaussiano mediante la expansión en serie de Tailor de $e^x$ . Para simplificar la nota, supongamos que $x\in \mathbb{R}^1$ :

$$\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$$

Esto también se analiza con más detalle en estas diapositivas por Chih-Jen Lin, de la NTU (diapositiva 11 en concreto). Obsérvese que en las diapositivas $\gamma=\frac{1}{2\sigma^2}$ se utiliza como parámetro del núcleo.

La ecuación del PO sólo es válida para el núcleo lineal.

Answer 2

Para cualquier núcleo psd válido $k : \mathcal X \times \mathcal X \to \mathbb R$ existe un mapa de características $\varphi : \mathcal X \to \mathcal H$ tal que $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$ . El espacio $\mathcal H$ y la incrustación $\varphi$ de hecho no tiene por qué ser única, pero hay una importante $\mathcal H$ conocido como el espacio de Hilbert del núcleo reproductor (RKHS).

El RKHS es discutido por: Steinwart, Hush y Scovel, Una descripción explícita de los espacios de Hilbert del núcleo reproductor de los núcleos RBF gaussianos , IEEE Transactions on Information Theory 2006 ( doi , citeseer pdf gratis ).

Es algo complicado, y tienen que analizarlo a través de la extensión del núcleo gaussiano a entradas y salidas complejas, pero se reduce a esto: definir $e_n : \mathbb R \to \mathbb R$ como $$ e_n(x) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} x^n e^{-\sigma^2 x^2} $$ y, para una tupla $\nu = (\nu_1, \cdots, \nu_d) \in \mathbb N_0^d$ su producto tensorial $e_\nu : \mathbb R^d \to \mathbb R$ como $$ e_\nu(x) = e_{\nu_1}(x_1) \cdots e_{\nu_d}(x_d) .$$ Entonces su Proposición 3.6 dice que cualquier función $f \in \mathcal H_\sigma$ la RKHS para un núcleo gaussiano de ancho de banda $\sigma > 0$ se puede escribir como $$ f(x) = \sum_{\nu \in \mathbb N_0^d} b_\nu e_\nu(x) \qquad \lVert f \rVert_{\mathcal H_\sigma(X)}^2 = \sum_{\nu \in \mathbb N_0^d} b_\nu^2 .$$

Podemos pensar en $\mathcal H_\sigma$ como si fuera esencialmente el espacio de los coeficientes sumables al cuadrado $(b_\nu)_{\nu \in \mathbb N_0^d}$ .

Sin embargo, la pregunta sigue siendo: ¿cuál es la secuencia $b_\nu$ para la función $\phi(x)$ ? El documento no parece responder directamente a esta pregunta (a no ser que se me haya escapado como una implicación obvia en alguna parte).

---

También dan una incrustación más directa en $L_2(\mathbb R^d)$ el espacio de Hilbert de las funciones cuadradas integrables de $\mathbb R^d \to \mathbb R$ : $$ \Phi(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$$ Tenga en cuenta que $\Phi(x)$ es a su vez una función de $\mathbb R^d$ a $\mathbb R$ . Es básicamente la densidad de un $d$ -gaussiana con media $x$ y la covarianza $\frac{1}{4 \sigma^2} I$ sólo la constante de normalización es diferente. Así, cuando tomamos $$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$$ estamos tomando la producto de funciones de densidad gaussianas que es a su vez una cierta constante por una función de densidad gaussiana. Cuando se hace esa integral por $t$ entonces, la constante que cae termina siendo exactamente $k(x, y)$ .

---

Estas no son las únicas incrustaciones que funcionan.

Otra se basa en la transformada de Fourier, que el célebre periódico de Rahimi y Recht ( Características aleatorias para máquinas de gran tamaño NIPS 2007) se aproxima con gran efecto.

También se puede hacer utilizando las series de Taylor: efectivamente la versión infinita de Cotter, Keshet y Srebro, Aproximaciones explícitas del núcleo gaussiano , arXiv:1109.4603 .

Answer 3

Me parece que su segunda ecuación sólo será cierta si $\phi$ es un mapeo lineal (y por lo tanto $K$ es un núcleo lineal). Como el núcleo gaussiano es no lineal, la igualdad no se mantendrá (excepto quizás en el límite como $\sigma$ llega a cero).

Answer 4

EXPRESIÓN EXPLÍCITA Y DERIVACIÓN MEDIANTE PRUEBA DIRECTA

La expresión explícita para $\phi$ que está pidiendo es la siguiente:

Lema:

Dado el núcleo RBF gaussiano $K_\sigma$ entre dos $n$ -vectores dimensionales ( $x$ y otro), para cada $j$ de 0 a infinito y para cada combinación de $n$ índices (etiquetados como $k$ ) que suman $j$ el vector de características $\phi(x)$ tiene una característica que se parece a esto:

$$ \phi_{\sigma, j, k}(x) = c_{\sigma, j}(x) \cdot f_{j, k}(x) $$

Dónde:

$$ \begin{aligned} c_{\sigma, j}(x) &= \frac{K_\sigma(x, 0)}{\sigma^j \sqrt{j!}}\\ f_{j, k}(x) &= \begin{pmatrix} j\\k_1,k_2, \dots, k_n \end{pmatrix}^{\frac{1}{2}} \prod_{d=1}^n{x_d^{k_d}} \end{aligned} $$

Esto puede derivarse directamente de la siguiente manera:

---

Definiciones:

• RBF gaussiano: https://en.wikipedia.org/wiki/Radial_basis_function
• Expansión de Taylor de la función exponencial: https://en.wikipedia.org/wiki/Exponential_function
• Teorema del multinomio: https://en.wikipedia.org/wiki/Multinomial_theorem

$$ \begin{aligned} K_\sigma(x, y) = &e^{-\frac{\|x-y\|_2^2}{2\sigma^2}}\\ \epsilon := &e^{\frac{1}{\sigma^2}}\\ \epsilon^x = &\sum_{j=0}^{\infty}\left\{ \frac{x^j}{\sigma^{2j} \cdot j!} \right\}\\ (x_1 + x_2 + \dots + x_n)^j = &\sum_{k_1+k_2+\dots+k_n=j}\left\{ \begin{pmatrix} j\\k_1,k_2, \dots, k_n \end{pmatrix} \prod_{d=1}^n{x_d^{k_d}} \right\}\\ \end{aligned} $$

---

Prueba directa:

En primer lugar, descomponemos la distancia euclidiana al cuadrado en sus componentes, y realizamos la expansión de Taylor para la $xy$ componente:

$$ \begin{aligned} K(x,y)= &e^{-\frac{\|x-y\|_2^2}{2\sigma^2}} =\epsilon^{\langle x, y \rangle} \cdot\epsilon^{-\frac{\|x\|_2^2}{2}} \cdot \epsilon^{-\frac{\|y\|_2^2}{2}}\\ = &\sum_{j=0}^{\infty}\left\{ \frac{\langle x, y \rangle^j}{\sigma^{2j} \cdot j!} \right\} \cdot\epsilon^{-\frac{\|x\|_2^2}{2}} \cdot \epsilon^{-\frac{\|y\|_2^2}{2}} \end{aligned} $$

Para mayor comodidad, refactorizamos la expresión (utilizando $c$ para una notación más compacta):

$$ \begin{aligned} K(x,y) = &\sum_{j=0}^{\infty}\left\{\frac{\epsilon^{-\frac{\|x\|_2^2}{2}}}{\sigma^j \cdot \sqrt{j!}} \cdot \frac{\epsilon^{-\frac{\|y\|_2^2}{2}}}{\sigma^j \cdot \sqrt{j!}} \cdot \langle x, y \rangle^j \right\}\\ = &\sum_{j=0}^{\infty}\left\{ c_{\sigma, j}(x) \cdot c_{\sigma, j}(y) \cdot \langle x, y \rangle^j \right\}\\ \end{aligned} $$

Y con ayuda del teorema del multinomio, podemos expresar la potencia del producto punto de la siguiente manera (utilizando $f$ para una notación más compacta):

$$ \begin{aligned} \langle x, y \rangle^j = &\left(\sum_{d=1}^n x_d y_d \right)^j\\ = &\sum_{k_1+k_2+\dots+k_n=j}\left\{ \begin{pmatrix} j\\k_1,k_2, \dots, k_n \end{pmatrix} \prod_{d=1}^n{(x_dy_d)^{k_d}} \right\}\\ = &\sum_{k_1+k_2+\dots+k_n=j}\left\{ \begin{pmatrix} j\\k_1,\dots, k_n \end{pmatrix}^{\frac{1}{2}} \prod_{d=1}^n{x_d^{k_d}} \cdot \begin{pmatrix} j\\k_1, \dots, k_n \end{pmatrix}^{\frac{1}{2}} \prod_{d=1}^n{y_d^{k_d}} \right\}\\ =: &\sum_{k_1+k_2+\dots+k_n=j}\left\{f_{j,k}(x) \cdot f_{j, k}(y) \right\}\\ \end{aligned} $$

Ahora sustituyendo en $K$ nos permitirá terminar la prueba:

$$ \begin{aligned} K(x,y) = &\sum_{j=0}^{\infty}\left\{ c_{\sigma, j}(x) \cdot c_{\sigma, j}(y) \cdot \sum_{k_1+k_2+\dots+k_n=j}\left\{f_{j,k}(x) \cdot f_{j, k}(y) \right\} \right\}\\ = &\sum_{j=0}^{\infty} \sum_{k_1+k_2+\dots+k_n=j}\left\{ c_{\sigma, j}(x) f_{j,k}(x) \cdot c_{\sigma, j}(y) f_{j, k}(y) \right\}\\ = &\langle \phi(x), \phi(y) \rangle\\ &\square \end{aligned} $$

Donde cada $\phi$ es un vector con una entrada para cada combinación de $n$ índices (etiquetados como $k$ ) que suman $j$ y esto para cada $j$ de 0 a infinito.

---

¡espero que esto ayude! Saludos,
Andrés