Reconnaître une grammaire dans une séquence de jetons flous

J'ai des documents texte qui contiennent principalement des listes d'articles.

Chaque élément est un groupe de plusieurs jetons de différents types: prénom, nom, date de naissance, numéro de téléphone, ville, profession, etc. Un jeton est un groupe de mots.

Les articles peuvent se trouver sur plusieurs lignes.

Les éléments d'un document ont à peu près la même syntaxe de jeton, mais ils ne doivent pas nécessairement être exactement les mêmes.

Il peut s'agir de jetons plus / moins entre les Articles, ainsi qu'au sein des Articles.

FirstName LastName BirthDate PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber
Occupation UnrecognizedToken
FirstName LastName PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber
City Occupation

Le but est d'identifier la grammaire utilisée, par exemple

Occupation City

et à la fin identifier tous les articles, même s'ils ne correspondent pas exactement.

Afin de rester court et lisible, utilisons à la place certains alias A, B, C, D, ... pour désigner ces types de jetons.

par exemple

A B C
D F
A B C
D E F
F
A B C
D E E F
A C B
D E F
A B D C
D E F
A B C
D E F G

Ici, nous pouvons voir que la syntaxe Item est

A B C
D E F

car c'est celle qui correspond le mieux à la séquence.

La syntaxe (types de jetons et commandes) peut varier considérablement d'un document à l'autre. Par exemple, un autre document peut avoir cette liste

D A
D A
D
D A
B
D A

Le but est de comprendre cette syntaxe sans en avoir connaissance .

Désormais, une nouvelle ligne est également considérée comme un jeton. Un document peut alors être représenté comme une séquence de jetons à une dimension:

Ici, la séquence répétée serait A B C B parce que c'est le jeton qui crée le moins de conflits.

Complexifions un peu. Désormais, chaque jeton n'a pas de type déterminé. Dans le monde réel, nous ne sommes pas toujours sûrs à 100% du type de certains jetons. Au lieu de cela, nous lui donnons une probabilité d'avoir un certain type.

  A 0.2    A 0.0    A 0.1
  B 0.5    B 0.5    B 0.9     etc.
  C 0.0    C 0.0    C 0.0
  D 0.3    D 0.5    D 0.0

Voici un graphique abstrait de ce que je veux réaliser:

Solution considérée A: Convolution d'un patch de jetons

Cette solution consiste à appliquer une convolution avec plusieurs patchs de jetons, et à prendre celui qui crée le moins de conflits.

La partie difficile ici est de trouver des correctifs potentiels pour rouler le long de la séquence d'observation. Peu d'idées pour celle-ci, mais rien de très satisfaisant:

Inconvénient: puisqu'un modèle de Markov n'a pas de mémoire, nous perdrons les ordres de transition. Par exemple, si la séquence répétée est A B C B D, nous perdons le fait que A-> B se produit avant C-> B.

Cela semble être largement utilisé en biologie afin d'analyser les nucléobases (GTAC) dans l'ADN / ARN. Inconvénient: les arbres de suffixes sont bons pour la correspondance exacte de jetons exacts (par exemple, des caractères). Nous n'avons ni séquences exactes, ni jetons exacts.

Essayez toutes les combinaisons de toutes les tailles. Pourrait réellement fonctionner, mais prendrait un certain (long (long)) temps.

Solution considérée B: Construire un tableau des distances de Levenshtein des suffixes

L'intuition est qu'il peut exister des minima locaux de distance lors du calcul de la distance de chaque suffixe à chaque suffixe.

La fonction de distance est la distance de Levenshtein, mais nous pourrons la personnaliser à l'avenir afin de prendre en compte la probabilité d'être d'un certain type, au lieu d'avoir un type fixe pour chaque jeton.

Afin de rester simple dans cette démonstration, nous utiliserons des jetons de type fixe et utiliserons le Levenshtein classique pour calculer la distance entre les jetons.

Par exemple, ayons la séquence d'entrée ABCGDEFGH ABCDEFGH ABCDNEFGH.

Nous calculons la distance de chaque suffixe avec chaque suffixe (rogné pour être de taille égale):

for i = 0 to sequence.lengh
  for j = i to sequence.lengh
    # Create the suffixes
    suffixA = sequence.substr(i)
    suffixB = sequence.substr(j)
    # Make the suffixes the same size
    chunkLen = Math.min(suffixA.length, suffixB.length)
    suffixA = suffixA.substr(0, chunkLen)
    suffixB = suffixB.substr(0, chunkLen)
    # Compute the distance
    distance[i][j] = LevenshteinDistance(suffixA, suffixB)

On obtient par exemple le résultat suivant (le blanc est une petite distance, le noir est grand):

Maintenant, il est évident que tout suffixe par rapport à lui-même aura une distance nulle. Mais le suffixe (exactement ou partiellement) ne nous intéresse pas, nous recadrons donc cette partie.

Étant donné que les suffixes sont rognés à la même taille, la comparaison d'une chaîne longue donnera toujours une distance plus grande que la comparaison de chaînes plus petites.

Nous devons compenser cela par une pénalité douce à partir de la droite (+ P), s'éteignant linéairement vers la gauche.

Je ne sais pas encore comment choisir une bonne fonction de pénalité qui conviendrait à tous les cas.

Ici, nous appliquons une pénalité (+ P = 6) à l'extrême droite, passant à 0 vers la gauche.

Nous pouvons maintenant voir clairement 2 lignes diagonales claires émerger. Il y a 3 éléments (Item1, Item2, Item3) dans cette séquence. La ligne la plus longue représente la correspondance entre Item1 vs Item2 et Item2 vs Item3. La deuxième plus longue représente la correspondance entre Item1 et Item3.

Maintenant, je ne suis pas sûr de la meilleure façon d'exploiter ces données. Est-ce aussi simple que de prendre les lignes diagonales les plus hautes?

Supposons que ce soit le cas.

Calculons la valeur moyenne de la ligne diagonale qui commence à partir de chaque jeton. Nous pouvons voir le résultat sur l'image suivante (le vecteur sous la matrice):

Il existe clairement 3 minima locaux, qui correspondent au début de chaque élément. Semble fantastique!

Ajoutons maintenant quelques imperfections supplémentaires dans la séquence: ABCGDEFGH ABCDEFGH TROLL ABCDEFGH

De toute évidence maintenant, notre vecteur de moyennes diagonales est foiré, et nous ne pouvons plus l'exploiter ...

Mon hypothèse est que cela pourrait être résolu par une fonction de distance personnalisée (au lieu de Levenshtein), où l'insertion d'un bloc entier pourrait ne pas être autant pénalisée. C'est de cela que je ne suis pas sûr.

Conclusion

Aucune des solutions explorées basées sur la convolution ne semble correspondre à notre problème.

La solution basée sur la distance de Levenshtein semble prometteuse, en particulier parce qu'elle est compatible avec les jetons de type basé sur les probabilités. Mais je ne sais pas encore comment en exploiter les résultats.

Je serais très reconnaissant si vous avez de l'expérience dans un domaine connexe et quelques bonnes astuces à nous donner, ou d'autres techniques à explorer. Merci beaucoup d'avance.

Vous voudrez peut-être jeter un œil aux modèles de Markov cachés ou aux grammaires stochastiques sans contexte . Ils peuvent tous deux être utilisés pour modéliser des grammaires et les déduire des données.

Par exemple, les deux ont été utilisés dans le passé pour modéliser des séquences génétiques, par exemple ceci et cela .