Núcleo de cadena

En el aprendizaje automático y la minería de datos , un kernel de cadena es una función kernel que opera sobre cadenas , es decir, secuencias finitas de símbolos que no necesariamente tienen la misma longitud. Los kernels de cadena pueden entenderse intuitivamente como funciones que miden la similitud entre pares de cadenas: cuanto más similares sean dos cadenas a y b , mayor será el valor del kernel de cadena K ( a , b ).

El uso de núcleos de cadena con algoritmos de aprendizaje basados ​​en núcleos , como las máquinas de vectores de soporte, permite que dichos algoritmos trabajen con cadenas sin tener que convertirlas en vectores de características de longitud fija y valores reales . ^{[ 1 ]} Los núcleos de cadena se utilizan en dominios donde se agrupan o clasifican datos de secuencia , por ejemplo, en minería de texto y análisis genético . ^{[ 2 ]}

Supongamos que se desea comparar automáticamente algunos fragmentos de texto e indicar su similitud relativa. Para muchas aplicaciones, podría ser suficiente encontrar algunas palabras clave que coincidan exactamente. Un ejemplo donde la coincidencia exacta no siempre es suficiente se encuentra en la detección de spam . ^{[ 3 ]} Otro ejemplo sería en el análisis genético computacional, donde los genes homólogos han mutado , lo que da como resultado subsecuencias comunes junto con símbolos eliminados, insertados o reemplazados.

Dado que varios métodos probados de agrupamiento de datos, clasificación y recuperación de información (por ejemplo, las máquinas de vectores de soporte) están diseñados para trabajar con vectores (es decir, los datos son elementos de un espacio vectorial), el uso de un núcleo de cadena permite extender estos métodos para manejar datos secuenciales.

El método del kernel de cadena contrasta con los enfoques anteriores para la clasificación de texto, donde los vectores de características solo indicaban la presencia o ausencia de una palabra. No solo mejora estos enfoques, sino que es un ejemplo de toda una clase de kernels adaptados a estructuras de datos, que comenzaron a aparecer a principios del siglo XXI. Gärtner ha recopilado una revisión de dichos métodos. ^{[ 4 ]}

En bioinformática, los kernels de cadena se utilizan especialmente para transformar secuencias biológicas, como proteínas o ADN, en vectores para su posterior uso en modelos de aprendizaje automático. Un ejemplo de kernel de cadena utilizado para este propósito es el kernel de perfil. ^{[ 5 ]}

Un núcleo en un dominio${\displaystyle D}$es una función${\displaystyle K:D\times D\rightarrow \mathbb {R} }$ que cumplan ciertas condiciones (ser simétricas en los argumentos, continuas y semidefinidas positivas en cierto sentido).

El teorema de Mercer afirma que${\displaystyle K}$entonces se puede expresar como${\displaystyle K(x,y)=\varphi (x)\cdot \varphi (y)}$con${\displaystyle \varphi }$mapear los argumentos en un espacio de producto interno .

Ahora podemos reproducir la definición de un núcleo de subsecuencia de cadena ^{[ 1 ]} sobre cadenas sobre un alfabeto.${\displaystyle \Sigma }$En términos de coordenadas, el mapeo se define de la siguiente manera:

${\displaystyle \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{array}}\right.}$

El${\displaystyle \mathbf {i} }$son multiíndices y${\displaystyle u}$es una cadena de longitud${\displaystyle n}$: las subsecuencias pueden aparecer de forma no contigua, pero los huecos se penalizan. El índice múltiple${\displaystyle \mathbf {i} }$da las posiciones de los caracteres coincidentes${\displaystyle u}$en${\displaystyle s}$.${\displaystyle l(\mathbf {i} )}$es la diferencia entre la primera y la última entrada en${\displaystyle \mathbf {i} }$, es decir: qué tan separados en${\displaystyle s}$la coincidencia de subsecuencia${\displaystyle u}$es. El parámetro${\displaystyle \lambda }$puede establecerse en cualquier valor entre${\displaystyle 0}$(no se permiten espacios, ya que solo${\displaystyle 0^{0}}$no lo es${\displaystyle 0}$pero${\displaystyle 1}$) y${\displaystyle 1}$ (incluso las "ocurrencias" muy extendidas tienen el mismo peso que las apariciones como una subcadena contigua, como${\displaystyle 1^{l(\mathbf {i} )}=1}$).

Para varios algoritmos relevantes, los datos ingresan al algoritmo solo en expresiones que involucran un producto interno de vectores de características, de ahí el nombre de métodos de kernel . Una consecuencia deseable de esto es que no es necesario calcular explícitamente la transformación.${\displaystyle \phi (x)}$, solo el producto interno a través del núcleo, que puede ser mucho más rápido, especialmente cuando se aproxima . ^{[ 1 ]}