VANESSA TEREZINHA ALES O ALGORITMO SEQUENTIAL MINIMAL OPTIMISATION PARA RESOLUÇÃO DO PROBLEMA DE SUPPORT VECTOR MACHINE: UMA TÉCNICA PARA RECONHECIMENTO DE PADRÕES Dissertação apresentada ao Curso de Pós- Graduação em Métodos Numéricos em Engenharia – Programação Matemática, Setores de Tecnologia e Ciências Exatas, Universidade Federal do Paraná, como requisito parcial à obtenção do título de Mestre em Ciências. Orientador: Prof. Dr. Celso Carnieri CURITIBA 2008 TERMO DE APROVAÇÃO VANESSA TEREZINHA ALES O ALGORITMO SEQUENTIAL MINIMAL OPTIMIZATION PARA RESOLUÇÃO DO PROBLEMA DE SUPPORT VECTOR MACHINE: UMA TÉCNICA DE RECONHECIMENTO DE PADRÕES Dissertação aprovada como requisito parcial para obtenção do grau de Mestre no Curso de Pós-Graduação em Métodos Numéricos em Engenharia, setores de Tecnologia e Ciências Exatas da Universidade Federal do Paraná, pela seguinte banca examinadora: ______________________________________________________ Orientador: Prof. Dr. Celso Carnieri Programa de Pós-Graduação em Métodos Numéricos em Engenharia - UFPR ________________________________________________________________ Prof. Dr. Arinei Carlos Lindbeck da Silva Programa de Pós-Graduação em Métodos Numéricos em Engenharia - UFPR ________________________________________________________________ Prof. Dr. Alexandre Rasi Aoki Programa de Pós Graduação em Engenharia Elétrica – UFPR e LACTEC ________________________________________________________________ Prof. Dr. Alessandro Lameiras Koerich Programa de Pós Graduação em Informática Aplicada – PUCPR Curitiba, 24 de Setembro de 2008 A Deus. A meus pais Moises e Terezinha, por toda a dedicação, amor, carinho e incentivo, em todos os momentos. Aos meus irmãos Wellington e William. E a todos, que de muitas formas me incentivaram e ajudaram para que fosse possível a concretização deste trabalho. Justamente quando você conseguir encontrar todas as respostas, mudarão todas as perguntas. Paulo Coelho A vitória mais bela que se pode alcançar é vencer a si mesmo. Santo Inácio de Loyola AGRADECIMENTOS A Deus, pela vida, benção, graças e proteção. Aos meus pais, Moises e Terezinha, pelo constante apoio, incentivo, carinho e compreensão. Aos meus irmãos pela amizade e apoio. Ao professor Celso Carnieri pela oportunidade, orientação, apoio, incentivo e paciência. Ao professor Arinei Carlos Lindbeck da Silva pela oportunidade, apoio, incentivo, ensinamentos da linguagem Visual Basic. Aos professores Sergio Scheer, Maria Teresinha Arns Steiner, Volmir Wilhelm, Luis Antonio Resende Santana, Neida Volpi, Liliana Cumin e Anselmo Chaves Neto, por contribuírem com a minha formação. A secretária Maristela Brandil pelo apoio, carinho e amizade. Ao amigo Vinícius, pelo incentivo e apoio, cuja amizade e companheirismo foram essenciais. Aos colegas que se tornaram amigos: Ana Beatriz, Ricardo, Wyrllen, Alessandra, Francisco, Marcos Aurélio, Bernadete, Maiko, Roberta, Vanderlei e Crisiane cuja amizade e colaboração foram fundamentais. Aos demais colegas que colaboraram no desenvolvimento da dissertação. À Pró-Reitoria, pelo apoio financeiro com a bolsa de estudos. A todos que me proporcionaram oportunidades para aquisição de conhecimentos e apoiaram meus estudos. Vanessa Terezinha Ales 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. Palavras chaves: Support Vector Machine. Kernel. Dualidade. Reconhecimento de padrões. Programação quadrática. 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. Key works: Support Vector Machine. Kernel. Duality. Pattern recognition. Quadratic programming. LISTA DE SIGLAS AG – Algoritmos Genéticos ESVM – Evolutionary Support Vector Machine GSVM – Generalized Support Vector Machine KDD – Knowledge Discovery in Databases KKT – Karush-Kuhn-Tucker LSVM – Lagrangian Support Vector Machine LS-SVM – Least Squares Support Vector Machine PSVM – Proximal Support Vector Machine RNA – Redes Neurais Artificiais RSVM – Reduced Support Vector Machine SVM – Support Vector Machine SVR – Support Vector Regression SMO – Sequential Minimal Optimization SSVM – Smooth Support Vector Machine S³VM – Semi-Supervised Support Vector Machine VC – Validação Cruzada VS – Vetores suportes VS-bound – Vetores suportes com valor máximo ν-SVM – ν- Support Vector Machine LISTA DE SÍMBOLOS λ – Autovalor i b – Bias y – Entrada i S – Conjunto de dados de treinamento ∂f – Derivada parcial da função f em relação a variável w ∂w n – Dimensão do espaço de entrada N – Dimensão do espaço feature E – Erro do ponto xi no espaço feature i (cid:92)n – Espaço de Entrada F – Espaço feature K(x,z) – Função kernel entre os pontos x e z β – Índices na função da análise de discriminante i L – Lagrangeano Dual W – Lagrangeano Primal ϕ:X →F – Mapeamento para o espaço feature γ – Margem funcional α – Multiplicador de Lagrange do ponto xi ou variáveis duais i ⋅ – Norma p p l – Número de pontos de treinamento C – Parâmetro de ponderação dos erros σ – Parâmetro do kernel gaussiano p – Parâmetro do kernel polinomial κ – Parâmetro do kernel sigmoidal k – Parâmetro kernel polinomial não homogêneo e sigmoidal β – Pesos da função discriminante xi – Ponto i do espaço de entrada x⋅z – Produto interno ξ – Variável de folga do ponto xi i w – Vetor de pesos π,π – Classes distintas 1 2 Σ ,Σ – Matrizes de covariância das classes π e π 1 2 1 2 μ , μ – Vetores de média das classes π e π 1 2 1 2 S , S – Matrizes de covariâncias amostrais das classes π e π 1 2 1 2 μ ,μ – Vetores de média amostral das classes π e π 1 2 1 2 sgn(f (x)) – Sinal da função f (x) (λ,e ) – Autovalor e autovetor i i