Sistemas Multiagentes Cognitivos
para Extração de
Informações Relevantes na Web
Fred Freitas
[email protected]
LCMI - Laboratório de Controle e Microinformática
Pós-Graduação em Inteligência Artificial
Projeto PROBAL
UFSC - Universität Karlsruhe (Alemanha)
Fred Freitas - LCMI - DAS - UFSC
Roteiro






Problemas de Busca na Internet
Técnicas existentes
Princípios da solução proposta
Justificativa para Multiagentes para Extração
Implementação
– Técnicas, experimentos, avaliação
Trabalho futuro
Fred Freitas - LCMI - DAS - UFSC
Problemas de Busca na Internet:
Tamanho

Enorme quantidade de páginas
– Solução : distribuir
– Não apenas um robô de busca, mas vários
– Brokering, indexadores e índices distribuídos, como o
Bright!
Fred Freitas - LCMI - DAS - UFSC
Problemas de Busca na Internet:
Semântica



“A abordagem estatística e’ necessariamente uma
pobre substituta da abordagem baseada em
conhecimento” [Croft 93]
Não dá para contextualizar toda a Internet
(Raciocínio de Senso Comum e PLN) de uma vez
Engenharia de conhecimento
– Combinar informações por problema, situação e
usuário, complementando IR [van de Velde 95]
Fred Freitas - LCMI - DAS - UFSC
Busca na Internet
Computação
Tradicional
Integrar BDs
Estruturar págs
Robôs,
Java
?
BD
Bright!
Ags.cog Ontologias
CFP Finder
nitivos
Recuperação de
Informações (IR)
ES
Mecanismos de
Busca distribuídos
Mediação,
Planejamento
Tagging
Wrapping
SD
Inteligência
Artificial
Robôs
Distribuídos
SMA
Reativo
Fred Freitas - LCMI - DAS - UFSC
ML
PLN
Stemming
WordNet
Hiperônimos
Sinônimos
Parsing
Modelagem
do Usuário,PDAs
(Estatística,
Aprendizado
e CBR)
Problemas de
cada solução
Computação
Tradicional
SMA
cognitivo
Normalização
BD
Aquisição de
Ags.cog conhecimento
nitivos
Recuperação de
Informações (IR)
ES
Ausência de
contexto e
estrutura
SD
Inteligência
Artificial
SMA
Reativo
Fred Freitas - LCMI - DAS - UFSC
ML
PLN
Alto custo
computacional
sem benefício
correspondente
Avaliação das abordagens
Abordagem
IR
Precisão
Baixa
Robustez
Alta
Custo
Baixo
PLN
Alta
Baixa
Alto
K
Alta
Boa
Acessível
Fred Freitas - LCMI - DAS - UFSC
Princípios: Contexto


As palavras dos textos podem ganhar mais
semântica, se interpretadas de acordo com o
contexto (agregar valor).
Aplicar o máximo de conhecimento a priori e
heurísticas. Conhecimento sobre:
–
–
–
–
Localização
Informações esperadas
Estrutura de tópicos
Estilo de composição das páginas
Fred Freitas - LCMI - DAS - UFSC
Princípios: Memória e Concorrência

Não desperdiçar esforços na interpretação das páginas.
– Ao tratá-las, passar apenas uma vez por página.



Os requisitos de Contexto e Memória levam naturalmente
ao uso de abordagens baseadas em conhecimento
explícito (agentes cognitivos).
Agentes podem ser dotados de adaptabilidade,
apresentando robustez a informações e situações não
previstas de antemão .
O requisito de Concorrência leva ao uso de Sistemas
Multiagentes Cognitivos.
Fred Freitas - LCMI - DAS - UFSC
Lição aprendida de IA :
Dividindo para conquistar


Todo o conhecimento humano está armazenado
numa só coleção ? Deve-se encontrar carros à venda
em sites de .edu ?
Porque os testes da área são sempre sobre corpora
homogêneos ?
– Nenhuma solução é geral
– Restringir a domínios
Fred Freitas - LCMI - DAS - UFSC
Como prover contexto






O usuário está atrás de informação útil e não de páginas!
Buscam-se normalmente as mesmas informações.
Ao invés de Recuperação, Extração de Informações (nova
área) Baseada em Conhecimento (nossa novidade).
Construção de BDs de informações úteis a partir de
paginas estruturadas.
Consultas semanticamente bem definidas podem combinar
informações de vários sites.
Solução atual :
– Wrappers : Extratores de textos baseados em gramáticas

Pobres, exigem informação muito estruturada
Fred Freitas - LCMI - DAS - UFSC
Utilidade de BDs sobre a Web

Dá pra fazer consultas como essa na Web?
– Achar carros vermelhos a partir de 93, por menos de
5000


Select * From Car Where Color=“red” And Year >=
1993 And Price < 5000
Motivo da impossibilidade [Campbell et al 98]:
– Buscas baseadas exclusivamente em palavras chaves
e freqüências.
Fred Freitas - LCMI - DAS - UFSC
Extratores Atuais
'97 CHEV Cavalier, Red, 5 spd, only 7,000 miles on her.
Previous owner heart broken! Asking only $11,995. #1415.
JERRY SEINER MIDVALE, 566-3800

Descriptor/String/Position(start/end)
Year|97|1|3
Make|CHEV|5|8
Model|Cavalier|10|17
Feature|Red|20|22
Feature|5 spd|25|29
Mileage|7,000|37|41
KEYWORD(Mileage)|miles|43|47
Price|11,995|108|114
PhoneNr|556-3800|146|153
[Campbell et al 98]



Wrappers são gerados
automaticamente.
Baseados em aprendizado
automático ( machine
learning), adaptam-se rápido
a formatos diferentes.
Mas, usam sintaxe, no
reconhecimento , não
semântica...
Porisso, não permitem
inferência nem cooperação!
Fred Freitas - LCMI - DAS - UFSC
As Classes de Páginas

Unidade Básica da Internet:
– Texto sem estruturação formal


Mas, há classes de páginas com alguma estrutura
– Ex: Calls for papers, pesquisadores, dados da bolsa, etc
As classes possuem ainda Similaridade estrutural
– O estilo de composição das páginas de uma mesma
categoria do Yahoo (que é manual!) possui fatos
relevantes que podem ajudar a diferenciá-las das outras
áreas [Cruz et al 97].
Fred Freitas - LCMI - DAS - UFSC
Cooperando produtivamente

Um só agente resolve?
– A Internet é muito grande e diversa.
– O domínio de atuação de um agente não pode ser irrestrito.




Clusters - Conjuntos de classes fortemente conectadas
entre si, através de links.
Cada agente que trata uma classe de páginas coopera
com os outros, identificando links e outras informações,
que interessem a estes.
Sistema Multiagente Cognitivo: Um tipo de conhecimento
para cada agente diminui a complexidade e aproveita a
concorrência.
Resolução Distribuída de Problemas (RDP).
Fred Freitas - LCMI - DAS - UFSC
Tecnologia disponível baseada em
conhecimento explícito


Capacidade de inferência
Protocolo peer-to-peer
– Comunicação a nível de conhecimento

Ontologias Reusáveis
– Repositórios de conhecimento reaproveitados
– Em IR, pouco se aproveita do trabalho alheio, só as
estatísticas.
Fred Freitas - LCMI - DAS - UFSC
Experimentos

CFP Finder: agente para recuperar, armazenar e
classificar por área e extrair informações relevantes
de páginas de Calls for Papers.
– Resultados promissores com poucas regras.
– 86% no reconhecimento.

Robô aproveita consultas dos engenhos de busca
– Altavista, Excite, InfoSeek, ...
Fred Freitas - LCMI - DAS - UFSC
Possível arquitetura de Mecanismos
de Busca
Ex:WordNet
Ex: IMPS
Ag.
Construtor
Ontols.
Robô
Ontologias
Mec.
Busca
...
Robô
Links
+ pags
Índices
Fred Freitas - LCMI - DAS - UFSC
Thesaurus
semântico
Links,
Conhecimento
Técnicas empregadas - Básicas

Análise Léxica (tokens),Stop-lists, stemming, ranking

Tagging - PLN
– Determina regiões num texto.
– EX do FAQ Finder [Burke et al 96]
:QUE
When do I have to change oil ?
:QUE
:ANS
After ...

Wrapping
– Gramáticas para reconhecer e capturar informações
dentro de um determinado formato.
– Ex: Datas
Fred Freitas - LCMI - DAS - UFSC
Ontologias
(deftemplate Pagina
(slot Ano )
(slot Nome)
PáginaWWW PáginaGopher
(slot URL)
(slot Formato)
PáginaHTML
PáginaPS
...
)
(defrule PagHTML
PáginaCFP
“Se a pagina é HTML”
(formato ?x)
(eq ?x ‘html’)
=>
Fred Freitas - LCMI - DAS - UFSC.... )
Página
Funcionamento de um agente
Fila de
URLs
(ALTA
Prioridade)
Outros
Agentes
Fila de
URLs
(BAIXA
Prioridade)
Robô
URLs
Regras de validação
Inválidas
URLs válidas
Onto
logias
Pré-process.:stemming,
tagging, indexação, etc
Atualização nos “slots” da
Ontologia da Página
KQML
Regras de
reconhecimento
Categorização
baseada em
ontologias
Biblio
teca
Base
Dados*
Extração de infs
relevantes dos
Fred documentos
Freitas - LCMI - DAS - UFSC
* - contém
estatísitcas
Técnicas empregadas - Avançadas

Princípio Huhns-Singh para agentes:
– Um agente deve mudar de comportamento quando
outro agente entra no ambiente.

Modelo baseado no InfoSleuth [Bayardo et al 96]
– Um novo agente se anuncia dizendo que paginas e
links quer e recebe dos outros o que eles querem

Java +JDBC, HTML, BDs, JESS, KQML (JATLite).
CLIPS ou KIF(ACL).
Fred Freitas - LCMI - DAS - UFSC
Metodologia de Avaliação


1. Obter boas performances com cada agente
2. Testar se a cooperação melhora a performance, já que:
– Há um número significativo de links errados vindos dos robôs
– O overhead de reconhecimento de informações para outros
agentes é baixo


A cooperação facilitará também o monitoramento
– Ex: Papers por conferência, autor, ...
O processo inicial de troca de mensagens de identificação
entre os agentes não será considerado na mensuração da
performance.
Fred Freitas - LCMI - DAS - UFSC
Ontologias comuns a todos os
agentes


Classes Página, PáginaWWW e outras.
Talvez devam conter até os centróides :
– De palavras-chave (com ordem, para identificar termos)
– De tags HTML (para avaliar a estrutura).

Ontologia do domínio:
– No nosso caso, o domínio científico







áreas
papers
CFPs
pesquisadores
órgãos
eventos
Fred Freitas - LCMI - DAS - UFSC
etc.
Ontologias de cada agente





Classes específicas das páginas de que trata
Regras de Reconhecimento
Um subconjunto de regras de reconhecimento e
classes para os outros agentes lhe indicarem páginas
e links
Regras e classes para indicar páginas e links para os
outros agentes
Regras de extração e categorização
Fred Freitas - LCMI - DAS - UFSC
Passos futuros

Imediatos:
–
–
–
–
–
–
–
Conhecimento declarativo para a inferência: JESS
Técnicas de IR: stemming, tagging, ranking, ...
Heurísticas : título, pesos de palavras, termos...
Nomes próprios e de cidades
Definir as gramáticas e os dicionários
Tratar sites
Concorrência: threads (ver como dividi-las).
Fred Freitas - LCMI - DAS - UFSC
Passos futuros

Médio Prazo:
– Incluir outros agentes (pesquisadores, papers, ...)
– Troca de mensagens (KQML ?)
– Aproveitar informações de organização das URLs
– Incluir aprendizado e conseqüente feedback do
usuário, para facilitar a aquisição do conhecimento
– Definir métricas de avaliação
– Buscar no BD com IR [Cohen 95]
Fred Freitas - LCMI - DAS - UFSC