Das Lernen aus strukturierten Eingabe- und Ausgabebeispielen ist die Grundlage für die automatisierte Verarbeitung natürlich auftretender Problemstellungen und eine Herausforderung für das Maschinelle Lernen. Die Einordnung von Objekten in eine Klassentaxonomie, die Eigennamenerkennung und das Parsen natürlicher Sprache sind mögliche Anwendungen. Klassische Verfahren scheitern an der komplexen Natur der Daten, da sie die multiplen Abhängigkeiten und Strukturen nicht erfassen können. Zudem ist die Erhebung von klassifizierten Beispielen in strukturierten Anwendungsgebieten aufwändig und ressourcenintensiv, während unklassifizierte Beispiele günstig und frei verfügbar sind. Diese Arbeit thematisiert halbüberwachte, diskriminative Vorhersagemodelle für strukturierte Daten. Ausgehend von klassischen halbüberwachten Verfahren werden die zugrundeliegenden analytischen Techniken und Algorithmen auf das Lernen mit strukturierten Variablen übertragen. Die untersuchten Verfahren basieren auf unterschiedlichen Prinzipien und Annahmen, wie zum Beispiel der Konsensmaximierung mehrerer Hypothesen im Lernen aus mehreren Sichten, oder der räumlichen Struktur der Daten im transduktiven Lernen. Desweiteren wird in einer Fallstudie zur Email-Batcherkennung die räumliche Struktur der Daten ausgenutzt und eine Lösung präsentiert, die der sequenziellen Natur der Daten gerecht wird. Aus den theoretischen Überlegungen werden halbüberwachte, strukturierte Vorhersagemodelle und effiziente Optmierungsstrategien abgeleitet. Die empirische Evaluierung umfasst Klassifikationsprobleme, Eigennamenerkennung und das Parsen natürlicher Sprache. Es zeigt sich, dass die halbüberwachten Methoden in vielen Anwendungen zu signifikant kleineren Fehlerraten führen als vollständig überwachte Baselineverfahren. / Learning mappings between arbitrary structured input and output variables is a fundamental problem in machine learning. It covers many natural learning tasks and challenges the standard model of learning a mapping from independently drawn instances to a small set of labels. Potential applications include classification with a class taxonomy, named entity recognition, and natural language parsing. In these structured domains, labeled training instances are generally expensive to obtain while unlabeled inputs are readily available and inexpensive. This thesis deals with semi-supervised learning of discriminative models for structured output variables. The analytical techniques and algorithms of classical semi-supervised learning are lifted to the structured setting. Several approaches based on different assumptions of the data are presented. Co-learning, for instance, maximizes the agreement among multiple hypotheses while transductive approaches rely on an implicit cluster assumption. Furthermore, in the framework of this dissertation, a case study on email batch detection in message streams is presented. The involved tasks exhibit an inherent cluster structure and the presented solution exploits the streaming nature of the data. The different approaches are developed into semi-supervised structured prediction models and efficient optimization strategies thereof are presented. The novel algorithms generalize state-of-the-art approaches in structural learning such as structural support vector machines. Empirical results show that the semi-supervised algorithms lead to significantly lower error rates than their fully supervised counterparts in many application areas, including multi-class classification, named entity recognition, and natural language parsing.

Graph-based semi-supervised learning (SSL) algorithms have been widely studied in the last few years. Most of these algorithms were designed from unconstrained optimization problems using a Laplacian regularizer term as smoothness functional in an attempt to reflect the intrinsic geometric structure of the datas marginal distribution. Although a number of recent research papers are still focusing on unconstrained methods for graph-based SSL, a recent statistical analysis showed that many of these algorithms may be unstable on transductive regression. Therefore, we focus on providing new constrained methods for graph-based SSL. We begin by analyzing the regularization framework of existing unconstrained methods. Then, we incorporate two normalization constraints into the optimization problem of three of these methods. We show that the proposed optimization problems have closed-form solution. By generalizing one of these constraints to any distribution, we provide generalized methods for constrained graph-based SSL. The proposed methods have a more flexible regularization framework than the corresponding unconstrained methods. More precisely, our methods can deal with any graph Laplacian and use higher order regularization, which is effective on general SSL taks. In order to show the effectiveness of the proposed methods, we provide comprehensive experimental analyses. Specifically, our experiments are subdivided into two parts. In the first part, we evaluate existing graph-based SSL algorithms on time series data to find their weaknesses. In the second part, we evaluate the proposed constrained methods against six state-of-the-art graph-based SSL algorithms on benchmark data sets. Since the widely used best case analysis may hide useful information concerning the SSL algorithms performance with respect to parameter selection, we used recently proposed empirical evaluation models to evaluate our results. Our results show that our methods outperforms the competing methods on most parameter settings and graph construction methods. However, we found a few experimental settings in which our methods showed poor performance. In order to facilitate the reproduction of our results, the source codes, data sets, and experimental results are freely available. / Algoritmos de aprendizado semissupervisionado baseado em grafos foram amplamente estudados nos últimos anos. A maioria desses algoritmos foi projetada a partir de problemas de otimização sem restrições usando um termo regularizador Laplaciano como funcional de suavidade numa tentativa de refletir a estrutura geométrica intrínsica da distribuição marginal dos dados. Apesar de vários artigos científicos recentes continuarem focando em métodos sem restrição para aprendizado semissupervisionado em grafos, uma análise estatística recente mostrou que muitos desses algoritmos podem ser instáveis em regressão transdutiva. Logo, nós focamos em propor novos métodos com restrições para aprendizado semissupervisionado em grafos. Nós começamos analisando o framework de regularização de métodos sem restrições existentes. Então, nós incorporamos duas restrições de normalização no problema de otimização de três desses métodos. Mostramos que os problemas de otimização propostos possuem solução de forma fechada. Ao generalizar uma dessas restrições para qualquer distribuição, provemos métodos generalizados para aprendizado semissupervisionado restrito baseado em grafos. Os métodos propostos possuem um framework de regularização mais flexível que os métodos sem restrições correspondentes. Mais precisamente, nossos métodos podem lidar com qualquer Laplaciano em grafos e usar regularização de ordem elevada, a qual é efetiva em tarefas de aprendizado semissupervisionado em geral. Para mostrar a efetividade dos métodos propostos, nós provemos análises experimentais robustas. Especificamente, nossos experimentos são subdivididos em duas partes. Na primeira parte, avaliamos algoritmos de aprendizado semissupervisionado em grafos existentes em dados de séries temporais para encontrar possíveis fraquezas desses métodos. Na segunda parte, avaliamos os métodos restritos propostos contra seis algoritmos de aprendizado semissupervisionado baseado em grafos do estado da arte em conjuntos de dados benchmark. Como a amplamente usada análise de melhor caso pode esconder informações relevantes sobre o desempenho dos algoritmos de aprendizado semissupervisionado com respeito à seleção de parâmetros, nós usamos modelos de avaliação empírica recentemente propostos para avaliar os nossos resultados. Nossos resultados mostram que os nossos métodos superam os demais métodos na maioria das configurações de parâmetro e métodos de construção de grafos. Entretanto, encontramos algumas configurações experimentais nas quais nossos métodos mostraram baixo desempenho. Para facilitar a reprodução dos nossos resultados, os códigos fonte, conjuntos de dados e resultados experimentais estão disponíveis gratuitamente.

Aprendizado supervisionado tem sido principalmente utilizado para classificação. Neste trabalho são mostrados os benefícios do uso de rankings ao invés de classificação de exemplos isolados. Um rankeador é um algoritmo que ordena um conjunto de exemplos de tal modo que eles são apresentados do exemplo de maior para o exemplo de menor expectativa de ser positivo. Um ranking é o resultado dessa ordenação. Normalmente, um ranking é obtido pela ordenação do valor de confiança de classificação dado por um classificador. Este trabalho tem como objetivo procurar por novas abordagens para promover o uso de rankings. Desse modo, inicialmente são apresentados as diferenças e semelhanças entre ranking e classificação, bem como um novo algoritmo de ranking que os obtém diretamente sem a necessidade de obter os valores de confiança de classificação, esse algoritmo é denominado de LEXRANK. Uma área de pesquisa bastante importante em rankings é a análise ROC. O estudo de árvores de decisão e análise ROC é bastante sugestivo para o desenvolvimento de uma visualização da construção da árvore em gráficos ROC. Para mostrar passo a passo essa visualização foi desenvolvido uma sistema denominado PROGROC. Ainda do estudo de análise ROC, foi observado que a inclinação (coeficiente angular) dos segmentos que compõem o fecho convexo de curvas ROC é equivalente a razão de verossimilhança que pode ser convertida para probabilidades. Essa conversão é denominada de calibração por fecho convexo de curvas ROC que coincidentemente é equivalente ao algoritmo PAV que implementa regressão isotônica. Esse método de calibração otimiza Brier Score. Ao explorar essa medida foi encontrada uma relação bastante interessante entre Brier Score e curvas ROC. Finalmente, também foram explorados os rankings construídos durante o método de seleção de exemplos do algoritmo de aprendizado semi-supervisionado multi-descrição CO-TRAINING / Supervised learning has been used mostly for classification. In this work we show the benefits of a welcome shift in attention from classification to ranking. A ranker is an algorithm that sorts a set of instances from highest to lowest expectation that the instance is positive, and a ranking is the outcome of this sorting. Usually a ranking is obtained by sorting scores given by classifiers. In this work, we are concerned about novel approaches to promote the use of ranking. Therefore, we present the differences and relations between ranking and classification followed by a proposal of a novel ranking algorithm called LEXRANK, whose rankings are derived not from scores, but from a simple ranking of attribute values obtained from the training data. One very important field which uses rankings as its main input is ROC analysis. The study of decision trees and ROC analysis suggested an interesting way to visualize the tree construction in ROC graphs, which has been implemented in a system called PROGROC. Focusing on ROC analysis, we observed that the slope of segments obtained from the ROC convex hull is equivalent to the likelihood ratio, which can be converted into probabilities. Interestingly, this ROC convex hull calibration method is equivalent to Pool Adjacent Violators (PAV). Furthermore, the ROC convex hull calibration method optimizes Brier Score, and the exploration of this measure leads us to find an interesting connection between the Brier Score and ROC Curves. Finally, we also investigate rankings build in the selection method which increments the labelled set of CO-TRAINING, a semi-supervised multi-view learning algorithm

Nos últimos 30 anos, a área de aprendizagem de máquina desenvolveu-se de forma comparável com a Física no início do século XX. Esse avanço tornou possível a resolução de problemas do mundo real que anteriormente não poderiam ser solucionados por máquinas, devido à dificuldade de modelos puramente estatísticos ajustarem-se de forma satisfatória aos dados de treinamento. Dentre tais avanços, pode-se citar a utilização de técnicas de aprendizagem de máquina na área de Química Medicinal, envolvendo métodos de análise, representação e predição de informação molecular por meio de recursos computacionais. Os dados utilizados no contexto biológico possuem algumas características particulares que podem influenciar no resultado de sua análise. Dentre estas, pode-se citar a complexidade das informações moleculares, o desbalanceamento das classes envolvidas e a existência de dados incompletos ou rotulados de forma incerta. Tais adversidades podem prejudicar o processo de identificação de compostos candidatos a novos fármacos, se não forem tratadas de forma adequada. Neste trabalho, foi abordada uma técnica de aprendizagem de máquina semi-supervisionada capaz de reduzir o impacto causado pelo problema da incerteza na rotulação dos dados, aplicando um método para estimar rótulos mais confiáveis para os compostos químicos existentes no conjunto de treinamento. Na tentativa de evitar os efeitos causados pelo desbalanceamento dos dados, foi incorporada ao processo de estimação de rótulos uma abordagem sensível ao custo, com o objetivo de evitar o viés em benefício da classe majoritária. Após o tratamento do problema da incerteza na rotulação, classificadores baseados em Máquinas de Aprendizado Extremo foram construídos, almejando boa capacidade de aproximação em um tempo de processamento reduzido em relação a outras abordagens de classificação comumente aplicadas. Por fim, o desempenho dos classificadores construídos foi avaliado por meio de análises dos resultados obtidos, confrontando o cenário com os dados originais e outros com as novas rotulações obtidas durante o processo de estimação semi-supervisionado / In the last 30 years, the area of machine learning has developed in a way comparable to Physics in the early twentieth century. This breakthrough has made it possible to solve real-world problems that previously could not be solved by machines because of the difficulty of purely statistical models to fit satisfactorily with training data. Among these advances, one can cite the use of machine learning techniques in the area of Medicinal Chemistry, involving methods for analysing, representing and predicting molecular information through computational resources. The data used in the biological context have some particular characteristics that can influence the result of its analysis. These include the complexity of molecular information, the imbalance of the classes involved, and the existence of incomplete or uncertainly labeled data. If they are not properly treated, such adversities may affect the process of identifying candidate compounds for new drugs. In this work, a semi-supervised machine learning technique was considered to reduce the impact caused by the problem of uncertainty in the data labeling, by applying a method to estimate more reliable labels for the chemical compounds in the training set. In an attempt to reduce the effects caused by data imbalance, a cost-sensitive approach was incorporated to the label estimation process, in order to avoid bias in favor of the majority class. After addressing the uncertainty problem in labeling, classifiers based on Extreme Learning Machines were constructed, aiming for good approximation ability in a reduced processing time in relation to other commonly applied classification approaches. Finally, the performance of the classifiers constructed was evaluated by analyzing the results obtained, comparing the scenario with the original data and others with the new labeling obtained by the semi-supervised estimation process

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.

Cette étude a pour sujet les hypergraphes. / This study has for subject the hypergraphs.

<p>Cilj &ndash; Cilj istraživanja u okviru doktorske disertacije je razvoj sistema za automatsku polu-nadgledanu klasifikaciju podataka. Sistem bi trebao biti primenljiv na &scaron;irokom spektru domena gde je neophodna klasifikacija podataka, a te&scaron;ko je, ili čak nemoguće, doći do dovoljno velikog i raznovrsnog obučavajućeg skupa podataka<br />Metodologija &ndash; Modeli opisani u disertaciji se baziraju na kombinaciji ko-trening algoritma i tehnika učenja sa grupom hipoteza. Prvi korak jeste obučavanje grupe klasifikatora velike raznolikosti i kvaliteta. Sa ovim ciljem modeli eksploati&scaron;u primenu različitih konfiguracija ko-trening algoritma na isti skup podataka. Prednost ovog pristupa je mogućnost kori&scaron;ćenja značajno manjeg anotiranog obučavajućeg skupa za inicijalizaciju algoritma.<br />Skup nezavisno obučenih ko-trening klasifikatora se kreira generisanjem predefinisanog broja slučajnih podela obeležja polaznog skupa podataka. Nakon toga se, polazeći od istog inicijalnog obučavajućeg skupa, ali kori&scaron;ćenjem različitih kreiranih podela obeležja, obučava grupa ko-trening klasifikatora. Nakon ovoga, neophodno je kombinovati predikcije nezavisno obučenih klasifikatora.<br />Predviđena su dva načina kombinovanja predikcija. Prvi način se zasniva na klasifikaciji zapisa na osnovu većine glasova grupe ko-trening klasifikatora. Na ovaj način se daje predikcija za svaki od zapisa koji su pripadali grupi neanotiranih primera kori&scaron;ćenih u toku obuke ko-treninga. Potom se primenjuje genetski algoritam u svrhu selekcije najpouzdanije klasifikovanih zapisa ovog skupa. Konačno,<br />163<br />najpouzdanije klasifikovani zapisi se koriste za obuku finalnog klasifikatora. Ovaj finalni klasifikator se koristi za predikciju klase zapisa koje je neophodno klasifikovati. Opisani algoritam je nazvan Algoritam Statistike Slučajnih Podela (Random Split Statistics algorithm, RSSalg).<br />Drugi način kombinovanja nezavisno obučenih ko-trening klasifikatora se zasniva na GMM-MAPML tehnici estimacije tačnih klasnih obeležja na osnovu vi&scaron;estrukih obeležja pripisanih od strane različitih anotatora nepoznatog kvaliteta. U ovom algoritmu, nazvanom Integracija Vi&scaron;estrukih Ko-treninranih Klasifikatora (Integration of Multiple Co-trained Classifiers, IMCC), svaki od nezavisno treniranih ko-trening klasifikatora daje predikciju klase za svaki od zapisa koji je neophodno klasifikovati. U ovoj postavci se svaki od ko-trening klasifikatora tretira kao jedan od anotatora čiji je kvalitet nepoznat, a svakom zapisu, za koga je neophodno odrediti klasno obeležje, se dodeljuje vi&scaron;e klasnih obeležja. Na kraju se primenjuje GMM-MAPML tehnika, kako bi se na osnovu dodeljenih vi&scaron;estrukih klasnih obeležja za svaki od zapisa izvr&scaron;ila estimacija stvarnog klasnog obeležja zapisa.<br />Rezultati &ndash; U disertaciji su razvijena dva modela, Integracija Vi&scaron;estrukih Ko-treninranih Klasifikatora (IMCC) i Algoritam Statistike Slučajnih Podela (RSSalg), bazirana na ko-trening algoritmu, koja re&scaron;avaju zadatak automatske klasifikacije u slučaju nepostojanja dovoljno velikog anotiranog korpusa za obuku. Modeli predstavljeni u disertaciji dizajnirani su tako da omogućavaju primenu ko-trening algoritma na skupove podataka bez prirodne podele obeležja, kao i da unaprede njegove performanse. Modeli su na vi&scaron;e skupova podataka različite veličine, dimenzionalnosti i redudantnosti poređeni sa postojećim ko-trening alternativama. Pokazano je da razvijeni modeli na testiranim skupovima podataka postižu bolje performanse od testiranih ko-trening alternativa.<br />Praktična primena &ndash; Razvijeni modeli imaju &scaron;iroku mogućnost primene u svim domenima gde je neophodna klasifikacija podataka, a anotiranje podataka dugotrajno i skupo. U disertaciji je prikazana i primena razvijenih modela u nekoliko konkretnih<br />164<br />situacija gde su modeli od posebne koristi: detekcija subjektivnosti, vi&scaron;e-kategorijska klasifikacija i sistemi za davanje preporuka.<br />Vrednost &ndash; Razvijeni modeli su korisni u &scaron;irokom spektru domena gde je neophodna klasifikacija podataka, a anotiranje podataka dugotrajno i skupo. Njihovom primenom se u značajnoj meri smanjuje ljudski rad neophodan za anotiranje velikih skupova podataka. Pokazano je da performanse razvijenih modela prevazilaze performanse postojećih alternativa razvijenih sa istim ciljem relaksacije problema dugotrajne i mukotrpne anotacije velikih skupova podataka.</p> / <p>Aim &ndash; The research presented in this thesis is aimed towards the development of the system for automatic semi-supervised classification. The system is designed to be applicable on the broad spectrum of practical domains where automatic classification of data is needed but it is hard or impossible to obtain a large enough training set.<br />Methodology &ndash; The described models combine co-training algorithm with ensemble learning with the aim to overcome the problem of co-training application on the datasets without the natural feature split. The first step is to create the ensemble of co-training classifiers. For this purpose the models presented in this thesis apply different configurations of co-training on the same training set. Compared to existing similar approaches, this approach requires a significantly smaller initial training set.<br />The ensemble of independently trained co-training classifiers is created by generating a predefined number of random feature splits of the initial training set. Using the same initial training set, but different feature splits, a group of co-training classifiers is trained. The two models differ in the way the predictions of different co-training classifiers are combined.<br />The first approach is based on majority voting: each instance recorded in the enlarged training sets resulting from co-training application is classified by majority voting of the group of obtained co-training classifiers. After this, the genetic algorithm is applied in order to select the group of most reliably classified instances from this set. The most reliable instances are used in<br />167<br />order to train a final classifier which is used to classify new instances. The described algorithm is called Random Split Statistic Algorithm (RSSalg).<br />The other approach of combining single predictions of the group of co-training classifiers is based on GMM-MAPML technique of estimating the true hidden label based on the multiple labels assigned by multiple annotators of unknown quality. In this model, called the Integration of Multiple Co-trained Classifiers (IMCC), each of the independently trained co-training classifiers predicts the label for each test instance. Each co-training classifier is treated as one of the annotators of unknown quality and each test instance is assigned multiple labels (one by each of the classifiers). Finally, GMM-MAPML technique is applied in order to estimate the true hidden label in the multi-annotator setting.<br />Results &ndash; In the dissertation the two models are developed: the Integration of Multiple Co-trained Classifiers (IMCC) and Random Split Statistic Algorithm (RSSalg). The models are based on co-training and aimed towards enabling automatic classification in the cases where the existing training set is insufficient for training a quality classification model. The models are designed to enable the application of co-training algorithm on datasets that lack the natural feature split needed for its application, as well as with the goal to improve co-training performance. The models are compared to their co-training alternatives on multiple datasets of different size, dimensionality and feature redundancy. It is shown that the developed models exhibit superior performance compared to considered co-training alternatives.<br />Practical application &ndash; The developed models are applicable on the wide spectrum of domains where there is a need for automatic classification and training data is insufficient. The dissertation presents the successful application of models in several concrete situations where they are highly<br />168<br />beneficial: subjectivity detection, multicategory classification and recommender systems.<br />Value &ndash; The models can greatly reduce the human effort needed for long and tedious annotation of large datasets. The conducted experiments show that the developed models are superior to considered alternatives.</p>

Modelos para aprendizado não supervisionado podem fornecer restrições complementares úteis para melhorar a capacidade de generalização de classificadores. Baseando-se nessa premissa, um algoritmo existente, denominado de C3E (Consensus between Classification and Clustering Ensembles), recebe como entradas estimativas de distribuições de probabilidades de classes para objetos de um conjunto alvo, bem como uma matriz de similaridades entre esses objetos. Tal matriz é tipicamente construída por agregadores de agrupadores de dados, enquanto que as distribuições de probabilidades de classes são obtidas por um agregador de classificadores induzidos por um conjunto de treinamento. Como resultado, o C3E fornece estimativas refinadas das distribuições de probabilidades de classes como uma forma de consenso entre classificadores e agrupadores. A ideia subjacente é de que objetos similares são mais propensos a compartilharem o mesmo rótulo de classe. Nesta tese, uma versão mais simples do algoritmo C3E, baseada em uma função de perda quadrática (C3E-SL), foi investigada em uma abordagem que permitiu a estimação automática (a partir dos dados) de seus parâmetros críticos. Tal abordagem faz uso de um nova estratégia evolutiva concebida especialmente para tornar o C3E-SL mais prático e flexível, abrindo caminho para que variantes do algoritmo pudessem ser desenvolvidas. Em particular, para lidar com a escassez de dados rotulados, um novo algoritmo que realiza aprendizado semissupervisionado foi proposto. Seu mecanismo explora estruturas intrínsecas dos dados a partir do C3E-SL em um procedimento de autotreinamento (self-training). Esta noção também inspirou a concepção de um outro algoritmo baseado em aprendizado ativo (active learning), o qual é capaz de se autoadaptar para aprender novas classes que possam surgir durante a predição de novos dados. Uma extensa análise experimental, focada em problemas do mundo real, mostrou que os algoritmos propostos são bastante úteis e promissores. A combinação de classificadores e agrupadores resultou em modelos de classificação com grande potencial prático e que são menos dependentes do usuário ou do especialista de domínio. Os resultados alcançados foram tipicamente melhores em comparação com os obtidos por classificadores tradicionalmente usados. / Unsupervised learning models can provide a variety of supplementary constraints to improve the generalization capability of classifiers. Based on this assumption, an existing algorithm, named C3E (from Consensus between Classification and Clustering Ensembles), receives as inputs class probability distribution estimates for objects in a target set as well as a similarity matrix. Such a similarity matrix is typically built from clusterers induced on the target set, whereas the class probability distributions are obtained by an ensemble of classifiers induced from a training set. As a result, C3E provides refined estimates of the class probability distributions, from the consensus between classifiers and clusterers. The underlying idea is that similar new objects in the target set are more likely to share the same class label. In this thesis, a simpler version of the C3E algorithm, based on a Squared Loss function (C3E-SL), was investigated from an approach that enables the automatic estimation (from data) of its critical parameters. This approach uses a new evolutionary strategy designed to make C3E-SL more practical and flexible, making room for the development of variants of the algorithm. To address the scarcity of labeled data, a new algorithm that performs semi-supervised learning was proposed. Its mechanism exploits the intrinsic structure of the data by using the C3E-SL algorithm in a self-training procedure. Such a notion inspired the development of another algorithm based on active learning, which is able to self-adapt to learn new classes that may emerge when classifying new data. An extensive experimental analysis, focused on real-world problems, showed that the proposed algorithms are quite useful and promising. The combination of supervised and unsupervised learning yielded classifiers of great practical value and that are less dependent on user-defined parameters. The achieved results were typically better than those obtained by traditional classifiers.

Earth Observation is the gathering of information about planet Earth’s system via Remote Sensing technologies for monitoring land cover types and their changes. Through the years, image classification techniques have been widely studied and employed to extract useful information from Earth Observation data such as satellite imagery. One of the most attractive use cases is the monitoring of polar regions, that recently observed some dramatic changes due to global warming. Indeed drifting ice caps and icebergs represent threats to ship activities and navigation in polar areas, and the risk of collision with land-derived ice highlights the need to design a robust and automatic Sea-Ice classification for delivering up-to- date and accurate information. To achieve this goal, satellite data such as Sentinel-1 Synthetic Aperture Radar images from the European Union’s Copernicus program can be given in input to a Deep Learning classifier based on Convolutional Neural Networks capable of giving the content categorization of such images as output. For the task at hand, the availability of labeled data is generally scarce, there- fore the problem of learning with limited labeled data must be faced. There- fore, this work aims at leveraging the broader pool of unlabeled satellite data available to open up new classification solutions. This thesis proposes a Semi-Supervised Learning approach based on Generative Adversarial Networks. Such an architecture takes in input both labeled and unlabeled data and outputs the classification results exploiting the knowledge retrieved from both the data sources. Its classification performance is evaluated and it is later compared with the Supervised Learning approach and the Transfer Learning approach based on pre-trained networks. This work empirically proves that the Semi-Supervised Generative Adversarial Networks approach outperforms the Supervised Learning method, improving its Overall Accuracy by at least 5% in configurations with less than 100 training labeled samples available in the use cases under evaluation, achieving performance comparable to the Transfer Learning approach and even over- coming it under specific experimental configurations. Further analyses are then performed to highlight the effectiveness of the proposed solution. / Jordobservation är samlingen av information om jordklotets system via fjärravkänningstekniker för övervakning av landskapstyper och deras förändringar. Under årens lopp har bildklassificeringstekniker studerats och använts för att extrahera användbar information från jordobservationsdata som satellitbilder. Ett av de mest attraktiva användningsfallen är övervakningen av polära regioner, som nyligen observerade några dramatiska förändringar på grund av den globala uppvärmningen. Driftande istäcken och isberg representerar ett verkligt hot mot fartygsaktiviteter och navigering inom polära områden, och risken för kollision med land-baserad is belyser behovet av att utforma en robust och automatisk Hav-Is-klassificering för att leverera aktuell och korrekt information. För att uppnå detta mål kan satellitdata som Sentinel-1 Synthetic Aperture Radar-bilder från Europeiska unionens Copernicus-program ges som input till en Deep Learning-klassificerare baserad på Convolutional Neural Networks som kan ge innehållskategorisering av sådana bilder som output. För den aktuella uppgiften är tillgängligheten av märkt data i allmänhet otillräcklig, därför måste problemet med inlärning med begränsad mängd märkt data ställas inför rätta. Därav syftar detta arbete till att utnyttja den bredare samlingen av omärkt satellitdata som finns tillgänglig för att öppna nya klassificeringslösningar. Denna avhandling föreslår en Semi-Supervised Learning-strategi baserad på Generative Adversarial Networks. En sådan arkitektur tar som input både märkt och omärkt data, och matar ut klassificeringsresultat som utnyttjar den kunskap som hämtats från båda datakällorna. Dess klassificeringsprestanda ut- värderas och jämförs senare med tillvägagångssättet Supervised Learning och metoden Transfer Learning baserat på förtränade nätverk. Detta arbete bevisar empiriskt att Semi-Supervised Generative Adversarial Network överträffar metoden Supervised Learning och förbättrar dess totala noggrannhet med minst 5% i konfigurationer med mindre än 100 tränings- märkta prover tillgängliga i användningsfallen under utvärdering, vilket uppnår prestanda som både är jämförbar med Transfer Learning-metoden och överlägsen jämte den under specifika experimentella konfigurationer. Ytterligare analyser utförs sedan för att belysa effektiviteten hos den föreslagna lösningen.

Natural Language Processing (NLP) develops computational approaches to processing language data. Supervised machine learning has become the dominant methodology of modern NLP. The performance of a supervised NLP system crucially depends on the amount of data available for training. In the standard supervised framework, if a sequence of words was not encountered in the training set, the system can only guess at its label at test time. The cost of producing labeled training examples is a bottleneck for current NLP technology. On the other hand, a vast quantity of unlabeled data is freely available. This dissertation proposes effective, efficient, versatile methodologies for 1) extracting useful information from very large (potentially web-scale) volumes of unlabeled data and 2) combining such information with standard supervised machine learning for NLP. We demonstrate novel ways to exploit unlabeled data, we scale these approaches to make use of all the text on the web, and we show improvements on a variety of challenging NLP tasks. This combination of learning from both labeled and unlabeled data is often referred to as semi-supervised learning. Although lacking manually-provided labels, the statistics of unlabeled patterns can often distinguish the correct label for an ambiguous test instance. In the first part of this dissertation, we propose to use the counts of unlabeled patterns as features in supervised classifiers, with these classifiers trained on varying amounts of labeled data. We propose a general approach for integrating information from multiple, overlapping sequences of context for lexical disambiguation problems. We also show how standard machine learning algorithms can be modified to incorporate a particular kind of prior knowledge: knowledge of effective weightings for count-based features. We also evaluate performance within and across domains for two generation and two analysis tasks, assessing the impact of combining web-scale counts with conventional features. In the second part of this dissertation, rather than using the aggregate statistics as features, we propose to use them to generate labeled training examples. By automatically labeling a large number of examples, we can train powerful discriminative models, leveraging fine-grained features of input words.