Procesamiento del Lenguaje Natural

Actividad: Análisis sintáctico

Objetivos

Se pretende implementar el algoritmo CKY probabilístico y aplicarlo para realizar el análisis sintáctico automático de una oración.

Pautas de elaboración

La definición de la gramática que se utilizó para la presente actividad:

G= (T, N, R, S)

Conjunto de terminales: T= {time, flies, arrow, an, like}

Conjunto de no terminales: N= {S, NP, VP, PP, Det, Nominal, Verb, Preposition, Noun}

Conjunto de reglas:

 R={

S → NP VP                                0.800

NP → time | flies | arrow                0.002

NP → Det Nominal                        0.300

NP → Nominal Nominal                0.200

Nominal → time | flies | arrow        0.002

Nominal → Nominal Noun                0.100

Nominal → Nominal PP                0.200

VP → time                                0.004

VP → flies| like                        0.008

VP → Verb NP                                0.300

VP → Verb PP                                0.200

PP → Preposition NP                        0.100

Verb → time                                0.010

Verb → flies| like                        0.020

Noun → time | flies | arrow                0.010

Det → an                                0.050

Preposition → like                        0.050

}

Axioma de la gramática: S

Se debe realizar el análisis sintáctico de la frase:

«Time flies like an arrow».

Los pasos que se deben realizar en la actividad son:

• Paso 1. Implementar en Python la estructura de la matriz de análisis sintáctico (CKY).

La implementación de la matriz sintáctico, se utilizaron las siguientes estructuras de datos:

Se tienen entidades para mantener los datos en memoria, tales como la siguiente figura:

[pic 1]

Figura de Entidades

Las clases se explican en breve:

Hoja. Mantiene el mínimo de información, Sintagma y las coordenadas de la matriz de sintagamas donde se localiza.

Nodo. Contiene un par de hojas o clases que representan la intersección o coincidencia entre los datos o sintagmas

SintagmaP. Mantiene un sintagma y la probabilidad de ocurrencia, contiene el nodo inicial

Main, crea las estructuras de los datos con diccionarios, y listas. Crea una instancia del objeto AlgoritmoCYK, y realiza la orquestación de métodos para llenar la matriz con los datos de probabilidad sintáctica en forma de diagonal.

Tree. Clase de utilería para tratar de generar un grafo con los nodos

• Paso 2. Implementar en Python la representación de la gramática proporcionada.

La representación de la gramática se modeló con la ayuda de un diccionario, tuplas y arreglos, tal como se muestra a continuación:

R = {
   "S": [(["NP", "VP"],[0.800])],
   "NP": [
          (["time", "flies", "arrow"], [0.002]),
          (["Det", "Nominal"], [0.300]),
          (["Nominal","Nominal"], [0.200])],
   "Nominal": [(["time", "flies","arrow"], [0.002]),
               (["Nominal","Noun"],[0.100]),
               (["Nominal","PP"],[0.200])],
   "VP": [
           (["time"],[0.004]),
           (["flies","like"],[0.008]),
       (["Verb", "NP"],[0.300]),
       (["Verb", "PP"], [0.200])
   ],
   "PP": [
       (["Preposition", "NP"],[0.100])
   ],
   "Verb":[
       (["time"],[0.010]),
       (["flies", "like"], [0.020])
   ],
   "Noun": [
       (["time", "flies", "arrow"], [0.010])
   ],
   "Det": [(["an"],[0.050])],
   "Preposition":[(["like"], [0.050])]
}

S = "Time flies like an arrow"

#obteniendo el conjunto de terminales a partir del axioma
T = list(S.lower().split())
# conjunto de no terminales
N = ["S", "NP", "VP", "PP", "Det", "Nominal", "Verb", "Preposition", "Noun"]

• Paso 3. Implementar en Python el algoritmo CKY probabilístico.

La implementación del algoritmo se realizó de la siguiente forma:

1. Se implementó la creación de un arreglo de arreglos bidimensional para representar en las columnas, las palabras correspondientes del axioma. Cada intersección con las filas, representan la probabilidad del sintagma con cada palabra de acuerdo a la regla gramatical
2. Recorrer en diagonal para cada elemento del axioma, verificando la regla gramatical y registrando su probabilidad
3. Para cada palabra del axioma, realizar el recorrido en diagonal para obtener las intersecciones y hacer el cálculo de las probabilidades.
4. Determinar la más alta probabilidad obtenida de los resultados
5. Mostrar el resultado

• Paso 4.

Se aplicó el algoritmo a la frase que se quiere analizar usando la matriz tabla, operando por columnas de abajo arriba y de izquierda a derecha. Para cada celda se obtuvieron los constituyentes sintácticos posibles y el cálculo de sus probabilidades.

El contenido de las celdas, está constituido por dos tipos de objeto: SintagmaP que guarda la probabilidad con la palabra del axiona y Rule, que es el resultado de aplicar la regla gramatical y la probabilidad de Viterbi obtenida, se almacenan en una lista de objetos.

[pic 2]

[pic 3]

El contenido de la celda 0,5 es la siguiente:

 [pic 4]

• Paso 5.

Se implementó el algoritmo para el cálculo de la ruta de Viterbi más probable.

Se utilizó una clase Tree para tratar de modelar el árbol, resultado de la ruta más probable, por cuestión de diseño tuvo limitaciones para presentar de forma correcta el grafo.

...