Um parser probabilístico para o português brasileiro: um estudo exploratório ^{⋆}

Andréia Gentil Bonfante Maria das Graças Volpe Nunes

Instituto de Ciências Matemáticas e de Computação Departamento de Ciências de Computação e Estatística USP São Carlos

Resumo Este trabalho descreve os passos iniciais de uma investigação de modelos estatísticos para a construção de um analisador sintático (parser) para o português brasileiro. São considerados alguns modelos bem sucedidos e apresentadas algumas propostas iniciais que serão exploradas.

1 Introdução

O grande desafio para muitos pesquisadores na área de Processamento Automático de Línguas Naturais (PLN) tem sido o de conseguir progressos constantes na construção de análisadores sintáticos (parsers). A função desempenhada por um parser é a de receber como entrada uma sentença marcada com rótulos morfossintáticos e produzir a partir daí uma estrutura hierarquizada dos elementos sintáticos encontrados (árvore sintática), ou seja, os constituintes formadores da sentença. Na aplicação de revisão gramatical automática, o parser tem papel nuclear que, uma vez desempenhado corretamente, a revisão se beneficia com um número menor de falsos positivos e falsos negativos. Para o tratamento da língua portuguesa escrita no Brasil, destaca-se o revisor gramatical ReGra [MH1], construído pela equipe do NILC (Núcleo Interinstitucional de Lingüística Computacional) ^{1}, com sede no Instituto de Ciências Matemáticas e de Computação da USP/São Carlos. Após vários anos no mercado como parte dos produtos RLP/Itautec e MS Office 2000, somente agora o módulo de parser do ReGra foi isolado para um aprimoramento in loco. O revisor como um todo e o módulo de parser em particular têm sido desenvolvidos através de especificação manual das regras (hoje com mais de 1000 regras sintáticas), o que torna esse processo bastante custoso, especialmente quanto ao esforço humano para a especificação de tais regras. Nesse contexto se insere nosso trabalho: procurar meios alternativos para o processo de revisão verificar seu comportamento relativamente o do ReGra.

⋆ Apoio: CNPQ, Finep, Itautec 1 Num convênio com a empresa Itautec/Philco, desde 1993.

O trabalho aqui proposto focaliza somente o processo parsing, que tem sido um domínio freqüente nas aplicações de métodos estatísticos. Pesquisas atuais mostram que o parsing pode ser realizado com abordagens que se utilizam do aprendizado de exemplos já prontos (no caso do parser, pares de sentenças/árvores-sintáticas) para realizar análises em exemplos novos. Segundo [Co1], as abordagens probabilísticas para problemas de aprendizado neste contexto consistem basicamente no aprendizado de uma função Score(x, y) (uma probabilidade condicional P (y|x) ou uma probabilidade conjunta P (x, y)) que mapeia o conjunto sentenças X no conjunto de árvores sintáticas (Y). A partir da especificação de Score, pode-se definir uma função f(x) como o membro mais desejável, ou seja, o de maior probabilidade dentro do conjunto Y, cuja distribuição de probabilidade será:

f(x) = argmax_{y∈Y} Score(x, y)  (1)

Onde argmax é maior saída encontrada para aquela entrada, ou seja, a árvore sintática de maior probabilidade (T_{best}) para a sentença (S).

A principal dificuldade da modelagem probabilística consiste na complexidade do espaço de eventos. Em problemas de PLN, tanto o espaço de entrada X quanto o espaço de saída Y podem ser de dimensão muito alta, com membros desses sendo estruturas complexas, como estruturas de árvores. Por exemplo, para o problema de parsing, o espaço de eventos é o conjunto de todos os pares sentença/arvore-sintática, sabidamente muito grande. A concentração da pesquisa estatística consiste na busca de uma distribuição que use um número finito de parâmetros, tantos quantos forem necessários para um modelo confiável.

2 Modelos Estatísticos

Existem várias estratégias para modelar eventos estruturados: a idéia é associar probabilidades a sub-estruturas dentro de eventos individuais como as regras no problema de parsing. A especificação dos parâmetros é um dos passos mais importantes para a modelagem estatística. O método Maximum-Likelihood Estimation(MLE) [BD1] dá boas condições para que os parâmetros sejam estimados.

Definir modelos que satisfaçam esses critérios para espaços de eventos complexos é bastante difícil. Algumas técnicas podem ser aplicadas a esse tipo de problema: modelos de Markov para probabilidades sobre seqüências; Hidden Markov Models (HMM) de probabilidades sobre pares seqüência/estado (como no Part-Of-Speech tagging); Probabilistic Context-Free Grammars para probabilidades sobre pares sentença/árvore; e ainda modelos history-based, uma espécie de generalização dos modelos anteriores. Descrevemos a seguir algumas dessas técnicas.

Gramáticas Livres de Contexto Probabilísticas (PCFGs) O uso das PCFGs apresenta muitas vantagens. De um lado, elas são uma extensão estatística das gramáticas livres de contexto e, assim, os algoritmos de parsing para essas últimas também podem ser usados para aquelas (em particular, todas as análises possíveis podem ser encontradas em tempo O(n^{3}) onde n é o tamanho da sentença). De outro lado, as PCFGs por si só não produzem bons parsers estatísticos, e não são muito usadas, pois os analisadores sintáticos resultantes, usando o método MLE, conseguem médias de 75% de precisão/recall^{2} e somente são bons para gramáticas que consideram apenas rótulos morfossintáticos das palavras.

O ponto crucial a ser observado é que a utilidade de uma parametrização particular pode ser investigada através de sua habilidade de discriminar entre diferentes árvores. Muitas vezes a diferença na escolha de determinada árvore pode estar em regras que não fazem menção à informação lexical. Um problema a ser destacado é que as PCFGs mais simples pecam no sentido de que ignoram a informação lexical quando optam por decisões de ligação (attachment), uma vez que esse ponto afeta no modo como a pontuação das regras é calculada. Mudanças nos parsers mais recentes trazem o conceito de parser lexicalizado, que alcançam médias de 87-88% de taxas de precisão/recall contra o 75% observados anteriormente.

O cálculo das estatísticas sobre as palavras traz consigo o problema dos dados esparsos. Algumas palavras nunca vistas antes prejudicam o bom funcionamento do modelo. Para minimizar as combinações a serem consideradas, a idéia chave é que cada constituinte tem um núcleo (head), que é o item lexical mais importante. Por exemplo, o núcleo de um sintagma nominal é o nome principal, que na maioria das vezes é o que aparece mais à direita. Mais geralmente, os núcleos são computados de uma maneira bottom-up e o núcleo de um constituinte c é uma função determinística da regra usada para expandir c. Assim, se restringirmos as estatísticas a pares de palavras, as melhores relacionariam os núcleos dos constituintes aos núcleos de todos os seus subconstituintes.

Os parsers estatísticos lexicalizados coletam basicamente dois tipos de estatísticas. Um relaciona o núcleo de um constituinte à regra r usada para expandilo, que é denotado por P (r|h), e o outro relaciona o núcleo m de um constituinte ao núcleo h de um subconstituinte, que é denotado por P (h|m, t).

Outro problema surge com relação à ausência de certas regras. Isso pode resultar em falha no processo de análise por não haver regra que represente tal problema no conjunto de regras a serem seguidas. Uma alternativa que se tem usado são as Markov Grammars(MGs) [Ma1] [Co2]. Ao invés de armazenar regras explícitas, uma MG armazena probabilidades que as habilitam a inventar regras durante o processamento. Por exemplo, para criar regras sobre sintagmas nominais, deve-se saber que há probabilidade de um sintagma nominal começar com um determinante (nesse caso, alta) ou então com preposição (nesse caso, baixa). E assim, sucessivamente, com os demais constituintes formadores de tal sintagma. Podemos então derivar a probabilidade P (t_{i}|l, t_{i−1}), onde t_{i−1} é o constituinte anterior e l é o tipo do constituinte que se está expandindo. Por exemplo, podemos capturar essa idéia para calcular a probabilidade de um adjetivo aparecer depois de um determinante no interior de um sintagma nominal.

2 Medidas usadas para observação da performance do parser proposto em [Bl2]

Assim, a probabilidade de uma regra passa a ser o produto das probabilidades de seus componentes individuais:

P (r|l) = ∏_{t_{i}∈r} P (t_{i}|l, t_{i−1})  (2)

Para parsers que usam as MGs não se calcula P (r|h) uma vez que as regras não são explícitas. Ao invés disso, essa probabilidade é distribuída , como se faz na equação anterior, exceto que agora as probabilidades são condicionadas ao núcleo h do constituinte. No resto, segue o mesmo esquema das regras. Assim, a equação P (s, π) = ∏_{c} P (r(c)) (onde s é a sentença, π é uma análise sintática particular de s, c varia sobre os constituintes π e r(c) é a regra usada para expandir c) passa a ser escrita em parser lexicalizado na forma:

P (s, π) = ∏_{c} P (h(c)|m(c)).P (r(c)|h(c))  (3)

Charniak, em [Ch3] mostra que conforme os eventos condicionais vão ficando mais específicos as probabilidades aumentam.

Outros trabalhos usam além dos núcleos lexicais o tipo do pai do elemento atual [Ch2], informação sobre o contexto imediatamente à esquerda de um constituinte [Co2], ou ainda uma grande variedade de informações condicionais, usando, por exemplo, o esquema de aprendizado por árvore de decisão para selecionar aqueles que parecem mais significativos [Ma1].

History-Based Models Alguns modelos mais gerais foram introduzidos em [BJ1]. Chamados de history-based models, tiveram vários adeptos, como [JL1], [Ma1], [Ra2], [Ra1], e foram aplicados a problemas de tagging e parsing. Esses modelos se caracterizam por duas diferenças em relação às PCFGs simples. Primeiro, a representação da árvore sintática foi enriquecida de duas formas: os rótulos não terminais foram estendidos para incluir informações como ítens lexicais (núcleos dos sintagmas), ou categorias semânticas; e o contexto a ser condicionado foi estendido para procurar por todas as estruturas já construídas, não somente o não terminal sendo expandido, como acontece com as PCFGs. Segundo, métodos mais poderosos de aprendizado de máquina, como árvores de decisão, foram usados para estimar os parâmetros. A idéia básica é expandir as características condicionais e o contexto de forma que incluam informações de desambiguização e, então, usar árvores de decisão para aprender exatamente que características ou combinação de características foram importantes para a análise sintática. Os resultados ganham uma melhora considerável (médias de 84% de precisão/recall) em relação aos experimentos com PCFGs, uma vez que o modelo tem parâmetros fortemente condicionados à informação lexical, o que ajuda na melhora de desempenho.

A idéia é definir um mapeamento um-para-um que mapeia cada membro X × Y numa seqüência de decisões < d_{1}, d_{2}...d_{n} >. A probabilidade conjunta de um membro (x, y) de X × Y é então descrita usando-se a cadeia de regras de probabilidade:

P (x, y) = P (< d_{1}, d_{2}...d_{n} >) = ∏_{i=1...n} P (d_{i}|d_{1}...d_{i−1})  (4)

Sendo esse contexto condicional para cada d_{i}, a n-upla < d_{1}, d_{2}...d_{n} > é referida como a história do modelo. O mapeamento entre os eventos X × Y e as seqüências de decisões é alcançado definindo-se um programa estocástico que gera eventos em X × Y, e assim faz escolhas entre decisões alternativas de acordo com alguma distribuição de probabilidade, e a probabilidade da seqüência de decisões escolhida é o produto das probabilidades das diferentes escolhas. No caso do parsing, são geradas derivações das árvores sintáticas: uma árvore é representada como uma seqüência de decisões onde cada decisão é a regra usada para expandir o não-terminal daquele ponto da derivação.

Maximum Entropy Inspired Model (MEI) Charniak, em [Ch1], propõe um parser baseado no modelo MEI que alcança média de 90% de precisão/recall, sendo considerado uma das melhores taxas já alcançadas. A inovação proposta está no uso do modelo MEI para condicionamento e tratamento de dados esparsos que permite testar e combinar diferentes eventos condicionais. O parser é baseado num modelo gerativo probabilístico. A diferença desse modelo está em como ele computa P (π) no intuito de retornar a máxima probabilidade para uma sentença s. O modelo atribui uma probabilidade para uma análise através de um processo top-down considerando cada constituinte c em π e atribuindo o seu pré-terminal t(c) = tag, o seu núcleo lexical h(c) e a sua expansão em constituintes e(c).

P (π) = ∏_{c∈π} P (t(c)|l(c), H(c))·P (h(c)|t(c), l(c), H(c))·P (e(c)|l(c), t(c), h(c), H(c))

(5)

Onde l(c) é o rótulo sintático de c (sintagma nominal, sintagma verbal, etc.) e H(c) é a história, ou contexto, relevante de c, ou seja, a informação fora de c que o modelo probabilístico considera importante em determinada questão.

Para atribuir a probabilidade da expansão e de um constituinte, o autor utiliza as Markov Grammars (MGs) citadas anteriormente. Nesse esquema, uma regra PCFG tradicional pode ser vista como contendo um lado esquerdo LHS com rótulo l(c), obtido dos símbolos não terminais da gramática, e um lado direito RHS que é uma seqüência de um ou mais símbolos. A cada expansão distingue-se um dos rótulos do RHS como o símbolo que representa o núcleo do constituinte expandido (M(c)). À esquerda de m pode estar uma seqüência de um ou mais rótulos L_{i}(c), incluíndo o símbolo especial △ de terminação. Analogamente, vale para o lado direito R_{i}(c) de m.

Assim, a expansão e passa a ser:

l → △L_{m}...L_{i}MR_{1}...R_{n}  (6)

Em uma MG de ordem zero (0-order MG) cada símbolo é gerado somente considerando l, isto é, de acordo com as distribuições P (L1|l), P (M|l), P (Ri|l).

Podemos também condicionar a m rótulos gerados anteriormente obtendo assim uma gramática de ordem m. Assim, numa MG de ordem dois, L_{2} seria condicionado à L_{1} e M. No modelo completo proposto, a probabilidade de cada rótulo nas expansões é também condicionada ao material especificado anteriormente, por exemplo P (e|l, t, h, H). Assim, poderia-se usar P (L2|L1, M, l, t, h, H).

3 Trabalho em Andamento

Tendo observado as características dos modelos acima descritos, iniciamos um trabalho cujo intuito é reunir, quando possível, o que nos é útil de cada modelo, fazendo uma adequação ao desafio que temos em mão. Desafio este que se inicia no próprio corpus de sentenças analisadas (treebank) a serem utilizadas para o aprendizado, uma vez que inexiste tal conjunto para a língua portuguesa escrita no Brasil, foco deste trabalho. Para suprir tal falta, há no NILC um projeto paralelo para a construção de uma treebank para o português, conforme mostramos abaixo.

Descrição da Treebank A opção pela elaboração de uma treebank para o português surgiu da necessidade de tal material para o desenvolvimento de aplicações específicas da nossa língua. Para isso, a equipe de desenvolvimento optou por especificar análises fugindo do conceito tradicional de formação que inclui sintagmas e, no máximo, as classes gramaticais das palavras. Conforme pode ser observado na Figura 1 (um exemplar do corpus), a treebank considera, além dos sintagmas, as noções de sujeito, predicado, complementos, etc. e ainda os núcleos formadores de cada sintagma, com o aparecimento da palavra juntamente com sua classe gramatical. As linhas marcadas com os caracteres ”//”representam as regras usadas naquele momento da análise. Os constituintes entre colchetes indicam presença não obrigatória dentro da regra. Os parênteses representam a hierarquia observada dentro da estrutura. A notação de índice (i) aparece uma vez que as regras também servem para amparar o processo de concordância durante a revisão gramatical posterior.

A seguir delimitamos alguns pontos observados para o desenvolvimento do trabalho aqui proposto.

Descrição do processo de parsing em desenvolvimento O algoritmo de parsing consiste de um simples bottom-up chart parser [Al1]. A partir da treebank são extraídas as regras formadoras daquelas sentenças e então é calculada a probabilidade de cada regra, seguindo características das PCFGs, de acordo com o método MLE. A entrada para o algoritmo consiste de uma sentença com todas as palavras marcadas com rótulos morfossintáticos. Uma vez que a treebank representa também as próprias palavras, surge um problema quando a palavra que está sendo analisada inexiste nos exemplos até então observados, o que acontece freqüentemente. O problema se torna simples quando se pode identificar a mesma classe gramatical, considerando a sua probababilidade com relação às demais e os elementos que o antecedem. Uma vez não observada a ocorrência da palavra ou da classe, a idéia é utilizar modelos como as MGs para criar possíveis regras, observando a probabilidade dos elementos isolados do sintagma candidato sendo expandido. A lexicalização existente na representação da treebank abre caminho para a obtenção do núcleo dos sintagmas, uma vez que pode ser possível, através de regras determinísticas, a projeção dos núcleos para seus pais. Com as árvores sintáticas sendo geradas, o próximo passo será então o calculo do T_{best} para a sentença em particular.

Figura 1. Trecho da treebank representando a sentença A seca castiga o Nordeste

4 Considerações Finais

No estágio atual do projeto, a treebank está sendo estendida e a implementação do modelo híbrido está em sua fase final. Os resultados a serem alcançados deverão ser comparados ao parser do ReGra e também aos índices da literatura. Num momento posterior, ao parser resultante deverá ser acrescentado o módulo de revisão propriamente dita. Vale ressaltar que, quaisquer que sejam os resultados obtidos, o projeto já terá contribuído no sentido de experimentar tais métodos pela primeira vez no processamento do português brasileiro.

Referências

[Al1] Allen. J.: Natural Language Understanding. The Benjamim/Cummings Publishing Company, Inc. (1987)

[BD1] Bickel and Docksum: Mathematical Statistics: Basic Ideas and Selected Topics. Prentice Hall, Englewood Cliffs, New Jersey.(1977)

[BJ1] Black, E., Jelinek, F, Lafferty, J., Magerman, D., Mercer, R. and Roukos, S.: Towards History-Based Grammars: Using Richer Models for Probabilistic Parsing. In Proceedings of the 5^{th} DARPA Speech and Natural Language Workshop, Harriman, NY.(1992)

[Bl2] Black, E. et al.: A Procedure for Quantitatively Comparing the Syntatic Coverage of a English Grammars. In Proceedings of the February 1991 DARPA Speech and Natural Language Workshop.(1991)

[Ch1] Charniak, E.: A Maximum-Entropy-Inspired Parser In 1^{st} Meeting of the North American Chapter of the Association for Computational Linguistics, Seattle, Washington, USA. (2000).

[CC2] Charniak, E., Carroll, G., Adcock, J., Cassandra, A., Gotoh, Y., Katz, J., Littman, M., McCann, J.: Taggers for parsers In Artificial Intelligence (forthcoming)

[Ch2] Charniak, E.: Statistical parsing with a context-free grammar and word statistics In Proceedings of the Fourteenth National Conference on Artificial Intelligence, AAAI Press/MIT Press, Menlo Park (1997), 598-603.

[Ch3] Charniak, E.: Statistical techniques for natural language parsing In AI Magazine 18 4 (1997), 33-43.

[Co1] Collins, M.: Head-Driven Statistical Models for Natural Language Parsing. PhD´ s Thesis in Computer and Information Science. University of Pennsylvania. (1999)

[Co2] Collins, M.: A new statistical parser based on bigram lexical dependencies In Proceedings of the 34^{th} Annual Meeting of the ACL. (1996)

[JL1] Jelinek, F, Lafferty, J., Magerman, D., Mercer, R., Ratnaparkhi, A., and Roukos, S.: Decision Tree Parsing using a Hidden Derivation Model. In Proceedings of the 1994 Human Language Technology Workshop, 272-277.(1992)

[Ma1] Magerman, D. M.: Statistical Decision-Tree Models for Parsing. In Proceedings of the 33^{rd} Annual Meeting of the Association for Computational Linguistics, 276-283. (1995)

[MH1] Martins, R. T.; Hasegawa, R.; Nunes, M. G. V.; Montilha, G.; Oliveira Jr., O. N.: Linguistic Issues in the development of ReGra: a Grammar Checker for Brazilian Portuguese. In Natural Language Engineering, 4, 287-307, Cambridge Universtity Press. (1998)

[Ra1] Ratnaparkhi, A.: A Linear Observed Time Statistical Parser Based on Maximum Entropy Models In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, Brown University, Providence, Rhode Island. (1997)

[Ra2] Ratnaparkhi, A.: A Maximum Entropy Model for Part-of-Speech Tagging In Conference on Empirical Methods in Natural Language Processing. (1996)