André Ricardo – arsl Danilo Veras – dlv Leila Soriano – lssta Luis 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 Gestão Portal de Informações Consciência Conhecimento Informação Dados 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 Template Documento Sistema de EI Item1: Item2: Item3: Item4: Item5: BD BC 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 CCT EI Entendimento do Somente uma parte do texto inteiro Representação alvo complexa Necessita reconhecer aspectos estilísticos texto é relevante Representação alvo rígida Estilo e cor do texto é irrelevante 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> ? / 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. 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. 0,5 título 0,2 S veículo 0,5 0,5 0 0,5 0,5 0,5 0,8 autor 0,2 0,2 0,5 0,5 outros data 0,1 HMM Textos livres e semi-estruturados Site L1 1 2 Site L2 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 usuário!! PX L1, L2, L2, L2, L1, L2, L1, L1, L2, L1 P1 L1, L2, L2, L1, L1, L1, L2, L2, L2, L2 4 transições que saem de L1 A1 Chegada Saída L1 L2 L1 L2 0.5 0.5 2 transições vão para L 2 transições vão para L 1 2 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 5 transições que saem de L2 A1 Chegada Saída L1 L2 L1 0.5 0.5 L2 0.2 0.8 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 A2 L1 0.5 0.5 L2 0.2 0.8 A3 L1 L2 L1 0.4 0.6 L2 0.25 0.75 Saída L2 Saída Saída L1 Chegada Chegada 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 SpellChecker 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, oferece soluçõ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 para aná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