André Ricardo – arslDanilo Veras – dlvLeila Soriano – lsstaLuis Otávio – locb

Motivação

Onde tudo começou

Processo de Extração

Wrappers

Aplicações

Referências

O que é informação? Bem dinâmico com valor associado

Curiosidade, busca por informação, busca por conhecimento O diferencial do ser humano

Consultar um dos pilares da gestão de conhecimento

Busca por informação como necessidade empresarial

Aspecto chave das empresas mecanismos para facilitar busca de

informação

Acesso eficiente às informações maior produtividade e novas oportunidades

A Internet Gigantesca base de documentos em

crescimento acelerado

Como obter informações relevantes em bases textuais? Extração de informação

MUC - Message Understanding Conference Abordagem de EI utilizando processamento

de linguagem natural Simulação de um analista do serviço de

inteligência procurando informações a respeito de um tópico particular

Aplicações: MUC-1 (1987), MUC-2 (1989): Naval

operations messages. MUC-3 (1991), MUC-4 (1992): Terrorism in

Latin American countries. MUC-5 (1993): Joint ventures and

microelectronics domain. MUC-6 (1995): News articles on

management changes. MUC-7 (1998): Satellite launch reports.

Extrair, de documentos textuais, apenas os dados relevantes ao usuário Utilização de um template

Sistema de EI

BD

Item1:Item2:Item3:Item4:Item5:

Template

BC

Documento

Pode ser dividido em 5 tarefas: Segmentação Classificação Associação Normalização Deduplicação

Processo de segmentar o texto de entrada em tokens cada token (segmento) deve corresponder

a um campo do template de saída i.e., cada token deve preencher um campo

do template

Determina qual campo do template de saída corresponde a cada segmento do texto de entrada A relação deve ser de um para um

É importante salientar que os processos de segmentação e classificação, em geral, acontecem simultaneamente

Determina quais segmentos (tokens) estão relacionados a um mesmo fato

Supondo um texto que descreva vários cursos universitários Um mesmo curso pode ser descrito por mais de um

parágrafo

A extração precisa determinar quais segmentos de quais parágrafos se referem ao mesmo curso

Permite que as informações sejam armazenadas segundo um padrão pré-estabelecido

O horário de um curso pode ser representado como 2pm-4pm ou como 4-6pm, por exemplo Neste caso, o processo de normalização poderia

transformar os dois formatos para 14h00-16h00 e 16h00-18h00, respectivamente

Elimina informações redundantes do banco de dados com os templates de saída

Um curso pode ser ministrado em mais um departamento e, por isso, ter sua descrição em mais de uma página web Sem o processo de deduplicação, o banco

terá informações redundantes

Recuperação de Informação Estuda formas de armazenar e recuperar

documentos de forma rápida e automática

Extração de Informação Objetiva obter informações específicas a

partir de um documento

EI e RI são tecnologias complementares

Recuperação de Informação: Entrega documentos para o usuário

Extração de Informação: Entrega fatos para o usuário/aplicações

Linguagem Natural é difícil de tratar automaticamente...

Flexível▪ 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.

Ambígua▪ Sam, Frodo’s partner, a CMU student, …

Dinâmica▪ Novas palavras: ecotourist, lol▪ Novos significados: to google, to message

Grande influência do tipo de texto: Estruturados Semi-estruturados Livres

Baseados em PLN

Wrappers Manual Automático

Sistemas baseados em PLN são 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.

Semantic word categories ▪ KILL: kill, murder, assassinate, strangle,

suffocate

Baseada em engenharia do conhecimento Construção de regras de extração Padrões de extração descobertos por investigação e

exame do corpus de treinamento

Vantagens Boa performance dos sistemas

Desvantagens Processo de desenvolvimento trabalhoso Escalabilidade Necessidade de um especialista

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

Autômatos Finitos Pattern matching Classificação de Textos Modelos de Markov Escondidos (HMM)

Definidos por: (1) estados que “aceitam” os símbolos do texto que

preenchem algum campo do formulário de saída;(2) estados que apenas consomem os símbolos

irrelevantes encontrados no texto;(3) símbolos que provocam as transições de estado.

Textos estruturados e semi-estruturados Delimitadores, ordem dos elementos

Algoritmos específicos para EI WIEN, SoftMealy, STALKER

<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

Utiliza expressões regulares que “casam” com o texto para extrair as informações

Textos livres, estruturados e semi Delimitadores, padrões regulares

▪ Ex. data, CEP

Algoritmos específicos para EI WHISK, Rapier

Tarefa de EI -> tarefa de classificação

Textos semi-estruturados

Classificadores Convencionais: KNN, Naive Bayes, Redes

Bayesianas Específicos: SRV

Vantagens Podem utilizar várias características de cada

fragmento▪ Ex. tamanho, posição, formatação, presença de

palavras

Desvantagens Classificação local

Classificam seqüências de padrões Classes representadas pelos estados do HMM Retorna a seqüência de estados com maior

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

Textos livres e semi-estruturados

autor

veículo

S0

título

data

0,2

0,8

0,2

0,50,5

0,50,5

0,5

0,5

0,5

0,1

0,5

0,2

HMM

outros

1 2 3

Site L1

Site 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

usuário!!

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

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

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 de se visitar um site depende de que site foi visitado no dia anterior, caracterizando uma Cadeia de Markov.

A1 Chegada

Saída

L1 L2

L1 0.5 0.5

L2 0.2 0.8

A2 Chegada

Saída

L1 L2

L1 0.4 0.6

L2 0.25 0.75

A3 Chegada

Saída

L1 L2

L1 0.4 0.6

L2 0.5 0.5

Vantagens Realizam uma classificação ótima para a

seqüência completa de entrada

Desvantagens Limitação: utilizam apenas um atributo por

padrão a ser classificado

Baseada em uma técnica de Spell-Checker Quebra os tokens em n-gramas (n=3)

▪ Ex. “cavalo” -> “cav”, “ava”, “val”, “alo”

Conjunto de treinamento▪ tokens com a classe correspondente▪ Persiste o treinamento

Classifica exemplos de entrada através de uma distribuição de probabilidade

Extração de Informação em BD Query Manager (QM)

▪ Ferramenta Web▪ Agiliza consulta e EI dos BD’s de empresas▪ Facilita construção de relatórios

Localizada no RJ, é especializada em soluções e-learning.

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.

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

Extração de Informação na WEB Monitoramento de opiniões espontâneas na 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:

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.

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.

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, oferecesoluções para a análise de logs de erro e acesso a bancos de dados.

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

▪ Geologia▪ Climatologia▪ Astrologia

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

Revista Espaço Acadêmico - http://www.espacoacademico.com.br/059/59silvafilho.htm

Wikipedia - http://www.wikipedia.org 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 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