Reconhecer uma gramática em uma sequência de tokens difusos

Tenho documentos de texto que contêm principalmente listas de itens.

Cada item é um grupo de vários tokens de diferentes tipos: nome, sobrenome, data de nascimento, número de telefone, cidade, ocupação etc. Um token é um grupo de palavras.

Os itens podem estar em várias linhas.

Os itens de um documento têm aproximadamente a mesma sintaxe de token, mas não precisam necessariamente ser exatamente iguais.

Eles podem ser mais ou menos tokens entre os itens e também dentro dos itens.

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

O objetivo é identificar a gramática usada, por exemplo

Occupation City

e, no final, identifique todos os itens, mesmo que eles não correspondam exatamente.

Para ficarmos curtos e legíveis, vamos usar alguns apelidos A, B, C, D, ... para designar esses tipos de token.

por exemplo

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

Aqui podemos ver que a sintaxe do item é

A B C
D E F

porque é o que melhor combina com a sequência.

A sintaxe (tipos e pedidos de token) pode variar muito de um documento para outro. por exemplo, outro documento pode ter essa lista

D A
D A
D
D A
B
D A

O objetivo é descobrir essa sintaxe sem o conhecimento prévio dela .

A partir de agora, uma nova linha também é considerada um token. Um documento pode ser representado como uma sequência unidimensional de tokens:

Aqui a sequência repetida seria A B C Bporque é o token que cria o mínimo de conflitos.

Vamos complexar um pouco. A partir de agora, cada token não possui um tipo determinado. No mundo real, nem sempre temos 100% de certeza de algum tipo de token. Em vez disso, damos a probabilidade de ter um determinado tipo.

  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

Aqui está um gráfico abstrato do que eu quero alcançar:

Solução considerada A: Convolução de um patch de tokens

Essa solução consiste em aplicar uma convolução com várias correções de tokens e escolher a que cria menos conflitos.

A parte difícil aqui é encontrar patches em potencial para rolar ao longo da sequência de observação. Poucas idéias para essa, mas nada muito satisfatório:

Desvantagem: como um modelo de Markov não tem memória, perderemos as ordens de transição. Por exemplo, se a sequência repetida for A B C B D, perdemos o fato de que A-> B ocorre antes de C-> B.

Isso parece ser amplamente utilizado em biologia, a fim de analisar nucleobases (GTAC) em DNA / RNA. Desvantagem: As árvores com sufixo são boas para a correspondência exata de tokens exatos (por exemplo, caracteres). Não temos sequências exatas nem tokens exatos.

Experimente todas as combinações de todos os tamanhos. Poderia realmente funcionar, mas levaria algum tempo (longo).

Solução considerada B: Construa uma tabela de distâncias de sufixos de Levenshtein

A intuição é que podem existir alguns mínimos locais de distância ao calcular a distância de cada sufixo a cada sufixo.

A função de distância é a distância de Levenshtein, mas poderemos personalizá-la no futuro para levar em consideração a probabilidade de ser de certos tipos, em vez de ter um tipo fixo para cada token.

Para permanecer simples nessa demonstração, usaremos tokens de tipo fixo e usaremos o Levenshtein clássico para calcular a distância entre os tokens.

por exemplo, vamos ter a sequência de entrada ABCGDEFGH ABCDEFGH ABCDNEFGH.

Calculamos a distância de cada sufixo com cada sufixo (cortado para ter o mesmo tamanho):

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)

Obtemos, por exemplo, o seguinte resultado (branco é pequena distância, preto é grande):

Agora, é óbvio que qualquer sufixo comparado a si mesmo terá uma distância nula. Mas não estamos interessados ​​no sufixo (exatamente ou parcialmente) se correspondendo, então cortamos essa parte.

Como os sufixos são cortados com o mesmo tamanho, a comparação de cadeias longas sempre produzirá uma distância maior do que a comparação de cadeias menores.

Precisamos compensar isso com uma penalidade suave, começando da direita (+ P), diminuindo linearmente para a esquerda.

Ainda não tenho certeza de como escolher uma boa função de penalidade que sirva para todos os casos.

Aqui aplicamos uma penalidade (+ P = 6) na extrema direita, diminuindo para 0 à esquerda.

Agora podemos ver claramente duas linhas diagonais claras emergindo. Existem 3 itens (Item1, Item2, Item3) nessa sequência. A linha mais longa representa a correspondência entre Item1 x Item2 e Item2 x Item3. O segundo mais longo representa a correspondência entre o Item1 e o Item3.

Agora não tenho certeza da melhor maneira de explorar esses dados. É tão simples quanto tirar as linhas diagonais mais altas?

Vamos assumir que é.

Vamos calcular o valor médio da linha diagonal que começa em cada token. Podemos ver o resultado na figura a seguir (o vetor abaixo da matriz):

Existem claramente 3 mínimos locais, que correspondem ao início de cada item. Parece fantastico!

Agora vamos adicionar mais algumas imperfeições na sequência: ABCGDEFGH ABCDEFGH TROLL ABCDEFGH

Claramente agora, nosso vetor de médias diagonais está confuso e não podemos mais explorá-lo ...

Minha suposição é que isso poderia ser resolvido por uma função de distância personalizada (em vez de Levenshtein), onde a inserção de um bloco inteiro pode não ser muito penalizada. É disso que não tenho certeza.

Conclusão

Nenhuma das soluções baseadas em convolução exploradas parece se encaixar no nosso problema.

A solução baseada em distância de Levenshtein parece promissora, principalmente porque é compatível com tokens do tipo baseado em probabilidade. Mas ainda não tenho certeza de como explorar os resultados.

Ficaria muito grato se você tiver experiência em um campo relacionado e algumas boas dicas para nos dar, ou outras técnicas para explorar. Muito obrigado antecipadamente.

Você pode dar uma olhada nos modelos de Markov ocultos ou gramáticas estocásticas livres de contexto . Ambos podem ser usados ​​para modelar gramáticas e inferi-las a partir de dados.

Por exemplo, ambas foram usadas no passado para modelar sequências genéticas, por exemplo, isto e isto .