Novas abordagens de aprendizado semisupervisionado por conectividade ótima

Abstract

The annotation of large data sets by a classifier is a problem whose challenge increases as the number of supervised samples available to train the classifier reduces in comparison to the number of unsupervised samples. In this context, semi-supervised learning methods aim at discovering and propagating labels to informative samples among the unsupervised ones, such that their addition to the correct class in the training set can improve the classification performance. This PhD thesis presents a series of novel semi-supervised learning approaches based on the Optimum-Path Forest (OPF) methodology. This methodology interprets the pattern recognition problem as a graph search problem, where the nodes are the training samples, the arcs are defined by a given adjacency relation, and the paths are assessed by some connectivity function. It identifies key nodes (prototypes) among the training samples and performs a competition process among them, such that each sample is conquered by the prototype that offers an optimum path to it. The result is a classifier — optimum-path forest rooted at the prototype set — which assigns labels to new samples by assessing extended paths to them. Classifiers can be created by one or multiple executions of the OPF algorithm for different graphs and connectivity functions. We present two approaches (OPFSEMI and its optimized version, OPFSEMImst) for the single-label problem, which differ from one another with respect to the final prototypes and number of executions of the OPF algorithm. We also propose a semi-supervised approach more suitable for the multi-label problem than the previous ones. This is a challenging problem, especially when it relies on the transformation of multi-label data into single-label data, which might affect performance at the boundary between classes. To resolve this problem, we improve the multi-label assignment by adding a final step in the training process of OPFSEMImst. The method, called OPFSEMImst+knn, creates an optimum-path forest rooted at the maxima of a probability density function, as estimated from a k-NN graph. Finally, we propose an active learning approach based on OPFSEMImst (OPFSEMI). The method selects informative samples for expert supervision, such that the number of active learning iterations (user effort) is reduced.