Método del núcleo

En aprendizaje automático , las máquinas de kernel son una clase de algoritmos para 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 , clústeres , clasificaciones , componentes principales , correlaciones , clasificaciones ) en conjuntos de datos. Para muchos algoritmos que resuelven estas tareas, los datos en representación bruta deben transformarse explícitamente en representaciones de vectores de características a través de un mapa de características especificado por el usuario ; en contraste, los métodos de kernel solo requieren un kernel especificado por el usuario , es decir, una función de similitud sobre todos los pares de puntos de datos calculada usando productos internos . El mapa de características en las máquinas de kernel es de dimensión infinita, pero solo requiere una matriz de dimensión finita de entrada del usuario según el teorema del representante . Las máquinas de kernel son lentas para calcular conjuntos de datos mayores a un par de miles de ejemplos sin procesamiento paralelo.

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

Entre los algoritmos capaces de operar con núcleos se incluyen el perceptrón de núcleo , las máquinas de vectores de soporte (SVM), los procesos gaussianos , el análisis de componentes principales (PCA), el análisis de correlación canónica , la regresión de cresta , la agrupación espectral , los filtros adaptativos lineales y muchos otros.

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

Los métodos de kernel pueden considerarse como aprendices basados ​​en instancias : en lugar de aprender un conjunto fijo de parámetros que corresponden a las características de sus entradas, en cambio "recuerdan" las${\displaystyle i}$-th ejemplo de entrenamiento${\displaystyle (\mathbf {x} _{i},y_{i})}$y aprende para ello un peso correspondiente${\displaystyle w_{i}}$La predicción para entradas no etiquetadas, es decir, aquellas que no están en el conjunto de entrenamiento, se trata mediante la aplicación de una función de similitud .${\displaystyle k}$, llamado núcleo , entre la entrada sin etiquetar${\displaystyle \mathbf {x'} }$y cada uno de los insumos de entrenamiento${\displaystyle \mathbf {x} _ {i}}$. Por ejemplo, un clasificador binario kernelizado normalmente calcula una suma ponderada de similitudes $${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),}$$ dónde

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$es la etiqueta predicha por el clasificador binario kernelizado para la entrada sin etiquetar${\displaystyle \mathbf {x'} }$cuya etiqueta verdadera 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 los 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 los pesos para los ejemplos de entrenamiento, determinados por el algoritmo de aprendizaje;
• la función signo${\displaystyle \operatorname {sgn} }$determina si la clasificación prevista${\displaystyle {\hat {y}}}$da positivo o negativo.

Los clasificadores de kernel se describieron ya en la década de 1960, con la invención del perceptrón de kernel . ^{[ 3 ]} Alcanzaron gran prominencia 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 .

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

Ciertos problemas en el aprendizaje automático tienen más estructura que una función de ponderación arbitraria.${\displaystyle k}$El cálculo se simplifica mucho si el núcleo se puede escribir en forma de "mapa de características".${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$lo cual 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 otro lado, una representación explícita para${\displaystyle \varphi }$no es necesario, siempre y cuando${\displaystyle {\mathcal {V}}}$es un espacio de producto interno . 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 interno a cualquier matriz definida positiva . De hecho, la condición de Mercer se puede reducir a este caso más simple. Si elegimos como nuestra medida la medida de conteo${\displaystyle \mu (T)=|T|}$a pesar de${\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 sumatoria$${\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 se cumple 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 de valor real${\displaystyle (c_{1},\dots ,c_{n})}$(cf. núcleo definido positivo ), entonces la función${\displaystyle k}$Satisface la condición de Mercer.

Algunos algoritmos que dependen de relaciones arbitrarias en el espacio nativo${\displaystyle {\mathcal {X}}}$De hecho, tendría una interpretación lineal en un contexto diferente: el espacio de rangos 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 de soporte . Algunos citan este atajo en el tiempo de ejecución como la principal ventaja. Los investigadores también lo utilizan para justificar el significado y las 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 las heurísticas de aprendizaje automático, las elecciones de una función${\displaystyle k}$que no satisfacen la condición de Mercer aún pueden funcionar razonablemente si${\displaystyle k}$al menos se aproxima a la idea intuitiva de similitud. ^{[ 6 ]} Independientemente de si${\displaystyle k}$es un núcleo Mercer,${\displaystyle k}$Todavía se le puede denominar "núcleo".

Si la función kernel${\displaystyle k}$También es una función de covarianza como la que se usa en los procesos gaussianos , luego la matriz de Gram${\displaystyle \mathbf {K} }$También se la puede llamar matriz de covarianza . ^{[ 7 ]}

Las áreas de aplicación de los métodos de 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 a mano .

• núcleo de Fisher
• Núcleos de grafos
• suavizador de núcleo
• Núcleo polinomial
• Núcleo de función de base radial (RBF)
• Núcleos de cadena
• núcleo tangente neuronal
• Núcleo de proceso gaussiano de red neuronal (NNGP)

• Métodos de kernel para salida vectorial
• Estimación de densidad de kernel
• Teorema del representante
• Aprendizaje por similitud
• Teorema de Cover

• Shawe-Taylor, J .; Cristianini, N. (2004). Métodos de núcleo para el análisis de patrones . Cambridge University Press. ISBN 9780511809682.
• Liu, W.; Principe, J.; Haykin, S. (2010). Filtrado adaptativo de kernel: una introducción completa . Wiley. ISBN 9781118211212.
• Schölkopf, B .; Smola, AJ; Bach, F. (2018). Aprendizaje con núcleos  : máquinas de vectores de soporte, regularización, optimización y más allá . MIT Press. ISBN 978-0-262-53657-8.

• Artículo sobre métodos de kernel en onlineprediction.net