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