¿Qué hace que el núcleo gaussiano sea tan mágico para PCA, y también en general?

67

Estaba leyendo sobre kernel PCA ( 1 , 2 , 3 ) con núcleos gaussianos y polinomiales.

¿Cómo separa el núcleo gaussiano aparentemente cualquier tipo de datos no lineales excepcionalmente bien? Realice un análisis intuitivo, así como uno matemáticamente involucrado si es posible.
¿Cuál es una propiedad del núcleo gaussiano (con ideal ) que otros núcleos no tienen? Las redes neuronales, SVM y redes RBF vienen a la mente. $\sigma$
¿Por qué no pasamos la norma, digamos, un PDF Cauchy y esperamos los mismos resultados?

machine-learning pca svm kernel-trick Simon Kuang
fuente

1

+1. Excelente pregunta que casi pasé por alto, porque no tenía una etiqueta [pca]. Editado ahora.

ameba dice Reinstate Monica

44

Buena pregunta. Me pregunto si la respuesta podría ser "oh sí, muchos otros granos también funcionarían bien, pero el gaussiano es bien conocido / fácil"

Stumpy Joe Pete

@StumpyJoePete No creo que sea una respuesta tan trivial. ¿Qué otro parámetro de ubicación de distribución es también su significado? ¿Qué parámetro de escala de otras distribuciones es también su varianza? ¿Qué otra distribución es tan universalmente intuitiva? Seguramente no es la distribución Cauchy, ¡ni siquiera tiene un medio!

shadowtalker

3

@ssdecontrol Estoy feliz de que me demuestren que estoy equivocado; He votado tanto la pregunta como una de las respuestas: creo que mi respuesta aburrida, aburrida y deflacionaria hace un buen incumplimiento que una respuesta real debería refutar.

Stumpy Joe Pete

Creo que esto puede ayudar: stats.stackexchange.com/questions/168051/…

54

Creo que la clave de la magia es la suavidad. Mi larga respuesta que sigue es simplemente explicar sobre esta suavidad. Puede o no ser una respuesta que espera.

Respuesta corta:

Dado un kernel definido positivo , existe su espacio correspondiente de funciones . Las propiedades de las funciones están determinadas por el núcleo. Resulta que si es un núcleo gaussiano, las funciones en son muy suaves. Entonces, una función aprendida (por ejemplo, una función de regresión, componentes principales en RKHS como en el núcleo PCA) es muy suave. Por lo general, la suposición de suavidad es sensata para la mayoría de los conjuntos de datos que queremos abordar. Esto explica por qué un núcleo gaussiano es mágico. $k$ $\mathcal{H}$ $k$ $\mathcal{H}$

Respuesta larga de por qué un núcleo gaussiano ofrece funciones suaves:

Un núcleo positivo definido define (implícitamente) un producto interno para el vector de características construido a partir de su entrada , y es un espacio de Hilbert. La notación significa un producto interno entre y . Para nuestro propósito, puede imaginar que es el espacio euclidiano habitual pero posiblemente con un número infinito de dimensiones. Imagine el vector habitual que es infinitamente largo como $k(x,y)$ $k(x,y)=\left\langle \phi(x),\phi(y)\right\rangle _{\mathcal{H}}$ $\phi(x)$ $x$ $\mathcal{H}$ $\left\langle \phi(x),\phi(y)\right\rangle$ $\phi(x)$ $\phi(y)$ $\mathcal{H}$ $\phi(x)=\left(\phi_{1}(x),\phi_{2}(x),\ldots\right)$ . En los métodos del kernel, es un espacio de funciones llamado reproducción del espacio Hilbert del kernel (RKHS). Este espacio tiene una propiedad especial llamada `` propiedad de reproducción '' que es que . Esto dice que para evaluar , primero se construye un vector de características (infinitamente largo como se mencionó) para . Luego construyes tu vector de características para denotado por (infinitamente largo). La evaluación de se obtiene tomando un producto interno de los dos. Obviamente, en la práctica, nadie construirá un vector infinitamente largo. Como solo nos importa su producto interno, solo evaluamos directamente el núcleo $\mathcal{H}$ $f(x)=\left\langle f,\phi(x)\right\rangle$ $f(x)$ $f$ $x$ $\phi(x)$ $f(x)$ $k$ . Eludir el cálculo de características explícitas y calcular directamente su producto interno se conoce como el "truco del núcleo".

¿Cuáles son las características?

diciendo características sin especificar cuáles son. Dado un núcleo , las características no son únicas. Pero se determina de manera única. Para explicar la suavidad de las funciones, consideremos las características de Fourier. Suponga una traducción invariante kernel , que significa , es decir, el kernel solo depende de la diferencia de los dos argumentos. El núcleo gaussiano tiene esta propiedad. Deje que denote la transformada de Fourier de . $\phi_{1}(x),\phi_{2}(x),\ldots$ $k$ $\left\langle \phi(x),\phi(y)\right\rangle$ $k$ $k(x,y)=k(x-y)$ $\hat{k}$ $k$

En este punto de vista de Fourier, las características de están dadas por . Esto significa que la representación de características de su función está dada por su transformada de Fourier dividida por la transformada de Fourer del núcleo . La representación de características de , que es es donde . Se puede demostrar que la propiedad de reproducción es válida (un ejercicio para los lectores). $f$ $f:=\left(\cdots,\hat{f}_{l}/\sqrt{\hat{k}_{l}},\cdots\right)$ $f$ $k$ $x$ $\phi(x)$ $\left(\cdots,\sqrt{\hat{k}_{l}}\exp\left(-ilx\right),\cdots\right)$ $i=\sqrt{-1}$

Como en cualquier espacio de Hilbert, todos los elementos que pertenecen al espacio deben tener una norma finita. Consideremos la norma al cuadrado de una : $f\in\mathcal{H}$

$\|f\|_{\mathcal{H}}^{2}=\left\langle f,f\right\rangle _{\mathcal{H}}=\sum_{l=-\infty}^{\infty}\frac{\hat{f}_{l}^{2}}{\hat{k}_{l}}.$

Entonces, ¿cuándo es esta norma finita, es decir, pertenece al espacio? Es cuando cae más rápido que para que la suma converja. Ahora, la transformada de Fourier de un núcleo gaussiano $f$ $\hat{f}_{l}^{2}$ $\hat{k}_{l}$ $k(x,y)=\exp\left(-\frac{\|x-y\|^{2}}{\sigma^{2}}\right)$

es otro gaussiano donde disminuye exponencialmente rápido con . Entonces, si va a estar en este espacio, su transformación de Fourier debe caer aún más rápido que el de . Esto significa que la función tendrá efectivamente solo unos pocos componentes de baja frecuencia con altos pesos. Una señal con solo componentes de baja frecuencia no se `` mueve '' mucho. Esto explica por qué un núcleo gaussiano le da una función suave. $\hat{k}_{l}$ $l$ $f$ $k$

Extra: ¿Qué pasa con un kernel de Laplace?

Si considera un núcleo de Laplace , su transformada de Fourier es una distribución de Cauchy que cae mucho más lento que el exponencial funcionan en la transformada de Fourier de un núcleo gaussiano. Esto significa que una función tendrá más componentes de alta frecuencia. Como resultado, la función dada por un núcleo de Laplace es `` más áspera '' que la dada por un núcleo gaussiano. $k(x,y)=\exp\left(-\frac{\|x-y\|}{\sigma}\right)$ $f$

¿Cuál es una propiedad del núcleo gaussiano que otros núcleos no tienen?

Independientemente del ancho gaussiano, una propiedad es que el núcleo gaussiano es `` universal ''. Intuitivamente, esto significa que, dada una función continua limitada (arbitraria), existe una función tal que y están cerca (en el sentido de hasta la precisión arbitraria necesaria. Básicamente, esto significa que el núcleo gaussiano proporciona funciones que pueden aproximarse a las funciones "agradables" (acotadas, continuas) arbitrariamente bien. Los granos gaussianos y de Laplace son universales. Un núcleo polinomial, por ejemplo, no lo es. $g$ $f\in\mathcal{H}$ $f$ $g$ $\|\cdot\|_{\infty})$

¿Por qué no pasamos la norma, digamos, un PDF Cauchy y esperamos los mismos resultados?

En general, puede hacer lo que quiera siempre que el resultante sea definitivo positivo. La definición positiva se define como para todos , y todos (conjunto de números naturales) . Si no es positivo definido, entonces no corresponde a un espacio interno del producto. Todo el análisis se rompe porque ni siquiera tiene un espacio de funciones como se mencionó. No obstante, puede funcionar empíricamente. Por ejemplo, el núcleo de la tangente hiperbólica (vea el número 7 en esta página ) $k$ $\sum_{i=1}^{N}\sum_{j=1}^{N}k(x_{i},x_{j})\alpha_{i}\alpha_{j}>0$ $\alpha_{i}\in\mathbb{R}$ $\{x_{i}\}_{i=1}^{N}$ $N\in\mathbb{N}$ $k$ $\mathcal{H}$

$k(x,y) = tanh(\alpha x^\top y + c)$

que pretende imitar unidades de activación sigmoideas en redes neuronales, solo es positivo definido para algunos ajustes de y . Aún así se informó que funciona en la práctica. $\alpha$ $c$

¿Qué pasa con otros tipos de características?

Dije que las características no son únicas. Para el kernel gaussiano, la expansión de Mercer proporciona otro conjunto de características . Consulte la Sección 4.3.1 del famoso libro de procesos gaussiano . En este caso, las características son polinomios de Hermite evaluados en . $\phi(x)$ $x$

wij
fuente

2

Todavía no estoy dispuesto a otorgar la recompensa, pero estoy tentado de otorgarla a esta respuesta, porque está muy dirigida a la pregunta y hace comparaciones explícitas con otros núcleos

shadowtalker

¡Finalmente esta pregunta obtuvo una gran respuesta! (+1) Estaba brevemente confundido por la notación que usaste aquí: - y en los siguientes párrafos. ¿No sería más clara una notación más explícita separando una función actúa sobre el espacio original y un vector , donde es funcional? Por cierto, ¿qué funciones están garantizadas para ser "reproducidas" por la "propiedad de reproducción"? ¿Todas? ¿Continuo? ¿Suave?

f (x) = ⟨ f, ϕ (x) ⟩

$f(x)=\left\langle f,\phi(x)\right\rangle$

f (x) = ⟨ Ψ (f), ϕ (x) ⟩

$f(x)=\left\langle \Psi(f),\phi(x)\right\rangle$

f (\cdot)

$f(\cdot)$

Ψ (f) \in H

$\Psi(f) \in \mathcal H$

Ψ (\cdot)

$\Psi(\cdot)$

ameba dice Reinstate Monica

@amoeba En la literatura, las personas no distinguen una representación de y la función misma. Si es necesario, a veces usan para representación para una función. Todas las funciones en el espacio tienen la propiedad de reproducción. Suave o no, eso lo especifica el núcleo. :)

f

$f$

f

$f$

f (\cdot)

$f(\cdot)$

H

$\mathcal{H}$

wij

Se actualizó la publicación. Se agregó un poco más en el kernel de tanh.

wij

Hmmm, creo que estoy confundido aquí. Comenzamos con un espacio vectorial , donde viven los puntos de datos . Luego elegimos un núcleo definida positiva . Luego afirmamos que el Teorema 1 sostiene: puede realizarse como un producto de punto en algún espacio Hilbert , tal que , donde . Bueno. Y ahora dice que cualquier función actúe sobre puede realizarse como un producto escalar de su representación

X

$\mathcal X$

x

$x$

k (\cdot, \cdot) : X \times X \to R

$k(\cdot, \cdot): \mathcal X \times \mathcal X \to \mathbb R$

k

$k$

H

$\mathcal H$

k (x, y) = ⟨ ϕ (x), ϕ (y) ⟩

$k(x,y) = \langle \phi(x), \phi(y)\rangle$

ϕ : X \to H

$\phi:\mathcal X \to \mathcal H$

f (x)

$f(x)$

X

$\mathcal X$

f \in H

$f\in \mathcal H$ con ? ¿Es esto correcto?

ϕ (x)

$\phi(x)$

ameba dice Reinstate Monica

18

Haré todo lo posible para responder esta pregunta no porque sea un experto en el tema (todo lo contrario), sino porque tengo curiosidad sobre el campo y el tema, combinado con la idea de que podría ser una buena experiencia educativa . De todos modos, aquí está el resultado de mi breve investigación amateur sobre el tema.

TL; DR : consideraría el siguiente pasaje del trabajo de investigación "La conexión entre los operadores de regularización y los núcleos de vectores de soporte" como la respuesta corta a esta pregunta:

Los núcleos gaussianos tienden a producir un buen rendimiento bajo supuestos generales de suavidad y deben considerarse especialmente si no se dispone de un conocimiento adicional de los datos.

Ahora, una respuesta detallada (a lo mejor de mi entendimiento; para detalles matemáticos, use referencias).

Como sabemos, el análisis de componentes principales (PCA) es un enfoque muy popular para la reducción de la dimensionalidad , solo y para la clasificación posterior de datos: http://www.visiondummy.com/2014/05/feature-extraction-using-pca . Sin embargo, en situaciones, cuando los datos conllevan dependencias no lineales (en otras palabras, linealmente inseparables ), la PCA tradicional no es aplicable (no funciona bien). Para esos casos, se pueden usar otros enfoques, y PCA no lineal es uno de ellos.

Enfoques, donde PCA se basa en el uso de la función del kernel, generalmente se hace referencia al uso de un término general "kernel PCA" ( kPCA ). El uso de la función de base radial gaussiana (RBF) es probablemente la variación más popular. Este enfoque se describe en detalle en múltiples fuentes, pero me gusta mucho una excelente explicación de Sebastian Raschka en esta publicación de blog . Sin embargo, si bien menciona la posibilidad de usar funciones de kernel, además de Gaussian RBF, la publicación se centra en este último debido a su popularidad. Esta bonita publicación de blog , que presenta aproximaciones de kernel y truco de kernel , menciona una posible razón más para la popularidad del kernel gaussiano para PCA: la dimensionalidad infinita.

Se pueden encontrar ideas adicionales en varias respuestas sobre Quora. En particular, leer esta excelente discusión revela varios puntos sobre las posibles razones de la popularidad del núcleo gaussiano, de la siguiente manera.

Los granos gaussianos son universales :

Los núcleos gaussianos son núcleos universales, es decir, su uso con la regularización adecuada garantiza un predictor óptimo global que minimiza los errores de estimación y aproximación de un clasificador.

Los granos gaussianos son circulares (¿qué conduce a la dimensionalidad infinita mencionada anteriormente?)
Los granos gaussianos pueden representar "terrenos muy variables"
El siguiente punto, que respalda la conclusión principal anterior, se entrega mejor citando al autor:

El kernel gaussiano RBF es muy popular y es un buen kernel predeterminado, especialmente en ausencia de conocimiento experto sobre datos y dominio porque también subsume el núcleo polinomial y lineal. Los núcleos lineales y los núcleos polinomiales son un caso especial del núcleo gaussiano RBF. Los núcleos gaussianos RBF son modelos no paramétricos, lo que esencialmente significa que la complejidad del modelo es potencialmente infinita porque el número de funciones analíticas es infinito.

Los núcleos gaussianos son óptimos (en suavidad , lea más aquí - mismo autor):

Un kernel gaussiano es solo un filtro de paso de banda; Selecciona la solución más suave. [...] Un núcleo gaussiano funciona mejor cuando la suma infinita de derivados de alto orden converge más rápido, y eso sucede para las soluciones más fluidas.

Finalmente, puntos adicionales de esta buena respuesta :

Los núcleos gaussianos admiten modelos infinitamente complejos
Los granos gaussianos son más flexibles

NOTAS

El punto mencionado anteriormente acerca de que el kernel gaussiano es la elección óptima , especialmente cuando no hay conocimiento previo sobre los datos, está respaldado por la siguiente oración de esta respuesta CV :

En ausencia de conocimiento experto, el núcleo de la función de base radial es un buen núcleo predeterminado (una vez que lo haya establecido, es un problema que requiere un modelo no lineal).

Para aquellos curiosos sobre las diferencias no esenciales entre el kernel gaussiano RBF y el kernel gaussiano estándar, esta respuesta podría ser de interés: https://stats.stackexchange.com/a/79193/31372 .

Para aquellos interesados en implementar kPCA por placer o negocios, esta buena publicación de blog puede ser útil. Está escrito por uno de los autores (¿creadores?) De Accord.NET , un marco de trabajo de código abierto .NET muy interesante para análisis estadístico, aprendizaje automático, procesamiento de señales y mucho más.

Aleksandr Blekh
fuente

55

Aprecio y aplaudo el esfuerzo realizado para componer esta respuesta, pero al mismo tiempo debo decir que cita muchas fuentes que no son muy autorizadas y que proporcionan solo este tipo de explicaciones generales que pueden ser correctas pero podrían También sea completamente falso. Por lo tanto, el núcleo RBF es un núcleo estacionario isotrópico con un espacio de Hilbert de reproducción de dimensiones infinitas. ¡Bueno! ¿Hay otros núcleos con estas propiedades? Si es así, ¿por qué RBF sería mejor que todos ellos? De hecho, ¿existe algún respaldo empírico a la afirmación de que RBF supera a dichos competidores?

ameba dice Reinstate Monica

@amoeba: Gracias por sus amables palabras. Con respecto a las fuentes que he usado, tiene razón en parte: es una mezcla y algunas fuentes son solo opiniones. Sin embargo, algunas fuentes (es decir, las publicaciones de blog) en sí mismas citan documentos sólidos. En este punto, me atraía más la calidad de una explicación que su rigor. En cuanto a sus preguntas, me estoy preparando para responderlas más tarde. Necesito leer un poco más de teoría. Ya he compilado fuentes con soporte empírico, pero necesito más tiempo para su sistematización (y dormir, :).

Aleksandr Blekh

1

Tengo la sensación de que el hecho de que el gaussiano tiene la máxima entropía entre las distribuciones simétricas reales juega un papel en su primer punto sobre el buen rendimiento bajo suposición general

shadowtalker

2

También @AleksandrBlekh esta es una compilación fantástica. La gente critica a Quora, pero no es menos autoritario que vincular a otra respuesta aquí

shadowtalker

@ssdecontrol: Gracias por sus amables palabras. Me alegra que estemos en la misma página sobre el tema. Tengo información adicional para abordar el comentario de ameba, así que mira este espacio, si estás interesado.

Aleksandr Blekh

8

Déjame poner mis dos centavos.

La forma en que pienso sobre los núcleos gaussianos son, en cierto sentido, como clasificadores de vecinos más cercanos. Lo que hace un núcleo gaussiano es que representa cada punto con la distancia a todos los demás puntos del conjunto de datos. Ahora piense en clasificadores con límites lineales o polinómicos, los límites están limitados a ciertas formas. Sin embargo, cuando miras al vecino más cercano, el límite prácticamente puede tomar cualquier forma. Es por eso que creo que pensamos en el núcleo gaussiano también como no paramétrico, es decir, ajustando el límite en función de los datos. Otra forma de pensar en eso es que el núcleo gaussiano se ajusta a la forma local en una región, de manera similar a cómo un vecino más cercano ajusta localmente el límite mirando la distancia a otros puntos en la región local.

No tengo un argumento matemático para esto, pero creo que el hecho de que el núcleo gaussiano de hecho se asigne a un espacio de dimensiones infinitas tiene algo que ver con su éxito. Para los núcleos lineales y polinomiales, los productos de punto se toman en espacios dimensionales finitos; por lo tanto, parece más poderoso hacer cosas en un espacio más grande. Espero que alguien comprenda mejor estas cosas. Eso también significa que si podemos encontrar otros núcleos con espacios dimensionales infinitos, también deberían ser bastante poderosos. Desafortunadamente, no estoy familiarizado con ninguno de esos núcleos.

Para su último punto, creo que Cauchy pdf o cualquier otro pdf que de alguna manera mida la distancia a otros puntos debería funcionar igualmente bien. Nuevamente, no tengo un buen argumento matemático para eso, pero la conexión con el vecino más cercano lo hace plausible.

Editar:

Aquí hay algunas ideas sobre cómo pensar en un clasificador que usa núcleos gaussianos como clasificadores vecinos más cercanos. Primero, pensemos en lo que hace un clasificador vecino más cercano. Esencialmente, un clasificador vecino más cercano es un clasificador estándar que utiliza las distancias entre puntos como entradas. Más formalmente, imagine que creamos una representación de entidad para cada punto en el conjunto de datos calculando su distancia a todos los otros puntos. Arriba, es una función de distancia. Entonces, lo que hace un clasificador vecino más cercano es predecir la etiqueta de clase para un punto basado en esta representación de entidad y etiquetas de clase para los datos. donde $\phi_i$ $x_i$

ϕ_{i} = (d (x_{i}, x_{1}), d (x_{i}, x_{2}), \dots, d (x_{i}, x_{n}))

$\phi_i = (d(x_i,x_1), d(x_i, x_2), \ldots, d(x_i, x_n))$

d

$d$

p_{i} = f (ϕ_{i}, y)

$p_i = f(\phi_i, y)$

p_{i}

$p_i$ es la predicción para el punto de datos e es un vector de etiquetas de clase para .

x_{i}

$x_i$

y

$y$

x_{1}, x_{2}, \dots, x_{n}

$x_1, x_2, \ldots, x_n$

La forma en que pienso sobre los núcleos es que hacen algo similar; crean una representación característica de cada punto utilizando sus valores de núcleo con otros puntos en el conjunto de datos. Similar al caso del vecino más cercano, más formalmente sería Ahora la conexión con el vecino más cercano es bastante obvia; Si nuestra función de kernel es alguna medida relacionada con las medidas de distancia que usamos en los clasificadores vecinos más cercanos, nuestro clasificador basado en el kernel será similar a un modelo vecino más cercano.

ϕ_{i} = (k (x_{i}, x_{1}), k (x_{i}, x_{2}), \dots, k (x_{i}, x_{n}))

$\phi_i = (k(x_i, x_1), k(x_i, x_2), \ldots, k(x_i, x_n))$

Nota: Los clasificadores que entrenamos usando núcleos no funcionan directamente con estas representaciones , pero creo que eso es lo que hacen implícitamente. $\phi_i$

goker
fuente

La interpretación de los vecinos más cercanos es interesante. ¿Crees que podrías ampliar eso un poco? Creo que lo entiendo pero no estoy seguro de hacerlo.

shadowtalker

@ssdecontrol agregué algunos comentarios; Espero que sean de ayuda.

goker

6

La razón es que la dimensión VC para los núcleos gaussianos es infinita y, por lo tanto, dados los valores correctos para los parámetros (sigma), pueden clasificar correctamente un número arbitrariamente grande de muestras.

Los RBF funcionan bien porque aseguran que la matriz tenga un rango completo. La idea es que , y los términos fuera de la diagonal pueden hacerse arbitrariamente pequeños disminuyendo el valor de . Observe que el núcleo corresponde a un producto de puntos en el espacio de características. En este espacio de características, la dimensión es infinita (considerando la expansión en serie de la exponencial). Por lo tanto, se podría ver esto como proyectar esos puntos en diferentes dimensiones para que pueda separarlos. $K(x_{i},x_{j})$ $K(x_{i},x_{i}) > 0$ $\sigma$

Considere, por el contrario, el caso de los núcleos lineales, que solo pueden romper cuatro puntos en el plano.

Puede echar un vistazo a este documento , aunque es muy técnico. Uno de los libros estándar sobre SVM debería hacer que este concepto sea más accesible.

jpmuc
fuente

1

'Los RBF funcionan bien porque aseguran que la matriz sea de rango completo': esto es cierto para todas las funciones válidas del núcleo (Mercer) (incluida la lineal), por lo que no estoy seguro de cómo explica el supuesto -Rendimiento del RBF.

K (x_{i}, x_{j})

$K(x_i,x_j)$

user603

2

Además de lo que acaba de escribir @ user603: ¿hay otros núcleos populares con una dimensión de VC infinita (dimensión del espacio objetivo)? Si es así, ¿son tan buenos como el RBF?

ameba dice Reinstate Monica

2

¿No es la dimensión VC una propiedad de un conjunto de clasificadores, no la propiedad de un núcleo?

wij

2

@ usuario603: esto no es cierto. Los núcleos Mercer solo requieren que la matriz del núcleo sea semidefinida positiva; Pueden ser singulares. Por ejemplo, el núcleo lineal de hecho proporciona matrices de núcleo singulares si está en su conjunto de puntos. (Por supuesto, la mayoría de los granos son estrictamente positivos y, por lo tanto, esta no es una propiedad particularmente distintiva del RBF gaussiano).

x_{i} = 0

$x_i = 0$

Dougal

¿Qué hace que el núcleo gaussiano sea tan mágico para PCA, y también en general?

Respuestas: