Approximate Model Selection on Regularization Path for Support Vector Machines

Model selection is an indispensable step to guarantee the generalization of support vector machines (SVM). The main problem of existing SVM model selection approaches is that a standard SVM needs to be solved with high complexity for each iteration. In this paper, a novel model selection approach for SVM via kernel matrix approximation and regularization path is proposed, based on the observation that approximate computation is sufficient for model selection. Firstly, a kernel matrix approximation algorithm KMA-α is presented and its matrix approximation error bound is analyzed. Then, an upper model approximation error bound is derived via the error bound of KMA-α. Under the guarantee of these approximation error bounds, an approximate model selection algorithm AMSRP is proposed. AMSRP applies KMA-α to compute a low-rank approximation of the kernel matrix that can be used to efficiently solve the quadratic programming of SVM, and further utilizes the regularization path algorithm to efficiently tune the penalty factor C. Finally, the feasibility and efficiency of AMSRP is verified on benchmark datasets. Experimental results show that AMSRP can significantly improve the efficiency of model selection for SVM, and meanwhile guarantee the test set accuracy. Theoretical and experimental results demonstrate that AMSRP is a feasible and efficient model selection algorithm.