Extração de Informação
Domingos Sávio
Raoni Franco
Roberto Costa
Ronaldo Marques
Roteiro






Motivação
História
Processo de Extração
Wrappers
Aplicações
Referências
Motivação

Internet – Crescimento exponencial de
informações;

Maior parte da informação está na base de
textos.
Motivação

Documentos não estruturados ou semiestruturados;

Migração de dados entre diferentes
interfaces.
Motivação

Como pesquisar?

Como resumir?

Como gerar bases de conhecimento?

O que é relevante?
História

Início (fim da década de 80)

MUC-Message Understanding Conference


Ontem

Internet


Processamento de Linguagem Natural
Wrappers
Hoje

Mash-up
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
Processo de Extração


Transformar infomações não-estruturadas em um
corpus de documentos ou páginas web dentro de
uma base de dados.
Aplicado em diferentes tipos de textos:






Artigos de Jornais
Web pages
Artigos Científicos
Mensagens de Newsgroup
Classified ads
Notas Médicas
EI Tradicional

Extrair informações relevantes de um trecho de
texto


Domínio específico


Blah blah blah relevante blah blah blah
ex: Domínio de Businness
O significado do que é “relevante” é pré-definido

ex: ciclo de vida de companhias:




Ações: juntar, separar, comprar
Companhias envolvidas e seus papéis
Capital envolvido
Dados obscuros e objetivos do escritor são
irrelevantes
Utilidade da EI
A base estruturada resultante pode ser usada
para:
 Procurar ou analisar, utilizando queries
padrões de banco de dados
 Mineração de Dados
 Geração de sumários (possivelmente em
outra linguagem)
 Construção de índices para a coleção de
documentos fonte.
Exemplo: Ataque Terrorista
Exemplo: Ataque Terrorista
Exemplo: Ataque Terrorista
EI comparada com outros
campos relacionados


EI vs. Recuperação de Informação
EI vs. Compreensão Completa do Texto
EI vs. Recuperação de
Informação

RI:



Dada uma consulta do usuário, um sistema de RI
seleciona um subconjunto de documentos
relevantes de um conjunto maior
Depois o usuário procura as informações que ele
necessita no subconjunto selecionado
EI extrai informações relevantes de
documentos RI e EI são tecnologias
complementares
EI vs. Recuperação de Informação

Recuperação de Informação:


Entrega documentos para o usuário
Extração de Informação:

Entrega fatos para o usuário/aplicacões
EI vs. Compreensão Completa do
Texto
• CCT – entendimento
do texto inteiro
• CCT – respresentação
alvo deve acomodar a
complexidade da língua
• CCT – necessita
reconhecer aspectos
estilísticos
• EI – somente uma
parte do texto é
relevante
• EI – representação
alvo rígida
• EI – estilo e cor do
texto é irrelevante
Por que EI é difícil?


Linguagem Natural é difícil
Languagem é flexível – várias formas para
expressar uma única informação
Frodo Baggins succeeds Bilbo Baggins as
chairperson of Bank of America.
 Bank of America named Frodo Baggins as its new
chair-person after Bilbo Baggins.
 Bilbo Baggins was succeeded by Frodo Baggins as
chair-person of Bank of America.
… precisa de mais alguma versão?

Por que EI é difícil?

Linguagem é ambígua – mesma sentença
podendo ter significados diferentes


Sam, Frodo’s partner, a CMU student, …
Linguagem é dinâmica


New words are constantly introduced into the
language: ecotourist, lol
Established words gain new senses: to google, to
message
Sample Job Posting
Subject: US-TN-SOFTWARE PROGRAMMER
Date: 17 Nov 1996 17:37:29 GMT
Organization: Reference.Com Posting Service
Message-ID: <[email protected]>
SOFTWARE PROGRAMMER
Position available for Software Programmer experienced in generating software for
PC-Based Voice Mail systems. Experienced in C Programming. Must be familiar
with communicating with and controlling voice cards; preferable Dialogic, however,
experience with others such as Rhetorix and Natural Microsystems is okay. Prefer 5
years or more
experience with PC Based Voice Mail, but will consider as little as 2 years. Need to
find a Senior level person who can come on board and pick up code with very little
training.
Present Operating System is DOS. May go to OS-2 or UNIX in future.
Please reply to:
Kim Anderson
AdNET
(901) 458-2888 fax
[email protected]
20
Extracted Job Template
computer_science_job
id: [email protected]
title: SOFTWARE PROGRAMMER
salary:
company:
recruiter:
state: TN
city:
country: US
language: C
platform: PC \ DOS \ OS-2 \ UNIX
application:
area: Voice Mail
req_years_experience: 2
desired_years_experience: 5
req_degree:
desired_degree:
post_date: 17 Nov 1996
21
Amazon Book Description
….
</td></tr>
</table>
<b class="sans">The Age of Spiritual Machines : When Computers Exceed Human Intelligence</b>
<font face=verdana,arial,helvetica size=-1>
by <a href="/exec/obidos/search-handle-url/index=books&field-author=
Kurzweil%2C%20Ray/002-6235079-4593641">
Ray Kurzweil</a><br>
</font>
<br>
<a href="http://images.amazon.com/images/P/0140282025.01.LZZZZZZZ.jpg">
<img src="http://images.amazon.com/images/P/0140282025.01.MZZZZZZZ.gif" width=90
height=140 align=left border=0></a>
<font face=verdana,arial,helvetica size=-1>
<span class="small">
<span class="small">
<b>List Price:</b> <span class=listprice>$14.95</span><br>
<b>Our Price: <font color=#990000>$11.96</font></b><br>
<b>You Save:</b> <font color=#990000><b>$2.99 </b>
(20%)</font><br>
</span>
22
<p> <br>…
<br>
Extracted Book Template
Title: The Age of Spiritual Machines :
When Computers Exceed Human Intelligence
Author: Ray Kurzweil
List-Price: $14.95
Price: $11.96
:
:
23
Tipos de texto

Estruturado


Não-Estruturado



Formato pre-definido e rígido
Livre
Sentenças em alguma linguagem natural
Semi-estruturado


Formatação não segue regras rígidas
Algum grau de estruturação


campos ausentes
variações na ordem dos dados
<HTML><TITLE>Some Country Codes</TITLE><BODY>
• Uno 97, 4p., <I>242</I><BR>
Ar, Dir, VE, Som, Prata
<B>Congo</B>
Estudantes caras-pintadas protestaram, ontem, no
• Gol
16V,Paulo
ano<I>20</I><BR>
94,
Ar, 2 portas,
Al.
<B>Egypt</B>
Centro
de São
exigindo
o impeachment
do
prefeito
Celso92,
Pitta,
de corrupção
<B>Spain</B>
• Corsa
c/<I>34</I><BR>
2 acusado
portas, Alarme,
Rodas por sua
ex-mulher.
<B>Belize</B> <I>501</I><BR>
<HR></BODY></HTML>
Tipos de Sistemas para EI

Baseados em PLN



Extrair informações de textos em linguagem
natural (livre)
Padrões lingüísticos
Wrappers



Principalmente para textos estruturados e
semi-estruturados
Formatação do texto, marcadores, freqüência
estatística das palavras
Construção

Manual X Aprendizagem
Construção manual de
Wrappers

Baseada em engenharia do conhecimento



Vantagem


Construção manual de regras de extração
Padrões de extração são descobertos por especialistas
após examinarem o corpus de treinamento
Boa performance dos Sistemas
Desvantagens



Processo de desenvolvimento trabalhoso
Escalabilidade
Especialista pode não estar disponível
Construção Automática de
Wrappers

Aprendizagem de máquina


Vantagens




Aprender sistemas de EI a partir de um conjunto de
treinamento
Mais fácil marcar um corpus do que criar regras de
extração
Menor esforço do especialista
Escalabilidade
Desvantagens

Esforço de marcação do corpus de treinamento
Natural Language Processing


Capazes de lidar com as irregularidades
das línguas naturais
Técnicas.



Part-of-speech (POS) tagging
 Mark each word as a noun, verb, preposition,
etc.
Syntactic parsing
 Identify phrases: NP, VP, PP
Semantic word categories
 KILL: kill, murder, assassinate, strangle,
suffocate
Wrappers - Técnicas de
Extração


Definem como o sistema realiza o processo
de extração da informação
Técnicas




Autômatos Finitos
Casamento de Padrões
Classificação de Textos
Modelos de Markov Escondidos
Wrappers – Autômatos Finitos


Regras de extração na forma de autômatos finitos
Definidos por:




(1) estados que “aceitam” os símbolos do texto que
preenchem algum campo do formulário de saída,
(2) os estados que apenas consomem os símbolos
irrelevantes encontrados no texto, e
(3) os símbolos que provocam as transições de estado
Textos estruturados e semi-estruturados

Delimitadores, ordem dos elementos
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 - Casamento de Padrões



Aprendem regras na forma de expressões regulares.
Expressões regulares que “casam” com o texto para extrair as
informações
Textos livres, estruturados e semi-estruturados

Delimitadores, padrões regulares (Ex. data, CEP)
Padrão :: * (Digit) ‘ BR’ * ‘$’ (Number)
Formulário:: Aluguel {Quartos $1} {Preço $2}
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>
Wrappers - Classificação de textos




Dividem o texto de entrada em fragmentos candidatos a
preencher algum campo do formulário de saída.
Classificam os fragmentos com base em suas características
 posição
 número de palavras
 presença de palavras específicas
 letras capitalizadas
Desvantagem
 Classificação local independente para cada fragmento
(desvantagem)
Textos semi-estruturados
Classificação de Textos

Classificam fragmentos do documento para
determinar que campo do formulário eles devem
preencher
Classificador
outros
empresa
outros
nome
cargo
endereco
endereco
telefone
telefone
Wrappers - Modelos de Markov
Escondidos (HMM)

Um HMM é um autômato finito probabilístico que consiste em:





Processo de classificação



O algoritmo Viterbi
Retorna a seqüência de estados ocultos com maior probabilidade de ter
emitido cada seqüência de símbolos de entrada.
Vantagem


(1) Um conjunto de estados ocultos S;
(2) Uma probabilidade de transição Pr[s’/s] entre os estados ocultos s E S e
s’ E S;
(3) Um conjunto de símbolos T emitidos pelos estados ocultos;
(4) Uma distribuição de probabilidade Pr[t/s] de emissão de cada símbolo t
E T para cada estado escondido s E S.
Realizar uma classificação ótima para a seqüência completa de entrada.
Desvantagem

Não é capaz de fazer uso de múltiplas características dos Tokens (por
exemplo, formatação, tamanho e posição),
Desenvolvimento Teórico

Um “modelo” HMM é definido
por:
a33
 O número de estados não-visíveis.
 A matriz de transição de estados.
a
 O número de observações ou a11
estados visíveis.
y1 y2 y3 y4
b31 b32 b33
b34
3
a23
31
a13
a12
a23
a22
1
 A matriz de probabilidade
2
de emissão de estados visíveis. b11
a21
b12 b13 b14
b21 b22 b23b24
y1 y2 y3 y4
y1 y2 y3 y4
Exemplo Ilustrativo
Lago L1
Lago L2
1
2
3
P1  L1, L2, L2, L1, L1, L1, L2, L2, L2, L2
P2  L2, L1, L2, L1, L1, L2, L1, L1, L2, L2
P3  L1, L1, L1, L2, L1, L2, L1, L2, L2, L2
Deseja-se
identificar este
pato!!
PX  L1, L2, L2, L2, L1, L2, L1, L1, L2, L1
Exemplo Ilustrativo
P1  L1, L2, L2, L1, L1, L1, L2, L2, L2, L2

2 transições vão para L1
4 transições que saem de L1
 2 transições vão para L2

A1
Saída
Chegada
L1 L2
L1 0.5 0.5
L2
Assume-se que a probabilidade de
se visitar um lago depende de que
lago foi visitado no dia anterior,
caracterizando uma
Cadeia de Markov.
Exemplo Ilustrativo
P1  L1, L2, L2, L1, L1, L1, L2, L2, L2, L2

1 transição vai para L1
5 transições que saem de L2
 4 transições vão para L2

A
Chegada
1
Saída
L1
L2
L1
L2
0.5
0.5
Assume-se que a probabilidade de
se visitar um lago depende de que
lago foi visitado no dia anterior,
caracterizando uma
Cadeia de Markov.
Exemplo Ilustrativo
P1  L1, L2, L2, L1, L1, L1, L2, L2, L2, L2

1 transição vai para L1
5 transições que saem de L2
 4 transições vão para L2

A
Chegada
1
Saída
L1
L2
L1
0.5
0.5
L2
0.2
0.8
Assume-se que a probabilidade de
se visitar um lago depende de que
lago foi visitado no dia anterior,
caracterizando uma
Cadeia de Markov.
Exemplo Ilustrativo
A1
Chegada
L2
Saída
Saída
L1
A2
L1 0.5 0.5
L2 0.2 0.8
A3
Chegada
Saída
L1
L2
L1 0.4 0.6
L2 0.5 0.5
Chegada
L1
L2
L1
0.4
0.6
L2
0.2
0.7
Exemplo Ilustrativo

Conclusões:

Probabilidade de PX ter sido gerado pelo Pato 1:
PX  L1, L2, L2, L2, L1, L2, L1, L1, L2, L1
0.5 x 0.8 x 0.8 x 0.2 x 0.5 x 0.2 x 0.5 x 0.5 x 0.2 = 0.00032
A1
Chegada
Saída
L1
L2
L1
0.5
0.5
L2
0.2
0.8
Exemplo Ilustrativo

Conclusões:

Probabilidade de PX ter sido gerado pelo Pato 2:
PX  L1, L2, L2, L2, L1, L2, L1, L1, L2, L1
0.6 x 0.75 x 0.75 x 0.25 x 0.6 x 0.25 x 0.4 x 0.6 x 0.25 = 0.000759375
A2
Chegada
Saída
L1
L2
L1
0.4
0.6
L2
0.25 0.75
Exemplo Ilustrativo

Conclusões:

Probabilidade de PX ter sido gerado pelo Pato 3:
PX  L1, L2, L2, L2, L1, L2, L1, L1, L2, L1
0.5 x 0.5 x 0.5 x 0.6 x 0.5 x 0.6 x 0.4 x 0.5 x 0.6 = 0.0027
A3
Chegada
Saída
L1
L2
L1
0.4
0.6
L2
0.5
0.5
Comparando as probabilidades,
conclui-se que o mais provável
é que o pato desconhecido seja
o Pato 3!
Aplicações

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

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

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
 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

Extração de Informação na WEB

Monitoramento de opiniões espontâneas da
WEB

Análises qualitativas e quantitativas dos dados recolhidos

Informação estruturada de cada post, a partir de cada serviço
cadastrado.
Empresa brasileira com
3 anos de mercado.

Aplicações

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

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
 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.
Referências










Uma Abordagem de Aprendizagem Híbrida para Extração de
Informação em Textos Semi-Estruturados. Eduardo F.A. Silva,
Flávia A. Barros & Ricardo B. C. Prudêncio
http://gate.ac.uk/ie/index.html
Negócios Integrados - http://www.ni.com.br/
PT Sistemas de informação - http://www.ptsi.pt/PTSI
ATSolutions - http://www.atsolutions.com.br/
Techne - http://www.techne.com.br/
Datacraft - http://www.datacraft.com.br/
NBCI - http://www.ncbi.nlm.nih.gov/
Semiotic Systems - http://www.semiotic.com.br/
E.life - http://www.elife.com.br/