Métodos para treinamento rápido e esparso de máquinas de vetores-suporte de mínimos quadrados: uma abordagem dual

Abstract

The least squares support vector machine model is a variant of the classical support vector machine model that employs equality constraints in the formulation of its primal problem. This allows the derivation of a linear system when applying the Karush–Kuhn–Tucker optimality conditions, considerably simplifying the training of this model when compared to the adjustment of support vector machines. However, a drawback of this formulation lies in the fact that the optimal vector of Lagrange multipliers of the problem is dense. Thus, all training patterns are considered support vectors, making the prediction stage computationally expensive when working with large datasets. In many cases, the solution of the system is obtained through the use of iterative methods based on conjugate directions, which, on the one hand, is advantageous since it avoids numerical difficulties related to matrix inversion, but, on the other hand, makes the training stage slow for datasets with high volume, as it is necessary to operate with dense kernel matrices. In this context, two new methodologies are proposed for the fast and sparse training of least squares support vector machines. In the first approach, the dual problem of least squares support vector machines is solved via a sequential minimal optimization algorithm with a new three-term conjugate descent direction which, combined with a working set selection strategy based on functional gain, allows an acceleration in convergence, reducing the number of iterations when compared to the standard sequential minimal optimization algorithm. In addition, an iterative pruning process based on the functional gain of the optimization problem is adopted in order to sparsify the obtained Lagrange multipliers. Finally, the last proposal consists of the use of a new spectral conjugate gradient method for solving the corresponding dual problem and sparsification through iterative pruning using the proximity of the pattern to the decision hyperplane as the criterion for removal. Numerical experiments carried out on several real and artificial datasets demonstrate that both approaches present competitive performance, with fast training and a high level of sparsity of the Lagrange multipliers. For binary classification datasets, the sparsity gain reached approximately 80% when compared to the total number of training samples for the considered dataset. The reduction in training time was approximately 99.9% in relation to standard least squares support vector machines. For datasets with higher volume, the proposals were the only ones that provided feasible training time with stable convergence. The quality of the decision boundaries was further analyzed for synthetic datasets, where the results indicate the generation of boundaries similar to the considered benchmarking model, confirming the predictive capability of the new methodologies. Finally, the results for regression datasets indicate that the proposal based on the spectral conjugate gradient method may be a sparse and fast-training alternative to the least squares support vector machine regression model.