Se afirma que SVM utilizando el kernel RBF es similar (equivalente) al método de clasificación K vecino más cercano. No tengo muy claro el proceso de análisis para construir este tipo de relación. Gracias por las explicaciones.
Respuestas
¿Demasiados anuncios?
regispaulo
Puntos
1
El límite de decisión para el algoritmo 1-NN es la unión de las celdas de Voronoi de cada instancia de entrenamiento.
En cuanto a SVM, cuando se utiliza el kernel RBf y si no hay regularización, la frontera de decisión también será una aproximación de la unión de las celdas de Voronoi. Así que en este caso, estos métodos son los mismos en términos de rendimiento, pero dependiendo de la estructura del conjunto de datos, sus complejidades podrían ser muy diferentes. Si el número de vectores de soporte en SVM es alto, tanto la complejidad de entrenamiento como la de prueba de SVM serán mucho mayores que 1-NN.
El poder de SVM, sin embargo, se hará evidente cuando se hace la regularización.
jpmuc
Puntos
4817
No son tan parecidos, pero están relacionados. La cuestión es que tanto kNN como RBF son métodos no paramétricos para estimar la densidad de probabilidad de los datos.
Para verlo, consideremos primero el caso de los métodos de núcleo. Supongamos que consideramos una región del espacio de características $R$ . Si se extraen puntos de muestra de la distribución de probabilidad real, p(x), de forma independiente, entonces la probabilidad de extraer una muestra de esa región es, $$ P = \int_{R} p(x) dx $$ ¿Y si tiene $N$ ¿puntos? La probabilidad de que $K$ puntos de esos $N$ caída de puntos en la región $R$ sigue la distribución binomial, $$ Prob(K) = {{N} \choose {K}}P^{K}(1-P)^{N-K} $$
En $N \to \infty$ esta distribución tiene un pico pronunciado, de modo que la probabilidad puede aproximarse por su valor medio $\frac{K}{N}$ . Una aproximación adicional es que la distribución de probabilidad sobre $R$ permanece aproximadamente constante, de modo que se puede aproximar la integral por, $$ P = \int_{R} p(x) dx \approx p(x)V $$ donde $V$ es el volumen total de la región. Con estas aproximaciones $p(x) \approx \frac{K}{NV}$ .
La idea de los métodos kernel es dividir el espacio de características en varias regiones, estimar los recuentos de cada región y utilizar esas estimaciones puntuales para interpolar todo el espacio de características. Puede parecer un galimatías.
Primero veamos cómo podemos reescribir la estimación de la probabilidad. Sea $\{x_{i}\}_{1}^{N}$ sea su conjunto de datos. Considere una región $V = h^{d}$ que corresponde a un hipercubo de lado $h$ en el $d$ -de características. La función Heaviside se define por, $$ H(x) = \begin{cases} 1, \text{if } |x| < 1/2 & \\ 0, \text{otherwise} \end{cases} $$
Entonces podemos escribir el número total de puntos que caen dentro del hipercubo, $V$ como, $$ K = \sum_{n}H\left(\frac{x-x_{n}}{h}\right) $$ donde $x$ es el centro del hipercubo. O bien, V es la vecindad centrada en $x$ y éste es el número de puntos cercanos a $x$ . Si sustituimos de nuevo, $$ p(x) \approx \sum_{n} \frac{1}{h^{d}}H\left(\frac{x-x_{n}}{h}\right) $$
El caso de RBF es una versión suavizada, donde $H$ se considera una gaussiana. Para el caso de kNN, consulte esta otra pregunta .
Obsérvese que estos dos algoritmos abordan el mismo problema de forma diferente: los métodos de núcleo fijan el tamaño de la vecindad ( $h$ ) y, a continuación, calcular $K$ mientras que kNN fija el número de puntos, $K$ y, a continuación, determina la región del espacio que contiene esos puntos.
Así que sí, están relacionados, pero no son equivalentes.
P.D. SVM no estima la densidad de probabilidad, sino que encuentra el hiperplano de separación. Aquí sólo he comparado los métodos kernel frente a kNN para la estimación de la densidad. Incluso para la detección de novedades, SVM no estima la f.d.p. sino su soporte (aquellos puntos para los que $p(x) \gt 0$ que es otra historia.
