¿Qué es la intuición detrás del hecho de que una SVM con un Núcleo Gaussiano tiene infinitas dimensiones espacio de características?
Respuestas
¿Demasiados anuncios?
Charan
Puntos
11
Esta respuesta se explica lo siguiente:
- Por qué la separación perfecta siempre es posible con un núcleo Gaussiano (de suficientemente pequeño ancho de banda)
- Cómo esta separación puede ser interpretado como lineal, pero sólo en abstracto, espacio de características distintas del espacio en el que los datos vidas
- Cómo la asignación del espacio de datos para la característica de que el espacio es "encontrado". Spoiler: no se encuentra por SVM, es implícitamente definido por el kernel que usted elija.
- ¿Por qué la característica de que el espacio es infinito-dimensional.
1. Lograr una perfecta separación
Perfecta separación siempre es posible con un núcleo Gaussiano debido a que el núcleo de la localidad de propiedades, que conducen a una arbitraria decisión flexibles límite. Por lo suficientemente pequeño núcleo de ancho de banda, la decisión de límite parecerá que acabas de dibujar pequeños círculos alrededor de los puntos cada vez que se necesitan para separar los ejemplos positivos y negativos:
(Crédito: Andrew Ng en línea de la máquina de aprendizaje del curso).
Así que, ¿por qué ocurre esto desde una perspectiva matemática?
Considerar la instalación estándar: usted tiene un núcleo Gaussiano $K(\mathbf{x},\mathbf{z}) = \exp(||\mathbf{x}-\mathbf{z}||^2 / \sigma^2)$ datos de entrenamiento y de $(\mathbf{x}^{(1)},y^{(1)}), (\mathbf{x}^{(2)},y^{(2)}), \ldots, (\mathbf{x}^{(n)},y^{(n)})$ cuando la $y^{(i)}$ valores $\pm 1$. Queremos aprender una función clasificadora
$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x})$$
Ahora, ¿cómo podremos asignar los pesos $w_i$? No tenemos más necesidad de infinitas dimensiones de los espacios y un algoritmo de programación cuadrática? No, porque sólo quiero demostrar que puedo separar los puntos a la perfección. Así que hacer $\sigma$ miles de millones de veces más pequeño que el más pequeño de la separación de $||\mathbf{x}^{(i)} - \mathbf{x}^{(j)}||$ entre cualquier dos ejemplos de formación, y solo he puesto $w_i = 1$. Esto significa que todos los puntos de entrenamiento son mil millones de sigmas aparte en cuanto al núcleo de que se trate, y a cada punto controla completamente el signo de $\hat{y}$ en su vecindario. Formalmente, tenemos
$$ \hat{y}(\mathbf{x}^{(k)}) = \sum_{i=1}^n y^{(k)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} K(\mathbf{x}^{(k)},\mathbf{x}^{(k)}) + \sum_{i \neq k} y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} + \epsilon$$
donde $\epsilon$ es algunos arbitrariamente pequeño valor. Sabemos $\epsilon$ es pequeña, debido a que $\mathbf{x}^{(k)}$ es mil millones de sigmas de distancia desde cualquier otro punto, por lo que para todos los $i \neq k$ hemos
$$K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = \exp(||\mathbf{x}^{(i)} - \mathbf{x}^{(k)}||^2 / \sigma^2) \approx 0.$$
Desde $\epsilon$ es tan pequeño, $\hat{y}(\mathbf{x}^{(k)})$ definitivamente tiene el mismo signo de $y^{(k)}$, y el clasificador logra la perfecta exactitud en los datos de entrenamiento.
2. Núcleo SVM aprendizaje lineal de separación
El hecho de que esto puede ser interpretado como "perfecto lineal de separación, en un infinito dimensional espacio de características" viene del kernel trick, que le permite interpretar el núcleo como un producto interior en un (potencialmente infinito-dimensional) espacio de características:
$$K(\mathbf{x}^{(i)},\mathbf{x}^{(j)}) = \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x}^{(j)})\rangle$$
donde $\Phi(\mathbf{x})$ es el mapeo del espacio de datos en el espacio de características. De ello se deduce inmediatamente que el $\hat{y}(\mathbf{x})$ función como una función lineal en el espacio de características:
$$ \hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x})\rangle = L(\Phi(\mathbf{x}))$$
donde la función lineal $L(\mathbf{v})$ se define en función de vectores en el espacio $\mathbf{v}$
$$ L(\mathbf{v}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\mathbf{v}\rangle$$
Esta función es lineal en $\mathbf{v}$ porque es una combinación lineal de interior de los productos fijos de los vectores. En el espacio de características, la decisión de límite de $\hat{y}(\mathbf{x}) = 0$ es sólo $L(\mathbf{v}) = 0$, el conjunto de nivel de una función lineal. Esta es la definición misma de un hyperplane en el espacio de características.
3. La comprensión de la cartografía y de la característica de espacio
Nota: En esta sección, la notación $\mathbf{x}^{(i)}$ se refiere a un conjunto arbitrario de $n$ puntos y no los datos de entrenamiento. Esto es pura matemática; los datos de entrenamiento no figura en esta sección a todos!!!!
Métodos del núcleo de hecho nunca "encontrar" o "calcular" el espacio de características o la asignación de $\Phi$ explícitamente. Núcleo de aprendizaje de métodos tales como la SVM no los necesitan para trabajar, solo necesita el kernel de la función de $K$.
Dicho esto, es posible escribir una fórmula para $\Phi$. El espacio de características que $\Phi$ mapas es una especie de resumen (y potencialmente infinito-dimensional), pero, esencialmente, la asignación de sólo utiliza el kernel para hacer algo simple característica de la ingeniería. En términos del resultado final, el modelo que terminan aprendizaje mediante el uso de kernels no es diferente de la tradicional función de la ingeniería popularmente se aplica en la regresión lineal y GLM de modelado, como tomar el registro de un predictor positivo de la variable antes de introducirlo en una fórmula de regresión. La matemática es principalmente sólo hay que asegurarse de que el kernel juega bien con el algoritmo de SVM, que tiene su cacareado ventajas de dispersión y escala bien para grandes conjuntos de datos.
Si usted todavía está interesado, aquí está cómo funciona. Esencialmente tomamos la identidad que quiere sostener, $\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \rangle = K(\mathbf{x},\mathbf{y})$, y la construcción de un espacio y el interior del producto que contiene, por definición. Para ello, definimos un espacio vectorial abstracto $V$ donde cada vector es una función del espacio de los datos que vive en, $\mathcal{X}$, para los números reales $\mathbb{R}$. Un vector $f$ $V$ es una función formada a partir de una combinación lineal finita de kernel rebanadas: $$f(\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$ Es conveniente escribir $f$ más compacto, como $$f = \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}$$ donde $K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y})$ es una función de dar una "rebanada" del kernel en $\mathbf{x}$.
El producto interior en el espacio no es el producto escalar ordinario, sino un resumen interior del producto basado en el kernel:
$$\langle \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}, \sum_{j=1}^n \beta_j K_{\mathbf{x}^{(j)}} \rangle = \sum_{i,j} \alpha_i \beta_j K(\mathbf{x}^{(i)},\mathbf{x}^{(j)})$$
Con la característica de un espacio definido de esta manera, $\Phi$ es un mapeo $\mathcal{X} \rightarrow V$, teniendo cada punto de $\mathbf{x}$ a la del núcleo "slice" en ese punto:
$$\Phi(\mathbf{x}) = K_\mathbf{x}, \quad \text{where} \quad K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y}). $$
Usted puede probar que $V$ es un producto interior espacio al $K$ es positiva definida kernel. Consulte este artículo para obtener más detalles. (Felicitaciones a f coppens para señalar esto!)
4. ¿Por qué es una de las características del espacio infinito-dimensional?
Esta respuesta le da un buen álgebra lineal explicación, pero aquí es una perspectiva geométrica, con la intuición y la prueba.
La intuición
Para cualquier punto fijo $\mathbf{z}$, tenemos un kernel función slice $K_\mathbf{z}(\mathbf{x}) = K(\mathbf{z},\mathbf{x})$. La gráfica de $K_\mathbf{z}$ es sólo una Gaussiana golpe centrado en $\mathbf{z}$. Ahora, si el espacio de características fueron sólo finito dimensionales, que significaría que podría tomar un conjunto finito de golpes en un conjunto fijo de puntos y cualquier forma Gaussiana protuberancia en cualquier otro lugar. Pero está claro que no hay manera de que podamos hacer esto, usted no puede hacer un nuevo golpe de los baches, porque el nuevo golpe podría estar muy lejos de los viejos. Así que, no importa cuántas función de los vectores (golpes) a los que tenemos, siempre podemos añadir nuevos golpes, y en el espacio de características estos son independientes de los vectores. Por lo que el espacio de características no puede ser finito dimensionales; tiene que ser infinito.
Prueba
Hacemos uso de la inducción. Suponga que tiene un conjunto arbitrario de puntos de $\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \ldots, \mathbf{x}^{(n)}$ de manera tal que los vectores $\Phi(\mathbf{x}^{(i)})$ son linealmente independientes en el espacio de características. Ahora encontrar un punto de $\mathbf{x}^{(n+1)}$ distinto de estas $n$ puntos, de hecho millones de sigmas lejos de todos ellos. Pretendemos que $\Phi(\mathbf{x}^{(n+1)})$ es linealmente independiente de la primera $n$ cuentan con vectores $\Phi(\mathbf{x}^{(i)})$.
La prueba por contradicción. Supongamos que al contrario que
$$\Phi(\mathbf{x}^{(n+1)}) = \sum_{i=1}^n \alpha_i \Phi(\mathbf{x}^{(i)})$$
Ahora toma el producto interior en ambos lados con un arbitrario $\mathbf{x}$. Por la identidad de $\langle \Phi(\mathbf{z}), \Phi(\mathbf{x}) \rangle = K(\mathbf{z},\mathbf{x})$, obtenemos
$$K(\mathbf{x}^{(n+1)},\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$
Aquí $\mathbf{x}$ es una variable libre, por lo que esta ecuación es una identidad que indica que dos funciones son las mismas. En particular, se dice que una Gaussiana centrada en $\mathbf{x}^{(n+1)}$ puede ser representado como una combinación lineal de Gaussianas en otros puntos de $\mathbf{x}^{(i)}$. Es obvio que la geometría que no se puede crear una Gaussiana golpe centrado en un punto a partir de un número finito de combinación de Gauss golpes centrados en otros puntos, sobre todo cuando todos los otros Gaussiano golpes son mil millones de sigmas de distancia. Así que nuestra suposición de dependencia lineal ha llevado a una contradicción, como nos propusimos mostrar.
davidsheldon
Puntos
211
El núcleo de la matriz del núcleo Gaussiano siempre ha rango completo para distintos $\mathbf x_1,...,\mathbf x_m$. Esto significa que cada vez que se añada un nuevo ejemplo, el rango aumenta por $1$. La forma más sencilla de ver esto si establece $\sigma$ muy pequeño. Entonces el núcleo de la matriz es casi en diagonal.
El hecho de que el rango siempre aumenta por uno de los medios que todas las proyecciones $\Phi(\mathbf x)$ en el espacio de características son linealmente independientes (no ortogonal, pero independiente). Por lo tanto, en cada ejemplo se agrega una nueva dimensión a la duración de las proyecciones de $\Phi(\mathbf x_1),...,\Phi(\mathbf x_m)$. Puesto que usted puede agregar uncountably infinitamente muchos ejemplos, el espacio de características debe tener dimensión infinita. Curiosamente, todas las proyecciones del espacio de entrada en el espacio de características de la mentira en una esfera, ya que $||\Phi(\mathbf x)||_{\mathcal H}^²=k(\mathbf x,\mathbf x)=1$. Sin embargo, la geometría de la esfera es plana. Usted puede leer más sobre esto en
Burges, C. J. C. (1999). La geometría y la Invariancia en el Kernel Basados en Métodos. En B. Schölkopf, C. J. C. Burges, & A. J. Smola (Eds.), Los avances en los Métodos del Núcleo de Vectores de Soporte de Aprendizaje (pp 89-116). MIT Press.
fcop
Puntos
2891
Para el fondo y las notaciones me refiero a la respuesta de Cómo calcular decisión límite de soporte de vectores?.
Así que las características de la 'original' espacio son los vectores $x_i$, el resultado binario $y_i \in \{-1, +1\}$ y los multiplicadores de Lagrange se $\alpha_i$.
Se sabe que el Núcleo puede ser escrito como $K(x,y)=\Phi(x) \cdot \Phi(y)$ ('$\cdot$' representa el interior del producto.) Donde $\Phi$ es (implícita y desconocido) transformación a un nuevo espacio de características.
Voy a tratar de dar algunos "intuitivo" explicación de lo que esto $\Phi$ parece, por lo que esta respuesta es no formal de la prueba, sólo quiere dar la sensación de que lo que yo pienso que esto funciona. No dude en corregirme si me equivoco. La base de mi explicación es la sección 2.2.1 de este pdf
Tengo para "transformar" mi espacio de características (para mi $x_i$) en algunos de los 'nuevos' espacio de características en la que la separación lineal será resuelto.
Para cada observación de la $x_i$, definir las funciones de $\phi_i(x)=K(x_i,x)$, así que tengo una función $\phi_i$ para cada elemento de mi entrenamiento de la muestra. Estas funciones $\phi_i$ abarcan un espacio vectorial. El espacio vectorial generado por los $\phi_i$, ten en cuenta que $V=span(\phi_{i, i=1,2,\dots N})$. ($N$ es el tamaño de la formación de la muestra).
Voy a tratar de argumentar que este espacio vectorial $V$ es el espacio vectorial lineal en el que la separación va a ser posible. Por definición de la extensión, cada uno de los vectores en el espacio vectorial $V$ puede escribirse como una combinación lineal de las $\phi_i$, es decir: $\sum_{i=1}^N \gamma_i \phi_i$ donde $\gamma_i$ son números reales. Así que, de hecho, $V=\{v=\sum_{i=1}^N \gamma_i \phi_i|(\gamma_1,\gamma_2,\dots\gamma_N) \in \mathbb{R}^N \}$
Tenga en cuenta que $(\gamma_1,\gamma_2,\dots\gamma_N)$ son las coordenadas de los vectores $v$ en el espacio vectorial $V$.
$N$ es el tamaño de la formación de la muestra y, por tanto, la dimensión del espacio vectorial $V$ puede ir a a $N$, dependiendo de si el $\phi_i$ son lineales independientes. Como $\phi_i(x)=K(x_i,x)$ (véase supra, hemos definido $\phi$ de esta manera), esto significa que la dimensión de $V$ depende del kernel utilizado y puede ir hasta el tamaño de la formación de la muestra.
Si el núcleo es 'complejo', entonces el $\phi_i(x)=K(x_i, x)$ todos serán independientes y, a continuación, la dimensión de la $V$$N$, el tamaño de la formación de la muestra.
La transformación, a la que se asigna el espacio de características a $V$ se define como
$\Phi: x_i \to \phi_i(x)=K(x_i, x)$.
Este mapa $\Phi$ mapas original de mi espacio de características en un espacio vectorial que puede tener una dimensión que va hasta el tamaño de mi entrenamiento de la muestra. Por lo $\Phi$ mapas de cada observación en mi entrenamiento de la muestra en un espacio vectorial donde los vectores son funciones. El vector $x_i$ de mi entrenamiento de la muestra es "mapeadas" a un vector en $V$, es decir, el vector $\phi_i$ con las coordenadas de todos iguales a cero, excepto el $i$-ésima coordenada es 1.
Obviamente, esta transformación (a) depende del kernel, (b) depende de los valores de $x_i$ en la formación de la muestra y (c) puede, dependiendo de mi núcleo, tiene una dimensión que va hasta el tamaño de mi entrenamiento de la muestra y (d) los vectores de $V$ parecerse a $\sum_{i=1}^N \gamma_i \phi_i$ donde $\gamma_i$ son números reales.
Buscando en la función de $f(x)$ Cómo calcular el límite de decisión de soporte de vectores? se puede ver que $f(x)=\sum_i y_i \alpha_i \phi_i(x)+b$. La decisión de la frontera encontrado por la SVM es $f(x)=0$.
En otras palabras, $f(x)$ es una combinación lineal de las $\phi_i$ $f(x)=0$ es lineal y la separación de hyperplane en el $V$-espacio : es una elección particular de la $\gamma_i$ es decir $\gamma_i=\alpha_i y_i$ !
El $y_i$ son conocidas a partir de nuestras observaciones, el $\alpha_i$ son los multiplicadores de Lagrange que la SVM ha encontrado. En otras palabras SVM encontrar, a través del uso de un kernel y mediante la resolución de un problema de programación cuadrática, lineal separación en la $V$-spave.
Este es mi comprensión intuitiva de cómo el 'kernel trick' permite 'implícita' transformar el original espacio de características en un nuevo espacio de características $V$, con una dimensión diferente. Esta dimensión depende del kernel que uso y para el kernel RBF esta dimensión se puede ir hasta el tamaño de la formación de la muestra. Como muestras de formación puede tener cualquier tamaño, este podría llegar a 'infinito'. Obviamente, en muchas dimensiones de los espacios el riesgo de sobreajuste aumentará.
Así que los núcleos son una técnica que permite SVM para transformar su espacio de características , ver también Lo que hace que el núcleo Gaussiano tan mágico para PCA, y también en general?
