Recuperaç ˜ao de Informaç ˜oes e Processamento de

UNIVERSIDADE CATÓLICA DE PELOTAS
CENTRO POLITÉCNICO
PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA
Recuperação de Informações e
Processamento de Linguagem Natural
Um Levantamento
por
Eduardo Bauer Londero
Trabalho Individual I
TI-2008/2-003
Orientador: Prof. Dr. Antônio Carlos da Rocha Costa
Co-orientador: Prof. Dr. Stanley Loh
Pelotas, dezembro de 2008
SUMÁRIO
LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
LISTA DE ABREVIATURAS E SIGLAS . . . . . . . . . . . . . . . . . . . . .
6
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1
9
INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 A RECUPERAÇÃO DE INFORMAÇÕES
2.1
Estratégias de RI . . . . . . . . . . . . .
2.1.1
Tipologia de Modelos de RI . . . . . . .
2.1.2
Modelo de Espaço de Vetores de Termos
2.1.3
Modelos probabilı́sticos . . . . . . . . .
2.2
Utilitários . . . . . . . . . . . . . . . . .
2.3
Tarefas da Recuperação de Informações
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
13
14
16
16
18
3 O PROCESSAMENTO DA LINGUAGEM NATURAL
3.1
O Tratamento da Linguagem pelo Computador . . .
3.2
Comunicação . . . . . . . . . . . . . . . . . . . . . .
3.3
As Tarefas do Processamento da Linguagem Natural
3.4
Arquitetura de um sistema PLN . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
21
22
24
25
4 FERRAMENTAS PRONTAS . . . .
4.1
Lucene . . . . . . . . . . . . . . . .
4.1.1
Principais Pacotes do LUCENE . .
4.2
MALLET . . . . . . . . . . . . . .
4.2.1
Filtros de Importação do MALLET
4.2.2
Classificadores do MALLET . . .
4.2.3
Principais Pacotes do MALLET .
4.3
GATE . . . . . . . . . . . . . . . .
4.4
Lemur . . . . . . . . . . . . . . . .
4.5
Simmetrics . . . . . . . . . . . . .
4.6
Outros Recursos . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
29
30
30
31
31
31
31
32
33
34
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
6
CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
ANEXO A
43
GLOSSÁRIO . . . . . . . . . . . . . . . . . . . . . . . . .
LISTA DE FIGURAS
Figura 2.1
Modelos de IR segundo a matemática empregada e a dependência
entre termos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Acompanhamento Anual da Pesquisa no TREC até 2001 . . . . . . .
14
19
Figura 3.2
Texto com marcadores criados pelo reconhecedor de entidades do
GATE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Arquitetura de um sistema PLN segundo (SILVA et al., 2007) . . . .
23
27
Figura 4.1
Figura 4.2
Análise sintática com o GATE . . . . . . . . . . . . . . . . . . . . .
Desempenho comparado das métricas do Simmetrics . . . . . . . . .
32
34
Figura 2.2
Figura 3.1
LISTA DE TABELAS
Tabela 4.1
Tabela 4.2
Tabela 4.3
Tabela 4.4
Tabela 4.5
Lista e localização de recursos integráveis em projetos de IR e NLP
Conceitos Básicos do Lucene . . . . . . . . . . . . . . . . . . . .
Pacotes e Classes Principais do LUCENE 2.4.0 e suas funções . . .
Pacotes Principais do MALLET e suas funções . . . . . . . . . . .
Mais recursos vinculados à PNL . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
29
30
36
37
38
LISTA DE ABREVIATURAS E SIGLAS
PLN
Processamento de Linguagem Natural
LC
Lingüı́stica Computacional
RI
Recuperação de Informações
ABNT
Associação Brasileira de Normas Técnicas
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
Autômato Finito
RESUMO
O presente trabalho examina duas áreas atuais e confluentes da Ciência da
Computação – Recuperação de Informações (RI) e Processamento de Linguagem Natural
(PNL) – seus conceitos e técnicas, e em seguida faz um levantamento das bibliotecas e
aplicativos públicos, maduros, atualizados e mais facilmente disponı́veis para utilização
em pesquisa. A recuperação de informações é área dedicada a facilitar a recuperação de
documentos e sua apresentação ordenada segundo critérios de relevância. A medida que o
volume de informações cresce, e os modelos atualmente empregados na sua recuperação
se mostram ineficazes, fica evidente a necessidade de propor e testar modelos de documentos mais complexos e formas de consultas mais elaboradas. Esses modelos de RI
mais complexos provavelmente farão uso de técnicas do Processamento Natural de Linguagem, que é a área da computação que se dedica a lidar com a lı́ngua natural falada
ou escrita. Por outro lado, aqueles tópicos que eram objeto de pesquisa algumas décadas
atrás, já se encontram implementados em bibliotecas públicas de programação. Para se
fazer um serviço de busca e recuperação com as técnicas tradicionais já existem componentes prontos para uso. Para levar a efeito a proposta de melhorar a Recuperação de
informações com Processamento da Linguagem Natural, acompanhando o estado da arte
atual, é necessário conhecer os conceitos e técnicas de ambas as áreas e dispor de bibliotecas equivalentes às utilizadas nas pesquisas ou pelo menos saber usar e adaptar as
bibliotecas de uso público geral. É o que procuro dar inicio através desse trabalho.1 .
Palavras-chave: Recuperação de Informações, Processamento de Linguagem Natural,
Lucene, GATE, Lemur, Simmetrics.
1
Esse trabalho foi composto com TeXnicCenter para LaTex e obedecendo a ortografia válida até janeiro
de 2009
TITLE: “INFORMATION RETRIEVAL AND NATURAL LANGUAGE PROCESSING - THE STATE OF THE ART ”
RESUMO
This work examines two areas from Computer Science – Information Retrieval
and Natural Language Processing – that begun to merge. It studies its models and techniques and also looks for public, proven, easily available and up-to-date programs, toolkits
or packages to use and integrate in research. The goal is to enhance IR by using NLP
ideas and techniques. Information Retrieval is dedicated to easy document recover and its
presentation ranked accordingly to relevance criteria. As document quantity in Internet
mounts, actual models became inefficient and new document models, more complex and
complete, should be proposed and tested as long as more sophisticated queries. These
new models should thrive with ideas and techniques borrowed from Natural Language
Processing, 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, its
desirable to know and use ”off-the-shell”programs and toolkits at least equivalent to those
currently used and mentioned in TREC encounters.
Palavras-chave: Information Retrieval, Natural Language Processing, Lucene, MALLET, Lemur, Simmetrics.
9
1
INTRODUÇÃO
Recuperação de Informações é a área dedicada a facilitar a procura de documentos ou passagens em grandes coleções de textos ou na Internet de acordo com os dados
de uma consulta e apresentá-los ordenados por critérios de relevância. Originalmente a
disciplina de Recuperação de Informações pertencia à Biblioteconomia e passou a interessar à Ciência da Computação quando as coleções de documentos em meio eletrônico
ganharam importância.
Em 1983, Gerald Salton, um dos pioneiros da área de Recuperação de Informações
(RI), previu que chegaria a época em que as pessoas seriam forçadas a utilizar a
informação mais facilmente disponı́vel e ignorar o restante dela. Essa época chegou.
Os sistemas corporativos limitados e carı́ssimos de então foram substituı́dos pelos gigantescos e gratuitos Google e Yahoo. Neles a informação trivial sobre determinado assunto
pode ser encontrada, mas é difı́cil determinar se o resultado da consulta feita é suficiente
ou relevante.
A medida que cresce a quantidade de páginas da internet, fica cada vez mais difı́cil
se encontrar informação de qualidade e os modelos de IR em uso se mostram inadequados
e precisam ser melhorados. Em 1983 as coleções para a busca de documentos e passagens
atingiam milhares de documentos. Em 2004 o Google tinha indexadas mais de 4 bilhões
de páginas (GROSSMAN; FRIEDER, 2004). Com o crescimento do tamanho do espaço
de busca, o desempenho precisa ser privilegiado, e as técnicas básicas da área, feitas para
computadores antigos, contraditoriamente, se consolidaram. Aquilo que funcionava em
computadores lentos de 1970, precisava ser mantido devido ao crescimento do número de
páginas a serem indexadas.
Em 1992 o Departamento de Defesa americano e o National Institute of Standards
and Technology promoveram a primeira conferência TREC - Text Retrieval Conference,
que se realiza desde então e continua sendo um dos mais importantes fóruns para acompanhar as tendências e o estágio alcançado pela pesquisa. Nos encontros TREC, várias
áreas originalmente privativas de Inteligência Artificial e Processamento Natural de Linguagem, tais como Sumarização Automática e Respondendo Perguntas1 passaram a ser
incluı́das na área de RI, porém com abordagens muito próprias, estatı́sticas e ligeiras,
adequadas ao tamanho dos córpora propostos.
Os sistemas de tradução automática, entendimento e geração de fala, respondendo
perguntas e sumarização se originaram na área da Inteligencia Artificial e do Processamento de Linguagem Natural. Exemplos pioneiros são o BASEBALL (GREEN et al.,
1963) e o BASEBALL-MOON, que funcionavam como interface em linguagem natural
1
Respondendo Perguntas será a versão adotada neste trabalho para se referir à Question Answering.
10
entre o usuário e um banco de dados.
A Recuperação de Informações tradicional lida principalmente com texto2 , nada
mais natural que buscar se envolver com Processamento Natural de Linguagem, na procura de mais caracterı́sticas que auxiliem a selecionar documentos relevantes. No entanto
o obstáculo é a complexidade e o desempenho dos algoritmos do PLN, além da própria
natureza ainda incompreendida da lı́ngua natural.
Com o esgotamento crescente dos modelos em uso na Recuperação de
Informações em virtude do crescimento da Internet e com a abordagem de problemas
de sumarização e respondendo perguntas, antes privativos de PLN e IA, o caminho para a
RI parece ser o de aos poucos enfrentar o problema de desempenho das técnicas de PLN
e buscar ao poucos conhecê-las e incorporá-las onde se provar vantajoso.
Além de estudar Recuperação de Informações e Processamento Natural de Linguagem esse trabalho busca levantar quais alternativas existem de utilização de programas e pacotes prontos, testados, atuais e facilmente integráveis existem para se produzir
pesquisa de qualidade o mais rapidamente possı́vel. Nessa área, examinaremos o Lucene,
um projeto de engine de recuperação que se firmou com padrão e serve à pesquisa como
parâmetro básico de comparação. Quanto aos pacotes de PLN, a disponibilidade é muito
maior. Examinaremos entre outros o GATE da Universidade Sheffield, o MALLET da
Universidade da Pensilvania e o Lemur da Universidade de Stanford.
2
Não é mais considerada uma área de ponta da pesquisa, porém o é a Recuperação de Informações de
Multimı́dia, dada a dificuldade ainda maior de processar e caracterizar esses itens. Essa área é listada como
objetivo nos Desafios da Computação para 2006-2016 (LUCENA; BAUZER, 2006).
11
2
A RECUPERAÇÃO DE INFORMAÇÕES
A Recuperação de Informações (RI) é a ciência dedicada a localizar documentos
relevantes, não apenas o mero casamento e identificação de padrões (GROSSMAN; FRIEDER, 2004). É uma ciência para encontrar documentos, extrair informações de dentro
de documentos, buscar criar metadados sobre eles, tanto em SGDBs, como em coleções,
como na WEB. RI é interdisciplinar e busca pontos de apoio em ciência da computação,
matemática, biblioteconomia, lingüı́stica, estatı́stica e psicologia cognitiva.
O maior campo de aplicação, em evidência hoje em dia, é a procura e ordenamento
de documentos na internet. Porém coleções de documentos, tais como correspondência
em email, manuais técnicos, legislação ou jurisprudência também podem se beneficiar
desse trabalho. Um problema relacionado ao da procura é o da filtragem e o roteamento
de documentos, no qual se busca direcionar correspondência (email ) que chega a uma
empresa para os setores adequados segundo perfis identificados.
Para medir a efetividade do IR dois conceitos básicos são utilizados: precisão e
recall. A precisão é um conceito intra-consulta formado pela taxa dos documentos significativos recuperados pela quantidade total de documentos recuperada em um consulta. O
recall é taxa formada pelo número de documentos relevantes recuperados dividido pela
quantidade total de documentos relevantes no córpora. Portanto, o recall só pode ser
medido em córpora fechados e conhecidos, precisando ser estimado quando se trata da
internet.
P recisao =
Recall =
2.1
RecuperadosRelevantes
Recuperados
RecuperadosRelevantes
Relevantes
(2.1)
(2.2)
Estratégias de RI
As estratégias de recuperação atribuem uma medida de similaridade entre uma
consulta e um documento. Elas se baseiam na noção de que a relevância de um documento
para uma dada consulta é proporcional à co-ocorrência de termos entre elas. Algumas
estratégias são balanceadas para aliviar os problemas causados pela ambigüidade tı́pica
da linguagem, que um conceito pode ser descrito por vários termos 1 ou um termo pode
identificar diversos conceitos conforme o contexto. Uma estratégia de recuperação é um
algoritmos que, dado uma consulta Q e um conjunto de documentos D1 , D2 , ..., Dn , cria
1
Exemplo de polissemia: ”Porto Alegre”equivale à ”capital gaúcha”.
12
um Coeficiente de Similaridade CS(Q, Di ) para cada documento 1 ≤ i ≤ n.
As estratégias identificadas por (GROSSMAN; FRIEDER, 2004) são:
• Modelo Espaço Vetorial: a consulta e cada documento são representados por um
vetor no espaço de termos. Uma medida de similaridade entre ambos vetores é
calculada.
• Recuperação Probabilı́stica: Uma probabilidade baseada na chance de que um
termo apareça em documentos relevantes é computada para cada documento da
coleção. Para termos comuns entre uma consulta e um documento, a similaridade é
a combinação das probabilidade de cada termo comum.
• Modelos de Linguagem: Um modelo é construı́do para cada documento e a probabilidade do documento gerar a consulta é computada.
• Redes de inferência: Uma rede Bayesiana é utilizada para inferir a relevância de um
documento frente a uma consulta. Essa relevância é dada pela força da evidência
contida em um documento que permita avaliar a sua similaridade com a consulta.
• Indexação Booleana: Um escore é atribuı́do de tal forma que uma consulta booleana
inicial resulte em um ordenamento. Isto é feito associando um peso a cada termo
da consulta, de modo que esse peso é utilizado para computar o coeficiente de
similaridade.
• Indexação por Semântica Latente: A ocorrência de termos em documentos é representada como uma matriz termos versus documentos. A matriz é reduzida através
de Decomposição Singular de Valores (DSV) para filtrar o ruı́do de cada documento de forma que dois deles que tenham a mesma semântica fiquem localizados
próximos em um espaço multidimensional.
• Rede Neural: Uma seqüência de neurônios, ou nós em uma rede, ao serem ativados
por uma determinada consulta ligam-na aos documentos que lhe correspondem. As
redes são uma modalidade supervisionada de treinamento e precisam ser treinadas
para responder a documentos relevantes ou não.
• Algoritmos Genéticos: Um consulta ótima para achar documentos relevantes pode
ser gerada por evolução. Uma consulta inicial é criada com pesos randômicos ou
estimados. Uma nova consulta é gerada e sobrevive ser estiver mais próxima dos
documentos relevantes ou é excluı́da se for menos capaz que a inicial.
• Recuperação por Conjunto Fuzzy: Um documento é mapeado para um conjunto
fuzzy, que é contém os elementos vinculados a um número que indica a força do relacionamento. Consultas booleanas são mapeadas para as operações de intersecção,
união e complemento
Para cada tipo de estratégia vários utilitários pode ser empregados para construir os elementos ou melhorar os resultados de cada abordagem. Esses utilitários são descritos na
seção 2.2.
13
2.1.1
Tipologia de Modelos de RI
Para a recuperação ser eficiente os documentos são transformados em algum tipo
de representação. A figura 2.1, encontrada em (KUROPKA, 2004) apud (WIKIPEDIA,
2008) faz a categorização dos modelos mais comuns de IR segundo duas dimensões:
a base matemática e as propriedades do modelo. Quanto à matemática, podem ser os
seguintes
• Modelos da teoria dos conjuntos representam documentos como conjuntos de palavras ou frases. As similaridades são derivadas de operações tı́picas de conjuntos:
Modelo padrão booleano
Modelo booleano estendido
Recuperação fuzzy
• Modelos algébricos representam documentos e consultas como vetores, matrizes ou
tuplas e a similaridade entre o vetor da consulta e do documento é representado por
um escalar.
Modelo de espaço vetorial
Modelo de espaço vetorial generalizado
Modelo de espaço vetorial por tópico
Modelo booleano estendido
Modelo de espaço vetorial por tópicos melhorado
Indexação semântica latente
• Modelos probabilı́sticos tratam o processo de IR como um inferência probabilı́stica
e as similaridades são computadas como probabilidades de um documentos ser relevante para um dada consulta. Probabilidade Bayesiana geralmente é empregada
nesses modelos.
Recuperação por independência binária
Modelo de relevância probabilı́stica (como o Okapi BM25)
Inferência incerta
Modelos de linguagem
Modelo de divergência-do-randômico
Alocação latente de Dirichilet
Quanto às propriedades dos modelos empregados:
• Modelos sem interdependências não tratam o relacionamento entre os termos. Esse
fato é geralmente representado no modelo de espaço vetorial pela presunção de
ortogonalidade entre os seus eixos e no modelo probabilı́stico pela (presunção
também) independência entre as variáveis de termos.
• Modelos com interdependência imanente permite uma representação dos relacionamentos entre termos. O grau de interdependência entre dois termos é definido pelo
modelo em si. Geralmente é direta ou indiretamente derivada da co-ocorrência dos
termos no conjunto dos documentos. Por exemplo, redução dimensional.
14
Figura 2.1: Modelos de IR segundo a matemática empregada e a dependência entre termos
• Modelos com interdependência transcendente consideram a relação entre os termos,
mas não determinam como esse relacionamento se estabelece. Eles dependem de
fontes externas – humana ou alguma heurı́stica complexa – para estabelecer o grau
e tipo de relacionamento entre os termos.
2.1.2
Modelo de Espaço de Vetores de Termos
O modelo de espaço de vetorial computa uma medida de similaridade definindo
um vetor que representa cada documento [Salton et al. 1975] apud(GROSSMAN; FRIEDER, 2004). O modelo se baseia na idéia de que, de algum modo, o significado do
documento é contido nas suas palavras nele empregadas. Ao se representar as palavras do
documento por um vetor, é possı́vel comparar documentos e consultas e determinar quão
parecidos eles são. Se uma consulta pode ser considerada como um documento, pode ser
possı́vel computar um coeficiente de similaridade SC entre consulta e os documentos
No modelo vetorial, os documentos e a consulta serão representados por vetores. O método tradicional é calcular o ângulo entre eles. Então, se dois vetores apontam
na mesma direção, ou aproximadamente na mesma direção, mesmo que não sejam de
mesmo tamanho, eles são semelhantes entre si. Para se calcular o ângulo entre dois vetores se recorre ao produto interno entre eles. Mas não necessariamente o produto interno,
(GROSSMAN; FRIEDER, 2004), qualquer função monotônica do ângulo é suficiente.
Geralmente é referido o CS - Coeficiente de Similaridade - ao invés do ângulo.
Além de simplesmente usarmos vetores com ı́ndices que registram a ocorrência
de termos, surgiu a idéia de permitir ao usuário dar peso à cada termo da consulta. Um
modo proposto com pesos foi fazê-lo proporcional à sua ocorrência em toda a coleção. A
idéia é de que um termo freqüente deve ter menor importância do que um termo raro.
Suponha que que existam n diferentes termos no conjunto de documentos, e que
a ocorrência de um termo na consulta ou em um documento seja assinalado por 0 ou 1
conforme a aparição 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 wj 2 calculado de forma que veremos mais
adiante:
~ =< c0 , c1 , ....cn >
C
De forma semelhante, os vetores de 2 documentos D1 e D2 são definidos da seguinte maneira:
~ 1 =< d1,0 , d1,2 , ..., d1,n >
D
e
~ 1 =< d2,0 , d2,2 , ..., d2,n >
D
Em uma coleção que contenha 10.000 termos diferentes, os vetores que representam cada documento teriam 10.000 ı́ndices. Um documento com 100 termos teria 9.900
ı́ndices zerados e 100 deles definidos como a combinação da freqüência do termo no
documento com a sua freqüência inversa. Como explicamos antes, em uma abordagem
simples os termos dos vetores consulta e documentos seriam simplesmente 0 ou 1. Porém
pode ser representados por pesos : o j−esimo termo do vetor do documento Di será dado
pela multiplicação da freqüência do termo no documento pela freqüência inversa do termo
na coleção:
dij = tfij × idfj
(2.3)
Na equação 2.5 cada termo será representado pelos seu peso especı́fico dado pela
combinação tf −idf . Os pesos são calculados pelo Inverse Document Frequency ( IDF ).
Para tanto, considere as seguintes definições:
d = número total de documentos
t = número de termos distintos na coleção de documentos3
tfij = número de ocorrências do termo tj no documento Di , chamada de
freqüência do termo.
dfj = número de documentos nos quais ocorre o termo tj chamada de freqüência
do documento.
idfj = log( dfdj ) = número de ocorrências do termo tj no documento Di , chamada
de freqüência do termo.
Observe que com a freqüência interna de documento servindo de peso para os
termos, palavras muito freqüentes em todos os documentos se enfraquecem ou somem
naturalmente. Por exemplo, os artigos e conetivos geralmente são comuns a todos os
documentos e portanto o peso delas vale log(d/d) = 0.
Conforme (GROSSMAN; FRIEDER, 2004), muitas pesquisas com pesos de termos foram feitas para melhorar a combinação básica tf − idf . Das diversas variações
estudadas, a fórmula a seguir foi identificada como de boa performance.
(log tfij + 1.0) ∗ idfj
2
j=1 [(log tfij + 1.0) ∗ idfj ]
wqj = Pt
2
(2.4)
w: peso do j-ésimo termo
Esse número geralmente é considerado após a retirada das stop-words e após a aplicação de um stemmer, que reduz as palavras aos seus radicais, e eventualmente um processo para reconhecer locuções verbais
e nominais.
3
16
Utilizaremos para representar cada documento Di um vetor (di1 , di2 , ..., dit ) de
tamanho t que é o número de termos distintos da coleção de documentos. A consulta C
será representada por um vetor (cw1 , cw2 , ..., cwt ), onde cada ı́ndice indica o peso de cada
termo presente. Um coeficiente de similaridade (SC) entre uma consulta e um documento
é definida pelo produto escalar dos dois vetores:
~ ·D
~i =
SC(C, Di ) = C
t
X
cwj × dij
(2.5)
j=1
Segundo (GROSSMAN; FRIEDER, 2004), existem muitas maneiras de comparar
um vetor consulta e um vetor documento. Ele as apresenta e discute em seu livro. A mais
comum é a medida do cosseno entre os ângulos formados pelos vetores do documento e
da consulta:
Pt
SC(C, Di ) = qP
t
j=1
wqj dij
2
j=1 (dij )
Pt
2
j=1 (wqj )
(2.6)
Na equação da medida do cosseno, dado que aparece no seu radical o comprimento
do vetor consulta e o comprimento do vetor documento, ocorre uma normalização. Com
o produto interno simples, um documento muito longo pode se parecer mais relevante
pelo simples fato de ter mais termos em comum com a consulta. A medida do cosseno
proporciona portanto uma normalização por medir apenas a diferença de ângulos e não a
projeção relativa entre dois vetores.
O coeficiente de Dice é definido como:
2 tj=1 wqj dij
SC(C, Di ) = Pt
Pt
2
2
j=1 (dij ) +
j=1 (wqj )
P
(2.7)
O coeficiente de Jaccard é definido como :
Pt
SC(C, Di ) = Pt
j=1 (dij
2.1.3
wqj dij
Pt
2
j=1 wqj dij
j=1 (wqj ) −
j=1
)2
+
Pt
(2.8)
Modelos probabilı́sticos
Segundo (GROSSMAN; FRIEDER, 2004), um modelo probabilı́stico calcula o
coeficiente de similaridade entre uma consulta e um documento como a probabilidade
que o documento vá ser relevante à consulta, o que reduz o problema da relevância a um
problema estatı́stico.
Todo o trabalho na recuperação probabilı́stica deriva da idéia de estimar o peso
de um termo baseado em quão freqüente um documento aparece ou não em documentos
relevantes ou não. Nesse caso, usa-se probabilidade Bayesiana.
2.2
Utilitários
Muitos diferentes utilitários estão envolvidos diretamente com as estratégias de
recuperação ou com a melhoria de seus resultados. A maioria dos utilitários retira ou
acrescenta termos à consulta original, numa tentativa de refiná-la. Outros refinam o foco
da consulta, através de subdocumentos ou passagens, ao invés de documentos completos.
17
A chave é que cada uma desses utilitários são componentes ”plugáveis”, que trabalham
com qualquer estratégia de recuperação. Esse utilitários seriam:
• Relevance Feedback: Os primeiros N documentos encontrados pela consulta inicial
são considerados relevantes. Eles são considerados relevantes por escolha manual
ou por presunção arbitrária. Eles são ordenados por uma dentre várias técnicas.
Os t termos mais freqüentes dos documentos são acrescentados à consulta inicial
produzindo um mecanismo de reforço.
• Clustering: Documentos são agrupados de forma automática ou manual. A
comparação da consulta apenas é feita contra grupos que se deveriam conter
informação relevante. É um limite ao espaço de busca, e tenta-se evitar documentos
irrelevantes antes que a busca se inicie.
• Passage-base Retrieval: A premissa é que documentos mais relevantes tem passagens irrelevantes e que a porção relevante é um trecho concentrado. Assim, as
consultas são feitas contra trechos, sobrepostos ou não, e os resultados de cada
passagem são combinados em um coeficiente de similaridade. O tamanho de cada
passagem pode ser fixo ou variável, conforme a implementação. Ou então o documentos pode ser dividido em sentenças, parágrafos, ou qualquer divisão natural do
documento.
• Parsing (stemming, processamento de nomes): Simplesmente casar termos nem
sempre dá bons resultados. A identificação de termos é computacionalmente mais
fácil do que o uso de operadores de proximidade. Regras de análise ou listas são
utilizados para identificar locuções válidas como ”Universidade Católica de Pelotas”. Essas locuções são tratadas como termos isolados. Outras técnicas de análise
evitam prefixos e sufixos (stemming) para buscar identidades entre termos que compartilham a mesma raiz. Essa última técnica aparece em
• N-grams : a consulta é particionada em n-grams (com ou sem sobreposição de
n caracteres). Os n-grams são utilizados para casar consultas com documentos.
Procura-se obter um casamento ”fuzzy”que seja resistente a erros de digitação,
pronúncia ou de recuperação OCR. Outra vantagem do n-grams é a independência
de lı́ngua.
• Thesauri: Thesauri são gerados automaticamente do texto ou criados de forma manual. A chave é não apenas criar o Thesaurus, mas usá-lo para expandir a consulta
ou a representação do documento para melhorar a recuperação.
• Redes Semânticas: São hierarquias de conceitos na qual conceitos individuais são
conectados com outros. A força do relacionamento é atribuı́da à associação. Uma
rede assim é a Wordnet4 , entre outras. Foram feitas tentativas de se construir ontologias assim automaticamente. O desafio é utilizar essa rede para expandir a consulta
e os documentos e aumentar a taxa de recuperação de documentos relevantes.
• Regressão analı́tica: Técnicas estatı́sticas são empregadas para identificar
parâmetros que descrevem caracterı́sticas que identificam determinado documento.
4
http://wordnet.princeton.edu/
18
Essas caracterı́sticas podem ser empregadas em uma regressão para identificar o
parâmetro exato que refina uma medida de similaridade
2.3
Tarefas da Recuperação de Informações
A recuperação de informações é uma designação que passou a abranger diversas
tarefas, muitas delas originalmente vinculadas com Inteligência Artificial, como Respondendo Perguntas, que passaram a ser abordadas pelo enfoque da IA, a partir de técnicas
mais simples e adequadas à grandes corpos de textos.
Muitas tarefas passam a se incorporar à área conforme são propostas nos encontros
anuais da TREC e CLEF. É famosa a inclusão do Respondendo Perguntas, antes tarefa da
Inteligência Artificial e da Lingüı́stica Computacional no TREC de 1999. As abordagens
inovadoras para esse problema trazidas para o TREC, baseadas em caracterı́sticas superficiais e em analisadores leves (CHAKRABARTI, 2004) trouxeram novas perspectivas
para o problema de encontrar passagens com respostas para determinada pergunta.
Nas conferências TREC, todas atividades assessórias à RI, são abordadas e passam
também a figurar academicamente como ”tarefas”da área. Na listagem abaixo, descrevemos algumas dessas tarefas:
• Recuperação de documentos é a tarefa tradicional da Recuperação de Informação.
• Agrupamento de documentos é a sua classificação. Pode ser tanto um filtro de
SPAM, como roteamento de emails de queixas em uma organização pública (governo, serviços, energia ou telefonia) de grande porte.
• Recuperação de documentos falados.
• Recuperação de páginas WEB, imagens, vı́deos e músicas são também consideradas sub-áreas, embora a dificuldade de caracterizar peças de multimı́dia e medir sua
similaridade sejam quase um mundo à parte.
• Sumarização de Textos: os sistemas de sumarização buscam a criação automática
de um resumo coerente de um texto dado.
• Respondendo Perguntas: são os que buscam respostas precisas, ou a identificação
de trechos que as contenham, a perguntas formuladas em linguagem natural.
• Tarefas Assessórias:
Desempenho em arquiteturas multicore.
Tipos de ı́ndice e sua manipulação (compactação).
• Psicologia e cognição: como o usuário interage com a interface de consulta, quais
hipóteses formula.
• Consultas: como melhorar consultas, como integrar e levar em consideração dados
do contexto do usuário.
• Recuperação cruzada é a consulta em uma lı́ngua e a recuperação de documentos
relevantes em outra.
19
A produção de pesquisa na área de IR varia conforme a época e as tarefas propostas pela organização do encontro. Na imagem 3.2 expomos como evolui a produção
apresentada no TREC conforme as áreas ao longo da primeira década de existência do
evento.
Figura 2.2: Acompanhamento Anual da Pesquisa no TREC até 2001
20
3 O PROCESSAMENTO DA LINGUAGEM
NATURAL
De acordo Daniel Jurasky (JURAFSKY; MARTIN, 2000) Processamento da Linguagem Natural (PNL) é a área da computação que lida com a lı́ngua humana falada ou
escrita. Isso envolve tudo, desde a contagem da palavras em um texto, até hifenização,
correção ortográfica , transcrição ou sı́ntese de fala, até sistemas complexos para responder perguntas ou tradutores automáticos1 . A Lingüı́stica Computacional, segundo
(GRISHMAN, 1986), é estritamente o estudo de sistemas computacionais para o entendimento da linguagem humana, incluindo-se aı́ a testagem de gramáticas propostas por
lingüistas2 .
Ainda de acordo com Jurafsky campos historicamente separados - Processamento
da Linguagem Natural, Reconhecimento de Fala, Lingüı́stica Computacional, Psicolinguı́stica Computacional - começaram a se combinar. A disponibilização de ferramentas
comerciais e a necessidade de técnicas baseadas em linguagem para a Web proporcionam
um grande estı́mulo. A disponibilidade de grandes córpora facilita o estudo de modelos
estatı́sticos em todos os nı́veis, da fonética ao discurso.
O conhecimento para lidar com linguagem pode ser separado em seis categorias
diferentes:
• Fonética 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.
• Semântica - O estudo do significado das palavras.
• Pragmática - O estudo de como a linguagem é utilizada para atingir objetivos dos
falantes.
• Discurso - O estudo de unidades lingüı́sticas maiores do que um enunciado3
1
A tradução automática é a primeira e eterna tarefa do PNL, e segundo Maria das Graças Volpe, a
PNL começou pelo final. A estratégia para essa área, segundo essa pesquisadora, deve ser a de resolver
problemas menores, capazes de no futuro compor uma solução total adequada.
2
Até hoje não foi possı́vel determinar qual gramática reconhece todas as formulações aceitas por falantes
naturais
3
Enunciado (utter) é a unidade de fala. Pode ser palavra, frase, oração, iniciado e terminado por silêncio
e caracterizado pela entonação que enfatiza o significado que se deseja transmitir
21
A fonética e a fonologia se dedica à lı́ngua falada, que veremos mais adiante, tem
por fundadas razões, motivos para ter um tratamento em separado. O mais óbvio deles, é
a separação entre palavras. A separação de palavras é uma tarefa do texto escrito no caso
do chinês e japonês (JURAFSKY; MARTIN, 2000).
A morfologia e a sintaxe geralmente podem ser estudadas dentro do âmbito do
texto escrito. A semântica e mais do que ela, a pragmática, dependem de fatores extratexto4 .
3.1
O Tratamento da Linguagem pelo Computador
As tecnologias para lidar com os problemas da PLN se baseiam em modelos formais ou representações de conhecimento de linguagem, fonética, morfologia, sintaxe,
semântica, pragmática e discurso. Um pequeno número de modelos, que inclui máquinas
de estado, sistemas de regras formais, lógica, e probabilidade, são utilizados para capturar
esse conhecimento.
Os automatas finitos (JURAFSKY; MARTIN, 2000) apareceram em 1950 a partir
do modelo de computação de Turing. A máquina de Turing podia ler uma fita finita de
sı́mbolos, podendo alterar seu estado ou o estado da fita. Os automatas finitos não podiam
interagir com a seqüência de sı́mbolos de entrada.
Inspirados no trabalho de Turing, McCulloch e Pitts construı́ram um modelo de
neurônio que podia ser descrito em termons de lógica proposicional. O neuron de McCulloch e Pitt era um dispositivo binário que recebia estimulo e podia chavear entre ligado e
desligado conforme determinados limiares. Em 1951 Kleene definiu o autômato finito e
a expressão regular para o neurônio de McCulloch/Pitts e provou sua equivalência.
Outra contribuição relevante do modelo de autômato finito foi o aparecimento da
interpretação de expressões regulares dentro de editores, com editor ed de Ken Thompson. O célebre programa ELIZA, que simulava um psicoterapeuta rogeriano 5 , funcionava
através de uma cascata de substituições de expressões regulares.
Problemas de morfologia são aqueles nos quais se busca entender como as palavras se subdividem ou se flexionam para indicar variações. Sabe-se que ”peixe”não tem
feminino, mas acrescentando-se ”s”temos o plural. O analisador morfológico deve ser
capaz de separar as sı́labas de uma palavra, além de identificar prefixos, sufixos, flexões e
composições.
Transdutores Finitos 6 (TF) são extensões de máquinas finitas que podem gerar 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 léxica, a
concatenação dos morfemas que compõem a palavra e uma superficial que representa a
escrita final da palavra.
Um transdutor mapeia sı́mbolos de um conjunto para outro. Um transdutor finito
faz isso através de um autômato finito. Ao passo que um autômato finito AF) define uma
linguagem formal através de um conjunto de cadeias de caracteres, ao passo que o TF
define a relação entre dois conjuntos de cadeias de caracteres.
A comunicação humana é muito complexa e está longe de ser adequadamente
4
Para lidar com a pragmática o agente de ser provido de conhecimento acerca do mundo, de preferência
conhecimento adquirido em primeira mão através de sentidos.
5
Tipo de terapia criada por Karl Rogers, chamada de não-diretiva
6
Do inglês Finite State Transducers (FST), extensões de Finite State Automata (FSA).
22
descrita e muito menos emulada ou entendida em tempo computacionalmente aceitável.
Na seção seguinte examinaremos essa questão para formamos uma idéia dos nı́veis em
que cada tarefa do PNL atua.
O algoritmo de Potter é eficiente para fazer stemming, retirar sufixos e prefixos, e
é preferı́vel em aplicações de IR, onde a análise morfológica exata não é necessária.
3.2
Comunicação
Faremos um breve relato do processo de comunicação como encontrado em (JURAFSKY; MARTIN, 2000). Veremos que a comunicação (vocalizada ou escrita) é fruto
de um processo de cálculo que envolve além do conhecimento dos significados e dos
contextos, o conhecimento que se tem acerca do ouvinte. A audiência é determinante na
escolha dos termos e da mensagem para o emissor e o receptor inclui na decodificação da
mensagem o conhecimento acerca do emissor e o que ele julga que o emissor saiba acerca
do receptor. Um episódio tı́pico de comunicação entre o falante E e o receptor R, no qual
o falante faz um enunciado M usando palavras P, é composto de 7 processos:
• Intenção: O emissor decide que existe uma proposição P que deve ser dita ao receptor R.
• Geração: O falante planeja um modo de transformar a proposição P em uma expressão vocal, incluindo aı́ seu conhecimento acerca do ouvinte, que aumentará a
chance da proposição ser entendida.
• Sı́ntese: O falante produz a realização fı́sica das palavras escolhidas. Isso pode ser
feito em tinta, voz, imagens ou outro meio.
• Percepção: O ouvinte reconhece a produção M e a separa em palavras Wi . Na
década de 90, com o aumento do poder dos computadores de mesa e dos algoritmos
de classificação 7 essa tarefa se tornou viável.
• Análise: O ouvinte deduz que M tem diversos significados P1 , P2 ..Pn . A análise
tem três partes: sintática, semântica e pragmática.
Na análise sintática é construı́da uma árvore que auxilia na identificação correta
dos termos. Locuções podem ser identificadas, pois as árvores onde os termos
são considerados individualmente são descartadas no processo de construção. Por
exemplo em ”Estou vendo a pedra”, ”Estou vendo”será etiquetado com V (verbo),
”pedra”e ”eu”como ”S”(Substantivo).
Na análise semântica a mensagem agora é traduzida em forma de regras lógicas
vinculadas nas quais já aparecem identificados objetos e relacionamentos. Por
exemplo:
V er(P edra, Agora)
Na análise pragmática, o enunciado será considerada dentro do seu contexto.
”Estou vendo a pedra”significa coisas diferentes para um alpinista ou um joalheiro.
7
Algoritmos como o Support Vector Machine (SVM) combinados com a utilização de técnicas de núcleo
permitiram o reconhecimento de escrita e de voz
23
• Eliminação da Ambigüidade: O receptor R deduz que E pretendia transmitir P i
(onde no caso ideal Pi = P ). A maioria dos falantes não é ambı́gua, mas quase todas as expressões vocais têm várias interpretações. A comunicação funciona porque
o ouvinte conclui qual interpretação provavelmente o falante pretendia transmitir.
No nı́vel da eliminação de ambigüidade (bem como no da geração) foi mencionado
que a probabilidade estaria envolvida.
• Incorporação: Na incorporação o ouvinte decide acreditar ou não em Pi . Um agente
totalmente ingênuo pode acreditar em tudo que ouve, ao passo que um agente sofisticado trata o ato da fala como evidência de Pi e não como confirmação dela.
A descrição das etapas da comunicação humana lembra a pilha de protocolos
TCP/IP e a OSI, na qual cada nı́vel no emissor prepara ou calcula de alguma forma a
mensagem, para que a contra-parte de mesmo nı́vel no receptor possa recebê-la e processá-la adequadamente. Para enviar um pacote no mundo TCP/IP, precisamos envolver o
conteúdo transmitido em diversos envelopes de marcações para que ocorra a comunicação
de forma segura. No entanto se examinarmos o texto da figura 3.1 retirado de (CUNNINGHAM, 2000) com as marcações criadas pelo reconhecedor de entidades do GATE,
veremos que o texto marcado é maior que o original. Se acrescentarmos marcações
sintáticas, semânticas (extraı́das de ontologias) e pragmáticas (oriundas de informações
acerca do ambiente), concluiremos que a mensagem M enviada representa o resumo mais
econômico do enunciado P que se deseja transmitir.
Figura 3.1: Texto com marcadores criados pelo reconhecedor de entidades do GATE
Portanto as semelhanças entre a comunicação humana e dos computadores são
bem superficiais. Existem apenas aproximações para a gramática natural (RUSSELL;
24
NORVIG, 2003), aquela que reconheceria todas as produções aceitas como válidas pelos
falantes. Também a eliminação da ambigüidade é um desafio teórico que ainda não foi
resolvido, computacionalmente difı́cil, e para propósitos práticos imediatos, não deve ser
considerado.
Como exemplo da dificuldade em lidar com a ambigüidade, considere a seguinte
frase: ”Eu nunca disse que ela roubou o dinheiro”. A seguir listamos a mesma frase com
a ênfase vocal marcada em negrito:
Eu nunca disse que ela roubou o dinheiro. (Mas alguém 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 escrito
o emissor usará outros recursos para desfazer ou diminuir a ambigüidade.
A complexidade total da comunicação humana não está ainda disponı́vel para ser
utilizada pela RI do mesmo modo que não está disponı́vel para tradução automática. É
preciso conhecer as tarefas mais simples primeiro, o que faremos na seção a seguir.
3.3
As Tarefas do Processamento da Linguagem Natural
A tradução automática é considerada por muitos autores (SILVA et al., 2007) o
marco inicial do PNL. Após uma apresentação inicial exitosa que traduziu em 1952 um
texto de 50 frases selecionadas sobre quı́mica do russo para o inglês, houve um perı́odo
entusiasmado de pesquisas. Os resultados seguintes entretanto não foram tão exitosos. A
seguir transcrevemos um exemplo encontrado em (SILVA et al., 2007) da má qualidade
dos primeiros sistemas automáticos de tradução.
(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 advantage
of) apparatus Boolean algebra.
O sistema simplesmente listava todas as possibilidade de tradução de cada palavra do russo para o inglês criando um bloco ilegı́vel de palavras. Não existia nenhum
analisador sintático e léxico capaz de selecionar as melhores alternativas de cada termo.
As tarefas do PNL se diversificaram a medida que a área amadureceu, encontrou
e procurou enfrentar problemas em todos os nı́veis da produção da linguagem. A lista a
seguir foi montada de acordo com (CUNNINGHAM, 2000) e (SILVA et al., 2007):
• Transcrição da fala.
• Classificação (etiquetar) automaticamente as unidades do texto segundo classes pertinentes à tarefa: morfossintáticas, sintáticas ou semânticas.
25
• Mapear representações da LN para representações sintáticas ou discursivas, e dessas
para LN.
• Sumarizar texto para facilitar a sua leitura.
• Tradução automática
• Geração de texto.
• Reconhecer entidades nomeadas.
• Interfaces naturais para bancos de dados (como BASEBALL) e sistemas
respondendo-perguntas.
• Geração de voz.
• Aprendizado de segunda lı́ngua e sistemas tutores
• Automação de tarefas administrativas (agenda, encontros, viagens).
• Programação automática(NLPQ e SAFE).
• Filtragem e roteamento de textos.
• Comparação, versionamento e ferramentas de autoria.
• Determinação de autoria.
• Ferramentas de acessibilidade.
Nos mais de 50 anos que nos separam das experiências pioneiras de tradução,
inúmeros programas e pacotes foram escritos por gerações de pesquisadores que resultaram em progressos razoáveis. Alguns desses programas, como o Lucene, alcançaram um
grau de maturidade para sua utilização tanto comercial e acadêmica. Outros, foram disponibilizados para a comunidade com código aberto, para poupar aos demais pesquisadores
(e ao autor) o trabalho de reescrever determinados programas consagrados ou ainda servir
como ambiente padrão de experimentação. Veremos alguns esses programas no capı́tulo
4.
3.4
Arquitetura de um sistema PLN
Segundo (SILVA et al., 2007), a arquitetura de um sistema computacional que
processa lı́ngua natural pode variar de acordo com a especificação da aplicação. Como é
freqüente na área do PLN, a maioria dos algoritmos utilizados são onerosos, e portanto a
regra é a customização caso a caso. Um sistema completo, como o da figura da página 27
exibe a maioria dos módulos que se pode empregar.
Descrevemos a seguir os componentes do sistema da figura 3.2.
• Analisador Léxico ou scanner é responsável pela separação e identificação dos
tokens da linguagem e a sua associação a atributos ou traços gramaticais ou
semânticos com base em consulta ao Léxico. Pode ser necessário uma etapa de
análise morfológica anterior ou concomitante
26
• Analisador Sintático ou parser é a etapa responsável pela construção de um estrutura sintática válida para a sentença de entrada, também chamada de estrutura
profunda. Em se tratando de lı́ngua natural adota-se uma gramática ”parcial”que
abranja as construções válidas para a área de interesse. Os formalismos mais simples são os mais eficientes.
• Analisador Semântico é responsável pela interpretação dos componentes da
sentença e dela própria. É necessário um conhecimento do domı́nio. A frase ”João
comeu a manga”terá as seguintes representações sintática e semântica:
s(sn(substpr(João)),sv(vtd(comer,passado,3ps),sn(det(o),subst(manga))
ação(comer,agente(anim(João)),objeto(comest(manga)))
A sentença ”João costurou a manga”terá estrutura profunda semelhante à acima,
trocando o terminal ”comeu”por ”costurou”. Formalismos de análise semântica
diferem dos de análise sintática. O exemplo acima foi construı́do com Lógica de
Predicados.
• Analisador do Discurso, considerando a modalidade multi-sentencial, busca o significado de uma sentença considerando os significados das sentenças próximas, anteriores ou posteriores. Para o texto ficar elegante, é comum o uso de anáforas, que
devem ser resolvidas. O analisador de discurso em geral estende a representação
semântica com anotações sobre as figuras de discurso.
• Analisador Pragmático é a interpretação da intenção do falante dentro do contexto da comunicação. ”Você quer mais prazo?”pode ser interpretado como uma
gentileza ou como uma cobrança.
27
Figura 3.2: Arquitetura de um sistema PLN segundo (SILVA et al., 2007)
28
4
FERRAMENTAS PRONTAS
A reutilização é importante tanto pela economia, como pela base comum que cria
de padrões e procedimentos entre profissionais e pesquisadores de qualquer área. A disponibilidade de ferramentas e bibliotecas prontas, preferencialmente escritas todas em uma
mesma linguagem ou ambiente, permite irmos mais longe, podemos projetar e construir
sistemas a partir da combinação de partes menores prontas.
Para a pesquisa, além da economia, o reaproveitamento facilita a comparabilidade, a discussão dos trabalhos cientı́ficos em bases comuns, além do acúmulo de uma
seqüência de produção cientı́fica de vários autores sobre uma mesma base de trabalhos.
Selecionamos ferramentas escritas em Java ou com interface em Java pela facilidade de integrá-las, pela possibilidade de utilizá-las tanto em aplicações WEB como em
aplicações standalone, e pela quantidade de bibliotecas – nativas ou não – já disponı́veis
nessa linguagem. Java tem uma coleção nativa de bibliotecas bem variada e sólida e ainda
está experimentando evolução, fruto da contribuição combinada da sua comunidade de
usuários.
Um exemplo da convergência da pesquisa para o mundo Java é o projeto WEKA –
Waikato Environment for Knowledge Analysis – da Universidade de Waikato, que iniciou
sendo escrito em C e em TCL/TK. A partir de 1993 passou a usar Java e hoje o WEKA é
a base de vários de outros projetos, colaboradores escrevem extensões para ele e serve de
base material para pesquisa em centenas de trabalhos.
Examinaremos um motor de recuperação de informações chamado Lucene e quatro frameworks de PNL: Gate, MALLET, Lemur e Simmetrics. Reunindo-os, dispomos de uma razoável plataforma de trabalho para conhecer estudar e testar estratégias de
combinação de PNL e RI.
Essas quatro biblioteca não esgotam o mundo das bibliotecas públicas para PNL,
muitas mais existem e algumas dessas outras estão listadas no anexo A. Parafraseando
Gerald Salton, somos obrigados a gastar o tempo que dispomos com o mais promissor e
facilmente disponı́vel e ignorar o resto.
O Lucene é uma biblioteca especializada na criação de ı́ndices de documentos e
indexação e casamento de consultas. Ele precisa ser associado a outros programas para
chegarmos a ter um programa de busca completo como o Yahoo ou o Google.
o Simmetrics é uma biblioteca especializada em métricas para palavras. Entre as
principais disponı́veis, de interesse para PLN, destacamos a distância de Lewenshtein e
o coeficiente de Dice. Interessante observar que a maioria dos membros dessa biblioteca
é direcionada para aplicações em biologia e que a análise de seqüências de DNA - que
é referido como o livro da vida - vem buscar apoio exatamente na mesma fonte que a
29
Lingüı́stica Computacional.
Já o Lemur é referido como Lemur Toolkit ou Toolkit nos papers dos pesquisadores da Universidade dede Massachussetts é distribuı́do juntamente com o motor de buscas
Indri.
Listamos a seguir os sites dos produtos e ( frameworks) mencionados neste trabalho, tal como disponı́veis em 2008.
Tabela 4.1: Lista e localização de recursos integráveis em projetos de IR e NLP
Nome
URL
Descrição
WEKA
http://www.cs.waikato.
WEKA é um produto
ac.nz/ml/weka/
voltado para aprendizado de máquina
GATE
http://gate.ac.uk/
GATE é um produto
voltado para engenharia
de texto
Lucene
http://lucene.apache.
Lucene é um indexador
org/
de documentos e consultas
LingPipe
http://www.cs.waikato.
LingPipe é uma biac.nz/ml/weka/
blioteca para processamento de linguagem
natural
Simmetrics http://www.dcs.shef.ac. Simmetrics é uma bibliuk/˜sam/simmetrics.html oteca aberta de métricas
e medidas de similaridade
Lemur
http://www.
Lemur é uma biblioteca
lemurproject.org/
de PNL da Universitutorials/
dade Carnegie Mellon
Esses programas foram escritos para a lı́ngua inglesa. Possivelmente será necessário criar ou adaptar módulos para lidar com a lı́ngua portuguesa, se não existirem.
Porém depois de vencida essa fase, estará disponı́vel para nosso idioma a mesma plataforma de trabalho.
4.1
Lucene
Lucene é o núcleo de um engine de busca textual. No Lucene não está incluı́da
a interface nem o crawler. Foi criado em 2000 por Douglas Cutting (GOSPODNETIC;
HATCHER, 2005), doado para a Fundação Apache e disponibilizado sob sua licença. Sua
aceitação é grande e tem portes para Python, C++, C##, Ruby, Perl, Delphi e PHP. Sua
aceitação também ocorre na comunidade cientı́fica. Chakrabarti, em seu artigo de 2004
para a WebKDD (CHAKRABARTI, 2004) o escolheu como máquina de busca padrão
para comparações.
Partindo da idéia de um documento contém campos de texto, e sendo independente de tipo de arquivo, Lucene é capaz de indexar arquivos em diversos formatos: PDF,
30
HTML e Microsoft Word. É um biblioteca de indexação e busca e não contém robôs de
busca (crawler) nem parser de HTML.
Para completar o Lucene, que afinal pode ser visto como um banco de dados dedicado a buscas textuais, existem dois outros projetos na Fundação Apache: o Nutch que
acrescenta funções de busca e parsing de HTML e o Solr que é um servidor WEB de
busca completo baseado no Lucene.
Os principais conceitos para começar a entender o Lucene são:
Tabela 4.2: Conceitos Básicos do Lucene
Explicação
É a classe que prepara o texto para indexação. Inglês e
lı́nguas latinas podem usar a StandardAnalyzer
Payloads
Cadeias de bytes carregadas com um ou mais posições de
termos
Snowball Stemmer Coleção de stemmers escritos por terceiros
Document
Documento é um registro no ı́ndice. Um documento tem
uma lista de campos, cada campo com um nome e um valor
textual.
Term
Termo é a unidade de indexação, que em lı́nguas ocidentais
corresponde a uma palavra.
TermEnum
TermEnum é utilizado para enumerar todos os termos em
um ı́ndice para um dado campo, a despeito de quais documentos em que ocorra o termo. Algumas consultas são
implementadas por enumeração de termos que seguem um
padrão, ou através de operações OR a partir da enumeração.
TermDocs
Ao contrário de TermEnum, TermDocs são utilizados para
identificar quais documentos contém um dado Termo.
TermDocs também dá a freqüência do termo no documento.
TermFreqVector
Um vetor de Freqüência de Termos é uma estrutura de dados
contendo termos e freqüência de determinado documento,
informação que pode ser recuperada através do objeto IndexReader apenas quando Vetores de Termos são armazenados durante a indexação.
Conceito
Analyser
4.1.1
Principais Pacotes do LUCENE
Os principais elementos da API do Lucene são expostos na tabela 4.3 da página
36.
Os pacotes listados na tabela são da versão 2.4 do Lucene. Observa-se a integração
da ferramenta de indexação Lucene com produtos como WordNet e Wikipedia.
4.2
MALLET
MALLET4 é uma biblioteca em Java para Recuperação de Informações criada na
Universidade da Pennsilvania por Andrew McCallun além de diversos colaboradores. A
4
Machine Learning for Language Toolkit
31
lista de patrocinadores é igualmente extensa.
4.2.1
Filtros de Importação do MALLET
Para o MALLET os dados são uma lista de ”instâncias”. Uma instância pode ter
um nome e uma classe (se o problema for de classificação). Se o problema for identificar a
lı́ngua de uma página WEB, a instância pode consistir em um vetor de palavras contadas,
o nome seria a URL e a classe a lı́ngua já identificada, ou por identificar.
4.2.2
Classificadores do MALLET
Um classificador é um algoritmo que pode fazer disitinções entre classes fixas tais
como ”spam”ou ”não-spam”baseando-se em exemplares já classificados. MALLET traz
diversos classificadores entre os quais Naı̈ve-Bayes, Máxima Entropia (C-45) e Árvores
de Decisão. Também traz pacotes para avaliar os modelos gerados, fazendo relatórios
através matriz de confusão e testes de cross-validation. Todos os algoritmos tem exemplos para auxiliar sua compreensão.
4.2.3
Principais Pacotes do MALLET
Os principais pacotes disponı́veis no MALLET são expostos na tabela 4.4 da
página 37.
4.3
GATE
GATE é acrônimo de General Architecture for Text Engeneering foi criado por
Hammish Cunningham e seus colegas na Universidade de Sheffield tendo em vista, no
campo do PNL, o mesmo problema encontrado no campo da RI: a falta de um ambiente
integrado e pronto para a utilização, com alto grau de automação, que incorpore algoritmos já aceitos e que não precisem ser baixados e portados, recompilados e depurados a
cada experimento e que permita a condução de experiências repetitivas e documentadas
de novos módulos6 .
• Análise Morfológica
• Reconhecimento de Entidade Nomeada
• Extração de Informação
• Etiquetamento
• Co-referência (resolução de anáforas)
• Análise de Texto
Na figura 3.1, encontrada em 3.1, observamos uma árvore de análise sintática
elaborada pelo GATE.
6
Nesse aspecto, o autor se inspirou em MatLab e Mathematica para tentar criar seu próprio ambiente de
experimentação de PNL
32
Figura 4.1: Análise sintática com o GATE
4.4
Lemur
LEMUR é uma biblioteca e associada a um motor de recuperação chamado INDRI. As principais caracterı́sticas de LEMUR seriam:
• Caracterı́sticas Gerais
Linguagens de consulta usando InQuery e Indri,
Recuperação XML e estruturada,
Utilizada em várias coleções de testes: TREC CDs 1 a 5, wt10g, RCV1, gov1
e gov2,
Indexação de páginas WEB,
Interface para Windows, Linux e WEB,
Recuperação de Informação Distribuı́da e agrupamento de documentos,
Código escrito em C++, 6 anos de uso por uma comunidade de usuários e
pesquisadores
Interface em Java e C,
Recuperação de Informação Distribuı́da e agrupamento de documentos.
• Indexação
Diversos métodos de indexação conforme o tamanho da coleção,
Suporte nativo para inglês, árabe e chinês,
Porter e Krovetz stemmers,
Indexação incremental,
33
Suporte para texto do TREC, WEB, HTML, XML, PDF, MBox, MS Word e
MS PowerPoint,
Indice inline e offset para anotações de texto (POS e Entidades Nomeadas),
Indexa atributos de documentos.
• Recuperação:
Suporte para a maioria dos modelos tais como Espaço Vetorial, KLDivergência, Indri, Tf-Idf, Okapi e InQuery,
Realimentação de relevância e Pseudo-Realimentação de relevância7 ,
Expansão de wildcards (com Indri),
Recuperação cruzada de linguagem,
Expansão de wildcards (com Indri),
Amaciamento através de Dirichilet apriori e Cadeias de Markov,
Suporta apriori arbitrário de documentos (Page Rank, URL depth, usw)
4.5
Simmetrics
Simmetrics é uma biblioteca Java criada na Universidade inglesa de Sheffield especializada em métricas. As métricas, embora isoladamente não formem um aplicativo
completo são peças básicas utilizadas em outros projetos. A distância de Lewenshtein
encontra utilização em um modo sofisticado de correção de erro, tanto na lı́ngua falada
como na escrita. Na Simmetrics existem métricas de RI, como o Coeficiente de Dice. E
principalmente várias métricas de distância de edição entre strings para uso na Biologia,
em genética.
1. Distância de Hamming: é o número de bits de diferença entre duas seqüências de
bits.
2. Distância de Lewenshtein: é a distância de edição entre duas seqüências de caracteres, contando da seguinte forma: copia de uma string para outra (custo 0), apagar
um caractere na string 1 (custo 1), inserir um caractere na string 2 (custo 1) e substituir um caractere por outro (custo 1). O algoritmo utiliza programação dinâmica.
3. Distância de Needleman-Wunch: também conhecida como Sellers, é uma extensão
de Lewenshtein na qual cada inserção extra (gap) custa um valor arbitrário.
4. Distância de Smith-Waterman: é outra extensão da de Lewenhstein, onde existem
duas funções ajustáveis, uma para a cópia (um custo variado por tipo de cópia) e
um custo por operação de ”gap”(inserção ou deleção).
5. Distância de Gotoh: uma extensão da distância de Sith-Waterman, que permite
custos de ”gap”baseados no comprimento da seqüência l. Utilizado em biologia,
para alinhamento de seqüências de DNA
7
Para Relevance and pseudo-relevance feedback
34
6. Distância de Bloco ou L1: distância a se percorrer no problema dos blocos da
cidade, no qual não se pode percorrer diagonais.
7. Distância de Monge e Elkan: Geralmente confundida coma Smith-Waterman, é
uma distância de Gotoh estendida, que leva em conta a similaridade semântica de
campos e sub-campos em consideração. Cada sub-campo é comparada com o subcampo mais similar utilizando a distância de Gotoh ao passo que entre campos são
comparados com algoritmo próprio.
Além das listadas, Simmetrics coleciona numerosas outras métricas, geralmente
empregadas em análise de seqüências de DNA em biologia. A ênfase nessas métricas são
variações na maneira de pesar as distâncias entre os elementos da cadeia e de valorar as
inserções no meio da cadeia, porém mantendo a mesma valoração para seus terminais.
Simmetrics também tem um levantamento do desempenho das métricas colecionadas, ilustrado na figura 4.2. Note que a ordenada é logarı́tmica, e portanto, todas as
métricas são consumidoras de recursos, a curvatura suave da figura pode ser enganadora.
Infelizmente, não dispomos de recursos no momento para avaliar mais exatamente
o significado do gráfico da figura 4.2 em termos da complexidade computacional, nem a
documentação da biblioteca fornece essa medida.
Figura 4.2: Desempenho comparado das métricas do Simmetrics
4.6
Outros Recursos
Além dos recursos mencionados no capı́tulo 4, muitas outras ferramentas, recursos e bibliotecas prontas estão disponı́veis para exame e eventual utilização. Precisamos
35
examinar no estudo as bibliotecas mais promissoras e disponı́veis, mas não se descarta
que entre as demais não possa existir contribuições úteis e que no contexto certo não se
revelem mais úteis do que as da seção 4.
36
Tabela 4.3: Pacotes e Classes Principais do LUCENE 2.4.0 e suas funções
Nome
Descrição das Classes
org.apache.lucene.analysis
O pacote principal do Lucene, possui filtros,
stemmers, separadores de palavras, separadores de letras, uniformizadores (retirar acento,
maiúsculas ou minúsculas).
org.apache.lucene.analysis.Analyzer Essa classe é um analisador 1 cria um TokenStreamer, o qual analisa texto.
org.apache.lucene.analysis.Tokenizer Um Tokenizer é um TokenStream cuja entrada
é um Reader2 .
org.apache.lucene.analysis.br
Pacote com stemmer brasileiro baseado no
stemmer alemão.
org.apache.gdata.data
Este pacote contém a representação interna dos
entradas dos GData.
org.apache.lucene.index
Código para manter e acessar ı́ndices.
org.apache.lucene.queryParser
Um analisador de consultas implementado com
JavaCC3
org.apache.lucene.search
Código para fazer procura em ı́ndices. Em destaque para a classe ScoreDocComparator, responsável por comparar dois objetos ScoreDoc
para ordenamento.
org.apache.lucene.store
Pacote de I/O binário para todos os dados dos
ı́ndices.
org.apache.lucene.wordnet
Este pacote utiliza sinônimos definidos no
WordNet para criar e aramazenar um ı́ndice no
Lucene, que será utilizado em expansão de consultas.
org.apache.lucene.wikipedia.analysis Este pacote contém apenas uma classe StandardTokenyzer que é compatı́vel com a sintaxe
da Wikipédia.
org.apache.regexp
Esta classe existe para permitir acesso ao útil
porém protegido pacote Regexp do Jakarta.
org.tartarus.snowball
Pacote ligado a utilização de stemmers em
várias linguagens, aparentemente é uma
implementação mais moderna e prática dos
stemmers separados por lı́ngua
com.sleepycat.db
Acesso ao banco de dados, necessário após uma
mudança na API desse mesmo banco.
lucli
Interpretador de linha de comando do Lucene
37
Tabela 4.4: Pacotes Principais do MALLET e suas funções
Nome
Descrição das Classes
cc.mallet.classify
AdaBoost, C4.5, Bagging, Balanced Winnow, Decision
tree, Naı̈ve Bayes, Winnow,
cc.mallet.classify.evaluate Matriz de Confusão, Cobertura de Acurácia e Gráficos
cc.mallet.cluster
Agrupador Guloso, Kmeans, KBest Cluster, HillClimbing
Cluster e Guloso por Densidade.
cc.mallet.fst
Transdutores, incluindo Campo Randômico Condicional5 .
cc.mallet.fst.confidence
Interface para Transdutores Corretores que corrigem segmentos gerados por transdutores.
cc.mallet.grmm.inference Contém interfaces implementadas por todos inferidores,
que são algoritmos para computar (ou estimar) distribuições
marginais sobre nós de um modelo representado como um
grafo.
cc.mallet.grmm.learning
Contém classes para fazer transformações globais em
gráficos depois de gerados
cc.mallet.optimize
Contem classes que buscam o máximo de uma função.
Exemplo: LineOptimizer, ByGradient, ByGISUpdate, ByBatchGradient.
cc.mallet.pipe
Contém classes para transformar dados arbitrários em
instâncias.
cc.mallet.topics
Esse pacote contém um grupo de algoritmos para
otimização de modelos: Latent Dirichilet Allocation, Four
Level Pachinko Allocation, entre outros.
cc.mallet.type
Esse pacote contem os tipos fundamentais de MALLET, incluindo Vetores de Caracterı́ticas, Instancia, Etiqueta, entre
outros.
38
Tabela 4.5: Mais recursos vinculados à PNL
URL
Observação
http://opennlp.
openNLP é um sı́tio que
sourceforge.net/
procura acompanhar as
opções em bibliotecas
de NLP
Wordnet
http://www.cs.waikato.
WordNet é dicionário e
ac.nz/ml/weka/
ontologia genérica
AGFL
http://www.agfl.cs.ru.
Grammar Work Lab
nl/index.html
para gramáticas AGFL
da Universidade Rabdoud de Nijmegen
WordFreakL
http://wordfreak.
Biblioteca
para
sourceforge.net/
anotações automáticas
ou humanas que facilita
a correção humana de
anotações automáticas
WordNet::Similarity
http://wn-similarity.
Módulos Perl que imsourceforge.net/
plementam várias medidas semânticas de similaridade baseadas no
WordNet
Livro sobre IR
http://www-csli.
Site do livro on-line do
stanford.edu/˜hinrich/
Manning e Prabhakar
information-retrieval-book.
sobre IR com estudo dihtml/
rigido
Stanford
http://www-nlp.
Tudo sobre NLP esstanford.edu/links/
tatı́stico, inclusive o restatnlp.html
positório de utilitários
IR Wiki
http://ir.dcs.gla.ac.
Infomação geral e
uk/wiki/FrontPage
acompanhamento dos
TREC
Natural Language Toolkit http://nltk.org/index.
Softwares, conjuntos de
php/Main_Page
dados e tutoriais
Nome
openNLP
39
5
TRABALHOS FUTUROS
O trabalho futuro, seguimento natural desse estudo é montar um laboratório com o
Lucene, Gate, MALLET e procurar integrar o Lemur no mesmo projeto. Córpora devem
ser buscados nos mesmos sites em lı́ngua inglesa ou nos congêneres nacionais para se
poder criar trabalhos comparáveis e referenciáveis.
Pacotes nacionais para PLN podem ser buscados nos grupos da UFSCAR e USP e
utilizados, caso sejam integráveis em um projeto baseado em Java. A UFMG também foi
identificada como referência em Recuperação de Informações, é uma ótima oportunidade
de trocar informações com pesquisadores brasileiros.
As seções sobre IR e PLN devem ser aprofundadas para incluir mais técnicas e
referências em lı́ngua portuguesa. O objetivo é criar um projeto que permita integrar um
ou mais desses pacotes e trabalhar sobre córpora em lı́ngua portuguesa, e que permita
buscar a melhoria da recuperação padrão do Lucene com a incorporação de filtros PLN
ao esquema de avaliação de relevância dos documentos indexados.
40
6
CONCLUSÃO
Foram examinadas brevemente a Recuperação de Informações e o Processamento
de Linguagem Natural, inclusive do ponto de vista da tipologia dos modelos de RI atualmente empregados.
Em uma pesquisa futura procuraremos novas maneiras de tratar o problema de selecionar documentos relevantes para uma dada consulta a partir do refinamento do modelo
de documento ou então da técnica de cálculo da relevância de cada termo em um documento ou consulta utilizando caracterı́sticas obtidas com Processamento da Linguagem
Natural que sejam mais computacionalmente econômicos.
O Lucene é a plataforma adequada para receber módulos que modifiquem suas
caracterı́sticas de filtragem e indexação pela facilidade de acesso ao seu código e pela
possibilidade de se fazer comparações com o trabalho de outros grupos de pesquisa.
A disponibilidade de diversas aplicações de PLN, maduras e testadas como GATE,
MALLET e Simmetrics, escritos na mesma linguagem JAVA que o Lucene facilitará a
criação e testagem de módulos embutidos no Lucene.
Adicionalmente, a pesquisa descobriu o Lemur, pacote da Universidade Carnegie
Mellow, escrito em C++, porém com uma interface em Java.
A criação ou adaptação de módulos de análise, filtragem e indexação adequados à
lı́ngua portuguesa tem agora uma boa oportunidade de ser empreendida, pois temos agora
uma situação de grande disponibilidade de componentes prontos ou semi-prontos para
acompanhar as tendências da pesquisas em outros idiomas e colaborar com o cenário da
pesquisa brasileiro.
41
REFERÊNCIAS
CHAKRABARTI, S. Discovering Links Between Lexical and Surface Features in Questions and Answers. In: WEBKDD, 2004. Anais. . . Springer, 2004. p.116–134. (Lecture
Notes in Computer Science, v.3932).
CUNNINGHAM, H. Software Architecture for Language Engineering.
2000. Tese (Doutorado em Ciência da Computação) — University of Sheffield.
http://gate.ac.uk/sale/thesis/.
CUNNINGHAM, H.; MAYNARD, D.; BONTCHEVA, K.; TABLAN, V. GATE: A framework and graphical development environment for robust NLP tools and applications.
In: ANNIVERSARY MEETING OF THE ASSOCIATION FOR COMPUTATIONAL
LINGUISTICS, 40., 2002. Proceedings. . . [S.l.: s.n.], 2002.
GOSPODNETIC, O.; HATCHER, E. Lucene in Action. [S.l.]: Greenwich, EUA : Manning, 2005. 421p.
GREEN, B. F.; WOLF, A. K.; CHOMSKY, C.; LAUGHERY, K. Baseball, An Automatic Question Answering System. In: Computers and Thought, Feigenbaum and Feldman(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 to
Natural Language Processing, Computational Linguistics, and Speech Recognition. [S.l.]:
Upper Saddle River, EUA : Prentice-Hall, 2000.
KUROPKA, D. Modelle zur Repräsentation natürlichsprachlicher Dokumente. [S.l.]:
Berlin : Logos Verlag, 2004. 242p.
LUCENA, C. J.; BAUZER, C. Grandes Desafios da Pesquisa em Computação no Brasil de 2006 a 2016. [S.l.]: Sociedade Brasileira de Computação, 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.; GRAçAS VOLPE, M. das. Introdução
ao Processamento das Linguagens Naturais e Algumas Aplicações. [S.l.]: São Paulo,
Brasil : USP, UFSCar e UNESP, 2007.
WIKIPEDIA. Informationa Retrieval — Wikipedia, The Free Encyclopedia. [Online;
acessada em 22-setembro-2008].
43
ANEXO A
GLOSSÁRIO
Embora esse texto seja uma panorâmica das áreas de RI e PNL, e no seu bojo sejam
apresentadas muitas definições, listamos a seguir mais alguns termos encontradiços nos
artigos e livros cujo conhecimento do significado possa ser útil ou interessante.
1. Conceito é uma lista de termos vinculadas (CUNNINGHAM et al., 2002)a mesma
coisa ou idéia.
2. Gazetteer é um dicionário ou diretório de informações geográficas sobre lugares e
nomes de lugares.
3. Ontologia é um modelo para descrever o mundo que consiste de tipos, propriedades, tipos de relacionamentos e restrições.
4. Ontologia genérica é uma ontologia como WordNet que não se prende a determinado assunto e pode ser visto como um dicionário hierarquizado por relacionamentos ”é um”.
5. Stop Words são palavras a serem excluı́das da análise estatı́stica ou da análise vetorial, geralmente palavras de classes fechadas como artigos, pronomes, advérbios
(de tempo, modo, afirmação, negação, dúvida, exclusão ou inclusão), preposições,
conjunções e interjeições.
6. Meronı́mia é um relacionamento ”parte de”.
7. Polissemia é a capacidade de um signo (termo, palavra ou locução) de ter múltiplos
significados (semenes).
8. Hipônimo é um conceito especializado de outro. Cavalo árabe é especialização de
cavalo.
9. Hiperônimo é um conceito que generaliza outro. Carro é generalização de mille.
10. Synset é um conceito do Wordnet, formado por um ou mais Lemmas.
11. Lemma, para o WordNet é termo que significa um conceito. ”Carro”e ”Automóvel”são dois lemas do mesmo conceito e tem por hiperônimo ”veı́culo motorizado”.
12. Cadeias Escondidas de Markov
44
13. Bag of Words é um modelo simplificado utilizado em PLN e RI. Nesse modelo,
um texto é apresentado como um conjunto desordenado de palavras, ignorando
gramática ou ordem. Pode ser empregado por um classificador Naı̈ve Bayes ou em
Análise Semântica Latente.
14. Latent Semantic Analysis é uma técnica de PLN patenteada em 1988, especialmente de semântica vetorial, que analisa as relações entre um conjunto de documentos e os termos neles contidos através da criação de um conjunto de conceitos.
15. Word Sense Disambiguation é o processo de esclarecimento do sentido de um
termo em uma senteça ou no discurso falado. Existem abordagens profundas ou
superficiais1 .
16. Rede Semântica é um grafo que representa o relacionamento entre conceitos.
Também é chamada de representação de conhecimento.
17. Etiquetagem gramática2 também chamado de desambiguação de tipo de palavra,
identifica o tipo gramatical - substantivo, verbo, adjetivo - de cada palavra.
18. Sstate space search é um campo da área da Inteligência Artificial na qual sucessivas configurações ou estados são considerados conforme determinado critério para
a escolha de estado-ótimo. O conjunto de estados futuro do sistema forma um grafo
no qual dois estados estão conectados se existe uma operação que possa conduzir o
sistema do primeiro estado ao segundo.
19. Cadeia de Markov, homenagem a Andrey Markov, é um processo estocástico com
a propriedade de Markov, que significa que os estados presente e futuros são independentes dos estados passados. A mudança de estado em cada momento depende
de uma distribuição de probabilidades, que define cada transição possı́vel.
20. Shallow Parsing é uma análise superficial, ligeira, que evita a análise mais completa que é NP-completa. Ela identifica substantivos, locuções nominais, verbos,
mas não faz análise sintática mais elaborada.
1
2
Deep and shallow approaches
Part-of-Speech tagging.