Research On Fast SVM Training Algorithm And Its Effective Parameter Selection Approach

Support Vector Machines(SVM) has became a popular machine learning method in recent years. According to the Statistical Learning Theory(SLT), the larger the margin between two classes, the lower the upper bound of SVM's generalized error will get. SVM algorithm is used to maximize the margin to ensure a small generalized error. However, in the practical usages of SVM, three issues must be solved, they are training algorithm speed, support vector storage and free-parameters selection. The current algorithm cannot meet all requirements, such as fast training speed, little memory consumption and few support vectors output. The main difficulty is that there is too many support vectors in training stage. This paper proposed a fast implement of a two-to-one method based on SV-truncating technique, and a new SVM training algorithm, named NullSVM, in which SV-truncating is embedded in SVM training. SV-truncating is performed when the number of support vectors exceeds a given threshold in NullSVM, to achieve a faster speed and less memory consumption. Though the error induced by the SV-truncating will decrease the recognition ratio, the experiments shows that it achieves a great speed up compared with traditional SVM.As for the free-parameters selection problem, Structural Risk(SR) is chosen as the evaluation function based on Structural Risk Minimization(SRM) principle in SLT. The most complex part of SR computing is the radius R of minimum enclosing ball of a vector set, with O (N~3) complexity. In this paper, the maximum distant of the vector set is used as a substitution of R, with a lower complexity O (N~2), and the error induced is under a certain bound. NullSVM has two free parameters C andσ. For a fixedσ, the feasible region of a larger C contains that of a smaller C, so it can set the solution of the small C problem as the initial value of the large C problem, to accelerate the convergence. By this, the proposed NullSVM can train a serial of C, which will be utilized by the SRM based free-parameters selection approach. In experiment, this approach is faster than the classical Cross-Validation(CV) based free-parameter selection approach by about five to ten times, and the SRM is less likely to overfitting than the classical CV approach. In addition, the recognition accuracy of the SRM based approach is less than one of CV based approach only in some special case of parameter range.