Cómo probar que la función de base radial es un kernel?

Question

Cómo probar que la función de base radial $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$ es un kernel? Como tengo entendido, con el fin de demostrar esto, tenemos que probar cualquiera de los siguientes:

1. Para cualquier conjunto de vectores $x_1, x_2, ..., x_n$ matriz $K(x_1, x_2, ..., x_n)$ = $(k(x_i, x_j))_{n \times n}$ es positivo semidefinite.

2. Un mapeo $\Phi$ puede ser presentado como $k(x, y)$ = $\langle\Phi(x), \Phi(y)\rangle$.

Alguna ayuda?

Answer 1

Voy a añadir un tercer método, sólo por la variedad: la construcción del núcleo a partir de una secuencia de pasos generales que se conoce para crear pd núcleos. Deje $\mathcal X$ denotar el dominio de los núcleos de abajo y $\varphi$ los mapas de características.

• Escalas: Si $\kappa$ es un ep del núcleo, por lo que es $\gamma \kappa$ para cualquier constante $\gamma > 0$.

  Prueba: si $\varphi$ es la función de mapa para $\kappa$, $\sqrt\gamma \varphi$ es válido función de mapa para $\gamma \kappa$.

• Sumas: Si $\kappa_1$ $\kappa_2$ pd núcleos, por lo que es $\kappa_1 + \kappa_2$.

  Prueba: Concatenar la función de los mapas de $\varphi_1$$\varphi_2$, para obtener el $x \mapsto \begin{bmatrix}\varphi_1(x) \\ \varphi_2(x)\end{bmatrix}$.

• Límites: Si $\kappa_1, \kappa_2, \dots$ pd kernels, y $\kappa(x, y) := \lim_{n \to \infty} \kappa_n(x, y)$ existe para todas las $x, y$, $\kappa$ es pd.

  Prueba: Para cada una de las $m, n \ge 1$ y cada una de las $\{ (x_i, c_i) \}_{i=1}^m \subseteq \mathcal{X} \times \mathbb R$ tenemos que $\sum_{i=1}^m c_i \kappa_n(x_i, x_j) c_j \ge 0$. Tomando el límite cuando $n \to \infty$ da la misma propiedad para $\kappa$.

• Productos: Si $\kappa_1$ $\kappa_2$ pd núcleos, por lo que es $g(x, y) = \kappa_1(x, y) \, \kappa_2(x, y)$.

  Prueba: Se sigue inmediatamente de la Schur producto teorema, pero Schölkopf y Smola (2002) dan la siguiente agradable, en la escuela primaria de la prueba. Vamos $$ (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) $$ ser independiente. Así $$\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).$$ Las matrices de covarianza debe ser psd, así que teniendo en cuenta la matriz de covarianza de $(V_1 W_1, \dots, V_n W_n)$ lo demuestra.

• Poderes: Si $\kappa$ es un ep del núcleo, por lo que es $\kappa^n(x, y) := \kappa(x, y)^n$ para cualquier entero positivo $n$.

  Prueba: inmediata de los "productos" de la propiedad.

• Los exponentes: Si $\kappa$ es un ep del núcleo, por lo que es $e^\kappa(x, y) := \exp(\kappa(x, y))$.

  Prueba: Hemos $e^\kappa(x, y) = \lim_{N \to \infty} \sum_{n=0}^N \frac{1}{n!} \kappa(x, y)^n$; el uso de los "poderes", "escalas", "sumas", y "límites" de las propiedades.

• Funciones: Si $\kappa$ es un ep de kernel y $f : \mathcal X \to \mathbb R$, $g(x, y) := f(x) \kappa(x, y) f(y)$ es así.

  Prueba: Utilizar la función de mapa de $x \mapsto f(x) \varphi(x)$.

Ahora, tenga en cuenta que \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*} Iniciar con el kernel lineal $\kappa(x, y) = x^T y$, aplicar "escalas" con $\frac{1}{\sigma^2}$, aplicar "exponentes", y aplicar las "funciones" con $x \mapsto \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x \rVert^2 \right)$.

Answer 2

Voy a utilizar el método 1. Compruebe Douglas Zare la respuesta de una prueba utilizando el método 2.

Voy a probar el caso al $x,y$ son números reales, por lo $k(x,y)=\exp(-(x-y)^2/2\sigma^2)$. El caso general sigue , mutatis mutandis, desde el mismo argumento, y es que vale la pena hacer.

Sin pérdida de generalidad, supongamos que $\sigma^2=1$.

Escribir $k(x,y)=h(x-y)$, donde $$h(t)=\exp\left(-\frac{t^2}{2}\right)=\mathrm{E}\left[e^{itZ}\right] $$ is the characteristic function of a random variable $Z$ with $N(0,1)$ de distribución.

Para los números reales $x_1,\dots,x_n$$a_1,\dots,a_n$, tenemos $$ \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 \, , $$ lo que implica que $k$ es positivo semidefinite función, también conocido como un núcleo.

Para entender este resultado en una mayor generalidad, retirar del Teorema de Bochner: http://en.wikipedia.org/wiki/Positive-definite_function

Answer 3

Zen utiliza el método 1. Aquí está el método 2: Mapa de $x$ a un esféricamente simétrica de la distribución Gaussiana centrada en $x$ en el espacio de Hilbert $L^2$. La desviación estándar y un factor constante tiene que ser ajustado para que esto funcione exactamente. Por ejemplo, en una dimensión,

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

Así, el uso de una desviación estándar de $\sigma/\sqrt 2$ y la escala de la distribución de Gauss para obtener $k(x,y) = \langle \Phi(x), \Phi(y)\rangle$. Este último reescalado se produce porque el $L^2$ norma de una distribución normal no es $1$ en general.