Research On Support Vector Machine Accelerated Training Algorithm

Support vector machine (SVM) is introduced by Vapnik and his co-workers based on Statistical Learning Theory (SLT). It is based on the theory of the VC dimension and the structural risk minimization principle. SVM solves the small sample problem mainly and finds the best compromise between the complexity of the model and the learning ability in order to obtaining the best generalization ability. SVM has shown successful applications in many fields. However, SVM reveals some shortcomings in practical applications, such as the large calculation, the slow training speed, and the parameters selection based on experience and so on. The slow training speed largely limits the application of SVM. Thus, on the premise of little change of classification accuracy, it has great significance in accelerating the SVM training both in theory and application fields.The main target of the thesis is: for the shortcoming of the slowly training speed about SVM, we want to find a new SVM accelerated training algorithm based on the existing SVM algorithms. The main reason of slowly training speed about SVM is that a large number of non-support vectors involved when training, then a large number of QP calculations is carried out. Based on the ideas above, we proposed an algorithm firstly in this thesis: a SVM chunking training algorithm based on the KKT conditions. It reduces the scale of the QP problem by dividing the QP problem into some sub-problems, and use KKT conditions to maintain the potential support vectors. Therefore, the SVM training is accelerated, on the premise of little change of classification accuracy. Based on this algorithm, we proposed a new algorithm: a SVM accelerated algorithm based the KKT conditions. In this algorithm, some training samples which are not relevant to building the hyperplane are removed before chunking training. From the theoretical analysis, this algorithm can remarkably reduce the computation complexity and accelerate SVM training. And experiments on both artificial and real datasets demonstrate the efficiency of these algorithms.