Autonomous navigation in outdoor, unstructured environments is one of the major challenges presents in the robotics field. One of its applications, intelligent autonomous vehicles, has the potential to decrease the number of accidents on roads and highways, increase the efficiency of traffic on major cities and contribute to the mobility of the disabled and elderly. For a robot/vehicle to safely navigate, accurate detection of navigable areas is essential. In this work, we address the task of visual road detection where, given an image, the objective is to classify its pixels into road or non-road. Instead of trying to manually derive an analytical solution for the task, we have used machine learning (ML) to learn it from a set of manually created samples. We have applied both traditional (shallow) and deep ML models to the task. Our main contribution regarding traditional ML models is an efficient and versatile way to aggregate spatially distant features, effectively providing a spatial context to such models. As for deep learning models, we have proposed a new neural network architecture focused on processing time and a new neural network layer called the semi-global layer, which efficiently provides a global context for the model. All the proposed methodology has been evaluated in the Karlsruhe Institute of Technology (KIT) road detection benchmark, achieving, in all cases, competitive results. / A navegação autônoma em ambientes externos não estruturados é um dos maiores desafios no campo da robótica. Uma das suas aplicações, os veículos inteligentes autônomos, tem o potencial de diminuir o número de acidentes nas estradas e rodovias, aumentar a eficiência do tráfego nas grandes cidades e contribuir para melhoria da mobilidade de deficientes e idosos. Para que um robô/veículo navegue com segurança, uma detecção precisa de áreas navegáveis é essencial. Neste trabalho, abordamos a tarefa de detecção visual de ruas onde, dada uma imagem, o objetivo é classificar cada um de seus pixels em rua ou não-rua. Ao invés de tentar derivar manualmente uma solução analítica para a tarefa, usamos aprendizado de máquina (AM) para aprendê-la a partir de um conjunto de amostras criadas manualmente. Nós utilizamos tanto modelos tradicionais (superficiais) quanto modelos profundos para a tarefa. A nossa principal contribuição em relação aos modelos tradicionais é uma forma eficiente e versátil de agregar características espacialmente distantes, fornecendo efetivamente um contexto espacial para esses modelos. Quanto aos modelos de aprendizagem profunda, propusemos uma nova arquitetura de rede neural focada no tempo de processamento e uma nova camada de rede neural, chamada camada semi-global, que fornece eficientemente um contexto global ao modelo. Toda a metodologia proposta foi avaliada no benchmark de detecção de ruas do Instituto de Tecnologia de Karlsruhe, alcançando, em todos os casos, resultados competitivos.

Treinamento semi-supervisionado é uma metodologia de aprendizado de máquina que conjuga características de treinamento supervisionado e não-supervisionado. Ela se baseia no uso de bases semi-rotuladas (bases contendo dados rotulados e não-rotulados) para o treinamento de classificadores. A adição de dados não-rotulados, mais baratos e geralmente disponíveis em maior quantidade do que os dados rotulados, pode aumentar o desempenho e/ou baratear o custo de treinamento desses classificadores (a partir da diminuição da quantidade de dados rotulados necessários). Esta dissertação analisa duas estratégias para se executar treinamento semi-supervisionado, especificamente em Support Vector Machines (SVMs): formas direta e indireta. A estratégia direta é atualmente mais conhecida e estudada, e permite o uso de dados rotulados e não-rotulados, ao mesmo tempo, em tarefas de aprendizagem de classificadores. Entretanto, a inclusão de muitos dados não-rotulados pode tornar o treinamento demasiadamente lento. Já a estratégia indireta é mais recente, sendo capaz de agregar os benefícios do treinamento semi-supervisionado direto com tempos menores para o aprendizado de classificadores. Esta opção utiliza os dados não-rotulados para pré-processar a base de dados previamente à tarefa de aprendizagem do classificador, permitindo, por exemplo, a filtragem de eventuais ruídos e a reescrita da base em espaços de variáveis mais convenientes. Dentro do escopo da forma indireta, está a principal contribuição dessa dissertação: idealização, implementação e análise do algoritmo split learning. Foram obtidos ótimos resultados com esse algoritmo, que se mostrou eficiente em treinar SVMs de melhor desempenho e em períodos menores a partir de bases semi-rotuladas. / Semi-supervised learning is a machine learning methodology that mixes features of supervised and unsupervised learning. It allows the use of partially labeled databases (databases with labeled and unlabeled data) to train classifiers. The addition of unlabeled data, which are cheaper and generally more available than labeled data, can enhance the performance and/or decrease the costs of learning such classifiers (by diminishing the quantity of required labeled data). This work analyzes two strategies to perform semi-supervised learning, specifically with Support Vector Machines (SVMs): direct and indirect concepts. The direct strategy is currently more popular and studied; it allows the use of labeled and unlabeled data, concomitantly, in learning classifiers tasks. However, the addition of many unlabeled data can lead to very long training times. The indirect strategy is more recent; it is able to attain the advantages of the direct semi-supervised learning with shorter training times. This alternative uses the unlabeled data to pre-process the database prior to the learning task; it allows denoising and rewriting the data in better feature espaces. The main contribution of this Master thesis lies within the indirect strategy: conceptualization, experimentation, and analysis of the split learning algorithm, that can be used to perform indirect semi-supervised learning using SVMs. We have obtained promising empirical results with this algorithm, which is efficient to train better performance SVMs in shorter times from partially labeled databases.

Em diversos domínios, além das informações sobre os objetos ou entidades que os compõem, existem, também, informaçõoes a respeito das relações entre esses objetos. Alguns desses domínios são, por exemplo, as redes de co-autoria, e as páginas Web. Nesse sentido, é natural procurar por técnicas de classificação que levem em conta estas informações. Dentre essas técnicas estão as denominadas classificação baseada em grafos, que visam classificar os exemplos levando em conta as relações existentes entre eles. Este trabalho aborda o desenvolvimento de métodos para melhorar o desempenho de classificadores baseados em grafos utilizando estratégias de ensembles. Um classificador ensemble considera um conjunto de classificadores cujas predições individuais são combinadas de alguma forma. Este classificador normalmente apresenta um melhor desempenho do que seus classificadores individualmente. Assim, foram desenvolvidas três técnicas: a primeira para dados originalmente no formato proposicional e transformados para formato relacional baseado em grafo e a segunda e terceira para dados originalmente já no formato de grafo. A primeira técnica, inspirada no algoritmo de boosting, originou o algoritmo KNN Adaptativo Baseado em Grafos (A-KNN). A segunda ténica, inspirada no algoritmo de Bagging originou trê abordagens de Bagging Baseado em Grafos (BG). Finalmente, a terceira técnica, inspirada no algoritmo de Cross-Validated Committees, originou o Cross-Validated Committees Baseado em Grafos (CVCG). Os experimentos foram realizados em 38 conjuntos de dados, sendo 22 conjuntos proposicionais e 16 conjuntos no formato relacional. Na avaliação foi utilizado o esquema de 10-fold stratified cross-validation e para determinar diferenças estatísticas entre classificadores foi utilizado o método proposto por Demsar (2006). Em relação aos resultados, as três técnicas melhoraram ou mantiveram o desempenho dos classificadores bases. Concluindo, ensembles aplicados em classificadores baseados em grafos apresentam bons resultados no desempenho destes / In many fields, besides information about the objects or entities that compose them, there is also information about the relationships between objects. Some of these fields are, for example, co-authorship networks and Web pages. Therefore, it is natural to search for classification techniques that take into account this information. Among these techniques are the so-called graphbased classification, which seek to classify examples taking into account the relationships between them. This paper presents the development of methods to improve the performance of graph-based classifiers by using strategies of ensembles. An ensemble classifier considers a set of classifiers whose individual predictions are combined in some way. This combined classifier usually performs better than its individual classifiers. Three techniques have been developed: the first applied for originally propositional data transformed to relational format based on graphs and the second and the third applied for data originally in graph format. The first technique, inspired by the boosting algorithm originated the Adaptive Graph-Based K-Nearest Neighbor (A-KNN). The second technique, inspired by the bagging algorithm led to three approaches of Graph-Based Bagging (BG). Finally the third technique, inspired by the Cross- Validated Committees algorithm led to the Graph-Based Cross-Validated Committees (CVCG). The experiments were performed on 38 data sets, 22 datasets in propositional format and 16 in relational format. Evaluation was performed using the scheme of 10-fold stratified cross-validation and to determine statistical differences between the classifiers it was used the method proposed by Demsar (2006). Regarding the results, these three techniques improved or at least maintain the performance of the base classifiers. In conclusion, ensembles applied to graph-based classifiers have good results in the performance of them

O aprendizado de máquina consiste em conceitos e técnicas que permitem aos computadores melhorar seu desempenho com a experiência, ou em outras palavras, aprender com dados. Duas de suas principais categorias são o aprendizado não-supervisionado e o semissupervisionado, que respectivamente consistem em inferir padrões em bases cujos dados não têm rótulo (classe) e classificar dados em bases parcialmente rotuladas. Embora muito estudado, trata-se de um campo repleto de desafios e com muitos tópicos abertos. Sistemas dinâmicos coletivos, por sua vez, são sistemas constituídos por muitos indivíduos, cada qual um sistema dinâmico por si só, de modo que todos eles agem coletivamente, ou seja, a ação de cada indivíduo é influenciada pela ação dos vizinhos. Uma característica notável desses sistemas é que padrões globais podem surgir espontaneamente das interações locais entre os indivíduos, fenômeno conhecido como emergência. Os desafios intrínsecos e a relevância do tema vêm motivando sua pesquisa em diversos ramos da ciência e da engenharia. Este trabalho de doutorado consiste no desenvolvimento e análise de modelos dinâmicos coletivos para o aprendizado de máquina, especificamente suas categorias não-supervisionada e semissupervisionada. As tarefas de segmentação de imagens e de detecção de comunidades em redes, que de certo modo podem ser entendidas como tarefas do aprendizado de máquina, são também abordadas. Em especial, desenvolvem-se modelos nos quais a movimentação dos objetos é determinada pela localização e velocidade de seus vizinhos. O sistema dinâmico assim modelado é então conduzido a um estado cujo padrão formado por seus indivíduos realça padrões subjacentes do conjunto de dados. Devido ao seu caráter auto-organizável, os modelos aqui desenvolvidos são robustos e as informações geradas durante o processo (valores das variáveis do sistema) são ricas e podem, por exemplo, revelar características para realizar soft labeling e determinar classes sobrepostas. / Machine learning consists of concepts and techniques that enable computers to improve their performance with experience, i.e., learn from data. Unsupervised and semi-supervised learning are important categories of machine learning, which respectively consists of inferring patterns in datasets whose data have no label (class) and classifying data in partially-labeled datasets. Although intensively studied, machine learning is still a field full of challenges and with many open topics. Collective dynamical systems, in turn, are systems made of a large group of individuals, each one a dynamical system by itself, such that all of them behave collectively, i.e., the action of each individual is influenced by the action of its neighbors. A remarkable feature of those systems is that global patterns may spontaneously emerge from the local interactions among individuals, a phenomenon known as emergence. Their relevance and intrinsic challenges motivate research in various branches of science and engineering. In this doctorate research, we develop and analyze collective dynamical models for their usage in machine-learning tasks, specifically unsupervised and semi-supervised ones. Image segmentation and network community detection are also addressed, as they are related to machine learning as well. In particular, we propose to work on models in which the objects motion is determined by the location and velocity of their neighbors. By doing so, the dynamical system reaches a configuration in which the patterns developed by the set of individuals highlight underlying patterns of the dataset. Due to their self-organizing nature, it is also expected that the models can be robust and the information generated during the process (values of the system variables) can be rich and reveal, for example, features to perform soft labeling and determine overlapping classes.

Em aplicações de sensoriamento remoto, há diversos problemas nos quais há conhecimento predominante sobre uma categoria ou classe alvo, e pouco conhecimento sobre as demais categorias. Nesses casos, o treinamento de um classificador é prejudicado pelo desbalanceamento de classes. Assim, o estudo de características visuais para se definir o melhor subespaço de características pode ser uma alternativa viável para melhorar o desempenho dos classificadores. O uso de abordagens baseadas em detecção de anomalias também pode auxiliar por meio da modelagem da classe normal (comumente majoritária) enquanto todas as outras classes são consideradas como anomalias. Este estudo apresentou uma base de imagens de sensoriamento remoto, cuja aplicação é identificar entre regiões de cobertura vegetal e regiões de não cobertura vegetal. Para solucionar o problema de desbalanceamento entre as classes, foram realizados estudos das características visuais a fim de definir qual o conjunto de atributos que melhor representa os dados. Também foi proposta a criação de um pipeline para se tratar bases desbalanceadas de cobertura vegetal. Este pipeline fez uso de técnicas de seleção de características e aprendizado ativo. A análise de características apresentou que o subespaço usando o extrator BIC com o índice de vegetação ExG foi o que melhor distinguiu os dados. Além disso, a técnica de ordenação proposta mostrou bom desempenho com poucas dimensões. O aprendizado ativo também ajudou na criação de um modelo melhor, com resultados comparáveis com as melhores características visuais. / In remote sensing applications, there are several problems in which there is predominant knowledge about a target category or class, and little knowledge of the other categories. In such cases, the training of a classifier is hampered by the class imbalance. Thus, the study of visual characteristics to determine the best subspace characteristics may be a feasible alternative to improve the performance of classifiers. The use of anomaly detection-based approaches can also help through the normal class modeling (usually the major class) while considering all other classes as anomalies. This study presents a remote sensing image dataset, whose application is to classify regions of the image into vegetation coverage (related to plantation) and non-vegetation coverage. To solve the class imbalance problem, studies were conducted using several visual characteristics in order to define the set of attributes that best represent the data. A pipeline that deals with the vegetation classification problem and its class imbalance issues is also proposed. This pipeline made use of feature selection techniques and active learning. The visual features analysis showed that a subspace using the BIC extractor with EXG vegetation index was the best to distinguished the data. Also, and the proposed sorting-based feature selection achieved good results with a low dimensional subspaces. Furthermore, the active learning helped creating a better model, with results comparable with the best visual features.

A coleta e a exploração de corpora para a criação de atividades é um tema cada vez mais recorrente, uma vez que a prática visa a garantir materiais de ensino que privilegiam a língua em uso. A disponibilidade de instrumentação computacional para análise de corpora é enorme, assim como o seu potencial para o ensino de línguas. Apesar dos benefícios, o uso desses recursos ainda não é uma realidade para a maioria dos professores, principalmente fora do contexto acadêmico. Nesta tese, desenvolve-se um sistema de análise de textos e corpora e de criação automática de atividades de leitura e ensino de léxico-gramática em língua inglesa, com base na investigação das possibilidades de construção e exploração de corpora da Linguística de Corpus em diálogo com métodos e ferramentas de trabalho das áreas do Processamento de Línguas Naturais e Aprendizado de Máquina. Os objetivos da pesquisa estão relacionados a um estudo inicial que teve como produto final um software desktop para a preparação semiautomática de atividades de leitura em inglês, segundo o conceito de atividade-padrão, para facilitar a produção de materiais baseados em corpora. A proposta da tese concentra-se na automatização das análises linguísticas para a criação automática de atividades de ensino. Para tanto, a linguagem de programação Python, com a biblioteca Natural Language Toolkit (NLTK), foi utilizada na construção de módulos de análise de texto e corpora. Os principais corpora foram: a. o corpus de referência British National Corpus (BNC); b. o corpus de referência Floresta Sinta(c)tica do NLTK; c. o corpus de referência MacMorpho do NLTK; d. um corpus de estudo/treinamento com 135 textos de anúncios de emprego em inglês da Internet; e. um corpus de estudo/treinamento com 771 textos de divulgação científica das revistas eletrônicas Scientific American e NewScientist. A partir das análises automáticas programadas, foram criados modelos em XML, que extraem informações de texto e corpus para a criação de atividades. Uma interface gráfica foi desenhada para implementação do sistema, por meio das linguagens PHP, JavaScript, HTML e CSS, e disponibilizada online para a avaliação de possíveis usuários finais. A análise das avaliações mostrou-se positiva tanto em relação a aspectos da interface quanto a informações geradas pelo sistema. Os resultados obtidos no trabalho são significativos, pois sugerem que o sistema proposto, que permite a automatização de análises de texto e corpora para a criação automática de atividades didáticas de leitura e ensino de léxico-gramática em língua inglesa, apresenta um diferencial em relação a ferramentas disponíveis para análise de textos: fornece análises mais apuradas para a tarefa de elaboração de atividades didáticas, quando comparado, por exemplo, a programas como concordanciadores. Dentre as contribuições do trabalho, destacam-se o percurso do desenvolvimento do sistema como parte integrante da pesquisa, o diálogo entre as Humanidades a Linguística e a Língua Inglesa e as Ciências Exatas a Computação, com o Processamento de Línguas Naturais e o Aprendizado de Máquina , e a automatização de tarefas de análise de textos para fins de criação de materiais pedagógicos para o ensino de línguas. / Collecting and analyzing corpora in order to create activities is a topic that has risen by leaps and bounds, since practice is aimed at ensuring that the teaching material is focused on the language currently in use. There is a great amount of computer devices available for corpora analysis, and its potential for teaching languages is evident. Even though they present huge benefits, most of the teachers do not take advantage of these resources yet, chiefly when they do not take part in the academic environment. Through this thesis, a system for analysis of text and corpora and automatic creation of reading and English lexical-grammar teaching activities is developed, based on the investigation of possible ways of collecting and analyzing corpora from Corpus Linguistics, in partnership with methods and working tools related to Natural Language Processing and Machine Learning. The purpose for this research is related to an initial study that resulted in a desktop software that semi-automatically prepares reading activities in English, based on the standard-activity concept, in order to facilitate the creation of corpora-based material. This thesis puts forward the automatization of linguistic analyses so that teaching activities may be created automatically. For this purpose, the programming language Python, together with the Natural Language Toolkit (NLTK) library, was used for the creation of text-analysis and corpora modules. The main corpora used were: a. British National Corpus (BNC) reference corpus; b. Floresta Sinta(c)tica reference corpus from NLTK; c. MacMorpho reference corpus from NLTK; d. a study/training corpus with 135 texts of job announcements in English taken from the Internet; e. a study/training corpus with 771 texts of scientific disclosure of the following e-magazines: Scientific American and NewScientist. As from the scheduled automatic analyses, some XML models were created; they gather information about texts and corpus in order to create activities. A graphic interface was designed with the purpose of implementing the system by means of PHP, JavaScript, HTML and CSS languages and made available online, so that it could be evaluated by potential final users. The evaluations analysis had a positive outcome, both in relation to interface aspects and information provided by the system. The outcome of this work is meaningful, since this new system, which allows for the automatization of text and corpora analyses in order to create reading and English lexical-grammar activities, has a differential with regard to the tools available to analyze texts: it allows for more accurate analyses for the task of creating teaching activities, when it is compared, for instance, to softwares such as the concordance ones. Among the contributions to this work, it is important to highlight the system development process as an integral part of the research, the dialog between the Humanities Linguistics and English language and the Exact Sciences Computing, with the Natural Language Processing and the Machine Learning , as well as the automatization of text-analysis tasks in order to create teaching material for language teaching.

Apesar do grau relativamente alto de maturidade existente na área de pesquisa de aprendizado supervisionado em lote, na qual são utilizados dados originários de problemas estacionários, muitas aplicações reais lidam com fluxos de dados cujas distribuições de probabilidade se alteram com o tempo, ocasionando mudanças de conceito. Diversas pesquisas vêm sendo realizadas nos últimos anos com o objetivo de criar modelos precisos mesmo na presença de mudanças de conceito. A maioria delas, no entanto, assume que tão logo um evento seja classificado pelo algoritmo de aprendizado, seu rótulo verdadeiro se torna conhecido. Este trabalho explora as situações complementares, com revisão dos trabalhos mais importantes publicados e análise do impacto de atraso na disponibilidade dos rótulos verdadeiros ou sua não disponibilização. Ainda, propõe um novo algoritmo que reduz drasticamente a complexidade de aplicação do teste de hipótese não-paramétrico Kolmogorov-Smirnov, tornado eficiente seu uso em algoritmos que analisem fluxos de dados. A exemplo, mostramos sua potencial aplicação em um método de detecção de mudança de conceito não-supervisionado que, em conjunto com técnicas de Aprendizado Ativo e Aprendizado por Transferência, reduz a necessidade de rótulos verdadeiros para manter boa performance de um classificador ao longo do tempo, mesmo com a ocorrência de mudanças de conceito. / Despite the relatively maturity of batch-mode supervised learning research, in which the data typifies stationary problems, many real world applications deal with data streams whose statistical distribution changes over time, causing what is known as concept drift. A large body of research has been done in the last years, with the objective of creating new models that are accurate even in the presence of concept drifts. However, most of them assume that, once the classification algorithm labels an event, its actual label become readily available. This work explores the complementary situations, with a review of the most important published works and an analysis over the impact of delayed true labeling, including no true label availability at all. Furthermore, this work proposes a new algorithm that heavily reduces the complexity of applying Kolmogorov- Smirnov non-parametric hypotheis test, turning it into an uselful tool for analysis on data streams. As an instantiation of its usefulness, we present an unsupervised drift-detection method that, along with Active Learning and Transfer Learning approaches, decreases the number of true labels that are required to keep good classification performance over time, even in the presence of concept drifts.

The state of the art in machine learning of Boolean functions is to learn a hypothesis h, which is similar to a target hypothesis f, using a training sample of size N and a family of a priori models in a given hypothesis set H, such that h must belong to some model in this family. An important characteristic in learning is that h should also predict outcome values of f for previously unseen data, so the learning algorithm should minimize the generalization error which is the discrepancy measure between outcome values of f and h. The method proposed in this thesis learns family of models compatible with training samples of size N. Taking into account that generalizations are performed through equivalence classes in the Boolean function domain, the search space for finding the correct model is the projection of H in all possible partitions of the domain. This projection can be seen as a model lattice which is anti-isomorphic to the partition lattice and also has the property that for every chain in the lattice there exists a relation order given by the VC dimension of the models. Hence, we propose a model selector that uses the model lattice for selecting the best model with VC dimension compatible to a training sample of size N, which is closely related to the classical sample complexity theorem. Moreover, this model selector generalizes a set of learning methods in the literature (i.e, it unifies methods such as: the feature selection problem, multiresolution representation and decision tree representation) using models generated from a subset of partitions of the partition space. Furthermore, considering as measure associated to the models the estimated error of the learned hypothesis, the chains in the lattice present the so-called U-curve phenomenon. Therefore, we can use U-curve search algorithms in the model lattice to select the best models and, consequently, the corresponding VC dimension. However, this new generation of learning algorithms requires an increment of computational power. In order to face this problem, we introduce a stochastic U-curve algorithm to work on bigger lattices. Stochastic search algorithms do not guarantee finding optimal solutions, but maximize the mean quality of the solution for a given amount of computational power. The contribution of this thesis advances both the state of the art in machine learning theory and in practical problem solutions in learning. / O estado da arte em aprendizado de funções Booleanas é aprender uma hipótese h, que é similar a uma hipótese objetivo f, a partir de uma amostra de tamanho N e uma família de modelos a priori em um dado conjunto de hipóteses H, tal que h deve pertencer a algum modelo nesta família. Uma característica importante no aprendizado é que h deve também predizer resultados de f para elementos que não aparecem no conjunto de treinamento, então o algoritmo de aprendizado deve minimizar o erro de generalização, o qual mede a discrepância entre os resultados de f e h. O método proposto nesta tese aprende uma família de modelos compatíveis com um conjunto de treinamento de tamanho N. Tomando em consideração que as generalizações são realizadas através de classes de equivalência no domínio da função Booleana, o espaço de busca para encontrar um modelo apropriado é a projeção de H em todas as possíveis partições do domínio. Esta projeção pode ser vista como um reticulado de modelos que é anti-isomórfica ao reticulado de partições e também tem a propriedade que para cada cadeia no reticulado existe uma relação de ordem dada pela dimensão VC dos modelos. Portanto, propomos um seletor de modelos que usa o reticulado de modelos para selecionar o melhor modelo com dimensão VC compatível ao conjunto de treinamento de tamanho N, o qual é intimamente relacionado ao teorema clássico de complexidade da amostra. Além disso, este seletor de modelos generaliza um conjunto de métodos de aprendizado na literatura (i.e, ele unifica métodos tais como: o problema de seleção de características, a representação multiresolução e a representação por árvores de decisão) usando modelos gerados por um subconjunto de partições do espaço de partições. Ademais, considerando como medida associada aos modelos o erro de estimação da hipótese aprendida, as cadeias no reticulado apresentam o fenômeno chamado U-curve. Portanto, podemos usar algoritmos de busca $U$-curve no reticulado de modelos para selecionar os melhores modelos, consequentemente, a correspondente dimensão VC. No entanto, esta nova geração de algoritmos de aprendizado requerem um incremento de poder computacional. Para enfrentar este problema, introduzimos o algoritmo Stochastic $U$-curve para trabalhar em reticulados maiores. Algoritmos de busca estocásticos não garantem encontrar soluções ótimas, mas maximizam a qualidade média das soluções para uma determinada quantidade de poder computacional. A contribuição desta tese avança ambos o estado da arte na teoria de aprendizado de máquina e soluções a problemas práticos em aprendizado.

As Interfaces Cérebro-Computador (do inglês Brain-Computer Interfaces BCI) são sistemas que visam permitir a interação entre usuários e máquinas por meio do monitoramento das atividades cerebrais. Sistemas de BCI são considerados como uma alternativa para que pessoas com perda severa ou total do controle motor, tais como as que sofrem de Esclerose Lateral Amiotrófica, possam contar com algum controle sobre o ambiente externo. Para mapear intenções individuais em operações de máquina, os sistemas de BCI empregam um conjunto de etapas que envolvem a captura e pré-processamento dos sinais cerebrais, a extração e seleção de suas características mais relevantes e a classificação das intenções. O projeto e a implementação de sistemas de BCI viáveis ainda são questões em aberto devido aos grandes desafios encontrados em cada uma de suas etapas. Esta lacuna motivou este trabalho de mestrado o qual apresenta uma avaliação dos principais extratores de características utilizados para classificar ensaios de imagética motora, cujos dados foram obtidos por meio de eletroencefalografia (EEG) e apresentam influências de artefatos, mais precisamente daqueles produzidos por interferências provenientes de atividades oculares (monitoradas por eletrooculografia EOG). Foram considerados sinais coletados pela BCI Competition IV-2b, os quais contêm informações sobre três canais de EEG e três outros de EOG. Como primeira etapa, foi realizado o pré-processamento desses canais utilizando a técnica de Análise de Componentes Independentes (ICA) em conjunto com um limiar de correlação para a remoção de componentes associados a artefatos oculares. Posteriormente, foram avaliadas diferentes abordagens para a extração de características, a mencionar: i) Árvore Diádica de Bandas de Frequências (ADBF); ii) Padrões Espaciais Comuns (CSP); iii) Padrões Espectro-Espaciais Comuns (CSSP); iv) Padrões Esparsos Espectro-Espaciais Comuns (CSSSP); v) CSP com banco de filtros (FBCSP); vi) CSSP com banco de filtros (FBCSSP); e, finalmente, vii) CSSSP com banco de filtros (FBCSSSP). Contudo, como essas técnicas podem produzir espaços de exemplos com alta dimensionalidade, considerou-se, também, a técnica de Seleção de Características baseada em Informação Mútua (MIFS) para escolher os atributos mais relevantes para o conjunto de dados adotado na etapa de classificação. Finalmente, as Máquinas de Vetores de Suporte (SVM) foram utilizadas para a classificação das intenções de usuários. Experimentos permitem concluir que os resultados do CSSSP e FBCSSSP são equiparáveis àqueles produzidos pelo estado da arte, considerando o teste de significância estatística de Wilcoxon bilateral com confiança de 0, 95. Apesar disso o CSSSP tem sido negligenciado pela área devido ao fato de sua parametrização ser considerada complexa, algo que foi automatizado neste trabalho. Essa automatização reduziu custos computacionais envolvidos na adaptação das abordagens para indivíduos específicos. Ademais, conclui-se que os extratores de características FBCSP, CSSP, CSSSP, FBCSSP e FBCSSSP não necessitam da etapa de remoção de artefatos oculares, pois efetuam filtragens por meio de modelos autoregressivos. / Brain-Computer Interfaces (BCI) employ brain imaging to enable human-machine interaction without physical control. BCIs are an alternative so that people suffering from severe or complete loss of motor control, like those with Amyotrophic Lateral Sclerosis (ALS), may have some interaction with the external environment. To transform individual intentions onto machine operations, BCIs rely on a series of steps that include brain signal acquisition and preprocessing, feature extraction, selection and classification. A viable BCI implementation is still an open question due to the great challenges involved in each one of these steps. This gap motivated this work, which presents an evaluation of themain feature extractors used to classify Motor Imagery trials, whose data were obtained through Electroencephalography (EEG) influenced by ocular activity, monitored by Electrooculography (EOG). In this sense, signals acquired by BCI Competition IV-2b, were considered. As first step the preprocessing was performed through Independent Component Analysis (ICA) together with a correlation threshold to identify components associated with ocular artifacts. Afterwards, different feature extraction approaches were evaluated: i) Frequency Subband Dyadic Three; ii) Common Spatial Patterns (CSP); iii) Common Spectral-Spatial Patterns (CSSP); iv) Common Sparse Spectral-Spatial Patterns (CSSSP); v) Filter Bank Common Spatial Patterns (FBCSP); vi) Filter Bank Common Sectral-Spatial Patterns (FBCSSP); and, finally, vii) Filter Bank Sparse Spectral- Spatial Patterns (FBCSSSP). These techniques tend to produce high-dimensional spaces, so a Mutual Information-based Feature Selection was considered to select signal attributes. Finally, Support Vector Machines were trained to tackle the Motor Imagery classification. Experimental results allow to conclude that CSSSP and FBCSSSP are statistically equivalent the state of the art, when two-sided Wilcoxon test with 0, 95 confidence is considered. Nevertheless, CSSSP has been neglected by this area due to its complex parametrization, which is addressed in this work using an automatic approach. This automation reduced computational costs involved in adapting the BCI system to specific individuals. In addition, the FBCSP, CSSP, CSSSP, FBCSSP and FBCSSSP confirm to be robust to artifacts as they implicitly filter the signals through autoregressive models.

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.