¿Qué son los núcleos en aprendizaje automático y SVM y por qué los necesitamos?

Hablando brevemente , un núcleo es un atajo que nos ayuda a hacer ciertos cálculos más rápido, lo que de otro modo implicaría cálculos en un espacio dimensional superior.

Definición matemática : K (x, y) = . Aquí K es la función del núcleo, x, y son n entradas dimensionales. f es un mapa del espacio de dimensión n al espacio de dimensión m. denota el producto escalar. generalmente m es mucho más grande que n.

Intuición : normalmente calcular requiere que primero calculemos f (x), f (y) y luego hagamos el producto puntual. Estos dos pasos de cálculo pueden ser bastante caros ya que implican manipulaciones en m espacio dimensional, donde m puede ser un gran número. Pero después de todos los problemas de ir al espacio de alta dimensión, el resultado del producto escalar es realmente escalar: ¡volvemos al espacio unidimensional nuevamente! Ahora, la pregunta que tenemos es: ¿realmente necesitamos pasar por todos los problemas para obtener este número? ¿Realmente tenemos que ir al espacio m-dimensional? La respuesta es no, si encuentra un núcleo inteligente.

Ejemplo simple: x = (x1, x2, x3); y = (y1, y2, y3). Entonces, para la función f (x) = (x1x1, x1x2, x1x3, x2x1, x2x2, x2x3, x3x1, x3x2, x3x3), el núcleo es K (x, y) = () ^ 2.

Pongamos algunos números para hacer esto más intuitivo: supongamos que x = (1, 2, 3); y = (4, 5, 6). Luego:
f (x) = (1, 2, 3, 2, 4, 6, 3, 6, 9)
f (y) = (16, 20, 24, 20, 25, 30, 24, 30, 36)
= 16 + 40 + 72 + 40 + 100+ 180 + 72 + 180 + 324 = 1024

Mucho álgebra. Principalmente porque f es un mapeo del espacio tridimensional a 9 dimensional.

Ahora usemos el núcleo en su lugar:
K (x, y) = (4 + 10 + 18) ^ 2 = 32 ^ 2 = 1024
El mismo resultado, pero este cálculo es mucho más fácil.

Belleza adicional de Kernel: ¡los núcleos nos permiten hacer cosas en infinitas dimensiones! A veces, ir a una dimensión superior no solo es computacionalmente costoso, sino también imposible. f (x) puede ser un mapeo de n dimensión a dimensión infinita, de lo que podemos tener poca idea de cómo tratar. Entonces kernel nos da un maravilloso atajo.

Relación con SVM: ahora, ¿cómo se relaciona con SVM? La idea de SVM es que y = w phi (x) + b, donde w es el peso, phi es el vector de características y b es el sesgo. si y> 0, clasificamos el dato a la clase 1, de lo contrario a la clase 0. Queremos encontrar un conjunto de peso y sesgo de manera que el margen se maximice. Las respuestas anteriores mencionan que el núcleo hace que los datos sean linealmente separables para SVM. Creo que una forma más precisa de decir esto es que los núcleos no hacen que los datos sean linealmente separables. El vector de características phi (x) hace que los datos sean linealmente separables . Kernel debe hacer que el proceso de cálculo sea más rápido y fácil, especialmente cuando el vector de características phi es de muy alta dimensión (por ejemplo, x1, x2, x3,…, x_D ^ n, x1 ^ 2, x2 ^ 2,…., X_D ^ 2).

Por qué también se puede entender como una medida de similitud:
si ponemos la definición de kernel arriba, , en el contexto de SVM y vectores de características, se convierte en . El producto interno significa la proyección de phi (x) sobre phi (y). o coloquialmente, cuánta superposición tienen xey en su espacio de características. En otras palabras, cuán similares son.

Mucho asombro y misticismo están asociados con los núcleos, pero creemos que no son tan importantes. Los granos son una combinación de dos buenas ideas, tienen una propiedad importante y están sujetos a una limitación importante. También es lamentable que las máquinas de vectores de soporte y los núcleos estén tan unidos entre sí. Los núcleos son la idea de sumar funciones que imitan la similitud (inducen una codificación positiva de proximidad) y las máquinas de vectores de soporte son la idea de resolver un problema dual inteligente para maximizar una cantidad llamada margen. Cada uno es una herramienta útil incluso sin el otro.

Las dos buenas ideas están relacionadas y desafortunadamente tratadas como si fueran lo mismo. Las dos buenas ideas que prometimos son:

1. El “truco del núcleo”. Agregar nuevas características / variables que son funciones de sus otras variables de entrada puede cambiar problemas linealmente inseparables en problemas linealmente separables. Por ejemplo, si nuestros puntos se codificaron no como u (i) = (x (i), y (i)) sino como u (i) = (x (i), y (i), x (i) * x ( i), y (i) * y (i), x (i) * y (i))
2. A menudo no necesitas las coordenadas de u (i). Solo le interesan las funciones de distancias || u (i) -u (j) | ^ 2 y, en muchos casos, puede obtenerlas mediante productos internos y relaciones como || u (i) -u (j) || ^ 2 = + – 2 .

Nos expandiremos sobre estos temas más adelante.

La propiedad importante es que los núcleos se ven como productos internos en un espacio transformado. La definición de un núcleo es: existe una función mágica phi () tal que para todo u, v:

.

Esto significa que k (.,.) Se comporta como un producto interno en algún espacio (posiblemente desconocido). La consecuencia importante es la semi-definición positiva, que implica k (u, u) ≥0 para todo u (y esto se deduce del hecho sobre los productos internos sobre los números reales que ≥0 para todo z) . Esta es la razón por la cual los problemas de optimización que usan el núcleo como su codificación están bien formados (como el problema de optimización de maximizar el margen, que es cómo funcionan las máquinas de vectores de soporte). Puede “regularizar” los problemas de optimización con una penalización del núcleo porque se comporta como una norma. Sin la propiedad semidefinida positiva, todos estos problemas de optimización podrían “ejecutarse hasta el infinito negativo” o utilizar términos negativos (que no son posibles desde un núcleo) para ocultar altas tasas de error. Los límites de las funciones del núcleo (no poder convertir las penalizaciones de distancia en bonos) ayudan a garantizar que el resultado de la optimización sea realmente útil (y no solo una falla en nuestra codificación problemática).

Y esto nos lleva a las principales limitaciones de los núcleos. La transformación phi () puede ser arbitrariamente mágica, excepto cuando se transforma un vector que no sabe cuál es el otro vector y phi () ni siquiera sabe qué lado del producto interno está codificando. Es decir, los núcleos no son tan potentes como cualquiera de las siguientes formas:

• husmeando (conociendo al otro):
• posicional (saber a qué parte del mapeo interno del producto):
• totalmente general:

No todo es un núcleo.

Algunos no núcleos son:

1. k (u, v) = -c para cualquier c> 0
2. k (u, v) = || uv ||
   Esto se puede demostrar de la siguiente manera. Supongamos que k (u, v) es un núcleo con k (u, u) = 0 para todos los u (lo cual es necesario para hacer coincidir || uv || como || uu || = 0 para todos los u). Por definición
   de núcleos k (u, u) = para alguna función real con valor vectorial phi (.). Pero, por las propiedades del producto interno real interno <.,.>, Esto significa que phi (u) es
   el vector cero para todos ustedes. Entonces k (u, v) = 0 para todo u, v y no coincide con || uv || para cualquier u, v tal que u ≠ v.

Hay algunos núcleos obvios:

1. k (u, v) = c para cualquier c ≥ 0 (núcleos constantes no negativos)
2. k (u, v) = (el núcleo de identidad)
3. k (u, v) = f (u) f (v) para cualquier función con valor real f (.)
4. k (u, v) = para cualquier función con valor vectorial real f (.) (de nuevo, la definición de un núcleo)
5. k (u, v) = transponer (u) B v donde B es cualquier matriz simétrica positiva simétrica

Y hay varias formas sutiles de construir nuevos núcleos a partir de viejos. Si q (.,.) Yr (.,.) Son núcleos, entonces también lo son:

1. k (u, v) = q (u, v) + r (u, v)
2. k (u, v) = cq (u, v) para cualquier c ≥ 0
3. k (u, v) = q (u, v) r (u, v)
4. k (u, v) = q (f (u), f (v)) para cualquier función con valor vectorial real f (.)
5. k (u, v) = lim_ {k-> infinito} q_k (u, v) donde q_k (u, v) es una secuencia de núcleos y el límite existe.
6. k (u, v) = p (q (u, v)) donde p (.) es cualquier polinomio con todos los términos no negativos.
7. k (u, v) = f (q (u, v)) donde f (.) es cualquier función con una serie de Taylor absolutamente convergente con todos los términos no negativos.

La mayoría de estos hechos están tomados del excelente libro: John Shawe-Taylor y Nello Cristianini “Kernel Methods for Pattern Analysis”, Cambridge 2004. Estamos permitiendo
núcleos de la forma k (u, v) = donde phi (.) se mapea en un espacio vectorial de dimensiones infinitas (como una serie). La mayoría de estos hechos pueden ser verificados por
imaginando cómo alterar la función phi (.). Por ejemplo, para agregar dos núcleos, simplemente construya un vector más grande con suficientes ranuras para todas las coordenadas para la codificación de vectores
los phi (.) de los dos núcleos que está intentando agregar. Para escalar un núcleo por c, multiplique todas las coordenadas de phi () por sqrt (c).

Multiplicar dos granos es lo más complicado. Sin pérdida de generalidad, suponga q (u, v) = y r (u, v) = yf (.) Y g ( .) se mapean en el mismo espacio vectorial de dimensiones finitas R ^ m (cualquier otra situación se puede simular o aproximar rellenando con ceros y / o tomando límites). Imagine una nueva función vectorial p (.) Que se correlaciona con R ^ {m * m} de manera que p (z) _ {m * (i-1) + j} = f (z) _i g (z) _j. Es fácil comprobar que k (u, v) =

es un núcleo yk (u, v) = q (u, v) r (u, v). (La prueba de referencia usa la notación tensorial y el producto Schur, pero estos son grandes martillos que usan los matemáticos cuando no quieren perder el tiempo con los índices de re-codificación).

Tenga en cuenta que uno de los atractivos de los métodos de kernel es que nunca tiene que implementar ninguna de las construcciones anteriores. Lo que haces es pensar en términos de subrutinas (fácil para los informáticos, desagradable para los matemáticos). Por ejemplo: si tuviera acceso a dos funciones q (.,.) Yr (.,.) Que afirman ser núcleos y desea el núcleo del producto, simplemente, cuando se le pida que evalúe el núcleo, simplemente obtenga los resultados para los dos sub-núcleos y se multiplican (por lo que nunca necesita ver el espacio en el que phi (.) está trabajando implícitamente).

Esta implicidad puede ser importante (aunque se hace demasiado). Por ejemplo, los gaussianos que hemos estado utilizando en todo momento son núcleos, pero núcleos de dimensión infinita, por lo que no podemos representar directamente el espacio en el que viven. Para ver el gaussiano es un núcleo, tenga en cuenta lo siguiente:

Y para todos los c ≥ 0, cada uno de los tres términos de la derecha es un núcleo (el primero porque la serie Taylor de exp () es absolutamente convergente y no negativa y los dos últimos son la forma f (u) f (v) enumeramos como núcleos obvios). El truco es mágico, pero la idea es utilizar el hecho de que la distancia al cuadrado euclidiana se divide muy bien en productos de punto (|| uv || ^ 2 = ) y exp () convierte la suma a la multiplicación. Es bastante notable que los núcleos (que son una generalización de productos internos que inducen espacios medio abiertos) pueden codificar conceptos acotados (más sobre esto más adelante cuando analicemos la dimensión VC del gaussiano).

El gran beneficio de la máquina de vectores de soporte es que con acceso solo a las etiquetas de datos y la función del kernel (de hecho, solo la función de kernel evaluada en pares de datos de entrenamiento) la máquina de vectores de soporte puede resolver rápidamente el margen óptimo y el peso de los datos logrando este margen

Por diversión, conectemos un nuevo núcleo llamado núcleo coseno:

(c ≥ 0).

Se puede pensar que este núcleo tiene una función phi (.) Que toma un vector z y agrega una coordenada adicional de sqrt (c) y luego proyecta el vector resultante en la esfera de la unidad. Este núcleo induce conceptos que se parecen a parábolas, como se ve en la figura 1.

Figura 1: concepto de ejemplo de coseno

La Figura 2 muestra el modelo de suma de conceptos (agregar todas las funciones de descuento con el mismo peso). En este caso, es demasiado amplio (promediar los conceptos de coseno que no son conceptos acotados como los gaussianos) crea un modelo demasiado amplio. El modelo no solo se generaliza mal (no coincide con la forma del diagrama de verdad) sino que también se equivoca con algunos de sus propios datos de entrenamiento.

Figura 2: Modelo de suma de núcleo de coseno

Y la figura 3 muestra el excelente ajuste devuelto por la máquina de vectores de soporte. En realidad, un ajuste excelente determinado por 4 vectores de soporte (indicados por etiquetas más grandes). Observe también que la máquina de vectores de soporte que utiliza conceptos ilimitados generó un modelo ilimitado muy bueno (ilimitado en el sentido de que las regiones azul y roja son infinitas). Al cambiar el núcleo o las funciones / conceptos de descuento, cambiamos el sesgo inductivo. Por lo tanto, cualquier conocimiento de qué tipo de modelo queremos (una clase limitada o no) debería influir en gran medida en nuestra elección de las funciones del núcleo (ya que la máquina de vectores de soporte solo puede elegir pesos para las funciones del núcleo, no ajustar sus formas o anchos de banda).

Figura 3: Modelo de vector de soporte de coseno

Otra familia de núcleos (que considero aflicciones) son los núcleos de “algo por nada”. Estos son núcleos de la forma:

o potencias superiores u otras funciones de acabado. La idea es que si observara la expansión de estos núcleos, vería muchos términos de orden superior (potencias de u_i y v_j)
y si estos términos estuvieran disponibles para la máquina de vectores de soporte, podría usarlos. Se afirma además que, además de obtener nuevas funciones de forma gratuita, no usa grados
de libertad explotándolos (para que los valide de forma cruzada y para modelos más simples). Ambas afirmaciones son falaces: no puede usar completamente los términos de orden superior porque están enredados con otros términos que no son ortogonales como resultado y la complejidad de un núcleo no es tan simple como los grados de libertad (pruebas sobre máquinas de vectores de soporte se expresan en términos de margen, no en términos de grados de libertad o incluso en términos de dimensión VC). El optimizador en el SVM se esfuerza por hacer una buena hipótesis utilizando los términos de orden superior, pero debido a las relaciones forzadas entre los términos, obtienes mejores ajustes como en la figura 4.

Figura 4: Modelo de vector de soporte de kernel mágico cuadrado

Si desea términos de orden superior, creo que es mucho mejor realizar una transformación primaria, por lo que los términos están disponibles en su forma más general. Es decir, volver a codificar el vector u = (x, y) como el vector más grande (x, y, x * y, x * x, y * y). Debe ser honesto: si está tratando de ajustar funciones más complicadas, está buscando un espacio de hipótesis más grande, por lo que necesita más datos para falsificar las hipótesis erróneas. Puede ser eficiente (no agregue términos que no cree que pueda usar, ya que dificultan la generalización), pero no puede obtener algo por nada (incluso con los métodos del núcleo).

Red neuronal y computadoras

crédito: John Mount

A2A.

Intuitivamente, una función del núcleo mide la similitud entre dos puntos de datos. La noción de similitud depende de la tarea. Entonces, por ejemplo, si su tarea es el reconocimiento de objetos, un buen núcleo asignará una puntuación alta a un par de imágenes que contienen los mismos objetos, y una puntuación baja a un par de imágenes con diferentes objetos. Tenga en cuenta que dicho núcleo captura una noción mucho más abstracta de similitud, en comparación con una función de similitud que solo compara dos imágenes píxel por píxel. Como otro ejemplo, considere una tarea de procesamiento de texto. Allí, una buena función del núcleo asignaría una puntuación alta a un par de cadenas similares, y una puntuación baja a un par de cadenas diferentes. Esta es la ventaja de las funciones del núcleo: pueden, en principio, capturar nociones de similitud arbitrariamente complejas, que se pueden usar en varios algoritmos de ML.

Por lo tanto, formalmente, una función del núcleo [matemática] K [/ matemática] toma dos puntos de datos [matemática] x_ {i} [/ matemática] y [matemática] x_ {j} [/ matemática] [matemática] \ in \ mathbb { R} ^ {d} [/ math], y produce una puntuación, que es un número real, es decir, [math] K: \ mathbb {R} ^ {d} \ times \ mathbb {R} ^ {d} \ rightarrow \ mathbb {R} [/ math].

Para utilizar las funciones del núcleo en los algoritmos ML más comunes, como los SVM, existen requisitos adicionales sobre las funciones del núcleo, de modo que puedan encajar en el marco. Considere el problema de optimización dual de SVM:

[matemáticas] \ max _ {\ alpha} 1 ^ T \ alpha – \ sum_ {i} \ sum_ {j} \ alpha_ {i} \ alpha_ {j} y_ {i} y_ {j} x_ {i} ^ Tx_ { j} [/ matemáticas]

sujeto a algunas restricciones que no son importantes para la discusión actual.

Tenga en cuenta que el valor óptimo de [math] \ alpha [/ math] dependerá de [math] x_ {i} ^ T x_ {j} [/ math] para todos los pares de puntos de datos [math] (x_ {i}, x_ {j}) [/ math]. Además, [matemática] x_ {i} ^ T x_ {j} [/ matemática] es una medida de similitud cruda entre [matemática] (x_ {i}, x_ {j}) [/ matemática]. En términos más generales, es posible que desee asignar sus datos a un nuevo espacio donde [math] x_ {i} [/ math] está asignado a [math] \ phi (x_ {i}) [/ math] y [math] x_ { j} [/ math] se asigna a [math] \ phi (x_ {j}) [/ math]. Entonces, tu función de similitud debería darte [matemáticas] \ phi (x_ {i}) ^ T \ phi (x_ {j}) [/ matemáticas]. Para [math] x_ {i} ^ Tx_ {j} [/ math], la asignación [math] \ phi (\ cdot) [/ math] es la función de identidad. [Vea aquí una discusión sobre el mapeo en SVM: la respuesta de Prasoon Goyal a En términos simples, ¿cómo funciona SVM?]

Por lo tanto, definir [math] K (x_ {i}, x_ {j}) = \ phi (x_ {i}) ^ T \ phi (x_ {j}) [/ math] y volver a colocar el problema de optimización original te dio

[matemáticas] \ max _ {\ alpha} 1 ^ T \ alpha – \ sum_ {i} \ sum_ {j} \ alpha_ {i} \ alpha_ {j} y_ {i} y_ {j} K (x_ {i}, x_ {j}) [/ matemáticas]

Ahora puede conectar cualquier función [math] \ mathbb {R} ^ {d} \ times \ mathbb {R} ^ {d} \ rightarrow \ mathbb {R} [/ math] como la función del núcleo en este problema de optimización como siempre que haya alguna función [matemática] \ phi (\ cdot) [/ matemática] para la cual [matemática] K (x_ {i}, x_ {j}) = \ phi (x_ {i}) ^ T \ phi ( x_ {j}) [/ math]. Tenga en cuenta que no necesita saber qué es [math] \ phi (\ cdot) [/ math]; solo el conocimiento de que existe es suficiente. Aquí es donde entra en juego el teorema de Mercer : establece que una función del núcleo [math] K (x_ {i}, x_ {j}) [/ math] tiene una representación [math] \ phi (x_ {i}) ^ T \ phi (x_ {j}) [/ math] para algunos [math] \ phi (\ cdot) [/ math] si y solo si es positivo semi-definido y simétrico . [Me saltearé las definiciones técnicas aquí para evitar desviarme de la idea principal de la pregunta; si tiene consultas específicas sobre esto, publique una pregunta por separado.]

La idea anterior se llama el truco Kernel : siempre que su problema de optimización dependa de [math] x_ {i}, x_ {j} [/ math] solo en forma de productos internos [math] x_ {i} ^ T x_ {j } [/ math], puede reemplazar [math] x_ {i} ^ T x_ {j} [/ math] por [math] K (x_ {i}, x_ {j}) [/ math], donde [math ] K (\ cdot, \ cdot) [/ math] satisface el teorema de Mercer.

Tenga en cuenta que en el primer segmento de la respuesta, observamos qué es una función del núcleo, mientras que en el segundo segmento, observamos las condiciones de las funciones del núcleo que pueden utilizarse en algoritmos como SVM. Es importante tener en cuenta que una función [matemática] K (x_ {i}, x_ {j}) [/ matemática] también es una función del núcleo, incluso si no es positiva, semi-definida y simétrica, solo que no puede ser utilizado en algoritmos que requieren estas condiciones. Existen algoritmos que pueden hacer uso de tales núcleos, por ejemplo, ver Aprendizaje con núcleos no positivos, aunque estos métodos son relativamente menos comunes.

Encontré esto en Reddit: explique Support Vector Machines (SVM) como si tuviera 5 años. • / r / MachineLearning

Simplemente la mejor explicación de SVM que he encontrado.
———————————————————————————————-

Tenemos 2 colores de bolas en la mesa que queremos separar.

Tomamos un palo y lo ponemos sobre la mesa, esto funciona bastante bien, ¿verdad?

Viene un villano y coloca más bolas en la mesa, funciona, pero una de las bolas está en el lado equivocado y probablemente haya un lugar mejor para poner el palo ahora.

Los SVM intentan colocar el palo en el mejor lugar posible al tener un espacio lo más grande posible a cada lado del palo.

Ahora, cuando el villano regresa, el palo todavía está en un lugar bastante bueno.

Hay otro truco en la caja de herramientas SVM que es aún más importante. Digamos que el villano ha visto lo bueno que eres con un palo, por lo que te da un nuevo desafío.

No hay palo en el mundo que te permita dividir bien esas bolas, entonces, ¿qué haces? ¡Volteaste la mesa, por supuesto! Lanzando las bolas al aire. Luego, con tus habilidades de ninja profesional, tomas una hoja de papel y la deslizas entre las bolas.

Ahora, mirando las bolas desde donde está parado el villano, las bolas se verán divididas por una línea curva.
Adultos aburridos, los datos de las bolas de llamadas, el palo de un clasificador, la optimización de trucos de brecha más grande, la vuelta de la tabla al kernel y el trozo de papel un hiperplano.
———————————————————————————————–

Ahora mira esto:

——————————————————————————————–
Otro punto que me gusta mencionar sobre el SVM (no relacionado con esta pregunta) es cómo se define mediante los ejemplos de casos límite. (tomado del curso CS109: Explicación SVM)

Suponga que desea separar las manzanas de las naranjas usando SVM. El cuadrado rojo son manzanas y los círculos azules son naranjas.

Ahora vea los vectores de soporte (Los puntos rellenos) que definen el margen aquí.

Intuitivamente, el círculo azul lleno es una naranja que se parece mucho a una manzana. Mientras que los cuadrados rojos rellenos son manzanas que se parecen mucho a las naranjas.

Piensa por esto en otro momento. Si desea que su hijo aprenda a diferenciar entre una manzana y una naranja, le mostraría una manzana perfecta y una naranja perfecta. Pero no los SVM, solo quieren ver una manzana que se parece a una naranja y viceversa. Este enfoque es muy diferente de cómo funcionan la mayoría de los algoritmos de aprendizaje automático, y tal vez por eso funciona tan bien en algunos casos.

Intuitivamente, un núcleo es solo una transformación de sus datos de entrada que le permite (o un algoritmo como SVM) tratarlo / procesarlo más fácilmente. Imagine que tenemos el problema del juguete de separar los círculos rojos de las cruces azules en un plano como se muestra a continuación.

Nuestra superficie de separación sería la elipse dibujada en la figura izquierda. Sin embargo, la transformación de nuestros datos en un espacio tridimensional a través del mapeo que se muestra en la figura facilitaría mucho el problema ya que, ahora, nuestros puntos están separados por un plano simple. Esta incrustación en una dimensión superior se llama truco del núcleo.

En conclusión, y de manera muy informal, un núcleo consiste en incrustar puntos generales en un espacio interno del producto.

PD: He tomado este gráfico de http://www.sussex.ac.uk/Users/ch …, que también se muestra en Hastie y Tibshirani: Elementos de aprendizaje estadístico.

Aquí hay una visualización aún más corta de lo que hace un SVM. Básicamente, el truco es buscar una proyección en un espacio dimensional superior donde haya una separación lineal de los datos (otros han publicado respuestas mucho más detalladas y correctas, así que solo quería compartir el video, no hecho por mí).

Para agregar a las otras respuestas, un kernel RBF, quizás el kernel más utilizado, actúa esencialmente como un filtro de paso de banda baja que prefiere modelos más suaves. Para una justificación matemática completa de este hecho, consulte la explicación de Charles Martin.

No es posible encontrar un hiperplano o un límite de decisión lineal para algunos problemas de clasificación. Si proyectamos los datos en una dimensión superior desde el espacio original, podemos obtener un hiperplano en la dimensión proyectada que ayuda a clasificar los datos.

Como mostramos en la figura anterior, es imposible encontrar una sola línea para separar las dos clases (verde y azul) en el espacio de entrada. Pero, después de proyectar los datos en una dimensión superior (es decir, el espacio de características en la figura), pudimos encontrar el hiperplano que clasifica los datos. Kernel ayuda a encontrar un hiperplano en el espacio dimensional superior sin aumentar mucho el costo computacional. Por lo general, el costo computacional aumentará si aumenta la dimensión de los datos.

¿Cómo es que Kernel no aumenta la complejidad computacional?

Sabíamos que el producto escalar de los mismos dos vectores dimensionales da un solo número. Kernel utiliza esta propiedad para calcular el producto punto en un espacio diferente sin siquiera visitar el espacio.

Supongamos que tenemos dos características. Significa que la dimensión del punto de datos es [math] \ mathbb R ^ 2. [/mates]

[matemáticas] x_ {i} = \ begin {bmatrix} x_ {i1} \\ x_ {i2} \ end {bmatrix} \ tag * {} [/ math]

i en el subíndice x representa los puntos de datos. Del mismo modo, 1 y 2 en el subíndice x denotan las características. Además, suponga que estamos aplicando alguna función de transformación para convertir el espacio de entrada bidimensional (dos características) en un espacio de característica cuatridimensional que es [matemáticas] (x_ {i1} ^ {2}, x_ {i1} x_ {i2} x_ {i2} x_ {i1}, x_ {i2} ^ {2}). [/ math] Requiere [math] \ mathcal {O} (n ^ {2}) [/ math] tiempo para calcular n puntos de datos en el espacio de cuatro dimensiones. Para calcular el producto escalar de dos vectores en el espacio de cuatro dimensiones / espacio transformado, la forma estándar es

1. Convierta cada punto de datos de [math] \ mathbb R ^ 2 \ a \ mathbb R ^ 4 [/ math] aplicando la transformación. (He tomado dos puntos de datos [matemáticas] x_ {i} [/ matemáticas] y [matemáticas] x_ {j} [/ matemáticas])

[matemáticas] \ phi (x_ {i}) = \ begin {bmatrix} x_ {i1} ^ {2} \\ x_ {i1} x_ {i2} \\ x_ {i2} x_ {i1} \\ x_ {i2 } ^ {2} \ end {bmatrix} \ hspace {2cm} \ phi (x_ {j}) = \ begin {bmatrix} x_ {j1} ^ {2} \\ x_ {j1} x_ {j2} \\ x_ {j2} x_ {j1} \\ x_ {j2} ^ {2} \ end {bmatrix} \ tag * {} [/ math]

2. Producto de puntos los dos vectores.

[matemáticas] \ phi (x_ {i}). \ phi (x_ {j}) \ tag * {} [/ matemáticas]

Como dije antes, la función Kernel calcula el producto punto en el espacio diferente sin siquiera visitarlo. La función del núcleo para la transformación anterior es

[matemáticas] K (x_ {i}, x_ {j}) = (x_ {i} ^ {T} x_ {j}) ^ {2} \ tag {1} [/ matemáticas]

Ejemplo:

Digamos que [matemáticas] x_ {i} = \ begin {bmatrix} 1 \\ 2 \ end {bmatrix} \ hspace {0.5cm} \ text {and} \ hspace {0.5cm} x_ {j} = \ begin {bmatrix } 3 \\ 5 \ end {bmatrix}. [/ Math]

El producto de punto en el espacio de cuatro dimensiones por la forma estándar es

[matemáticas] = \ begin {bmatrix} 1 \\ 2 \\ 2 \\ 4 \ end {bmatrix} \ cdot \ begin {bmatrix} 9 \\ 15 \\ 15 \\ 25 \ end {bmatrix} = 9 + 30 + 30 + 100 = 169 \ etiqueta * {} [/ matemáticas]

El producto de punto anterior se puede calcular utilizando la función del núcleo anterior (ecuación 1) sin siquiera transformar el espacio original.

[matemáticas] K (x_ {i}, x_ {j}) = \ begin {bmatrix} 1 \\ 2 \ end {bmatrix} \ cdot \ begin {bmatrix} 3 \\ 5 \ end {bmatrix} = (3+ 10) ^ {2} = 169. [/ Matemáticas]

El método estándar para calcular el producto punto requiere tiempo [matemático] \ matemático {O} (n ^ {2}) [/ matemático]. Pero, el núcleo requiere solo [math] \ mathcal {O} (n) [/ math] time.

Kernel también puede considerarse como una medida de similitud. La medida de similitud cuantifica la similitud entre dos puntos de datos. El valor del kernel será grande si [math] \ phi (x_ {i}) [/ math] y [math] \ phi (x_ {j}) [/ math] están muy juntos. Será cero, si son ortogonales entre sí. Kernel no se puede aplicar a todos los algoritmos de aprendizaje automático. Se aplicará solo si el algoritmo solo necesita conocer el producto interno de los puntos de datos en el espacio de coordenadas. La forma dual de la función objetivo de SVM y sus restricciones se dan a continuación.

[matemáticas] L_ {D} = \ sum_ {i = 1} ^ {N} \ alpha_ {i} – \ frac {1} {2} \ sum_ {i = 1} ^ {N} \ sum_ {j = 1 } ^ {N} \ alpha_ {i} \ alpha_ {k} y_ {i} y_ {k} \ underset {\ text {Producto interno}} {(x_ {i} ^ {T} x_ {j})} \ etiqueta {2} [/ math]

[matemáticas] st: \ alpha_ {i} \ geq 0 \ tag * {} [/ matemáticas]

[matemáticas] \ hspace {0.5cm} \ sum_ {i = 1} ^ {N} \ alpha_ {i} \ y_ {i} = 0 \ tag * {} [/ matemáticas]

Solo requiere el producto interno de los puntos de datos en el espacio de coordenadas para determinar el hiperplano de separación. Entonces, podemos reemplazar eso por kernel.

[matemáticas] L_ {D} = \ sum_ {i = 1} ^ {N} \ alpha_ {i} – \ frac {1} {2} \ sum_ {i = 1} ^ {N} \ sum_ {j = 1 } ^ {N} \ alpha_ {i} \ alpha_ {k} y_ {i} y_ {k} K (x_ {i} ^ {T} x_ {j}) \ tag * {} [/ math]

SVM en su configuración general funciona al encontrar un hiperplano “óptimo” que separa dos nubes de datos de puntos. Pero esto está limitado en el sentido de que solo funciona cuando las dos nubes de puntos (cada una correspondiente a una clase) pueden estar separadas por un hiperplano. ¿Qué pasa si el límite de separación no es lineal?

Esta es una imagen que encontré en la web. Este es un ejemplo perfecto de la limitación de SVM en su configuración general. SVM aprenderá la línea de color rojo de los puntos de datos que podemos ver claramente que no es óptima. El límite óptimo es la curva verde, que es una estructura no lineal.

Para superar esta limitación, utilizamos el concepto de núcleos. Dado un punto de prueba, los núcleos se ajustarán a una curva en los puntos de datos, específicamente a los puntos que están ‘cerca’ del conjunto de prueba. Entonces, si usa un núcleo RBF, se ajustará a una distribución gaussiana sobre los puntos ‘cercanos’ del punto de prueba. La cercanía se define usando std. distancia métrica

Supongamos que esta es la función que estamos tratando de aproximar. La región amarilla es el gaussiano que se ajusta sobre los puntos de entrenamiento que están cerrados al punto de prueba (suponga que está uno en el centro del gaussiano). Por lo tanto, se aproxima a la función (separación de límites) mediante el uso de gaussianos por partes (para el núcleo RBF). Y utiliza solo un conjunto disperso de datos de entrenamiento (vectores de soporte) para hacerlo.

Esta es la intuición de usar núcleos en SVM. Por supuesto, existen buenos argumentos teóricos para usar núcleos como la proyección de puntos de datos en el espacio de dimensión infinita donde se vuelve linealmente separable, pero esta es la intuición que tengo para usar núcleos. HTH

Sé que pegar un enlace a una charla externa no sería una respuesta adecuada aquí, pero esta charla es tan increíble y responde a su pregunta de manera tan intuitiva que le animo a que la vea.

http://www.google.co.in/url?sa=t …

La intención del Truco Kernel: permitirnos representar un conjunto infinito de funciones discretas con una familia de funciones continuas. Y en muchos casos en el aprendizaje automático, podemos expresar nuestros productos punto con una función analítica simple, con algunos parámetros ajustables.

Por favor, vea las publicaciones de mi blog para más detalles

Kernels Parte 1: ¿Qué es un Kernel RBF? De Verdad?

Granos Parte 2: Gravedad Cuántica Afina

Granos y gravedad cuántica Parte 3: Estados coherentes

La analogía del equilibrio de una configuración de masa de resorte es otra forma de entenderla, que se logra cuando la configuración tiene la energía potencial mínima.
// Advertencia: baja matemática, alcance limitado.
Podemos comparar:
Modelo de aprendizaje de la línea horizontal en la figura, que contiene el punto de datos [math] y_0 [/ math] consultado.
Los puntos de datos [math] y_i [/ ​​math] son ​​como partículas ponderadas.
La similitud de los puntos de datos con el punto de consulta es comparable a la longitud del resorte
y las constantes de resorte [math] k_i [/ ​​math] a las funciones de Kernel, agregando ponderaciones a los puntos de datos correspondientes a su similitud con la consultada.
Energía potencial [matemática] U = \ frac {1} {2} \ Sigma k_i (y_i-y_o) ^ 2 [/ matemática] a Error al predecir los puntos de datos similares a los consultados desde el modelo de aprendizaje.
y equilibrio al estado cuando este error es mínimo.

Todos los resortes son idénticos hasta que las funciones del kernel no son de usuario para pesar los datos correspondientes a su similitud.

Una vez usados, los resortes ya no son iguales.

A veces, ningún valor de los parámetros de un modelo global [ no lineal ] puede proporcionar una buena aproximación de la función verdadera. Hay dos enfoques para este problema.
Primero, podríamos usar un modelo global más grande y complejo y esperar
que puede aproximar los datos lo suficiente.
El segundo enfoque es ajustar el modelo simple a parches locales en lugar de toda la región de interés.
En el segundo enfoque
Ahora, el error en la predicción se comporta de manera similar a que las estrías de placas delgadas minimizan la energía de flexión de una placa y la energía de las restricciones que tiran de la placa, en un modelo local plano [la línea en la figura] ahora puede rotar y traducirse. Los resortes se ven obligados a permanecer orientados verticalmente, en lugar de moverse a la distancia más pequeña entre los puntos de datos y la línea.
El ajuste (la línea en equilibrio) producido por resortes igualmente fuertes a un conjunto de puntos de datos (los puntos negros), minimizando el criterio, se ve como sigue

A medida que los núcleos se ponen en acción, los muelles más cercanos al punto de consulta se fortalecen y los muelles más alejados se debilitan. Las fuerzas de los resortes están dadas por K (d (xi, q)), y el ajuste minimiza el criterio .. & [equilibrio] se ve como sigue
http://www.qou.edu/arabic/resear …

Las SVM dependen de dos ideas: dimensión de VC y optimización. Dados los puntos en el plano y el hecho de que son separables (respuesta de Nikhil), hay líneas infinitas (medios planos en 2D) que los separarían. El SVM encuentra el mejor resolviendo un problema de optimización en aquellos que separan medios planos. Lo bueno es que es un problema de programación lineal que es rápido y fácil de resolver.

La dimensión VC está relacionada con un hecho que damos por sentado: ¿son separables los puntos de entrenamiento? Bueno, cuando se trata de puntos en 2D, el número máximo de puntos que se garantiza que son separables son 3, que es precisamente la dimensión VC. Tenga en cuenta que el diagrama en la respuesta de Nikhil proyecta los tres puntos en una línea a 2D, y dibujó un clasificador que funciona. La dimensión VC depende de los clasificadores (hiperplanos en el caso de SVM) y la dimensión en la que se encuentran los datos (2D en este caso). Ahora, si los puntos están en n dimensiones, la dimensión VC es n + 1. Entonces, en cambio, si tenemos m puntos, necesitamos que los puntos se encuentren en un espacio de dimensión al menos (m-1). Cuando esto sucede, estamos seguros de encontrar una solución a la optimización que realizamos. Aquí es donde entra el núcleo. Proyectamos los puntos m que se encuentran en la dimensión n, n <(m-1), en un espacio dimensional (m-1) para garantizar que encontremos un clasificador lineal en esa dimensión.

Para hacerlo concreto, como en el ejemplo de Nikhil, teníamos tres puntos en 1 dimensión. No solucionable Entonces lo proyectamos en un espacio de al menos (3-1) = 2 dimensiones, y encontraremos una solución.

Editar:
Como señala Yan King Yin, tres puntos en un plano no pueden separarse si son colineales. La dimensión VC excluye estos casos (medir conjuntos de cero), de lo contrario los medios planos no podrían separar nada.

Edición 2:

Dado que la gente todavía está mirando esta respuesta, y la parte de Kernels está oculta en un comentario, la incluyo en la respuesta:

Tenemos un conjunto de puntos de datos que no se pueden separar linealmente (relacionado con la dimensión VC de los semiplanos). Usar un clasificador no lineal para separarlos es doloroso.

El algoritmo lineal SVM realmente solo necesita tomar el producto interno de los puntos que está tratando de clasificar. Esto se debe a que los semiplanos se pueden determinar utilizando productos internos, y las SVM buscan semiplanos.

Por lo tanto, queremos hacer dos cosas: queremos mapear todos los puntos de datos del espacio en el que entran en un espacio de producto interno útil, que generalmente será de mayor dimensión (la utilidad está relacionada con la separabilidad relacionada con la dimensión VC). Luego, queremos usar un SVM lineal para clasificar los puntos en este espacio usando un semiplano único. Esto significa que queremos tomar productos internos de los puntos de datos transformados.

Una función del núcleo hace precisamente esto, pero en un solo paso. No se molesta en encontrar los puntos transformados, ya que ya sabe cuál será su producto de puntos gracias a la función del núcleo.

Este es el truco del núcleo: utilice una función del núcleo para convertir una clasificación no lineal en lineal (si es posible).

Primero, ahorras una ENORME cantidad de tiempo porque este es un programa lineal y no una optimización no lineal porque los puntos son extraños.
En segundo lugar, ahorra tiempo y espacio al no asignar los puntos en el espacio transformado, sino al pasar directamente de dos puntos en el espacio original al producto escalar en el espacio dimensional superior.

La clasificación lineal realizada en realidad se convierte en una clasificación no lineal en el espacio original.

1. Para un conjunto de datos con n características (~ n-dimensional), los SVM encuentran un hiperplano n-1 dimensional para separarlo (digamos para la clasificación)
2. Por lo tanto, los SVM funcionan muy mal con conjuntos de datos que no son separables linealmente
3. Pero, con bastante frecuencia, es posible transformar nuestro conjunto de datos no separable linealmente en un conjunto de datos de dimensiones superiores donde se vuelve separable linealmente, para que los SVM puedan hacer un buen trabajo
4. Desafortunadamente, con bastante frecuencia, el número de dimensiones que tiene que agregar (mediante transformaciones) depende del número de dimensiones que ya tiene (y no linealmente 🙁)

1. Para conjuntos de datos con muchas características, resulta casi imposible probar todas las transformaciones interesantes

1. Afortunadamente, lo único que los SVM deben hacer en el espacio de características (de mayor dimensión) (durante el entrenamiento) es calcular los productos de punto por pares
2. Para un par dado de vectores (en un espacio de características de dimensiones más bajas) y una transformación en un espacio de dimensiones más altas, existe una función (La Función Kernel) que puede calcular el producto escalar en el espacio de dimensiones más altas sin transformar explícitamente el vectores en el espacio de dimensiones superiores primero
3. ¡Somos salvos!

Otra pregunta famosa que he encontrado y que está relacionada con el tema es la complejidad computacional para las predicciones que usan SVM con y sin el truco del núcleo.

Digamos que el espacio de características original tiene | X | caracteristicas. El nuevo espacio de características tiene | F | dimensiones. Una función del núcleo tarda k tiempo en evaluarse. Además hay m ejemplos de entrenamiento y | S | vectores de soporte

Sin usar el truco del kernel: el tiempo necesario sería O (| F |).

Explicación: Para un ejemplo de prueba, tendríamos que calcular realmente el término signo (w0 + w * x), lo que llevaría tiempo O (| F |).

Con el truco del núcleo: el tiempo necesario sería O (k * | S |)

Explicación: Simplemente calcularíamos el producto de punto del ejemplo de prueba con el de los vectores de soporte. El número de vectores de soporte multiplicado por el tiempo necesario para ejecutar la función del núcleo una vez sería la complejidad computacional.

Corrige mi respuesta si me equivoco aquí.

Esta es una de las explicaciones más sencillas del truco SVM y Kernel.