Clasificación de secuencias de símbolos

Question

Digamos que tengo secuencias de símbolos que pueden tener cinco valores : A, B, C, X, Y. La longitud media de las secuencias es aproximadamente 7. Es importante que los símbolos A, B, C tengan una mayor importancia que X e Y, que puede considerarse como "cualquier cosa diferente de A, B o C".

Necesito clasificar esos datos entre dos clases: positivos y negativos. La clase positiva se compone de secuencias generalmente bien alineadas como

X X A B Y C
A B C X X
A Y A X B C X X

Observe que los ejemplos positivos tienen generalmente los símbolos A,B y C en ese orden.

Los ejemplos negativos parecen más "desordenados" como

B X A X X X X C
C A Y Y X X B

Mi primer pensamiento fue que la entropía era la clave de ese problema. Revisé varios artículos pero nada me satisfizo realmente. Así que mi pregunta es:

¿Qué características utilizaría con fines de clasificación?

Answer 1

Yo no utilizaría detectores de rasgos, sino redes neuronales recurrentes. Son muy buenas para secuencias simbólicas: por ejemplo, son capaces de reconocer lenguas sensibles al contexto.

Echa un vistazo Clasificación biológica de fonemas con redes neuronales LSTM (Graves, Schmidhuber) para obtener una explicación de cómo utilizar las RNN para la clasificación. Véase Generación de texto con redes neuronales recurrentes (Martens, Sutskever, Hinton) para una impresionante aplicación simbólica de las RNN.

Answer 2

Parece que esta pregunta está pidiendo una forma de cuantificar el sentido de las cuerdas "generalmente bien alineadas". Por supuesto, hay muchas maneras de hacerlo, pero los ejemplos y la descripción sugieren que cualquier solución cumpla dos criterios:

1.  The X's and Y's should play no role in the result.

2.  The strings in which the A, B, and C's appear in order are the most "well aligned."

Esto sugiere basar la clasificación en un editar distancia entre las subcadenas {A,B,C} o en una ordenación parcial de permutaciones de conjuntos múltiples . Para ofrecer un asesoramiento más específico, necesitaríamos más información sobre la finalidad de la ordenación de importancia prevista y sobre cómo se generan estas cadenas.

Answer 3

Los métodos de kernel (como la máquina de vectores de soporte) suelen ser bastante buenos para este tipo de problemas, ya que se pueden utilizar funciones de kernel que operan directamente sobre cadenas de símbolos de longitud variable. Algunos ejemplos son núcleo espectral (que proyecta las cadenas en un espacio de características implícito en el que cada dimensión registra el número de ocurrencias de todas las posibles subcadenas de una longitud determinada -o menos-) y la función kernel mismatch que es similar, pero el recuento de subcadenas permite un cierto número de coincidencias erróneas. También existe el alineación de secuencias kernel, que puede ser de interés.

Answer 4

¿Podemos hacerlo programáticamente? Es decir, escribiendo un código que haga lo que tú dices, por ejemplo, dando a "A x X B Y c" más importancia que a "B X X X A C". de acuerdo en que este código debe ser un poco complejo sin embargo?