MP-SMO: an algorithm for the VLSI implementation of the support vector machines training.

Máquinas de aprendizagem, como Redes Neuronais Artificiais (ANNs), Redes Bayesianas, Máquinas de Vetores de Suporte (SVMs) e outras, são aplicadas em problemas de classificação de padrões. Devido ao baixo erro de teste, a SVM possui uma grande quantidade de aplicações, como no reconhecimento de imagens, seleção de genes, classificação de textos, robótica, reconhecimento de escrita a mão e outras. Dos algoritmos desenvolvidos para o treinamento da SVM, o Sequential Minimal Optimization (SMO) é um dos mais rápidos e o mais fácil de implementar em software. Devido a sua importância, várias otimizações para diminuir ainda mais o seu tempo de execução têm sido reportadas. A maioria das implementações do treinamento da SVM foram realizadas em software. Não obstante, a implementação em hardware é necessária em algumas aplicações com restrições: de área, e/ou de energia e/ou de tempo de treinamento, por exemplo, em algumas aplicações portáveis ou móveis. Nas implementações em hardware anteriores a este trabalho, o treinamento da SVM foi realizado com um conjunto de exemplos cuja quantidade é da ordem de somente dezenas, e unicamente uma delas usou o algoritmo SMO. Neste trabalho é apresentada uma modificação do algoritmo SMO, que denominamos algoritmo SMO de Múltiplos Pares (MP-SMO), para a aceleração do treinamento da SVM. A diminuição do tempo de treinamento é obtida realizando a otimização de um ou mais pares de coeficientes, chamados Multiplicadores de Lagrange, em cada iteração. De modo diferente, o algoritmo SMO original otimiza somente um par. O algoritmo MP-SMO apresenta as seguintes características: 1) a otimização de cada par de coeficientes é mantida simples usando a solução analítica do algoritmo SMO original. 2) as heurísticas para a seleção dos múltiplos pares a otimizar são adaptações das soluções anteriores para a seleção de um par por iteração. Testou-se o algoritmo otimizando até dois, três e quatro pares de coeficientes por iteração, e melhores resultados foram obtidos quando comparados com os do algoritmo SMO. Nos testes realizados com sete benchmarks, o tempo de treinamento diminuiu entre 22,5% e 42,8%. A diminuição do tempo de execução do algoritmo SMO em hardware é também abordada nesta dissertação. Os algoritmos SMO e MP-SMO foram completamente implementados em hardware dedicado para o benchmark Tic-tac-toe endgame. Este benchmark é composto por 958 exemplos, uma quantidade superior às usadas nas implementações anteriores. Com o algoritmo MP-SMO pretendeu-se reduzir o número de iterações, como na implementação em software, e poder incluir paralelismo na implementação em hardware. Para diminuir o tempo de execução de cada iteração, arquiteturas dos tipos pipeline e paralela foram usadas. Foram implementadas e testadas em um dispositivo do tipo FPGA (Field Programmable Gate Array) dezesseis diferentes arquiteturas no total, combinando ou não o algoritmo SMO ou o MP-SMO com pipelining e/ou paralelismo. O tempo de treinamento diminuiu no melhor caso para 1,8% do obtido com o algoritmo SMO implementado sem pipelining nem paralelismo, ou seja, diminuiu em mais de 50 vezes. Esta dissertação apresenta também a análise do custo em área e potência decorrente do aumento da velocidade de treinamento.Learning Machines, like Artificial Neural Networks (ANNs), Bayesian Networks, Support Vector Machines (SVMs) and others are applied in pattern classification problems. As the test error in SVM is small, it has several applications, such as image recognition, gene selection, text classification, robotics, handwritten recognition and others. Among the developed algorithms for the SVM training, the Sequential Minimal Optimization (SMO) is one of the fastest and the simplest to implement in software. Due to its importance, many improvements have been proposed in order to obtain even faster solutions than the original algorithm. Most of the SVM training implementations are in software. However, in some applications with restrictions of: area, and/or power and/or training time, a hardware implementation is necessary, for example, in some mobile or portable applications. In related previous works, the SVMs were trained in hardware using sets of only tens of examples, and in only one implementation the SMO algorithm was employed. In this work, a modified version of the SMO algorithm, named here the Multiple Pairs SMO (MP-SMO) algorithm, for the SVM training acceleration is presented. The training time reduction is obtained optimizing per iteration one or more pairs of coefficients known as Lagrange Multipliers, instead of only one pair as in the original SMO algorithm. The MP-SMO algorithm has the following features: 1) the optimization of each pair is as simple as in the original SMO algorithm because of the use of the same analytical method. 2) the solution for the pairs of coefficients selection can be chosen between two adapted heuristics for the SMO algorithm. The algorithm was tested optimizing up to two, three and four pairs of coefficients per iteration, and the training time was improved, when compared against the SMO algorithm. The tests for seven benchmarks showed an improvement that ranged from 22.5% to 42.8%. The reduction of the training time of the SMO algorithm executed in hardware is also treated in this dissertation. The algorithms SMO and MP-SMO were completely implemented in dedicated hardware for the Tic-tac-toe endgame benchmark. This benchmark is composed of 958 examples, a number greater than the used in the previous hardware implementations. The implementation of the MP-SMO algorithm is intended to reduce the number of iterations, as in the software implementation, and to include parallelism in the hardware implementation. In order to reduce the iteration execution time, the pipeline and parallel architectures were realized. Sixteen different architectures were implemented and tested on a Field Programmable Gate Array (FPGA) device, combining or not the SMO or MP-SMO algorithm with pipelining and/or parallelism. The training time was reduced to 1.8% of that obtained with the SMO algorithm without neither pipelining nor parallelism, that is, more than 50 times. This dissertation also presents an analysis of the area and power cost of the training speed increase