A anotac~ao de papeis sem^anticos (APS) e uma tarefa do processamento de lngua natural (PLN) que permite analisar parte do signicado das sentencas atraves da detecc~ao dos participantes dos eventos (e dos eventos em si) que est~ao sendo descritos nelas, o que e essencial para que os computadores possam usar efetivamente a informac~ao codicada no texto. A maior parte das pesquisas desenvolvidas em APS tem sido feita para textos em ingl^es, considerando as particularidades gramaticais e sem^anticas dessa lngua, o que impede que essas ferramentas e resultados sejam diretamente transportaveis para outras lnguas como o portugu^es. A maioria dos sistemas de APS atuais emprega metodos de aprendizado de maquina supervisionado e, portanto, precisa de um corpus grande de senten cas anotadas com papeis sem^anticos para aprender corretamente a tarefa. No caso do portugu^es do Brasil, um recurso lexical que prov^e este tipo de informac~ao foi recentemente disponibilizado: o PropBank.Br. Contudo, em comparac~ao com os corpora para outras lnguas como o ingl^es, o corpus fornecido por este projeto e pequeno e, portanto, n~ao permitiria que um classicador treinado supervisionadamente realizasse a tarefa de anotac~ao com alto desempenho. Para tratar esta diculdade, neste trabalho emprega-se uma abordagem semissupervisionada capaz de extrair informac~ao relevante tanto dos dados anotados disponveis como de dados n~ao anotados, tornando-a menos dependente do corpus de treinamento. Implementa-se o algoritmo self-training com modelos de regress~ ao logstica (ou maxima entropia) como classicador base, para anotar o corpus Bosque (a sec~ao correspondente ao CETENFolha) da Floresta Sinta(c)tica com as etiquetas do PropBank.Br. Ao algoritmo original se incorpora balanceamento e medidas de similaridade entre os argumentos de um verbo especco para melhorar o desempenho na tarefa de classicac~ao de argumentos. Usando um benchmark de avaliac~ao implementado neste trabalho, a abordagem semissupervisonada proposta obteve um desempenho estatisticamente comparavel ao de um classicador treinado supervisionadamente com uma maior quantidade de dados anotados (80,5 vs. 82,3 de \'F IND. 1\', p > 0, 01) / Semantic role labeling (SRL) is a natural language processing (NLP) task able to analyze part of the meaning of sentences through the detection of the events they describe and the participants involved, which is essential for computers to eectively understand the information coded in text. Most of the research carried out in SRL has been done for texts in English, considering the grammatical and semantic particularities of that language, which prevents those tools and results to be directly transported to other languages such as Portuguese. Most current SRL systems use supervised machine learning methods and require a big corpus of sentences annotated with semantic roles in order to learn how to perform the task properly. For Brazilian Portuguese, a lexical resource that provides this type of information has recently become available: PropBank.Br. However, in comparison with corpora for other languages such as English, the corpus provided by that project is small and it wouldn\'t allow a supervised classier to perform the labeling task with good performance. To deal with this problem, in this dissertation we use a semi-supervised approach capable of extracting relevant information both from annotated and non-annotated data available, making it less dependent on the training corpus. We implemented the self-training algorithm with logistic regression (or maximum entropy) models as base classier to label the corpus Bosque (section CETENFolha) from the Floresta Sintá(c)tica with the PropBank.Br semantic role tags. To the original algorithm, we incorporated balancing and similarity measures between verb-specic arguments so as to improve the performance of the system in the argument classication task. Using an evaluation benchmark implemented in this research project, the proposed semi-supervised approach has a statistical comparable performance as the one of a supervised classier trained with more annotated data (80,5 vs. 82,3 de \'F IND. 1\', p > 0, 01).

A tarefa de classificação em Aprendizado de Máquina consiste da criação de modelos computacionais capazes de identificar automaticamente a classe de objetos pertencentes a um domínio pré-definido a partir de um conjunto de exemplos cuja classe é conhecida. Existem alguns cenários de classificação nos quais cada objeto pode estar associado não somente a uma classe, mas a várias classes ao mesmo tempo. Adicionalmente, nesses cenários denominados multirrótulo, as classes podem ser organizadas em uma taxonomia que representa as relações de generalização e especialização entre as diferentes classes, definindo uma hierarquia de classes, o que torna a tarefa de classificação ainda mais específica, denominada classificação hierárquica. Os métodos utilizados para a construção desses modelos de classificação são complexos e dependem fortemente da disponibilidade de uma quantidade expressiva de exemplos previamente classificados. Entretanto, para muitas aplicações é difícil encontrar um número significativo desses exemplos. Além disso, com poucos exemplos, os algoritmos de aprendizado supervisionado não são capazes de construir modelos de classificação eficazes. Nesses casos, é possível utilizar métodos de aprendizado semissupervisionado, cujo objetivo é aprender as classes do domínio utilizando poucos exemplos conhecidos conjuntamente com um número considerável de exemplos sem a classe especificada. Neste trabalho são propostos, entre outros, métodos que fazem uso do aprendizado semissupervisionado baseado em desacordo coperspectiva, tanto para a tarefa de classificação multirrótulo plana quanto para a tarefa de classificação hierárquica. São propostos, também, outros métodos que utilizam o aprendizado ativo com intuito de melhorar a performance de algoritmos de classificação semissupervisionada. Além disso, são propostos dois métodos para avaliação de algoritmos multirrótulo e hierárquico, os quais definem estratégias para identificação dos multirrótulos majoritários, que são utilizados para calcular os valores baseline das medidas de avaliação. Foi desenvolvido um framework para realizar a avaliação experimental da classificação hierárquica, no qual foram implementados os métodos propostos e um módulo completo para realizar a avaliação experimental de algoritmos hierárquicos. Os métodos propostos foram avaliados e comparados empiricamente, considerando conjuntos de dados de diversos domínios. A partir da análise dos resultados observa-se que os métodos baseados em desacordo não são eficazes para tarefas de classificação complexas como multirrótulo e hierárquica. Também é observado que o problema central de degradação do modelo dos algoritmos semissupervisionados agrava-se nos casos de classificação multirrótulo e hierárquica, pois, nesses casos, há um incremento nos fatores responsáveis pela degradação nos modelos construídos utilizando aprendizado semissupervisionado baseado em desacordo coperspectiva / In machine learning, the task of classification consists on creating computational models that are able to automatically identify the class of objects belonging to a predefined domain from a set of examples whose class is known a priori. There are some classification scenarios in which each object can be associated to more than one class at the same time. Moreover, in such multilabeled scenarios, classes can be organized in a taxonomy that represents the generalization and specialization relationships among the different classes, which defines a class hierarchy, making the classification task, known as hierarchical classification, even more specific. The methods used to build such classification models are complex and highly dependent on the availability of an expressive quantity of previously classified examples. However, for a large number of applications, it is difficult to find a significant number of such examples. Moreover, when few examples are available, supervised learning algorithms are not able to build efficient classification models. In such situations it is possible to use semi-supervised learning, whose aim is to learn the classes of the domain using a few classified examples in conjunction to a considerable number of examples with no specified class. In this work, we propose methods that use the co-perspective disagreement based learning approach for both, the flat multilabel classification and the hierarchical classification tasks, among others. We also propose other methods that use active learning, aiming at improving the performance of semi-supervised learning algorithms. Additionally, two methods for the evaluation of multilabel and hierarchical learning algorithms are proposed. These methods define strategies for the identification of the majority multilabels, which are used to estimate the baseline evaluation measures. A framework for the experimental evaluation of the hierarchical classification was developed. This framework includes the implementations of the proposed methods as well as a complete module for the experimental evaluation of the hierarchical algorithms. The proposed methods were empirically evaluated considering datasets from various domains. From the analysis of the results, it can be observed that the methods based on co-perspective disagreement are not effective for complex classification tasks, such as the multilabel and hierarchical classification. It can also be observed that the main degradation problem of the models of the semi-supervised algorithms worsens for the multilabel and hierarchical classification due to the fact that, for these cases, there is an increase in the causes of the degradation of the models built using semi-supervised learning based on co-perspective disagreement

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-02-20T21:14:32Z No. of bitstreams: 1 MateusSilverioDeAssis_DISSERT.pdf: 3929319 bytes, checksum: 7463541e5cc8c5aebedc5bd30d218bd4 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-02-23T20:13:22Z (GMT) No. of bitstreams: 1 MateusSilverioDeAssis_DISSERT.pdf: 3929319 bytes, checksum: 7463541e5cc8c5aebedc5bd30d218bd4 (MD5) / Made available in DSpace on 2017-02-23T20:13:22Z (GMT). No. of bitstreams: 1 MateusSilverioDeAssis_DISSERT.pdf: 3929319 bytes, checksum: 7463541e5cc8c5aebedc5bd30d218bd4 (MD5) Previous issue date: 2016-08-19 / Ao longo dos ?ltimos anos, as t?cnicas computacionais aplicadas ao aprendizado de m?quina t?m sido divididas ou categorizadas quanto ao grau de supervis?o presente nos conjuntos de treinamentos e quanto ao n?mero de r?tulos presente no atributo classe. Dentro dessas divis?es, encontramos o aprendizado semissupervisionado, t?cnica que trabalha muito bem quando nem todos os r?tulos dos exemplos do conjunto de treinamento s?o conhecidos. Por outro lado, a classifica??o multirr?tulo, tamb?m est? presente nessas categorias e prop?e classificar exemplos quando estes est?o associados a um ou mais r?tulos. A combina??o dessas t?cnicas de aprendizado gera a classifica??o multirr?tulo semissupervisionado. Ainda nesse contexto, existem vertentes que trabalham com o aprendizado semissupervisionado para dados de vis?o ?nica e aprendizado semissupervisionado para dados de vis?o m?ltipla. Os algoritmos de aprendizado semissupervisionado para dados de vis?o m?ltipla tem como ideia b?sica a explora??o da discord?ncia entre as predi??es dos diferentes classificadores, sendo este um assunto pouco abordado em pesquisas. Nesse sentido, esse trabalho prop?e novos m?todos para classifica??o multirr?tulo semissupervisionado em uma abordagem para dados de vis?o m?ltipla, mostra os resultados de alguns experimentos realizados com esses novos m?todos e compara alguns desses resultados com resultados de experimentos utilizando m?todos j? existentes. / In the the last years, the computational techniques used for machine learning have been divided or categorized according to the degree of supervision that exists in these training?s set and according on the number of labels in this class attribute. Within these divisions, we find the semi-supervised learning, a technique that works well when nor all labels examples of the training set are known. In the other hand, the multi-label classification also is present in these categories and it proposes to classify examples when they are associated with one or more labels. The combination of these learning techniques generates the classification semi-supervised multi-label. Also in this context, there are sides that work with the semi-supervised learning for single vision and semisupervised learning data for multiple viewing data. The semi-supervised learning algorithms for multiple viewing data has the basic idea of the exploitation of disagreements between the predictions of different classifiers, which is a subject rarely addressed in research. Thus, this work proposes the use of semi-supervised learning for multi-label classification using an approach with multiple viewing data, showing the results of some experiments and comparing some results of experiments using the new methods with the results of experiments using existing methods.

A tarefa de classificação em Aprendizado de Máquina consiste da criação de modelos computacionais capazes de identificar automaticamente a classe de objetos pertencentes a um domínio pré-definido a partir de um conjunto de exemplos cuja classe é conhecida. Existem alguns cenários de classificação nos quais cada objeto pode estar associado não somente a uma classe, mas a várias classes ao mesmo tempo. Adicionalmente, nesses cenários denominados multirrótulo, as classes podem ser organizadas em uma taxonomia que representa as relações de generalização e especialização entre as diferentes classes, definindo uma hierarquia de classes, o que torna a tarefa de classificação ainda mais específica, denominada classificação hierárquica. Os métodos utilizados para a construção desses modelos de classificação são complexos e dependem fortemente da disponibilidade de uma quantidade expressiva de exemplos previamente classificados. Entretanto, para muitas aplicações é difícil encontrar um número significativo desses exemplos. Além disso, com poucos exemplos, os algoritmos de aprendizado supervisionado não são capazes de construir modelos de classificação eficazes. Nesses casos, é possível utilizar métodos de aprendizado semissupervisionado, cujo objetivo é aprender as classes do domínio utilizando poucos exemplos conhecidos conjuntamente com um número considerável de exemplos sem a classe especificada. Neste trabalho são propostos, entre outros, métodos que fazem uso do aprendizado semissupervisionado baseado em desacordo coperspectiva, tanto para a tarefa de classificação multirrótulo plana quanto para a tarefa de classificação hierárquica. São propostos, também, outros métodos que utilizam o aprendizado ativo com intuito de melhorar a performance de algoritmos de classificação semissupervisionada. Além disso, são propostos dois métodos para avaliação de algoritmos multirrótulo e hierárquico, os quais definem estratégias para identificação dos multirrótulos majoritários, que são utilizados para calcular os valores baseline das medidas de avaliação. Foi desenvolvido um framework para realizar a avaliação experimental da classificação hierárquica, no qual foram implementados os métodos propostos e um módulo completo para realizar a avaliação experimental de algoritmos hierárquicos. Os métodos propostos foram avaliados e comparados empiricamente, considerando conjuntos de dados de diversos domínios. A partir da análise dos resultados observa-se que os métodos baseados em desacordo não são eficazes para tarefas de classificação complexas como multirrótulo e hierárquica. Também é observado que o problema central de degradação do modelo dos algoritmos semissupervisionados agrava-se nos casos de classificação multirrótulo e hierárquica, pois, nesses casos, há um incremento nos fatores responsáveis pela degradação nos modelos construídos utilizando aprendizado semissupervisionado baseado em desacordo coperspectiva / In machine learning, the task of classification consists on creating computational models that are able to automatically identify the class of objects belonging to a predefined domain from a set of examples whose class is known a priori. There are some classification scenarios in which each object can be associated to more than one class at the same time. Moreover, in such multilabeled scenarios, classes can be organized in a taxonomy that represents the generalization and specialization relationships among the different classes, which defines a class hierarchy, making the classification task, known as hierarchical classification, even more specific. The methods used to build such classification models are complex and highly dependent on the availability of an expressive quantity of previously classified examples. However, for a large number of applications, it is difficult to find a significant number of such examples. Moreover, when few examples are available, supervised learning algorithms are not able to build efficient classification models. In such situations it is possible to use semi-supervised learning, whose aim is to learn the classes of the domain using a few classified examples in conjunction to a considerable number of examples with no specified class. In this work, we propose methods that use the co-perspective disagreement based learning approach for both, the flat multilabel classification and the hierarchical classification tasks, among others. We also propose other methods that use active learning, aiming at improving the performance of semi-supervised learning algorithms. Additionally, two methods for the evaluation of multilabel and hierarchical learning algorithms are proposed. These methods define strategies for the identification of the majority multilabels, which are used to estimate the baseline evaluation measures. A framework for the experimental evaluation of the hierarchical classification was developed. This framework includes the implementations of the proposed methods as well as a complete module for the experimental evaluation of the hierarchical algorithms. The proposed methods were empirically evaluated considering datasets from various domains. From the analysis of the results, it can be observed that the methods based on co-perspective disagreement are not effective for complex classification tasks, such as the multilabel and hierarchical classification. It can also be observed that the main degradation problem of the models of the semi-supervised algorithms worsens for the multilabel and hierarchical classification due to the fact that, for these cases, there is an increase in the causes of the degradation of the models built using semi-supervised learning based on co-perspective disagreement

A anotac~ao de papeis sem^anticos (APS) e uma tarefa do processamento de lngua natural (PLN) que permite analisar parte do signicado das sentencas atraves da detecc~ao dos participantes dos eventos (e dos eventos em si) que est~ao sendo descritos nelas, o que e essencial para que os computadores possam usar efetivamente a informac~ao codicada no texto. A maior parte das pesquisas desenvolvidas em APS tem sido feita para textos em ingl^es, considerando as particularidades gramaticais e sem^anticas dessa lngua, o que impede que essas ferramentas e resultados sejam diretamente transportaveis para outras lnguas como o portugu^es. A maioria dos sistemas de APS atuais emprega metodos de aprendizado de maquina supervisionado e, portanto, precisa de um corpus grande de senten cas anotadas com papeis sem^anticos para aprender corretamente a tarefa. No caso do portugu^es do Brasil, um recurso lexical que prov^e este tipo de informac~ao foi recentemente disponibilizado: o PropBank.Br. Contudo, em comparac~ao com os corpora para outras lnguas como o ingl^es, o corpus fornecido por este projeto e pequeno e, portanto, n~ao permitiria que um classicador treinado supervisionadamente realizasse a tarefa de anotac~ao com alto desempenho. Para tratar esta diculdade, neste trabalho emprega-se uma abordagem semissupervisionada capaz de extrair informac~ao relevante tanto dos dados anotados disponveis como de dados n~ao anotados, tornando-a menos dependente do corpus de treinamento. Implementa-se o algoritmo self-training com modelos de regress~ ao logstica (ou maxima entropia) como classicador base, para anotar o corpus Bosque (a sec~ao correspondente ao CETENFolha) da Floresta Sinta(c)tica com as etiquetas do PropBank.Br. Ao algoritmo original se incorpora balanceamento e medidas de similaridade entre os argumentos de um verbo especco para melhorar o desempenho na tarefa de classicac~ao de argumentos. Usando um benchmark de avaliac~ao implementado neste trabalho, a abordagem semissupervisonada proposta obteve um desempenho estatisticamente comparavel ao de um classicador treinado supervisionadamente com uma maior quantidade de dados anotados (80,5 vs. 82,3 de \'F IND. 1\', p > 0, 01) / Semantic role labeling (SRL) is a natural language processing (NLP) task able to analyze part of the meaning of sentences through the detection of the events they describe and the participants involved, which is essential for computers to eectively understand the information coded in text. Most of the research carried out in SRL has been done for texts in English, considering the grammatical and semantic particularities of that language, which prevents those tools and results to be directly transported to other languages such as Portuguese. Most current SRL systems use supervised machine learning methods and require a big corpus of sentences annotated with semantic roles in order to learn how to perform the task properly. For Brazilian Portuguese, a lexical resource that provides this type of information has recently become available: PropBank.Br. However, in comparison with corpora for other languages such as English, the corpus provided by that project is small and it wouldn\'t allow a supervised classier to perform the labeling task with good performance. To deal with this problem, in this dissertation we use a semi-supervised approach capable of extracting relevant information both from annotated and non-annotated data available, making it less dependent on the training corpus. We implemented the self-training algorithm with logistic regression (or maximum entropy) models as base classier to label the corpus Bosque (section CETENFolha) from the Floresta Sintá(c)tica with the PropBank.Br semantic role tags. To the original algorithm, we incorporated balancing and similarity measures between verb-specic arguments so as to improve the performance of the system in the argument classication task. Using an evaluation benchmark implemented in this research project, the proposed semi-supervised approach has a statistical comparable performance as the one of a supervised classier trained with more annotated data (80,5 vs. 82,3 de \'F IND. 1\', p > 0, 01).

A Mineração de Opiniões é um processo que tem por objetivo extrair as opiniões e suas polaridades de sentimentos expressas em textos em língua natural. Essa área de pesquisa tem ganhado destaque devido ao volume de opiniões que os usuários compartilham na Internet, como revisões em sites de e-commerce, rede sociais e tweets. A Mineração de Opiniões baseada em Aspectos é uma alternativa promissora para analisar a polaridade do sentimento em um maior nível de detalhes. Os métodos tradicionais para extração de aspectos e classificação de sentimentos exigem a participação de especialistas de domínio para criar léxicos ou definir regras de extração para diferentes idiomas e domínios. Além disso, tais métodos usualmente exploram algoritmos de aprendizado supervisionado, porém exigem um grande conjunto de dados rotulados para induzir um modelo de classificação. Os desafios desta tese de doutorado estão relacionados a como diminuir a necessidade de grande esforço humano tanto para rotular dados, quanto para tratar a dependência de domínio para as tarefas de extração de aspectos e classificação de sentimentos dos aspectos para Mineração de Opiniões. Para reduzir a necessidade de grande quantidade de exemplos rotulados foi proposta uma abordagem semissupervisionada, denominada por Aspect-based Sentiment Propagation on Heterogeneous Networks (ASPHN) em que são propostas representações de textos nas quais os atributos linguísticos, os aspectos candidatos e os rótulos de sentimentos são modelados por meio de redes heterogêneas. Para redução dos esforços para construir recursos específicos de domínio foi proposta uma abordagem baseada em aprendizado por transferência entre domínios denominada Cross-Domain Aspect Label Propagation through Heterogeneous Networks (CD-ALPHN) que utiliza dados rotulados de outros domínios para suportar tarefas de aprendizado em domínios sem dados rotulados. Nessa abordagem são propostos uma representação em uma rede heterogênea e um método de propagação de rótulos. Os vértices da rede são os aspectos rotulados do domínio de origem, os atributos linguísticos e os candidatos a aspectos do domínio alvo. Além disso, foram analisados métodos de extração de aspectos e propostas algumas variações para considerar cenários nãosupervisionados e independentes de domínio. As soluções propostas nesta tese de doutorado foram avaliadas e comparadas as do estado-da-arte utilizando coleções de revisões de diferentes produtos e serviços. Os resultados obtidos nas avaliações experimentais são competitivos e demonstram que as soluções propostas são promissoras. / Opinion Mining is a process that aims to extract opinions and their sentiment polarities expressed in natural language texts. This area of research has been in the highlight because of the volume of opinions that users share on the available visualization means on the Internet (reviews on e-commerce sites, social networks, tweets, others). Aspect-based Opinion Mining is a promising alternative for analyzing the sentiment polarity on a high level of detail. The traditional methods for aspect extraction and sentiment classification require the participation of domain experts to create lexicons or define extraction rules for different languages and domains. In addition, such methods usually exploit supervised machine learning algorithms, but require a large set of labeled data to induce a classification model. The challenges of this doctoral thesis are related on to how to reduce the need for great human effort both: (i) to label data; and (ii) to treat domain dependency for the tasks of aspect extraction and aspect sentiment classification for Opinion Mining. In order to reduce the need for a large number of labeled examples, a semi-supervised approach was proposed, called Aspect-based Sentiment Propagation on Heterogeneous Networks (ASPHN). In this approach, text representations are proposed in which linguistic attributes, candidate aspects and sentiment labels are modeled by heterogeneous networks. Also, a cross-domain learning approach called Cross-Domain Aspect Label Propagation through Heterogeneous Networks (CD-ALPHN) is proposed in order to reduce efforts to build domain-specific resources, This approach uses labeled data from other domains to support learning tasks in domains without labeled data. A representation in a heterogeneous network and a label propagation method are proposed in this cross-domain learning approach. The vertices of the network are the labeled aspects of the source domain, the linguistic attributes, and the candidate aspects of the target domain. In addition, aspect extraction methods were analyzed and some variations were proposed to consider unsupervised and domain independent scenarios. The solutions proposed in this doctoral thesis were evaluated and compared to the state-of-the-art solutions using collections of different product and service reviews. The results obtained in the experimental evaluations are competitive and demonstrate that the proposed solutions are promising.

Com o aumento da capacidade de armazenamento, as bases de dados são cada vez maiores e, em muitas situações, apenas um pequeno subconjunto de itens de dados pode ser rotulado. Isto acontece devido ao processo de rotulagem ser frequentemente caro, demorado e necessitar do envolvimento de especialistas humanos. Com isso, diversos algoritmos semissupervisionados foram propostos, mostrando que é possível obter bons resultados empregando conhecimento prévio, relativo à pequena fração de dados rotulados. Dentre esses algoritmos, os que têm ganhado bastante destaque na área têm sido aqueles baseados em redes. Tal interesse, justifica-se pelas vantagens oferecidas pela representação via redes, tais como, a possibilidade de capturar a estrutura topológica dos dados, representar estruturas hierárquicas, bem como modelar manifolds no espaço multi-dimensional. No entanto, existe uma grande quantidade de dados representados em tabelas atributo-valor, nos quais não se poderia aplicar os algoritmos baseados em redes sem antes construir uma rede a partir desses dados. Como a geração das redes, assim como sua relação com o desempenho dos algoritmos têm sido pouco estudadas, esta tese investigou esses aspectos e propôs novos métodos para construção de redes, considerando características ainda não exploradas na literatura. Foram propostos três métodos para construção de redes com diferentes topologias: 1) S-kNN (Sequential k Nearest Neighbors), que gera redes regulares; 2) GBILI (Graph Based on the Informativeness of Labeled Instances) e RGCLI (Robust Graph that Considers Labeled Instances), que exploram os rótulos disponíveis gerando redes com distribuição de grau lei de potência; 3) GBLP (Graph Based on Link Prediction), que se baseia em medidas de predição de links gerando redes com propriedades mundo-pequeno. As estratégias de construção de redes propostas foram analisadas por meio de medidas de teoria dos grafos e redes complexas e validadas por meio da classificação semissupervisionada. Os métodos foram aplicados em benchmarks da área e também na classificação de gêneros musicais e segmentação de imagens. Os resultados mostram que a topologia da rede influencia diretamente os algoritmos de classificação e as estratégias propostas alcançam boa acurácia. / With the increase capacity of storage, databases are getting larger and, in many situations, only a small subset of data items can be labeled. This happens because the labeling process is often expensive, time consuming and requires the involvement of human experts. Hence, several semi-supervised algorithms have been proposed, showing that it is possible to achieve good results by using prior knowledge. Among these algorithms, those based on graphs have gained prominence in the area. Such interest is justified by the benefits provided by the representation via graphs, such as the ability to capture the topological structure of the data, represent hierarchical structures, as well as model manifold in high dimensional spaces. Nevertheless, most of available data is represented by attribute-value tables, making necessary the study of graph construction techniques in order to convert these tabular data into graphs for applying such algorithms. As the generation of the weight matrix and the sparse graph, and their relation to the performance of the algorithms have been little studied, this thesis investigated these aspects and proposed new methods for graph construction with characteristics litle explored in the literature yet. We have proposed three methods for graph construction with different topologies: 1) S-kNN (Sequential k Nearest Neighbors) that generates regular graphs; 2) GBILI (Graph Based on the informativeness of Labeled Instances) and RGCLI (Robust Graph that Considers Labeled Instances), which exploit the labels available generating power-law graphs; 3) GBLP (Graph Based on Link Prediction), which are based on link prediction measures and generates small-world graphs. The strategies proposed were analyzed by graph theory and complex networks measures and validated in semi-supervised classification tasks. The methods were applied in benchmarks of the area and also in the music genre classification and image segmentation. The results show that the topology of the graph directly affects the classification algorithms and the proposed strategies achieve good accuracy.

Machine learning enables machines to learn automatically from data. In literature, graph-based methods have received increasing attention due to their ability to learn from both local and global information. In these methods, each data instance is represented by a vertex and is linked to other vertices according to a predefined affinity rule. However, they usually have unfeasible time cost for large problems. To overcome this problem, techniques can employ a heuristic to find suboptimal solutions in a feasible time. Early heuristic optimization methods exploit nature-inspired collective processes, such as ants looking for food sources and swarms of bees. Nowadays, advances in the field of complex systems provide powerful tools to assess and to understand dynamical systems. Complex networks, which are graphs with nontrivial topology, are among these theoretical tools capable of describing the interplay of topology, structure, and dynamics of complex systems. Therefore, machine learning methods based on complex networks and collective dynamics have been proposed. They encompass three steps. First, a complex network is constructed from the input data. Then, the simulation of a distributed collective system in the network generates rich information. Finally, the collected information is used to solve the learning problem. The coordination of the individuals in the system permit to achieve dynamics that is far more complex than the behavior of single individuals. In this research, I have explored collective dynamics in machine learning tasks, both in unsupervised and semi-supervised scenarios. Specifically, I have proposed a new collective system of competing particles that shifts the traditional vertex-centric dynamics to a more informative edge-centric one. Moreover, it is the first particle competition system applied in machine learning task that has deterministic behavior. Results show several advantages of the edge-centric model, including the ability to acquire more information about overlapping areas, a better exploration behavior, and a faster convergence time. Also, I have proposed a new network formation technique that is not based on similarity and has low computational cost. Since addition and removal of samples in the network is cheap, it can be used in real-time application. Finally, I have conducted analytical investigations of a flocking-like system that was needed to guarantee the expected behavior in community detection tasks. In conclusion, the result of the research contributes to many areas of machine learning and complex systems. / Aprendizado de máquina permite que computadores aprendam automaticamente dos dados. Na literatura, métodos baseados em grafos recebem crescente atenção por serem capazes de aprender através de informações locais e globais. Nestes métodos, cada item de dado é um vértice e as conexões são dadas uma regra de afinidade. Todavia, tais técnicas possuem custo de tempo impraticável para grandes grafos. O uso de heurísticas supera este problema, encontrando soluções subótimas em tempo factível. No início, alguns métodos de otimização inspiraram suas heurísticas em processos naturais coletivos, como formigas procurando por comida e enxames de abelhas. Atualmente, os avanços na área de sistemas complexos provêm ferramentas para medir e entender estes sistemas. Redes complexas, as quais são grafos com topologia não trivial, são uma das ferramentas. Elas são capazes de descrever as relações entre topologia, estrutura e dinâmica de sistemas complexos. Deste modo, novos métodos de aprendizado baseados em redes complexas e dinâmica coletiva vêm surgindo. Eles atuam em três passos. Primeiro, uma rede complexa é construída da entrada. Então, simula-se um sistema coletivo distribuído na rede para obter informações. Enfim, a informação coletada é utilizada para resolver o problema. A interação entre indivíduos no sistema permite alcançar uma dinâmica muito mais complexa do que o comportamento individual. Nesta pesquisa, estudei o uso de dinâmica coletiva em problemas de aprendizado de máquina, tanto em casos não supervisionados como semissupervisionados. Especificamente, propus um novo sistema de competição de partículas cuja competição ocorre em arestas ao invés de vértices, aumentando a informação do sistema. Ainda, o sistema proposto é o primeiro modelo de competição de partículas aplicado em aprendizado de máquina com comportamento determinístico. Resultados comprovam várias vantagens do modelo em arestas, includindo detecção de áreas sobrepostas, melhor exploração do espaço e convergência mais rápida. Além disso, apresento uma nova técnica de formação de redes que não é baseada na similaridade dos dados e possui baixa complexidade computational. Uma vez que o custo de inserção e remoção de exemplos na rede é barato, o método pode ser aplicado em aplicações de tempo real. Finalmente, conduzi um estudo analítico em um sistema de alinhamento de partículas. O estudo foi necessário para garantir o comportamento esperado na aplicação do sistema em problemas de detecção de comunidades. Em suma, os resultados da pesquisa contribuíram para várias áreas de aprendizado de máquina e sistemas complexos.

This work applies complex network theory to the problem of semi-supervised and unsupervised learning in networks that are representations of multivariate datasets. Complex networks allow the use of nonlinear dynamical systems to represent behaviors according to the connectivity patterns of networks. Inspired by behavior observed in nature, such as competition for limited resources, dynamical system models can be employed to uncover the organizational structure of a network. In this dissertation, we develop a technique for classifying data represented as interaction networks. As part of the technique, we model a dynamical system inspired by the biological dynamics of resource competition. So far, similar methods have focused on vertices as the resource of competition. We introduce edges as the resource of competition. In doing so, the connectivity pattern of a network might be used not only in the dynamical system simulation but in the learning task as well. / Este trabalho aplica a teoria de redes complexas para o estudo de uma técnica aplicada ao problema de aprendizado semissupervisionado e não-supervisionado em redes, especificamente, aquelas que representam conjuntos de dados multivariados. Redes complexas permitem o emprego de sistemas dinâmicos não-lineares que podem apresentar comportamentos de acordo com os padrões de conectividade de redes. Inspirado pelos comportamentos observados na natureza, tais como a competição por recursos limitados, sistema dinâmicos podem ser utilizados para revelar a estrutura da organização de uma rede. Nesta dissertação, desenvolve-se uma técnica aplicada ao problema de classificação de dados representados por redes de interação. Como parte da técnica, um sistema dinâmico inspirado na competição por recursos foi modelado. Métodos similares concentraram-se em vértices como o recurso da concorrência. Neste trabalho, introduziu-se arestas como o recurso-alvo da competição. Ao fazê-lo, utilizar-se-á o padrão de conectividade de uma rede tanto na simulação do sistema dinâmico, quanto na tarefa de aprendizado.

Com uma quantidade quase incontável de informação textual disponível na web, a automatização de diversas tarefas referentes ao processamento automático de textos é uma necessidade inegável. Em abordagens superficiais do PLN (Processamento da Linguagem Natural), importantes propriedades do texto são perdidas, como posição, ordem, adjacência e contexto dos segmentos textuais. Uma análise textual mais profunda, como a realizada no nível do discurso, ocupa-se da busca e identificação da organização retórica do texto, gerando uma estrutura hierárquica em que as intenções do autor são explicitadas e relacionadas entre si. Para a automatização dessa tarefa, tem-se utilizado técnicas de aprendizado automático, predominantemente do paradigma supervisionado. Nesse paradigma, são necessários dados rotulados manualmente para a geração dos modelos de classificação. Como a anotação para essa tarefa é algo custoso, os resultados obtidos no aprendizado são insatisfatórios, pois estão bem aquém do desempenho humano na mesma tarefa. Nesta tese, o uso massivo de dados não rotulados no aprendizado semissupervisionado sem fim foi empregado na tarefa de identificação das relações retóricas. Foi proposto um framework que utiliza textos obtidos continuamente da web. No framework, realiza-se a monitoração da mudança de conceito, que pode ocorrer durante o aprendizado contínuo, e emprega-se uma variação dos algoritmos tradicionais de semissupervisão. Além disso, foram adaptados para o Português técnicas do estado da arte. Sem a necessidade de anotação humana, a medida-F melhorou, por enquanto, em 0,144 (de 0,543 para 0,621). Esse resultado consiste no estado da arte da análise discursiva automática para o Português. / Considering the almost uncountable textual information available on the web, the auto- matization of several tasks related to the automatic text processing is an undeniable need. In superficial approaches of NLP (Natural Language Processing), important properties of the text are lost, as position, order, adjacency and context of textual segments. A de- eper analysis, as carried out in the discursive level, deals with the identification of the rhetoric organization of the text, generating a hierarchical structure. In this structure, the intentions of the author are identified and related among them. To the automati- zation of this task, most of the works have used machine learning techniques, mainly from the supervised paradigm. In this paradigm, manually labeled data is required to obtain classification models, specially to identify the rhetorical relations. As the manual annotation is a costly process, the obtained results in the task are unsatisfactory, because they are below the human perfomance. In this thesis, the massive use of unlabeled data was applied in a semi-supervised never-ending learning to identify the rhetorical relations. In this exploration, a framework was proposed, which uses texts continuously obtained from the web. In the framework, a variation of traditional semi-supervised algorithms was employed, and it uses a concept-drift monitoring strategy. Besides that, state of the art techniques for English were adapted to Portuguese. Without the human intervention, the F-measure increased, for while, 0.144 (from 0.543 to 0.621). This result consists in the state-of-the-art for Discourse Analysis in Portuguese.