Método del núcleo

Clase de algoritmos para el análisis de patrones

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 , 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 : por el contrario, los métodos kernel solo requieren un kernel especificado por el usuario , es decir, una función de similitud sobre todos los pares de puntos de datos calculados utilizando productos internos . El mapa de características en las máquinas kernel es de dimensión infinita, pero solo 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 para calcular conjuntos de datos más grandes que 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 calcular nunca 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 computacionalmente más barata que el cálculo explícito de las coordenadas. Este enfoque se denomina " truco kernel ". ^[2] Las funciones kernel se han introducido para datos de secuencia, gráficos , texto, imágenes y vectores.

Los algoritmos capaces de operar con kernels incluyen el perceptrón de kernel , 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 , el agrupamiento 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 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 kernel pueden considerarse 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 ejemplo de entrenamiento -ésimo y aprenden para él un peso correspondiente . 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 , llamada kernel , entre la entrada no etiquetada y cada una de las entradas de entrenamiento . Por ejemplo, un clasificador binario kernelizado normalmente calcula una suma ponderada de similitudes donde ${\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'} ),}$$

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$es la etiqueta prevista del clasificador binario kernelizado para la entrada sin etiquetar cuya etiqueta verdadera 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 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 en el conjunto de entrenamiento del clasificador, con ; ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}}$ ${\displaystyle y_{i}\in \{-1,+1\}}$
• son los pesos de los ejemplos de entrenamiento, según lo determina el algoritmo de aprendizaje; ${\displaystyle w_{i}\in \mathbb {R} }$
• La función de signo determina si la clasificación prevista resulta positiva o negativa. ${\displaystyle \operatorname {sgn} }$ ${\displaystyle {\hat {y}}}$

Los clasificadores de kernel fueron descritos 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 .

Matemáticas: el truco del núcleo

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

El truco del núcleo 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 , ciertas funciones se pueden expresar como un producto interno en otro espacio . La función se conoce a menudo como núcleo o función de 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 . ${\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 satisface La restricción clave es que debe ser un producto interno adecuado. Por otro lado, no es necesaria una representación explícita para, siempre que sea un espacio de producto interno . La alternativa se desprende 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 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}}.}$$ ${\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 medida la medida de conteo para todos los , que cuenta el número de puntos dentro del conjunto , entonces la integral en el teorema de Mercer se reduce a una suma Si esta suma se cumple para todas las secuencias finitas de puntos en y todas las elecciones de coeficientes de valor real (cf. kernel definido positivo ), entonces la función satisface la condición de Mercer. ${\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.}$$ ${\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 entorno diferente: el espacio de rango de . La interpretación lineal nos da una idea sobre el 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 en el tiempo de ejecución como el beneficio principal. Los investigadores también lo utilizan para justificar los significados y las 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 kernel" ^[4] ), donde , debe ser semidefinida positiva (PSD) . ^[5] Empíricamente, para las heurísticas de aprendizaje automático, las elecciones de una función que no satisfacen la condición de Mercer aún pueden funcionar razonablemente si al menos se aproximan a la idea intuitiva de similitud. ^[6] Independientemente de si es un kernel de Mercer, aún puede denominarse "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 kernel es también una función de covarianza como la utilizada en los procesos gaussianos , entonces la matriz de Gram también puede denominarse matriz de covarianza . ^[7] ${\displaystyle k}$ ${\displaystyle \mathbf {K} }$

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 a mano .

Granos populares

• Núcleo de Fisher
• Núcleos gráficos
• Suavizado de núcleos
• 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 red neuronal (NNGP)

Véase también

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

Referencias

1. "Método Kernel". Engati . Consultado el 4 de abril de 2023 .
2. Theodoridis, Sergios (2008). Reconocimiento de patrones . Elsevier BV p. 203. ISBN 9780080949123.
3. 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 control remoto . 25 : 821–837.Citado en Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Ajuste automático de la capacidad de clasificadores de dimensión VC muy grande . Avances en sistemas de procesamiento de información neuronal. CiteSeerX 10.1.1.17.7215 . 
4. Hofmann, Thomas; Scholkopf, Bernhard; Smola, Alexander J. (2008). "Métodos de núcleo en aprendizaje automático". Anales de estadística . 36 (3). arXiv : math/0701907 . doi : 10.1214/009053607000000677 . S2CID  88516979.
5. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . EE. UU., Massachusetts: MIT Press. ISBN 9780262018258.
6. Sewell, Martin. "Máquinas de vectores de soporte: la condición de Mercer". Máquinas de vectores de soporte. Archivado desde el original el 15 de octubre de 2018. Consultado el 30 de mayo de 2014 .
7. Rasmussen, Carl Edward; Williams, Christopher KI (2006). Procesos gaussianos para el aprendizaje automático . MIT Press. ISBN 0-262-18253-X. ^{[ página necesaria ]}
8. Honarkhah, M.; Caers, J. (2010). "Simulación estocástica de patrones utilizando modelado de patrones basado en la distancia". Geociencias matemáticas . 42 (5): 487–517. Código Bibliográfico :2010MaGeo..42..487H. doi :10.1007/s11004-010-9276-7. S2CID  73657847.

Lectura adicional

• Shawe-Taylor, J. y 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 núcleo: 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. MIT Press. ISBN 978-0-262-53657-8.

Enlaces externos

• Kernel-Machines Org: sitio web de la comunidad
• Artículo sobre métodos del núcleo de onlineprediction.net