Contributions to support vector machine classifier

Abstract

Nas últimas décadas a área de aprendizado de máquina tem se tornado cada vez mais presente da tecnologia da informação. Com o aumento crescente da quantidade de dados disponíveis, a tarefa de automaticamente descobrir padrões nos dados tem sido realçada pelas pesquisas acadêmicas e do meio industrial. Um método para identificar padrões é estimar uma função que se aproxima do comportamento dos dados disponí- veis, e para criar uma função com capacidade de aprendizagem é necessária conter os seguintes tópicos: uma teoria baseada no princípio da indução e a possibilidade de incluir conhecimento passado. Nesta tese o foco é no algoritmo de Máquina de Vetores de Suporte (Support Vector Machine, SVM) para tarefas de classificação de dados, in- troduzido em meados dos anos 90. Desta forma, é necessário analisar vários aspectos do SVM, incluindo a formulação, métodos de treinamento, o ajuste de hiperparâmetros e a aplicabilidade em conjunto de dados de diferentes tamanhos e finalidades. Base- ado nessas análises, nós fizemos três propostas de contribuição. Dada a complexidade computacional do SVM, na primeira contribuição, propõe-se um método para viabilizar o uso do SVM em grandes conjuntos de dados (por exemplo nos casos em que não é possível carregar todo o conjunto de dados na memória disponível) por meio da pré- seleção de instâncias candidatas que são mais provaveis a melhorar a performance do erro de generalização. O objetivo do método é diminuir o tempo dos processos de treinamento e ajuste de hiperparâmetros do SVM degradando o mínimo possível o erro de generalização. A segunda contribuição está relacionada com a tarefa de ajuste de hyperparâmetros, que dependendo do caso pode ser demorada. A utilização do SVM com uma função kernel fornece uma liberdade que viabiliza aplicar o método em muitas situações, contudo, a escolha dos hiperparâmetros pode ser uma desvantagem. Desta forma, nós propõe-se um método para ajuste dos hiperparâmetros que utiliza um mínimo local pré-definido como critério de parada e possui um mecanismo para escapar de eventuais locais mínimos. Muitas tentativas foram realizadas para abordar os problemas do SVM relacionados ao custo computacional, aprendizado incremental e consumo de memória relacionado a ambos. Na última contribuição, introduz-se uma nova variação do SVM com uma complexidade computacional menor comparado ao SVM original, que é capaz de li- dar com procedimentos incrementais e decrementais (sem a necessidade de retreinar completamente), e é eficiente no gerenciamento de memória. A fim de lidar com gran- des conjuntos de dados nos problemas de aprendizado nós propõe-se um método de amostragem passiva que seleciona um sub-conjunto dos conjuntos de treinamento disponível diminuindo a necessidade de recurso computacional, porém, mantendo a capacidade de generalização. Os resultados do protocolo experimental mostra que o método proposto pré-seleciona instâncias que tem mais chance de serem vetores de suporte (e seus respectivos vizinhos) mesmo em um espaço reduzido, logo, não compromete a capacidade de generalização. Os métodos de otimização de caixa-preta (blackbox) baseados em meta-heurística ou por busca extensiva podem ser utilizados para ajuste de hiperparâmetros, contudo não fornecem propriedades de convergência matemática e um critério dinâmico de parada, o que pode resultar em resultados sub-ótimos. Desta maneira, propõe-seum método para seleção de hiperparâmetros baseado em métodos de otimização por busca direcionada. O método proposto fornece ao usuário uma flexibilidade ao permitir a escolha de parâmetros a fim de explorar diferentes estratégias e situações. Os experimentos mostram que o método proposto é menos suscetível a resultados sub- ótimo. Por fim, introduz-se uma nova variante do SVM adequada para o aprendizado incremental e decremental que integra elementos do SVM, da variação do SVM gêmeo (Twin SVM) e da teoria difusa (fuzzy ). O método proposto mantém a flexibilidade do SVM e adiciona os procedimentos de incremento e decremento. O conceito difuso incorporado realça a resistência a ruído e tende a melhorar a generalização do método proposto quando utilizamos o modelo linear. A etapa incremental pode ser utilizada em diferentes quantidades, e o procedimento decremental controla a complexidade do modelo. Segundo os resultados apresentados, o método possui uma capacidade de generalização competitiva comparada aos outros métodos de aprendizado incremental baseado em SVM. Para o desenvolvimento da tese foi realizada uma pesquisa exploratória a fim de com- preender as limitações do SVM, logo ter capacidade de formular as hipóteses. Uma pesquisa empírica foi realizada para analisar de maneira mais profunda os métodos por meio de uma pesquisa bibliográfica por meio de uma revisão sistemática. Define-se o escopo da tese como uma variante do SVM adequada para conjuntos de dados con- tínuos e de larga escala, com uma solução eficiente para ajustes de hiperparâmetros. Uma pesquisa quantitativa foi conduzida com o propósito de validação para comparar diretamente os métodos propostos com trabalhos relacionados utilizando conjuntos de dados benchmark ou criados a fim de analisar aspectos individuais, analisando as saídas de forma numérica (como a exatidão), a complexidade computacional, o tempo de processamento e o consumo de memória RAM. Questiona-se a validação em relação aos resultados do protocolo experimental e a aplicabilidade em situações reais, e foram desenvolvidos múltiplos procedimentos experimentais para suavizar a incerteza da validação interna e avaliar as variáveis com parâmetros numéricos. Nesta tese apresentamos metodologias que visam melhorar as questões de esca- labilidade, eficiência computacional e performance de generalização do SVM ou de uma variante, e todos os métodos propostos são adequados para serem utilizados em cenários reais.

Abstract: Over the past decade machine learning has become one of the mainstays of the infor- mation technology, and with the increasing amount of available data the automatically discover of patterns in data has become one of the main tasks in the field. A method to find these patterns is to estimate a data-based function and to build a successful learning function it must include: a solid theoretical background based on an induction principle, the possibility to include prior knowledge, and an efficient way to apply it in practice. In this thesis, we will focus on the Support Vector Machine (SVM) algorithm for classification tasks, which has been introduced in the mid-90s and has become popular in academic and industrial communities since then. We will analyze many aspects of the SVM, including its formulation, the training method, the hyperparameters tuning, and applicability on a range of different datasets. Based on the analysis, we propose three contributions. Given the computational complexity of the SVM, in the first contri- bution, we propose a method to make viable the usage of the SVM for large datasets (i.e., cases that the dataset does not fit on available memory) by preselecting instance candidates that are more suitable to enhance the generalization error performance. The method goal is to decrease the training and hyperparameter tuning procedures time degrading as less as possible the generalization error. The second contribution is related to the hyperparameter tuning task, that depending on the case may be time-consuming. The use of the SVM with a kernel function gives a freedom that allows to apply the method in many situations, however, choosing the hyperparameters is a downside. In this way, we propose a hyperparameters tuning method with mathematical convergence properties that uses a predefined local minima as stopping criteria and have a mechanism to escape from undesired local minima. Many attempts have been made to tackle the problems of the SVM computational cost, incremental learning, and memory consumption related to both. In the last contribution, we introduce a novel SVM-variant with a smaller computational complexity compared to the original SVM, which is able to deal with incremental and decremental procedures (without the need for full retraining) and being memory efficient. We perform exploratory research to understand the SVM limitations, so we are able to formulate our hypothesis. We did empirical research to further analyze the proposed methods through bibliography research over a systematic review. We set the thesis scope as an SVM-variant suitable for continuous and large-scale datasets with an effective hyperparameters tuning solution. We conduct quantitative research with a pro- posal validation that directly compares the proposed methods with related work using benchmark or controlled generated datasets, analyzing the numerical outputs as accu- racy, computational complexity, processing time, and RAM consumption. We question the validation regarding the results of the experimental protocol and the applicability in real-world situations. We develop multiple experimental procedures to mitigate the uncertainty of the internal validation, and we evaluate the variables with numerical parameters. To deal with large datasets in learning problems we propose a passive sampling thatselects a subset from the available training data that can be handled within time an computational resource constraints, maintaining the generalization capability. The ex- perimental protocol results shows that the proposed method preselects instances that are likely to be support vectors (and its neighbors) even in a reduced space, thus, it does not compromise much the generalization capability. Most common methods for hyperparameters tuning does not provide mathematical con- vergence properties and dynamic stopping criteria, leading to sub-optimal outcomes, in this way, the proposed model selection technique leads to an outcome less susceptible to sub-optimal results and requires inferior processing time compared to frequently used methods. The prosed method gives the user a flexibility of choosing parameters to explore different strategies and situations, and the experimental shows that the method is more likely to require less function evaluations to reach good set of hyperparameters. We introduced a novel SVM-variant suitable for incremental and decremental learning that integrates elements from many methods from literature. The proposed method keeps the SVM flexibility and adds incremental and decremental procedures. The fuzzy concept incorporated enhances noise-resistance and generalization performance when using the linear model. The incremental step can run with different batch sizes, and the decremental procedure controls the model complexity. According to the experimental results, the method presents a competitive generalization capability compared to the best methods available. In this thesis, we present methodologies that address the issues of improving scalability, computational and data efficiency, and generalization performance of the SVM or a variant, and all proposed methods are suitable to be used in real-world scenarios.