Ces dernières années, l’intérêt pour l’apprentissage automatique n’a cessé d’augmenter dans des domaines aussi variés que la reconnaissance d’images ou l’analyse de données médicales. Cependant, une limitation du cadre classique PAC a récemment été mise en avant. Elle a entraîné l’émergence d’un nouvel axe de recherche : l’Adaptation de Domaine, dans lequel on considère que les données d’apprentissage proviennent d’une distribution (dite source) différente de celle (dite cible) dont sont issues les données de test. Les premiers travaux théoriques effectués ont débouché sur la conclusion selon laquelle une bonne performance sur le test peut s’obtenir en minimisant à la fois l’erreur sur le domaine source et un terme de divergence entre les deux distributions. Trois grandes catégories d’approches s’en inspirent : par repondération, par reprojection et par auto-étiquetage. Dans ce travail de thèse, nous proposons deux contributions. La première est une approche de reprojection basée sur la théorie du boosting et s’appliquant aux données numériques. Celle-ci offre des garanties théoriques intéressantes et semble également en mesure d’obtenir de bonnes performances en généralisation. Notre seconde contribution consiste d’une part en la proposition d’un cadre permettant de combler le manque de résultats théoriques pour les méthodes d’auto-étiquetage en donnant des conditions nécessaires à la réussite de ce type d’algorithme. D’autre part, nous proposons dans ce cadre une nouvelle approche utilisant la théorie des (epsilon, gamma, tau)-bonnes fonctions de similarité afin de contourner les limitations imposées par la théorie des noyaux dans le contexte des données structurées / During the past few years, an increasing interest for Machine Learning has been encountered, in various domains like image recognition or medical data analysis. However, a limitation of the classical PAC framework has recently been highlighted. It led to the emergence of a new research axis: Domain Adaptation (DA), in which learning data are considered as coming from a distribution (the source one) different from the one (the target one) from which are generated test data. The first theoretical works concluded that a good performance on the target domain can be obtained by minimizing in the same time the source error and a divergence term between the two distributions. Three main categories of approaches are derived from this idea : by reweighting, by reprojection and by self-labeling. In this thesis work, we propose two contributions. The first one is a reprojection approach based on boosting theory and designed for numerical data. It offers interesting theoretical guarantees and also seems able to obtain good generalization performances. Our second contribution consists first in a framework filling the gap of the lack of theoretical results for self-labeling methods by introducing necessary conditions ensuring the good behavior of this kind of algorithm. On the other hand, we propose in this framework a new approach, using the theory of (epsilon, gamma, tau)- good similarity functions to go around the limitations due to the use of kernel theory in the specific context of structured data

Algoritmos de aprendizado semi-supervisionado ativo podem se configurar como ferramentas úteis em cenários práticos em que os dados são numerosamente obtidos, mas atribuir seus respectivos rótulos de classe se configura como uma tarefa custosa/difícil. A literatura em aprendizado ativo destaca diversos algoritmos, este trabalho partiu do tradicional Hierarchical Sampling estabelecido para operar sobre hierarquias de grupos. As características de tal algoritmo o coloca à frente de outros métodos ativos, entretanto o mesmo ainda apresenta algumas dificuldades. A fim de aprimorá-lo e contornar suas principais dificuldades, incluindo sua sensibilidade na escolha particular de uma hierarquia de grupos como entrada, este trabalho propôs estratégias que possibilitaram melhorar o algoritmo na sua forma original e diante de variantes propostas na literatura. Os experimentos em diferentes bases de dados reais mostraram que o algoritmo proposto neste trabalho é capaz de superar e competir em qualidade dentro do cenário de classificação ativa com outros algoritmos ativos da literatura. / Active semi-supervised learning can play an important role in classification scenarios in which labeled data are laborious and/or expensive to obtain, while unlabeled data are numerous and can be easily acquired. There are many active algorithms in the literature and this work focuses on an active semi-supervised algorithm that can be driven by clustering hierarchy, the well-known Hierarchical Sampling (HS) algorithm. This work takes as a starting point the original Hierarchical Sampling algorithm and perform changes in different aspects of the original algorithm in order to tackle its main drawbacks, including its sensitivity to the choice of a single particular hierarchy. Experimental results over many real datasets show that the proposed algorithm performs superior or competitive when compared to a number of state-of-the-art algorithms for active semi-supervised classification.

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).

Nas últimas décadas, com o crescimento acelerado na geração e armazenamento de dados, houve um aumento na necessidade de criação e gerenciamento de grandes bases de dados. Logo, a utilização de técnicas de mineração de dados adequadas para descoberta de padrões e informações úteis em bases de dados é uma tarefa de interesse. Em especial, bases de séries temporais têm sido alvo de pesquisas em áreas como medicina, economia e agrometeorologia. Em mineração de dados, uma das tarefas mais exploradas é a classificação. Entretanto, é comum em bases de séries temporais, a quantidade e complexidade de dados extrapolarem a capacidade humana de análise manual dos dados, o que torna o processo de supervisão dos dados custoso. Como consequência disso, são produzidos poucos dados rotulados, em comparação a um grande volume de dados não rotulados disponíveis. Nesse cenário, uma abordagem adequada para análise desses dados é a classificação semissupervisionada, que considera dados rotulados e não rotulados para o treinamento do classificador. Nesse contexto, este trabalho de mestrado propõe 1) uma metodologia de análise de dados obtidos a partir de séries temporais de imagens de satélite (SITS) usando tarefas de mineração de dados e 2) uma técnica baseada em grafos para classificação semissupervisionada de séries temporais extraídas de imagens de satélite. A metodologia e a técnica de classificação desenvolvidas são aplicadas na análise de séries temporais de índices de vegetação obtidas a partir de SITS, visando a identificação de áreas de plantio de cana-de-açúcar. Os resultados obtidos em análise experimental, realizada com apoio de especialistas no domínio de aplicação, indicam que a metodologia proposta é adequada para auxiliar pesquisas em agricultura. Além disso, os resultados do estudo comparativo mostram que a técnica de classificação semissupervisionada desenvolvida supera métodos de classificação supervisionada consolidados na literatura e métodos correlatos de classificação semissupervisionada. / The amount of digital data generated and stored as well as the need of creation and management of large databases has increased significantly, in the last decades. The possibility of finding valid and potentially useful patterns and information in large databases has attracted the attention of many scientific areas. Time series databases have been explored using data mining methods in serveral domains of application, such as economics, medicine and agrometeorology. Due to the large volume and complexity of some time series databases, the process of labeling data for supervised tasks, such as classification, can be very expensive. To overcome the problem of scarcity of labeled data, semi-supervised classification, which benefits from both labeled and unlabeled data available, can be applied to classify data from large time series databases. In this Master dissertation, we propose 1) a framework for the analysis of data extracted from satellite image time series (SITS) using data mining tasks and 2) a graph-based semi-supervised classification method, developed to classify temporal data obtained from satellite images. According to experts in agrometeorology, the use of the proposed method and framework provides an automatic way of analyzing data extracted from SITS, which is very useful for supporting research in this domain of application. We apply the framework and the proposed semi-supervised classification method in the analysis of vegetation index time series, aiming at identifying sugarcane crop fields, in Brazil. Experimental results indicate that our proposed framework is useful for supporting researches in agriculture, according to experts in the domain of application. We also show that our method is more accurate than traditional supervised methods and related semi-supervised methods.

<div>Structured prediction makes coherent decisions as structured objects to present the interrelations of these predicted variables. They have been widely used in many areas, such as bioinformatics, computer vision, speech recognition, and natural language processing. Machine Learning with reduced supervision aims to leverage the laborious and error-prone annotation effects and benefit the low-resource languages. In this dissertation we study structured prediction with reduced supervision for two sets of problems, sequence labeling and dependency parsing, both of which are representatives of structured prediction problems in NLP. We investigate three different approaches.</div><div> </div><div>The first approach is learning with modular architecture by task decomposition. By decomposing the labels into location sub-label and type sub-label, we designed neural modules to tackle these sub-labels respectively, with an additional module to infuse the information. The experiments on the benchmark datasets show the modular architecture outperforms existing models and can make use of partially labeled data together with fully labeled data to improve on the performance of using fully labeled data alone.</div><div><br></div><div>The second approach builds the neural CRF autoencoder (NCRFAE) model that combines a discriminative component and a generative component for semi-supervised sequence labeling. The model has a unified structure of shared parameters, using different loss functions for labeled and unlabeled data. We developed a variant of the EM algorithm for optimizing the model with tractable inference. The experiments on several languages in the POS tagging task show the model outperforms existing systems in both supervised and semi-supervised setup.</div><div><br></div><div>The third approach builds two models for semi-supervised dependency parsing, namely local autoencoding parser (LAP) and global autoencoding parser (GAP). LAP assumes the chain-structured sentence has a latent representation and uses this representation to construct the dependency tree, while GAP treats the dependency tree itself as a latent variable. Both models have unified structures for sentence with and without annotated parse tree. The experiments on several languages show both parsers can use unlabeled sentences to improve on the performance with labeled sentences alone, and LAP is faster while GAP outperforms existing models.</div>

<div>Many real-world domains are relational, consisting of objects (e.g., users and pa- pers) linked to each other in various ways. Because class labels in graphs are often only available for a subset of the nodes, semi-supervised learning for graphs has been studied extensively to predict the unobserved class labels. For example, we can pre- dict political views in a partially labeled social graph dataset and get expected gross incomes of movies in an actor/movie graph with a few labels. Recently, advances in representation learning for graph data have made great strides for the semi-supervised node classification. However, most of the methods have mainly focused on learning node representations by considering simple relational properties (e.g., random walk) or aggregating nearby attributes, and it is still challenging to learn complex inter- action patterns in partially labeled graphs and provide explanations on the learned representations. </div><div><br></div><div>In this dissertation, multiple methods are proposed to alleviate both challenges for semi-supervised node classification. First, we propose a graph neural network architecture, REGNN, that leverages local inferences for unlabeled nodes. REGNN performs graph convolution to enable label propagation via high-order paths and predicts class labels for unlabeled nodes. In particular, our proposed attention layer of REGNN measures the role equivalence among nodes and effectively reduces the noise, which is generated during the aggregation of observed labels from distant neighbors at various distances. Second, we also propose a neural network archi- tecture that jointly captures both temporal and static interaction patterns, which we call Temporal-Static-Graph-Net (TSGNet). The architecture learns a latent rep- resentation of each node in order to encode complex interaction patterns. Our key insight is that leveraging both a static neighbor encoder, that learns aggregate neigh- bor patterns, and a graph neural network-based recurrent unit, that captures complex interaction patterns, improves the performance of node classification. Lastly, in spite of better performance of representation learning on node classification tasks, neural network-based representation learning models are still less interpretable than the pre- vious relational learning models due to the lack of explanation methods. To address the problem, we show that nodes with high bridgeness scores have larger impacts on node embeddings such as DeepWalk, LINE, Struc2Vec, and PTE under perturbation. However, it is computationally heavy to get bridgeness scores, and we propose a novel gradient-based explanation method, GRAPH-wGD, to find nodes with high bridgeness efficiently. In our evaluations, our proposed architectures (REGNN and TSGNet) for semi-supervised node classification consistently improve predictive performance on real-world datasets. Our GRAPH-wGD also identifies important nodes as global explanations, which significantly change both predicted probabilities on node classification tasks and k-nearest neighbors in the embedding space after perturbing the highly ranked nodes and re-learning low-dimensional node representations for DeepWalk and LINE embedding methods.</div>

The supervised and semi-supervised machine learning paradigms hinge on the idea that the training data is labeled. The label quality is often brought into question, and problems related to noisy, inaccurate, or missing labels are studied. One of these is an interesting and prevalent problem in the semi-supervised classification area where only some positive labels are known. At the same time, the remaining and often the majority of the available data is unlabeled, i.e., there are no negative examples. Known as Positive-Unlabeled (PU) learning, this problem has been identified with increasing frequency across many disciplines, including but not limited to health science, biology, bioinformatics, geoscience, physics, business, and politics. Also, there are several closely related machine learning problems, such as cost-sensitive learning and mixture proportion estimation. This dissertation explores the PU learning problem from the perspective of density estimation and proposes a new modular method compatible with the relabeling framework that is common in PU learning literature. This approach is compared with two existing algorithms throughout the manuscript, one from a seminal work by Elkan and Noto and a current state-of-the-art algorithm by Ivanov. Furthermore, this thesis identifies two machine learning application domains that can benefit from PU learning approaches, which were not previously seen that way: predicting length of stay in hospitals and automatic music tagging. Experimental results with multiple synthetic and real-world datasets from different application domains validate the proposed approach. Accurately predicting the in-hospital length of stay (LOS) at the time of admission can positively impact healthcare metrics, particularly in novel response scenarios such as the Covid-19 pandemic. During the regular steady-state operation, traditional classification algorithms can be used for this purpose to inform planning and resource management. However, when there are sudden changes to the admission and patient statistics, such as during the onset of a pandemic, these approaches break down because reliable training data becomes available only gradually over time. This thesis demonstrates the effectiveness of PU learning approaches in such situations through experiments by simulating the positive-unlabeled scenario using two fully-labeled publicly available LOS datasets. Music auto-tagging systems are typically trained using tag labels provided by human listeners. In many cases, this labeling is weak, which means that the provided tags are valid for the associated tracks, but there can be tracks for which a tag would be valid but not present. This situation is analogous to PU learning with the additional complication of being a multi-label scenario. Experimental results on publicly available music datasets with tags representing three different labeling paradigms demonstrate the effectiveness of PU learning techniques in recovering the missing labels and improving auto-tagger performance. / Graduate

We tackle the task of semi-supervised video object segmentation, i.e, pixel-level object classification of the images in video sequences using very limited ground truth training data of its corresponding video. Recently introduced online adaptation of convolutional neural networks for video object segmentation (OnAVOS) has achieved good results by pretraining the network, fine-tuning on the first frame and training the network at test time using its approximate prediction as newly obtained ground truth. We propose Flow Adaptive Video Object Segmentation (FAVOS) that refines the generated adaptive ground truth for online updates and utilizes temporal consistency between video frames with the help of optical flow. We validate our approach on the DAVIS Challenge and achieve rank 1 results on the DAVIS 2016 Challenge (single-object segmentation) and competitive scores on both DAVIS 2018 Semi-supervised Challenge and Interactive Challenge (multi-object segmentation). While most models tend to have increasing complexity for the challenging task of video object segmentation, FAVOS provides a simple and efficient pipeline that produces accurate predictions.

Cette thèse a pour objectif d'améliorer la classification d'objets sous-marins dans des images sonar haute résolution. En particulier, il s'agit de distinguer les mines des objets inoffensifs parmi une collection d'objets ressemblant à des mines. Nos recherches ont été dirigées par deux contraintes classiques en guerre de la mine : d'une part, le manque de données et d'autre part, le besoin de lisibilité des décisions. Nous avons donc constitué une base de données la plus représentative possible et simulé des objets dans le but de la compléter. Le manque d'exemples nous a mené à utiliser une représentation compacte, issue de la reconnaissance de visages : les Structural Binary Gradient Patterns (SBGP). Dans la même optique, nous avons dérivé une méthode d'adaptation de domaine semi-supervisée, basée sur le transport optimal, qui peut être facilement interprétable. Enfin, nous avons développé un nouvel algorithme de classification : les Ensemble of Exemplar-Maximum Excluding Ball (EE-MEB) qui sont à la fois adaptés à des petits jeux de données mais dont la décision est également aisément analysable / This thesis aims to improve the classification of underwater objects in high resolution sonar images. Especially, we seek to make the distinction between mines and harmless objects from a collection of mine-like objects. Our research was led by two classical constraints of the mine warfare : firstly, the lack of data and secondly, the need for readability of the classification. In this context, we built a database as much representative as possible and simulated objects in order to complete it. The lack of examples led us to use a compact representation, originally used by the face recognition community : the Structural Binary Gradient Patterns (SBGP). To the same end, we derived a method of semi-supervised domain adaptation, based on optimal transport, that can be easily interpreted. Finally, we developed a new classification algorithm : the Ensemble of Exemplar-Maximum Excluding Ball (EE-MEB) which is suitable for small datasets and with an easily interpretable decision function

Understanding travel behavior and identifying the mode of transportation are essential for adequate urban devising and transportation planning. Global positioning systems (GPS) tracking data is mainly used to find human mobility patterns in cities. Some travel information, such as most visited location, temporal changes, and the trip speed, can be easily extracted from GPS raw tracking data. GPS trajectories can be used as a method to indicate the mobility modes of commuters. Most previous studies have applied traditional machine learning algorithms and manually computed data features, making the model error-prone. Thus, there is a demand for developing a new model to resolve these methods' weaknesses. The primary purpose of this study is to propose a semi-supervised model to identify transportation mode by using a contemporary machine learning algorithm and GPS tracking data. The model can accept GPS trajectory with adjustable length and extracts their latent information with LSTM Autoencoder. This study adopts a deep neural network architecture with three hidden layers to map the latent information to detect transportation mode. Moreover, different case studies are performed to evaluate the proposed model's efficiency. The model results in an accuracy of 93.6%, which significantly outperforms similar studies.