Análise de Constituintes e Livre de Contexto

Cálculo da árvore de estrutura frasal de uma sentença usando gramáticas livres de contexto, algoritmos de programação dinâmica como CKY e Earley, e gramáticas probabilísticas que resolvem ambiguidades.

Definition

A análise de constituintes atribui uma árvore de estrutura frasal aninhada a uma sentença de acordo com uma gramática livre de contexto, tipicamente selecionando a árvore mais provável sob uma gramática probabilística.

Scope

Abrange a análise sintática com gramáticas livres de contexto: os algoritmos CKY e Earley, a forma normal de Chomsky, gramáticas probabilísticas livres de contexto e seus refinamentos lexicalizados, e analisadores estatísticos treinados em treebanks. Aborda a resolução de ambiguidades e a avaliação de analisadores. Representações de dependência e formalismos não livres de contexto são tratados em tópicos relacionados.

Core questions

• Como o algoritmo CKY analisa uma sentença em tempo cúbico?
• Por que as gramáticas frequentemente precisam ser convertidas para a forma normal de Chomsky primeiro?
• Como as gramáticas probabilísticas e lexicalizadas melhoram a desambiguação?
• Como a precisão do analisador é medida em relação a um treebank?

Key concepts

• gramática livre de contexto
• algoritmo CKY
• algoritmo Earley
• forma normal de Chomsky
• gramática probabilística livre de contexto
• lexicalização
• árvore de análise
• treebank

Key theories

Análise sintática por programação dinâmica

Os algoritmos CKY e Earley calculam todas as análises em tempo polinomial preenchendo uma tabela de subconstituintes, evitando a explosão exponencial da busca ingênua.

Análise probabilística lexicalizada

Condicionar as probabilidades das regras em palavras-chave melhora substancialmente a precisão da análise ao capturar preferências lexicais ausentes nas PCFGs simples.

History

O algoritmo CKY (década de 1960) e o algoritmo de Earley de 1970 proporcionaram reconhecimento eficiente livre de contexto. Com o Penn Treebank, analisadores probabilísticos e, posteriormente, lexicalizados de Collins e Charniak alcançaram alta precisão no final da década de 1990, definindo a era da análise estatística antes dos modelos neurais.

Debates

Quanta lexicalização é necessária?

Analisadores lexicalizados são precisos, mas esparsos; o debate girava em torno de se as PCFGs não lexicalizadas com divisão de estado cuidadosa poderiam igualá-los, o que trabalhos posteriores mostraram ser parcialmente possível.

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

O que é uma 'chart' em análise sintática?

Uma 'chart' é uma tabela que armazena cada constituinte parcial encontrado em cada extensão da sentença, de modo que subestruturas compartilhadas são calculadas uma vez e reutilizadas, resultando em análise em tempo polinomial.