Método Kernel

En el aprendizaje automático, las máquinas kernel son una clase de algoritmos para el análisis de patrones, cuyo miembro más conocido es la máquina de vectores de soporte (SVM). Estos métodos implican el uso de clasificadores lineales para resolver problemas no lineales.^[1] La tarea general del análisis de patrones es encontrar y estudiar tipos generales de relaciones (por ejemplo, conglomerados, clasificaciones, componentes principales, correlaciones, clasificaciones) en conjuntos de datos. Para muchos algoritmos que resuelven estas tareas, los datos en representación bruta tienen que transformarse explícitamente en representaciones de vectores de características mediante un mapa de características especificado por el usuario: en cambio, los métodos kernel sólo requieren un kernel especificado por el usuario, es decir, una función de similitud sobre todos los pares de puntos de datos calculada mediante productos internos. El mapa de características de las máquinas kernel es de dimensión infinita, pero sólo requiere una matriz de dimensión finita a partir de la entrada del usuario, de acuerdo con el teorema del Representante. Las máquinas kernel son lentas de calcular para conjuntos de datos superiores a un par de miles de ejemplos sin procesamiento paralelo.

Los métodos kernel deben su nombre al uso de funciones kernel, que les permiten operar en un espacio de características implícito de alta dimensión sin tener que calcular las coordenadas de los datos en ese espacio, sino simplemente calculando los productos internos entre las imágenes de todos los pares de datos en el espacio de características. Esta operación suele ser más barata computacionalmente que el cálculo explícito de las coordenadas. Este enfoque se denomina "truco del núcleo".^[2] Se han introducido funciones de núcleo para datos secuenciales, gráficos, texto, imágenes y vectores.

Entre los algoritmos capaces de funcionar con kernels figuran el perceptrón kernel, las máquinas de vectores soporte (SVM), los procesos gaussianos, el análisis de componentes principales (PCA), el análisis de correlación canónica, la regresión ridge, la agrupación espectral, los filtros adaptativos lineales y muchos otros.

La mayoría de los algoritmos kernel se basan en la optimización convexa o en problemas propios y están bien fundamentados estadísticamente. Normalmente, sus propiedades estadísticas se analizan mediante la teoría del aprendizaje estadístico (por ejemplo, mediante la complejidad de Rademacher).

Motivación y explicación informal

Los métodos kernel pueden considerarse aprendices basados en instancias: en lugar de aprender un conjunto fijo de parámetros correspondientes a las características de sus entradas, "recuerdan" las características de sus entradas ${\displaystyle i}$ del ejemplo de formación ${\displaystyle (\mathbf {x} _{i},y_{i})}$ y aprender para ella un peso correspondiente ${\displaystyle w_{i}}$. La predicción para entradas no etiquetadas, es decir, las que no están en el conjunto de entrenamiento, se trata mediante la aplicación de una función de similitud ${\displaystyle k}$, llamada un kernel, entre la entrada no etiquetada ${\displaystyle \mathbf {x'} }$ y cada una de las entradas de formación ${\displaystyle \mathbf {x} _{i}}$. or ejemplo, un clasificador binario kernelizado suele calcular una suma ponderada de similitudes:

${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} )}$,

Donde:

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$ es la etiqueta predicha por el clasificador binario kernelizado para la entrada no etiquetada ${\displaystyle \mathbf {x'} }$ cuya verdadera etiqueta oculta ${\displaystyle y}$ es de interés;
• ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ es la función kernel que mide la similitud entre cualquier par de entradas ${\displaystyle \mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}}$;
• la suma abarca el n ejemplos etiquetados ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}}$ en el conjunto de entrenamiento del clasificador, con ${\displaystyle y_{i}\in \{-1,+1\}}$;
• el ${\displaystyle w_{i}\in \mathbb {R} }$ son las ponderaciones de los ejemplos de entrenamiento, determinadas por el algoritmo de aprendizaje;
• la función signo ${\displaystyle \operatorname {sgn} }$ determina si la clasificación prevista ${\displaystyle {\hat {y}}}$ sale positivo o negativo.

Los clasificadores de núcleo se describieron ya en la década de 1960, con la invención del perceptrón de núcleo.^[3] Alcanzaron gran protagonismo con la popularidad de la máquina de vectores de soporte (SVM) en la década de 1990, cuando se descubrió que la SVM era competitiva con las redes neuronales en tareas como el reconocimiento de escritura a mano.

Matemáticas: el truco del kernel

SVM con kernel dado por ${\displaystyle \varphi ((a,b))=(a,b,a^{2}+b^{2})}$ y por lo tanto ${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}}$ . Los puntos de entrenamiento se mapean en un espacio tridimensional en el que se puede encontrar fácilmente un hiperplano de separación.

El truco del núcleo (o kernel) evita el mapeo explícito necesario para que los algoritmos de aprendizaje lineal aprendan una función no lineal o un límite de decisión. Para todo ${\displaystyle \mathbf {x} }$ and ${\displaystyle \mathbf {x'} }$ en el espacio de entrada ${\displaystyle {\mathcal {X}}}$, ciertas funciones ${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$ puede expresarse como un producto interior en otro espacio ${\displaystyle {\mathcal {V}}}$. La función ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ a menudo se denomina núcleo o función de núcleo. La palabra "núcleo" se utiliza en matemáticas para designar una función de ponderación de una suma o integral ponderada.

Ciertos problemas de aprendizaje automático tienen más estructura que una función de ponderación arbitraria ${\displaystyle k}$. El cálculo es mucho más sencillo si el núcleo puede escribirse en forma de "mapa de características" ${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$ que satisface:

${\displaystyle k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}.}$

La restricción clave es que ${\displaystyle \langle \cdot ,\cdot \rangle _{\mathcal {V}}}$ debe ser un producto interno adecuado. Por otra parte, una representación explícita para ${\displaystyle \varphi }$ no es necesario, siempre que ${\displaystyle {\mathcal {V}}}$ es un espacio producto interior. La alternativa se deduce del teorema de Mercer: una función definida implícitamente ${\displaystyle \varphi }$ existe siempre que el espacio ${\displaystyle {\mathcal {X}}}$ puede equiparse con una medida adecuada que garantice la función ${\displaystyle k}$ satisface la condición de Mercer.

El teorema de Mercer es similar a una generalización del resultado del álgebra lineal que asocia un producto interior a cualquier matriz definida positiva. De hecho, la condición de Mercer puede reducirse a este caso más simple. Si elegimos como medida la medida de recuento ${\displaystyle \mu (T)=|T|}$ para todos los ${\displaystyle T\subset X}$, que cuenta el número de puntos dentro del conjunto ${\displaystyle T}$,entonces la integral en el teorema de Mercer se reduce a una suma:

:${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_{i}c_{j}\geq 0.}$

Si esta suma es válida para todas las secuencias finitas de puntos ${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$ en ${\displaystyle {\mathcal {X}}}$ y todas las opciones de ${\displaystyle n}$ coeficientes reales ${\displaystyle (c_{1},\dots ,c_{n})}$ (véase núcleo definido positivo), entonces la función ${\displaystyle k}$ cumple la condición de Mercer.

Algunos algoritmos que dependen de relaciones arbitrarias en el espacio nativo ${\displaystyle {\mathcal {X}}}$ tendría, de hecho, una interpretación lineal en un entorno diferente: el espacio de alcance de ${\displaystyle \varphi }$. La interpretación lineal nos da una idea del algoritmo. Además, a menudo no es necesario calcular ${\displaystyle \varphi }$ directamente durante el cálculo, como ocurre con las máquinas de vectores soporte. Algunos citan esta reducción del tiempo de ejecución como la principal ventaja. Los investigadores también lo utilizan para justificar los significados y propiedades de los algoritmos existentes.

Teóricamente, una matriz de Gram ${\displaystyle \mathbf {K} \in \mathbb {R} ^{n\times n}}$ con respecto a ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}}$ (a veces también llamada "matriz de núcleo"^[4]), donde ${\displaystyle K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})}$, debe ser semidefinida positiva (PSD).^[5] Empíricamente, para la heurística de aprendizaje automático, la elección de una función ${\displaystyle k}$ que no cumplan la condición de Mercer pueden seguir funcionando razonablemente si ${\displaystyle k}$ al menos se aproxima a la idea intuitiva de similitud.^[6] Independientemente de si ${\displaystyle k}$ puede seguir denominándose "núcleo" o "kernel".

Si la función kernel ${\displaystyle k}$ es también una función de covarianza como la utilizada en los procesos gaussianos, entonces la matriz de Gram ${\displaystyle \mathbf {K} }$ también puede denominarse matriz de covarianza.^[7]

Aplicaciones

Las áreas de aplicación de los métodos kernel son diversas e incluyen geoestadística,[8] kriging, ponderación de distancia inversa, reconstrucción 3D, bioinformática, quimioinformática, extracción de información y reconocimiento de escritura.

Núcleos o kernels populares

• Proyección de Fisher
• Gráfico de kernel
• Suavizado de kernel
• Núcleo polinómico
• Núcleo de función de base radial (RBF)
• Núcleos de cadena
• Kernel de tangente neural
• Núcleo del proceso gaussiano de red (NNGP)

Véase también

• Métodos kernel para vectores de salida
• Teorema de representación
• Aprendizaje por similitud
• Teorema de Cover
• Estimación de Densidad de Kernel

Referencias

1. «Kernel method». Engati (en inglés). Consultado el 4 de marzo de 2024.
2. Theodoridis, Sergios (2008). «Pattern Recognition». Elsevier B.V. ISBN 9780080949123.
3. Aizerman, M. A.; Braverman, Emmanuel M.; Rozonoer, L. I. (1964). «"Theoretical foundations of the potential function method in pattern recognition learning"». Automation and Remote Control. «Cited in Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Automatic capacity tuning of very large VC-dimension classifiers. Advances in neural information processing systems.»
4. Hofmann, Thomas; Schölkopf, Bernhard; Smola, Alexander J. (1 de junio de 2008). «Kernel methods in machine learning». The Annals of Statistics 36 (3). ISSN 0090-5364. doi:10.1214/009053607000000677. Consultado el 5 de marzo de 2024.
5. Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). «Foundations of Machine Learning». US, Massachusetts: MIT Press. ISBN 9780262018258.
6. «Support Vector Machines: Mercer's Condition». web.archive.org. 15 de octubre de 2018. Archivado desde el original el 15 de octubre de 2018. Consultado el 5 de marzo de 2024.
7. Rasmussen, Carl Edward; Williams, Christopher K. I. (2006). «Gaussian Processes for Machine Learning.». MIT Press. ISBN 0-262-18253-X.

Lectura adicional

• Shawe-Taylor, J.; Cristianini, N. (2004). Kernel Methods for Pattern Analysis. Cambridge University Press.
• Liu, W.; Principe, J.; Haykin, S. (2010). Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley. ISBN 9781118211212.
• Schölkopf, B.; Smola, A. J.; Bach, F. (2018). Learning with Kernels : Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press. ISBN 978-0-262-53657-8.

Enlaces externos

• Kernel-Machines Org—community website
• onlineprediction.net Kernel Methods Article