Analizadores Sintacticos : Dependency Parsing

Analizadores Sintacticos : Dependecy Parsing

Un Analizador Sintactico es un componente de Software cuya entrada es una oracion especificada en un lenguaje (formal o no formal) y como salida arroja una estructura que representa las relaciones entre los componentes de la oracion de entrada.

En Ciencias de la computacion normalmente un parser o analizador sintactico es un sub-componente de los compiladores de los lenguajes de programacion.

Este componente se encarga de asegurarse que las intrucciones esten definidas correctamente segun una gramatica.

Adicionalmente el analizador sintactico retorna una estructura de datos, usualmente un arbol que establece relaciones entre los componentes de la oracion de entrada, usualmente este arbol es usado posteriormente por un analizador semantico que se encarga de 'traducir' el significado de una oracion a lenguaje de maquina.

 Los lenguajes de programacion se consideran lenguajes formales y parsearlos es, digamos, un problema resuelto.

Parsing en Procesamiento de Lenguaje Natural

En el procesamiento de Lenguaje Natural existen componentes de software que analizan sintacticamente una oracion. Sin embargo en el contexto de lenguajes no formales el reto es mas complicado, existen una gran cantidad de variaciones, y posibilidades para expresar ideas, de manera correcta.
A nivel Linguistico existen muchas discusiones en las que se debaten como saber si algo es gramatical o no, la mejor respuesta al momento es: preguntele a un nativo de ese idioma si una frase es gramatical o no.

A nivel de Lenguaje Natural existen algoritmos de parseo muy conocidos como es el Algoritmo de CYK(Cocke–Younger–Kasami),  este algoritmo recibe una gramatica libre de contexto que especifica las reglas para formar oraciones correctas en un lenguaje (por ejemplo: espaniol, ingles...etc) y apartir de estas reglas es capaz de establecer : 

• Si una oracion  es correcta o no con respecto a la gramatica
• En caso de ser una oracion correcta construye un arbol de derivacion sintactica. Es decir un arbol en el cual se especifica la relacion entre los componentes de la oracion con respecto a la gramatica especificada

El arbol en la imagen representa la salida de un analizador sintactico para la oracion "john ha limpiado la impresora". 

NP= Noun Phrase (frase Nominal)
Aux=Verbo Auxiliar
VP=Verb Phrase (Frase Verbal)
Det =Determiner = Determinante
N=Noun=Sustantivo

Este arbol fue establecido a una gramatica que define cada uno de los componentes anteriormente mencionados. Las gramaticas en este caso CFG( context free grammar) usualmente se escriben en notacion BNF.
En esta gramatica almenos deberia existir una regla que diga por ejemplo que:

S=NP AUX VP
Npr= John
N=impresora
NP=Npr | DET N
...

Para poder generar este tipo de arboles sintacticos se necesita de un experto, seguramente un linguista que pueda especificar las reglas del lenguaje que se desea modelar. Ello puede ser un trabajo muy arduo y complicado, se necesitan muchas reglas para poder capturar la esencia de un lenguaje.

Dada la dificultad mencionada se empezo a usar aprendizaje de maquina para construir analizadores sintacticos que puedan aprender en base a un conjunto de ejemplos con arboles de parseo.
De esta forma no se necesita de la especificacion de miles de reglas para cosntruir un analizador que arroje resultados medianamente buenos.

Dependency Parsing 

El analisis sintactico que mencione en la seccion anterior genera arboles que establecen la relacion entre los constituyentes linguisticos de una oracion, es decir establece cual es la verbo de una oracion, y atraves de la construccion del arbol establece cual es posible sujeto y objeto de una oracion.

Este tipo de parseo resulta no solo computacionalmente caro (la complejidad de CYK(O(N^3)) ) si no que ademas el resultado es dificil de usar en las aplicaciones.

Los analizadores sintacticos nacieron de  la necesidad de tener un analizador sintactico que sea computacionalmente mas 'barato' y cuyos resultados sean mas faciles de usar a nivel aplicativo.

Un analizador sintactico retorna como salida un Grafo dirigido no ciclico, este grafo recibe el nombre de grafo de dependencias.

En este grafo las palabras corresponden a Nodos y las aristas corresponden a relaciones entre palabras.

Cada arista del grafo tiene una etiqueta que identifica la relacion entre las dos palabras.

Ejemplo:

En este ejemplo 'Subj' significa que la relacion entre john y hit, es la de 'sujeto'.

Y que 'the' es el determinante de 'Ball'.

Es una estructura mucho mas simple que la de un arbol de constituyentes (La imagen del primer ejemplo) porque es una estructura mas facil de procesar computacionalmente hablando, pues no contiene otros constituyentes anidados como es el caso del primer ejemplo.

El parseo por dependencias se usa en una gran cantidad de aplicaciones, por ejemplo en extraccion de informacion para identificar cuales son los objetos asociados a una relacion, extraccion de entidades...

Existen dos implementaciones de Analizadores sintacticos muy famosas, el MaltParser  y el MSTParser.

MaltParser
Web: http://www.maltparser.org/

El MaltParser funciona usando un algoritmo basado en transiciones.

Basicamente tiene una serie de estados y un clasificador basado en ejemplos es capaz de determinar para cada caso en particular que estado es el mas adecuado para llegar a un grafo de dependencias correcto.

Para la toma de esta desicion el clasificador entrenado toma en cuenta que tipo es la palabra que actualemtne esta analizando, que otras palabras se encuentan alrededor, que otras relaciones ha identificado al momento.

El Maltparser ha arrojado en sus experimentos buenos resultados con lenguajes cuyo orden es menos flexible por ejemplo: chino, ingles, espaniol.

Para lenguajes donde el orden es flexible Mlatparser tiene problemas , es el caso de turco y checo por ejemplo.

Lo anterior se debe a que el MaltParser asume ciertas restricciones sobre los grafos de dependencias, estas restricciones no le permiten manejar cierta cantidad de construcciones que son mas comunes en lenguajes cuyo orden es mas flexible.

MSTParser
Web: http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html

MST(Maximum Spanning Tree)

Este Constructor de Analizadores Sintactico aprende al igual que el Malt apartir de una serie de ejemplos parseados.

Apartir de esos ejemplos el MSTParser es capaz de calcular una funcion que dado un grafo evalua que tan probable es que ese grafo sea correcto. Apartir de esa funcion esta estrategia busca dada una oracion, el grafo para esa oracion cuyo valor  es el maximo.

El MST es en otras palabras un problema de optimizacion donde se busca el grafo con mayor peso posible segun una funcion de peso.

Comparacion

Ambos Malt y MST tienen puntajes excelentes de porencima del 80% analizando sintacticamente diferentes lenguajes.

El MaltParser usa un algoritmo que es Voraz (Greedy) para cada estado dentro de su procesamiento escogera aquel que parezca de momento el mas adecuado. En contraste el MSTParser busca dentro todo el espacio de posibles grafos, cual seria la combinacion mas apropiada para obtener el grafo mas probable.

Ambos tienen sus ventajas y desventajas. Por ejemplo el MaltParser es capaz de capturar con mejor rendimiento construcciones particulares, esto con el costo que un error sera propagado para el resto de las desiciones a tomar.

Algunos Papers han propuesto la union de ambos metodos, como es el caso de: Integrando MST y MALT

Material Sobre el tema: Diapositivas de una mis presentaciones acerca del tema en un Seminario de mi maestria.