Método de forma normal de Chomsky: implicaciones del rendimiento del analizador CYK?

Los analizadores de gráficos se pueden implementar según la forma normal de Chomsky o directamente según las reglas de producción. Supongamos por el momento que tenemos un analizador gráfico CYK que usa la forma normal de Chomsky. La binarización no está definida de forma exclusiva. ¿Esto afecta el rendimiento del análisis del gráfico CYK? ¿Se puede aprovechar esto para mejorar el rendimiento de un analizador gráfico CYK?

Si bien la respuesta obvia es que la complejidad fundamental no puede cambiar, puede haber algoritmos mejores o peores para analizar las cadenas que realmente encontrará. Sin embargo, parece que el problema es menos la frecuencia relativa de las producciones gramaticales individuales (las A, B y C en la pregunta) y más un problema de los análisis de punto muerto no utilizados que puede producir una binarización versus otra.

Con un poco de búsqueda encontré una mejor binarización para el análisis CKY (Song, Ding y Lin, EMNLP 2008), que parece concluir definitivamente que puede elegir una binarización "mejor" o "peor" en relación con las cadenas que realmente espera tener que analizar. Su nombre para los "análisis de callejones sin salida" que uno esperaría minimizar en la práctica parece ser componentes incompletos , y hay un buen ejemplo en la primera página.

En realidad, la forma normal de Chomsky (CNF) no es necesaria para ejecutar CYK, solo la binarización. La binarización es esencial para preservar la complejidad cúbica del análisis, aunque es esencial solo con respecto a los no terminales (NT). Pero luego, si tiene reglas que incluyen solo 2 no terminales y algunos terminales, el algoritmo CYK se vuelve más complejo de programar y explicar.

Como usted dice, hay muchas formas de hacer binarización. Algunos producirán gramáticas más pequeñas que otras. Por ejemplo

X -> B C D
Y -> B C E 

se puede binarizar como

X -> Z D
Y -> Z E
Z -> B C

guardando así una regla por factorización, que puede ahorrar en el cálculo y en el tamaño de su resultado.

Pero con otras reglas, es posible que desee factorizar el final de las reglas en lugar del principio.

No estoy familiarizado con el trabajo de Song, Ding y Lin , citado por la respuesta de Rob Simmons . La idea es interesante, pero me pregunto qué tan efectiva puede ser comparada con otras formas de optimizar el cálculo. No temo tanto.

El punto es que analizar los problemas solo con respecto a un algoritmo CKY puro parece un ejercicio académico pero costoso, ya que hay otros tipos de optimización que pueden mejorar significativamente la eliminación de los análisis sin salida.

CYK es solo una de las variaciones más simples en una familia de algoritmos que, aparentemente, se basan en el mismo modelo de programación dinámica. Aparentemente digo porque la versión más simple de estos algoritmos no se conoce como programación dinámica, sino como producto cruzado. Es la vieja construcción de una gramática CF F que genera la intersección del lenguaje de la gramática CF F y el lenguaje regular de una FSA A., debido a Bar Hillel, Perles y Shamir (1961) , como lo señaló Lang en 1995 .

Todos los analizadores gráficos o analizadores CF generales basados ​​en programación dinámica pueden verse como una variante "optimizada" de esa construcción de productos cruzados, la optimización se utiliza principalmente para evitar cálculos inútiles del analizador. Pero el problema es sutil, ya que evitar el cálculo inútil puede dar lugar a la duplicación de los útiles, lo que puede ser peor.

Al ser ascendente, el algoritmo CKY produce cálculos inútiles de análisis parciales que no pueden derivarse del axioma de la gramática.

Algoritmos como el analizador GLR (por nombrar uno de los más conocidos, aunque se han publicado versiones defectuosas), tienen un conocimiento de arriba hacia abajo que evitará muchos cálculos inútiles, posiblemente a un costo. Y hay muchas otras variantes con diferentes comportamientos con respecto al ahorro en cálculos inútiles.

Es con estas estrategias de optimización en mente que se debe analizar la estrategia de binarización. ¿Cuál es el punto de optimizar lo que puede ser un problema menor e ignorar las técnicas más potentes?

La optimización del proceso de análisis también está estrechamente vinculada a la "calidad" de la estructura de análisis obtenida, que representa todos los análisis posibles, y a menudo se llama bosque de análisis (compartido). Discuto eso en otra respuesta .

Algunos de estos temas se discuten en la literatura. Por ejemplo, Billot y Lang analizan algunos aspectos de la binarización con respecto a las estrategias de análisis.