Predição de Palavras: Desenvolvimento de uma Técnica Baseada em Markov Monica Jordan1, Paulo C. Pereira2, Alceu de Souza Britto Jr3, Álvaro Luiz Stelle4, Percy Nohama5 1,4,5
Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial (CPGEI) Universidade Tecnológica Federal do Paraná (UTFPR), Brasil 2 Centrais Elétricas do Brasil (Eletrosul), Brasil 2,3,5 Pontifícia Universidade Católica do Paraná (PUCPR), Brasil
Resumo – A busca pela inclusão social tem promovido a pesquisa de ferramentas que ampliam o uso do computador por pessoas com necessidades especiais, como emuladores de teclado e mouse, interfaces adaptadas e aceleradores de uso. Um importante acelerador é a predição de palavras, a qual permite diminuir o número de ações a ser executada pelo usuário. O trabalho descrito neste artigo, destinado às crianças em fase alfabetização, objetiva o desenvolvimento de um acelerador de uso para digitação de textos que une um emulador de teclado à predição de palavras, utilizando modelos escondidos de Markov, a qual considera as classes gramaticais como sendo os estados e as palavras classificadas como as observações em cada estado. A técnica está sendo desenvolvida sobre um corpus composto por textos infantis extraídos da Internet, processado por etiquetador e software de lingüística. As seqüências de classes gramaticais obtidas no processamento do corpus são a base do desenvolvimento da técnica, que com base nas ocorrências de maior freqüência indica as próximas palavras possíveis. O artigo ainda apresenta um protocolo de testes para a avaliação da técnica e discute a implementação da técnica. Palavras-chave: Predição de Palavras, Modelos Escondidos de Markov, Inclusão Digital, Emulador de Teclado, Lingüística. Abstract – The purpose of social inclusion for disabilities has been promoting development of tools that extend computer use for those persons with special necessities, as keyboard and mouse emulators plus accelerators. An important accelerator is the word prediction, which allows diminishing user’s action to be executed. This article describes a word prediction technique for children based on hidden Markov Models. In this method grammatical classes are considered as states and the classified words as observations of each state. It is being developed on a tagged corpus composed of infantile texts extracted of Internet and processed by linguistic software. The obtained grammatical class sequences are the base of the technique which indicates the next probable words as consequence of the most frequent sequences. It is also shown a test protocol in order to evaluate the proposed technique and discusses its practical realization. Key-words: Word Prediction, Hidden Markov Models, Digital Inclusion, Keyboard Emulator, Linguistics.
Introdução A atual preocupação com a inclusão social e digital de pessoas com necessidades especiais, que oferece a estas pessoas uma participação mais ativa na sociedade, tem levado vários grupos de pesquisa ao desenvolvimento de ferramentas auxiliares que ampliam a capacidade funcional dessas pessoas [1], [2], [3] e [4]. Uma dessas ferramentas, apresentada com grande importância, é o computador, visto este fruto da tecnologia ter invadido os lares com o advento da informática [4]. No entanto, apesar de sua presença, nem todas as pessoas estão aptas a comandar um computador, necessitando de dispositivos auxiliares, como apontadores alternativos [5] e [6], acionador de chave simples (alavanca, pedal ou botões, para acionamento por pressão, sopro ou toque), ou, ainda, aplicativos
ampliadores de comunicação ou facilitadores de uso (emuladores de teclado e mouse) [1], [7] e [8]. Visando atender essas demandas, desenvolveu-se um emulador de teclado, chamado Teclado Virtual Livre [1] e [2]. Este aplicativo possui um acelerador de uso, o qual oferece ao usuário um conjunto de dez palavras baseado na probabilidade de ocorrência destas tendo sido digitada uma palavra qualquer. A técnica conhecida por predição de palavras procura, num banco de dados, a palavra digitada e conta aquelas que mais frequentemente ocorrem em seguida. Tal técnica apresentou sucesso nos testes realizados [7], porém apontou para problemas como a desconsideração da concordância verbal e nominal, além do tempo de processamento. Desta forma, projetou-se o desenvolvimento de uma nova técnica de
predição que considere regras da língua portuguesa e que realiza a busca de forma mais direta, diminuindo o processamento computacional envolvido. Calcados na citação de Gasperin e Lima [9], que afirmam mostrarem-se mais satisfatórias, dentre as técnicas de desenvolvimento de ferramentas de predição, o levantamento estatístico simples e as cadeias de Markov, e nas inúmeras aplicações dos modelos de Markov em técnicas de reconhecimento de fala e escrita [10] e [11], os autores deste trabalho optaram pela adoção dos apontamentos Markovianos para o desenvolvimento de uma técnica de predição de palavras. Metodologia O desenvolvimento de uma nova técnica de predição exigiu a elaboração de um conjunto de palavras dentro do universo formado por palavras presentes em textos infantis, devido ao objetivo principal do trabalho inicial, quando se desenvolveu o Teclado Virtual Livre, ser de fornecer um aplicativo auxiliar para crianças alfabetizadas impossibilitadas de comandarem o computador através do teclado convencional. Procedeu-se, então, à confecção de um corpus (lista de palavras retiradas de fontes que caracterizem a realidade dos usuários alvo) com a busca por textos de domínio público compreensíveis por crianças alfabetizadas e que apresentassem qualidade ortográfica e gramatical. A fonte de busca foi a Internet, de onde se retiraram textos que atendessem aos critérios descritos, os quais foram armazenados em arquivos com extensão .txt. Para cada arquivo de texto foi criado um arquivo .hea contendo: título, fonte, autor, língua e tipo de texto. O corpus foi etiquetado com auxílio do VISL (Visual Interactive Syntax Learning), desenvolvido pela Universidade do Sul da Dinamarca [12]. Adotou-se a configuração Flat Structure, com o parser configurado para morphological tagging. O etiquetador conta com 13 etiquetas básicas (classes gramaticais), complementadas pela flexão dos elementos morfossintáticos, indicados por outras 33 etiquetas [13]. A aplicação do etiquetador com as configurações citadas, apresenta como resultado as palavras do texto a ser etiquetado listadas e seguidas de suas classificações gramaticais, como se pode visualizar no texto a seguir: bom [bom] ADJ M S dia [dia] N M S para [para] PRP todos [todo] DET M P Onde: ADJ (adjetivo), N (nome ou substantivo), PRP (preposição), DET (determinantes: artigos, pronomes
demonstrativos, etc.), M (masculino), S (singular) e P (plural). Com o corpus etiquetado, passou-se ao estudo do comportamento das palavras neste. Inicialmente, com auxílio do software WordSmith Tool Text Converter®, obteve-se uma lista de todas as palavras presentes nos textos constituintes do corpus com o número de vezes em que aparecem e o percentual de ocorrência de cada uma. Esta lista é chamada de wordlist. Esta lista permitiu procedimentos preliminares necessários para o tratamento do corpus, como eliminação de sinais de hífen, pontuações de abreviaturas, separação de palavras compostas (por exemplo: couve-flor separada em couve flor para interpretação da técnica), eliminação de parêntesis, colchetes e demais sinais utilizados pelo etiquetador, e determinação dos bigramas a serem analisados pelo modelo de predição. Com o corpus tratado, partiu-se à modelagem do sistema Markoviano. As cadeias de Markov compõem um processo estocástico, isto é, especificam a probabilidade de alguns eventos (estados) e as relações entre esses (transições), num mesmo processo ao longo do tempo. O processo é dito Markoviano se a probabilidade em um dado tempo condiciona-se a somente um histórico finito. Chamam-se modelos escondidos de Markov, conhecidos como HMM (Hidden Markov Models), quando para tais eventos (estados) relaciona-se uma lista de observações ou ocorrências possíveis [14]. Um HMM é definido pelos parâmetros: - matriz A = {aij}, composta pelas probabilidades de transição; - matriz B = {bj}, probabilidades de observação; - matriz π = {πi }, probabilidades iniciais das seqüências. Neste estudo, as classes gramaticais foram adotadas como sendo os estados e as palavras, dentro de cada classe, como as ocorrências. Pode-se visualizar uma pequena seqüência deste modelo na Figura 1, na qual nota-se que os estados são representados pelas classes gramaticais det (determinantes), n (nome ou substantivos), v (verbo) e adj (adjetivo). E as probabilidades da transição entre estados indicada pelo valor numérico, bem como a direção da transição, como indica o sentido das flechas.
Figura 1 – Exemplo de seqüência do Modelo de Markov
Do texto etiquetado foi montado um arquivo .xls que associa aos pares a palavra à sua classe gramatical. Esta classe gramatical apresenta-se detalhada com classe, gênero e número, quando couber (por exemplo, mesa: substantivo, feminino, singular). Pela contagem das palavras etiquetadas no texto todo (wordlist), obteve-se uma contagem da freqüência de ocorrência das classes gramaticais. Este levantamento de freqüência, associado à identificação, no corpus, de quais palavras começam frases, servirá como matriz inicial, pois se o usuário digitar uma palavra vai-se na lista de associação e identifica-se a classe dela. Caso a palavra apareça classificada de diferentes formas, o algoritmo procurará a com maior ocorrência. Na seqüência, gerou-se, com auxilio do ® WordSmith Tool Text Converter , uma lista de palavras, chamada concord, que conta a vizinhança de uma palavra central, na qual seleciona-se uma palavra e ajusta o aplicativo para que gere e aponte a lista de seqüências em que ela aparece, mostrando sua vizinhança à direita e esquerda, com o número de vizinhos prédeterminado. As palavras centrais selecionadas foram as 13 etiquetas das classes gramaticais e o tamanho da vizinhança igual a 7, sempre considerando pontuações finais como fim de seqüência. Desta forma pôde-se obter a freqüência das seqüências de classes gramaticais no corpus etiquetado, ou seja, a matriz de transição. A matriz de observação foi gerada pelas palavras com maior ocorrência no corpus, dentro de sua classe gramatical, conforme etiqueta. O HMM definido é a base para o desenvolvimento do algoritmo de predição que indica as próximas dez palavras mais prováveis, considerando o estado anterior. No desenvolvimento deste algoritmo consideram-se os dois estados anteriores (bigrama), ou seja, as duas palavras já digitadas no contexto, ou somente a anterior, caso só tenha sido digitada uma ou ocorrer a existência de uma pontuação indicadora de fim de oração. Na seqüência, o modelo é treinado, a partir de adaptação do algoritmo de Baum-Welch [11], com base no corpus elaborado e inserido ao código fonte do Teclado Virtual Livre para realização dos testes. O desenvolvimento dos algoritmos utiliza a linguagem de programação Visual C++. Os testes do aplciativo com a técnica de predição baseada em HMM seguem um protocolo desenvolvido e apresentado ao Comitê de Ética da Pontifícia Universidade Católica do Paraná. O protocolo envolve o uso do aplicativo Teclado Virtual Livre por crianças alfabetizadas de três escolas da cidade de Curitiba, sendo duas de ensino fundamental e uma de ensino especial.
O uso do aplicativo realiza-se em duas sessões, sendo uma para apresentação do aplicativo e outra para a tomada dos parâmetros analisados. Na segunda sessão solicita-se às crianças que digitem um determinado texto por duas vezes: uma sem a predição de palavras e outra com. Tomam-se como parâmetros para análise comparativa o tempo e o número de cliques envolvidos na execução das tarefas. O texto contém 95 palavras, sendo necessários cerca de 570 cliques para sua digitação. O grupo de controle é composto pelos dados obtidos na digitação do texto sem a predição. Ainda apresenta-se às crianças um questionário com 3 perguntas, questionando se foi bom ou ruim escrever o texto, se ela cansou e gostou. Este questionário é apresentado ao final da digitação do texto sem a predição e, depois, com a técnica. As comparações realizam-se dentro de cada grupo de criança, ou seja, cada escola compondo um grupo. Inexistem comparações entre os grupos, pois os mesmos apresentam diferenças culturais e cognitivas, as quais não serão consideradas por não constituírem objetivo deste trabalho. Resultados Preliminares A busca por textos infantis na internet resultou em um corpus de texto com 40.361 palavras, sendo 7500 palavras diferentes, divididas em 100 textos de boa qualidade gramatical e sem excessivas figuras de linguagem. Os textos base do corpus apresentam lendas e cultura popular brasileiras, diálogos, textos religiosos de vocabulário e linguagem infantis, fábulas, nomes de animais e astros (sol, lua, via láctea, etc), expressões populares, elementos da natureza, peças da casa e objetos do dia-a-dia. A wordlist obtida com o uso do WordSmith Tool Text Converter®, indicou os verbetes “e” e “a”, como os mais ocorridos no corpus, e as palavras “para”, “não” e “uma”, as com maior freqüência. Já o uso do concord indicou as seqüências com maior ocorrência, como, por exemplo, para uma das classes gramaticais com maior ocorrência no corpus (artigo, definido como determinante pelo etiquetador utilizado), ser seguido de um substantivo em 37% das vezes em que aparece. Estas seqüências de classes gramaticais são a base de dados do algoritmo de predição em desenvolvimento que, reconhecendo a palavras digitada, procurará no corpus as seguintes mais prováveis. Na realização dos testes de aplicação do Teclado Virtual Livre, obteve-se redução de 15% no número de cliques necessários para a
digitação de um determinado texto. A quantidade de cliques englobava, além do texto, os cliques necessários à correção, como, por exemplo, no texto “...eu e ele gostamos...”, em que o aplicativo apontou para “...eu e ele gosta...”. Como o trabalho aqui apresentado considera as concordâncias verbal e nominal, este tipo de erro será mitigado, e o valor de 15% ultrapassado, diminuindo ainda mais a dificuldade do usuário final em produzir um texto usando um computador. Para o parâmetro tempo espera-se um comportamento semelhante ao apresentado nos testes com o Teclado Virtual Livre, que inicialmente apresentou incremento, só reduzindo com o treinamento do usuário. Como se objetiva oferecer uma ferramenta auxiliar a pessoa com necessidades especiais, este incremento não tem importância se destacada a facilidade em desempenhar a tarefa de digitação. Este fator poderá ser determinado pelas respostas obtidas pelo questionário a ser respondido pelos voluntários. A pesquisa, enfim, visa obter como resultado um acelerador de digitação adaptado à língua portuguesa, com inteligência de predição e rápido processamento, aliando os conceitos de Markov a um emulador de teclado. Discussão e Conclusões Encontra-se na literatura diversos trabalhos que citam o sucesso das técnicas de comunicação aumentativa. Alm [15] conclui em uma de suas publicações que os resultados obtidos com sistemas de comunicação com ferramentas de aceleração de linguagem, como predição de textos demonstram as melhorias obtidas na quantidade e qualidade de conversação. Silveira [16] aponta a dificuldade dos usuários de CAA em elaborarem textos extensos, bem como em exporem seus pontos de vista detalhadamente. Todos os resultados obtidos com os trabalhos de Alm [15] mostraramse expressivos e têm motivado seu grupo a permanecer desenvolvendo trabalhos na área de sistemas para auxiliar pessoas com necessidades especiais. A seleção minuciosa dos textos que compõe o corpus, atentando para redações com vocabulário infantil sem excesso de figuras de linguagem e com a melhor ortografia possível demandou tempo e dedicação do grupo de pesquisa. Da mesma forma, na fase de desenvolvimento do algoritmo de predição, diversos tipos de processamento de corpus foram envolvidos a fim de se obter uma lista de seqüências de palavras que considere possíveis inferências negativas para a técnica, como: pontuações que quebram uma seqüência e devem ser consideradas, análise de palavras compostas e as concordâncias verbais e
nominais. Estes trabalhos, no entanto, conferem à técnica uma característica positiva no âmbito do aprendizado, pois oferecerá ao seu usuário um contexto mais gramaticalmente correto. Desta forma, pode-se apontar a importância de agregar aos sistemas de comunicação um acelerador de uso eficiente, que permita maior autonomia às pessoas consideradas não capazes por não se expressarem, ou o fazerem de forma lenta e dependente de outra pessoa. Agradecimentos Os autores deste trabalho agradecem às escolas que permitiram que os testes sejam realizados em suas instalações e sob a supervisão de suas pedagogas, ao CNPq e à CAPES pelo apoio financeiro fornecido à pesquisa. Referências [1] Jordan, M., Matias, D.H., Nohama, P. (2006), “Amplisoft: Comunicação Alternativa para Todos”, Anais do IV Congresso Iberoamericano sobre Tecnologias de Apoio a Portadores de Deficiência, Vitória, v. 2. p. CO319-CO324, Fev. [2] Hirotomi, T., Mirenkov, N.N. (2003), “SelfExplanatory Componentes: a Basics for new Communicators”, In: Journal of Viausl Languages and Computing, p. 215-232. [3] Hartyley, S.D, Wirz, S.L. (2002), Development of a ‘Communication Disability Model’ and its Implication on Service Delivery in Low-Income Countries”, In: Social Science & Medicine, v. 54, p. 1543-1557. [4] Pinheiro, P.C.P., “Inclusão Digital, Inclusão Social e o Deficiente Físico.” [http://www.crp.ce.gov.br/artigosinclusaodigita l.htm#patricia]. Janeiro 2006. [5] Dias, N.; Osowsky, J.; Gamba, H.R.; Nohama, P. (2004), “Controle do Cursor do Mouse pelo Movimento da Cabeça Usando Câmera CCD e Processamento de Imagem”, IFMBE Proceedings of the Latin American Congress on Biomedical Engineering, João Pessoa, v. 5. p. 441-444. [6] Muller, R.W., Schmal, R.M., Jordan, M., Nohama, P. (2004), “A Novel Utrasonic Mouse Activated by Head Movement”, Proceedings of the 11th Biennial Conference of the International Society for Augmentative and Alternative Communication, Natal, v. 11. p. 1-2.
[7] Henzen, A., Charão, A.F. “Emulador de Teclado e Mouse.” [http://www.projetoetm.com.br]. Jul 2004. [8] Matias, D.H., Nohama, P. (2003), “Teclado Virtual Alfanumérico com Predição de Palavras”, Anais do II Seminário e I Oficinas ATIID, São Paulo, v. 1. p. 1-4. [9]
Gasperin, C.V., Lima, V.L.S. (2001) “Fundamentos do Processamento Estatístico da Linguagem Natural”, Technical Report Series PUCRS, n.21.
[10] Zimmermann, M., Bunke, H. (2004), “ NGram Language Models for Offline Handwritten Recognition”, Proceedings of the th 9 Int’I Workshop IEEE on Frontiers in Handwriting Recognition. [11] Rabiner, L.R. (1989), “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Proceeding of the IEEE, v.77, n. 2. [12] “VISL – World of VISL”, [http://visl.sdu.dk/], Janeiro 2005. [13]
Sardinha, T.B. (2004), “Lingüística Corpus”, São Paulo: Ed. Manole.
de
[14] Wang, X. (1997), “Incorporating Knowledge on Segmental Duration in HMM-based Continuous Speech Recognition”, Tese de Doutorado, Universidade de Amsterdam, 190 pp. [15] Alm, N., Newell, A.F., Arnott, J.L. (1997), “Lessons from Applying Conversation Modelling to Augmentative and Alternative Communication”, In: Disability InFormation Resources, Japão. [16]
Silveira, M.S. (1996), “Comunicación Alternativa e Informática: Utilización de recursos de Inteligencia Artificial y Multimedia”, Anais do II Congresso Iberoamericano de Comunicação Alternativa e Aumentativa, Chile.
Contato Monica Jordan E-mail:
[email protected] Prof. Dr. Álvaro Luiz Stelle
[email protected] Universidade Tecnológica Federal do Paraná. Endereço: Av. Sete de Setembro 3165, Curitiba, PR, Brasil, CEP 80230-901
