DIMENSIONALITY REDUCTION

Kernel Functions

Últimamente los kernels se han puesto muy de moda, en especial por la popularidad que han tenido las SVM o las redes neuronales. Las funciones kernel pueden usarse en multitud de algoritmos para convertir un algoritmo lineal en uno no-lineal. En el anterior post expliqué qué es un kernel y cómo se usan estos en el caso de KPCA (Kernel PCA). Hoy me centraré en explicar tres muy famosos (me gustaría explicar más pero hay demasiados 😥).

Recordemos que un kernel es una función que toma dos vectores de datos en el espacio $\mathbb{R}^p$ y devuelve el producto escalar de ambos vectores en un espacio $\mathbb{R}^m$ donde m > p.

\[k(x, y) = \langle \phi(x), \phi(y) \rangle = \phi(x)^t\phi(y)\]

Para generar una función kernel no es necesario conocer $\phi$, es lo que conocemos como ‘kernel trick’.

Linear Kernel

El kernel lineal es el más simple de todos. Se define como:

\[k(x, y) = \langle x, y \rangle + c\]

Los algoritmos que usan un kernel lineal son prácticamente equivalentes a los algoritmos originales sin kernel. Por ejemplo, KPCA con un kernel lineal es igual a PCA. Esto se debe a que la matriz $K$ será igual a la matriz de covarianzas.

Polynomial Kernel

El kernel polinómico de grado $d$ se define como:

\[k(x, y) = (\gamma \langle x, y \rangle + \lambda)^d = (\gamma x^ty + \lambda)^d\]

Donde los parámetros $\gamma$ y $\lambda$ servirán para ajustar los coeficientes del kernel polinómico. Cuando $\gamma = 1$ y $\lambda = 0$ el kernel se denomina homogéneo.

En este caso, el espacio sobre el que se calcula el producto escalar, o sea, $\phi(x)$ es de dimensiones:

\[\pmatrix{ k + d \cr d} = \frac{(k + d)!}{d! \; k!}\]

Donde $k$ es la dimensión original del vector $x$. O sea:

\[\phi: \mathbb{R}^k \rightarrow \mathbb{R}^{\pmatrix{ k + d \cr d}}\]

Por ejemplo, para $k = d = 2$, $\phi$ es un mapping de $\mathbb{R}^2$ a $\mathbb{R}^6$. Si desarrollamos el kernel;

\[k(x, y) = (\gamma x^ty + \lambda)^2 =\] \[= \gamma x_1^2y_1^2 + 2\gamma x_1y_1x_2y_2 + \gamma x_2^2y_2^2 + \lambda^2 + 2\lambda \gamma x_1 y_1 + 2 \lambda \gamma x_2y_2\]

Donde se sigue que el mapping viene dado por;

\[\phi(x) = \pmatrix{ \sqrt{\gamma}x_1^2, & \sqrt{\gamma}x_2^2, & \sqrt{2\gamma}x_1x_2, & \sqrt{2\lambda \gamma}x_1, & \sqrt{2\lambda \gamma}x_2, & \lambda}\]

Radial Basis Kernel

El kernel RBF o Gaussian Kernel se define como:

\[k(x, y) = e^{- \frac{\lVert x- y \rVert^2}{2 \sigma^2}} = e^{-\gamma \lVert x- y \rVert^2}\]

Donde $\gamma$ es igual a $\frac{1}{2 \sigma^2}$. $\gamma$ es un parámetro que medirá la varianza del kernel. Por otra parte, $\lVert x- y \rVert^2$ representa la distancia euclídea al cuadrado entre $x$ e $y$.

En el caso del kernel RBF, el espacio sobre el que se calculará el producto escalar entre los vectores es un espacio de dimensiones infinitas como luego veremos.

\[\phi: \mathbb{R}^p \rightarrow \mathbb{R}^{\infty}\]

Podemos interpretar el kernel RBF como una medida de similitud entre dos vectores. Para entender cómo funciona usaremos el siguiente conjunto de datos en $\mathbb{R}^2$. Donde se representan dos de las características más importantes de algunas de las figuras más influyentes en la política española.

Usando el kernel RBF (con $\gamma = 1$) podemos calcular la similitud entre dos observaciones. Por ejemplo;

\[k(x_{P.Iglesias}, x_{A.Garzón}) = e^{- \lVert \pmatrix{0.2, 0.5} - \pmatrix{0.7, 0.75} \rVert^2} = 0.73\] \[k(x_{P.Iglesias}, x_{Abascal}) = e^{- \lVert \pmatrix{0.2, 0.5} - \pmatrix{5, 4} \rVert^2} = 0\]

Según la distancia euclídea a la que se encuentre una observación $y$ con respecto a Pablo Iglesias, el kernel asignará un valor mayor o menor. El kernel RBF representa la similitud entre dos vectores como una función que decrece según la distancia euclídea entre estos.

Parámetro $\gamma$

El parámetro $\gamma$ es un hiperparámetro crítico en un kernel RBF. $\gamma$ es inversamente proporcional a la $\sigma^2$:

\[\sigma^2 = \frac{1}{2\gamma}\]

Para ilustrar lo que representa el valor $\gamma$ vamos a representar la siguiente función;

\[k(x_i, x_{Rivera}) = e^{-0.2 \lVert x_i- \pmatrix{3.5, 2.2} \rVert^2}\]

La función nos devolverá un valor igual a 1 si consideramos como $x_i$ a $x_{Rivera}$. En cambio, si evaluamos la observación $x_{A.Garzón}$ en la función, el valor que se devuelve será muy cercano a 0. El valor de $\gamma$ en este caso es de 0.2 pero, ¿qué ocurre si variamos $\gamma$?

Si aumentamos $\gamma$ estamos disminuyendo la varianza, por lo tanto, la función irá encogiendo según aumente $\gamma$. Esto hará que Albero Garzón tome cada vez valores menores y más cercanos a cero de similitud. Cuando el valor de $\gamma$ sea muy elevado todas las observaciones fuera de un determinado radio están igual de lejos.

Dimensiones infinitas?

Como se ha dicho anteriormente, el kernel RBF proyecta los vectores en un espacio de dimensiones infinitas. Sea $\gamma = \frac{1}{2}$:

\[k(x, y) = e^{-\frac{1}{2} \lVert x - y \rVert^2} = e^{-\frac{1}{2} \langle x - y, \; x- y \rangle} =\] \[= e^{-\frac{1}{2} (\langle x, \; x- y \rangle - \langle y, \; x - y \rangle )} = e^{-\frac{1}{2} (\langle x, x \rangle - \langle x, y \rangle - \langle y, x \rangle + \langle y, y \rangle)} =\] \[= e^{-\frac{1}{2} ( \lVert x \rVert^2 + \lVert y \rVert^2 - 2 \langle x, y \rangle ) } = e^{-\frac{1}{2} ( \lVert x \rVert^2 + \lVert y \rVert^2) } e^{\langle x, y\rangle}\]

Sea $C = e^{-\frac{1}{2} ( \lVert x \rVert^2 + \lVert y \rVert^2) }$

\[k(x, y) = C e^{\langle x, y \rangle}\]

Y aproximando la exponencial usando una serie de Taylor tenemos que:

\[k(x, y) = C e^{\langle x, y \rangle} = C \sum_{n = 0}^{\infty} \frac{\langle x , y \rangle^n}{n !}\]

Si nos damos cuenta, el numerador del sumatorio es un kernel polinómico homogéneo de orden $n$. Por tanto, el kernel RBF no es más que una combinación de todos los kernels polinómicos de orden $n \geq 0$.

Referencias