Teorema de Cover: A grandes rasgos, dice que dado cualquier conjunto aleatorio de puntos finitos (con etiquetas arbitrarias), entonces con alta probabilidad estos puntos pueden hacerse linealmente separables [1] al mapearlos a una dimensión más alta [2].
Implicación: Genial, lo que este teorema me dice es que si tomo mi conjunto de datos y mapeo estos puntos a una dimensión más alta, entonces puedo encontrar fácilmente un clasificador lineal. Sin embargo, la mayoría de los clasificadores necesitan calcular algún tipo de similitud, como el producto de puntos, y esto significa que la complejidad temporal de un algoritmo de clasificación es proporcional a la dimensión del punto de datos. Por lo tanto, una mayor dimensión significa una mayor complejidad de tiempo (por no mencionar la complejidad de espacio para almacenar esos puntos de gran dimensión).
Truco del núcleo: Dejemos que $n$ sea la dimensión original de los puntos de datos y $f$ sea el mapa que mapea estos puntos a un espacio de dimensión $N (>> n)$ . Ahora bien, si existe una función $K$ que toma las entradas $x$ y $y$ del espacio original y calcula $K(x, y) = \langle f(x), f(y) \rangle$ entonces soy capaz de calcular el producto punto en un espacio de mayor dimensión pero en complejidad $O(n)$ en lugar de $O(N)$ .
Implicación: Por lo tanto, si el algoritmo de clasificación sólo depende del producto punto y no depende del mapa real $f$ Puedo utilizar el truco del núcleo para ejecutar el algoritmo en un espacio de alta dimensión sin apenas coste adicional.
¿Implica la separabilidad lineal que los puntos de la misma clase se acercarán más que los puntos de clases diferentes? No, no hay ninguna garantía como tal. La separabilidad lineal no implica realmente que el punto de una misma clase se haya acercado o que los puntos de dos clases diferentes se hayan alejado.
Entonces, ¿por qué iba a funcionar kNN? No es necesario. Sin embargo, si lo hace, entonces es puramente por el núcleo.
¿Qué significa eso? Considere el vector de características booleanas $x = (x_1, x_2)$ . Cuando se utiliza el núcleo polinómico de grado dos, el vector de características $x$ se asigna al vector $(x_1^2, \sqrt{2} x_1x_2, x_2^2)$ . A partir de un vector de características booleanas, sólo con el polinomio de grado dos, hemos obtenido un vector de características de "conjunciones". Así, los propios núcleos producen unos brillantes mapas de características. Si sus datos tienen buenas características originales y si sus datos podrían beneficiarse de los mapas de características creados por estos núcleos. Por beneficio, quiero decir que las características producidas por estos mapas de características pueden acercar los puntos de la misma clase y alejar los puntos de clases diferentes, entonces kNN se beneficia del uso de los núcleos. De lo contrario, los resultados no serán diferentes de los que se obtienen al ejecutar kNN en los datos originales.
Entonces, ¿por qué utilizar el kNN del núcleo? Hemos demostrado que la complejidad de cálculo del uso de los núcleos es sólo ligeramente superior a la del kNN habitual y, si los datos se benefician del uso de los núcleos, ¿por qué no utilizarlos de todos modos?
¿Hay algún artículo que haya estudiado qué clase de datos pueden beneficiarse de los núcleos en kNN? Que yo sepa, no.
[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1
