Tengo documentos de texto que contienen principalmente listas de artículos.
Cada elemento es un grupo de varios tokens de diferentes tipos: nombre, apellido, fecha de nacimiento, número de teléfono, ciudad, ocupación, etc. Un token es un grupo de palabras.
Los artículos pueden estar en varias líneas.
Los elementos de un documento tienen aproximadamente la misma sintaxis de token, pero no necesariamente tienen que ser exactamente iguales.
Pueden ser algunos tokens más / menos entre elementos, así como dentro de los elementos.
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
El objetivo es identificar la gramática utilizada, p. Ej.
Occupation City
y al final identificar todos los artículos, incluso aunque no coincidan exactamente.
Para mantenernos cortos y legibles, usemos en su lugar algunos alias A, B, C, D, ... para designar esos tipos de tokens.
p.ej
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
Aquí podemos ver que la sintaxis del elemento es
A B C
D E F
porque es el que coincide mejor con la secuencia.
La sintaxis (tipos de token y pedidos) puede variar mucho de un documento a otro. por ejemplo, otro documento puede tener esa lista
D A
D A
D
D A
B
D A
El objetivo es descubrir esa sintaxis sin un conocimiento previo de la misma .
A partir de ahora, una nueva línea también se considera un token. Un documento se puede representar como una secuencia de tokens de 1 dimensión:
Aquí la secuencia repetida sería A B C B porque es el token el que crea los menores conflictos.
Complejémoslo un poco. A partir de ahora, cada ficha no tiene un tipo determinado. En el mundo real, no siempre estamos 100% seguros del tipo de token. En cambio, le damos una probabilidad de tener un cierto 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
Aquí hay un gráfico abstracto de lo que quiero lograr:
Solución considerada A: Convolución de un parche de tokens
Esta solución consiste en aplicar una convolución con varios parches de tokens, y tomar el que crea menos conflictos.
La parte difícil aquí es encontrar posibles parches para rodar a lo largo de la secuencia de observación. Pocas ideas para esta, pero nada muy satisfactorio:
Construye un modelo de Markov de la transición entre tokensInconveniente: dado que un modelo de Markov no tiene memoria, perderemos los órdenes de transición. Por ejemplo, si la secuencia repetida es A B C B D, perdemos el hecho de que A-> B ocurre antes de C-> B.
Esto parece ser usado ampliamente en biología para analizar nucleobases (GTAC) en ADN / ARN. Inconveniente: los árboles de sufijo son buenos para la coincidencia exacta de tokens exactos (por ejemplo, personajes). No tenemos secuencias exactas ni tokens exactos.
Fuerza brutaPrueba todas las combinaciones de todos los tamaños. Realmente podría funcionar, pero tomaría un tiempo (largo (largo)).
Solución considerada B: construir una tabla de distancias de sufijos de Levenshtein
La intuición es que puede existir algunos mínimos locales de distancia cuando se calcula la distancia de cada sufijo a cada sufijo.
La función de distancia es la distancia de Levenshtein, pero podremos personalizarla en el futuro para tener en cuenta la probabilidad de ser de ciertos tipos, en lugar de tener un tipo fijo para cada ficha.
Para ser simple en esa demostración, usaremos tokens de tipo fijo y utilizaremos el clásico Levenshtein para calcular la distancia entre tokens.
Por ejemplo, tengamos la secuencia de entrada ABCGDEFGH ABCDEFGH ABCDNEFGH.
Calculamos la distancia de cada sufijo con cada sufijo (recortado para que sea del mismo tamaño):
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)
Obtenemos, por ejemplo, el siguiente resultado (el blanco es pequeña distancia, el negro es grande):
Ahora, es obvio que cualquier sufijo en comparación con sí mismo tendrá una distancia nula. Pero no nos interesa que el sufijo (exacta o parcialmente) coincida, por lo que recortamos esa parte.
Dado que los sufijos se recortan al mismo tamaño, comparar cadenas largas siempre producirá una distancia mayor que comparar cadenas más pequeñas.
Necesitamos compensar eso con una penalización suave comenzando desde la derecha (+ P), desvaneciéndose linealmente hacia la izquierda.
Todavía no estoy seguro de cómo elegir una buena función de penalización que se ajuste a todos los casos.
Aquí aplicamos una penalización (+ P = 6) en el extremo derecho, desvaneciéndonos a 0 a la izquierda.
Ahora podemos ver claramente emerger 2 líneas diagonales claras. Hay 3 elementos (Elemento1, Elemento2, Elemento3) en esa secuencia. La línea más larga representa la coincidencia entre Item1 vs Item2 y Item2 vs Item3. El segundo más largo representa la coincidencia entre Item1 vs Item3.
Ahora no estoy seguro de la mejor manera de explotar esos datos. ¿Es tan simple como tomar las líneas diagonales más altas?
Asumamos que es así.
Calculemos el valor promedio de la línea diagonal que comienza en cada token. Podemos ver el resultado en la siguiente imagen (el vector debajo de la matriz):
Claramente, hay 3 mínimos locales que coinciden con el comienzo de cada artículo. ¡Se ve fantastico!
Ahora agreguemos algunas imperfecciones más en la secuencia:
ABCGDEFGH ABCDEFGH TROLL ABCDEFGH
Claramente ahora, nuestro vector de promedios diagonales está en mal estado, y ya no podemos explotarlo ...
Mi suposición es que esto podría resolverse mediante una función de distancia personalizada (en lugar de Levenshtein), donde la inserción de un bloque completo puede no estar tan penalizada. De eso no estoy seguro.
Conclusión
Ninguna de las soluciones exploradas basadas en convolución parece ajustarse a nuestro problema.
La solución basada en la distancia de Levenshtein parece prometedora, especialmente porque es compatible con tokens de tipo basado en la probabilidad. Pero todavía no estoy seguro de cómo explotar los resultados.
Estaría muy agradecido si tiene experiencia en un campo relacionado, y un par de buenos consejos para darnos, u otras técnicas para explorar. Muchas gracias por adelantado.
fuente
Respuestas:
Es posible que desee echar un vistazo a los modelos ocultos de Markov o las gramáticas estocásticas sin contexto . Ambos pueden usarse para modelar gramáticas e inferirlas a partir de datos.
Por ejemplo, ambos se han usado en el pasado para modelar secuencias genéticas, por ejemplo, esto y esto .
fuente