2011s2-mc906-seminario-10

Prévia do material em texto

Análise e implementação de mecanismo de
correção ortográfica utilizando técnicas de
inteligência artificial
Leandro Guimarães Conde das Neves
Raphael Kubo da Costa
Ricardo Nunes Miranda
October 20, 2011
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Verificação e correção ortográfica
Verificação: dado um texto, quero saber se todas as palavras
estão corretas
Correção: dado um conjunto de palavras consideradas
incorretas, quero substituí-las pelas palavras corretas
Ou obter uma lista de palavras candidatas a substitutas
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
IA e aplicações
Áreas de IA relacionadas a verificação e correção de erros
ortográficos:
Aprendizado de máquina (AIMA, parte VI) (c.f. p.13)
Processamento de Linguagens Naturais (AIMA, cap. 23)
Decisões probabilísticas (AIMA, parte V)
Importância do problema:
Edição de textos (documentos, formulários, email)
Correção e sugestões de busca
Análise e sugestão de produtos similares
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Ideia inicial
Texto do Peter Norvig, “How to Write a Spelling
Corrector” (c.f. p.13)
Corretor ortográfico em 21 linhas de Python
Baseado no teorema de Bayes
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
A Teoria
Teorema de Bayes aplicado
Dada uma palavra w e uma correção c, estou interessado em
argmaxcP(c |w), ou argmaxcP(w|c)P(c)
P(c) : Probabilidade de uma correção c (modelo de
linguagem). “Qual a probabilidade de c aparecer em um
texto?”
P(w |c) :Probabilidade de w ter sido digitada no lugar de c
(modelo de erros).
argmaxc : Mecanismo de controle, para enumerar todos os
valores factíveis de c e escolher o melhor.
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Implementação de Norvig
P(c): Entra-se uma grande quantidade de palavras e
calcula-se a frequencia de cada uma (treinamento).
Para palavras desconhecidas, usa-se probabilidade 1, não 0
(smoothing).
P(w |c) : Hack: palavras a uma distância de edição 1 são mais
prováveis que palavras a distância 2 etc.
argmaxc : Pegam-se as palavras com distância de edição
máxima 2 e que existam no modelo de linguagem.
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Escopo do Projeto
Implementar algumas das melhorias sugeridas pelo próprio
Norvig ao seu algoritmo
Buscar outras maneiras de se implementar um
verificador/corretor
Analisar implementações existentes (GNU Aspell, Hunspell)
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
O quê temos até agora
Implementação baseada na de Norvig (também em Python)
Capaz de receber diferentes modelos de linguagem
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
O quê falta ser feito
Analisar as implementações open source existentes.
Implementar mecanismos de spell checking além dos sugeridos
pelo texto do Peter Norvig.
Difícil precisar o quanto pode ser feito. Possíveis áreas, como
análise morfológica ou fonética, são complicadas.
Melhorar o modelo de erro
Efeito Cupertino, modelo de teclado usado.
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Trabalhos correlatos
Using the Web for Language Independent Spellchecking and Autocorrection
Paper do Google publicado em 2009 (c.f. p.12)
Implementação de um sistema de verificação e correção
ortográfica que não requer anotações manuais
Base teórica similar à descrita por Norvig (error model,
teorema de Bayes)
Diferença: base de dados proporcional ao Google
1 bilhão de páginas de notícias, 10 milhões de tokens mais
frequentes
Error model com 3.7x108páginas analisadas, triplas (palavra
desejada, palavra entrada, contagem)
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Trabalhos correlatos
Using the Web for Language Independent Spellchecking and Autocorrection
As páginas analisadas serviram para coletar tanto palavras
consideradas corretas quanto aquelas que seriam erros
Mecanismo em três etapas:
1 Todas as sugestões s para uma palavra w são ordenadas por
P(s|w)
2 Um classificador de ortografia prediz se w está errada
1 Em caso positivo e s não é um conjunto vazio, um classificador
de autocorreção prediz se as melhores sugestões estão corretas
Taxa de erro de 3.8% num texto originalmente com 10.8% em
inglês
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Referências bibliográficas
CHUNG, G. Y; ELLIS, G.; HUTCHINSON, B.; WHITELAW,
C; Using the Web for Language Independent Spellchecking and
Autocorrection. Proceedings of the 2009 Conference on
Empirical Methods in Natural Language Processing,
Singapura, p. 890-899, 2009.
BASU, A.; CHOUDHURY, M; GANGULY, N.; MUKHERJEE,
A.; THOMAS, M.; How Difficult is it to Develop a Perfect
spell-checker? A Cross-linguistic Analysis through Complex
Network Approach. TextGraphs-2: Graph-Based Algorithms
for Natural Language Processing, Rochester, p. 81-88, 2007.
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial
Referências bibliográficas
NORVIG, P. How to Write a Spelling Corrector. Disponível
em: http://norvig.com/spell-correct.html. Acesso em: 20 de
out. de 2011.
NORVIG, P.; RUSSELL, S. J. Artificial Intelligence: A Modern
Approach. 2a edição. New Jersey: Prentice Hall, 1995. 946 p.
BRANTS, T., FRANZ, A. All Our N-Gram are Belong to You.
Disponível em:
http://googleresearch.blogspot.com/2006/08/all-our-n-gram-
are-belong-to-you.html. Acesso em: 20 de out. de
2011.
Leandro Guimarães Conde das Neves Raphael Kubo da Costa Ricardo Nunes Miranda
Análise e implementação de mecanismo de correção ortográfica utilizando técnicas de inteligência artificial