Núcleo de cadena

Un núcleo de cadena es una función del núcleo definida en cadenas , es decir secuencias finitas de caracteres que no necesariamente tienen la misma longitud. Los núcleos de cadena pueden entenderse intuitivamente como funciones que miden la similitud de pares de cadenas: cuanto más similares sean dos cadenas a y b , mayor será el valor del núcleo de cadena K(a, b) .

El uso de núcleos de cadena con algoritmos de aprendizaje del núcleo, como máquinas de vectores de soporte, permite que dichos algoritmos operen en cadenas sin tener que convertirlas en vectores de características de longitud constante que tienen elementos reales [1] . Los núcleos de cadenas se utilizan en áreas donde se agrupa o clasifica una secuencia de datos, como el procesamiento de datos de texto y el análisis de genes [2] .

Introducción informal

Supongamos que alguien va a comparar automáticamente dos fragmentos de texto y determinar su similitud relativa. Para muchas aplicaciones, puede ser suficiente encontrar algunas palabras clave que coincidan completamente. Un ejemplo en el que una coincidencia tan exacta no siempre es suficiente se puede encontrar en los detectores de spam [3] . Otro ejemplo es el análisis de genes por computadora, en el que los genes homólogos tienen mutaciones en las que se pueden eliminar, insertar o reemplazar caracteres en la secuencia general.

Antecedentes

Dado que algunos métodos bien establecidos de agrupación, clasificación y extracción de información de los datos (por ejemplo, la máquina de vectores de soporte) están diseñados para trabajar con vectores (es decir, los datos representan elementos de un espacio vectorial), el uso de un núcleo de cadena permite estos métodos se extiendan a datos secuenciales.

El método del núcleo de cadenas contrasta con los enfoques de clasificación de texto comunes antes de su aparición, donde los vectores de características mostraban solo la presencia o ausencia de una palabra. Esto no solo mejoró los enfoques existentes, sino que también es un ejemplo de cómo toda la clase de kernels se está adaptando a las estructuras de datos que comenzaron a aparecer en el siglo XXI. Gärtner [4] realizó una revisión de tales métodos .

En bioinformática, los núcleos de cuerdas se utilizan para transformar secuencias biológicas, como proteínas o ADN, en vectores para su uso posterior en modelos de aprendizaje automático. Un ejemplo de un kernel de cadena para tales fines es el kernel de perfil [5] .

Definición

El núcleo del dominio D es una función que satisface algunas condiciones ( simétrica en argumentos, continua , definida positiva en algún sentido). $K:D\times D\to \mathbb {R}$

El teorema de Mercer establece que K se puede expresar como unafunción c queasigna los argumentos a un espacio de producto escalar . ${\ Displaystyle K (x, y) = \ varphi (x) \ cdot \ varphi (y)}$ $\varphi$

Ahora podemos reproducir la definición del núcleo de subsecuencias de cadenas [1] sobre cadenas del alfabeto . El mapeo por coordenadas se define de la siguiente manera: $\Sigma$

\varphi _{u}:\left\{{\begin{array}{l}\Sigma ^{n}\rightarrow \mathbb {R} ^{\Sigma ^{n))\\s\mapsto \sum _{\mathbf {i} :u=s_{\mathbf {i} }}\lambda ^{l(\mathbf {i} )}\end{matriz}}\right.

Los índices son multiíndices y u es una cadena de longitud n ; las subsecuencias pueden ser discontinuas, pero los espacios se penalizan. El índice múltiple especifica las posiciones coincidentes de los caracteres en u y s . es la diferencia entre el primer y el último elemento en , es decir, qué tan lejos está una subsecuencia en s de su correspondiente subsecuencia en u . El parámetro se puede configurar en cualquier valor entre 0 (no se permiten espacios, ya que solo 0 0 no es 0, sino 1) y 1 (las subsecuencias incluso con grandes distancias pesan lo mismo que sin distancias, es decir, como subsecuencias continuas), desde . $\mathbf{i}$ $\mathbf{i}$ ${\ estilo de visualización l (\ mathbf {i})}$ $\mathbf{i}$ $\lambda$ $1^{l(\mathbf {i} )}=1$

Para algunos algoritmos importantes, el algoritmo obtiene los datos solo en expresiones que utilizan el producto escalar del vector de características, por lo que se denominan métodos kernel . Por lo tanto, es deseable que no sea necesario calcular explícitamente la transformación , sino que sea posible calcular solo el producto escalar a través del kernel, lo que puede ser mucho más rápido, especialmente cuando se usa la aproximación [1] . $\varfi(x)$

Notas

↑ 1 2 3 Lodhi, Saunders, Shawe-Taylor, Cristianini, Watkins, 2002 , p. 419-444.
↑ Leslie, Eskin, Noble, 2002 , pág. 566-575.
↑ Amayri, Bouguila .
↑ Gartner, 2003 .
↑ Kuang, Ie, Wang et al., 2005 , pág. 527-550.

Literatura

Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins. Clasificación de texto mediante núcleos de cadenas // Journal of Machine Learning Research. — 2002.
Leslie C., Eskin E., Noble WS Pacific Symposium on Biocomputing Proceedings. — 2002.
Ola Amayri, Nizar Bouguila. Filtrado de spam de máquinas de vectores de soporte en línea mejorado utilizando núcleos de cadena // Progreso en el reconocimiento de patrones, análisis de imágenes, visión por computadora y aplicaciones. XIV Congreso Iberoamericano de Reconocimiento de Patrones, CIARP 2009, Guadalajara, Jalisco, México, 15 al 18 de noviembre. — Springer. - T. 5856. - (Apuntes de cátedra en Informática).
Gärtner T. Una encuesta de núcleos para datos estructurados // ACM SIGKDD Exploration Newsletter. - ACM, 2003. - V. 5 , núm. 1 .
Rui Kuang, Eugene Ie, Ke Wang, Kai Wang, Mahira Siddiqi, Yoav Freund, Christina Leslie. Kernels de cadenas basados en perfiles para detección de homología remota y extracción de motivos // Journal of Bioinformatics and Computational Biology. - 2005. - junio ( vol. 3 , número 3 ). — ISSN 0219-720 .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG