Projeto X-Finder Agents
Recuperação e Indexação de
páginas especializadas na Web
Disciplina: Inteligência Artificial Simbólica
Professora: Flávia Barros
1
X-Finder Agents
Andamento


A cada novo assunto pertinente* apresentado, será
proposta 1 tarefa cujo resultado será posteriormente
avaliado em uma aula de laboratório
Teremos 3 tarefas ao todo (3 etapas do projeto),
segundo o cronograma de aulas da página do curso
Grupos

No máximo, 4 alunos por equipe
* o que não é pertinente será cobrado em uma lista de exercícios
2
Páginas Especializadas
Páginas especializadas: estrutura na Web


apesar da aparência caótica, a Web pode ser vista
como um aglomerado de classes particulares de
páginas
essas páginas especializadas têm em comum
características sintáticas (formato) e semânticas
(conteúdo)
Exemplos

FAQs, páginas de hotéis, páginas pessoais, chamadas
de trabalho (cfp), lista de artigos, restaurantes,
classificados, cinemas, ...
3
Páginas Especializadas
Exemplo: página de publicações
4
Arquitetura do Sistema
Web
Busca por palavraschave do domínio
(ex. Publications)
Engenhos de
Busca
tradicionais
(ex. Google)
URLs + Páginas
HTML recuperadas
Consulta:
palavras-chave
URLs recuperadas
Base de
Índices
Específica
Classificador
URLs classificadas
positivamente
5
Objetivo
Projeto básico (para todos)

Implementar um conjunto de agentes capazes de
recuperar, classificar e indexar páginas
especializadas
Extensões eventuais
(a) prover extração de informação
(b) estender a busca com as palavras mais comuns
(ex. bolo, carnes, ...)
(c) introduzir conectores lógicos para consulta a
posteriori
(d) notificação personalizada
6
Etapa 1: Criar o corpus
Identificar palavras-chave a serem usadas nas
consultas aos engenhos de busca genéricos


ex. “conference”, “symposium” e “call for papers”
para o caso das páginas de chamadas de trabalho
ex. “receitas”, “ingredientes” para o caso de
receitas culinárias
Montar um corpus de páginas à mão
7
Etapa 1: Criar o corpus
Criação manual do corpus:



Fazer consultas a Engenhos de Busca usando as
palavras-chaves identificadas
Separar páginas positivas (que pertencem à classe
escolhida) das negativas
Armazená-las em um BD (ou arquivo) indicando se são
positivas ou negativas
 url, classe, arquivo html

Recolher 300 páginas
 200 positivas e 100 negativas

Separar o corpus em dois:
 Treinamento (140 páginas + e 70 páginas -)
 Teste (60 páginas + e 30 páginas -)
8
Etapa 2: Montar a Base de Regras
Com base no corpus de treinamento, identificar
possíveis regras de classificação



Se a palavra “publications” aparece no título
E existem parágrafos com nomes de conferências ou
congressos
Então é uma página de publicações
Implementar as regras de classificação

Reutilizar uma classe que manipula arquivos html
(www.cin.ufpe.br/~compint/aulas-IAS/programas/PaginaWWW.java)

utilizar JEOPS ou Clips
9
Montar regras com fator de
certeza associado
Montar regras com fator de certeza (F.C.) associado


Objetivo: melhorar a precisão do sistema
Se evidência1 Então pag.positiva com F.C.% de chance
O F.C. é calculado pelo do Teorema de Bayes


P(pag.pos | evidência1) =
P(pag.pos ^ evidência1) / P(evidência1)
Onde:
 P(pag.pos | evidência1) é a probabilidade de uma página ser
positiva dado que a evidência1 ocorreu
 P(pag.pos ^ evidência1) é a quantidade de páginas positivas
que contêm a evidência1
 P(evidência1) é a quantidade de páginas positivas e
negativas (o corpus inteiro) que contêm a evidência1
10
Utilizar as regras com fator de
certeza associado
Quando a máquina de inferência dispara regras com a
mesma conclusão, ela deve combinar os F.C. associados
O objetivo é calcular a probabilidade final de uma dada
página ser positiva
 P-atual = P-anterior + P-nova * (1 - P-anterior)
Por exemplo:
 Se evidência1 Então pag.positiva com 90%
 Se evidência2 Então pag.positiva com 85%
 P-atual = 0,9 + 0,85 * (1 - 0,90)
Quando a máquina de inferência pára, teremos a
probabilidade final de uma página ser positiva
Em JEOPS, pode-se implementar a probabilidade
acumulada no objeto
11
Etapa 2: Regras com fator de
certeza associado
A probabilidade final é comparada a um limiar
 Se P-final >= limiar Então página positiva
Cada classificador poderá usar um limiar diferente

O limiar é calculado “iterativamente” com base na
F-measure para o corpus de treinamento
1.
2.
3.
4.
5.
Escolher um limiar inicial (p. ex. = 60%)
Calcular F-measure
Aumentar o limiar em 0.5 e calcular F-measure
Repetir passo 3 até F-measure começar a piorar
Escolher para o sistema o limiar que apresentou melhor
F-measure
Com base no corpus de teste, medir o desempenho
do sistema classificador

Precisão, Cobertura e F-measure
12
Etapa 2: Avaliação final do
sistema
Precisão:

total de páginas classificadas corretamente como
positivas sobre o total de páginas classificadas
como positivas (sendo elas positivas ou negativas
no corpus)
Cobertura:

total de páginas classificadas corretamente como
positivas sobre o total de páginas positivas
existentes no corpus
F-measure:

2 * cobertura * precisão
cobertura + precisão
13
Etapa 2: Avaliação final do
sistema
Exemplo:






total de páginas do corpus = 200
total de páginas positivas do corpus = 170
total de páginas negativas do corpus = 30
total de páginas positivas classificadas corretamente como
positivas = 130
total de páginas negativas classificadas como positivas = 20
total geral de páginas classificadas como positivas = 150
Precisão = 130 / 150 = 0,87
Cobertura = 130 / 170 = 0,76
F-measure = (2 * 0,87 * 0,76) / (0,87 + 0,76)
= 1,32 / 1,63 = 0,81
14
Etapa 3: Aprendizagem Automática
Preparar o corpus



“enxugar” o texto, inclusive tirando tags
escolher as palavras mais pertinentes (TFIDF)
compor o vetor de representação
Escolher alguns algoritmos de aprendizagem
(ID3, RN, Bayes, etc.)


codificar os exemplos
rodar os algoritmos e obter os resultados
Avaliar os métodos de classificação

dedutivo x indutivo: discutir resultados!
15
Etapa 4: Ontologias
A definir
16
Etapa 5: Criar Base de Índices
Tendo construído o classificador (regras ou
aprendizagem)

criar base de índices com as páginas pertencentes
à classe desejada
 stop-list, arquivos invertidos, ...
 utilizar inicialmente apenas as páginas do corpus


prover interface para consulta (simples!)
Opcional: automatizar busca na Web a fim de
alimentar a base de índices automática e
periodicamente
17
Etapa 5 - opcional:
Implementar Protótipo
Automatizar consulta a mecanismos de busca

Reutilizar/programar as classes para acesso aos
mecanismos de busca
Identificar estrutura da página de resposta do
mecanismo de busca para extração dos links

ex. terceira linha, depois de um <LI>...
Automatizar extração de links das respostas

Reutilizar/programar uma classe que manipula
arquivos html
Automatizar atualização e indexação
periódicas da base de índices
18
Etapa 6 - opcional
Se der tempo, dividir os grupos para estender
o trabalho em alguma das seguintes direções:
(a) prover extração de informação
(b) estender a busca com as palavras mais comuns
(ex. bolo, carnes, ...)
(c) introduzir conectores lógicos para consulta a
posteriori
(d) fazer notificação personalizada
19
Referências
Internet Categorization and Search: A Self-Organizing
Approach, Hsinchun Chen, University of Arizona,
1996.
Learning from Hotlists and Coldlists: Towards a WWW
information filtering and seeking agent, Michael
Pazzani, University of California.
The State of the Art in Text Filtering, Douglas W.
Oard, University of Maryland, 1997.
BRight: a Distributed System for Web Information
Indexing and Searching, Pedro Falcão & Silvio Meira,
Universidade Federal de Pernambuco.
20
Referências
Ontologies for Enhancing Web Searches' Precision
and Recall, Flávia A. Barros, Pedro F. Gonçalves,
Universidade Federal de Pernambuco.
Information Retrieval: Data Structures & Algorithms,
Willian B. Frakes e Ricardo Baeza-Yates, Prentice Hall,
1992.
Filtragem e Recomendação de Documentos na Web.
Uma Abordage Usando Java, José Abelardo Sánchez
Cardoza, Universidade Federal de Pernambuco, 1998.
21
Referências - links
Universidade de Maryland


http://www.cs.umbc.edu/abir/
http://www.cs.umbc.edu/agents/
Intelligent Software Agents

http://www.sics.se/ps/abc/survey.html
MIT Media Lab

http://lcs.www.media.mit.edu/groups/agents/resources
Sycara’s Page

http://almond.srv.cs.cmu.edu/afs/cs/user/katia/www/katiahome.html
Sasdwedish Institute of Computer Science

http://www.dsv.su.se/~fk/if_Doc/IntFilter.html
22