Las otras respuestas son buenas, pero siento que hablan más sobre por qué el Truco del Kernel es genial. Aquí hablaré sobre lo que es y llegaré a los detalles más pequeños para ayudarlo a comprender mejor el concepto subyacente. Comenzaré con el ejemplo más común y luego expandiré al caso general. Esta respuesta debería aclarar todas las razones por las cuales el truco de Kernel funciona, incluyendo ¿qué significa trabajar en una dimensión infinita?
Figura 1: Ejemplo de datos etiquetados inseparables en 2-Dimension es separable en 3-Dimension. Fuente: [ 4 ]
En el ejemplo anterior, los datos originales están en 2 dimensiones. Supongamos que lo denotamos como, [math] \ mathbf {x} = \ {x_1, x_2 \} [/ math]. Podemos ver en la Fig. [Math] ~ [/ math] 1 (izquierda) que [math] \ mathbf {x} [/ math] es inseparable en su espacio. Pero son separables en este espacio transformado (ver Fig. [Matemáticas] ~ [/ matemáticas] 1, derecha),
[matemáticas] \ Phi (\ mathbf {x}) \ rightarrow {x_1 ^ 2, x_2 ^ 2, \ sqrt {2} x_1x_2} [/ math]
donde, [math] \ Phi [/ math] es una función de transformación de 2-D a 3-D aplicada en [math] \ mathbf {x} [/ math]. Estos puntos se pueden separar con la transformación [math] \ Phi (\ mathbf {x}) \ rightarrow {x_1 ^ 2, x_2 ^ 2} [/ math] también, pero el anterior ayudará a explicar el uso de una dimensión superior espacio. El [math] \ sqrt {2} [/ math] no es necesario pero hará que nuestras explicaciones adicionales sean matemáticamente convenientes .
Ahora podemos tener un límite de decisión en este espacio tridimensional de [matemáticas] \ Phi [/ matemáticas] que se verá así,
[matemáticas] \ beta_0 + \ beta_1x_1 ^ 2 + \ beta_2x_2 ^ 2 + \ beta_3 \ sqrt {2} x_1x_2 = 0 ~~~~ (2) [/ matemáticas]
Si estuviéramos haciendo una regresión logística, nuestro modelo se vería así: Ecuación [matemática] ~ 2 [/ matemática]. En SVM, se puede encontrar un límite de decisión similar (un clasificador) utilizando el Truco del kernel en su función objetivo. En resumen, para eso necesitamos encontrar los productos de punto de [math] \ langle \ Phi (\ mathbf {x} _ {i}), \ Phi (\ mathbf {x} _ {j}) \ rangle [/ math ] (ver Ec. 13 en [6]). (Tenga en cuenta que el producto punto también es una medida de similitud). Hagamos eso. Lo haré así
Mi manera:
[matemáticas] \ langle \ Phi (\ mathbf {x} _ {i}), \ Phi (\ mathbf {x} _ {j}) \ rangle \\ [/ math]
[matemáticas] = \ langle \ {x_ {i1} ^ {2}, x_ {i2} ^ {2}, \ sqrt {2} x_ {i1} x_ {i2} \}, \ {x_ {j1} ^ { 2}, x_ {j2} ^ {2}, \ sqrt {2} x_ {j1} x_ {j2} \} \ rangle ~~~~ (3.1) \\ [/ math]
[matemáticas] = x_ {i1} ^ {2} x_ {j1} ^ {2} + x_ {i2} ^ {2} x_ {j2} ^ {2} + 2x_ {i1} x_ {i2} x_ {j1} x_ {j2} ~ (3.2) [/ matemáticas]
En cambio, mi amigo Sam, que es más inteligente, hizo lo siguiente:
La manera de Sam:
[matemáticas] \ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle ^ {2} \\ [/ math]
[matemáticas] = \ langle \ {x_ {i1}, x_ {i2} \}, \ {x_ {j1}, x_ {j2} \} \ rangle ^ {2} ~~~~ \\ [/ math]
[matemáticas] = (x_ {i1} x_ {j1} + x_ {i2} x_ {j2}) ^ {2} ~~~~ (4.1) \\ [/ matemáticas]
[matemáticas] = x_ {i1} ^ {2} x_ {j1} ^ {2} + x_ {i2} ^ {2} x_ {j2} ^ {2} + 2x_ {i1} x_ {i2} x_ {j1} x_ {j2} ~ (4.2) [/ matemáticas]
¿Qué es diferente?
Operaciones de computación:
- Mi manera : para llegar a la ecuación [math] ~ [/ math] 3.1, realizamos [math] 3 \ times2 [/ math] cálculos para transformar cada una de [math] \ mathbf {x} _i [/ math] y [ math] \ mathbf {x} _j [/ math] en el espacio tridimensional de [math] \ Phi [/ math]. Después de eso, realizamos un producto de punto entre [math] \ Phi (\ mathbf {x} _i) [/ math] y [math] \ Phi (\ mathbf {x} _j) [/ math] que tiene [math] 3 [ / math] operaciones adicionales (en la ecuación [math] ~ [/ math] 3.2). Total: 9 operaciones.
- La manera de Sam : Hasta la ecuación [matemáticas] ~ [/ matemáticas] 4.1, Sam realizó 2 operaciones de computación. Finalmente, en la ecuación [matemáticas] ~ [/ matemáticas] 4.2, hizo un cálculo más. Total: 3 operaciones. Tenga en cuenta que en la ecuación [math] ~ [/ math] 4.1 estamos cuadrando un escalar, por lo tanto, solo una operación.
Espacio de cómputo:
- A mi manera : apliqué la función de transformación de mapeo [math] \ Phi [/ math] en mis datos [math] \ mathbf {x} [/ math] ‘s. Y luego realicé mis operaciones en el espacio [math] \ Phi [/ math] (un espacio 3-D).
- La manera de Sam: Sam no aplicó la función de transformación. Se quedó en el espacio 2-D original y llegó al mismo resultado que obtuve de los cálculos en un espacio 3-D.
Sam es definitivamente más listo que yo. Lo que hizo resultó ser el truco de Kernel. Pero no te dejaré aquí. Vamos a guisar más con más ejemplos.
Supongamos que quisiera una expresión más grande para mi límite de decisión que la de la ecuación [math] ~ [/ math] 2 (porque espero que funcione mejor), que tiene términos de primer y segundo orden como,
[matemáticas] \ beta_0 + \ beta_1x_1 + \ beta_2x_2 + \ beta_3x_1 ^ 2 + \ beta_4x_2 ^ 2 + \ beta_5 \ sqrt {2} x_1x_2 = 0 ~~~~ (5) [/ matemáticas]
Veamos mi camino y el de Sam otra vez,
Mi manera:
Definir, [matemáticas] \ Phi (\ mathbf {x}) \ rightarrow {1, \ sqrt {2} x_1, \ sqrt {2} x_2, x_1 ^ 2, x_2 ^ 2, \ sqrt {2} x_1x_2} [/ mates].
[matemáticas] \ langle \ Phi (\ mathbf {x} _ {i}), \ Phi (\ mathbf {x} _ {j}) \ rangle \\ [/ math]
[matemáticas] = \ langle \ {1, \ sqrt {2} x_ {i1}, \ sqrt {2} x_ {i2}, x_ {i1} ^ 2, x_ {i2} ^ 2, \ sqrt {2} x_ {i1} x_ {i2} \}, \ {1, \ sqrt {2} x_ {j1}, \ sqrt {2} x_ {j2}, x_ {j1} ^ 2, x_ {j2} ^ 2, \ sqrt {2} x_ {j1} x_ {j2} \} \ rangle ~~ (6.1) [/ math]
[matemáticas] = 1 + 2x_ {i1} x_ {j1} + 2x_ {i2} x_ {j2} + x_ {i1} ^ 2x_ {j1} ^ 2 + x_ {i2} ^ 2x_ {j2} ^ 2 + 2x_ { i1} x_ {i2} x_ {j1} x_ {j2} ~ (6.2) [/ matemáticas]
La manera de Sam:
[matemáticas] (1 + \ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle) ^ {2} \\ [/ matemáticas]
[matemáticas] = (1 + x_ {i1} x_ {j1} + x_ {i2} x_ {j2}) ^ 2 ~~ (7.1) \\ [/ matemáticas]
[matemáticas] = 1 + 2x_ {i1} x_ {j1} + 2x_ {i2} x_ {j2} + x_ {i1} ^ 2x_ {j1} ^ 2 + x_ {i2} ^ 2x_ {j2} ^ 2 + 2x_ { i1} x_ {i2} x_ {j1} x_ {j2} ~ (7.2) [/ matemáticas]
Comparando mi camino y el de Sam otra vez:
- Tuve que definir explícitamente [matemáticas] \ Phi [/ matemáticas]. Si bien se podría argumentar que Sam también tenía que saber explícitamente agregar un [math] 1 [/ math] al producto punto de [math] \ mathbf {x} _ {i}, \ mathbf {x} _ {j} [/ matemáticas], pero como veremos pronto, el enfoque de Sam puede generalizarse fácilmente.
- Mi camino tomó 16 operaciones, el camino de Sam solo tomó 3 operaciones. (Nuevamente, tenga en cuenta que en la ecuación [matemáticas] ~ 7 [/ matemáticas] .1 estamos cuadrando un escalar, por lo tanto, solo una operación).
- Sam nuevamente no dejó el espacio 2-D original para encontrar la misma medida de similitud que encontré en el espacio 5-D.
Del mismo modo, podemos seguir yendo a dimensiones más altas. Si fuera para Sam, puede encontrar fácilmente la medida de similitud que tiene términos de tercer orden en un espacio 9-D al,
La manera de Sam:
[matemáticas] \ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle ^ {3} \\ [/ math]
[matemáticas] = (x_ {i1} x_ {j1} + x_ {i2} x_ {j2}) ^ {3} ~~~~ (8.1) \\ [/ matemáticas]
[matemáticas] = 1 + 3x_ {i1} x_ {j1} + 3x_ {i2} x_ {j2} + 3x_ {i1} ^ 2x_ {j1} ^ 2 + 3x_ {i2} ^ 2x_ {j2} ^ 2 + x_ { i1} ^ 3x_ {j1} ^ 3 + x_ {i2} ^ 3x_ {j2} ^ 3 + 3x_ {i1} ^ 2x_ {j1} ^ 2x_ {i2} x_ {j2} + 3x_ {i1} x_ {j1} x_ {i2} ^ 2x_ {j2} ^ 2 + 6x_ {i1} x_ {j1} x_ {i2} x_ {j2} ~ (8.2) [/ matemáticas]
En este punto, ni siquiera me molestaré en seguir mi camino. Espero que entiendas por qué el camino de Sam es claramente mejor que el mío. Simplemente está calculando el producto punto en el espacio original y elevando el resultado (un escalar) a una potencia. Y esta es exactamente la medida de similitud en un espacio dimensional superior.
Este es precisamente el truco de Kernel. Ahora hagamos coincidir los términos y afirmaciones del truco Kernel definido anteriormente con el método de Sam.
- Kernel: en los ejemplos anteriores, las funciones de Kernel utilizadas por Sam son,
- [matemáticas] K (\ mathbf {x} _i, \ mathbf {x} _ {j}) = \ langle \ mathbf {x} _i, \ mathbf {x} _ {j} \ rangle ^ 2 [/ math]
- [matemáticas] K (\ mathbf {x} _i, \ mathbf {x} _ {j}) = (1+ \ langle \ mathbf {x} _i, \ mathbf {x} _ {j} \ rangle) ^ 2 [ /mates]
- [matemáticas] K (\ mathbf {x} _i, \ mathbf {x} _ {j}) = \ langle \ mathbf {x} _i, \ mathbf {x} _ {j} \ rangle ^ 3 [/ math]
Función de mapeo: Sam no necesitaba conocer una función de mapeo de 3, 5 o 9 dimensiones, [matemática] \ Phi [/ matemática], para obtener la medida de similitud en estas dimensiones altas.
Resumen mágico : todo lo que Sam necesita hacer es darse cuenta de que hay un espacio dimensional más alto que puede separar los datos. ¡Elija un Kernel correspondiente y listo! Ahora está trabajando en la alta dimensión mientras realiza el cálculo en el espacio original de baja dimensión. Y aún está separando los datos inseparables anteriores. Los ejemplos de kernel que Sam ha usado hasta ahora son casos especiales de un kernel lineal, [math] K (\ mathbf {x} _i, \ mathbf {x} _j) = (a \ langle \ mathbf {x} _i, \ mathbf {x x } _j \ rangle + b) ^ n [/ math].
¿Cómo funciona el truco de Kernel en dimensión infinita?
Bueno, este no es el final. Recuerde que me dijeron que Kernels puede encontrar las similitudes en espacios de dimensiones infinitas (y, por supuesto, no hacer cálculos en el espacio infinito). Si todavía estás conmigo hasta ahora, prepárate para este loco.
Aquí está el truco detrás de esta magia. Mostraré el truco con un Kernel gaussiano (también llamado Función de base radial, RBF), y la misma lógica puede extenderse a otros Kernels de dimensiones infinitas, como Exponencial, Laplace, etc.
Un núcleo gaussiano se define como,
[matemáticas] K (\ mathbf {x} _i, \ mathbf {x} _j) = \ exp {\ left (- \ cfrac {|| \ mathbf {x} _i- \ mathbf {x} _j || ^ 2} {2 \ sigma ^ 2} \ right)} ~~~~ (9) [/ math]
Por simplicidad, suponga [math] \ sigma = 1 [/ math]. El núcleo gaussiano en la ecuación [math] ~ [/ math] 9 puede entonces expandirse como,
[matemáticas] \ exp {\ left (- \ cfrac {|| \ mathbf {x} _i- \ mathbf {x} _j || ^ 2} {2} \ right)} = C \ Big \ {1- \ underbrace {\ cfrac {\ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle} {1!}} _ {1er orden} + \ underbrace {\ cfrac {\ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle ^ {2}} {2!}} _ {2do orden} – \ underbrace {\ cfrac {\ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle ^ {3}} {3!}} _ {3er orden} + \ ldots \ Big \} [/ math]
donde, [matemáticas] C = \ exp {\ left (- \ cfrac {1} {2} || \ mathbf {x} _i || ^ 2 \ right)} \ exp {\ left (- \ cfrac {1} {2} || \ mathbf {x} _j || ^ 2 \ right)} [/ math]
Según el cálculo de Sam, ahora sabemos que [math] \ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle ^ n [/ math] producirá [math] n [/ math ] -terminos de pedido. Como el gaussiano tiene una expansión de series infinitas, obtenemos términos de todos los pedidos hasta el infinito. Y, por lo tanto, un núcleo gaussiano nos permite encontrar similitudes en una dimensión infinita. También en este caso, todo el cálculo que tenemos que hacer es encontrar la distancia euclidiana al cuadrado entre [math] \ mathbf {x} _i [/ math] y [math] \ mathbf {x} _j [/ math], y encontrar su exponencial (los cálculos ocurren en el espacio original).
¿Entonces Sam no tiene nada de qué preocuparse mientras usa Kernels?
Lo hace. Al final, él necesita
- elegir cuál de las funciones de Kernel usar. [1] tiene una lista exhaustiva de Kernels para elegir. Y,
- sintonice los hiperparámetros de un núcleo. Por ejemplo, en Gaussian Kernel necesitamos ajustar [math] \ sigma [/ math]. [5] tiene una lista de documentos que hablan de esto.
Versión completa: The Kernel Trick por Chitta Ranjan en Data Science for Mortals
En esta publicación, traté de explicar los detalles elementales del truco del kernel. Mi objetivo es que entiendas el truco del kernel. Por favor, deje un comentario si no entendió una parte o nada de eso.
Actualizar:
¿Necesitamos conocer primero la función Kernel apropiada? (gracias, Sean Cascketta)
Sí, necesitamos determinar qué función de Kernel será apropiada. Sin embargo, no necesitamos saberlo primero. Primero, tenemos que darnos cuenta de que un límite de decisión lineal no va a funcionar. Esto se logra cuando se ve una precisión deficiente del modelo, y se puede utilizar cierta visualización de datos (por ejemplo, la Figura 1), si es posible. Al darnos cuenta de que el límite lineal no va a funcionar, vamos por un truco de Kernel. Todos los núcleos conducirán a un límite de decisión no lineal, y posiblemente mejor. [1] da una lista exhaustiva de opciones. Pero no hay una forma directa de saber qué función de Kernel será la mejor opción. Los métodos de optimización del modelo de aprendizaje automático convencional, como la validación cruzada, se pueden utilizar para encontrar la función del núcleo que funcione mejor. Sin embargo, dado que con el truco Kernel no hay un cálculo adicional para separar los puntos de datos en alguna dimensión alta o infinita, las personas simplemente van con la dimensión infinita usando el Kernel Gaussiano (RBF). RBF es el kernel más utilizado. Tiene un hiperparámetro de ajuste [math] \ sigma [/ math] que está sintonizado para elegir entre un límite suave o con curvas. En resumen, como regla general, una vez que se dé cuenta de que el límite lineal no va a funcionar, pruebe con un límite no lineal con un núcleo RBF.
Referencias
[1] Funciones del núcleo para aplicaciones de aprendizaje automático
[2] ¿Alguien puede explicar Kernel Trick intuitivamente?
[3] El truco del grano
[4] Berkeley CS281B Lecture: The Kernel Trick
[5] Máquinas de vectores de soporte: parámetros
[6] Máquinas de vectores de soporte: Conferencia (Stanford CS 229)
