| Resumo: Através das últimas décadas a área de aprendizado de máquina tem se tornado um dos pilares da tecnologia da informação, e com o aumento crescente da quantidade de dados disponíveis, a tarefa de automaticamente descobrir padrões nos dados é uma das principais atividades da área. Um método para achar esses padrões é estimar uma função baseada em dados, e para criar uma função com sucesso de aprendizagem é necessária conter os seguinte tópicos: uma base teórica sólida baseada no princípio da indução, a possibilidade de incluir conhecimento passado, e um método eficiente para ser utilizado na prática. Nesta tese nosso foco é no algoritmo de Máquina de Vetores de Suporte (Support Vector Machine, SVM) para tarefas de classificação, introduzido por (BOSER; GUYON; VAPNIK, 1992) (VAPNIK, 1998) em meados dos anos 90. Nós iremos 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 configurações. Baseado nessas análises, nós fizemos três propostas de contribuição.
Dada a complexidade computacional do SVM, na primeira contribuição, nós propusemos um método para viabilizar o uso do SVM em grandes conjuntos de dados (casos que o conjunto de dados em questão não cabe na memória disponível) através da pré-seleção de instâncias candidatas que são mais prováveis 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 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 um ponto negativo. Desta forma, nós propomos um método para ajuste dos hiperparâmetros com propriedades de convergência matemática que utiliza um mínimo local pré-definido como critério de parada, e possui um mecanismo para escapar de eventuais locais mínimos indesejados.
Muitas tentativas foram feitas para atacar os problemas do SVM relacionados ao custo computacional, aprendizado incremental e consumo de memória relacionado a ambos. Na última contribuição, nós introduzimos uma nova variação do SVM com uma complexidade computacional menor comparado ao SVM original, que é capaz de lidar com procedimentos incrementais e decrementais (sem a necessidade de re-treinar completamente), e é eficiente na gestão de memória.
Nós realizamos uma pesquisa exploratória para compreender as limitações do SVM, para que sejamos capazes de formular nossas hipóteses. Fizemos uma pesquisa empírica para analisar de maneira mais profunda os métodos através de uma pesquisa bibliográfica por meio de uma revisão sistemática. Definimos o escopo da tese como uma variante do SVM adequada para conjuntos de dados contínuos e de larga escala, com uma solução eficiente para ajustes de hiperparâmetros. Nós conduzimos uma pesquisa quantitativa, com o propósito de validação, que compara diretamente os métodos propostos com trabalhos relacionados utilizando conjuntos de dados referência ou criados de maneira controlada, 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. Nós questionamos a validação em relação aos resultados do protocolo experimental e a aplicabilidade em situações reais. Nós desenvolvemos múltiplos procedimentos experimentais para suavizar a incerteza da validação interna e avaliar as variáveis com parâmetros numéricos.
A fim de lidar com grande conjuntos de dados nos problemas de aprendizado nós propomos um método amostragem passiva que seleciona um sub-conjunto dos conjunto 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 muito a capacidade de generalização.
A maioria dos métodos de ajuste de parâmetros não fornece propriedades de convergência matemática e um critério dinâmico de parada, o que pode resultar em resultados sub-ótimos. Desta maneira, nosso método proposto para seleção de modelo é menos suscetível a resultados sub-ótimos e exige um menor tempo de processamento comparado aos outros métodos. 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 é mais provável a utilizar menos avaliações de funções para obter um bom conjunto de hiperparâmetros.
Nós introduzimos uma nova variante do SVM adequada para o aprendizado incremental e decremental que integra elementos de vários metódos da literatura. 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 à ruído e melhora a performance da generalização 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 melhores métodos disponíveis.]
Nesta tese apresentamos metodologias que visam melhorar as questões de escalabilidade, 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. |
