O algoritmo Sequential Minimal Optimisation para resolução do problema de Support Vector Machine : uma técnica para reconhecimento de padrões

Abstract

Resumo: O presente trabalho tem por finalidade estudar o algoritmo Sequential Minimal Optimization (SMO) para resolução do problema quadrático do Support Vector Machine (SVM), uma técnica de reconhecimento de padrões. Diagnosticar doenças, automatizar processos de leitura de documentos, identificar pessoas, encontrar substâncias adulterantes em produtos são algumas aplicações de reconhecimento de padrões. Existem muitas técnicas de reconhecimento de padrões, porém, são limitadas a um conjunto de problemas. O SVM é uma técnica que utiliza a metodologia de aprendizagem supervisionada para o treinamento do processo de reconhecimento de padrões. A modelagem do problema do SVM envolve um problema quadrático convexo e, portanto, existe uma única solução, porém a busca dessa solução requer ferramentas complexas. A técnica de reconhecimento SVM tem como objetivo separar os padrões em classes distintas através de uma superfície separadora, esta com a maior distância possível das margens, que definem uma segurança na classificação de novos dados. As margens são determinadas pelos vetores suportes, definidos pelo valor de seu respectivo Multiplicador de Lagrange, proveniente da modelagem dual. O produto interno que aparece no problema dual pode ser substituído por uma função kernel que possibilita encontrar uma superfície separadora não linear, abrangendo mais aplicações. A utilização desta requer a escolha de uma função kernel adequada e a calibração dos parâmetros para que o processo apresente menos erros e generalize a situação. Para obtenção da solução do SVM utilizou-se o algoritmo SMO, desenvolvido por Platt, que escolhe dois pontos por iteração para fazer a otimização. Foram realizados treinamentos e testes em bancos de dados prontos resultando em processos de classificação muito bons se comparados com outras técnicas de reconhecimento de padrões.

Abstract: The purpose of this work is to study the Sequential Minimal Optimization (SMO) algorithm for solving the quadratic problem of Support Vector Machine (SVM), a technique for pattern recognition. Some applications of recognition are diagnosing diseases, automating the process of reading documents, identifying persons, finding adulterating substances in products. There are many techniques for achieving pattern recognition, each one limited to a set of problems. The SVM is a technique that uses the supervised learning methodology for training the process of pattern recognition. The model of SVM problem involves a convex quadratic problem and therefore, there exists a unique solution. However, for finding the solution it’s necessary using complex tools. The technique of SVM has the objective of separating the patterns in distinct classes through a separating surface with the maximum distance from margin in order to obtain better results when classifying new data. The margins are determined by the support vectors, which are obtained calculating the Lagrange Multipliers in the dual model. The inner product that appears in the dual problem may be substituted by kernel function to find a non linear surface, boosting the possible applications. To obtain a good generalization and make fewer errors it is necessary to use an adequate kernel function and calibration of the parameters. To obtain the solution of the quadratic problem of SVM it was used the SMO algorithm developed by Platt, which chooses two points in each iteration for optimization. Many training experiments were made in data base resulting in good classification performance when compared with other pattern recognition methods.