Extração de Informação
Ana Carolina do Amaral
Marcílio José A. Gomes Filho
Rodrigo C. Mendes
Flávia Barros
Roteiro

Introdução
Motivação
 Um pouco de História
 Processo de Extração
 Conceitos
 Wrappers
 Aplicações
 Referências

Motivação
O volume de informação vem
aumentado consideravelmente,
principalmente com o advento da
internet.
 Como conseguir extrair informação
relevante de tantos artefatos digitais?

Motivação

O Problema:
Documentos em sua maioria não
estruturados ou semi-estruturados. (Internet
- WEB)
 Migração de dados entre interfaces
diferentes. (WebServices – Banco de
Dados)

Motivação

O que queremos:







responder a consultas de usuários
gerar resumos do texto original
preencher bancos de dados
preencher bases de conhecimento
mineração de dados
sumarizar textos
...
Processo de Extração


Trata o problema da extração de dados relevantes
a partir de uma coleção de documentos [Mus99]
Os dados a serem extraídos são previamente
definidos em um template (formulário)
Template
Sistema p/ EI
Item1:
Item2:
Item3:
Item4:
Item5:
BD
BC
Um pouco de História

MUC-Message Understanding Conference
[final da década de 80]


Uso de técnicas de PLN (Processamento
de Linguagem Natural)
Internet/Web [década de 90]

Desenvolvimento de wrappers
Conceitos

Sistemas baseados em PLN



Processamento de Linguagem Natural.
Criados para extrair informação a partir de
textos livres (sem estruturação).
Wrappers


Crescimento da Web a partir dos anos 1990.
Incapacidade dos sistemas anteriores para
extrair informações de seus textos, motivou a
criação de sistemas específicos para esse
domínio.
Conceitos

Quadro Comparativo
Wrappers
Sistemas de EI baseados
em PLN
Motivação
Principalmente, extrair informações
das diversas fontes na Web.
Extrair informações de
textos em linguagem
natural.
Tipos de texto
Geralmente estruturados e semiestruturados, mas também textos
livres, em alguns casos.
Apenas texto livre.
Padrões usados
para extração
Informações de formatação do
texto, marcadores presentes nos
documentos, freqüência estatística
das palavras e, em alguns casos,
PLN.
Padrões lingüísticos
baseados em PLN (uso
intenso de PLN).
Conceitos

Tipos de Texto

Estruturado - segue um formato predefinido e
rígido.
Conceitos

Tipos de Texto

Não estruturado (Livre) - Não apresentam
nenhuma estrutura regular e as informações
apresentam-se como sentenças livres,
escritas em alguma língua natural.
Conceitos

Tipos de Texto

Semi-estruturado - Não possuem uma
formatação rígida, permitindo, por exemplo, a
ocorrência de variações na ordem dos dados.
Em geral, não respeitam rigidamente a
gramática da língua natural, e podem possuir
muitas palavras abreviadas.
M. E. Califf & R. J. Mooney. (1999). Relational learning of
pattern-match rules for information extraction. In Proceedings of
the Sixteenth National Conference on Artificial Intelligence, pp.
328--334 Orlando, FL.
Conceitos

Tipos de Wrappers


Singleshot - são aqueles que extraem do
documento de entrada apenas dados
isolados, ou seja, eles não são capazes de
ligar uma instância de um campo (slot) do
formulário de saída a uma instância de outro
campo.
Multishot - são aqueles capazes de extrair do
documento de entrada os dados relacionados
entre si, ou seja eles são capazes de ligar as
instancias de diferentes campos.
Conceitos

Tipos de Wrappers – Exemplo:
Capitol Hill 1 br twnhme. Fplc D/W W/D.Undrgrnd pkg
incl $675. 3 BR, upper flr of turn of ctry HOME. incl gar,
grt N. Hill loc $995. (206) 999-9999 <br>
<i> <font size=2> (This ad last ran on 08/03/97.)
</font> </i><hr>
sistem a m ulti-slot
sistem a single-slot
bairro: Capitol Hill
quartos: 1
preço: 675
bairro: Capitol Hill
quartos: 3
preço: 995
bairro: Capitol Hill
bairro: Capitol Hill
quartos: 1
quartos: 3
preço: 675
preço: 995
Formulário Preenc hido
Formulário Preenc hido
Sistemas baseados em PLN

Precisam de um pré-processamento
lingüístico para a realização da extração
Classes sintáticas e semânticas das
palavras
 Algumas vezes é impossível fazer este préprocessamento (Informal Domains)


Web!
Wrappers
A princípio não eram capazes de tratar
textos livres
 Recentemente, tornaram-se mais
poderosos


fazem uso das informações de formatação
e também das características lingüísticas
Wrappers

Técnicas para extração de informação
preencherFormulario(documento) =
fomularioPreenchido
 Determinam as regras de extração
 Autômatos finitos, casamento de padrões,
classificadores de texto e modelos de
Markov escondidos

Wrappers – Autômatos finitos

Definição

(S, Σ,T,s0,F)






S é um conjunto finito de estados
Σ é um alfabeto finito de símbolos de entrada
T é a função de transição (T : S × Σ -> S)
s0  S é o estado inicial
F S é o conjunto de estados finais
Excelentes em textos estruturados
 Podem ser definidos manualmente ou ser
aprendidos automaticamente
Wrappers – Autômatos finitos

Tipos

Acceptors: apenas um estado inicial,
resposta é sim ou não


Recognizers: um ou mais estados finais.


Filtragem e existência do dado
Categorização!
Transducers: geram um conjunto de
símbolos de saída para a entrada
Wrappers – Autômatos finitos

Exemplo
<LI> <A HREF="…"> Mani Chandy </A>, <I>Professor of Computer
Science</I> and <I>Executive Officer for Computer Science</I>
…
<LI> Fred Thompson, <I>Professor Emeritus of Applied Philosophy and
Computer Science</I>
? / next_token
?/å
b
U
?/ å
s<U,U> / å
s<b,U> /
“U=” + next_token
s<b,N> /
“N=” + next_token
N
_
U
etc.
s<U,N> /
“N=” + next_token
s<N,N> / å
_
N
?/ å
? / next_token
Key
• ? : wildcard
• U : state to extract URL
• U : state to skip over tokens
until we reach N
• N : state to extract Name
• N : state to skip over tokens
until we reach A
• s<X,Y> : separator rule for
the separator of
states X and Y
• etc.
Wrappers – Autômatos finitos

Devemos definir
Os estados que deverão “aceitar” os
símbolos a serem extraídos para preencher
o formulário de saída
 Os estados que irão apenas consumir os
símbolos irrelevantes encontrados no
documento
 Os símbolos do documento de entrada que
provocaram a transição de um estado para
outro

Wrappers – Casamento de
padrões
Padrões podem ser descritos através de
expressões regulares ou em uma
linguagem específica ao sistema de EI
 O processo de extração se dá quando
se realiza o casamento dos padrões
definidos com o texto de entrada

Wrappers – Casamento de
padrões
Trata textos estruturados, semiestruturados e livres
 Expressões regulares são mais intuitivas
do que autômatos


Realizam extração multi-slot
Wrappers - Classificação
Classifica(fragmentoTexto) = [escore
campo 1, ..., escore campo n]
 Limitações:

Criação dos fragmentos
 Classificam cada fragmento de forma
independente => ótima localmente, mas
nada garante que seja ótima também
globalmente

Wrappers - Classificação
B. Th o m a s, An ti-Un ific a tio n Ba se d Le a rn in g o f T-Wra p p e rs fo r
In fo rm a tio n Extra c tio n, In Pro c . AAAI-9 9 Wo rksh o p o n M a c hine
Le a rn in g fo r In fo rm a tio n Extra c tio n, 1 9 9 9 .
d iv isã o e m fra g m e n to s
B. Th o m a s, An ti-Un ific a tio n Ba se d Le a rn in g o f T-Wra p p e rs fo r
In fo rm a tio n Extra c tio n, In Pro c . AAAI-9 9 Wo rksh o p o n M a c hine
Le a rn in g fo r In fo rm a tio n Extra c tio n, 1 9 9 9 .
fra g m e nto 1 fra g m e nto 2 fra g m e nto 3 fra g m e nto 4
e xtra ç ã o d e
c a ra c te rístic a s
fra g m e nto 1 fra g m e nto 2 fra g m e nto 3 fra g m e nto 4
1
3
0
0
4
1
1
5
2
2
3
2
Wrappers – Modelos de Markov
escondidos

Exploram a ocorrência dos padrões em
seqüência no texto de entrada para
classificá-los de uma só vez

Maximiza a probabilidade de acerto para
todo o conjunto de padrões
Wrappers – Modelos de Markov
escondidos

Modelos de Markov - definição
Conjunto de estados S
 Probabilidade a priori (s) para os estados s
S
 Probabilidade de transição Pr[s’/s] do
estado s  S para o estado s’  S


S = {ensolarado, chuvoso, nublado}
(nublado)
Pr[chuvoso/ensolarado]
Wrappers – Modelos de Markov
escondidos

Estados ocultos


É possível observar os símbolos (estados visíveis)
emitidos pelos estados escondidos
A cada estado oculto, é associada uma das
classes a serem extraídas
 Cada estado oculto emite tokens de acordo
com a probabilidade de pertencer à classe
associada ao estado
 Criado o modelo, pode-se utilizar o algoritmo
Viterbi para decodificar uma entrada e
determinar os estados ocultos associados
Wrappers – Modelos de Markov
escondidos
B
.T
homas
, Anti-U
nification B
as
ed L
earning of T
-W
rappers
for Information E
x
traction, In P
roc. AAAI-99 W
ork
s
hop on
título
0,2
B
. |T
homas| , | Anti-U
nification | B
as
ed | L
earning | of
|T
-W
rappers| for | Information | E
x
traction | , | In |
P
roc. | AAAI-99 | W
ork
s
hop | on | M
achine | L
earning |
0,5 0,5
S
0
0,8
autor0
0,2
A
lgoritmoV
iterbi
B
.= a
u
to
r | T
h
o
m
a
s= a
u
to
r| ,=o
u
tro| A
n
ti-U
n
ifica
tio
n= títu
lo
| B
a
se
d= títu
lo
| L
e
a
rn
Aplicações de RI

Extração de Informação em Documentos

Palavras-chave
Indexação
 Catalogação

Empresa do Rio de Janeiro com mais de 12 anos de experiência
em Gerenciamento Eletrônico de Documentos.
Aplicações de RI

Extração de Informação em Documentos

Conteúdo
Análise Estrutural
 Análise Semântica

Empresa portuguesa responsável por 3,4% do PIB de Portugal.
Aplicações de RI

Extração de Informação em Documentos

Análise do Código Fonte de Aplicações
Uso de Padrões
 Qualidade do Código

Empresa de Curitiba, oferece sistemas de análise do código fonte
em diversas linguagens.
Aplicações de RI

Extração de Informação na WEB

Filtragem de Fóruns
Controle do Conteúdo
 Assunto dos Diálogos

Empresa de São Paulo com mais de 20 anos de mercado. Oferece
soluções para e-learning.
Aplicações de RI

Extração de Informação na WEB

Monitoramento da WEB
Busca por Hackers
 Busca por Terroristas

Empresa mundialmente reconhecida, presente no Brasil há 10 anos,
oferecendo soluções nas áreas de segurança web e redes.
Aplicações de RI

Extração de Informações Estratégicas

Business Intelligence
Análise de Mercado
 Melhoria de Processos

Empresa brasileira que oferece soluções na área de BI.
Aplicações de RI

Extração de Informações Estratégicas

Análises Biológicas de Dados
Regiões Codificantes (DNA)
 Regiões Ativas (Proteínas)

National Center for Biotechnology Information, criado em 1988, localizado
nos Estados Unidos. É a principal fonte de informações sobre Genômica
na Internet.
Aplicações de RI

Extração de Informações Estratégicas

Análises de Arquivos de LOG
Logs de Erro
 Logs de Acesso

Empresa mundialmente reconhecida, com mais de 25 anos, oferece
soluções para a análise de logs de erro e acesso a bancos de dados.
Aplicações de RI

Extração de Informações Estratégicas

Análises de Imagens
Geologia
 Climatologia
 Astrologia

Empresa brasileira com 10 anos de mercado, oferece soluções para
análise e classificação de imagens.