Método de forma normal de Chomsky: implicações no desempenho do analisador CYK?

9

Os analisadores de gráficos podem ser implementados com base na forma normal de Chomsky ou diretamente com base nas regras de produção. Vamos, por enquanto, supor que temos um analisador de gráfico CYK que usa a forma normal de Chomsky. A binarização não está definida exclusivamente. Isso afeta o desempenho da análise do gráfico CYK. Isso pode ser explorado para melhorar o desempenho de um analisador de gráfico CYK?

fl.formal-languages parsing Kaveh
fonte
As abordagens criam gramáticas do mesmo tamanho, não criam? O CYK sempre preenche a tabela completa, portanto você pode acelerar a verificação de "Existe uma regra de ajuste?". Portanto, eu esperaria que apenas a contagem de regras tenha uma influência, não uma estrutura gramatical.
Raphael
O método usado para a binarização também afeta o tamanho da gramática, que afeta o desempenho do CYK: informatica-didactica.de/cmsmadesimple/… discute algumas alternativas ao CNF
Max

Respostas:

6

Embora a resposta óbvia seja que a complexidade fundamental não pode mudar, pode haver algoritmos melhores ou piores para analisar as strings que você realmente encontrará. No entanto, parece que o problema é menos a frequência relativa de produções gramaticais individuais (os A's, B's e Cs na questão) e mais uma questão do beco sem saída analisado que uma binarização versus outra pode produzir.

Com um pouco de pesquisa, encontrei Better Binarization para o CKY Parsing (Song, Ding e Lin, EMNLP 2008), que parece concluir definitivamente que você pode escolher uma binarização "melhor" ou "pior" em relação às strings que você realmente espera ter que analisar. O nome deles para o "beco sem saída" que se espera minimizar na prática parece ser constituintes incompletos , e há um bom exemplo na primeira página.

Rob Simmons
fonte
Considere a gramática, incluindo produções (S -> ABC) (T -> ABD). Se "BC" for sempre precedido por "A", mas "AB" ocasionalmente não for seguido por "C", haverá menos becos sem saída se você combinar B e C, e a frequência relativa for irrelevante. Seu argumento sobre "poucos" e "muitos" faz sentido se as palavras aparecerem aleatoriamente, mas o que eu acho que Song, Ding e Lin estão fazendo é explorar a frequência ngram, que é um pouco mais sofisticada. Eles também apontam que, no meu exemplo, você ainda pode ganhar com a binarização "AB" explorando o compartilhamento!
Rob Simmons
4

Na verdade, a forma normal de Chomsky (CNF) não é necessária para executar o CYK, apenas a binarização. A binarização é essencial para preservar a complexidade cúbica da análise, embora essencial apenas em relação aos não terminais (NT). Porém, se você tiver regras incluindo apenas 2 não terminais e alguns terminais, o algoritmo CYK se tornará mais complexo para programar e explicar.

Como você diz, existem muitas maneiras de fazer a binarização. Alguns produzirão gramáticas menores que outros. Por exemplo

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

pode ser binarizado como

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

economizando, assim, uma regra por fatoração, que pode economizar na computação e no tamanho do resultado.

Mas com outras regras, você pode querer fatorar o final das regras e não o começo.

Não estou familiarizado com o trabalho de Song, Ding e Lin , citado pela resposta de Rob Simmons . A idéia é interessante, mas eu me pergunto até que ponto ela pode ser comparada a outras maneiras de otimizar a computação. Eu não temo muito.

O ponto é que analisar os problemas apenas em relação a um algoritmo CKY puro parece um exercício acadêmico, mas caro, uma vez que existem outros tipos de otimização que podem melhorar significativamente a eliminação de análises de becos sem saída.

O CYK é apenas uma das variações mais simples de uma família de algoritmos que são todos criados no mesmo modelo de programação dinâmica, aparentemente. Estou dizendo aparentemente porque a versão mais simples desses algoritmos não é conhecida como programação dinâmica, mas como produto cruzado. É a antiga construção de uma gramática G de CF que gera a interseção entre a linguagem da gramática F e a linguagem regular de uma FSA A., devido a Bar Hillel, Perles e Shamir (1961) , como observou Lang em 1995 .

Todo analisador de gráfico ou analisador de CF geral baseado em programação dinâmica pode ser visto como uma variante "otimizada" dessa construção de produtos cruzados, sendo a otimização usada principalmente para evitar cálculos inúteis do analisador. Mas o problema é sutil, pois evitar a computação inútil pode resultar na duplicação de outras úteis, o que pode ser pior.

Sendo de baixo para cima, o algoritmo CKY produz cálculos inúteis de análises parciais que não podem derivar do axioma da gramática.

Algoritmos como o analisador GLR (para citar um dos mais conhecidos, embora tenha sido publicada uma versão defeituosa), possuem algum conhecimento de cima para baixo que evitará muitos desses cálculos inúteis, possivelmente a custo. E existem muitas outras variantes com comportamento diferente em relação à economia em cálculos inúteis.

É com essas estratégias de otimização em mente que a estratégia de binarização deve ser analisada. Qual é o objetivo de otimizar o que pode ser um problema menor e ignorar técnicas mais poderosas.

A otimização do processo de análise também está intimamente ligada à "qualidade" da estrutura de análise obtida, que representa todos os possíveis análises e é frequentemente chamada de floresta de análise (compartilhada). Eu discuto isso em outra resposta .

Algumas dessas questões são discutidas na literatura. Por exemplo, por Billot e Lang analisam alguns aspectos da binarização com relação às estratégias de análise.

babou
fonte