Agentes de Busca na Internet
Fred Freitas
Mêuser Valenca
Sumário
 Agentes de Busca
 Prevenindo-se contra
robôs
 Robôs com IA :
 Histórico de Robôs
assistentes
 Robôs não-inteligentes
 .Internet Softbot,
-WebCrawler
.Letizia,
-Lycos
.Info Agent,
 Arquitetura : BRight!
.Internet Consultant
 Diretrizes ao escrever
 IA na Web : SHOE
um robô
 Estratégia de Busca
Agentes de Busca na Web
Necessidade de Agentes na Web
 O volume de Informações é imenso.
 O tipo e a qualidade da informação varia
largamente.
 Informações altamente dinâmicas.
 O usuário atravessa muitos links até
encontrar o que deseja.
 O surfe deixa muitos usuários perdidos.
Agentes de Busca na Web
 Conceito: são sistemas que utilizam Robôs
que atravessam o hyperespaço da WWW
em nome do usuário.
 Funcionalidade - Robô empregado.
 Buscas (indexação) - Booleana e Vetorial.
 Atributos - precision e recall.
Agentes de Busca na Web
Arquitetura
Agents
Agents
Search
Engine
Internet
Webspace
Query
Server
.
Database
Agentes de Busca na Web
Robôs na Web (não inteligentes)
 Worm - Oliver McBryan (03/94)
- Primeiro Spider largamente utilizado
- Indexa apenas título e cabeçalho.
 RBSE(Repository Based Engineering) - (02/94)
- Primeiro Spider a indexar por conteúdo
- Objetivo de capturar mais informações.
Agentes de Busca na Web
WebCrawler
 Projeto - Brian Pinkerton (U.Washington-Seattle)
 Apresentado - 04/94 c/ base de dados inicial 6000
servidores, respondendo 6000 perguntas/dia sendo
atualizado semanalmente.
 Funções - Indexação de Documentos e Navegação
em tempo real.
Agentes de Busca na Web
WebCrawler-Características
 Utiliza sistema de indexação detalhado do texto.
 Não sobrecarrega a rede, a carga ocorre somente
no servidor.
 Usa uma estratégia de busca em largura.
 Seu Robô cumpre os padrões - Consenso.
Agentes de Busca na Web
WebCrawler-Algorítmo
1. Inicia com conjunto conhecido de documentos.
2. Descobre novos documentos.
3. Marca os documentos que são retidos
(adicionados para a base de dados de índices).
4. Descobre seus links.
5. Indexa o conteúdo do documento(título,cabeçalho,
linhas de texto, data de modificação, tamanho do
arquivo)
Agentes de Busca na Web
WebCrawler-Mecanismo de Busca
 Modo Indexação- Tantos servidores quanto
possível.
1.Novo servidor encontrado - lista de visita
imediata.
2.Um documento de cada novo servidor é retido e
indexado antes de visitar algum outro.
3.Quando não há novos servidores, procura nos
que já tem até encontrar 1.
Agentes de Busca na Web
WebCrawler-Mecanismo de Busca
 Modo de Busca
1.Consulta índice-similaridade
2.Desta lista os mais relevantes são escolhidos e os links
inexplorados são seguidos.
3.Novos documentos recuperados/indexados outra
consulta.
4.Resultados são escolhidos por relevância e novos
documentos próximos ao topo da lista são candidatos a
próxima exploração.(fish search)
5.O processo continua até encontrar suficiente documentos
similares para satisfazer o usuário ou até um tempo limite.
Agentes de Busca na Web
WebCrawler’s
 AGENTES.
- Utiliza 15 agentes em paralelo.
- Cada novo documento é entregue a um agente que
recupera a URL.
- Um agente qualquer responde ao mecanismo de busca
com um objeto contendo conteúdo ou explanação porque
o documento não pode ser recuperado, ficando livre.
Agentes de Busca na Web
WebCrawler’s
 DATABASE.
- Atualizada após algumas 100 de documentos.
- Indexa por palavra(relevância)- palavras que aparecem
frequentemente no documento e infrequentemente no
domínio de referência são atribuídos maior peso.
- Cada objeto é armazenado numa árvore binária em
separado : documentos, servidores e links.
Agentes de Busca na Web
WebCrawler’s
 QUERY SERVER
- Usuário entra com uma palavra chave.
- Os títulos e URLs de documentos contendo algumas ou
todas as palavras são recuperadas do índice.
- É apresentada ao usuário lista ordenada por relevância.
- Relevância - é uma média ponderada do peso da palavra
no documento e seu peso na pergunta.
Agentes de Busca na Web
Lycos
 Projeto - Dr Michael Mauldin ( Cornegie Mellon-08/94)
 Lycos(06/95) - características: 5 M URLs, 1,2 M
Documentos, 3,9 M URLs a explorar, 1,8 B sumários.
 Busca em profundidade.
 Explora os espaços - HTTP, FTP e Gopher
 Ignora os espaços/ extensões - Wais, Telnet, Usenet etc. -
exe, gif, gz, tar, wav etc.
Agentes de Busca na Web
Lycos - Indexação
 OBJETIVO - reduzir armazenamento.
- Título, cabeçalho e Sub.
- 100 mais importantes palavras(TF*IDF).
- Primeiras 20 linhas.
- Tamanho em bytes e Número de palavras.
Agentes de Busca na Web
Lycos - Seleção de palavras
 TF (frequência) = número de ocorrências de um termo
particular na coleção de N documentos.
 DF (frequência no documento) = é o número de
documentos no qual o termo particular ocorre.
 DF (inverso da frequência no documento) = medir quão
bom um termo particular é para discriminar um
documento.
Agentes de Busca na Web
Lycos - Algorítmo
 Quando 1 URL é recuperada, procura por
outros links e coloca numa fila interna
 A escolha da próxima URL a explorar é
aleatória entre - HTTP, FTP e Gopher,
colocadas em fila por ordem de preferência.
 Preferência - Documentos populares (com
muitos links) e menores URLs (explorar a
raiz)
Arquitetura do BRight!
Brokers
Servidores
de Índices
Web
Escalabilidade
Servidores Web
Menor carga de trabalho para indexação
Robôs Indexadores
Escopos mais restritos
Canais de Transmissão
Menor tráfego redundante
Usuário
Escolha transparente de servidores de índices
Diretrizes ao escrever um robô
 QUESTIONAR : É necessário ? Posso arcar
com essa responsabilidade ?
 Não descer muitos níveis.
 IDENTIFICAR seu robô e a si próprio.
 Anunciá-lo antes de disponibilizá-lo.
 Avisar aos administradores se ele visitará
poucos servidores e também seu provedor.
 Testar localmente antes, extensivamente.
Diretrizes ao escrever um robô
 NÃO APROPRIAR-SE dos servidores :O
robô deve ir devagar e alternando vários
servidores.
 Processar apenas os dados que interessam :
tipos de arquivos, data dos arquivos.
 Não rodá-lo com freqüência, tentando
buscar novos links.
 Rodá-lo em horário oportuno.
Diretrizes ao escrever um robô
 Evitar armadilhas : círculos, formulários e
URLs sem trailing.
 Controlá-lo : Interatividade e um log-BD
público com estatísticas de sucesso, hosts
acessados recentes e tamanho de arquivos.
 Ética : respeitar o princípio de exclusão.
 Avisar aos administradores sobre links com
erros.
Prevenindo-se contra robôs
# /robots.txt
# mail webmaster<server> for critics
User-agent: webcrawler
Disallow:
User-agent: lycra
Disallow: \
User-agent: *
Disallow: \tmp
Disallow: \logs
<meta name=“robots” content=“noindex/nofollow”>
Dotando robôs de IA:Assistentes
 Metáfora: Na estrada da informação, o robô
é um táxi-cicerone.
 Comércio:domínios fechados, acessam BDs
conhecidos (informação estruturada).
 Notificadores, delegados pelo usuário, com
um modelo dele(às vezes com aprendizado).
 Normalmente proativo,tem algo de IA :PLN
planejamento, metas, função de avaliação.
Assistentes : Internet Softbot
 Perfil do usuário,proativo(sugestões).
 Acessa BDs conhecidos.
 Meta, auto-início (reativo), não-móvel.
 Interface gráfica expressiva:conjuncões,
disjuncões,negacão e quantificadores.
 Linguagem lógica interna e planejamento.
 Incipiente refinamento de planejamento.
 Futuro:PLN,aprendizado e multiagentes.
Assistentes : Letizia
 H.Lieberman-MIT-Macintosh Clisp.
 Imita o comportamento do usuário, baseado
em preferência, não em relevância.
 Segue o usuário e tenta antecipar o que é de
interesse, com heurísticas simples e metas.
 HP dinâmica e acessível, com sugestões.
 Aproveita o tempo inútil e é ético.
Assistentes : Letizia
 Behavior-BR - justificativas ! - IR/IF e OO.
Interesse:seguir um link ou revisitá-lo, ou
acessar muitas páginas sobre um assunto.
 Desinteresse: desprezar um link ou retornar.
 Persistência de interesse e “esquecimento”.
 Achados ao acaso: tenta descobrir interesses
não-óbvios.
Assistentes pessoais : Info Agent
Delegação
Usuário
Servicos Internos
Interface
Busca externa
 Genérico,extensível,filos.OO e orientado a usuário.
 Interface interage c/ usuário,dinamicamente modela-
-o e comunica-se com os outros agentes (KQML).
 Servicos internos:suporte(impressoras,traducão,etc).
 Agente de busca externa : Harvest E/OU outro.
Assistentes : Internet Consultant
 Agente Interface PLN c/
GeradorLN
PAU
Analisador
Metas
BC
MU
Rec.
Domínios
Instrument.
Gerador de
Planos
Broker de
Recursos
Executor
pragmática : interpreta e
modela o usuário e
extrai metas.
 Planejador : Gera e
executa planos para
atingir as metas.
 Informações:Busca as
fontes e recupera as
informações desejadas.
Assistentes : Internet Consultant
 M.Inaba - Honolulu - Macintosh Clisp e
MERA-CLOS. MERA : linguagem
diagramática,vinda de E-R, com hierarquias
semânticas e herança “a la “ Java.
 Pode atuar como tutor inteligente.
 Reusa mec.de busca : Lycos, WebCrawler ...
 Modelo do usuário:Iniciante, médio e expert,
reconhecido pela terminologia, ferramentas
usadas,tarefas,etc.Resposta p/ cada modelo.
IC : Classes de Comunicação
 Humano-agente : conjunto de classes de
Pessoas, classes de Agentes e relações (msgs).
Comunicação definida pela subclasse da
entidade ato locucionário (Q,O,T) e as relações
de comunicação (Query, Proposition, Speaker
e Listener).
 Agente-agente:rels. Receptor,Remetente e Obj.
 Agente-recurso : relações Usa e Consome.
Internet Consultant : Conclusões
 KB:vocábulos ingleses, padrões de questões
do usuário, informações sobre servidores e
operadores para planejamento do controle
dos browsers.
 Futuro:diálogos,comunicação em HTML,
variedade de tarefas, mobilidade,
aprendizado do modelo de usuário.
 Performance ?
Dotando a WWW de IA : SHOE
 Simple HTML Ontology Extensions - Sean
Luke - Universidade de Maryland - 96.
 Motivação : Difícil combinar info parcial...
HTML/HTTP preocuparam-se com
apresentação e navegação, não com busca
semântica(só léxica).Robôs c/inferência em
ambiente difícil, PLN ainda não resolve.
Onde está o relacionamento entre páginas ?
Dotando a WWW de IA : SHOE
 Achar a Home-Page do Sr. ou Sra. Cook
que trabalham na mesma empresa, no
projeto ARPA 123-4567.
 Se perguntar por Cook, milhares de
respostas... (Culinária :) ) e não consegue-se
achar a Home-Page do Sr. Cook desse
projeto :(
 O que fazer ??
Dotando a WWW de IA : SHOE
 Solucão:Não apenas palavras-chave, mas
conj. oficial de atributos/relações(ontologia)
 HTML:REL,REV,CLASS e META.
 Dobson/Burill-95:E/R,atributos s/semântica.
 SHOE:’é-um’,hierarquia de classes (mais
importante que relacionamentos) e
inferência(estrutura p/reflexividade,
fechamento transitivo e outras regras).
 Novo problema:veracidade das afirmações.
Definições em SHOE
 Ontologias específicas e gerais em HTML.
Ex: Person is-a thing.
 Entidades em docs/subdocs,rels. e atributos.
 Herança entre ontologias.
 Instanciamento entidade/ontologia.
 Robô Exposé (Evett-95) em Macintosh
Clisp, C e PARKA - Univ. Maryland.
Definindo ontologias em SHOE
<ONTOLOGY “our” VERSION=“1.0>
<ONTOLOGY-EXTENDS “organization” VERSION=“2.1”
PREFIX=“org” URL=“http://www.ont.org/orgont.html”
<ONTDEF CATEGORY=“Person” ISA=“org.Thing”>
<ONTDEF RELATION=“lastName”ARGS=“Person STRING”>
<ONTDEF RELATION=“firstName”ARGS=“Person STRING”>
<ONTDEF RELATION=“marriedTo”ARGS=“Person Person”>
<ONTDEF RELATION=“employee”
ARGS=“ org.Organization Person”>
</ONTOLOGY>
Instanciando em SHOE
<HEAD>
<META HTTP-EQUIV=“Instance-Key”
CONTENT=“http://www.cs.umd.edu/~george”>
<USE-ONTOLOGY “our” VERSION=“1.0” PREFIX=“our”
URL=“http://ont.org/our.html”>
<BODY>...
< CATEGORY=“our.Person” >
< RELATION=“our.firstName” TO=“George”>
< RELATION=“our.lastName” TO=“Cook”>
< RELATION=“our.marriedTo”
TO=“http://www.cs.umd.edu/~helena”>
< RELATION=“our.employee”
FROM=“http://www.cs.umd.edu/”>
Instanciando em SHOE
No texto:
Meu nome é <ATTRIBUTE “our.firstName”> George
</ATRIBUTE> <ATTRIBUTE “our.lastName”> Cook
</ATRIBUTE> e moro...
<INSTANCE “http://www.cs.umd.edu/~george#HELENA”>
< CATEGORY=“our.Person” >
< RELATION=“our.firstName” TO=“Helena”>
< RELATION=“our.lastName” TO=“Cook”>
< RELATION=“our.marriedTo”
TO=“http://www.cs.umd.edu/~George”>
</INSTANCE>
SHOE : Consulta ao robô Exposé
Com o auxílio da interface gráfica, chegamos a :
(query ‘(:and
(#!instanceOf ?X #!Person)
(#!instanceOf ?Y #!Person)
(#!instanceOf ?Z #!Organization)
(#lastName ?X “Cook”)
(#lastName ?Y “Cook”)
(#employee ?Z ?X)
(#employee ?Z ?Y)
(#marriedTo ?X ?Y)
(#involvedIn (z,”ARPA 123-4567”) ))
Discussão
 O que é melhor : Um só agente ou muitos
(Resolucão Distribuída de Problemas) ?
 O que é melhor : Dotar agentes-assistentes
de IA ou dotar a WWW de IA ?
Bibliografia
 Harrison,C.,Caglayan,A.,”Agent Sourcebook”,Jonh





Wiley,97.
Koster,M.,”Guidelines for Robot Writers”,93.
Koster,M.,“The Web Robots FAQ...”,
http://info.webcrawler.com.
Koster,M.,”Robots in the Web:threat or treat?”,NEXOR,95
Hermans,B.,”Intelligent Software Agents on the Internet”.
Lieberman,H.,”Letizia:Na Agent that assists Web
Browsing”,MIT,95.
Bibliografia
 Rhodes,B Starner,T.,”Remembrance Agent-A continuously
running automated information retrieval system”,MIT,96
 Inaba,M.,”Internet Consultant: An Integrated
Conversational Agent for Internet Exploration”,Hawaii,95.
 Luke,S.et al,”Ontology-Based Knowledge Discovery
onthe World-Wide Web”,UMBC,96.