Mineração da Web
Recuperação de Informação
Tipos de Consultas &
Operações sobre Consultas
Flávia Barros
1
Aulas passadas
Modelos de RI

Booleano, Espaço Vetorial, ...
Preparação dos documentos

Operações sobre o texto
 Criação da Visão Lógica do documento
Lista de termos usado para representar o
documento
Criação da representação do documento


 Com base em algum Modelo de RI
2
Roteiro – 1a parte
Tipos de Consultas
Consultas baseadas em Palavras-Chaves




Baseadas em palavras isoladas
Com contexto
Booleanas
Em Linguagem Natural
Com casamento de Padrão
Com estrutura
3
Tipos de Consultas
Existem diversos tipos de consultas que
podem ser submetidas aos sistemas de RI
Contudo...


Nem todos os tipos podem ser usados em todos
os sistemas
Isso vai depender do modelo de RI adotado pelo
sistema
4
Consultas baseadas em
Palavras-chave
Tipos




Baseadas em palavras isoladas
Com contexto
Booleanas
Em Linguagem Natural
Permitem ordenamento das respostas


segundo a função de relevância do modelo de RI
adotado
Segundo algum outro critério adicional
5
Consulta baseada em
Palavras-chave isoladas
Single Keyword query


Tipo mais simples de consulta a um sistema de RI
Consiste em uma lista de palavras
 Sem operadores booleanos explícitos
 Porém funciona como OR
Funcionamento geral


O sistema de RI recupera todos os documentos que
contêm pelo menos uma das palavras da consulta
Em seguida, os documentos recuperados são
ordenados de acordo com o modelo de RI
implementado pelo sistema
6
Consultas com Contexto
Posição das Palavras
Alguns sistemas de RI são capazes de buscar
palavras dentro de algum “contexto”

Documentos onde as palavras da consulta
aparecem próximas uma da outra podem ser mais
relevantes do que aqueles onde as palavras
aparecem distantes
 Ex.: “recuperação” e “informação” no contexto de
docs. sobre o tema de Recuperação de Informação
A consulta também é formulada como uma
lista de palavras

Contudo, a ordenação dos documentos depende da
posição das palavras nesses documentos
7
Consultas com Contexto
Busca pela Posição das Palavras
Como verificar essa proximidade?

Depende da implementação do sistema de RI
 E.g., Bases de índices invertidos que guardam a posição
onde cada palavra ocorre em cada documento
Palavra
Casa
Amarela
...
Documento
(Doc1, 12); (Doc2, 1); ....
(Doc1, 13); (Doc2, 20); ....
...
8
Consultas com Contexto
Grupos Nominais (GN)
Consultas baseadas em Grupos Nominais

recuperam documentos com um GN específico
 i.e., lista de palavras contíguas no texto do
documento
 ex., “inteligência artificial”
Pode levar em consideração stopwords e/ou
stemming

Exemplo - “venda carro” casa com
 “venda de carros”
 “vendendo carro”,…
9
Consultas com Contexto
Grupos Nominais
A Base de índices do sistema de RI deve
armazenar as posições de cada palavra no
documento
Processo de recuperação

Recuperar os documentos que contêm todas as
palavras da consulta
 Registrando as posições de cada palavra nos docs

Fazer a intersecção entre documentos recuperados
 Para eliminar redundâncias

Verificar a ocorrência do GN (palavras contíguas)
10
Consultas com Contexto
Proximidade das Palavras
Consulta


Lista de palavras com uma distância máxima
permitida entre elas
Exemplo: “carro” e “corrida” com 4 palavras
casa com “…carro que ganhou a corrida…”
As palavras não precisam estar na mesma
ordem em que foram definidas na consulta

Exemplo: “…corrida terminou com carro…”
Pode também levar em conta stemming e/ou
stopwords
12
Consultas com Contexto
Busca com Proximidade das Palavras
Semelhante à busca por grupos nominais


Recupera os documentos que contêm todas as
palavras da consulta
Em um contexto que satisfaz as restrições de
proximidade
13
Consultas com Contexto
Documentos que satisfazem uma consulta
com Contexto podem ser ordenados da
mesma forma que no caso das consultas
básicas

i.e., de acordo com o modelo de RI implementado
pelo sistema
Para consultas por proximidade, a distância
entre os termos também pode ser levada em
conta para definir a relevância do documento

Ex.: documento com o texto “…corrida de carro…”
seria mais relevante que documento com texto
“…carro que ganhou a corrida…”
15
Consultas Booleanas
Palavras combinadas com operadores booleanos:
 OR: (ki OR kj )
 AND: (ki AND kj )
 BUT: (ki BUT kj )
 Satisfaz ki but not kj
Em geral, sistemas de RI não usam o operador NOT


Uma vez que um número muito grande de documentos
poderia ser recuperado
Operador BUT restringe o universo de documentos
Problema

Usuários inexperientes têm dificuldades com lógica
booleana
16
Consultas Booleanas
Recuperação com índices invertidos
Palavra isolada

Recupera documentos contendo essa palavra
OR

Recupera docs. com ki e kj , e faz a união dos resultados
AND

Recupera docs. com ki e kj , e faz a interseção dos
resultados
BUT

Recupera docs. com ki e kj , e utiliza o conjunto
complementar dos resultados
17
Consultas em Linguagem Natural
Em geral, consultas de texto completo são
consideradas como strings arbitrárias pelos
sistemas de RI de propósito geral

Excluímos aqui os sistemas de Pergunta-Resposta,
e os sistema de RI com interface em Linguagem
Natural
No modelo Espaço Vetorial, essas consultas


São tratadas como um “bag” de palavras
São processadas usando métodos padrão de
recuperação com Espaço Vetorial
18
Casamento de Padrão
Alguns sistemas de RI permitem consultas
que “casam” com strings

em lugar de apenas palavras isoladas
Um padrão é descrito por um conjunto de
características sintáticas

Padrão simples
 ex., uma palavra, um prefixo, um sufixo, etc

Padrão complexo
 ex., expressões regulares
19
Casamento de Padrão
Estamos interessados em documentos que
contêm segmentos de texto que casam com o
padrão especificado
Isso requer estruturas de dados e algoritmos
mais sofisticados do que índices invertidos
para uma recuperação eficiente
20
Casamento de Padrão
Padrões Simples
Prefixos


Padrão que casa com o início da palavra
“anti” casa com “antiguidade”, “anticorpos”, etc.
Sufixos


Padrão que casa com o final da palavra
“ções” casa com “canções”, “infecções”, etc.
Substrings


Padrão que casa seqüências quaisquer de caracteres
“cid” casa com “capacidade”, “genocídio” etc.
Intervalos


Pares de strings que casam com qualquer palavra
“alfabeticamente” entre eles
“tin” to “tix” casa com “tipo”, “tiro”, “tísico”, etc.
21
Casamento de Padrões Simples
Tratamento de Erros
Permite a recuperação de documentos com
palavras “similares” a uma dada palavra

Caso de consulta ou documentos com erros
 Erros de edição, erros de OCR, espaço no meio da
palavra, dentre outros
Recupera documentos que são similares até
um dado limite, medido por

Distância de edição
 Levenstein distance

Subseqüência comum mais longa
 Longest Common Subsequence (LCS)
22
Casamento de Padrões Simples
Tratamento de Erros
Distância de edição - Levenstein distance

Número mínimo de caracteres deletados,
adicionados ou substituídos necessários para
tornar os 2 strings equivalentes
 “casamento” para “casmento” tem distância = 1
 “casamento” para “casammentto” tem distância = 2
 “casamento” para “cazammeno” tem distância = 3
23
Casamento de Padrões Simples
Tratamento de Erros
Subseqüência comum mais longa



Computa o tamanho da subseqüência de
caracteres mais longa comum aos dois strings
Uma subseqüência de um string é obtida pela
eliminação de zero ou mais caracteres
Exemplos:
 “casamento” e “asamento” = 8
 “casamento” e “casammentto” = 5
24
Casamento de Padrões Complexos
Expressões Regulares
Linguagem para compor padrões complexos a partir
de padrões simples


Um caracter individual é uma expressão regular (ER)
União
 Se e1 e e2 são ERs, então (e1 | e2 ) é uma ER que casa
com tudo que e1 ou e2 casam

Concatenação
 Se e1 e e2 são ERs, então e1 e2 é uma ER que casa com
um string que consiste em um substring que casa com
e1 imediatamente seguido de um substring que casa e2

Repetição (Kleene closure):
 Se e1 é uma ER, então e1* é uma ER que casa com uma
seqüência de zero ou mais strings que casam com e1
25
Casamento de Padrões Complexos
Expressões Regulares
Exemplos de Expressões Regulares

(u|e)nabl(e|ing) casa com





unable
unabling
enable
Enabling
(un|en)*able casa com




able
unable
unenable
enununenable
26
Consultas com Estrutura
Assumem que o documento possui uma
estrutura que pode ser explora na busca
A estrutura poderia ser:

Conjunto fixo de campos
 e.g. título, autor, resumo, etc.

Estruturas hierárquicas em forma de árvore
livro
capítulo
capítulo
título
seção
título
título
seção
subseção
27
Consultas com Estrutura
Permitem consultas por textos que ocorrem
em campos específicos:

“inteligência artificial” aparecendo no título do
capítulo
SFQL


Relational database query language SQL
aumentada com busca “full text”
Select abstract from journal.papers where
author contains “Teller” and
title contains “nuclear fusion” and
date < 1/1/1950
28
Roteiro - 2a parte
Operações sobre as Consultas
Expansão de Consultas
Feedback de Relevância
29
Expansão de Consultas
Objetivo:

Adicionar novos termos à consulta
 Termos correlacionados
Motivação

Aumentar a quantidade de documentos
recuperados
 Cobertura do sistema de RI
30
Expansão de consultas usando
Tesauros
Tesauros contêm sinônimos e termos
semanticamente relacionados às suas entradas
(palavras)
Exemplo:
physician
syn: ||croaker, doc, doctor, MD, medical,
mediciner, medico, ||sawbones
rel: medic, general practitioner, surgeon,
31
Expansão de consultas usando
Tesauros
Para cada termo t da consulta, expande a
consulta com os sinônimos e palavras
relacionadas a t contidos no tesauro
Esse método geralmente aumenta a
cobertura da recuperação

Recupera mais documentos
Porém, pode diminuir significativamente a
precisão


Recuperar documentos irrelevantes
Particularmente para termos ambíguos
32
WordNet
O mais elaborado banco de dados de
relacionamentos semânticos de palavras em
inglês
Desenvolvido pelo famoso psicólogo cognitivo
George Miller e um grupo da universidade de
Princeton
Contém cerca de 144,000 palavras em inglês

Substantivos, adjetivos, verbos, e advérbios
agrupados em cerca de 109,000 sinônimos
chamados de synsets.
33
Expansão com Tesauro Estatístico
Análise Automática Global
Tesauros produzidos manualmente


não são facilmente encontrados para todas as
línguas
são limitados no tipo de relações semânticas que
representam
Termos semanticamente relacionados podem
ser descobertos a partir de análises
estatísticas em um corpus de documentos
36
Análise Automática Global
Constrói matrizes que “quantificam”
associações entre termos

Matriz de associação
 Considera a co-ocorrência (ou freqüência comum) dos
termos em todos os documentos do corpus

Matriz de correlação métrica
 considera a distância entre os termos nos documentos
do corpus
 as distâncias entre todas as ocorrências desses termos
no mesmo documento são contadas, o que
indiretamente quantifica a co-ocorrência dos termos
Expande consultas usando os termos mais
similares estatisticamente

i.e. com maior associação
37
Análise Automática Global
Expansão da Consulta
Regra Geral

Para cada termo i da consulta, expanda a consulta
com os n termos j com maior valor de cij
(correlação)
Mais de um fator de correlação pode ser
combinado para escolher os termos para a
expansão

Por exemplo, pegar os n maiores termos de
ambas as matrizes e fazer a interseção
 determinando que termos estão relacionados em ambas
as matrizes
43
Expansão da Consulta
Problemas com a Análise Global
Ambigüidade

pode introduzir termos estatisticamente
relacionados que, mesmo assim, são irrelevantes
para a consulta
 “Apple computer”  “Apple red fruit computer”
 apple e red fruit estão relacionados no corpus de docs.
 Porém, red fruit não é relevante para a consulta original
Redundância

Uma vez que os termos adicionados são
correlacionados aos termos da consulta original, a
expansão pode não recuperar muitos documentos
adicionais
44
Expansão da Consulta
Análise Automática Local
Após a consulta inicial, determina termos
correlacionados analisando os m primeiros
documentos recuperados

i.e. de melhor ranking
Esta análise se baseia apenas em um conjunto
“local” de documentos específico para uma
consulta
Evita ambigüidade, uma vez que considera
apenas documentos relevantes em um contexto

“Apple computer” 
“Apple computer Powerbook laptop”
45
Análise Global vs. Local
Análise Global

requer computação intensiva off-line
 durante a construção da matriz de correlações entre
termos
Análise Local


requer menos computação para cálculo das
correlações
Entretanto, esse cálculo é refeito para cada
consulta em tempo de execução
Análise local tem gerado melhores resultados
experimentais
46
Expansão de Consultas
Conclusões
Expansão de consultas com termos
relacionados pode melhorar desempenho do
sistema de RI

particularmente a cobertura
Contudo, termos similares devem ser
escolhidos com cuidado para evitar perda de
precisão
48
Feedback de relevância
Após apresentar os resultados de uma
consulta, o sistema de RI pode permitir ao
usuário fornecer feedback sobre um ou mais
documentos recuperados
Esse feedback pode ser usado para
reformular a consulta inicial


Novos resultados serão produzidos com base na
consulta reformulada
Processo é interativo e iterativo
49
Arquitetura para Feedback de
Relevância
Consulta
inicial
documentos
Consulta
revisada
Reformulação
da consulta
Feedback
1. Doc1 
2. Doc2 
3. Doc3 
.
.
Rankings
Documentos
reordenados
Sistemas de RI
Documentos
ordenados
1. Doc1
2. Doc2
3. Doc3
.
.
1. Doc2
2. Doc4
3. Doc5
.
.
Feedback de relevância
Repesagem de Termos
Term reweighting
Objetivo:

Aumentar o peso dos termos que aparecem em
documentos relevantes e diminuir o peso de
termos que aparecem em documentos
irrelevantes
Existem diversos algoritmos para reformular
consultas com base em repesagem de pesos
51
Feedback de relevância
Repesagem de Termos
Reformulação de consulta para o Modelo
Vetorial

Nesse modelo, consultas e documentos são
representados como vetores de pesos
 Modelo vetorial recupera documentos que são similares à
consulta do usuário

Se soubéssemos a priori que documentos são
relevantes, saberíamos quais consultas seriam as
mais adequadas
 As consultas ideais seriam aquelas mais similares aos
documentos relevantes no espaço vetorial
52
Feedback de relevância
Repesagem de Termos
Reformulação de Consulta para o Modelo
Vetorial



Adicione à consulta inicial os vetores dos
documentos considerados com relevantes
Subtraia da consulta inicial os vetores dos
documentos considerados com irrelevantes
Desta forma, os pesos da consulta são
reformulados, aproximando-se dos documentos
relevantes
53
Feedback de relevância
Repesagem de Termos
Métodos:



Método Rochio Padrão
Método Ide
Método Ide “Dec Hi”
Ocultei os slides pq era muita fórmula……..
54
Feedback de relevância
Repesagem de Termos
Comparação dos Métodos

Todos os métodos, de uma forma geral, melhoram
os resultados da RI
 Resultados experimentais não indicam uma dominância
clara de nenhum método


Geralmente, parâmetros são definidos como
constantes iguais a 1
Alguns autores usam apenas o conjunto dos
documentos relevantes (ou seja  = 0 )
 Método de Feedback Positivo
60
Feedback de relevância
Porque Feedback não é largamente usado



Usuários algumas vezes relutam em fornecer
feedback explícito
Requer maior tempo de computação
Às vezes, dificulta o entendimento de porque um
determinado documento foi recuperado
61
Pseudo-Feedback
Usa feedback de relevância sem uma
entrada explícita do usuário
Apenas assume que os top m documentos
recuperados são relevantes, e então
reformulam a consulta

É um método de feedback positivo
Melhorou o desempenho de RI no corpus do
TREC
62
Arquitetura de Pseudo-Feedback
Corpus de
Documentos
Consulta
inicial
Consulta
Reformulad
a
Rankings
Sistema
RI
Reformulação
da consulta
Pseudo
Feedback
1. Doc1 
2. Doc2 
3. Doc3 
.
.
Documentos
Ordenados
Documentos
reordenados
1. Doc1
2. Doc2
3. Doc3
.
.
1. Doc2
2. Doc4
3. Doc5
.
.
Próxima aula
Construção de bases de índices
Definição das equipes e dos projetos
64