Recuperação de Informação Eduardo Amaral - efas Frederico Fernandes - fbf2 Juliano Rabelo - jcbr Flávia Barros - fab

Recuperação de Informação

Eduardo Amaral - efasFrederico Fernandes - fbf2

Juliano Rabelo - jcbrFlávia Barros - fab

RoteiroIntroduçãoAquisiçãoPré-ProcessamentoIndexaçãoRecuperaçãoOrdenaçãoAvaliação e ValidaçãoCategorização

“Morrendo ignorante num mar de informações”

- Dificuldade de localizar documentos relevantes !!

Como funciona?

Web Pages 1870 found.

Aquisição Representação Indexação Recuperação Ordenação Avaliaçãoe Validação

Usuário

Necessidade deInformação

Casamento

Documento

s

indexaçãoConsultaCaracterização

formulação

Motivação

Itrodução- Motivação- Definição- Histórico- Arquitetura

Recuperação de Informação: Definição

Área de pesquisa e desenvolvimento que investiga métodos e técnicas para a representação, a organização, o armazenamento, a busca e a recuperação de itens de informação

Objetivo principal: facilitar o acesso a documentos (itens de informação) relevantes à necessidade de informação do usuário

Aquisição Representação Indexação Recuperação Ordenação Avaliaçãoe Validação

Introdução- Motivação- Definição- Histórico- Arquitetura

1ª Fase: Décadas de 50 e 60 (cartões perfurados) Indexação manual - documentos descritos por termos do tesaurus. Sistemas DIALOG e MEDLARS (60’s) Início da indexação automática: título e abstract Muita Teoria...

2ª Fase: Décadas de 70 e 80 Noções de estatística e probabilidade estabelecidas

SMART: 1º sistema de RI automático para o conteúdo usando Modelo de Espaço Vetorial (Salton 71)

Aumento do poder computacional 3ª Fase: WEB

Explosão de Serviços + agentes (90’s) Internet (www): gigabytes de dados não estruturados TREC (Text REtrieval Conference)

Aquisição Representação Indexação Recuperação Ordenação

Histórico

Avaliaçãoe Validação


Sistemas de RI - Arquitetura

Consulta

RespostaBase deÍndices

Engenho de Busca

Usuário

WebWeb

Spider

Indexador

Representação dos Docs

Servidor de Consultas

AquisiçãoPré-

ProcessadorDocs

Recuperador

Ordenador

21

34

Motor deIndexação

Browser

Aquisição Representação Indexação Recuperação Ordenação



Base de Índices

Usuário

Servidor de Consultas

Recuperador

OrdenadorBrowser

desonesto -> doc1 peso 1;

socrates -> doc1 peso 1; doc 3 peso 2futebol -> doc3 peso 3; doc 2 peso 5

honesto -> doc1 peso 2; doc 3 peso 1

Servidor de consultas

2

resultados1 - doc12 - doc3

Resposta4 honesto 2

socrates 1

doc1honesto 1socrates 1

doc3

3

Relevancia (Consulta, doc3) = 2 Relevancia (Consulta, doc1) = 3

Consulta 1 (socrates AND honesto)

Base deÍndicesIndexado

rMotor deIndexação

Pré-Processador

Motor de Indexação

Operações de Texto Representação

desonesto / soubesse /vantagem / honesto /seria / honesto /menos/desonestidade/socrates

Doc : www.filosofia.com honesto 2desonesto 1soubesse 1vantagem 1seria 1menos 1desonestidade 1socrates 1

Doc : www.filosofia.com

Centróide

Doc: www.filosofia.comPeso : 2

Word : honestoDoc: www.filosofia.comPeso : 1

Word : desonesto

Doc: www.filosofia.comPeso : 1

Word : socrates...

Se o desonesto soubesse a vantagem de ser honesto, ele seria honesto ao menos por desonestidade.” Sócrates

Doc originalDoc : www.filosofia.com

Representação Invertida

AquisiçãoUso de crawlers (spiders)

Programas que navegam pela web e fazem download das páginas para um servidor

Conjunto inicial de links Busca (largura ou profundidade)

Crawler do Google Roda em várias máquinas em paralelo Indexou 26 Milhões de páginas em 8 dias

AquisiçãoPré-Processamento Indexação Recuperação OrdenaçãoIntrodução Avaliação

e Validação

Pré-ProcessamentoObjetivo Criar uma representação computacional do

documentoFases Operações sobre o texto Criação da representação

Aquisição

Pré-Processamento- Fases- Operações sobre o texto- Representação do documento Indexação Recuperação OrdenaçãoIntrodução

Se o desonesto soubesse a vantagem de ser honesto, ele seria honesto ao menos por desonestidade.”Sócrates

Doc original

desonesto / soubesse /vantagem / honesto /seria / honesto /menos/desonestidade/socrates

honesto 2desonesto 1soubesse 1vantagem 1seria 1menos 1desonestidade 1socrates 1

Operações de Texto RepresentaçãoDoc : www.filosofia.com

Doc : www.filosofia.comDoc : www.filosofia.com


Operações sobre o textoAnálise léxica Converter uma cadeia de caracteres em

uma cadeia de palavras/tokens.Eliminação de stopwords Palavras consideradas irrelevantes. Ex :

artigos, pronomes,alguns verbos, “WWW”.

Aquisição

Pré-Processamento- Fases- Operações sobre o texto- Representação do documento Indexação Recuperação OrdenaçãoIntrodução Avaliação

e Validação

Operações sobre o textoStemming Redução de uma palavra ao seu radical

Geralmente apenas redução de sufixos. Ex: Algoritmo de Porter.

Permite casamento entre variações de uma mesma palavra

engineer engineer engineer

engineering engineered engineer

Term Stem

Aquisição


Regras de redução:ed -> 0ing -> 0


Representação do Documento

Texto Completo Difícil (caro) de manipular computacionalmente

Dado um documento, identificar os conceitos que melhor descrevem o seu conteúdoRepresentar como um Centróide Conjunto de termos com pesos associados ou não Perda da semântica

“Se o desonesto soubesse a vantagemde ser honesto, ele seria honestoao menos por desonestidade.”

Sócrates

honesto 2desonesto 1soubesse 1vantagem 1seria 1menos 1desonestidade 1socrates 1

Centróide

Aquisição


e Validação


Centróide Pesos das Palavras como indicação de

relevância: Freqüência de ocorrência no documento Term Frequency x Inverse Document

Frequency(TFIDF)

TF-IDF também considera palavras com baixa ocorrência na base de documentos como melhores discriminantes

)(log)()(

DFD

TFTFIDFTF(w): freqüência da palavra w no doc.DF(w): freqüência de w em DD = total de documentos

Aquisição


e Validação


Centróide Limitar tamanho do centróide em 50

deixando apenas palavras com maior peso Estudos mostram que isso não diminui

muito o seu poder de representação

Aquisição


e Validação


Enriquecendo a representação Usar formatação do texto como

indicação da importância das palavras (título, início, negrito,...)

Adicionar informação sobre a localização da palavra no documento

Aquisição


Representação de documento do Google

word : z - hit hit hit hitword : y - hit hit hit ...word : w - hit

Doc :xxx1bit capitalization; 3bit font size; 12 bit positionhit:


IndexaçãoOpção imediata: texto plano Textos pequenos ou muito voláteis

Objetivo: agilizar buscaPara bases maiores: estrutura de índices Índices invertidos Vetores e árvores de sufixos Arquivos de assinatura

Aquisição Pré-ProcessamentoIndexação

Recuperação OrdenaçãoIntrodução Avaliaçãoe Validação

Índices Invertidos: EstruturaComposição: vocabulário e ocorrências

lettersmademanytextwords

Vocabulário60502811, 1933, 40

Ocorrências

This is a text. A text has many words. Words are made from letters.

1 6 9 11 17 19 24 28 33 40 46 50 55 60



Índices Invertidos: EstruturaEspaço requerido Pouco para vocabulário Grande parte para ocorrências

Técnicas para redução de espaço Stemming (vocabulário) Endereçamento de blocos (ocorrências)

Poucos ponteiros, ponteiros menores e menos ocorrências

Google: Endereçamento “hierárquico” de blocos



Índices Invertidos: Estrutura Índice Base

Pequena(1Mb)

BaseMédia(200 Mb)

Base Grande(2 Gb)

End. dePalavras

45% * 73%** 36% 64% 35% 63%

End. deDocumentos

19% 26% 18% 32% 26% 47%

End. 64KBlocos

27% 41% 18% 32% 5% 9%

End. 256Blocos

18% 25% 1.7% 2.4% 0.5% 0.7%

* - com StopList ** - sem StopListAquisição Pré-Processamento

IndexaçãoRecuperação OrdenaçãoIntrodução Avaliação

e Validação

Índices Invertidos: Construção

Baixo custo: O (número de caracteres)Palavras inseridas num trie

letters: 60

many: 28

made: 50

text: 11, 19words: 33, 40

lmt

w

ad

n




Trie: muito espaço requerido Para bases grandes:

Índices parciais persistidos Merge dos índices

...




Ao final do processo: Um arquivo de ocorrências Outro do vocabulário com ponteiro para

ocorrências Pode ser mantido na memória



Outras Estruturas de ÍndicesArquivos de assinatura Baseados em hashing Pouco espaço requerido (10 a 20% do

original) Busca seqüencial

aceitável para bases pequenasÁrvores e vetores de sufixos...



RecuperaçãoObtenção dos documentos que satisfazem uma consulta (query)Índices Invertidos Custos de busca e armazenamento

sublinear O (n0.85)

Aquisição Pré-Processamento IndexaçãoRecuperação

OrdenaçãoIntrodução Avaliaçãoe Validação

RecuperaçãoProcurar termos da Consulta no vocabulárioTabelas hash, tries, ... O(tamanho da palavra)

Lista em ordem alfabética O(log (tamanho do texto)) Mais barato em espaço



RecuperaçãoConsultas simples Lista de ocorrências da palavra Recupera documentos onde a palavra ocorre

pelo menos uma vez Consultas compostas (booleanas) Listas de cada termo Recupera documentos onde cada palavra da

Consulta ocorre pelo menos uma vez Merge de listas Combina as listas de documentos recuperados

de acordo com o operador booleano da consulta



OrdenaçãoOrdenar os documentos de acordo com a relevância em relação à ConsultaRelevância: difícil de medir Mede-se a similaridade entre cada

documento e a consultaModelo “Espaço Vetorial” Consulta e documento são representados

como um vetor Similaridade é proporcional ao co-seno do

ângulo formado Tende a retornar documentos pequenos

Aquisição Pré-Processamento Indexação RecuperaçãoOrdenação

Introdução Avaliaçãoe Validação

OrdenaçãoGoogle Proximidade das palavras da Consulta no

documento Tamanho da fonte, texto de links, ... PageRank

Aquisição Pré-Processamento Indexação RecuperaçãoOrdenação

Introdução Avaliaçãoe Validação

AvaliaçãoCobertura: total de documentos relevantes retornados sobre o número total dos relevantes existentesPrecisão: documentos relevantes retornados sobre o número total de retornados

Todos os Documentos

Documentos Relevantes

Documentos Retornados

Relevantes Retornados

Aquisição Pré-Processamento Indexação Recuperação OrdenaçãoIntrodução


ValidaçãoTeste do sistema num corpus conhecido e etiquetado manualmente Sabe-se a relevância de um documento em

relação a uma ConsultaTREC, Reuters, ...

Aquisição Pré-Processamento Indexação Recuperação OrdenaçãoIntrodução


Consultas (Q) e Documentos (D) representados como vetores Similaridade: cosseno do ângulo formado entre Q e D Ex: Dados uma consulta q e um documento d

Sim = = = 0.29

Ordenação: encontrar quais os documentos são mais similares a consulta

Olimpíadas

Brasil

Sidney

d0.4

0.50.3

q

d • q|d| · |q|

0.5 · 0.4 + 0.3 · 0.3 + 0.2 · 0.3( 0.25 + 0.09 + 0.04 )½ · ( 0.16 + 0.09 + 0.09 )½

Brasil Olimpíadas SidneyConsulta q :

Documento d :Brasil em Sidney 2000 O Brasil não foi bem no quadra das medalhas da Olimpíada de Sidney 2000 ...

Brasil 0.4Olimpíadas 0.3Sidney 0.3

Brasil 0.5Olimpíadas 0.3Sidney 0.2

Representação de q

Representação de d

Espaço Vetorial

Indexação Ordenação Vantagem Desvantagem

Booleano termo1-url1,url2 Simplicidade Não ofereceordenação

Booleano Estendido termo1-(url1,peso),(url2,peso)

Distância Euclidiana Tem ordenação Ordenação não muitoboa

Vector Space termo1-(url1,peso),(url2,peso)

CossenoPropriedades

interessantes. Modelomais utilizado e

aceito na comunidade

Indexação comSemântica Lantente(LSI)

termo1-(url1,peso),(url2,peso)

SVD (Singular ValueDecomposition)

Relaciona termos quenão são co-citados

Elevado custo demanutençãoe

computacional

Comparação

BibliografiaBaeza-Yates & Ribeiro-Neto - Modern Information RetrielvalSparck Jones & Petter Willett - Reading in Information RetrievalBrin, Sergey & Page, Lawrence - Anatomy of a large Scale Search EngineRay Denenberg - Structuring and indexing the WebHeydon and Najork - Mercator : A Scalable, Extensible Web Crawler

Documents

Recuperação de Informação Eduardo Amaral - efas Frederico Fernandes - fbf2 Juliano Rabelo - jcbr Flávia Barros - fab