MP-SMO: um algoritmo para a implementação VLSI do treinamento de máquinas de vetores de suporte (2009)
- Authors:
- Autor USP: HERNANDEZ, RAUL ACOSTA - EP
- Unidade: EP
- Sigla do Departamento: PSI
- Subjects: INTELIGÊNCIA ARTIFICIAL; ALGORITMOS; MICROELETRÔNICA; CIRCUITOS FPGA
- Language: Português
- Abstract: 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, varias 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 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 hardware anteriores a este trabalho, o treinamento da SVM foi realizado com um conjunto formado por somente dezenas de exemplos, e unicamente uma delas usou o algoritmo SMO. Neste trabalho é apresentada uma modificação do algoritmo SMO, chamada 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, a diferença do algoritmo SMO original que 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 obtidos com o algoritmo SMO. 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 software, e incluir paralelismo na implementação 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 diminui-se no melhor caso para 1.8% do obtido com o algoritmo SMO implementado sem pipelining nem paralelismo. Esta dissertação apresenta também a análise do custo em área e potência decorrente do aumento da velocidade de treinamento.
- Imprenta:
- Data da defesa: 02.09.2009
-
ABNT
ACOSTA HERNANDEZ, Raul. MP-SMO: um algoritmo para a implementação VLSI do treinamento de máquinas de vetores de suporte. 2009. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2009. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3140/tde-28102009-172855/. Acesso em: 19 abr. 2024. -
APA
Acosta Hernandez, R. (2009). MP-SMO: um algoritmo para a implementação VLSI do treinamento de máquinas de vetores de suporte (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3140/tde-28102009-172855/ -
NLM
Acosta Hernandez R. MP-SMO: um algoritmo para a implementação VLSI do treinamento de máquinas de vetores de suporte [Internet]. 2009 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3140/tde-28102009-172855/ -
Vancouver
Acosta Hernandez R. MP-SMO: um algoritmo para a implementação VLSI do treinamento de máquinas de vetores de suporte [Internet]. 2009 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3140/tde-28102009-172855/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
