¿Por qué utilizar el núcleo RBF si se necesita menos?

Question

He visto en internet teoremas como el teorema de Cover Wikipedia que demuestran cómo dado $p$ puntos en $\mathbb{R}^N$ la separabilidad lineal es casi segura ya que la fracción $\dfrac{p}{N}$ se mantiene cerca de $1$ (y también un poco más lejos en realidad). Es posible comprobar el gráfico en la prueba citada más abajo para una rápida comprensión. Mi pregunta es, dado esto, ¿por qué habríamos de mapear a un espacio de características de dimensión infinita si a $p$ ¿es suficiente un espacio de características dimensional? ¿Es porque es más rápido calcular el kernel RBF que un kernel $p$ dimensional? ¿Es porque es más difícil diseñarlo? ¿O es porque no he entendido bien la afirmación?

Una demostración del teorema que implementa la notación que estoy utilizando se puede encontrar aquí Prueba del teorema de Cover

Answer 1

Una forma de verlo es decir que el núcleo RBF escala dinámicamente el espacio de características con el número de puntos. Como sabemos por geometría, para $p$ puntos siempre se puede sacar un máximo de $(p-1)$ -a través de ellos. Esa es la dimensionalidad inherente del espacio que implica el núcleo RBF. Pero, a medida que se añaden más puntos, la dimensionalidad del espacio aumenta en consecuencia. Esto hace que el núcleo RBF sea bastante flexible. Proporciona separabilidad lineal independientemente del número de puntos.

Actualización en respuesta al comentario:

No puedo darte un enlace a una prueba formal, pero supongo que no debería ser muy difícil de construir. Sabemos que:

• un núcleo es el producto punto en un espacio de características,
• $k(x, y) = \| \varphi(x) \| \cdot \| \varphi(y) \| \cdot \cos(\angle(\varphi(x), \varphi(y)))$ y, en consecuencia
• $k(x, x) = \| \varphi(x) \|^2$
• RBF es un núcleo,
• para el núcleo RBF, $k(x, x) = e^0 = 1$ y
• $k(x, \infty) = e^{-\infty} = 0$

Geométricamente, el núcleo RBF proyecta los puntos sobre un segmento de una hiperesfera con un radio de $1$ en un $p$ -espacio dimensional. Los puntos cercanos en el espacio de entrada se asignan a puntos cercanos en el espacio de características. Los puntos alejados entre sí en el espacio de entrada se asignan a puntos ortogonales (cercanos) en la hiperesfera.

Teóricamente, los puntos del espacio de características inducido por RBF son siempre linealmente separables, independientemente de $\gamma$ . Es sólo una cuestión numérica que para un pequeño $\gamma$ podría resultar difícil encontrar el hiperplano de separación.

Por otra parte, si elige $\gamma$ muy grande, empujará todas las proyecciones hacia las esquinas del hipercubo que encierra la hiperesfera: $(1, 0, 0, \ldots), (0, 1, 0, \ldots), (0, 0, 1, \ldots)$ etc. Esto le dará una separabilidad trivialmente simple en el conjunto de entrenamiento, pero una generalización muy mala.

Actualización (ejemplo gráfico):

Para obtener alguna intuición, observe este conjunto de datos unidimensional trivialmente simple. Es obvio que ninguna frontera lineal puede separar las dos clases, azul y roja:

Sin embargo, el núcleo RBF transforma los datos en un espacio de características 3D en el que son linealmente separables. Si denotamos $k_{ij} = k(x_i, x_j)$ es fácil ver que la transformación $$ \begin{array}{rrrrrrr} \textbf{z}_1 = \varphi(x_1) & = & [ & 1, & 0, & 0 & ]^T \\ \textbf{z}_2 = \varphi(x_2) & = & [ & k_{12}, & z_{22}, & 0 & ]^T \\ \textbf{z}_3 = \varphi(x_3) & = & [ & k_{13}, & (k_{23} - k_{12}k_{13}) / z_{22}, & z_{33} & ]^T \\ \end{array} $$ reproduce el núcleo RBF, $k(x_i, x_j) = \varphi(x_i) \cdot \varphi(x_j)$ donde $z_{22} = \sqrt{1 - k_{12}^2}$ y $z_{33} = \sqrt{1 - z_{31}^2 - z_{32}^2}$ . El parámetro del núcleo $\gamma$ controla hasta dónde llegan los puntos en el espacio de características:

Como puede ver, como $\gamma \rightarrow 0$ los puntos se acercan mucho entre sí. Pero esto es sólo una parte del problema. Si nos acercamos un poco $\gamma$ vemos que los puntos siguen estando en una línea casi recta:

Cierto, la línea no es exactamente recto, pero ligeramente curvado, por lo que existe un plano que separa las dos clases, pero el margen es muy fino y numéricamente difícil de satisfacer. Se puede decir que $\gamma $ controla la no linealidad de la transformación: Cuanto menor sea el $\gamma$ más se acerca la transformación a la lineal.

Answer 2

Aunque los puntos se sitúan teóricamente en un espacio de dimensiones infinitas, se encuentran necesariamente dentro de un espacio de dimensiones máximas. $p$ -subespacio dimensional (ya que sólo hay $p$ puntos). Obsérvese que el vector de pesos primario (teóricamente infinito) es una combinación lineal de las imágenes de los vectores de soporte en el espacio de características,

$\vec{w} = \sum_{i=1}^\ell y_i\alpha_i\phi(\vec{x}_i)$

lo que significa que también es necesario que el vector se encuentre dentro de ese $p$ -subespacio dimensional. Las dimensiones adicionales son esencialmente irrelevantes y no afectan en modo alguno al modelo resultante.

Por eso, el "truco del núcleo" nos permite representar un espacio teóricamente infinito utilizando sólo cantidades de dimensión finita (como la matriz de Gram).

Sin embargo, hay otras razones para utilizar el kernel RBF, y es que el problema puede ser no linealmente separable. Consideremos el caso en el que el $p=N$ todos los puntos del conjunto de datos son colineales, es decir, se encuentran a lo largo de una línea recta en N dimensiones. Para la mayoría de los etiquetados de los puntos, no habrá ningún límite de decisión que clasifique los puntos de datos sin error. Sin embargo, si tomamos esos mismos puntos y usamos un kernel RBF, los puntos serán mapeados en el orto positivo de una hiperesfera unitaria de dimensión infinita (como muestra @IgorF. +1), y los puntos ya no serán co-lineales y cualquier etiquetado de los puntos puede ser linealmente separado (siempre que ninguno de los puntos de diferentes etiquetas sean duplicados exactos).