Processamento de Linguagem Natural PCS5737

prof./autor Jorge Kinoshita.
Periodo: 20/09/99 a 11/12/99
local: sala B2-10
horario: 17:00h-20:00h

Programa preliminar.

1 22-09
apresentacao

historico:

linguistas: Saussure, Chomsky (teoria X-barra).

linguistica computacional: redes ATN, Prolog, gramaticas de unificacao (ex: PATR).

Caso tipico: Gramatica de unificacao + teoria X-barra.

o estado atual. Grandes avancos na Universidade da Pennsylvania (UPPEN).

TreeBank alavancou varios projetos.

http://www.cis.upenn.edu/~adwait/statnlp.html

Passos normais:

quebrar o texto em sentencas

submeter a um tagger (etiquetador)

submeter aa analise sintatica. Resolucao de ambiguidade: atribuir pesos maiores para as arvore mais provaveis, observando alguma estatistica.

fazer um processamento sobre o resultado

minha pesquisa e visao sobre a area.

2 29-09 Tagger 1: baseado em regras aprendidas : Eric Brill
As regras sao aprendidas a partir do corpus do TREEBANK.
fase de treinamento.
fase de aplicacao.

1. tagging inicial - atribui a tag mais frequente para cada palavra conhecida (que apareceu no corpus) e a tag mais provavel (olhando sufixo e primeira letra se eh maiscula ou nao) para as palavras desconhecidas.

2. correcao da tag inicial atraves de regras como: se a tag eh VBZ e a palavra anterior eh DT entao troque VBZ por NNS.

fase de treinamento.

1. regras para chutar as tags das palavras desconhecidas vendo o sufixo.

2. regras de correcao de tags. Para o treinamento o corpus eh dividido em duas partes: uma para a montagem do dicionario e outra para se inferir as regras de correcao.

3 06-10 Tagger 2: Baseado em exemplos: Daelemans
link: http://ilk.kub.nl/ em publications
Os exemplos sao colhidos da seguinte forma:
f1, f2 ,... fn classe
onde f1..fn sao as features ou caracteristicas. No caso do tagger se refere as tags das palavras anteriores e tags-compostas das palavras posteriores. A classe se refere aa tag.
A cada feature podemos atribuir um peso. Se todas tiverem o mesmo peso entao eh o modelo IB1 senao eh o IB-IG. O peso pode ser obtido atraves da analise do quanto cada feature contribui para o aumento da entropia da peso. Isto pode ser feito automaticamente.
Alem disso, Daelemans propoe que cada linha da tabela seja armazenada em uma arvore de decisao. O seu tagger tem desempenho semelhante ao do Eric Brill.

4 13-10 Tagger 3: estatistico baseado no modelo de entropia maxima
link: http://www.cis.upenn.edu/~adwait/statnlp.html : para a tese de doutorado.
Adwat Ratnaparkhi propoe um modelo de resolucao de ambiguidades que ocorrem na linguagem natural em sua tese de doutorado de 1998. Uma das aplicacoes deste modelo eh o tagger aqui analisado.
O modelo possui algumas semelhancas com o modelo baseado em exemplos do Daelemans. Para Adwat cada feature eh apenas uma funcao que devolve zero ou um. Assim, ele propoe que se crie uma tabela do tipo:
f1,f2,...fn C1 C2 C3 ... Ca
0   0      0   p11 p12 p13 ...
0   0      1
para k features temos 2 ** k combinacoes de features e associamos uma probabilidade de cada combinacao de feature levar a uma determinada classe. A soma de todas as probabilidades desta tabela deve ser 1 (eh uma funcao de distribuicao de probabilidade).
Esta tabela eh montada seguindo certas restricoes. Uma para cada feature fi.
A soma de todas as celulas que possuem fi ativo deve ter probabilidade igual aa que ocorre no corpus de treinamento.
Esta restricao nao eh suficiente para montar a tabela e os numeros sao colocados de forma a que se tenha a entropia maxima ou em outras palavras, de forma a nao privelegiar nenhum tipo de distribuicao em especial (deve ser sem vicio: unbiased). Assim cada p da tabela possui uma formula do tipo: pi * a1 ** f1 * a2 ** f2 ... O objetivo entao eh se calcular os a1 .. an e isto eh feito pelo GIS.
A aplicacao desta tabela eh feita da seguinte forma:
dada uma sequencia de palavras descobrir dentre todas as possiveis sequencias de tags aquele que possui a melhor probabilidade de ocorrencia, onde esta probabilidade eh retirada da tabela mencionada.
Este modelo serve para outras aplicacoes como a de se detectar quebras de sentencas.

5 20-10 Quebrar em sentencas: estatistico, entropia maxima - ver Adwait Ratnaparkhi

6 27-10 Parser 1: Shallow parser: Daelemans
passos: POS tagger, chuncking (descobrir os sintagmas), atribuir sujeito e objeto.

7 03-11 Alinhamento de corpus bilingue, Dekay Wu
Trainable coarse biblingual grammars for parallel bracketing
stochastic inversion transduction grammars

8 10-11 parsers CKY e Earley.
Pergunta: como implementar a gramatica do Dekay Wu usando estes parsers?
livro:
The Theory of Parsing Translation, and Compiling. Vol 1. Parsing. Prentice-Hall.
Aho,A.V.; Ullman,J.D.; chap 4., general parsing methods, pgs. 314-332

9 17-11 Alinhamento de corpus bilingue, Dan Melamed
em http://www.cis.upenn.edu/~melamed/
artigos:

     I. Dan Melamed (1998). Empirical Methods for MT Lexicon Construction, in L. Gerber and D. Farwell, Eds., Machine Translation and the Information Soup, Springer-Verlag.

     I. Dan Melamed (1996). A Geometric Approach to Mapping Bitext Correspondence, IRCS Technical Report #96-22, a revised version of the paper presented at the First Conference on Empirical Methods in Natural Language Processing   (EMNLP'96), Philadelphia, PA, May.

10 24-11 livro: finite-state language processing. Editado por Emmanuel Roche, Yves Schabes. MIT. 1997
capitulo 7: Deterministic Tagging.

11 01-12 Um projeto envolvendo Example based machine translation.
http://crl.nmsu.edu/users/sb/papers/ebmt/col94/col94.html

12 08-12 apresentacao trabalhos.

bibliografia complementar:
[1] Natural Language Processing in Prolog; Gerald Gazdar & Chris Mellish; Addison Wesley .
Para se estudar parser tabular bottom-up normal da ordem de n**3: cap 6: Well formed substring tables and charts.

[2] Survey of the State of the Art in Human Language Technology - 1995. http://cslu.cse.ogi.edu/HLTsurvey/ - um otimo survey a respeito da area criado pelos mestres no assunto (Fernando Pereira, Joshi, Martin Kay, etc.) e apoiado pelo NSF.

agradecimentos:
parte deste material (aulas 2, 7,10) foi reunida pelo mestrando Carlos Eduardo Dantas de Menezes.
o material da aula 8 foi cedido pelo mestrando Paulo Barreto.

Revisao para o proximo curso: terceiro quadrimestre de 2000
- adicionar uma aula sobre PC-KIMMO (sistema de regras para analise morfologica), provavelmente no lugar da aula 5: http://www.sil.org/pckimmo/v2/doc/guide.html

1	22-09	apresentacao historico: linguistas: Saussure, Chomsky (teoria X-barra). linguistica computacional: redes ATN, Prolog, gramaticas de unificacao (ex: PATR). Caso tipico: Gramatica de unificacao + teoria X-barra. o estado atual. Grandes avancos na Universidade da Pennsylvania (UPPEN). TreeBank alavancou varios projetos. http://www.cis.upenn.edu/~adwait/statnlp.html Passos normais: quebrar o texto em sentencas submeter a um tagger (etiquetador) submeter aa analise sintatica. Resolucao de ambiguidade: atribuir pesos maiores para as arvore mais provaveis, observando alguma estatistica. fazer um processamento sobre o resultado minha pesquisa e visao sobre a area.
2	29-09	Tagger 1: baseado em regras aprendidas : Eric Brill As regras sao aprendidas a partir do corpus do TREEBANK. fase de treinamento. fase de aplicacao. 1. tagging inicial - atribui a tag mais frequente para cada palavra conhecida (que apareceu no corpus) e a tag mais provavel (olhando sufixo e primeira letra se eh maiscula ou nao) para as palavras desconhecidas. 2. correcao da tag inicial atraves de regras como: se a tag eh VBZ e a palavra anterior eh DT entao troque VBZ por NNS. fase de treinamento. 1. regras para chutar as tags das palavras desconhecidas vendo o sufixo. 2. regras de correcao de tags. Para o treinamento o corpus eh dividido em duas partes: uma para a montagem do dicionario e outra para se inferir as regras de correcao.
3	06-10	Tagger 2: Baseado em exemplos: Daelemans link: http://ilk.kub.nl/ em publications Os exemplos sao colhidos da seguinte forma: f1, f2 ,... fn classe onde f1..fn sao as features ou caracteristicas. No caso do tagger se refere as tags das palavras anteriores e tags-compostas das palavras posteriores. A classe se refere aa tag. A cada feature podemos atribuir um peso. Se todas tiverem o mesmo peso entao eh o modelo IB1 senao eh o IB-IG. O peso pode ser obtido atraves da analise do quanto cada feature contribui para o aumento da entropia da peso. Isto pode ser feito automaticamente. Alem disso, Daelemans propoe que cada linha da tabela seja armazenada em uma arvore de decisao. O seu tagger tem desempenho semelhante ao do Eric Brill.
4	13-10	Tagger 3: estatistico baseado no modelo de entropia maxima link: http://www.cis.upenn.edu/~adwait/statnlp.html : para a tese de doutorado. Adwat Ratnaparkhi propoe um modelo de resolucao de ambiguidades que ocorrem na linguagem natural em sua tese de doutorado de 1998. Uma das aplicacoes deste modelo eh o tagger aqui analisado. O modelo possui algumas semelhancas com o modelo baseado em exemplos do Daelemans. Para Adwat cada feature eh apenas uma funcao que devolve zero ou um. Assim, ele propoe que se crie uma tabela do tipo: f1,f2,...fn C1 C2 C3 ... Ca 0 0 0 p11 p12 p13 ... 0 0 1 para k features temos 2 ** k combinacoes de features e associamos uma probabilidade de cada combinacao de feature levar a uma determinada classe. A soma de todas as probabilidades desta tabela deve ser 1 (eh uma funcao de distribuicao de probabilidade). Esta tabela eh montada seguindo certas restricoes. Uma para cada feature fi. A soma de todas as celulas que possuem fi ativo deve ter probabilidade igual aa que ocorre no corpus de treinamento. Esta restricao nao eh suficiente para montar a tabela e os numeros sao colocados de forma a que se tenha a entropia maxima ou em outras palavras, de forma a nao privelegiar nenhum tipo de distribuicao em especial (deve ser sem vicio: unbiased). Assim cada p da tabela possui uma formula do tipo: pi * a1 ** f1 * a2 ** f2 ... O objetivo entao eh se calcular os a1 .. an e isto eh feito pelo GIS. A aplicacao desta tabela eh feita da seguinte forma: dada uma sequencia de palavras descobrir dentre todas as possiveis sequencias de tags aquele que possui a melhor probabilidade de ocorrencia, onde esta probabilidade eh retirada da tabela mencionada. Este modelo serve para outras aplicacoes como a de se detectar quebras de sentencas.
5	20-10	Quebrar em sentencas: estatistico, entropia maxima - ver Adwait Ratnaparkhi
6	27-10	Parser 1: Shallow parser: Daelemans passos: POS tagger, chuncking (descobrir os sintagmas), atribuir sujeito e objeto.
7	03-11	Alinhamento de corpus bilingue, Dekay Wu Trainable coarse biblingual grammars for parallel bracketing stochastic inversion transduction grammars
8	10-11	parsers CKY e Earley. Pergunta: como implementar a gramatica do Dekay Wu usando estes parsers? livro: The Theory of Parsing Translation, and Compiling. Vol 1. Parsing. Prentice-Hall. Aho,A.V.; Ullman,J.D.; chap 4., general parsing methods, pgs. 314-332
9	17-11	Alinhamento de corpus bilingue, Dan Melamed em http://www.cis.upenn.edu/~melamed/ artigos: I. Dan Melamed (1998). Empirical Methods for MT Lexicon Construction, in L. Gerber and D. Farwell, Eds., Machine Translation and the Information Soup, Springer-Verlag. I. Dan Melamed (1996). A Geometric Approach to Mapping Bitext Correspondence, IRCS Technical Report #96-22, a revised version of the paper presented at the First Conference on Empirical Methods in Natural Language Processing (EMNLP'96), Philadelphia, PA, May.
10	24-11	livro: finite-state language processing. Editado por Emmanuel Roche, Yves Schabes. MIT. 1997 capitulo 7: Deterministic Tagging.
11	01-12	Um projeto envolvendo Example based machine translation. http://crl.nmsu.edu/users/sb/papers/ebmt/col94/col94.html
12	08-12	apresentacao trabalhos.