Aplicação de Aprendizagem Ativa em Tarefas de Extração de Opinião

Aplicação de Aprendizagem Ativa em Tarefas de Extração de Opinião Lucio Verdial Dissertação de Mestrado apresentada à Faculdade de Ciências da Universidade do Porto em Ciência de Computadores 2013 Aplicação de Aprendizagem Ativa em Tarefas de Extração de Opinião Lucio Verdial MSc FCUP 2013 2.º CICLO Aplicação de Aplicação de Aprendizagem Ativa em Tarefas de Extração de Opinião Lucio Verdial Mestrado em Ciência de Computadores Departamento de Ciência de Computadores 2013 Orientador Alípio Mário Guedes Jorge, Professor associado, Faculdade de Ciências da Universidade do Porto Universidade do Porto Todas as correções determinadas pelo júri, e só essas, foram efetuadas. O Presidente do Júri, Porto, ______/______/_________ Dedico `a minha fam´ılia, principalmente aos meus pais: Rogerio Verdial e Jacinta Dias e em mem´oria do meu avˆo Manuel da Costa 1 Agradecimentos Ao longo destes dois anos em que estive fora do meu pa´ıs, longe da minha fam´ılia e do meu povo timorense para estudar, enriquecer o meu conhecimento t´ecnico e pr´atico, aumentar a minha experiˆencia, apreender coisas novas, ganhar nova experiˆencia para que quando voltar o meu pa´ıs poderia contribuir para o seu desenvolvimento. Durante estes dois anos, tive oportunidade de contar com o apoio de diversas pessoas que, diretamente e indiretamente, contribu´ıram, desde que sa´ı do meu pa´ıs at´e escrever esta disserta¸c˜ao. Estou especialmente grato ao meu orientador, Prof. Al´ıpio Jorge, pela sua valiosa orienta¸c˜ao, pela paciˆencia, disponibilidade, conselho e ajuda para finalizar esta disserta¸c˜ao e terminar o meu mestrado. Um especial agradecimento ao programa de Erasmus Mundus e toda a sua estrutura, pela ajuda financeira, pela paciˆencia e disponibilidade da equipa para procurar a solu¸c˜ao sobre quais quer problemas que enfrentei durante estes dois anos. Um especial agradecimento `a Universidade do Porto, Faculdade de Ciˆencia, Departamento de Ciˆencias dos Computadores porque me deixou entrar nesta universidade. Com muito orgulho fui estudante da Universidade do Porto. Agrade¸co projeto de e-Policy (Engineering the Policy-making LIfe Cycle) [1] pela disponibiliza¸c˜ao de alguns dados e pelo enquadramento do problema. Agrade¸co tamb´em ao Pedro Coelho e Brett Drury pela disponibiliza¸c˜ao de conjunto de dados. Agrade¸co tamb´em aos meus amigos Adelaide Carvalho, Maria Pereira e Jos´e Carlos Marques, pelas suas ajudas na parte da l´ıngua portuguesa, principalmente pela paciˆencia que tiveram em corrigir o meu portuguˆes. Por fim, mas n˜ao menos importante, `a minha fam´ılia. Especialmente aos meus pais: Rogerio Verdial e Jacinta Dias, os meus irm˜aos, especialmente a minha irm˜a mais velha Ludovina Verdial e o meu tio Domingos Verdial. Pois se n˜ao fossem eles, n˜ao vinha at´e Portugal. Quero que saibam que entendo todas as dificuldades que vocˆes passaram para que eu cumprisse o meu objetivo, e agrade¸co sinceramente por toda a ajuda ao longo deste dois anos. Espero, de certo modo, recompens´a-los com o meu sucesso. Para vocˆes todos, mais uma vez o meu sincero e profundo agradecimento. Lucio Verdial 2 Resumo A quantidade da informa¸c˜ao no formato de texto na Web est´a continuamente a aumentar. Desenvolver um sistema que seja capaz de classificar automaticamente estes textos em fun¸c˜ao dos interesses dos utilizadores ´e muito desafiante. A ´area de extra¸c˜ao de conhecimento de texto (text mining) aborda o problema da classifica¸c˜ao de texto. Tipicamente, a classifica¸c˜ao de texto ´e utilizada para determinar os t´opicos dos documentos, como por exemplo, Desporto, Educa¸c˜ao ou M´usica. A extra¸c˜ao de opini˜ao (opinion mining) tem como objetivo a classifica¸c˜ao de documentos em fun¸c˜ao dos sentimentos nelas expressam. Essa an´alise ´e dificultada pela subjetividade das frases e express˜oes utilizadas. Neste problema de extra¸c˜ao de opini˜ao a classifica¸c˜ao de documentos ´e frequentemente baseada em palavras ou termos positivos ou negativos como: Bom, Mau, Melhor, Pior, Feio, Bonito, Gosta, Desgosta, etc. Esta disserta¸c˜ao foca-se na extra¸c˜ao de opini˜ao, em que se classifica os documentos como positivos ou negativos. As abordagens utilizadas nesta disserta¸c˜ao s˜ao: (i) calcular os scores dos documentos assumindo que temos uma base de dados de palavras positivas e negativas; (ii) extrair s´o as palavras positivas e negativas; (iii) procurar sin´onimos na base de dados da WordNet. Estas abordagens designam-se como t´ecnicas lingu´ısticas. Al´em das t´ecnicas lingu´ısticas, utilizam-se tamb´em v´arios modelos de representa¸c˜ao de documento na matriz de indexa¸c˜ao, nomeadamente Bin´ario, Tf (Term frequency) e Tf-Idf (Term frequency-Inverse document frequency). A utiliza¸c˜ao destas t´ecnicas relativamente superficiais tem como objetivo melhorar o resultado obtido com as t´ecnicas de extra¸c˜ao de conhecimento de texto nas tarefas de extra¸c˜ao de opini˜ao. Na aprendizagem supervisionada, precisamos de um conjunto de treino com informa¸c˜ao da vari´avel objetivo, com o tamanho suficiente para construir um modelo de classifica¸c˜ao ou regress˜ao. No nosso caso interessam-nos modelos de classifica¸c˜ao. No caso de termos exemplos n˜ao etiquetados (sem informa¸c˜ao da vari´avel objetivo) a t´ecnica de aprendizagem 3 ativa serve para selecionar automaticamente os exemplos a etiquetar que s˜ao mais favor´aveis para a constru¸c˜ao de um modelo de classifica¸c˜ao. Esta sele¸c˜ao pode ser feita iterativamente. Utilizam-se ent˜ao trˆes algoritmos de aprendizagem ativa para etiquetar os casos do conjunto de treino. Os algoritmos referidos s˜ao Confian¸ca, Distˆancia e D-confian¸ca. A utiliza¸c˜ao destes trˆes algoritmos tem como objetivo reduzir os esfor¸cos de etiquetagem por parte do utilizador, mantendo um n´ıvel razo´avel de capacidade preditiva. Na maioria dos problemas, a Confian¸ca produz melhores resultados comparando com a D-confian¸ca e a Distˆancia. Em certos problemas, como se mostra nesta disserta¸c˜ao, a Dconfian¸ca tem melhores resultados. Enquanto a Distˆancia n˜ao tem melhores resultados para nenhum dos problemas. As experiˆencias mostram que, na maioria dos conjuntos de dados podemos reduzir significativamente o n´umero de exemplos necess´arios para obter um classificador compar´avel ao que se obt´em a partir de todos os exemplos. 4 Abstract The quantity of information in text format on the Web is continuously increasing. Develop a system that is able to automatically classify these texts as a function of users’ interests is very challenging. The area of the text mining approaches a text classification. Typically, text classification is used to identify topics in documents, such as Sports, Education or Music. The aim of Opinion Mining is to classify documents according to their sentiment. The subjectivity of the phrases used makes this analysis more difficult. In Opinion Mining document classification is instead based on negative and positive words or terms such as Best, Worst, Ugly, Beautiful, Like, Dislike, etc. This thesis focuses on the opinion mining that classifies documents as positive or negative. The approaches used in this thesis are: (i) calculation of the scores of the documents assuming that we have a database of positive and negative words, (ii) extracting only the positive and negative words (iii) looking for synonyms in the WordNet database. These approaches are designated as linguistic techniques. Besides of the linguistic techniques, various models of representing document on documentterm matrix are used, including Binary, Tf (Term Frequency) and Tf-Idf (Term frequencyInverse document frequency). Using of these techniques relatively surfaces with the objective to improve the results obtained with the text mining techniques in tasks of opinion mining. In supervised learning, we need a training set with the information of target variable that is big enough to build a classification or a regression model. In our case we are interested in classification model. In the case we have unlabelled examples (without information on the target variable) active learning technique is used to automatically select the examples label that are more favourable for the construction of a classification model. This selection can be done iteratively. We use three algorithms of active learning for labelling the cases of the training set. The 5 algorithms are referred as Confidence, Distance and D-confidence. Using of these three algorithms with the objective to reduce the intensity of labelling by the user while maintaining a reasonable level of predictive capability. In most problems, the Confidence produces better results when compared to the D-confidence and the Distance. In certain problems discussed in this thesis the D-confidence has better results while the Distance does not have best results for any problems. The experiments show that in most datasets we can significantly reduce the number of samples to obtain a classifier comparable to that one obtained from the whole set of examples. 6 Cap´ıtulo 1 Introdu¸c˜ao O aproveitamento da tecnologia da Web pelas empresas para vender os seus produtos e o n´umero de pessoas que usa essa tecnologia para fazer compras online est´a a aumentar cada vez mais. Muitos produtos est˜ao a ser vendidos via Web, e cada vez mais pessoas est˜ao a fazer compras por esta via. Para perceber melhor o que o p´ublico pensa sobre um determinado bem ou servi¸co, normalmente as empresas reservam um espa¸co pr´oprio para os seus clientes efetivos e potenciais escreverem as suas opini˜oes e coment´arios. Estes coment´arios s˜ao muito importantes para as empresas, nomeadamente para a tomada de decis˜ao. Ap´os o nascimento da Web [25], as empresas e os indiv´ıduos passaram a poder colocar informa¸c˜oes na Web e assim facilmente outras entidades passaram a poder aceder-lhes. A Web permite que as empresas possam facilmente interagir com os seus clientes e vice-versa. O aumento de popularidade de informa¸c˜ao no formato texto na Web, levou ao aumento da relevˆancia da t´ecnica extra¸c˜ao de conhecimento de texto (text mining) e extra¸c˜ao de opini˜ao (opinion mining). A extra¸c˜ao de conhecimento de texto (text mining) e a extra¸c˜ao de opini˜ao (opinion mining) s˜ao t´ecnicas utilizadas atualmente para extrair informa¸c˜ao de dados com o formato de texto n˜ao estruturado. Para limitar o nosso trabalho focalizar-nos-emos mais na extra¸c˜ao de opini˜ao (opinion mining), em detrimento da extra¸c˜ao de conhecimento de texto (text mining). A extra¸c˜ao de opini˜ao ´e vulgarmente identificada como a an´alise de sentimento [25]. Trata-se do processamento de tipo de linguagem que o p´ublico utiliza ao comentar determinado bem, servi¸co ou assunto. A an´alise de sentimento implica a constru¸c˜ao de um sistema para recolher e analisar as opini˜oes sobre determinado produto que surgem nos foruns da Internet, nos grupos de discuss˜ao, blogues, etc. 13 CAP´ ITULO 1. INTRODUC¸ ˜ AO 14 Um exemplo pr´atico pode ser a decis˜ao sobre a instala¸c˜ao de uma central el´ectrica. Suponhamos que um governo quer decidir se deve instalar uma central el´etrica perto de uma cidade [1]. Necessita, obrigatoriamente, das opini˜oes, ideias e pensamentos das pessoas que moram perto dessa cidade. A maneira mais simples ´e aproveitar a vantagem da tecnologia de Web para criar um f´orum de discuss˜ao, recolher e analisar as opini˜oes antes da tomada da decis˜ao. Provavelmente, gerar-se-˜ao muitos dados e documentos o que faz com que seja dif´ıcil lidar com este problema manualmente. Haver´a necessidade de encontrar especialistas para analisarem os dados e mesmo estes demorar˜ao muito tempo a analis´a-los. A extra¸c˜ao de conhecimento de texto (text mining) serviria para resolver este problema, mais espec´ıficamente a extra¸c˜ao de opini˜ao serviria para semi-automaticamente etiquetar os coment´arios como a favor ou contra determinada ideia. At´e aqui, podemos simplesmente perceber que o problema ´e de classifica¸c˜ao de texto. A classifica¸c˜ao de texto ´e uma t´ecnica de extra¸c˜ao de conhecimento de texto (text mining) para classificar os documentos baseados nos t´opicos. No ponto de partida, os documentos n˜ao s˜ao classificados e etiquetados. Etiquetar estes documentos ´e uma tarefa muito pesada quando feita manualmente. Por esta raz˜ao surge a t´ecnica de aprendizagem ativa (active learning): estrat´egia em que o computador seleciona os exemplos para etiquetar. Nesta disserta¸c˜ao aplicamos t´ecnicas de aprendizagem ativa como Confian¸ca (Confidence), Distˆancia (Farthest first) e D-confian¸ca (D-confidence), avaliamo-los num conjunto de dados existentes e etiquetados e aplicamo-los aos conjuntos n˜ao etiquetados. O trabalho inclui a sele¸c˜ao de um classificador e um modelo adequado para representa¸c˜ao de texto, tendo em mente que este ´e um problema de extra¸c˜ao de opini˜ao. 1.1 Problemas Assumimos que podemos facilmente obter documentos sobre coment´arios de determinados assuntos de um grupo de discuss˜ao ou blogues. Portanto a ideia ´e a seguinte: precisamos de encontrar uma t´ecnica capaz de estudar estes documentos. Inicialmente propusemos a t´ecnica da aprendizagem de m´aquina (machine learning) para abordar o problema. Sabemos tamb´em que a t´ecnica de aprendizagem de m´aquina ´e uma aprendizagem supervisionada. Na aprendizagem supervisionada, temos um conjunto de treino com tamanho suficiente para construir um modelo de classifica¸c˜ao ou regress˜ao. Para construir um modelo de classifia¸c˜ao precisamos de um conjunto de treino em que os exemplos estejam etiquetados (tˆem os respetivos valores da vari´avel objetivo ou classe). No entanto, a disponibilidade de exemplos etiquetados pode ser reduzida pois o custo de especialistas humanos para fazerem essa etiquetagem ´e elevado. As t´ecnicas de aprendizagem ativa permitem selecionar criteriosamente e de forma autom´atica os exemplos a etiquetar. Assim, reduzem-se os custos CAP´ ITULO 1. INTRODUC¸ ˜ AO 15 sem prejudicar significativamente a capacidade preditiva do modelo. 1.2 Hip´oteses O nosso trabalho tem duas hip´oteses principais. A nossa hip´otese relativamente `a extra¸c˜ao de opini˜ao (opinion mining) ´e que a utiliza¸c˜ao de conhecimento lingu´ıstico relativamente superficial permite melhorar o resultado obtido com as t´ecnicas de extra¸c˜ao de conhecimento de texto nas tarefas de extra¸c˜ao de opini˜ao. A hip´otese relativamente `as t´ecnicas existentes de aprendizagen ativa ´e que estas permitem reduzir os esfor¸cos de etiquetagem por parte do utilizador, mantendo um n´ıvel razo´avel de capacidade preditiva. 1.3 A Nossa Abordagem Neste trabalho utiliz´amos t´ecnicas de extra¸c˜ao de texto aplicadas ao problema de extra¸c˜ao de opini˜ao. Para al´em dessas t´ecnicas, us´amos t´ecnicas lingu´ısticas baseadas em listas de palavras relacionadas com sentimentos e opini˜oes. Explor´amos tamb´em o recurso WordNet, em particular a utiliza¸c˜ao de sin´onimos. Em rela¸c˜ao `a aprendizagem ativa, aplic´amos a Confian¸ca, a Distˆancia e a D-confian¸ca (vejam o cap´ıtulo 3) que s˜ao os trˆes algoritmos utilizados para lidar com o problema do conjunto de treino que n˜ao est´a etiquetado, ou seja usamos estes algoritmos para preparar o conjunto de treino necess´ario ao algoritmo de aprendizagem de m´aquina (machine learning). Posteriormente, explicaremos detalhadamente cada um deste algoritmos. Em termos de metodologia de avalia¸c˜ao, us´amos valida¸c˜ao cruzada (vejam cap´ıtulo 4, subsubsec¸c˜ao 4.3.1.1) sobre 7 conjuntos de dados. O classificador base utilizado foi o Support Vector Machine (SVM) (vejam cap´ıtulo 4, sec¸c˜ao 4.1). 1.4 Estrutura da Disserta¸c˜ao Este documento encontra-se organizado de seguinte forma: come¸camos pela introdu¸c˜ao do problema no cap´ıtulo 1; os cap´ıtulos 2 e 3 descrevem o estado da arte de extra¸c˜ao de opini˜ao e t´ecnica de aprendizagem ativa; o cap´ıtulo 4 enuncia a metodologia experimental; o cap´ıtulo 5 descrevem as experiˆencias realizadas e os resultados alcan¸cados e, por fim, a conclus˜ao e trabalho futuro s˜ao discutidos no cap´ıtulo 6. Cap´ıtulo 2 Extra¸c˜ao de Opini˜ao Informa¸c˜oes digitais na forma texto n˜ao estruturado est˜ao a aumentar no ambiente da Web. Hoje em dia, muitas pessoas est˜ao interessadas em fazer pesquisas para arranjar uma maneira eficiente para transformar estas informa¸c˜oes digitais em informa¸c˜oes que sejam ´uteis para as empressas. Estas informa¸c˜oes digitais contˆem informa¸c˜ao valiosa para as empresas. As empresas, de qualquer modo, precisam destas informa¸c˜oes para tomar decis˜oes. 2.1 Extra¸c˜ao de Opini˜ao Extra¸c˜ao de opini˜ao ´e vulgarmente identificada como a an´alise de sentimento [25]. Tratase do processamento de tipo de linguagem que o p´ublico utiliza ao comentar determinado bem, servi¸co ou assunto. A an´alise de sentimento implica a constru¸c˜ao de um sistema para recolher e analisar as opini˜oes sobre determinado produto que surgem nos foruns da Internet, nos grupos de discuss˜ao, blogues, etc. Antes da Web, quando um indiv´ıduo queria comprar alguma coisa, tipicamente perguntava aos seus amigos ou familiares antes de decidir o que comprar [25]. Quando uma empresa queria recolher as opini˜oes do p´ublico sobre uma determinado assunto ou produto, lan¸cava inqu´eritos. Hoje, recorrendo-se `a Web j´a n˜ao ´e preciso fazer inqu´eritos. As pessoas emitem opini˜oes e coment´arios sobre os produtos e servi¸cos e expressam as suas ideias nos foruns da Internet, grupos de discuss˜ao e blogues criando o que coletivamente se designa por conte´udo gerado pelo utilizador (user generated content) [24]. Estes coment´arios contˆem informa¸c˜ao valiosa para as empresas. Os coment´arios na Web s˜ao apresentados normalmente sob a forma de texto n˜ao estruturado, facto que associado `a quantidade crescente desses coment´arios torna muito dif´ıcil a extra¸c˜ao de informa¸c˜ao ´util, sobretudo se for realizada manualmente por peritos humanos. 16 CAP´ ITULO 2. EXTRAC¸ ˜ AO DE OPINI ˜ AO 17 A tarefa ´e tecnicamente desafiante por causa da necessidade de processamento de linguagem natural que lhe ´e subjacente, mas tamb´em assume grande interesse pr´atico [24] por contribuir para a tomada de decis˜ao de muitos agentes econ´omicos. Por exemplo, os gestores de empresas para a defini¸c˜ao de v´arias estrat´egias necessitam de conhecer a opini˜ao dos consumidores e do p´ublico em geral sobre os seus bens ou servi¸cos e os potenciais clientes tamb´em querem saber as opini˜oes de clientes atuais antes de comprar um produto ou contratar um servi¸co. Ambos, tˆem interesse em extrair informa¸c˜ao ´util do conte´udo gerado pelo utilizador para fundamentarem as suas decis˜oes. Explorar e sumariar estes coment´arios ou opini˜oes para os converter em informa¸c˜ao ´util requer t´ecnicas e mecanismos de extra¸c˜ao de dados que permitam resolver, ainda que parcialmente, a complexidade e a grandeza dos conte´udos gerados pelos utilizadores. H´a, por conseguinte, necessidade de aperfei¸coar e automatizar as t´ecnicas existentes ou de criar outras novas para extrair dados e constitui-los em informa¸c˜ao de modo a satisfazer crit´erios de eficiˆencia de tempo e de recursos materiais e de efic´acia da sua disponibiliza¸c˜ao aos agentes econ´omicos. A extra¸c˜ao de opini˜ao ou an´alise de sentimento enquadra-se neste contexto. Liu [24] refere as seguintes trˆes tarefas principais da an´alise dos documentos que expressam opini˜oes ou sentimentos: 1. Classifica¸c˜ao do sentimento (Sentiment classification). A classifica¸c˜ao do sentimento ´e um problema de classifica¸c˜ao. Embora seja an´aloga `a classifica¸c˜ao do texto, o modelo subjacente `a classifica¸c˜ao de sentimento difere do modelo de classifica¸c˜ao de texto. O modelo de classifica¸c˜ao do texto classifica os documentos num t´opico predefinido, por exemplo, pol´ıtica, ciˆencia e desporto. Este modelo prefere as palavras dos t´opicos ou dos t´ıtulos dos documentos em detrimento das palavras de opini˜ao, por exemplo, ´otimo, excelente, terr´ıvel, mau, pior. Os documentos s˜ao classificados como positivos ou negativos. A classifica¸c˜ao incide sobre o n´ıvel mais geral, o pr´oprio documento, e n˜ao refere sequer os aspetos que as pessoas gostaram ou desgostaram. Assim por exemplo, da revis˜ao de um produto, resulta apenas a classifica¸c˜ao do documento como positivo ou negativo consoante o revisor. 2. Sumariza¸c˜ao com base nas propriedades da opini˜ao (Featured-based opinion mining and summarization). A extra¸c˜ao atua ao n´ıvel da frase para descobrir os detalhes ou propriedades dos aspetos que determinam os sentimentos positivos ou negativos relativos ao objeto em causa. O objeto pode ser um produto, um servi¸co, um indiv´ıduo ou qualquer outra entidade. Este modelo, proposto por Hu e Liu [18], formaliza mais o problema da extra¸c˜ao de opini˜ao. Identifica as partes importantes da informa¸c˜ao e descreve a estrutura do CAP´ ITULO 2. EXTRAC¸ ˜ AO DE OPINI ˜ AO 18 resultado da sumariza¸c˜ao da opini˜ao num texto n˜ao estruturado. Classificar os documentos de texto ao n´ıvel de documento ou da frase n˜ao nos diz se o autor gosta ou n˜ao gosta. Um documento positivo n˜ao significa que o autor tem opini˜ao positiva sobre todos os aspetos ou propriedades do objeto. Tamb´em um documento negativo n˜ao significa que o autor expressa uma opini˜ao negativa sobre todos os aspetos ou propriedades do objeto [26]. No documento de revis˜ao sobre um produto, o autor normalmente descreve os aspetos positivos e negativos, embora a opini˜ao geral possa ser positiva ou negativa. Para extrair detalhes dos aspetos ou das propriedades, precisamos do modelo de n´ıvel de propriedade ou feature level. Consideramos trˆes t´ecnicas importantes: •Identifica¸c˜ao das propriedades do objeto. Por exemplo, na frase ”the Picture quality of this camera is amazing”, o objeto ´e a cˆamara e a propriedade ´e a qualidade da fotografia, ”picture quality”. Em [27] a prop˜oe o modelo supervisionado de extra¸c˜ao de padr˜ao. E em [31] utiliza o modelo n˜ao supervisionado. A t´ecnica, basicamente, procura substantivos frequentes nas frases como caracter´ısticas que s˜ao geralmente utilizadas para descrever as propriedades dum objeto. •Determina¸c˜ao da orienta¸c˜ao da opini˜ao. Procura-se na frase determinar qual a opini˜ao da propriedade do objeto que pode ser positiva, negativa ou neutral. Na frase referida a opini˜ao da propriedade ”Picture quality” ´e positiva. Mais uma vez, h´a muitas t´ecnicas que podem ser utilizadas. Uma abordagem, que produziu bom resultado, baseou-se no l´exico [18]. Esta abordagem basicamente utiliza as palavras da opini˜ao na frase para determinar a orienta¸c˜ao da opini˜ao na propriedade do objeto. •Agrupamento em sin´onimos. A mesma propriedade de um objeto poderia ser expressa em diferentes palavras e frases. Esta t´ecnica agrupa estes sin´onimos. 3. Extra¸c˜ao de frases comparativas e rela¸c˜oes (Comparative sentence and relation mining). A extra¸c˜ao compara diretamente um objeto contra um ou mais objetos similares. O objetivo ´e analisar e extrair as rela¸c˜oes comparativas dentro das frases sobre determinado objeto. Por exemplo, o computador de marca x ´e melhor do que o computador de marca y. Em inglˆes, a rela¸c˜ao ´e normalmente expressa na forma comparativa ou superlativa de um adjetivo ou adv´erbio. A forma comparativa ´e utilizada para expressar a superioridade ou inferioridade de um objeto relativamente a outro - o objeto ´e mais do que ou menos do que outro objeto. A forma superlativa ´e utilizada CAP´ ITULO 2. EXTRAC¸ ˜ AO DE OPINI ˜ AO 19 para expressar se um objeto ´e melhor ou pior do que outro. Esta t´ecnica ´e melhor explicada por Jindal e Liu [19]. Jindal e Liu [19] enunciaram duas tarefas para extrair informa¸c˜oes comparativas: •”Dado um conjunto de documentos, identificar as frases comparativas que contˆem e classific´a-las em diferentes tipos ou classes”; •”Extrair rela¸c˜oes comparativas das frases identificadas. Isso envolve a extra¸c˜ao de entidades e das suas caracter´ısticas que est˜ao a ser comparadas, e palavras-chave comparativas”. A rela¸c˜ao expressa-se com:(< relationW ord >, < features >, < entityS1>, < entityS2>), Por exemplo, a frase comparativa: ”Canon’s optics is better than those of Sony and Nikon”. A rela¸c˜ao extra´ıda ´e: (better,optics,Canon,Sony, Nikon). Entre estas trˆes tarefas, destacamos a primeira porque vai ser utilizada nesta disserta¸c˜ao para fazer a experiˆencia t´ecnica com o algoritmo de classifica¸c˜ao de SVM e como t´ecnica de aprendizagem ativa ou active learning. Procuramos a seguir aprofundar a tarefa de classifica¸c˜ao de sentimento. 2.2 Classifica¸c˜ao de Sentimento Dado o conjunto de documentos D, um classificador classifica cada documento d∈Dem uma de duas classes, Positiva ou Negativa, Sim ou N˜ao, Gostam ou nao gostam [25]. Para explicar o conceito utilizamos classe Positiva e Negativa, mas no problema real podemos classificar em outras classes dependendo das suas interpretabilidades. Positiva significa que documento d expressa opini˜ao positiva. Negativa significa que documento d expressa opini˜ao negativa. Por exemplo dada um documento dos coment´arios sobre instala¸c˜ao de central el´ectrico, e o sistema classifica-o automaticamente em classes, positiva ou negativa. Existem muitas t´ecnicas de classifica¸c˜ao que utilizam as formas de aprendizagem de m´aquina para problemas de classifica¸c˜ao [30]. O desenho de algoritmos espec´ıficos para a classifica¸c˜ao de sentimento, tamb´em ´e muito utilizado sobretudo para explorar as palavras e as frases de opini˜ao juntamente com fun¸c˜oes de c´alculo de valor [36]. A classifica¸c˜ao de sentimento basicamente determina as orienta¸c˜oes semˆanticas das opini˜oes sobre o objeto em cada documento que satisfaz a assun¸c˜ao referida. CAP´ ITULO 2. EXTRAC¸ ˜ AO DE OPINI ˜ AO 20 2.2.1 Classifica¸c˜ao baseada nas frases de sentimento As frases de sentimento s˜ao as frases que descrevem os objetos. Estas frases contˆem um adjetivo ou adv´erbio, porque segundo v´arias pesquisas [15,16,38] estes dois termos s˜ao bons indicadores de subjetividade e de opini˜oes. Turney [36] desenhou um algoritmo para lidar com este problema, seguindo a ideia de se basear nas palavras positivas e negativas que existem em cada documento. Turney implementou este algoritmo para classificar a revis˜ao dos clientes. O algoritmo utiliza um processo de linguagem natural designado como part-of-speech (POS) tagging. O part-of-speech de uma palavra ´e uma estrutura lingu´ıstica que define a sintaxe e a morfologia de palavra. POS, em inglˆes, s˜ao geralmente substantivos, verbos, adjetivos, adv´erbios, pronomes, preposi¸c˜oes, conjun¸c˜oes e interjei¸c˜oes. Em [24] explica que Turney utiliza PennTreebank POS Tags padr˜oes para identificar as frases. O algoritmo do Turney consiste nos seguintes em trˆes passos: Passo 1. Extrair as frases que contˆem um adjetivo ou adv´erbio uma vez que segundo v´arias pesquisas [15,16,38] estes dois termos s˜ao bons indicadores de subjetividade e de opini˜oes. No entanto, apesar de um adjetivo isolado poder indicar subjetividade, ´e necess´ario um contexto suficiente para determinara sua orienta¸c˜ao (ou parecer) semˆantica. Por exemplo, o adjetivo ”unpredictable”pode ter uma orienta¸c˜ao negativa de uma revis˜ao automotiva, numa frase como ”unpredictable steering”, mas poderia ter uma orienta¸c˜ao positiva numa revis˜ao de um filme se surgisse numa frase como ”unpredictable plot”. Por isso, o algoritmo extrai duas palavras consecutivas, em que um membro do par ´e um adjetivo ou adv´erbio e o outro ´e uma palavra de contexto. As duas palavras consecutivas que se extraem devem seguir as regras definidas na tabela 2.1. Por exemplo, na primeira linha da tabela 2.1, a primeira palavra tem que ser um adjetivo e a segunda tem que ser um substantivo e a terceira que n˜ao se extrair´a poder´a ser uma qualquer. Tabela 2.1: Padr˜ao para extrair dois-palavras em documentos [24] Primeira Palavra Segunda Palavra Terceira Palavra (n˜ao extrair´a) JJ NN ou NNS Qualquer JJ JJ Nao NN nem NNS NN ou NNS JJ Nao NN nem NNS RB, RBS, RBR JJ Nao NN nem NNS RB, RBS,RBR VB,VBD,VBN ou VBG Qualquer Por exemplo, na frase ”this camera produces beautiful pictures”, extrai-se ”beautiful pictures”. CAP´ ITULO 2. EXTRAC¸ ˜ AO DE OPINI ˜ AO 21 Passo 2. Utiliza pointwise mutual information para calcular a semˆantica de orienta¸c˜ao. P MI(termo1, termo2) = log P r(termo1∧termo2) P r(termo1)P r(termo2) (2.1) P r(termo1∧termo2) ´e a probabilidade de ocorrerem ambos os termos, termo1 e termo2. E P r(termo1)P r(termo2) ´e a probabilidade de ocorrˆencia dos dois termos se forem estatisticamente independentes. O r´acio entre P r(termo1∧termo2) e P r(termo1)P r(termo2) ´e a medida do grau de dependˆencia estat´ıstica entre os termos. O log deste r´acio ´e a quantidade de informa¸c˜ao que se adquire sobre a presen¸ca de uma das palavras, quando observamos a outra. A orienta¸c˜ao semˆantica ou opini˜ao (SO) de uma frase ´e calculada com base na sua associa¸c˜ao com a palavra referˆencia positiva ”excelente”e sua associa¸c˜ao com a palavra referˆencia negativa ”pior”: SO(frase) = P MI(frase, ”excelente”) −P M I(frase, ”pior”) (2.2) As probabilidades s˜ao calculadas mediante as consultas efetuadas a um motor de busca e coletado n´umero de hits. Para cada consulta de pesquisa, um motor de busca geralmente d´a o n´umero de documentos relevantes para a consulta, que ´e o n´umero de hits. SO(frase) = log2hits(frase Near”excelente”) hits(”p´essimo”) hits(frase Near”p´essimo”) hits(”excelente”) (2.3) Para evitar a divis˜ao por zero, 0,01 ´e adicionado aos hits Passo 3. Dada uma revis˜ao, o algoritmo calcula a m´edia de todas as frases SO na revis˜ao, e classifica a avalia¸c˜ao como recomendado se a m´edia SO for positiva, caso contr´ario ´e n˜ao recomendado. Precisa de notar que, este experiˆencia utilizou AltaVista Advance Search Engine para calcular fun¸c˜ao Near, para mais detalha vejam [36]. 2.2.2 Usando m´etodos de classifica¸c˜ao de texto A abordagem mais simples para classifica¸c˜ao de sentimento consiste em tratar o problema como se fosse um tema de um de problema de classifica¸c˜ao de texto. Ent˜ao, pode usar-se qualquer algoritmo de classifica¸c˜ao de texto [30], por exemplo, o na¨ıve Bayesian, SVM, kNN, etc. A abordagem foi experimentada por [30], com as revis˜oes de filme de duas classes, positivos e negativos. Demonstrou-se que o uso de um unigram (um saco de palavras individuais) na classifica¸c˜ao resulta num bom desempenho, usando quer o na¨ıve Bayesian quer o SVM. CAP´ ITULO 2. EXTRAC¸ ˜ AO DE OPINI ˜ AO 22 2.2.3 Classifica¸c˜ao utilizando uma fun¸c˜ao score Dave [9], propuseram este algoritmo, consiste em dois passos: Passo 1. Calcular o score para cada termo em conjunto de treino com equa¸c˜ao: score(ti) = (P r(ti|C)−P r(ti|C0)) (P r(ti|C)−P r(ti|C0)) (2.4) Em que ti´e um termo e C ´e a classe, C0´e complemento, n˜ao C, P r(ti|C) ´e a probabilidade condicionada do termo tina classe C ´e calculada pelo contar o n´umero do termo tiocorre na classe C e o divide pelo n´umero total dos termos nas opini˜oes de classe C. o score de um termo ´e -1 ou 1. Passo 2. Para classificar o novo documento di=ti...tn, o algoritmo somando os scores de todos os termos e utilizando o total para determinar a classe. class(di) = (Ceval(d)>0 C’ caso contr´ario (2.5) Em que, eval(di) = X j score(tj) (2.6) O algoritmo foi aplicado a grandes conjuntos de dados, e os resultados de accuracy variam entre (84.6%-88.3%), sem utilizar o stemming e retirar stopwords [9]. 2.3 T´ecnicas Utilizadas Nesta Disserta¸c˜ao Pang [30] tratou o problema de extra¸c˜ao de opini˜ao com aprendizagem supervisionada ou m´etodo de Machine Learning (Aprendizagem de M´aquina) para classificar os documentos em duas classes: a classe positiva, se o documento expressa um sentimento positivo e a classe negativa se o documento expressa sentimento negativo. Na representa¸c˜ao dos documentos, Pang utilizou o framework de bag-of-word e avaliou-o com o SVM, Naive Bayes e Maximum Entropy. A nossa abordagem ´e um pouco diferente, mas baseia-se na ideia base de Pang [30]. Utiliz´amos o pr´e-processamento e represent´amos os documentos com matriz de indexa¸c˜ao de bag-of-word, mas com diferentes modelos, nomeadamente Bin´ario, Tf e Tf-Idf. Aproveit´amos a lista das palavras positivas e negativas de Liu para calcular os scores e junt´a-los `a matriz de CAP´ ITULO 3. APRENDIZAGEM ATIVA 29 n˜ao etiquetados com a previs˜ao da menor probabilidade, isto ´e a que tem mais incerteza [23]. Intuitivamente, a abordagem de confian¸ca ´e usar modelo de classifica¸c˜ao em cada itera¸c˜ao para calcular a confian¸ca posterior em cada caso etiquetado para cada caso n˜ao etiquetado, ou seja, usa os casos etiquetados na itera¸c˜ao i para treinar o classificador, hi; e depois calcular a confian¸ca para cada caso n˜ao etiquetado, ordenar o resultado de confian¸ca e selecionar o caso com menor confian¸ca para etiquetar e se juntar´a ao conjunto etiquetado. Figura 3.2: Confian¸ca Resumidamente, na figura 3.2 em cima, os passos mais importantes s˜ao 5 e 6, passo 5 ´e treinar o modelo com o conjunto Li, enquanto passo 6 para calcular a confian¸ca de cada caso n˜ao Li. Nesta fase, associamos a confian¸ca de cada classe para cada caso. O Passo 7 ´e para selecionar o caso com menor confian¸ca a ser etiquetado e juntaremos ao conjunto L. Repete o passo 3 at´e passo 9, at´e i satisfazer algum crit´erio definido pelo utilizador (crit´erio de paragem). No nosso caso, deixamos at´e etiquetar todos os casos do conjunto U. 3.3 Distˆancia (Farthest first) Trata-se de um algoritmo que ´e utilizado para calcular a aproxima¸c˜ao do problema de otimiza¸c˜ao do clustering K-Centre [17]. KFF para a aprendizagem ativa [4] consiste no seguinte: Dado o conjunto atual de L, caso etiquetado, escolhemos um caso x∈U, que esteja mais distante de L. Usa-se LS(x, y) como conjunto, para treinar o modelo do classificador. A pr´oxima consulta (query) ´e o caso mais distante do conjunto observado (mais diferente do conjunto observado). Resumidamente, na figura 3.3 em cima, come¸camos por conjunto W e L. No Passo 2 calculase a distˆancia entre todos os casos com a fun¸c˜ao de distˆancia euclidiana. Inicializa-se a itera¸c˜ao no passo 3. No Passo 4 separa-se o conjunto U do conjunto W. Passo 6 ´e treinar o modelo com o conjunto Li. Passo 7 e 8 s˜ao para selecionar o caso mais distante (mais CAP´ ITULO 3. APRENDIZAGEM ATIVA 30 Figura 3.3: Distˆancia diferente) do conjunto Li, baseando no resultado do passo 2. Repete o passo 4 at´e passo 11, at´e i satisfazer algum crit´erio definido pelo utilizador (crit´erio de paragem). No nosso caso, deixamos at´e etiquetar todos os casos do conjunto U. 3.4 D-confian¸ca (D-confidence) Escudeiro e Jorge [11] propuseram uma nova t´ecnica que designaram por D-confian¸ca. Dado o conceito alvo, um conjunto de classes e uma amostra de casos n˜ao etiquetados extra´ıda do espa¸co alvo, procura-se identificar todas classes do espa¸co alvo, efetuando poucas consultas e minimizar o erro de precis˜ao da aprendizagem. Entretando no nosso caso, n˜ao nos interessa muito a identifica¸c˜ao de classes no espa¸co alvo. O objetivo do Escudeiro e Jorge [11] ´e identificar os casos que representam todos os outros e cobrem todas as classes de modo a diminuir o n´umero de consultas ao conjunto de espa¸co alvo (working set). As consultas requerem etiquetagem para um caso espec´ıfico. Todos os modelos de aprendizagem ativa pressup˜oem que, pelo menos, no working set, cada caso tenham uma classe. Normalmente, a aprendizagem ativa depende da confian¸ca do classificador para selecionar a consulta [3] e do pressuposto que o conjunto pr´e-etiquetado cobre todas as classes etiquetadas. No entanto, a t´ecnica de D-confian¸ca [11] ´e um pouco diferente, O D-confian¸ca, pesa a confian¸ca do classificador como inverso da distˆancia entre o caso em quest˜ao e as classes j´a conhecidas, ou seja calcular o r´acio de d-confian¸ca com a confian¸ca sobre a distˆancia. A equa¸c˜ao:(3.1) ´e para calcular o r´acio de d-confian¸ca. Espera-se que este desvio favore¸ca a r´apida cobertura do espa¸co, apresentando uma tendˆencia para explorar ´areas desconhecidas. CAP´ ITULO 3. APRENDIZAGEM ATIVA 31 Como consequˆencia, a convergˆencia torna-se mais r´apida do que se utiliz´assemos apenas a confian¸ca. dConf(u) = maxkconf(uj, ck) dist(uj, ck(3.1) Em que, conf(uj, ck) ´e a confian¸ca posterior na classe ckdado caso ujna itera¸c˜ao i e dist(uj, ck) ´e a distˆancia agregada para classe conhecida, calculado por ClassDist(uj, ck) baseando na distˆancia individual entre cada par dos casos. Para mais informa¸c˜oes em baixo na figura 3.4 mostramos o algoritmo de D-confian¸ca. Figura 3.4: D-confian¸ca [11] Resumidamente, na figura 3.4, os passos basicamente s˜ao dos passos de algoritmo confian¸ca e algoritmo distˆancia. O que difere ´e no passo 9, em que calcular o r´acio de D-confian¸ca por confian¸ca sobre distˆancia, equa¸c˜ao:(3.1). Acabamos de abordar o estado de arte da aprendizagem ativa, come¸camos basicamente pela ideia geral do conceito aprendizagem ativa at´e destacamos trˆes algoritmos recentes, nomeadamente Confian¸ca (Confidence), Distˆancia (Farthest first) e D-confian¸ca (D-Confidence). Estes trˆes algoritmos ser˜ao implementados na parte pr´atica (cap´ıtulo 5). A seguir vamos falar sobre metodologia experimental, em que basicamente falamos sobre algoritmo de classifica¸c˜ao SVM, procedimento e medidas de avalia¸c˜ao. Cap´ıtulo 4 Metodologia Experimental Na parte de pr´atica, utilizamos o SVM como o nosso classificador, taxa de erro (error rate) como a nossa medida de avali¸c˜ao dos erros, valida¸c˜ao cruzada como m´etodo de avalia¸c˜ao. J´a seguir abordamos os significados de cada conceito. 4.1 M´aquinas de Vetores Suporte - SVMs A m´aquina de vetores suporte (Support Vector MachinesSVMs) foi inicialmente introduzida por Vladimir Vapnik [8]. O SVM ´e considerado o algoritmo mais usado no problema de classifica¸c˜ao [39]. O SVM superou os outros algoritmos, por exemplo, o KNN e naive Bayes no problema de classifica¸c˜ao de texto [20], Tong [34] implementou o SVM com a aprendizagem ativa (active learning) e o resultado foi melhor. Pang [30] compararam o algoritmo SVM com o Naive Bayes e o Maximum Entropy, na classifica¸c˜ao de sentimento. O SVM continuou a ser o favorito, pois, o resultado superou os dos dois outros algoritmos. SVM ´e um algoritmo de aprendizagem supervisionada em que h´a dois conjuntos de dados: o conjunto de treino e o conjunto de teste. O conjunto de treino ´e usado para treinar o modelo ou classificador e o conjunto de teste para testar o modelo. No conjunto de treino as classes s˜ao etiquetadas, ou s˜ao classes conhecidas, enquanto o conjunto de teste n˜ao precisa de classes. A ideia fundamental do SVM ´e encontrar um hiperplano que separe perfeitamente as duas classes [6] o que ´e f´acil para casos lineares, mas no caso real os problemas nem sempre est˜ao linearmente separados. Os artigos [6,21] explicam melhor o SVM no contexto matem´atico. 32 CAP´ ITULO 4. METODOLOGIA EXPERIMENTAL 33 4.1.1 SVMs lineares Neste problema a ideia ´e procurar o hiperplano que separa melhor as classes. Tipicamente h´a muitos hiperplanos, mas escolhemos aquele que tem margem m´axima, conhecido por maximum margin hyperplane. Formalmente, dado X como o conjunto de treino com n objetos xi∈Xe com as respetivas etiquetas yi∈Y, em que X ´e o conjunto de entrada e Y={−1,+1}s˜ao as poss´ıveis etiquetas (classes). X ´e linearmente separ´avel, se ´e poss´ıvel separar os objetos das classes -1 e +1 por um hiperplano [21]. O hiperplano ´e calculado por: h(x) = w.x +b(4.1) em que, w.x ´e o produto escalar entre w e x, w∈X´e o vetor normal ao hiperplano e 2 ||w|| ´e a distˆancia do hiperplano em rela¸c˜ao `a origem, com b∈R. (a) (b) Figura 4.1: (a) Ilustra¸c˜ao de hiperplano h(x), que separa linearmente as duas classes {−1,+1}, (b) O melhor hiperplano ´e aquele que tem margem m´axima e est´a representado pela linha azul. 4.1.2 SVMs n˜ao lineares Neste problema, SVM mapear o conjunto de treino do seu espa¸co original para um novo espa¸co de maior dimens˜ao (multidimensional) [21,35], depois procura-se o hiperplano, que neste novo espa¸co, capaz de separar as classes. Calcular o produto interno neste espa¸co novo ´e computacionalmente pesado, portanto, utiliza-se outra variante de kernel que em vez de calcular os produtos internos num espa¸co multidimensional, aproveita o facto de que K(x;z) = Φ(x).Φ(z), portanto simplesmente substituem-se os produtos internos por c´alculos do kernel, muito mais simples no espa¸co de entrada original (e muito menor) [35]. Um kernel ´e uma fun¸c˜ao K () tal que para todo x, z∈X CAP´ ITULO 4. METODOLOGIA EXPERIMENTAL 34 (a) (b) Figura 4.2: (a) Ilustra¸c˜ao de conjunto de dados e da fronteira de decis˜ao em duas dimens˜oes, (b) Ilustra¸c˜ao do exemplo de transforma¸c˜ao de duas dimens˜oes em trˆes dimens˜oes e fronteira de decis˜ao. K(x;z) = Φ(x).Φ(z) (4.2) Em que Φ ´e mapeamento de espa¸co original X para um espa¸co novo com tamanho multidimensional Z. Existem trˆes fun¸c˜oes de kernel mais conhecidas: Gaussian Kernel: K(Xi;Xj) = e −kxi−xjk2 2σ2!(4.3) Kernel Polinomial de grau d: K(Xi;Xj)=(Xi;Xj)d(4.4) Kernel radial: K(Xi;Xj) = e−γkXi−Xjk2(4.5) A raz˜ao que nos leva a escolher o SVM ´e muito simples, porque o SVM como um algoritmo de aprendizagem da m´aquina teve sucesso no problema de classifica¸c˜ao especialmente no problema com alta dimensionalidade, como por exemplo classifica¸c˜ao de texto [11,20,34,37]. 4.2 Medidas de Avalia¸c˜ao H´a muitas medidas de avalia¸c˜ao da classifica¸c˜ao, as mais utilizadas s˜ao nomeadamente accuracy, taxa de erro, precision erecall,F-measure [24]. No nosso caso, utilizamos a taxa de erro. CAP´ ITULO 4. METODOLOGIA EXPERIMENTAL 35 Taxa de erro ´e para medir a propor¸c˜ao do erro de previs˜ao do modelo do classificador [21,35]. Portanto, formalmente, dado conjunto de teste, obtemos a previs˜ao com o modelo de classificador, para calcular a taxa de erro (L0/1), precisamos a informa¸c˜ao das verdadeiras classes do conjunto do teste. L0/1=1 Ntest Ntest X i=1 I(ˆ h0(Xi), Yi) (4.6) Em que, I( ) ´e a fun¸c˜ao do indicador, se X=Y ent˜ao I(X,Y)=0, caso contr´ario I(X,Y)=1, ˆ h0(Xi) valor de previs˜ao do caso i, Yi´e a verdadeira classe do caso i. O valor de (L0/1) ´e variar entre 0 e 1, quanto mais pr´oximo de 0 ´e considerado melhor erro. Outra maneira de calcular o erro de classificador ´e utilizando matriz de confus˜ao [21], em que as linhas representam as classes verdadeiras e as colunas representam as classes de previs˜ao. A matriz de confus˜ao M tem dimens˜ao de k×k,k´e o n´umero classes. A diagonal desta matriz apresenta os acertos do classificador e os outros elementos s˜ao os erros cometidos pelo classificador. Portanto, para calcular o erro ´e: erro : 1 −PiMi,i Pi,j Mi,j (4.7) 4.3 Procedimento da Avalia¸c˜ao 4.3.1 Procedimento da avalia¸c˜ao da extra¸c˜ao de opini˜ao Depois de construir o modelo de classifica¸c˜ao, ´e necess´ario que avaliar o seu erro de classifica¸c˜ao. Nesta avalia¸c˜ao basicamente ´e para saber a fiabilidade do nosso modelo. Para medir estes erros ´e necess´ario que responder as seguintes perguntas: qual o parˆametro utilizado para medir o erro? -medida de avalia¸c˜ao (vejam na se¸c˜ao 4.2) e como avaliar? -m´etodo da avalia¸c˜ao 4.3.1.1 Valida¸c˜ao cruzada (Cross-validation) Existem muitos m´etodos de avalia¸c˜ao da classifica¸c˜ao, entre eles, m´etodo Hold-Out em que dividir aleatoriamente o conjunto em dois subconjuntos, 70% como conjunto de treino e 30% como conjunto de teste [21, 24]. O Hold-Out ´e normalmente utilizado no caso em que o conjunto de dados ´e razoavelmente grande. M´etodo Random Subsampling, em que aleatoriamente escolher conjunto de teste e conjunto de treino e repetir o v´arias vezes, no final calcular erro que corresponde `a m´edia dos erros em cada repeti¸c˜ao. Entretanto o mais interessante para o nosso problema e j´a usaram no CAP´ ITULO 4. METODOLOGIA EXPERIMENTAL 36 problema de classifica¸c˜ao do texto [5], aprendizagem ativa [10,12,34] e extra¸c˜ao opini˜ao [30] ´e m´etodo Cross-Validation (valida¸c˜ao Cruzada). A ideia de valida¸c˜ao Cruzada ´e similar ao Random subsampling, essencialmente consiste em k repeti¸c˜oes de algumas parte de conjunto de dados como conjunto de treino e o resto para testar [21]. Inicialmente, come¸ca por dividir conjunto de dados em k subconjunto com mesmo tamanho, para cada subconjunto utilizado como conjunto de teste e o resto de k-1 como conjunto de treino. Mais uma vez, vai produzir o k erro, o erro final ´e calculado por m´edia pesada dos k. 4.3.2 Procedimento da avalia¸c˜ao da aprendizagem ativa Para avaliar os trˆes algoritmos de aprendizagem ativa, no nosso caso, para cada AA (aprendizagem ativa) na primeira itera¸c˜ao selecionamos aleatoriamente dois casos para etiquetar manualmente e depois treinamos o classificador (o nosso caso, utilizamos SVM como o classificador). Em seguida previmos os restos dos exemplos, baseando nos resultados da previs˜ao, come¸camos por simplesmente selecionar os pr´oximos casos dependendo do crit´erio de sele¸c˜ao ou consulta de cada AA. J´a fal´amos no cap´ıtulo 3. Portanto, formalmente como explic´amos em cima, utilizamos 5f-cv (5 folds-Cross validation) (utilizamos apenas 5f-cv porque os conjuntos de dados s˜ao bastante grande, portanto seria muito lenta se utilizar mais folds) para avaliar a fiabilidade do nosso modelo. Inicialmente, dividimos aleatoriamente o conjunto de dados em 5 partes dos mesmos tamanhos. Basicamente n´os temos 5 itera¸c˜oes (5f-cv), em cada itera¸c˜ao seleciona dois casos pr´e-etiquetados (conjunto Li) para treinar o classificador, hi; e test´a-lo com o conjunto n˜ao etiquetado, Ui; depois baseando-se no m´etodo de cada aprendizagem, nomeadamente baseando-se na Confian¸ca, Distˆancia, e D-confian¸ca, seleciona dez casos para juntar com conjunto U. Guardamos sempre a taxa de erro de cada itera¸c˜ao. Portanto at´e etiquetar todos os casos n˜ao etiquetados em U, ter´ıamos n taxa de erro em que n ´e o n´umero de itera¸c˜ao. 4.4 Os passos necess´arios para cada t´ecnica utilizada nesta disserta¸c˜ao Seguidamente apresentamos a explica¸c˜ao de cada t´ecnica utilizada nesta disserta¸c˜ao: 1. Matriz de indexa¸c˜ao para representar os documentos; No nosso caso, antes de implementar a matriz de indexa¸c˜ao, fizemos os pr´e-processamentos - remover Stopwords, remover pontua¸c˜ao, Stemming, espa¸cos brancos e os Sparseterms. Passos necess´arios: •Calcular o score para cada documento; CAP´ ITULO 4. METODOLOGIA EXPERIMENTAL 37 •Implementar o pr´e-processamento e representar os documentos com matriz de indexa¸c˜ao; •Pr´e-processamento sem Sparseterms; •Pr´e-processamento com Sparseterms de 97% at´e 99%; •Implementar SVM com 5f-cv; 2. Palavras postivas e negativas (PosNeg); Nesta abordagem, aproveit´amos a lista de PosNeg de Liu e a lista das palavras de nega¸c˜ao (exemplo: don´t,not,doesn´t,didn’t ect.) para extrair os atributos interessantes nos documentos. Al´em disso, calcul´amos os scores. Utiz´amos os pr´e-processamentos como 1aabordagem. Passos necess´arios: •Calcular o score para cada documento; •Extrair os atributos interessantes baseandos na lista de Liu (positivos e negativos) e lista de nega¸c˜ao (exemplo: don´t,not,doesn´t,didn’t, ect.); •Implementar o pr´e-processamento e representar os documentos com matriz de indexa¸c˜ao; •Pr´e-processamento sem Sparseterms; •Pr´e-processamento com Sparseterms de 97% at´e 99%; •Criar novo conjunto de dados compostos por matriz de indexa¸c˜ao, score e as etiquetagens; •Implementar SVM com 5f-cv. 3. Sin´onimos das palavras positivas e negativas Nesta abordagem, aproveitamos as palavras extra´ıdas na 2aabordagem para enriquecer os atributos atrav´es da procura dos seus sin´onimos na base de dados do WordNet. Passos necess´arios: •Calcular o score para cada documento; •Extrair os atributos interessantes baseandos na lista de Liu (positivos e negativos) e lista de nega¸c˜ao (exemplo: don´t,not,doesn´t,didn’t ect.); •Enriquecer os atributos com os seus sin´onimos na base de dados do WordNet; •Implementar pr´e-processamento e representar os documentos com Tf-Idf; •Pr´e-processamento sem Sparseterms; •Pr´e-processamento com Sparseterms de 97% at´e 99%; •Criar novo conjunto de dados compostos por matriz de indexa¸c˜ao, score e as etiquetagens; CAP´ ITULO 4. METODOLOGIA EXPERIMENTAL 38 •Implementar SVM com 5f-cv. Tivemos a falar sobre o algoritmo SVM, metodologia de avalia¸c˜ao como ´e que avaliar o nosso resultado, medidas utilizadas e agora seguidamente vamos entrar na parte pr´atica, designado como experiˆencia pr´atica e resultado do cap´ıtulo 5. Resumindamente, uma parte sobre conjunto de dados utilizados, resultados dos classifica¸c˜ao de texto e resultados dos aprendizagem ativa. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 45 A figura 5.1, representa o resultado da t´ecnica de AA do conjunto de dados Movie Reviews, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 10 casos). Utilizando o modelo Tf-Idf, os passos de pr´e-processamento Termsparse (97%), Stemming eStopwords e a t´ecnica lingu´ıstica de Score. Como podemos observar na figura 5.1, pode-se concluir que o algoritmo com melhor resultado ´e o algoritmo Confian¸ca. A Confian¸ca consegue atingir 0.1052 de erro, na 84aitera¸c˜ao (por volta de 832 casos etiquetados). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.1829. 5.3.2 Airline Figura 5.2: Airline A figura 5.2, representa o resultado da t´ecnica de AA do conjunto de dados Airline Food Reviews, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 10 casos). Utilizando o modelo Tf-Idf, os passos de pr´e-processamento Termsparse (98%), Stemming eStopwords e a t´ecnica lingu´ıstica de score e palavras Positivas e Negativas. Como podemos observar na figura 5.2, o erro tende a baixar com o n´umero de itera¸c˜oes para as trˆes abordagens de AA. Neste conjunto a t´ecnica D-confian¸ca tem melhores resultados. O valor de m´ınimo de erro atingido ´e de 0.1449 (D-confian¸ca, itera¸c˜ao 74, ou seja 732 casos). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.2036. De qualquer das formas, o erro do baseline ´e atingido com 392 casos (itera¸c˜ao 40) com D-confian¸ca e Distˆancia. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 46 5.3.3 Music Figura 5.3: Music A figura 5.3, representa o resultado da t´ecnica de AA do conjunto de dados Music Reviews, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 10 casos). Utilizando o modelo Tf-Idf, os passos de pr´e-processamento Termsparse (97%), Stemming eStopwords. Como podemos observar na figura 5.3, o erro tende a baixar com o n´umero de itera¸c˜oes para as trˆes abordagens de AA, embora com oscila¸c˜oes grandes. Neste conjunto a t´ecnica Confian¸ca tem melhores resultados. O valor de m´ınimo de erro atingido ´e de 0.111 (Confian¸ca, itera¸c˜ao 129, ou seja 1282 casos). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.1538. De qualquer das formas, o erro do baseline ´e atingido com 182 casos (itera¸c˜ao 19) com Confian¸ca. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 47 5.3.4 Teacher Figura 5.4: Teacher A figura 5.4, representa o resultado da t´ecnica de AA do conjunto de dados Teacher Reviews, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 10 casos). Utilizando o modelo Tf-Idf, os passos de pr´e-processamento Termsparse (99%), Stemming eStopwords e a t´ecnica lingu´ıstica de score e palavras positivas e negativas. Neste caso tamb´em, como podemos observar na figura 5.4, o erro tende a baixar com o n´umero de itera¸c˜oes para as trˆes abordagens de AA, apesar de o fazer de forma pouco suave. Neste conjunto a t´ecnica Confian¸ca tem melhores resultados. O valor de m´ınimo de erro atingido ´e de 0.111 (Confian¸ca, itera¸c˜ao 45, ou seja 442 casos). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.1699. De qualquer das formas, o erro do baseline ´e atingido com 422 casos (itera¸c˜ao 43) com Confian¸ca. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 48 5.3.5 Post-tagati economia Figura 5.5: Post-tagati Economia A figura 5.5, representa o resultado da t´ecnica de AA do conjunto de dados Post-tagati economia, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 10 casos). Utilizando o modelo Tf-Idf, os passos de pr´e-processamento Termsparse (98%), Stemming eStopwords. Como podemos observar na figura 5.5, o erro tende a baixar com o n´umero de itera¸c˜oes para as trˆes abordagens de AA. Neste conjunto a t´ecnica Confian¸ca tem melhores resultados. O valor de m´ınimo de erro atingido ´e de 0.281 (Confian¸ca, itera¸c˜ao 42, ou seja 412 casos). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.3130. De qualquer das formas, o erro do baseline ´e atingido com 162 casos (itera¸c˜ao 17) com Confian¸ca. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 49 5.3.6 Post-tagati tecnologia Figura 5.6: Post-tagati Tecnologia A figura 5.6, representa o resultado da t´ecnica de AA do conjunto de dados Post-tagati Tecnologia, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 10 casos). Utilizando o modelo Tf-Idf, os passos de pr´e-processamento Termsparse (99%), Stemming eStopwords. Como podemos observar na figura 5.6, o erro tende a baixar com o n´umero de itera¸c˜oes para as trˆes abordagens de AA. Neste conjunto a t´ecnica Confian¸ca tem melhores resultados. O valor de m´ınimo de erro atingido ´e de 0.178 (Confian¸ca, itera¸c˜ao 28, ou seja 272 casos). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.1935. De qualquer das formas, o erro do baseline ´e atingido com 202 casos (itera¸c˜ao 21) com Confian¸ca. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 50 5.3.7 Post-tagati environment Figura 5.7: Post-tagati Environment A figura 5.7, representa o resultado da t´ecnica de AA do conjunto de dados Post-tagati Environment, o eixo X representa os erros de previs˜ao, eixo Y reprenta as itera¸c˜oes (cada itera¸c˜ao seleciona 3 casos). Utilizando o modelo Bin´ario, os passos de pr´e-processamento Termsparse (97%), Stemming eStopwords. Este conjunto de dados ´e o conjunto de dados mais pequeno dos outros. Utilizou-se o query para cada caso mas n˜ao resultou num melhor resultado, portanto optou-se por utilizar query de 3 casos. Como podemos observar na figura 5.7, a t´ecnica D-confian¸ca parace ter melhores resultados. O primeiro m´ınimo local abaixo do baseline ´e de 0.361 (D-confian¸ca, itera¸c˜ao 5, ou seja 12 casos). ` A medida que o conjunto de exemplos etiquetados cresce o erro tende para o da abordagem supervisionada (baseline): 0.4143. De qualquer das formas, o erro do baseline ´e atingido com 145 casos (itera¸c˜ao 51) com Confian¸ca. 5.3.8 Resumo do resultado de aprendizagem ativa Na maioria dos problemas, a Confian¸ca produz melhores resultados comparando com a D-confian¸ca e a Distˆancia. Em certos problemas, como se mostra nesta disserta¸c˜ao, a Dconfian¸ca tem melhores resultados. Enquanto a Distˆancia n˜ao tem melhores resultados para nenhum dos problemas. A confian¸ca tem melhores resultados em problemas: Movie,Music, Teacher,Post-tagati economia, Post-tagati tecnologia. Enquanto D-confian¸ca tem melhores resultados em problemas: Airlines ePost-tagati environment. CAP´ ITULO 5. EXPERI ˆ ENCIAS E RESULTADOS 51 Os erros de AA ultrapassam os erros de baseline (erro de t´ecnica supervisionada), significa que com AA podemos selecionar os melhores casos para conjunto de treino. Algumas experiˆencias (Movie,Airlines,Music,Teacher,Post-tagati economia e Post-tagati tecnologia) sugerem que uma boa sele¸c˜ao de exemplos pode melhorar bastante a capacidade preditiva do modelo baseline. Este resultado pode ser explorado para se obterem melhores classificadores de opini˜ao. Em particular, podemos utilizar crit´erios de paragem de active learning para decidir qual o melhor sub conjunto de exemplos a utilizar na constru¸c˜ao do classificador de opini˜ao [12]. Em conjuntos pequenos como por exemplo conjunto de Post-tagati environment, n˜ao ´e f´acil observar o efeito da sele¸c˜ao de exemplos feita pela aprendizagem ativa. De qualquer das formas, as t´ecnicas de AA s˜ao ´uteis precisamente em tarefas com um elevado n´umero de exemplos. Cap´ıtulo 6 Conclus˜ao e Trabalho Futuro 6.1 Conclus˜ao 6.1.1 Contribui¸c˜ao de trabalho A nossa principal contribui¸c˜ao foi a obten¸c˜ao de resultados experimentais a partir da aplica¸c˜ao de aprendizagem ativa a problemas de extra¸c˜ao de opini˜ao. Em particular aplic´amos a nova t´ecnica de D-confian¸ca, que j´a tinha mostrado bons resulatdos noutro tipo de problemas. Fizemos tamb´em um grande n´umero de experiˆencias em extra¸c˜ao de opini˜ao combinando a utiliza¸c˜ao de modelos vetoriais (Bin´ario, Tf e Tf-Idf) com diferentes m´etodos de pr´eprocessamento e t´ecnicas lingu´ısticas. 6.1.2 Conclus˜ao de trabalho Neste trabalho, explor´amos t´ecnicas de extra¸c˜ao de conhecimento de texto e de extra¸c˜ao de opini˜ao sobre alguns conjuntos de textos. Tamb´em obtivemos resultados experimentais com trˆes t´ecnicas de aprendizagem ativa nesses problemas de extra¸c˜ao de opini˜ao. Em rela¸c˜ao `a extra¸c˜ao de opini˜ao, os resultados variam de um pr´e-processamento para outro, mas maioriatariamente obt´em-se melhores resultados com modelo Tf-Idf. Os conjuntos de dados Movie,Airline,Music,Teacher,Post-tagati economia e Post-tagati tecnologia s˜ao aqueles que obtˆem melhores resultados com Tf-Idf, o ´unico conjunto de dados que obt´em um melhor resultado com o Bin´ario ´e o conjunto de dados Post-tagati environment. A utiliza¸c˜ao de sparseterm ´e muito importante, com esta t´ecnica, reduz-se o n´umero de atributos, o que significa a utiliza¸c˜ao de menores recursos computacionais. Em certos problemas, ao representar os documentos s´o com palavras positivas e negativas obtemos melhores resultados do que utilizando todas as palavras. ´ E o caso dos problemas Airline Food Reviews eTeacher 52 CAP´ ITULO 6. CONCLUS ˜ AO E TRABALHO FUTURO 53 Reviews. A utiliza¸c˜ao de extra¸c˜ao de sin´onimos na base de dados WordNet n˜ao melhora os resultados na maioria dos casos, embora tamb´em n˜ao piore. Entretando, relativamente `a aprendizagem ativa (AA), as experiˆencias mostram que, na maioria dos conjuntos de dados podemos reduzir significativamente o n´umero de exemplos necess´arios para obter um classificador compar´avel ao que se obt´em a partir de todos os exemplos. Os erros de AA ultrapassam os erros de baseline (erro de t´ecnica supervisionada), significa que com AA podemos selecionar os melhores casos para conjunto de treino. Algumas experiˆencias (Movie,Airlines,Music,Teacher,Post-tagati economia e Post-tagati tecnologia) sugerem que uma boa sele¸c˜ao de exemplos pode melhorar bastante a capacidade preditiva do modelo baseline. Este resultado pode ser explorado para se obterem melhores classificadores de opini˜ao. 6.2 Trabalho Futuro •Crit´erio de Paragem. Nas nossas experiˆencias vimos que a utiliza¸c˜ao de determinados exemplos pode piorar o erro dos classificadores de opini˜ao. Poderemos ent˜ao utilizar crit´erios de paragem de aprendizagem ativa para selecionar subconjuntos dos exemplos etiquetados para que se possa maximizar o desempenho preditivo dos classificadores. No nosso caso, infelizmente, n˜ao tivemos oportunidade para investigar este assunto, portanto, colocamo-lo como o trabalho a desenvolver no futuro pr´oximo. •Prot´otipo Colocamos tamb´em nos trabalhos futuros, criar um prot´otipo para classifica¸c˜ao de extra¸c˜ao de opini˜ao com a t´ecnica de aprendizagem ativa. A ideia ´e desenhar um sistema que sirva para etiquetar os documentos e classificar os documentos automaticamente. Apˆendice A Abreviaturas e Acr´onimos 5f-cv 5 folds-Cross Validation AA Aprendizagem Ativa bin Bin´ario Bow Bag of Word C Classe CiO conjunto das classes conhecidas no Li ClassDist(uj;ck) Distˆancia individual entre cada par dos casos Confi(uj, ck) As confiancas posteriores na classe ckdado caso uj d∈DSub documento de Documentos D-confianca Distancia-Confian¸ca D Documentos dist(uj;ck) A distˆancia agregada para classe conhecida DocFreq(w) O numero de documentos que contem a palavra w ePolicy Engineering the POlicy-making LIfe CYcle ET Extra¸c˜ao de Texto hiModelo de classificador na itera¸c˜ao i hits Numero de acertos I() Fun¸c˜ao de indicador i Itera¸c˜ao JJ Adjective K Numero de Classes k Numero de parti¸c˜ao de k-folds Cross Validation KFF Kernel Farthest-First KNN K-Nearest-Neighbors L Conjunto pequeno L0/1Error rate LiConjunto pequeno na itera¸c˜ao i N O numero de todos os documentos n Numero de itera¸c˜ao da avaliacao de aprendizagem ativa NN Noun, singular or mass NNS Noun, plural PMI Pointwise Mutual Information POS Part-of-speech posneg Positivo e negativo Pr(ti|C) Probabilidade condicionada do termo tina classe C qiQuery na itera¸c˜ao i RB Adverb RBR Adverb, comparative RBS Adverb, superlative SO Orienta¸c˜ao sem˜ Antica SVM Support Vector machine TermFreq(w, d) A frequˆencia de uma palavra do documento TF-IDF Term Frequencyinverse document frequency Tf Term Frequency tiUm termo U Conjunto nao etiquetado Ui Conjunto W - Conjunto Li VB Verb, base form VBD Verb, past tense VBG Verb, gerund or present participle VBN Verb, past participle w Word (palavra) W working set 54