Método de kernel

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

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). La tarea general del análisis de patrones es encontrar y estudiar tipos generales de relaciones (por ejemplo , grupos , clasificaciones , componentes principales , correlaciones , clasificaciones ) en conjuntos de datos. Para muchos algoritmos que resuelven estas tareas, los datos en representación sin procesar 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 del kernel requieren solo un kernel especificado por el usuario , es decir, una función de similitud sobre pares de puntos de datos en representación sin formato.

Los métodos del kernel deben su nombre al uso de funciones del kernel , que les permiten operar en un espacio de características implícitas de alta dimensión sin siquiera calcular las coordenadas de los datos en ese espacio, sino simplemente computando los productos internos 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 denomina " truco del núcleo ". ^[1] Se han introducido funciones del núcleo para datos de secuencia, gráficos , texto, imágenes y vectores.

Los algoritmos capaces de operar con núcleos incluyen el perceptrón del núcleo , máquinas de vectores de soporte (SVM), procesos gaussianos , análisis de componentes principales (PCA), análisis de correlación canónica , regresión de crestas , agrupamiento espectral , filtros adaptativos lineales y muchos otros. Cualquier modelo lineal se puede convertir en un modelo no lineal aplicando el truco del kernel al modelo: reemplazando sus características (predictores) por una función del kernel. ^{[ cita requerida ]}

La mayoría de los algoritmos del kernel se basan en optimización convexa o problemas 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 ).

Motivación y explicación informal

Los métodos del kernel se pueden considerar como aprendices basados ​​en instancias : en lugar de aprender un conjunto fijo de parámetros correspondientes a las características de sus entradas, "recuerdan" el -ésimo ejemplo de entrenamiento y aprenden el peso correspondiente . La predicción de entradas sin etiquetar, es decir, aquellas que no están en el conjunto de entrenamiento, se trata mediante la aplicación de una función de similitud , llamada kernel , entre la entrada sin etiquetar y cada una de las entradas de entrenamiento . Por ejemplo, un clasificador binario kernelizado normalmente calcula una suma ponderada de similitudes${\displaystyle i}$${\displaystyle (\mathbf {x} _{i},y_{i})}$${\displaystyle w_{i}}$ ${\displaystyle k}$${\displaystyle \mathbf {x'} }$${\displaystyle \mathbf {x} _{i}}$

${\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 del clasificador binario kernelizado para la entrada sin etiqueta cuya verdadera etiqueta oculta es de interés;${\displaystyle \mathbf {x'} }$${\displaystyle y}$
• ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$es la función del núcleo que mide la similitud entre cualquier par de entradas ;${\displaystyle \mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}}$
• la suma varía sobre los n ejemplos etiquetados en el conjunto de entrenamiento del clasificador, con ;${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}}$${\displaystyle y_{i}\in \{-1,+1\}}$
• la son los pesos para los ejemplos de entrenamiento, según lo determinado por el algoritmo de aprendizaje;${\displaystyle w_{i}\in \mathbb {R} }$
• la función de signo determina si la clasificación predicha resulta positiva o negativa.${\displaystyle \operatorname {sgn} }$${\displaystyle {\hat {y}}}$

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

SVM con kernel dado por φ (( a , b )) = ( a , b , a ² + b ² ) y por lo tanto K ( x , y ) = . Los puntos de entrenamiento se asignan a un espacio tridimensional donde se puede encontrar fácilmente un hiperplano separador.${\displaystyle \mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}}$

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 y en el espacio de entrada , determinadas funciones pueden expresarse como un producto interno en otro espacio . La función a menudo se denomina kernel o función de kernel . La palabra "núcleo" se usa en matemáticas para denotar una función de ponderación para una suma ponderada o integral .${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x'} }$${\displaystyle {\mathcal {X}}}$${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$${\displaystyle {\mathcal {V}}}$${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$

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

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

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

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 para todos , que cuenta el número de puntos dentro del conjunto , entonces la integral en el teorema de Mercer se reduce a una suma${\displaystyle \mu (T)=|T|}$${\displaystyle T\subset X}$${\displaystyle T}$

${\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 mantiene para todas las secuencias finitas de puntos en y todas las opciones de coeficientes de valor real (cf. kernel definida positiva ), entonces la función satisface la condición de Mercer.${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$${\displaystyle {\mathcal {X}}}$${\displaystyle n}$${\displaystyle (c_{1},\dots ,c_{n})}$${\displaystyle k}$

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

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

Si la función del núcleo también es una función de covarianza como se usa en los procesos gaussianos , entonces la matriz de Gram también se puede llamar matriz de covarianza . ^[6]${\displaystyle k}$${\displaystyle \mathbf {K} }$

Aplicaciones

Las áreas de aplicación de los métodos del kernel son diversas e incluyen geoestadística , ^[7] 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úcleos populares

• Núcleo de Fisher
• Núcleos de gráficos
• Kernel más suave
• Núcleo polinomial
• Núcleo de función de base radial (RBF)
• Núcleos de cadena
• Núcleo tangente neuronal
• Núcleo del proceso gaussiano de la red neuronal (NNGP)

Ver también

• Métodos de kernel para salida vectorial
• Estimación de la densidad de kernel
• Representante teorema
• Teorema de Cover

Referencias

1. Theodoridis, Sergios (2008). Reconocimiento de patrones . Elsevier BV pág. 203. ISBN 9780080949123.
2. Aizerman, MA; Braverman, Emmanuel M .; Rozonoer, LI (1964). "Fundamentos teóricos del método de función potencial en el aprendizaje de reconocimiento de patrones". Automatización y Telemando . 25 : 821–837.Citado en Guyon, Isabelle; Boser, B .; Vapnik, Vladimir (1993). Ajuste automático de la capacidad de clasificadores de dimensiones VC muy grandes . Avances en sistemas de procesamiento de información neuronal. CiteSeerX 10.1.1.17.7215 . 
3. Hofmann, Thomas; Scholkopf, Bernhard; Smola, Alexander J. (2008). "Métodos de Kernel en Machine Learning" .
4. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258.
5. Sewell, Martin. "Máquinas de vectores de soporte: condición de Mercer" . www.svms.org .
6. Rasmussen, CE; Williams, CKI (2006). "Procesos gaussianos para el aprendizaje automático".
7. Honarkhah, M .; Caers, J. (2010). "Simulación estocástica de patrones utilizando el modelado de patrones basado en la distancia". Geociencias matemáticas . 42 : 487–517. doi : 10.1007 / s11004-010-9276-7 .

Lectura adicional

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

Enlaces externos

• Kernel-Machines Org : sitio web de la comunidad
• www.support-vector-machines.org (literatura, revisión, software, enlaces relacionados con Support Vector Machines - Sitio académico)
• onlineprediction.net Artículo sobre métodos del kernel