Frederico Brito Fernandes - [email protected]
Agentes Inteligentes - Cin UFPE
Novembro 2000
 Sistemas tradicionais de Recuperação de Informação (RI) usam
termos para indexação e recuperação dos dados (há 20 anos !!!)
 Termos são palavras ou conjuntos de palavras de um documento
 Indexação  armazenamento da informação nas bases de índice
docs.
Arquivos Invertidos
termo1 - doc1, doc3,...
termo2 - doc41, ...
... - ...
BI
BI
 Recuperação
Necessidade do Usuário
(palavras-chave, profile, etc)
+
Informação
BI
BI
Armazenada
=
docs.
relevantes
2
 Stop List  lista de palavras  Stemming e n-grams  redução
de termos. Ex: CONNECT
comuns, irrelevantes
Artigos: a, os, ...
Pronomes: meu, aquele, ...
Advérbios: muito, bem, ...
...
CONNECTED
CONNECTING
CONNECTION
CONNECTIONS
 Term Frequency-Inverse Document Frequency (TFIDF):
 atribuição de peso aos termos
 D 

TFIDF( )  TF ( )  log

DF
(

)


TF(w): freqüência da palavra w no doc.
DF(w): freqüência de w em D
D = total de documentos
3
 Precisão
 Documentos relevantes retornados dividido pelo
número total de retornados
 Cobertura
 Total de documentos relevantes retornados dividido
pelo número total dos relevantes
Todos os Documentos
Documentos Relevantes
Documentos Retornados
Relevantes Retornados
by Flávia ([email protected])
4
Outros Conceitos:
 Robô (ou spider)  programas
que percorrem links na web,
geralmente com objetivo de indexá-la
 Corpus  conjunto de documentos etiquetados
 Filtragem  à partir do profile(gosto) do usuário, documentos
interessantes são selecionados
 Routing  faz a mesma coisa que filtragem, a medida que os
documentos vão sendo adicionados ao Corpus
 Arquivo invertido  termos (índices) mapeando os documentos
em que aparecem
5
 Base de Índice  banco de dados de um sistema de índices
 Similaridade  o grau de quanto 2 documentos são semelhantes
 Co-Citação (co-citation)  dois documentos são citados por um
mesmo documento
 Thesaurus  identifica o relacionamento entre termos
 Trec (Text Retrieval Conference)  conferência de IR para
demonstração de experimentos com grandes banco de dados,
banco de dados multimídia, etc
6
Engenhos de Busca
Ex: Radix, Altavista
Usuário
Resultado
w
e
b
Consulta
palavras-chave
Documentos
+
URLs
Busca
Interface
Casamento de
Termos
Índices + URLs
BI
BI
Robôs
Stop List
7
 Representação Física de Documentos Textuais Digitais
 Texto completo
 Difícil de manipular
 Centróide - conjunto de termos com pesos associados ou não
 Perda de semântica
“Se o desonesto soubesse a
vantagem de ser honesto,
ele seria honesto ao menos
por desonestidade.”
Sócrates
Centróide
honesto
desonesto
soubesse
vantagem
seria
menos
desonestidade
2
1
1
1
1
1
1
8
Modelos
booleano
vetor
probabilista
 Motivação: que documentos são relevantes a uma consulta do
usuário ? Ou qual o grau de semelhança entre dois documentos ?
 Surgiu a necessidade de criar modelos para interpretar e manipular documentos
 Representação Lógica (Modelos) de Documentos Textuais
Mostraremos alguns deles !!
Digitais
Framework para manipular e interpretar documentos
 Várias abordagens: teoria dos conjuntos, álgebra linear, probabilidade, etc
 Ex: Vector Space
doc1
doc2
9
Modelos
booleano
vetor
probabilista
 Definição Formal de modelo em IR:
 É definido pela quádrupla [ D, Q, ƒ, R(qi,dj) ]
D - visão lógica dos documentos
Q - visão lógica da query do usuário
ƒ - um framework para modelar essas representações e seus
relacionamentos
R(qi,dj) - uma função que associa um número real com uma
query qi  Q e um documento dj  D
Obs.: Para simplificação, considere Q = D, e R(qi,dj) = Sim
10
Modelos
 Modelos Clássicos de IR:
 Booleano  documentos são representados como um conjunto de
booleano
vetor
probabilista
termos que aparecem no documento
 Vector Space  como um vetor em um espaço t-dimensional
 Probabilista  baseado na teoria da probabilidade
 Derivações:
 Booleano  Fuzzy, Booleano Estendido
 Vector Space  Vetor Generalizado, Indexação com Semântica
Latente, Redes Neurais
 Probabilista  Rede de Inferência, Rede de Crença
 Alternativo:
 Baseado em Links  algoritmos Companion e Cocitation [1]
[1] HENZINGER, M. R. & DEAN, J. Finding Related Pages in World Wide Web
11
Booleano
Modelos
booleano
vetor
probabilista
 D: conjunto de termos do documento, com pesos binários
 f: teoria dos conjuntos e álgebra booleana
 Sim: apenas retorna 1 (se o termo esta presente no doc.) ou 0
 Ex.: sejam os k termos
k1
k2
k1  k2  k3
Documentos relevantes
k3
 Vantagem:
 Oferece um framework simples e elegante
 Desvantagem:
 Determinístico: um documento é ou não relevante
 Problemas com Precisão e Cobertura: Resultados (muito)
grandes ou pequenos e sem uma escala de relevância
12
Modelos
Vector Space
booleano
vetor
probabilista
 D: um vetor
 f : espaço vetorial t-dimensional e operações de álgebra linear sobre
vetores
 As dimensões do espaço vetorial são os termos do documento
 Os termos recebem pesos de relevância no documento (negrito, título, etc)
 Esses pesos são usados como índices do vetor
Sidney
 Modelo mais utilizado em IR
Brasil
Olimpíadas
Sidney
di
0.3
0.5
0.2
Brasil
Olimpíadas
Sidney
dj
0.2
0.4
0.4
dj
0.2
0.3
di
0.5
Olimpíadas
di = 0.3 Brasil + 0.5 Olimpiadas + 0.2 Sidney
dj = 0.2 Brasil + 0.4 Olimpiadas + 0.4 Sidney
Brasil
13
Vector Space
Modelos
booleano
vetor
probabilista
 Sim: produto interno / produto das normas
Sim = d • d =
= 0.28
0.3
·
0.2
+
0.5
·
0.4
+
0.2
·
0.4
i
j
( 0.09 + 0.25 + 0.04 )½ · ( 0.04 + 0.16 + 0.16 )½
|di| · |dj|
 Vantagem:
 Oferece um framework simples e elegante
 Medida de similaridade: os documentos são retornados em
ordem decrescente do seu grau de semelhança
 Em geral, seu desempenho (precisão e cobertura) supera
todos os outros modelos
14
Probabilista
Modelos
booleano
vetor
probabilista
 Baseado no principio probabilístico
“Dada uma query q e um documento dj em uma coleção, este modelo tenta
estimar a probabilidade de que o usuário ache o documento dj interessante (i.e.,
relevante)
 Idéia fundamental
 Dada uma query, existe um conjunto de documentos relevantes e outro não
 Esse conjunto de documentos relevantes tem certas propriedades
 Definimos probabilidades associadas a essas propriedades
 O usuário interage para definir que documentos foram ou não relevantes
 As probabilidades são então melhoradas
 Vantagens e Desvantagens:
 Medida de similaridade: os documentos são retornados em ordem
decrescente do seu grau de semelhança
 Necessidade de separar os documentos relevantes a priori
15
Booleano Estendido
Modelos
booleano
vetor
probabilista
 Combinação do modelo booleano com o vector space
 D: um ponto no espaço
 f : espaço t-dimensional e distância entre pontos
 Sim : distância de dj  D para o ponto 1 (no caso de AND)
 Estende o modelo booleano com pesos entre [0,1]
idfx
wx,j = fx,j · max idf
i
i
16
Booleano Estendido
Modelos
booleano
vetor
probabilista
 Relaxa álgebra booleana e interpreta operações booleanas em
termos de distâncias algébricas (tome wx,j como x)
and = 1 or =
Sim = 1 -
(1-x1)p + (1-x2)p + ... + (1-xm)p
m
1/p
Distância para
o ponto (1,1,...,1)
(x1)p + (x2)p + ... + (xm)p
m
1/p
Distância para
o ponto (0,0,...,0)
(1-x1)p + (x2)p + ... + (1-xm)p
m
1/p
17
Latent Semantic Indexing
Modelos
booleano
vetor
probabilista
 Busca documentos relevantes através do conceito, e não
mais apenas por termos:
termo
query
doc1
doc2
 D: uma coluna da matriz termo-documento (
abaixo)
M
 f : operações com matrizes (ex. transposta t)
 Sim: obtido com algumas transformações
Termo1
Termo2
...
Termo t
Doc1
w11
w21
...
wt1
Doc2
w12
w22
...
wt2
Doc3
w13
w23
...
wt3
...
...
...
...
...
Doc N
w1n
w2n
w
wtn
M : matriz termo-documento, com pesos nas linhas e documentos nas colunas
18
Latent Semantic Indexing
Modelos
booleano
vetor
probabilista
 Decompondo a matriz M em três componentes :
 M = K S Dt , onde K= M Mt e Dt = Mt M
 Reduzindo o espaço para dimensionalidade s :
 Ms = Ks Ss Dts
 O relacionamento entre os documentos é obtido com :
 Mts Ms = ( Ds Ss ) ( Ds Ss )t
Sim
Doc1
Doc2
...
DocN
Doc1
w11 Matriz que nos fornece o fator de
w21 similaridade entre Doc1 e todos os
...
outros documentos
wN1
19
Modelos
Rede Neural
booleano
vetor
probabilista
 D: um nó na rede
 f : rede neural com três camadas
Termos de
uma query
ka
kb
kc
Termos
de D
D
k1
d1
ka
kb
kc
dj
Dj+1
Propagação 1
Propagação 2
t
t
 wi,j
 wi,q
i=1
t
i=1
t
 w2i,j )½
( i=1
 w2i,q )½
( i=1
 Sim:
t

t
 wi,q wi,j =
i=1
i=1
t
(
i=1
w2
wi,q wi,j
i,q
)½
t
( w2i,j )
i=1
½
kt
dN
Igual ao vector space
na primeira passagem
20
Modelos
Baseado em Links
booleano
vetor
probabilista
 D: como um nó
 f : estrutura de links, e operações como pai(d) e filho(d)
 Princípio Básico:
di
dj
“Se existe um link de di para dj, então o autor recomenda
dj e o link oferece um documento relacionado”
 Gráfico da Vizinhança:
- a partir de um documento d-
fb
bf
bf
f
b b
b
d
bf
fb
f
- Gráfico de links gerado a partir do nó d, com a ferramenta Connectivity Server -
21
Modelos
Baseado em Links
booleano
vetor
probabilista
 Algoritmo Companion
 Construção do Gráfico de Vizinhança
 Eliminação de Duplicatas  95% de links em comum e mais de 10 links
 Atribuição de pesos aos links:
A
1/k
1/j
1/k
1/j
B
 Calculo do Authority e Hub:
Dados os hosts:
- A com 2 nós (k=2)
- B com 1 nó (j=2)
- C com 2 nós
C
A[n] =  H[n]
H[n] =  A[n]
 Sim = nós com maiores Authority
22
Baseado em Links
Modelos
booleano
vetor
probabilista
 Algoritmo Cocitation
 Dois nós são co-citados se tem o mesmo pai
 Grau de Co-Citação  numero de pais em comum
A
B
C
D
E
u
F
G
H
1
3
2
1
 Sim = nós com maiores graus de co-citação (F, G, E, H)
23
Modelos
booleano
vetor
probabilista
 Conclusões
 Grande diversidade de modelos
 Modelos híbridos (booleano probabilista, booleano estendido)
 Vector Space: mais utilizado e divulgado na literatura
 Em termos de precisão e cobertura,
 Alguns modelos se mostraram mais eficientes que o
Vector Space em domínios especializados
 Bases grandes e heterogêneas: não se tem registro de
nenhum modelo que supere o Vector Space
24
Lista de Croft versus Características de Agentes
- Bruce Croft apresentou na revista D-Lib Magazine em Nov. de 95 [1] a lista dos 10 maiores desafios em RI -
Adaptação
10.
9.
8.
7.
6.
5.
4.
3.
2.
1.
Relevância do Feedback
Extração de Informação
Recuperação Multimídia
Recuperação Efetiva
Filtering e Routing
Interface e Navegação
Expansão de termos
Eficiência e Flexibilidade
RI Distribuída
Soluções Integradas






[1] http://www.dlib.org/dlib/november95/11croft.html
Cooperação









Autonomia




25
 Agentes Baseados em Recuperação de Informação (ABRI)
EachMovie
Firefly
GroupLens
Morse
MovieCritic
Phoaks
RARE/Tunes
ReferralWeb
SiteSeer
Yenta
CARROT
InfoSleuth
Retsina
SAIRE
UMDL
Syskill and Webert
Interface
Adaptativa
Colaborativo
ABRI
Interface Simples
para Múltiplas Fontes
NetBot
Jango
ShopBot
Pró-Ativo
RemembranceAgent
Adaptação para
Usuários e Conteúdo
Bases (grandes)
Distribuídas
Compreensão
de Conteúdo
Push
Especialista
em Conteúdo
URLAgents
KnowBot
ShopBot
Backweb
Marimba
Pointcast
SIFT
TopicAGENTs
Fishwrap
MyYahoo
MetaBusca
All-in-one
Fastfind
Metacrawler
Metasearch
Profusion
Savvysearch
WebCompass
26
KnowBots
 Provê uma linguagem de consulta para acessar várias fontes
 ShopBot  e-commerce
 MetaBusca  engenhos de busca
 Ex:
Metacrawler : MetaBusca
 Única interface
 Consulta vários engenhos de busca
 Combina os resultados
NetBot Jango : ShopBot
 Única interface
 Consulta vários sites a procura de
determinados produtos: CDs, charutos
 Mostra uma lista de produto + preço + site
27
Bases (Grandes) Distribuídas
 Corpus dinâmico, medido em MB (ou GB)
 Documentos heterogêneos: tamanhos, formatos, linguagens
 Arquitetura:
BI
BI
}-{
}-{
BI
}-{
Agentes
}-{
BI
Múltiplas
Fontes de Informação
}-{
}-{
Múltiplos
Usuários
28
Bases (Grandes) Distribuídas
 Sobre a arquitetura:
 Cada usuário é representado (pelo menos) por um agente, que
tem (ou obtém) o perfil ou necessidade do usuário. Problema do
Profile do Usuário
 As consultas podem ser modificadas (ex. expandida) e enviadas
para as bases. Problema do Processamento de Consultas
 As bases podem ter diferentes modelos de documentos e
consultas. Problema da Heterogeneidade
 Documentos de diferentes bases precisam ser comparados e
ranqueados. Problema da Fusão de Dados
29
Bases (Grandes) Distribuídas
Ex:
SAIRE
UMDL
 Scalable Agent-based Information
Retrieval Engine
 Provê acesso aos dados da NASA
EOSDIS
 Suporte para leigos e experts
 Três variedades de agentes:
Interface, Coordenador e Especialista
em Domínios
 Comunicação entre agentes
 University of Michigan Digital
Library
 Três tipos de agentes:
 Interface - consultas e profile
 Mediador - planejamento
 Buscador - engenhos de busca
 O usuário pode navegar através de
um applet java, sob uma ontologia de
informação desenvolvida por eles
http://saire.ivv.nasa.gov/saire.html
http://www.si.umich.edu/UMDL/
30
Filtragem Colaborativa
 Um sistema de filtragem colaborativo faz recomendações a um
usuário de acordo com o grupo de usuários similares a ele
 Recomenda:
 Pessoas - Yenta, ReferralWeb
 Produtos - Firefly, Similarities Engine, Tunes (music), EachMovie,
Morse, RARE, MovieCritic (movies & videos)
 Leituras - Wisewire, Firefly, Fab, Phoaks
Baseado em Conteúdo vs. Recomendação Colaborativa
Recomendação
Colaborativa
similar a
Recomendação
Baseada em
Conteúdo
gosta
Documento
gosta
similar a
Documento
recomendado
31
Filtragem Colaborativa
Ex:
FAB
Firefly
 recomenda sites usando técnicas de
RI adaptativa
 Agente: coletor, selecionador e
enviador
 Feedback do usuário: adaptar
profile e dar(tirar) crédito aos agentes
 Um algoritmo genético é usado
para desenvolver a população de
agentes coletores
 Aplicado a música, filmes, sites,
livros, etc
 Usa vários conjuntos de vizinhos para
aumentar a precisão
 Recomenda usuários que não gostam
de um site, ou um site que um dado
usuário não gosta
 Comprada pela Microsoft, Abril 98
Http://fab.stanford.edu
32
Interface Adaptativa
Ex:
SysKill & Webert
 controla o browser adicionando
painéis
 Facilita ao usuário avaliar um site
como bom ou ruim a respeito de uma
das várias classes definidas pelos
usuários
 Pode estimar quais sites o usuário
poderia gostar
33
Pró-Ativo
Ex:
Remembrance Agent
 Indexa arquivos pessoais e e-mails
 Sugere arquivos relevantes à tarefa
que o usuário está executando
 Opera continuamente
Letizia
 Agente que navega semelhante ao usuário
 Usuários geralmente navegam em profundidade,
enquanto Letizia navega em largura
 Usa uma variedade de heurísticas para identificar
sites interessantes
 Quando um site interessante é encontrado, é
mostrado em uma janela diferente
34
Pró-Ativo
PUSH
Ex:
TopicAGENTs
 Provê uma visão do agente das tarefas de recuperação de
informação para o usuário
 Tarefas: filtragem, categorização, routing
 Variedade de serviços de envio:
 Sites
 Entrada no banco de dados
 E-mail
 Fax
35
Conclusões
 Vantagens de Agentes baseados em Recuperação de Informação:
 Manipulam dinamicamente bases heterogêneas e distribuídas
 Melhoram a performance via agentes especializados
 Podem adaptar-se aos interesses e preferências dos usuários
 Tecnologias já disponíveis:
 Linguagens e protocolos de comunicação entre agentes. Ex: KQML
 Métodos e algoritmos de Machine Learning
 etc.
 Futuro:
 Melhorar o processamento e representação de metadados
 Habilidade para manipular mídias: imagens, sons, vídeos, etc
 Fusão inteligente de bases heterogêneas
36
 Em desenvolvimento no CIn-UFPE
 Ajuda o usuário a encontrar documentos semelhantes ao que ele está
consultando/editando no momento
 Plataformas: IE, Netscape e Microsof Word
 Compara o conteúdo de dois documentos
 Representa um aumento na precisão dos documentos recuperados
 Extremamente útil na Intranet de uma empresa:
 Padronização dos documentos
 Business da empresa
 Facilidade para o funcionário encontrar documentos similares ao
que está editando.
 Economiza tempo dele mesmo e de outros
37
Arquitetura
Active Search
Internet
Explorer
Interface
Algoritmo
de
Lista URLs
Similaridade
similares
Netscape
Centróides
Buscados
Documento
Atual
MS
Word
StopList
Centróide
Doc.Atual
Algoritmo
de
Busca
-------- ---
Web
...
}-{
query
-------- ---
Preparação do
Documento
Doc
Ps
Html
Servidor de
Consulta
Ontologia
Intranet
Google
Radix
Internet
38
Protótipo
39
Próximos Passos...
 Estudar e implementar mais modelos de representação de
documentos (medidas de similaridade)
 Realizar medições da qualidade das respostas para os
diferentes modelos
 Precisão, cobertura, f-measure, etc
 Estudar e implementar técnicas de filtragem e clustering
40
 Recuperação de Informação
 BAEZA-YATES, Ricado, RIBEIRO-NETO, Berthier. Modern
Information Retrieval
 JONES, Karen S., WILLET, Peter. Readings in Information
Retrieval
 http://www.cs.kun.nl/is/edu/ir1/dir.htm
 http://www.ils.unc.edu/viles/inls172-s99/172-Syll-S99.html
 http://www.pitt.edu/~korfhage/glossary.html
 Agentes baseados em Recuperação de Informação
 http://www.cs.umbc.edu/abir/
41