Embed Size (px)
Citation preview
UNIVERSIDADE CATOLICA DE PELOTASCENTRO POLITECNICO
PROGRAMA DE POS-GRADUACAO EM INFORMATICA
Recuperacao de Informacoes eProcessamento de Linguagem Natural
Um Levantamentopor
Eduardo Bauer Londero
Trabalho Individual ITI-2008/2-003
Orientador: Prof. Dr. Antonio Carlos da Rocha CostaCo-orientador: Prof. Dr. Stanley Loh
Pelotas, dezembro de 2008
SUMARIO
LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
LISTA DE ABREVIATURAS E SIGLAS . . . . . . . . . . . . . . . . . . . . . 6
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1 INTRODUCAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 A RECUPERACAO DE INFORMACOES . . . . . . . . . . . . . . . . . . 112.1 Estrategias de RI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.1.1 Tipologia de Modelos de RI . . . . . . . . . . . . . . . . . . . . . . . . . 132.1.2 Modelo de Espaco de Vetores de Termos . . . . . . . . . . . . . . . . . . 142.1.3 Modelos probabilısticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 Utilitarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3 Tarefas da Recuperacao de Informacoes . . . . . . . . . . . . . . . . . . 18
3 O PROCESSAMENTO DA LINGUAGEM NATURAL . . . . . . . . . . . 203.1 O Tratamento da Linguagem pelo Computador . . . . . . . . . . . . . . 213.2 Comunicacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 As Tarefas do Processamento da Linguagem Natural . . . . . . . . . . . 243.4 Arquitetura de um sistema PLN . . . . . . . . . . . . . . . . . . . . . . 25
4 FERRAMENTAS PRONTAS . . . . . . . . . . . . . . . . . . . . . . . . . 284.1 Lucene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.1.1 Principais Pacotes do LUCENE . . . . . . . . . . . . . . . . . . . . . . . 304.2 MALLET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2.1 Filtros de Importacao do MALLET . . . . . . . . . . . . . . . . . . . . . 314.2.2 Classificadores do MALLET . . . . . . . . . . . . . . . . . . . . . . . . 314.2.3 Principais Pacotes do MALLET . . . . . . . . . . . . . . . . . . . . . . 314.3 GATE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.4 Lemur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.5 Simmetrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.6 Outros Recursos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5 TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6 CONCLUSAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
REFERENCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
ANEXO A GLOSSARIO . . . . . . . . . . . . . . . . . . . . . . . . . 43
LISTA DE FIGURAS
Figura 2.1 Modelos de IR segundo a matematica empregada e a dependenciaentre termos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Figura 2.2 Acompanhamento Anual da Pesquisa no TREC ate 2001 . . . . . . . 19
Figura 3.1 Texto com marcadores criados pelo reconhecedor de entidades doGATE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Figura 3.2 Arquitetura de um sistema PLN segundo (SILVA et al., 2007) . . . . 27
Figura 4.1 Analise sintatica com o GATE . . . . . . . . . . . . . . . . . . . . . 32Figura 4.2 Desempenho comparado das metricas do Simmetrics . . . . . . . . . 34
LISTA DE TABELAS
Tabela 4.1 Lista e localizacao de recursos integraveis em projetos de IR e NLP . 29Tabela 4.2 Conceitos Basicos do Lucene . . . . . . . . . . . . . . . . . . . . . 30Tabela 4.3 Pacotes e Classes Principais do LUCENE 2.4.0 e suas funcoes . . . . 36Tabela 4.4 Pacotes Principais do MALLET e suas funcoes . . . . . . . . . . . . 37Tabela 4.5 Mais recursos vinculados a PNL . . . . . . . . . . . . . . . . . . . . 38
LISTA DE ABREVIATURAS E SIGLAS
PLN Processamento de Linguagem Natural
LC Linguıstica Computacional
RI Recuperacao de Informacoes
ABNT Associacao Brasileira de Normas Tecnicas
DoD Departament of Defense
TREC Text Retrieval Conference
NIST National Institute of Standars and Technology
WebKDD Workshop in Knowledge Discovery and WEB Data Mining
WEKA Waikato Environment for Knowledge Analysis
GATE General Architecture for Text Engeneering
MALLET MAchine Learning for LanguagE Toolkit
POS Part-Of-Speech
SVM Support Vector Machine
AF Automato Finito
RESUMO
O presente trabalho examina duas areas atuais e confluentes da Ciencia daComputacao – Recuperacao de Informacoes (RI) e Processamento de Linguagem Natural(PNL) – seus conceitos e tecnicas, e em seguida faz um levantamento das bibliotecas eaplicativos publicos, maduros, atualizados e mais facilmente disponıveis para utilizacaoem pesquisa. A recuperacao de informacoes e area dedicada a facilitar a recuperacao dedocumentos e sua apresentacao ordenada segundo criterios de relevancia. A medida que ovolume de informacoes cresce, e os modelos atualmente empregados na sua recuperacaose mostram ineficazes, fica evidente a necessidade de propor e testar modelos de docu-mentos mais complexos e formas de consultas mais elaboradas. Esses modelos de RImais complexos provavelmente farao uso de tecnicas do Processamento Natural de Lin-guagem, que e a area da computacao que se dedica a lidar com a lıngua natural faladaou escrita. Por outro lado, aqueles topicos que eram objeto de pesquisa algumas decadasatras, ja se encontram implementados em bibliotecas publicas de programacao. Para sefazer um servico de busca e recuperacao com as tecnicas tradicionais ja existem compo-nentes prontos para uso. Para levar a efeito a proposta de melhorar a Recuperacao deinformacoes com Processamento da Linguagem Natural, acompanhando o estado da arteatual, e necessario conhecer os conceitos e tecnicas de ambas as areas e dispor de bi-bliotecas equivalentes as utilizadas nas pesquisas ou pelo menos saber usar e adaptar asbibliotecas de uso publico geral. E o que procuro dar inicio atraves desse trabalho.1.
Palavras-chave: Recuperacao de Informacoes, Processamento de Linguagem Natural,Lucene, GATE, Lemur, Simmetrics.
1Esse trabalho foi composto com TeXnicCenter para LaTex e obedecendo a ortografia valida ate janeirode 2009
RESUMO
TITLE: “INFORMATION RETRIEVAL AND NATURAL LANGUAGE PROCES-SING - THE STATE OF THE ART ”
This work examines two areas from Computer Science – Information Retrievaland Natural Language Processing – that begun to merge. It studies its models and techni-ques and also looks for public, proven, easily available and up-to-date programs, toolkitsor packages to use and integrate in research. The goal is to enhance IR by using NLPideas and techniques. Information Retrieval is dedicated to easy document recover and itspresentation ranked accordingly to relevance criteria. As document quantity in Internetmounts, actual models became inefficient and new document models, more complex andcomplete, should be proposed and tested as long as more sophisticated queries. Thesenew models should thrive with ideas and techniques borrowed from Natural LanguageProcessing, which is the computer area dedicated to deal with natural, written or spoken,language. To reach the goal proposed here, to enhance IR through NLP techniques, itsdesirable to know and use ”off-the-shell”programs and toolkits at least equivalent to thosecurrently used and mentioned in TREC encounters.
Palavras-chave: Information Retrieval, Natural Language Processing, Lucene, MAL-LET, Lemur, Simmetrics.
9
1 INTRODUCAO
Recuperacao de Informacoes e a area dedicada a facilitar a procura de documen-tos ou passagens em grandes colecoes de textos ou na Internet de acordo com os dadosde uma consulta e apresenta-los ordenados por criterios de relevancia. Originalmente adisciplina de Recuperacao de Informacoes pertencia a Biblioteconomia e passou a inte-ressar a Ciencia da Computacao quando as colecoes de documentos em meio eletronicoganharam importancia.
Em 1983, Gerald Salton, um dos pioneiros da area de Recuperacao de Informacoes(RI), previu que chegaria a epoca em que as pessoas seriam forcadas a utilizar ainformacao mais facilmente disponıvel e ignorar o restante dela. Essa epoca chegou.Os sistemas corporativos limitados e carıssimos de entao foram substituıdos pelos gigan-tescos e gratuitos Google e Yahoo. Neles a informacao trivial sobre determinado assuntopode ser encontrada, mas e difıcil determinar se o resultado da consulta feita e suficienteou relevante.
A medida que cresce a quantidade de paginas da internet, fica cada vez mais difıcilse encontrar informacao de qualidade e os modelos de IR em uso se mostram inadequadose precisam ser melhorados. Em 1983 as colecoes para a busca de documentos e passagensatingiam milhares de documentos. Em 2004 o Google tinha indexadas mais de 4 bilhoesde paginas (GROSSMAN; FRIEDER, 2004). Com o crescimento do tamanho do espacode busca, o desempenho precisa ser privilegiado, e as tecnicas basicas da area, feitas paracomputadores antigos, contraditoriamente, se consolidaram. Aquilo que funcionava emcomputadores lentos de 1970, precisava ser mantido devido ao crescimento do numero depaginas a serem indexadas.
Em 1992 o Departamento de Defesa americano e o National Institute of Standardsand Technology promoveram a primeira conferencia TREC - Text Retrieval Conference,que se realiza desde entao e continua sendo um dos mais importantes foruns para acom-panhar as tendencias e o estagio alcancado pela pesquisa. Nos encontros TREC, variasareas originalmente privativas de Inteligencia Artificial e Processamento Natural de Lin-guagem, tais como Sumarizacao Automatica e Respondendo Perguntas1 passaram a serincluıdas na area de RI, porem com abordagens muito proprias, estatısticas e ligeiras,adequadas ao tamanho dos corpora propostos.
Os sistemas de traducao automatica, entendimento e geracao de fala, respondendoperguntas e sumarizacao se originaram na area da Inteligencia Artificial e do Processa-mento de Linguagem Natural. Exemplos pioneiros sao o BASEBALL (GREEN et al.,1963) e o BASEBALL-MOON, que funcionavam como interface em linguagem natural
1Respondendo Perguntas sera a versao adotada neste trabalho para se referir a Question Answering.
10
entre o usuario e um banco de dados.A Recuperacao de Informacoes tradicional lida principalmente com texto2, nada
mais natural que buscar se envolver com Processamento Natural de Linguagem, na pro-cura de mais caracterısticas que auxiliem a selecionar documentos relevantes. No entantoo obstaculo e a complexidade e o desempenho dos algoritmos do PLN, alem da proprianatureza ainda incompreendida da lıngua natural.
Com o esgotamento crescente dos modelos em uso na Recuperacao deInformacoes em virtude do crescimento da Internet e com a abordagem de problemasde sumarizacao e respondendo perguntas, antes privativos de PLN e IA, o caminho para aRI parece ser o de aos poucos enfrentar o problema de desempenho das tecnicas de PLNe buscar ao poucos conhece-las e incorpora-las onde se provar vantajoso.
Alem de estudar Recuperacao de Informacoes e Processamento Natural de Lin-guagem esse trabalho busca levantar quais alternativas existem de utilizacao de progra-mas e pacotes prontos, testados, atuais e facilmente integraveis existem para se produzirpesquisa de qualidade o mais rapidamente possıvel. Nessa area, examinaremos o Lucene,um projeto de engine de recuperacao que se firmou com padrao e serve a pesquisa comoparametro basico de comparacao. Quanto aos pacotes de PLN, a disponibilidade e muitomaior. Examinaremos entre outros o GATE da Universidade Sheffield, o MALLET daUniversidade da Pensilvania e o Lemur da Universidade de Stanford.
2Nao e mais considerada uma area de ponta da pesquisa, porem o e a Recuperacao de Informacoes deMultimıdia, dada a dificuldade ainda maior de processar e caracterizar esses itens. Essa area e listada comoobjetivo nos Desafios da Computacao para 2006-2016 (LUCENA; BAUZER, 2006).
11
2 A RECUPERACAO DE INFORMACOES
A Recuperacao de Informacoes (RI) e a ciencia dedicada a localizar documentosrelevantes, nao apenas o mero casamento e identificacao de padroes (GROSSMAN; FRI-EDER, 2004). E uma ciencia para encontrar documentos, extrair informacoes de dentrode documentos, buscar criar metadados sobre eles, tanto em SGDBs, como em colecoes,como na WEB. RI e interdisciplinar e busca pontos de apoio em ciencia da computacao,matematica, biblioteconomia, linguıstica, estatıstica e psicologia cognitiva.
O maior campo de aplicacao, em evidencia hoje em dia, e a procura e ordenamentode documentos na internet. Porem colecoes de documentos, tais como correspondenciaem email, manuais tecnicos, legislacao ou jurisprudencia tambem podem se beneficiardesse trabalho. Um problema relacionado ao da procura e o da filtragem e o roteamentode documentos, no qual se busca direcionar correspondencia (email ) que chega a umaempresa para os setores adequados segundo perfis identificados.
Para medir a efetividade do IR dois conceitos basicos sao utilizados: precisao erecall. A precisao e um conceito intra-consulta formado pela taxa dos documentos signi-ficativos recuperados pela quantidade total de documentos recuperada em um consulta. Orecall e taxa formada pelo numero de documentos relevantes recuperados dividido pelaquantidade total de documentos relevantes no corpora. Portanto, o recall so pode sermedido em corpora fechados e conhecidos, precisando ser estimado quando se trata dainternet.
Precisao =RecuperadosRelevantes
Recuperados(2.1)
Recall =RecuperadosRelevantes
Relevantes(2.2)
2.1 Estrategias de RIAs estrategias de recuperacao atribuem uma medida de similaridade entre uma
consulta e um documento. Elas se baseiam na nocao de que a relevancia de um documentopara uma dada consulta e proporcional a co-ocorrencia de termos entre elas. Algumasestrategias sao balanceadas para aliviar os problemas causados pela ambiguidade tıpicada linguagem, que um conceito pode ser descrito por varios termos 1 ou um termo podeidentificar diversos conceitos conforme o contexto. Uma estrategia de recuperacao e umalgoritmos que, dado uma consulta Q e um conjunto de documentos D1, D2, ..., Dn, cria
1Exemplo de polissemia: ”Porto Alegre”equivale a ”capital gaucha”.
12
um Coeficiente de Similaridade CS(Q, Di) para cada documento 1 ≤ i ≤ n.As estrategias identificadas por (GROSSMAN; FRIEDER, 2004) sao:
• Modelo Espaco Vetorial: a consulta e cada documento sao representados por umvetor no espaco de termos. Uma medida de similaridade entre ambos vetores ecalculada.
• Recuperacao Probabilıstica: Uma probabilidade baseada na chance de que umtermo apareca em documentos relevantes e computada para cada documento dacolecao. Para termos comuns entre uma consulta e um documento, a similaridade ea combinacao das probabilidade de cada termo comum.
• Modelos de Linguagem: Um modelo e construıdo para cada documento e a proba-bilidade do documento gerar a consulta e computada.
• Redes de inferencia: Uma rede Bayesiana e utilizada para inferir a relevancia de umdocumento frente a uma consulta. Essa relevancia e dada pela forca da evidenciacontida em um documento que permita avaliar a sua similaridade com a consulta.
• Indexacao Booleana: Um escore e atribuıdo de tal forma que uma consulta booleanainicial resulte em um ordenamento. Isto e feito associando um peso a cada termoda consulta, de modo que esse peso e utilizado para computar o coeficiente desimilaridade.
• Indexacao por Semantica Latente: A ocorrencia de termos em documentos e repre-sentada como uma matriz termos versus documentos. A matriz e reduzida atravesde Decomposicao Singular de Valores (DSV) para filtrar o ruıdo de cada docu-mento de forma que dois deles que tenham a mesma semantica fiquem localizadosproximos em um espaco multidimensional.
• Rede Neural: Uma sequencia de neuronios, ou nos em uma rede, ao serem ativadospor uma determinada consulta ligam-na aos documentos que lhe correspondem. Asredes sao uma modalidade supervisionada de treinamento e precisam ser treinadaspara responder a documentos relevantes ou nao.
• Algoritmos Geneticos: Um consulta otima para achar documentos relevantes podeser gerada por evolucao. Uma consulta inicial e criada com pesos randomicos ouestimados. Uma nova consulta e gerada e sobrevive ser estiver mais proxima dosdocumentos relevantes ou e excluıda se for menos capaz que a inicial.
• Recuperacao por Conjunto Fuzzy: Um documento e mapeado para um conjuntofuzzy, que e contem os elementos vinculados a um numero que indica a forca do re-lacionamento. Consultas booleanas sao mapeadas para as operacoes de interseccao,uniao e complemento
Para cada tipo de estrategia varios utilitarios pode ser empregados para construir os ele-mentos ou melhorar os resultados de cada abordagem. Esses utilitarios sao descritos nasecao 2.2.
13
2.1.1 Tipologia de Modelos de RIPara a recuperacao ser eficiente os documentos sao transformados em algum tipo
de representacao. A figura 2.1, encontrada em (KUROPKA, 2004) apud (WIKIPEDIA,2008) faz a categorizacao dos modelos mais comuns de IR segundo duas dimensoes:a base matematica e as propriedades do modelo. Quanto a matematica, podem ser osseguintes
• Modelos da teoria dos conjuntos representam documentos como conjuntos de pala-vras ou frases. As similaridades sao derivadas de operacoes tıpicas de conjuntos:
Modelo padrao booleano
Modelo booleano estendido
Recuperacao fuzzy
• Modelos algebricos representam documentos e consultas como vetores, matrizes outuplas e a similaridade entre o vetor da consulta e do documento e representado porum escalar.
Modelo de espaco vetorial
Modelo de espaco vetorial generalizado
Modelo de espaco vetorial por topico
Modelo booleano estendido
Modelo de espaco vetorial por topicos melhorado
Indexacao semantica latente
• Modelos probabilısticos tratam o processo de IR como um inferencia probabilısticae as similaridades sao computadas como probabilidades de um documentos ser re-levante para um dada consulta. Probabilidade Bayesiana geralmente e empregadanesses modelos.
Recuperacao por independencia binaria
Modelo de relevancia probabilıstica (como o Okapi BM25)
Inferencia incerta
Modelos de linguagem
Modelo de divergencia-do-randomico
Alocacao latente de Dirichilet
Quanto as propriedades dos modelos empregados:
• Modelos sem interdependencias nao tratam o relacionamento entre os termos. Essefato e geralmente representado no modelo de espaco vetorial pela presuncao deortogonalidade entre os seus eixos e no modelo probabilıstico pela (presuncaotambem) independencia entre as variaveis de termos.
• Modelos com interdependencia imanente permite uma representacao dos relaciona-mentos entre termos. O grau de interdependencia entre dois termos e definido pelomodelo em si. Geralmente e direta ou indiretamente derivada da co-ocorrencia dostermos no conjunto dos documentos. Por exemplo, reducao dimensional.
14
Figura 2.1: Modelos de IR segundo a matematica empregada e a dependencia entre termos
• Modelos com interdependencia transcendente consideram a relacao entre os termos,mas nao determinam como esse relacionamento se estabelece. Eles dependem defontes externas – humana ou alguma heurıstica complexa – para estabelecer o graue tipo de relacionamento entre os termos.
2.1.2 Modelo de Espaco de Vetores de TermosO modelo de espaco de vetorial computa uma medida de similaridade definindo
um vetor que representa cada documento [Salton et al. 1975] apud(GROSSMAN; FRI-EDER, 2004). O modelo se baseia na ideia de que, de algum modo, o significado dodocumento e contido nas suas palavras nele empregadas. Ao se representar as palavras dodocumento por um vetor, e possıvel comparar documentos e consultas e determinar quaoparecidos eles sao. Se uma consulta pode ser considerada como um documento, pode serpossıvel computar um coeficiente de similaridade SC entre consulta e os documentos
No modelo vetorial, os documentos e a consulta serao representados por veto-res. O metodo tradicional e calcular o angulo entre eles. Entao, se dois vetores apontamna mesma direcao, ou aproximadamente na mesma direcao, mesmo que nao sejam demesmo tamanho, eles sao semelhantes entre si. Para se calcular o angulo entre dois veto-res se recorre ao produto interno entre eles. Mas nao necessariamente o produto interno,(GROSSMAN; FRIEDER, 2004), qualquer funcao monotonica do angulo e suficiente.Geralmente e referido o CS - Coeficiente de Similaridade - ao inves do angulo.
Alem de simplesmente usarmos vetores com ındices que registram a ocorrenciade termos, surgiu a ideia de permitir ao usuario dar peso a cada termo da consulta. Ummodo proposto com pesos foi faze-lo proporcional a sua ocorrencia em toda a colecao. Aideia e de que um termo frequente deve ter menor importancia do que um termo raro.
Suponha que que existam n diferentes termos no conjunto de documentos, e quea ocorrencia de um termo na consulta ou em um documento seja assinalado por 0 ou 1conforme a aparicao de cada um termo em cada uma delas ou pelo seus pesos estimados.Um vetor Consulta C, seria representado pelos ındices c1, c2 ... cn que podem valer 0
15
ou 1 em uma abordagem simples ou um peso wj2 calculado de forma que veremos mais
adiante:
~C =< c0, c1, ....cn >
De forma semelhante, os vetores de 2 documentos D1 e D2 sao definidos da se-guinte maneira:
~D1 =< d1,0, d1,2, ..., d1,n >
e~D1 =< d2,0, d2,2, ..., d2,n >
Em uma colecao que contenha 10.000 termos diferentes, os vetores que represen-tam cada documento teriam 10.000 ındices. Um documento com 100 termos teria 9.900ındices zerados e 100 deles definidos como a combinacao da frequencia do termo nodocumento com a sua frequencia inversa. Como explicamos antes, em uma abordagemsimples os termos dos vetores consulta e documentos seriam simplesmente 0 ou 1. Porempode ser representados por pesos : o j−esimo termo do vetor do documento Di sera dadopela multiplicacao da frequencia do termo no documento pela frequencia inversa do termona colecao:
dij = tfij × idfj (2.3)
Na equacao 2.5 cada termo sera representado pelos seu peso especıfico dado pelacombinacao tf−idf . Os pesos sao calculados pelo Inverse Document Frequency ( IDF ).Para tanto, considere as seguintes definicoes:
d = numero total de documentost = numero de termos distintos na colecao de documentos3
tfij = numero de ocorrencias do termo tj no documento Di, chamada defrequencia do termo.
dfj = numero de documentos nos quais ocorre o termo tj chamada de frequenciado documento.
idfj = log( ddfj
) = numero de ocorrencias do termo tj no documento Di, chamadade frequencia do termo.
Observe que com a frequencia interna de documento servindo de peso para ostermos, palavras muito frequentes em todos os documentos se enfraquecem ou somemnaturalmente. Por exemplo, os artigos e conetivos geralmente sao comuns a todos osdocumentos e portanto o peso delas vale log(d/d) = 0.
Conforme (GROSSMAN; FRIEDER, 2004), muitas pesquisas com pesos de ter-mos foram feitas para melhorar a combinacao basica tf − idf . Das diversas variacoesestudadas, a formula a seguir foi identificada como de boa performance.
wqj =(log tfij + 1.0) ∗ idfj∑t
j=1[(log tfij + 1.0) ∗ idfj]2(2.4)
2w: peso do j-esimo termo3Esse numero geralmente e considerado apos a retirada das stop-words e apos a aplicacao de um stem-
mer, que reduz as palavras aos seus radicais, e eventualmente um processo para reconhecer locucoes verbaise nominais.
16
Utilizaremos para representar cada documento Di um vetor (di1, di2, ..., dit) detamanho t que e o numero de termos distintos da colecao de documentos. A consulta Csera representada por um vetor (cw1, cw2, ..., cwt), onde cada ındice indica o peso de cadatermo presente. Um coeficiente de similaridade (SC) entre uma consulta e um documentoe definida pelo produto escalar dos dois vetores:
SC(C, Di) = ~C · ~Di =t∑
j=1
cwj × dij (2.5)
Segundo (GROSSMAN; FRIEDER, 2004), existem muitas maneiras de compararum vetor consulta e um vetor documento. Ele as apresenta e discute em seu livro. A maiscomum e a medida do cosseno entre os angulos formados pelos vetores do documento eda consulta:
SC(C, Di) =
∑tj=1 wqjdij√∑t
j=1(dij)2∑t
j=1(wqj)2(2.6)
Na equacao da medida do cosseno, dado que aparece no seu radical o comprimentodo vetor consulta e o comprimento do vetor documento, ocorre uma normalizacao. Como produto interno simples, um documento muito longo pode se parecer mais relevantepelo simples fato de ter mais termos em comum com a consulta. A medida do cossenoproporciona portanto uma normalizacao por medir apenas a diferenca de angulos e nao aprojecao relativa entre dois vetores.
O coeficiente de Dice e definido como:
SC(C, Di) =2
∑tj=1 wqjdij∑t
j=1(dij)2 +∑t
j=1(wqj)2(2.7)
O coeficiente de Jaccard e definido como :
SC(C, Di) =
∑tj=1 wqjdij∑t
j=1(dij)2 +∑t
j=1(wqj)2 −∑tj=1 wqjdij
(2.8)
2.1.3 Modelos probabilısticosSegundo (GROSSMAN; FRIEDER, 2004), um modelo probabilıstico calcula o
coeficiente de similaridade entre uma consulta e um documento como a probabilidadeque o documento va ser relevante a consulta, o que reduz o problema da relevancia a umproblema estatıstico.
Todo o trabalho na recuperacao probabilıstica deriva da ideia de estimar o pesode um termo baseado em quao frequente um documento aparece ou nao em documentosrelevantes ou nao. Nesse caso, usa-se probabilidade Bayesiana.
2.2 UtilitariosMuitos diferentes utilitarios estao envolvidos diretamente com as estrategias de
recuperacao ou com a melhoria de seus resultados. A maioria dos utilitarios retira ouacrescenta termos a consulta original, numa tentativa de refina-la. Outros refinam o focoda consulta, atraves de subdocumentos ou passagens, ao inves de documentos completos.
17
A chave e que cada uma desses utilitarios sao componentes ”plugaveis”, que trabalhamcom qualquer estrategia de recuperacao. Esse utilitarios seriam:
• Relevance Feedback: Os primeiros N documentos encontrados pela consulta inicialsao considerados relevantes. Eles sao considerados relevantes por escolha manualou por presuncao arbitraria. Eles sao ordenados por uma dentre varias tecnicas.Os t termos mais frequentes dos documentos sao acrescentados a consulta inicialproduzindo um mecanismo de reforco.
• Clustering: Documentos sao agrupados de forma automatica ou manual. Acomparacao da consulta apenas e feita contra grupos que se deveriam conterinformacao relevante. E um limite ao espaco de busca, e tenta-se evitar documentosirrelevantes antes que a busca se inicie.
• Passage-base Retrieval: A premissa e que documentos mais relevantes tem pas-sagens irrelevantes e que a porcao relevante e um trecho concentrado. Assim, asconsultas sao feitas contra trechos, sobrepostos ou nao, e os resultados de cadapassagem sao combinados em um coeficiente de similaridade. O tamanho de cadapassagem pode ser fixo ou variavel, conforme a implementacao. Ou entao o docu-mentos pode ser dividido em sentencas, paragrafos, ou qualquer divisao natural dodocumento.
• Parsing (stemming, processamento de nomes): Simplesmente casar termos nemsempre da bons resultados. A identificacao de termos e computacionalmente maisfacil do que o uso de operadores de proximidade. Regras de analise ou listas saoutilizados para identificar locucoes validas como ”Universidade Catolica de Pelo-tas”. Essas locucoes sao tratadas como termos isolados. Outras tecnicas de analiseevitam prefixos e sufixos (stemming) para buscar identidades entre termos que com-partilham a mesma raiz. Essa ultima tecnica aparece em
• N-grams : a consulta e particionada em n-grams (com ou sem sobreposicao den caracteres). Os n-grams sao utilizados para casar consultas com documentos.Procura-se obter um casamento ”fuzzy”que seja resistente a erros de digitacao,pronuncia ou de recuperacao OCR. Outra vantagem do n-grams e a independenciade lıngua.
• Thesauri: Thesauri sao gerados automaticamente do texto ou criados de forma ma-nual. A chave e nao apenas criar o Thesaurus, mas usa-lo para expandir a consultaou a representacao do documento para melhorar a recuperacao.
• Redes Semanticas: Sao hierarquias de conceitos na qual conceitos individuais saoconectados com outros. A forca do relacionamento e atribuıda a associacao. Umarede assim e a Wordnet4, entre outras. Foram feitas tentativas de se construir ontolo-gias assim automaticamente. O desafio e utilizar essa rede para expandir a consultae os documentos e aumentar a taxa de recuperacao de documentos relevantes.
• Regressao analıtica: Tecnicas estatısticas sao empregadas para identificarparametros que descrevem caracterısticas que identificam determinado documento.
4http://wordnet.princeton.edu/
18
Essas caracterısticas podem ser empregadas em uma regressao para identificar oparametro exato que refina uma medida de similaridade
2.3 Tarefas da Recuperacao de InformacoesA recuperacao de informacoes e uma designacao que passou a abranger diversas
tarefas, muitas delas originalmente vinculadas com Inteligencia Artificial, como Respon-dendo Perguntas, que passaram a ser abordadas pelo enfoque da IA, a partir de tecnicasmais simples e adequadas a grandes corpos de textos.
Muitas tarefas passam a se incorporar a area conforme sao propostas nos encontrosanuais da TREC e CLEF. E famosa a inclusao do Respondendo Perguntas, antes tarefa daInteligencia Artificial e da Linguıstica Computacional no TREC de 1999. As abordagensinovadoras para esse problema trazidas para o TREC, baseadas em caracterısticas super-ficiais e em analisadores leves (CHAKRABARTI, 2004) trouxeram novas perspectivaspara o problema de encontrar passagens com respostas para determinada pergunta.
Nas conferencias TREC, todas atividades assessorias a RI, sao abordadas e passamtambem a figurar academicamente como ”tarefas”da area. Na listagem abaixo, descreve-mos algumas dessas tarefas:
• Recuperacao de documentos e a tarefa tradicional da Recuperacao de Informacao.
• Agrupamento de documentos e a sua classificacao. Pode ser tanto um filtro deSPAM, como roteamento de emails de queixas em uma organizacao publica (go-verno, servicos, energia ou telefonia) de grande porte.
• Recuperacao de documentos falados.
• Recuperacao de paginas WEB, imagens, vıdeos e musicas sao tambem considera-das sub-areas, embora a dificuldade de caracterizar pecas de multimıdia e medir suasimilaridade sejam quase um mundo a parte.
• Sumarizacao de Textos: os sistemas de sumarizacao buscam a criacao automaticade um resumo coerente de um texto dado.
• Respondendo Perguntas: sao os que buscam respostas precisas, ou a identificacaode trechos que as contenham, a perguntas formuladas em linguagem natural.
• Tarefas Assessorias:
Desempenho em arquiteturas multicore.
Tipos de ındice e sua manipulacao (compactacao).
• Psicologia e cognicao: como o usuario interage com a interface de consulta, quaishipoteses formula.
• Consultas: como melhorar consultas, como integrar e levar em consideracao dadosdo contexto do usuario.
• Recuperacao cruzada e a consulta em uma lıngua e a recuperacao de documentosrelevantes em outra.
19
A producao de pesquisa na area de IR varia conforme a epoca e as tarefas pro-postas pela organizacao do encontro. Na imagem 3.2 expomos como evolui a producaoapresentada no TREC conforme as areas ao longo da primeira decada de existencia doevento.
Figura 2.2: Acompanhamento Anual da Pesquisa no TREC ate 2001
20
3 O PROCESSAMENTO DA LINGUAGEMNATURAL
De acordo Daniel Jurasky (JURAFSKY; MARTIN, 2000) Processamento da Lin-guagem Natural (PNL) e a area da computacao que lida com a lıngua humana falada ouescrita. Isso envolve tudo, desde a contagem da palavras em um texto, ate hifenizacao,correcao ortografica , transcricao ou sıntese de fala, ate sistemas complexos para res-ponder perguntas ou tradutores automaticos1. A Linguıstica Computacional, segundo(GRISHMAN, 1986), e estritamente o estudo de sistemas computacionais para o enten-dimento da linguagem humana, incluindo-se aı a testagem de gramaticas propostas porlinguistas2.
Ainda de acordo com Jurafsky campos historicamente separados - Processamentoda Linguagem Natural, Reconhecimento de Fala, Linguıstica Computacional, Psico-linguıstica Computacional - comecaram a se combinar. A disponibilizacao de ferramentascomerciais e a necessidade de tecnicas baseadas em linguagem para a Web proporcionamum grande estımulo. A disponibilidade de grandes corpora facilita o estudo de modelosestatısticos em todos os nıveis, da fonetica ao discurso.
O conhecimento para lidar com linguagem pode ser separado em seis categoriasdiferentes:
• Fonetica e Fonologia - O estudo de sons da lıngua falada.
• Morfologia - O estudo de partes significativas das palavras.
• Sintaxe - O estudo de relacionamentos estruturais entre as palavras.
• Semantica - O estudo do significado das palavras.
• Pragmatica - O estudo de como a linguagem e utilizada para atingir objetivos dosfalantes.
• Discurso - O estudo de unidades linguısticas maiores do que um enunciado3
1A traducao automatica e a primeira e eterna tarefa do PNL, e segundo Maria das Gracas Volpe, aPNL comecou pelo final. A estrategia para essa area, segundo essa pesquisadora, deve ser a de resolverproblemas menores, capazes de no futuro compor uma solucao total adequada.
2Ate hoje nao foi possıvel determinar qual gramatica reconhece todas as formulacoes aceitas por falantesnaturais
3Enunciado (utter) e a unidade de fala. Pode ser palavra, frase, oracao, iniciado e terminado por silencioe caracterizado pela entonacao que enfatiza o significado que se deseja transmitir
21
A fonetica e a fonologia se dedica a lıngua falada, que veremos mais adiante, tempor fundadas razoes, motivos para ter um tratamento em separado. O mais obvio deles, ea separacao entre palavras. A separacao de palavras e uma tarefa do texto escrito no casodo chines e japones (JURAFSKY; MARTIN, 2000).
A morfologia e a sintaxe geralmente podem ser estudadas dentro do ambito dotexto escrito. A semantica e mais do que ela, a pragmatica, dependem de fatores extra-texto4.
3.1 O Tratamento da Linguagem pelo ComputadorAs tecnologias para lidar com os problemas da PLN se baseiam em modelos for-
mais ou representacoes de conhecimento de linguagem, fonetica, morfologia, sintaxe,semantica, pragmatica e discurso. Um pequeno numero de modelos, que inclui maquinasde estado, sistemas de regras formais, logica, e probabilidade, sao utilizados para capturaresse conhecimento.
Os automatas finitos (JURAFSKY; MARTIN, 2000) apareceram em 1950 a partirdo modelo de computacao de Turing. A maquina de Turing podia ler uma fita finita desımbolos, podendo alterar seu estado ou o estado da fita. Os automatas finitos nao podiaminteragir com a sequencia de sımbolos de entrada.
Inspirados no trabalho de Turing, McCulloch e Pitts construıram um modelo deneuronio que podia ser descrito em termons de logica proposicional. O neuron de McCul-loch e Pitt era um dispositivo binario que recebia estimulo e podia chavear entre ligado edesligado conforme determinados limiares. Em 1951 Kleene definiu o automato finito ea expressao regular para o neuronio de McCulloch/Pitts e provou sua equivalencia.
Outra contribuicao relevante do modelo de automato finito foi o aparecimento dainterpretacao de expressoes regulares dentro de editores, com editor ed de Ken Thomp-son. O celebre programa ELIZA, que simulava um psicoterapeuta rogeriano 5, funcionavaatraves de uma cascata de substituicoes de expressoes regulares.
Problemas de morfologia sao aqueles nos quais se busca entender como as pala-vras se subdividem ou se flexionam para indicar variacoes. Sabe-se que ”peixe”nao temfeminino, mas acrescentando-se ”s”temos o plural. O analisador morfologico deve sercapaz de separar as sılabas de uma palavra, alem de identificar prefixos, sufixos, flexoes ecomposicoes.
Transdutores Finitos 6 (TF) sao extensoes de maquinas finitas que podem ge-rar sımbolos. TF trabalham com a morfologia de 2 nıveis propostas por Koskenniemi(1983). Uma morfologia de 2 nıveis representa uma palavra como 2 fitas, uma lexica, aconcatenacao dos morfemas que compoem a palavra e uma superficial que representa aescrita final da palavra.
Um transdutor mapeia sımbolos de um conjunto para outro. Um transdutor finitofaz isso atraves de um automato finito. Ao passo que um automato finito AF) define umalinguagem formal atraves de um conjunto de cadeias de caracteres, ao passo que o TFdefine a relacao entre dois conjuntos de cadeias de caracteres.
A comunicacao humana e muito complexa e esta longe de ser adequadamente
4Para lidar com a pragmatica o agente de ser provido de conhecimento acerca do mundo, de preferenciaconhecimento adquirido em primeira mao atraves de sentidos.
5Tipo de terapia criada por Karl Rogers, chamada de nao-diretiva6Do ingles Finite State Transducers (FST), extensoes de Finite State Automata (FSA).
22
descrita e muito menos emulada ou entendida em tempo computacionalmente aceitavel.Na secao seguinte examinaremos essa questao para formamos uma ideia dos nıveis emque cada tarefa do PNL atua.
O algoritmo de Potter e eficiente para fazer stemming, retirar sufixos e prefixos, ee preferıvel em aplicacoes de IR, onde a analise morfologica exata nao e necessaria.
3.2 ComunicacaoFaremos um breve relato do processo de comunicacao como encontrado em (JU-
RAFSKY; MARTIN, 2000). Veremos que a comunicacao (vocalizada ou escrita) e frutode um processo de calculo que envolve alem do conhecimento dos significados e doscontextos, o conhecimento que se tem acerca do ouvinte. A audiencia e determinante naescolha dos termos e da mensagem para o emissor e o receptor inclui na decodificacao damensagem o conhecimento acerca do emissor e o que ele julga que o emissor saiba acercado receptor. Um episodio tıpico de comunicacao entre o falante E e o receptor R, no qualo falante faz um enunciado M usando palavras P, e composto de 7 processos:
• Intencao: O emissor decide que existe uma proposicao P que deve ser dita ao re-ceptor R.
• Geracao: O falante planeja um modo de transformar a proposicao P em uma ex-pressao vocal, incluindo aı seu conhecimento acerca do ouvinte, que aumentara achance da proposicao ser entendida.
• Sıntese: O falante produz a realizacao fısica das palavras escolhidas. Isso pode serfeito em tinta, voz, imagens ou outro meio.
• Percepcao: O ouvinte reconhece a producao M e a separa em palavras Wi. Nadecada de 90, com o aumento do poder dos computadores de mesa e dos algoritmosde classificacao 7 essa tarefa se tornou viavel.
• Analise: O ouvinte deduz que M tem diversos significados P1, P2..Pn. A analisetem tres partes: sintatica, semantica e pragmatica.
Na analise sintatica e construıda uma arvore que auxilia na identificacao corretados termos. Locucoes podem ser identificadas, pois as arvores onde os termossao considerados individualmente sao descartadas no processo de construcao. Porexemplo em ”Estou vendo a pedra”, ”Estou vendo”sera etiquetado com V (verbo),”pedra”e ”eu”como ”S”(Substantivo).
Na analise semantica a mensagem agora e traduzida em forma de regras logicasvinculadas nas quais ja aparecem identificados objetos e relacionamentos. Porexemplo:
V er(Pedra, Agora)
Na analise pragmatica, o enunciado sera considerada dentro do seu contexto.”Estou vendo a pedra”significa coisas diferentes para um alpinista ou um joalheiro.
7Algoritmos como o Support Vector Machine (SVM) combinados com a utilizacao de tecnicas de nucleopermitiram o reconhecimento de escrita e de voz
23
• Eliminacao da Ambiguidade: O receptor R deduz que E pretendia transmitir P i(onde no caso ideal Pi = P ). A maioria dos falantes nao e ambıgua, mas quase to-das as expressoes vocais tem varias interpretacoes. A comunicacao funciona porqueo ouvinte conclui qual interpretacao provavelmente o falante pretendia transmitir.No nıvel da eliminacao de ambiguidade (bem como no da geracao) foi mencionadoque a probabilidade estaria envolvida.
• Incorporacao: Na incorporacao o ouvinte decide acreditar ou nao em Pi. Um agentetotalmente ingenuo pode acreditar em tudo que ouve, ao passo que um agente so-fisticado trata o ato da fala como evidencia de Pi e nao como confirmacao dela.
A descricao das etapas da comunicacao humana lembra a pilha de protocolosTCP/IP e a OSI, na qual cada nıvel no emissor prepara ou calcula de alguma forma amensagem, para que a contra-parte de mesmo nıvel no receptor possa recebe-la e pro-cessa-la adequadamente. Para enviar um pacote no mundo TCP/IP, precisamos envolver oconteudo transmitido em diversos envelopes de marcacoes para que ocorra a comunicacaode forma segura. No entanto se examinarmos o texto da figura 3.1 retirado de (CUN-NINGHAM, 2000) com as marcacoes criadas pelo reconhecedor de entidades do GATE,veremos que o texto marcado e maior que o original. Se acrescentarmos marcacoessintaticas, semanticas (extraıdas de ontologias) e pragmaticas (oriundas de informacoesacerca do ambiente), concluiremos que a mensagem M enviada representa o resumo maiseconomico do enunciado P que se deseja transmitir.
Figura 3.1: Texto com marcadores criados pelo reconhecedor de entidades do GATE
Portanto as semelhancas entre a comunicacao humana e dos computadores saobem superficiais. Existem apenas aproximacoes para a gramatica natural (RUSSELL;
24
NORVIG, 2003), aquela que reconheceria todas as producoes aceitas como validas pelosfalantes. Tambem a eliminacao da ambiguidade e um desafio teorico que ainda nao foiresolvido, computacionalmente difıcil, e para propositos praticos imediatos, nao deve serconsiderado.
Como exemplo da dificuldade em lidar com a ambiguidade, considere a seguintefrase: ”Eu nunca disse que ela roubou o dinheiro”. A seguir listamos a mesma frase coma enfase vocal marcada em negrito:
Eu nunca disse que ela roubou o dinheiro. (Mas alguem pode ter dito)Eu nunca disse que ela roubou o dinheiro. (Eu nunca disse isso mesmo)Eu nunca disse que ela roubou o dinheiro. (Mas posso ter deixado subentendido)Eu nunca disse que ela roubou o dinheiro. (Eu disse outra coisa)Eu nunca disse que ela roubou o dinheiro. (Mas talvez outra pessoa tenha roubado)Eu nunca disse que ela roubou o dinheiro. (Ela pode ter pego emprestado)Eu nunca disse que ela roubou o dinheiro. (Outra coisa talvez)
O significado que se deseja transmitir se encontra marcado na voz. No texto escritoo emissor usara outros recursos para desfazer ou diminuir a ambiguidade.
A complexidade total da comunicacao humana nao esta ainda disponıvel para serutilizada pela RI do mesmo modo que nao esta disponıvel para traducao automatica. Epreciso conhecer as tarefas mais simples primeiro, o que faremos na secao a seguir.
3.3 As Tarefas do Processamento da Linguagem NaturalA traducao automatica e considerada por muitos autores (SILVA et al., 2007) o
marco inicial do PNL. Apos uma apresentacao inicial exitosa que traduziu em 1952 umtexto de 50 frases selecionadas sobre quımica do russo para o ingles, houve um perıodoentusiasmado de pesquisas. Os resultados seguintes entretanto nao foram tao exitosos. Aseguir transcrevemos um exemplo encontrado em (SILVA et al., 2007) da ma qualidadedos primeiros sistemas automaticos de traducao.
(In, At, Into, To, For, On) (last, latter, new, latest, lowest, worst) (time, tense)for analysis and sinthesis relay-contact electrical (circuit, diagram, scheme)parallel-(series, successive, consecutive) consistent (connection, junction,combination) (with,from) (success, luck) (to be utilize, to be take advantageof) apparatus Boolean algebra.
O sistema simplesmente listava todas as possibilidade de traducao de cada pala-vra do russo para o ingles criando um bloco ilegıvel de palavras. Nao existia nenhumanalisador sintatico e lexico capaz de selecionar as melhores alternativas de cada termo.
As tarefas do PNL se diversificaram a medida que a area amadureceu, encontroue procurou enfrentar problemas em todos os nıveis da producao da linguagem. A lista aseguir foi montada de acordo com (CUNNINGHAM, 2000) e (SILVA et al., 2007):
• Transcricao da fala.
• Classificacao (etiquetar) automaticamente as unidades do texto segundo classes per-tinentes a tarefa: morfossintaticas, sintaticas ou semanticas.
25
• Mapear representacoes da LN para representacoes sintaticas ou discursivas, e dessaspara LN.
• Sumarizar texto para facilitar a sua leitura.
• Traducao automatica
• Geracao de texto.
• Reconhecer entidades nomeadas.
• Interfaces naturais para bancos de dados (como BASEBALL) e sistemasrespondendo-perguntas.
• Geracao de voz.
• Aprendizado de segunda lıngua e sistemas tutores
• Automacao de tarefas administrativas (agenda, encontros, viagens).
• Programacao automatica(NLPQ e SAFE).
• Filtragem e roteamento de textos.
• Comparacao, versionamento e ferramentas de autoria.
• Determinacao de autoria.
• Ferramentas de acessibilidade.
Nos mais de 50 anos que nos separam das experiencias pioneiras de traducao,inumeros programas e pacotes foram escritos por geracoes de pesquisadores que resulta-ram em progressos razoaveis. Alguns desses programas, como o Lucene, alcancaram umgrau de maturidade para sua utilizacao tanto comercial e academica. Outros, foram dispo-nibilizados para a comunidade com codigo aberto, para poupar aos demais pesquisadores(e ao autor) o trabalho de reescrever determinados programas consagrados ou ainda servircomo ambiente padrao de experimentacao. Veremos alguns esses programas no capıtulo4.
3.4 Arquitetura de um sistema PLNSegundo (SILVA et al., 2007), a arquitetura de um sistema computacional que
processa lıngua natural pode variar de acordo com a especificacao da aplicacao. Como efrequente na area do PLN, a maioria dos algoritmos utilizados sao onerosos, e portanto aregra e a customizacao caso a caso. Um sistema completo, como o da figura da pagina 27exibe a maioria dos modulos que se pode empregar.
Descrevemos a seguir os componentes do sistema da figura 3.2.
• Analisador Lexico ou scanner e responsavel pela separacao e identificacao dostokens da linguagem e a sua associacao a atributos ou tracos gramaticais ousemanticos com base em consulta ao Lexico. Pode ser necessario uma etapa deanalise morfologica anterior ou concomitante
26
• Analisador Sintatico ou parser e a etapa responsavel pela construcao de um es-trutura sintatica valida para a sentenca de entrada, tambem chamada de estruturaprofunda. Em se tratando de lıngua natural adota-se uma gramatica ”parcial”queabranja as construcoes validas para a area de interesse. Os formalismos mais sim-ples sao os mais eficientes.
• Analisador Semantico e responsavel pela interpretacao dos componentes dasentenca e dela propria. E necessario um conhecimento do domınio. A frase ”Joaocomeu a manga”tera as seguintes representacoes sintatica e semantica:
s(sn(substpr(Joao)),sv(vtd(comer,passado,3ps),sn(det(o),subst(manga))
acao(comer,agente(anim(Joao)),objeto(comest(manga)))
A sentenca ”Joao costurou a manga”tera estrutura profunda semelhante a acima,trocando o terminal ”comeu”por ”costurou”. Formalismos de analise semanticadiferem dos de analise sintatica. O exemplo acima foi construıdo com Logica dePredicados.
• Analisador do Discurso, considerando a modalidade multi-sentencial, busca o sig-nificado de uma sentenca considerando os significados das sentencas proximas, an-teriores ou posteriores. Para o texto ficar elegante, e comum o uso de anaforas, quedevem ser resolvidas. O analisador de discurso em geral estende a representacaosemantica com anotacoes sobre as figuras de discurso.
• Analisador Pragmatico e a interpretacao da intencao do falante dentro do con-texto da comunicacao. ”Voce quer mais prazo?”pode ser interpretado como umagentileza ou como uma cobranca.
27
Figura 3.2: Arquitetura de um sistema PLN segundo (SILVA et al., 2007)
28
4 FERRAMENTAS PRONTAS
A reutilizacao e importante tanto pela economia, como pela base comum que criade padroes e procedimentos entre profissionais e pesquisadores de qualquer area. A dispo-nibilidade de ferramentas e bibliotecas prontas, preferencialmente escritas todas em umamesma linguagem ou ambiente, permite irmos mais longe, podemos projetar e construirsistemas a partir da combinacao de partes menores prontas.
Para a pesquisa, alem da economia, o reaproveitamento facilita a comparabili-dade, a discussao dos trabalhos cientıficos em bases comuns, alem do acumulo de umasequencia de producao cientıfica de varios autores sobre uma mesma base de trabalhos.
Selecionamos ferramentas escritas em Java ou com interface em Java pela facili-dade de integra-las, pela possibilidade de utiliza-las tanto em aplicacoes WEB como emaplicacoes standalone, e pela quantidade de bibliotecas – nativas ou nao – ja disponıveisnessa linguagem. Java tem uma colecao nativa de bibliotecas bem variada e solida e aindaesta experimentando evolucao, fruto da contribuicao combinada da sua comunidade deusuarios.
Um exemplo da convergencia da pesquisa para o mundo Java e o projeto WEKA –Waikato Environment for Knowledge Analysis – da Universidade de Waikato, que iniciousendo escrito em C e em TCL/TK. A partir de 1993 passou a usar Java e hoje o WEKA ea base de varios de outros projetos, colaboradores escrevem extensoes para ele e serve debase material para pesquisa em centenas de trabalhos.
Examinaremos um motor de recuperacao de informacoes chamado Lucene e qua-tro frameworks de PNL: Gate, MALLET, Lemur e Simmetrics. Reunindo-os, dispo-mos de uma razoavel plataforma de trabalho para conhecer estudar e testar estrategias decombinacao de PNL e RI.
Essas quatro biblioteca nao esgotam o mundo das bibliotecas publicas para PNL,muitas mais existem e algumas dessas outras estao listadas no anexo A. ParafraseandoGerald Salton, somos obrigados a gastar o tempo que dispomos com o mais promissor efacilmente disponıvel e ignorar o resto.
O Lucene e uma biblioteca especializada na criacao de ındices de documentos eindexacao e casamento de consultas. Ele precisa ser associado a outros programas parachegarmos a ter um programa de busca completo como o Yahoo ou o Google.
o Simmetrics e uma biblioteca especializada em metricas para palavras. Entre asprincipais disponıveis, de interesse para PLN, destacamos a distancia de Lewenshtein eo coeficiente de Dice. Interessante observar que a maioria dos membros dessa bibliotecae direcionada para aplicacoes em biologia e que a analise de sequencias de DNA - quee referido como o livro da vida - vem buscar apoio exatamente na mesma fonte que a
29
Linguıstica Computacional.Ja o Lemur e referido como Lemur Toolkit ou Toolkit nos papers dos pesquisado-
res da Universidade dede Massachussetts e distribuıdo juntamente com o motor de buscasIndri.
Listamos a seguir os sites dos produtos e ( frameworks) mencionados neste traba-lho, tal como disponıveis em 2008.
Tabela 4.1: Lista e localizacao de recursos integraveis em projetos de IR e NLPNome URL DescricaoWEKA http://www.cs.waikato.
ac.nz/ml/weka/WEKA e um produtovoltado para aprendi-zado de maquina
GATE http://gate.ac.uk/ GATE e um produtovoltado para engenhariade texto
Lucene http://lucene.apache.org/
Lucene e um indexadorde documentos e con-sultas
LingPipe http://www.cs.waikato.ac.nz/ml/weka/
LingPipe e uma bi-blioteca para proces-samento de linguagemnatural
Simmetrics http://www.dcs.shef.ac.uk/˜sam/simmetrics.html
Simmetrics e uma bibli-oteca aberta de metricase medidas de similari-dade
Lemur http://www.lemurproject.org/tutorials/
Lemur e uma bibliotecade PNL da Universi-dade Carnegie Mellon
Esses programas foram escritos para a lıngua inglesa. Possivelmente sera ne-cessario criar ou adaptar modulos para lidar com a lıngua portuguesa, se nao existirem.Porem depois de vencida essa fase, estara disponıvel para nosso idioma a mesma plata-forma de trabalho.
4.1 LuceneLucene e o nucleo de um engine de busca textual. No Lucene nao esta incluıda
a interface nem o crawler. Foi criado em 2000 por Douglas Cutting (GOSPODNETIC;HATCHER, 2005), doado para a Fundacao Apache e disponibilizado sob sua licenca. Suaaceitacao e grande e tem portes para Python, C++, C##, Ruby, Perl, Delphi e PHP. Suaaceitacao tambem ocorre na comunidade cientıfica. Chakrabarti, em seu artigo de 2004para a WebKDD (CHAKRABARTI, 2004) o escolheu como maquina de busca padraopara comparacoes.
Partindo da ideia de um documento contem campos de texto, e sendo indepen-dente de tipo de arquivo, Lucene e capaz de indexar arquivos em diversos formatos: PDF,
30
HTML e Microsoft Word. E um biblioteca de indexacao e busca e nao contem robos debusca (crawler) nem parser de HTML.
Para completar o Lucene, que afinal pode ser visto como um banco de dados de-dicado a buscas textuais, existem dois outros projetos na Fundacao Apache: o Nutch queacrescenta funcoes de busca e parsing de HTML e o Solr que e um servidor WEB debusca completo baseado no Lucene.
Os principais conceitos para comecar a entender o Lucene sao:
Tabela 4.2: Conceitos Basicos do LuceneConceito ExplicacaoAnalyser E a classe que prepara o texto para indexacao. Ingles e
lınguas latinas podem usar a StandardAnalyzerPayloads Cadeias de bytes carregadas com um ou mais posicoes de
termosSnowball Stemmer Colecao de stemmers escritos por terceirosDocument Documento e um registro no ındice. Um documento tem
uma lista de campos, cada campo com um nome e um valortextual.
Term Termo e a unidade de indexacao, que em lınguas ocidentaiscorresponde a uma palavra.
TermEnum TermEnum e utilizado para enumerar todos os termos emum ındice para um dado campo, a despeito de quais do-cumentos em que ocorra o termo. Algumas consultas saoimplementadas por enumeracao de termos que seguem umpadrao, ou atraves de operacoes OR a partir da enumeracao.
TermDocs Ao contrario de TermEnum, TermDocs sao utilizados paraidentificar quais documentos contem um dado Termo.TermDocs tambem da a frequencia do termo no documento.
TermFreqVector Um vetor de Frequencia de Termos e uma estrutura de dadoscontendo termos e frequencia de determinado documento,informacao que pode ser recuperada atraves do objeto In-dexReader apenas quando Vetores de Termos sao armaze-nados durante a indexacao.
4.1.1 Principais Pacotes do LUCENEOs principais elementos da API do Lucene sao expostos na tabela 4.3 da pagina
36.Os pacotes listados na tabela sao da versao 2.4 do Lucene. Observa-se a integracao
da ferramenta de indexacao Lucene com produtos como WordNet e Wikipedia.
4.2 MALLETMALLET4 e uma biblioteca em Java para Recuperacao de Informacoes criada na
Universidade da Pennsilvania por Andrew McCallun alem de diversos colaboradores. A4Machine Learning for Language Toolkit
31
lista de patrocinadores e igualmente extensa.
4.2.1 Filtros de Importacao do MALLETPara o MALLET os dados sao uma lista de ”instancias”. Uma instancia pode ter
um nome e uma classe (se o problema for de classificacao). Se o problema for identificar alıngua de uma pagina WEB, a instancia pode consistir em um vetor de palavras contadas,o nome seria a URL e a classe a lıngua ja identificada, ou por identificar.
4.2.2 Classificadores do MALLETUm classificador e um algoritmo que pode fazer disitincoes entre classes fixas tais
como ”spam”ou ”nao-spam”baseando-se em exemplares ja classificados. MALLET trazdiversos classificadores entre os quais Naıve-Bayes, Maxima Entropia (C-45) e Arvoresde Decisao. Tambem traz pacotes para avaliar os modelos gerados, fazendo relatoriosatraves matriz de confusao e testes de cross-validation. Todos os algoritmos tem exem-plos para auxiliar sua compreensao.
4.2.3 Principais Pacotes do MALLETOs principais pacotes disponıveis no MALLET sao expostos na tabela 4.4 da
pagina 37.
4.3 GATEGATE e acronimo de General Architecture for Text Engeneering foi criado por
Hammish Cunningham e seus colegas na Universidade de Sheffield tendo em vista, nocampo do PNL, o mesmo problema encontrado no campo da RI: a falta de um ambienteintegrado e pronto para a utilizacao, com alto grau de automacao, que incorpore algorit-mos ja aceitos e que nao precisem ser baixados e portados, recompilados e depurados acada experimento e que permita a conducao de experiencias repetitivas e documentadasde novos modulos6.
• Analise Morfologica
• Reconhecimento de Entidade Nomeada
• Extracao de Informacao
• Etiquetamento
• Co-referencia (resolucao de anaforas)
• Analise de Texto
Na figura 3.1, encontrada em 3.1, observamos uma arvore de analise sintaticaelaborada pelo GATE.
6Nesse aspecto, o autor se inspirou em MatLab e Mathematica para tentar criar seu proprio ambiente deexperimentacao de PNL
32
Figura 4.1: Analise sintatica com o GATE
4.4 LemurLEMUR e uma biblioteca e associada a um motor de recuperacao chamado IN-
DRI. As principais caracterısticas de LEMUR seriam:
• Caracterısticas Gerais
Linguagens de consulta usando InQuery e Indri,
Recuperacao XML e estruturada,
Utilizada em varias colecoes de testes: TREC CDs 1 a 5, wt10g, RCV1, gov1e gov2,
Indexacao de paginas WEB,
Interface para Windows, Linux e WEB,
Recuperacao de Informacao Distribuıda e agrupamento de documentos,
Codigo escrito em C++, 6 anos de uso por uma comunidade de usuarios epesquisadores
Interface em Java e C,
Recuperacao de Informacao Distribuıda e agrupamento de documentos.
• Indexacao
Diversos metodos de indexacao conforme o tamanho da colecao,
Suporte nativo para ingles, arabe e chines,
Porter e Krovetz stemmers,
Indexacao incremental,
33
Suporte para texto do TREC, WEB, HTML, XML, PDF, MBox, MS Word eMS PowerPoint,
Indice inline e offset para anotacoes de texto (POS e Entidades Nomeadas),
Indexa atributos de documentos.
• Recuperacao:
Suporte para a maioria dos modelos tais como Espaco Vetorial, KL-Divergencia, Indri, Tf-Idf, Okapi e InQuery,
Realimentacao de relevancia e Pseudo-Realimentacao de relevancia7,
Expansao de wildcards (com Indri),
Recuperacao cruzada de linguagem,
Expansao de wildcards (com Indri),
Amaciamento atraves de Dirichilet apriori e Cadeias de Markov,
Suporta apriori arbitrario de documentos (Page Rank, URL depth, usw)
4.5 SimmetricsSimmetrics e uma biblioteca Java criada na Universidade inglesa de Sheffield es-
pecializada em metricas. As metricas, embora isoladamente nao formem um aplicativocompleto sao pecas basicas utilizadas em outros projetos. A distancia de Lewenshteinencontra utilizacao em um modo sofisticado de correcao de erro, tanto na lıngua faladacomo na escrita. Na Simmetrics existem metricas de RI, como o Coeficiente de Dice. Eprincipalmente varias metricas de distancia de edicao entre strings para uso na Biologia,em genetica.
1. Distancia de Hamming: e o numero de bits de diferenca entre duas sequencias debits.
2. Distancia de Lewenshtein: e a distancia de edicao entre duas sequencias de carac-teres, contando da seguinte forma: copia de uma string para outra (custo 0), apagarum caractere na string 1 (custo 1), inserir um caractere na string 2 (custo 1) e subs-tituir um caractere por outro (custo 1). O algoritmo utiliza programacao dinamica.
3. Distancia de Needleman-Wunch: tambem conhecida como Sellers, e uma extensaode Lewenshtein na qual cada insercao extra (gap) custa um valor arbitrario.
4. Distancia de Smith-Waterman: e outra extensao da de Lewenhstein, onde existemduas funcoes ajustaveis, uma para a copia (um custo variado por tipo de copia) eum custo por operacao de ”gap”(insercao ou delecao).
5. Distancia de Gotoh: uma extensao da distancia de Sith-Waterman, que permitecustos de ”gap”baseados no comprimento da sequencia l. Utilizado em biologia,para alinhamento de sequencias de DNA
7Para Relevance and pseudo-relevance feedback
34
6. Distancia de Bloco ou L1: distancia a se percorrer no problema dos blocos dacidade, no qual nao se pode percorrer diagonais.
7. Distancia de Monge e Elkan: Geralmente confundida coma Smith-Waterman, euma distancia de Gotoh estendida, que leva em conta a similaridade semantica decampos e sub-campos em consideracao. Cada sub-campo e comparada com o sub-campo mais similar utilizando a distancia de Gotoh ao passo que entre campos saocomparados com algoritmo proprio.
Alem das listadas, Simmetrics coleciona numerosas outras metricas, geralmenteempregadas em analise de sequencias de DNA em biologia. A enfase nessas metricas saovariacoes na maneira de pesar as distancias entre os elementos da cadeia e de valorar asinsercoes no meio da cadeia, porem mantendo a mesma valoracao para seus terminais.
Simmetrics tambem tem um levantamento do desempenho das metricas colecio-nadas, ilustrado na figura 4.2. Note que a ordenada e logarıtmica, e portanto, todas asmetricas sao consumidoras de recursos, a curvatura suave da figura pode ser enganadora.
Infelizmente, nao dispomos de recursos no momento para avaliar mais exatamenteo significado do grafico da figura 4.2 em termos da complexidade computacional, nem adocumentacao da biblioteca fornece essa medida.
Figura 4.2: Desempenho comparado das metricas do Simmetrics
4.6 Outros RecursosAlem dos recursos mencionados no capıtulo 4, muitas outras ferramentas, recur-
sos e bibliotecas prontas estao disponıveis para exame e eventual utilizacao. Precisamos
35
examinar no estudo as bibliotecas mais promissoras e disponıveis, mas nao se descartaque entre as demais nao possa existir contribuicoes uteis e que no contexto certo nao serevelem mais uteis do que as da secao 4.
36
Tabela 4.3: Pacotes e Classes Principais do LUCENE 2.4.0 e suas funcoesNome Descricao das Classesorg.apache.lucene.analysis O pacote principal do Lucene, possui filtros,
stemmers, separadores de palavras, separado-res de letras, uniformizadores (retirar acento,maiusculas ou minusculas).
org.apache.lucene.analysis.Analyzer Essa classe e um analisador 1 cria um TokenS-treamer, o qual analisa texto.
org.apache.lucene.analysis.Tokenizer Um Tokenizer e um TokenStream cuja entradae um Reader2.
org.apache.lucene.analysis.br Pacote com stemmer brasileiro baseado nostemmer alemao.
org.apache.gdata.data Este pacote contem a representacao interna dosentradas dos GData.
org.apache.lucene.index Codigo para manter e acessar ındices.org.apache.lucene.queryParser Um analisador de consultas implementado com
JavaCC3
org.apache.lucene.search Codigo para fazer procura em ındices. Em des-taque para a classe ScoreDocComparator, res-ponsavel por comparar dois objetos ScoreDocpara ordenamento.
org.apache.lucene.store Pacote de I/O binario para todos os dados dosındices.
org.apache.lucene.wordnet Este pacote utiliza sinonimos definidos noWordNet para criar e aramazenar um ındice noLucene, que sera utilizado em expansao de con-sultas.
org.apache.lucene.wikipedia.analysis Este pacote contem apenas uma classe Stan-dardTokenyzer que e compatıvel com a sintaxeda Wikipedia.
org.apache.regexp Esta classe existe para permitir acesso ao utilporem protegido pacote Regexp do Jakarta.
org.tartarus.snowball Pacote ligado a utilizacao de stemmers emvarias linguagens, aparentemente e umaimplementacao mais moderna e pratica dosstemmers separados por lıngua
com.sleepycat.db Acesso ao banco de dados, necessario apos umamudanca na API desse mesmo banco.
lucli Interpretador de linha de comando do Lucene
37
Tabela 4.4: Pacotes Principais do MALLET e suas funcoesNome Descricao das Classescc.mallet.classify AdaBoost, C4.5, Bagging, Balanced Winnow, Decision
tree, Naıve Bayes, Winnow,cc.mallet.classify.evaluate Matriz de Confusao, Cobertura de Acuracia e Graficoscc.mallet.cluster Agrupador Guloso, Kmeans, KBest Cluster, HillClimbing
Cluster e Guloso por Densidade.cc.mallet.fst Transdutores, incluindo Campo Randomico Condicional5.cc.mallet.fst.confidence Interface para Transdutores Corretores que corrigem seg-
mentos gerados por transdutores.cc.mallet.grmm.inference Contem interfaces implementadas por todos inferidores,
que sao algoritmos para computar (ou estimar) distribuicoesmarginais sobre nos de um modelo representado como umgrafo.
cc.mallet.grmm.learning Contem classes para fazer transformacoes globais emgraficos depois de gerados
cc.mallet.optimize Contem classes que buscam o maximo de uma funcao.Exemplo: LineOptimizer, ByGradient, ByGISUpdate, By-BatchGradient.
cc.mallet.pipe Contem classes para transformar dados arbitrarios eminstancias.
cc.mallet.topics Esse pacote contem um grupo de algoritmos paraotimizacao de modelos: Latent Dirichilet Allocation, FourLevel Pachinko Allocation, entre outros.
cc.mallet.type Esse pacote contem os tipos fundamentais de MALLET, in-cluindo Vetores de Caracterıticas, Instancia, Etiqueta, entreoutros.
38
Tabela 4.5: Mais recursos vinculados a PNLNome URL ObservacaoopenNLP http://opennlp.
sourceforge.net/openNLP e um sıtio queprocura acompanhar asopcoes em bibliotecasde NLP
Wordnet http://www.cs.waikato.ac.nz/ml/weka/
WordNet e dicionario eontologia generica
AGFL http://www.agfl.cs.ru.nl/index.html
Grammar Work Labpara gramaticas AGFLda Universidade Rab-doud de Nijmegen
WordFreakL http://wordfreak.sourceforge.net/
Biblioteca paraanotacoes automaticasou humanas que facilitaa correcao humana deanotacoes automaticas
WordNet::Similarity http://wn-similarity.sourceforge.net/
Modulos Perl que im-plementam varias me-didas semanticas de si-milaridade baseadas noWordNet
Livro sobre IR http://www-csli.stanford.edu/˜hinrich/information-retrieval-book.html/
Site do livro on-line doManning e Prabhakarsobre IR com estudo di-rigido
Stanford http://www-nlp.stanford.edu/links/statnlp.html
Tudo sobre NLP es-tatıstico, inclusive o re-positorio de utilitarios
IR Wiki http://ir.dcs.gla.ac.uk/wiki/FrontPage
Infomacao geral eacompanhamento dosTREC
Natural Language Toolkit http://nltk.org/index.php/Main_Page
Softwares, conjuntos dedados e tutoriais
39
5 TRABALHOS FUTUROS
O trabalho futuro, seguimento natural desse estudo e montar um laboratorio com oLucene, Gate, MALLET e procurar integrar o Lemur no mesmo projeto. Corpora devemser buscados nos mesmos sites em lıngua inglesa ou nos congeneres nacionais para sepoder criar trabalhos comparaveis e referenciaveis.
Pacotes nacionais para PLN podem ser buscados nos grupos da UFSCAR e USP eutilizados, caso sejam integraveis em um projeto baseado em Java. A UFMG tambem foiidentificada como referencia em Recuperacao de Informacoes, e uma otima oportunidadede trocar informacoes com pesquisadores brasileiros.
As secoes sobre IR e PLN devem ser aprofundadas para incluir mais tecnicas ereferencias em lıngua portuguesa. O objetivo e criar um projeto que permita integrar umou mais desses pacotes e trabalhar sobre corpora em lıngua portuguesa, e que permitabuscar a melhoria da recuperacao padrao do Lucene com a incorporacao de filtros PLNao esquema de avaliacao de relevancia dos documentos indexados.
40
6 CONCLUSAO
Foram examinadas brevemente a Recuperacao de Informacoes e o Processamentode Linguagem Natural, inclusive do ponto de vista da tipologia dos modelos de RI atual-mente empregados.
Em uma pesquisa futura procuraremos novas maneiras de tratar o problema de se-lecionar documentos relevantes para uma dada consulta a partir do refinamento do modelode documento ou entao da tecnica de calculo da relevancia de cada termo em um docu-mento ou consulta utilizando caracterısticas obtidas com Processamento da LinguagemNatural que sejam mais computacionalmente economicos.
O Lucene e a plataforma adequada para receber modulos que modifiquem suascaracterısticas de filtragem e indexacao pela facilidade de acesso ao seu codigo e pelapossibilidade de se fazer comparacoes com o trabalho de outros grupos de pesquisa.
A disponibilidade de diversas aplicacoes de PLN, maduras e testadas como GATE,MALLET e Simmetrics, escritos na mesma linguagem JAVA que o Lucene facilitara acriacao e testagem de modulos embutidos no Lucene.
Adicionalmente, a pesquisa descobriu o Lemur, pacote da Universidade CarnegieMellow, escrito em C++, porem com uma interface em Java.
A criacao ou adaptacao de modulos de analise, filtragem e indexacao adequados alıngua portuguesa tem agora uma boa oportunidade de ser empreendida, pois temos agorauma situacao de grande disponibilidade de componentes prontos ou semi-prontos paraacompanhar as tendencias da pesquisas em outros idiomas e colaborar com o cenario dapesquisa brasileiro.
41
REFERENCIAS
CHAKRABARTI, S. Discovering Links Between Lexical and Surface Features in Ques-tions and Answers. In: WEBKDD, 2004. Anais. . . Springer, 2004. p.116–134. (LectureNotes in Computer Science, v.3932).
CUNNINGHAM, H. Software Architecture for Language Engineering.2000. Tese (Doutorado em Ciencia da Computacao) — University of Sheffield.http://gate.ac.uk/sale/thesis/.
CUNNINGHAM, H.; MAYNARD, D.; BONTCHEVA, K.; TABLAN, V. GATE: A fra-mework and graphical development environment for robust NLP tools and applications.In: ANNIVERSARY MEETING OF THE ASSOCIATION FOR COMPUTATIONALLINGUISTICS, 40., 2002. Proceedings. . . [S.l.: s.n.], 2002.
GOSPODNETIC, O.; HATCHER, E. Lucene in Action. [S.l.]: Greenwich, EUA : Man-ning, 2005. 421p.
GREEN, B. F.; WOLF, A. K.; CHOMSKY, C.; LAUGHERY, K. Baseball, An Automa-tic Question Answering System. In: Computers and Thought, Feigenbaum and Feld-man(eds), MacGraw-Hill (New York NY). [S.l.: s.n.], 1963.
GRISHMAN, R. Computational Linguistics: An Introduction. Cambridge, England:Cambridge University Press, 1986.
GROSSMAN, D. A.; FRIEDER, O. Information Retrieval: Algorithms and Heuristics.[S.l.]: Dordrecht, Netherlands : Springer, 2004. 272p.
JURAFSKY, D.; MARTIN, J. H. Speech and Language Processing : An Introduction toNatural Language Processing, Computational Linguistics, and Speech Recognition. [S.l.]:Upper Saddle River, EUA : Prentice-Hall, 2000.
KUROPKA, D. Modelle zur Reprasentation naturlichsprachlicher Dokumente. [S.l.]:Berlin : Logos Verlag, 2004. 242p.
LUCENA, C. J.; BAUZER, C. Grandes Desafios da Pesquisa em Computacao no Bra-sil de 2006 a 2016. [S.l.]: Sociedade Brasileira de Computacao, 2006.
RUSSELL, S. J.; NORVIG, P. Artificial Intelligence. [S.l.]: Upper Saddle River, EUA :Prentice-Hall, 2003. 1021p.
42
SILVA, B. C. da; MONTILLA, G.; PARDO, T.; GRAcAS VOLPE, M. das. Introducaoao Processamento das Linguagens Naturais e Algumas Aplicacoes. [S.l.]: Sao Paulo,Brasil : USP, UFSCar e UNESP, 2007.
WIKIPEDIA. Informationa Retrieval — Wikipedia, The Free Encyclopedia. [Online;acessada em 22-setembro-2008].
43
ANEXO A GLOSSARIO
Embora esse texto seja uma panoramica das areas de RI e PNL, e no seu bojo sejamapresentadas muitas definicoes, listamos a seguir mais alguns termos encontradicos nosartigos e livros cujo conhecimento do significado possa ser util ou interessante.
1. Conceito e uma lista de termos vinculadas (CUNNINGHAM et al., 2002)a mesmacoisa ou ideia.
2. Gazetteer e um dicionario ou diretorio de informacoes geograficas sobre lugares enomes de lugares.
3. Ontologia e um modelo para descrever o mundo que consiste de tipos, proprieda-des, tipos de relacionamentos e restricoes.
4. Ontologia generica e uma ontologia como WordNet que nao se prende a determi-nado assunto e pode ser visto como um dicionario hierarquizado por relacionamen-tos ”e um”.
5. Stop Words sao palavras a serem excluıdas da analise estatıstica ou da analise ve-torial, geralmente palavras de classes fechadas como artigos, pronomes, adverbios(de tempo, modo, afirmacao, negacao, duvida, exclusao ou inclusao), preposicoes,conjuncoes e interjeicoes.
6. Meronımia e um relacionamento ”parte de”.
7. Polissemia e a capacidade de um signo (termo, palavra ou locucao) de ter multiplossignificados (semenes).
8. Hiponimo e um conceito especializado de outro. Cavalo arabe e especializacao decavalo.
9. Hiperonimo e um conceito que generaliza outro. Carro e generalizacao de mille.
10. Synset e um conceito do Wordnet, formado por um ou mais Lemmas.
11. Lemma, para o WordNet e termo que significa um conceito. ”Carro”e ”Au-tomovel”sao dois lemas do mesmo conceito e tem por hiperonimo ”veıculo mo-torizado”.
12. Cadeias Escondidas de Markov
44
13. Bag of Words e um modelo simplificado utilizado em PLN e RI. Nesse modelo,um texto e apresentado como um conjunto desordenado de palavras, ignorandogramatica ou ordem. Pode ser empregado por um classificador Naıve Bayes ou emAnalise Semantica Latente.
14. Latent Semantic Analysis e uma tecnica de PLN patenteada em 1988, especial-mente de semantica vetorial, que analisa as relacoes entre um conjunto de docu-mentos e os termos neles contidos atraves da criacao de um conjunto de conceitos.
15. Word Sense Disambiguation e o processo de esclarecimento do sentido de umtermo em uma senteca ou no discurso falado. Existem abordagens profundas ousuperficiais1.
16. Rede Semantica e um grafo que representa o relacionamento entre conceitos.Tambem e chamada de representacao de conhecimento.
17. Etiquetagem gramatica2 tambem chamado de desambiguacao de tipo de palavra,identifica o tipo gramatical - substantivo, verbo, adjetivo - de cada palavra.
18. Sstate space search e um campo da area da Inteligencia Artificial na qual sucessi-vas configuracoes ou estados sao considerados conforme determinado criterio paraa escolha de estado-otimo. O conjunto de estados futuro do sistema forma um grafono qual dois estados estao conectados se existe uma operacao que possa conduzir osistema do primeiro estado ao segundo.
19. Cadeia de Markov, homenagem a Andrey Markov, e um processo estocastico coma propriedade de Markov, que significa que os estados presente e futuros sao inde-pendentes dos estados passados. A mudanca de estado em cada momento dependede uma distribuicao de probabilidades, que define cada transicao possıvel.
20. Shallow Parsing e uma analise superficial, ligeira, que evita a analise mais com-pleta que e NP-completa. Ela identifica substantivos, locucoes nominais, verbos,mas nao faz analise sintatica mais elaborada.
1Deep and shallow approaches2Part-of-Speech tagging.
