método del núcleo

Clase de algoritmos para 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, 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 : por el contrario, los métodos del kernel solo requieren un kernel especificado por el usuario , es decir, una función de similitud sobre todas las funciones. pares de puntos de datos calculados utilizando productos internos . El mapa de características en las máquinas del kernel es de dimensión infinita pero solo requiere una matriz de dimensión finita de la entrada del usuario de acuerdo con el teorema del Representante . Las máquinas del kernel tardan en calcular conjuntos de datos de más de un par de miles de ejemplos sin procesamiento paralelo.

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 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 del núcleo ". ^[2] Se han introducido funciones kernel 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 , 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 crestas , la agrupación espectral , los filtros adaptativos lineales y muchos otros.

La mayoría de los algoritmos del kernel se basan en optimización convexa o problemas propios y están estadísticamente bien fundamentados. 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 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 -ésimo ejemplo de entrenamiento y aprenden para él el peso correspondiente . La predicción para 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 núcleo , 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'} ),}$$

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$es la etiqueta predicha 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 del núcleo 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 determinado por 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 se describieron ya en la década de 1960, con la invención del perceptrón de kernel . ^[3] Saltaron a 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 kernel dado por y por lo tanto . Los puntos de entrenamiento se asignan a un espacio tridimensional donde se puede encontrar fácilmente un hiperplano de separación. ${\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 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 , ciertas funciones pueden expresarse como un producto interno en otro espacio . La función a menudo se denomina núcleo o función núcleo . La palabra "núcleo" se utiliza en matemáticas para indicar 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 vuelve 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}}.}$$

espacio de producto internoteorema de Mercermedidala 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 puede reducirse a este caso más simple. Si elegimos como 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.}$$

núcleo definido positivo ${\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 del algoritmo. Además, a menudo no es necesario 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 principal beneficio. 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 kernel" ^[4] ), donde debe ser semidefinida positiva (PSD) . ^[5] Empíricamente, para las heurísticas del 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 núcleo Mercer, todavía se le puede denominar "núcleo". ${\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 que se utiliza 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 .

Núcleos populares

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

Ver también

• Métodos kernel para salida vectorial.
• Estimación de la densidad del grano.
• Teorema del representante
• Aprendizaje por similitud
• teorema de cover

Referencias

1. "Método del núcleo". Engatí . Consultado el 4 de abril de 2023 .
2. Theodoridis, Sergios (2008). Reconocimiento de patrones . Elsevier BV pág. 203.ISBN​ 9780080949123.
3. Aizerman, MA; Braverman, Emmanuel M.; Rozonoer, LI (1964). "Fundamentos teóricos del método de la función potencial en el aprendizaje por reconocimiento de patrones". Automatización y Control Remoto . 25 : 821–837.Citado en Guyon, Isabelle; Bóser, B.; Vápnik, Vladimir (1993). "Sintonización automática de capacidad de clasificadores de dimensiones VC de gran tamaño" . Avances en los sistemas de procesamiento de información neuronal. CiteSeerX 10.1.1.17.7215 . 
4. Hofmann, Thomas; Scholkopf, Bernhard; Smola, Alexander J. (2008). "Métodos del kernel en aprendizaje automático". Los anales de la estadística . 36 (3). arXiv : matemáticas/0701907 . doi : 10.1214/009053607000000677 . S2CID  88516979.
5. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258.
6. Sewell, Martín. "Máquinas de vectores de soporte: 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 aprendizaje automático . Prensa del MIT. ISBN 0-262-18253-X. ^{[ página necesaria ]}
8. Honarkhah, M.; Caers, J. (2010). "Simulación estocástica de patrones mediante modelado de patrones basado en distancias". Geociencias Matemáticas . 42 (5): 487–517. Código Bib : 2010MaGeo..42..487H. doi :10.1007/s11004-010-9276-7. S2CID  73657847.

Otras lecturas

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

enlaces externos

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