A análise de métodos de decomposição para máquinas de vetor de suporte

A máquina de vetor de suporte (SVM) é uma técnica nova e promissora para reconhecimento de padrões. Ela requer a solução de um grande problema de programação quadrática densa. Métodos tradicionais de otimização não podem ser aplicados diretamente devido a restrições de memória. Até agora, muito poucos métodos conseguem lidar com o problema de memória, e um importante é o "método de decomposição." No entanto, não há prova de convergência até o momento. Neste artigo, conectamos esse método aos métodos de gradiente projetado e fornecemos provas teóricas para uma versão dos métodos de decomposição. Também é fornecida uma extensão para a formulação com restrições de limite da SVM. Em seguida, mostramos que essa prova de convergência é válida para métodos de decomposição gerais se a seleção do conjunto de trabalho atender a um requisito simples.