Constitución y Análisis Sintáctico Libre de Contexto
Cálculo del árbol de estructura de frases de una oración utilizando gramáticas libres de contexto, algoritmos de programación dinámica como CKY y Earley, y gramáticas probabilísticas que resuelven la ambigüedad.
Definition
El análisis sintáctico de constituyentes asigna un árbol de estructura de frases anidado a una oración de acuerdo con una gramática libre de contexto, seleccionando típicamente el árbol más probable bajo una gramática probabilística.
Scope
Cubre el análisis sintáctico con gramáticas libres de contexto: los algoritmos CKY y Earley, la forma normal de Chomsky, las gramáticas probabilísticas libres de contexto y sus refinamientos lexicalizados, y los analizadores estadísticos entrenados con treebanks. Aborda la resolución de ambigüedades y la evaluación de analizadores. Las representaciones de dependencia y los formalismos no libres de contexto se tratan en temas relacionados.
Core questions
- ¿Cómo analiza el algoritmo CKY una oración en tiempo cúbico?
- ¿Por qué las gramáticas a menudo deben convertirse primero a la forma normal de Chomsky?
- ¿Cómo mejoran la desambiguación las gramáticas probabilísticas y lexicalizadas?
- ¿Cómo se mide la precisión del analizador frente a un treebank?
Key concepts
- gramática libre de contexto
- algoritmo CKY
- algoritmo Earley
- forma normal de Chomsky
- gramática probabilística libre de contexto
- lexicalización
- árbol de análisis sintáctico
- treebank
Key theories
- Análisis sintáctico por programación dinámica
- Los algoritmos CKY y Earley calculan todos los análisis en tiempo polinómico rellenando una tabla de subconstituyentes, evitando la explosión exponencial de la búsqueda ingenua.
- Análisis sintáctico probabilístico lexicalizado
- Condicionar las probabilidades de las reglas a las palabras clave mejora sustancialmente la precisión del análisis al capturar preferencias léxicas ausentes en las PCFG simples.
History
El algoritmo CKY (década de 1960) y el algoritmo de Earley de 1970 permitieron un reconocimiento eficiente libre de contexto. Con el Penn Treebank, los analizadores probabilísticos y luego lexicalizados de Collins y Charniak lograron una alta precisión a finales de la década de 1990, definiendo la era del análisis sintáctico estadístico antes de los modelos neuronales.
Debates
- ¿Cuánta lexicalización se necesita?
- Los analizadores lexicalizados son precisos pero dispersos; el debate se centró en si las PCFG no lexicalizadas con una cuidadosa división de estados podrían igualarlos, lo que trabajos posteriores demostraron que era parcialmente posible.
Key figures
- Jay Earley
- Michael Collins
- Eugene Charniak
Related topics
Seminal works
- earley1970
- collins2003
Frequently asked questions
- ¿Qué es un 'chart' en el análisis sintáctico?
- Un 'chart' es una tabla que almacena cada constituyente parcial encontrado en cada tramo de la oración, de modo que las subestructuras compartidas se calculan una vez y se reutilizan, lo que permite un análisis sintáctico en tiempo polinómico.