Study On Training And Simplifying Algorithms Of Support Vector Classification

Support Vector Machines (SVMs) are new developed machine learning methodsbased on the Statistical Learning Theory (SLT). The main advantage of SVMs is that itcan serve better in the processing of small samples by substituting Structural RiskMinimization (SRM) for Empirical Risk Minimization(ERM). Moreover, SVMs cansolve practical problems such as over learning, high dimension and local minima,which exist in most of learning methods. Currently, being the optimal learning theoryfor small samples, SVMs are attracting more and more researchers and becoming ahotspot in the fields of artificial intelligent and machine learning.Today, SLT has been a transition period from theory to application, and thealgorithms of SVMs must be improved in need of practical engineering problems.Starting with an introduction to the foundational theory and an analysis of theproperties of SVMs, and aiming at the weak points of training and simplifyingalgorithms of support vector classification(SVC), the thesis proposes new methods toimprove training efficiency and speed up classification process of SVC. The mainresearch in this thesis can be classed as follows:1. Sequential minimal optimization (SMO) algorithm is a quite efficient methodfor training SVMs. However, the feasible direction strategy for selecting working setsmay degrade the performance of the kernel cache maintained in SMO. A novel strategyfor selecting working sets applied in SMO is presented to handle such difficulties, andthe SMO with the new strategy is guaranteed to converge to an optimal solution. Basedon the new working set selection strategy, the new method takes both iteration timesand kernel cache performance into consideration, which leads to decrease of thenumber of kernel evaluation. As a result, the training efficiency of the new method isimproved greatly compared with older version.2. A novel SVM training method is proposed to handle large data sets. Theapproach remove from the training set the data that is irrelevant to the final decisionfunction based on a relatively rough hyperplane, and thus the number of vectors for SVM training becomes small and the training time can be decreased sharply.Experimental results show that SVM with the selected patterns was trained much fasterwith fewer redundant support vectors, without compromising the generalizationcapability.3. Most of SVM training methods which can process very large data sets areonly empirical observations and not theoretical guarantees. A novel SVM trainingmethod, Approximate Vector Machine (AVM), based on approximate solution ispresented to overcome such difficulties. This approach only obtains an approximatelyoptimal hyperplane by incremental learning, and uses probabilistic speedup and hotstart tricks to accelerate training speed during each iterative stage. Analysis in theoryindicates that AVM has time and space complexities that are independent of trainingset size. Therefore, it is suitable to handle very large data sets.4. Reduced set method is an important approach to speed up classificationprocess of SVM by compressing the number of support vectors', included in themachine's solution. Existing works find the reduced set vectors based on solving anunconstrained optimization problem with multivariables, which may suffer fromnumerical instability or get trapped in a local minimum. A novel reduced set methodrelying on kernel-based clustering is presented to simplify SVM solution. Thisapproach is conceptually simpler, involves only linear algebra and overcomes thedifficulties existing in former reduced set methods. Experiments on real data setsindicate that the proposed method is effective in simplifying SVM solution whilepreserving machine's generalization performance.