Extração de Informação

Equipe:

Domingos Sávio

Raoni Franco

Roberto Costa

Ronaldo Marques

Revisada por Flavia Barros

Jul/2007

Roteiro

Motivação

História

Processo de Extração

Wrappers

Aplicações

Referências

Problemas

Internet Crescimento exponencial

Maior parte da informação está em forma de texto livre Documentos não estruturados ou semi-

estruturados

Migração de dados entre diferentes interfaces

Algumas questões

Como localizar informação relevante?

Como extrair a informação relevante?

Como gerar BDs ou bases de conhecimento automaticamente?

Extração de Informação pode ajudar... Trata o problema da extração de dados relevantes

a partir de uma coleção de documentos [Mus99] Blah blah blah trecho relevante blah blah blah

Extração de Informação (EI)

Os dados a serem extraídos são previamente definidos em um template (formulário)

Os dados extraídos podem ser diretamente apresentados na tela ser usados para preencher um BD ou uma BC

Sistema p/ EI

BD

Item1:Item2:Item3:Item4:Item5:

Template

BC

Extração de Informação

A base estruturada resultante pode ser usada para: Procurar ou analisar dados utilizando linguagens

de queries de BDs Mineração de Dados Geração de sumários

possivelmente em outra língua Construção de índices para a coleção de

documentos fonte

Extração de Informação

Domínio específico 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 não são considerados

Processo de Extração

Técnica pode ser aplicada a diferentes tipos de textos: Artigos de Jornais Web pages Artigos Científicos Mensagens de Newsgroup Classified ads Anotações Médicas

Exemplo: Ataque Terrorista

Exemplo: Ataque Terrorista

Exemplo: Ataque Terrorista

História da EI

Início (fim da década de 80) MUC-Message Understanding Conference

Processamento de Linguagem Natural

Década de 90… Internet

Wrappers (extratores)

EI versus outras áreas relacionadas

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• respresentação alvo

deve acomodar a complexidade da língua

• necessita reconhecer aspectos estilísticos

• EI • somente uma parte

do texto é relevante• representação alvo

rígida

• estilo e cor do texto é irrelevante

Por que EI é difícil?

Língua Natural é difícil de tratar automaticamnete é muito 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.…

Por que EI é difícil?

Língua natural é ambígua mesma sentença podendo ter significados

diferentes Sam, Frodo’s partner, a CMU student, …

Língua natural é dinâmica New words are constantly introduced into the

language: ecotourist, lol Established words gain new senses: to google, to

message

19

Subject: US-TN-SOFTWARE PROGRAMMERDate: 17 Nov 1996 17:37:29 GMTOrganization: Reference.Com Posting ServiceMessage-ID: <56nigp$mrs@bilbo.reference.com>

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 AndersonAdNET(901) 458-2888 faxkimander@memphisonline.com

Subject: US-TN-SOFTWARE PROGRAMMERDate: 17 Nov 1996 17:37:29 GMTOrganization: Reference.Com Posting ServiceMessage-ID: <56nigp$mrs@bilbo.reference.com>

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 AndersonAdNET(901) 458-2888 faxkimander@memphisonline.com

Sample Job Posting

20

Extracted Job Template

computer_science_jobid: 56nigp$mrs@bilbo.reference.comtitle: SOFTWARE PROGRAMMERsalary:company:recruiter:state: TNcity:country: USlanguage: Cplatform: PC \ DOS \ OS-2 \ UNIXapplication:area: Voice Mailreq_years_experience: 2desired_years_experience: 5req_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><br><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><p> <br>

….</td></tr></table><b class="sans">The Age of Spiritual Machines : When Computers Exceed Human Intelligence</b><br><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><p> <br>…

22

Extracted Book Template

Title: The Age of Spiritual Machines : When Computers Exceed Human IntelligenceAuthor: Ray KurzweilList-Price: $14.95Price: $11.96::

Tipos de texto

Estruturado Formato pre-definido e rígido

Não-Estruturado 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

Tipos de texto

Estruturado

Não-Estruturado

Semi-estruturado

<HTML><TITLE>Some Country Codes</TITLE><BODY> <B>Congo</B> <I>242</I><BR> <B>Egypt</B> <I>20</I><BR> <B>Spain</B> <I>34</I><BR> <B>Belize</B> <I>501</I><BR>

<HR></BODY></HTML>

• Uno 97, 4p., Ar, Dir, VE, Som,

Prata

• Gol 16V, ano 94, Ar, 2 portas, Al.

• Corsa 92, c/ 2 portas, Alarme,

Rodas

Estudantes caras-pintadas protestaram, ontem, no Centro de São Paulo exigindo o impeachment do prefeito Celso Pitta, acusado de corrupção por sua ex-mulher.

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 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

Vantagem 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 Aprender sistemas de EI a partir de um conjunto de

treinamento

Vantagens 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>

b

U_U

N_N

? / å etc.

? / å

? / å

? / next_token

? / 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 ofstates X and Y

• etc.

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 ofstates X and Y

• etc.

s<U,U> / ås<U,U> / å

s<b,U> /“U=”+ next_token

s<N,N> / ås<N,N> / ås<b,N> /“N=”+ next_token

s<U,N> /“N=”+ next_tokens<U,N> /“N=”+ next_token

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)

Wrappers - Casamento de Padrões

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

Wrappers - Classificação de textos

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

outrosempresaoutrosnomecargoenderecoenderecotelefonetelefone

Wrappers - Modelos de Markov Escondidos (HMM) Um HMM é um autômato finito probabilístico que

consiste em: (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.

Processo de classificação Retorna a seqüência de estados ocultos com maior

probabilidade de ter emitido cada seqüência de símbolos de entrada.

Wrappers - Modelos de Markov Escondidos (HMM)

Vantagem 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:

1 2

3

y1 y2 y3 y4 y1 y2 y3 y4

y1 y2 y3 y4

a12

a13

a21

a23

a31 a23

a11 a22

a33

b11

b31

b21

b32

b12 b22

b33

b13 b23b14 b24

b34

O número de estados não-visíveis. A matriz de transição de estados.

O número de observações ou estados visíveis.

A matriz de probabilidade de emissão de estados visíveis.

Exemplo Ilustrativo

1 2 3

Lago L1

Lago L2

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

PX L1, L2, L2, L2, L1, L2, L1, L1, L2, L1

Deseja-seidentificar este

pato!!

Exemplo Ilustrativo

P1 L1, L2, L2, L1, L1, L1, L2, L2, L2, L2

4 transições que saem de L1

2 transições vão para L1

2 transições vão para L2

A1 Chegada

Saída

L1 L2

L1 0.5 0.5

L2

Assume-se que a probabilidade dese visitar um lago depende de quelago foi visitado no dia anterior,caracterizando uma Cadeia de Markov.

Exemplo Ilustrativo

P1 L1, L2, L2, L1, L1, L1, L2, L2, L2, L2

A1 Chegada

Sa

ída

L1 L2

L1 0.5 0.5

L2

5 transições que saem de L2

1 transição vai para L1

4 transições vão para L2

Assume-se que a probabilidade dese visitar um lago depende de quelago foi visitado no dia anterior,caracterizando uma Cadeia de Markov.

Exemplo Ilustrativo

P1 L1, L2, L2, L1, L1, L1, L2, L2, L2, L2

A1 Chegada

Sa

ída

L1 L2

L1 0.5 0.5

L2 0.2 0.8

5 transições que saem de L2

1 transição vai para L1

4 transições vão para L2

Assume-se que a probabilidade dese visitar um lago depende de quelago foi visitado no dia anterior,caracterizando uma Cadeia de Markov.

Exemplo Ilustrativo

0.80.2L2

0.50.5L1

L2L1Saída

ChegadaA1

0.70.2L2

0.60.4L1

L2L1Saída

ChegadaA2

0.50.5L2

0.60.4L1

L2L1Saída

ChegadaA3

Exemplo Ilustrativo

Conclusões: Probabilidade de PX ter sido gerado pelo Pato 1:

PX L1, L2, L2, L2, L1, L2, L1, L1, L2, L1

A1 Chegada

Saída

L1 L2

L1 0.5 0.5

L2 0.2 0.8

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

Exemplo Ilustrativo

Conclusões: Probabilidade de PX ter sido gerado pelo Pato 2:

PX L1, L2, L2, L2, L1, L2, L1, L1, L2, L1

A2 Chegada

Saída

L1 L2

L1 0.4 0.6

L2 0.25 0.75

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

Exemplo Ilustrativo

Conclusões: Probabilidade de PX ter sido gerado pelo Pato 3:

PX L1, L2, L2, L2, L1, L2, L1, L1, L2, L1

A3 Chegada

Saída

L1 L2

L1 0.4 0.6

L2 0.5 0.5

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

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 EstruturalAná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õesQualidade do Código

Empresa de Curitiba, oferece sistemas de análise do código fonteem diversas linguagens.

Aplicações

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.

Extração de Informação na WEBMonitoramento da WEB

Busca por HackersBusca por Terroristas

Empresa mundialmente reconhecida, presente no Brasil há 10 anos,

oferecendo soluções nas áreas de segurança web e redes.

Aplicações

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.

Extração de Informações Estratégicas Business Intelligence

Análise de MercadoMelhoria 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, localizadonos Estados Unidos. É a principal fonte de informações sobre Genômicana Internet.

Aplicações

Extração de Informações EstratégicasAnálises de Arquivos de LOG

Logs de ErroLogs 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

Extração de Informações Estratégicas Análises de Imagens

GeologiaClimatologiaAstrologia

Empresa brasileira com 10 anos de mercado, oferece soluções paraanálise e classificação de imagens.

Aplicações de RI

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/