Research On The Learning Algorithm Of Support Vector Machines

Support vector machine (SVM) is a novel and powerful machine learning approach developed in the framework of statistical learning theory, which bases on the VC theory and the principle of structural risk minimization. It always performs well in many practical applications with high generalization because of its better trade-off between the complexity of machines and empirical risks. Compared with traditional learning approaches, such as Neural Network, SVM holds the advantages of good generalization, being insensitive to high dimension data and convergence to global optimum, so it solves the intractable problems of the former, such as over-learning, local minima, dimension curse etc. Currently, SVM is attracting more and more researchers and becoming a new active hotspot in the fields of artificial intelligence and machine learning.However, being a new theory, many aspects of SVM are immature and incomplete currently, and more researches and improvements should be done. In all of them, the research of learning algorithms of SVM is a more important and challenging one. In this paper, we make comprehensive studies on the learning algorithms of SVM, from the points of improving generalization performance, accelerating speed, exploring new-type algorithms, enhancing the robustness of learning as well as realizing semi-supervised learning.The main works of this paper include the following five parts:1. The well-designed ensemble learning algorithm can improve the generalization performance of SVM. Based on the analyses of the effects of several disturbance mechanisms on augmenting the diversity among classifiers, we propose two novel ensemble learning algorithms for effectively improving the generalization performance of SVM. The common character of them is that each member classifier is trained in a randomly selected feature subspace with randomly selected model parameters and then the finial decision is made by the majority voting procedure among them. The experimental results show that both algorithms have the ability of improving the generalization performance of SVM significantly.2. The learning process of SVM needs to solve a convex quadratic programming, but both the computational costs and the storage costs are high for large-scale datasets. Hence, the parallel learning algorithms are very suitable for training SVM in such scenarios by splitting the costs into the multiple nodes (CPU processors) of the parallel system. A novel "multi-trifurcate cascading (MTC)" architecture is proposed in this paper, which holds the advantages of fast feedback, high utilization rate of nodes, and more feeding support vectors. Meanwhile, a parallel learning algorithm of SVM is designed based on the MTC architecture. The experimental results show that the proposed algorithm obtains very high speedup and efficiency, and significantly improves the training speed of SVM.3. Most learning algorithms of SVM focus on solving its dual optimization effectively, however it can also been trained by solving its primal optimization directly. In this paper, an unconstraint, continuous, twice-differentiable and strictly convex optimization is obtained by utilizing the Huber function to remove the l₁ -norm in the objective of the primal one, which is called the y- approximation of the original primal optimization. Then, the approximation is solved by the Newton method and the updating rule of the solution is deduced and simplified. After that, a fast learning algorithm of SVM is proposed, which solves the approximate solution of SVM in the primal space directly. Finally, the convergence, the complexity and the properties of the solution are analyzed.4. The essential reason of the sensitivity of SVM to noise is that the adopted Hinge loss function has no limits on the penalty loss of noise samples, In this paper, a novel robust support vector machine is proposed based on the new smooth Ramp loss function, which is much insensitive to noise and yields better generalization performance. Since the optimization of robust SVM is non-convex, the CCCP procedure is utilized to transform it into a series of unconstraint, twice-differentiable and strictly convex optimizations, and then the Newton method is used to solve these optimizations. Finally, the learning algorithm of robust SVM is designed on the basis of the deduced updating rule of the solution. 5. Semi-supervised SVM makes use of the "labeled" and the "unlabeled" samples simultaneous. However, solving the optimal solution of it is a NP-hard problem. The progressive learning algorithm can solve the approximate solution of semi-supervised SVM quickly by only labeling few unlabeled samples in each of its iterations. However, such algorithm has two serious deficiencies that cause the loss of the generalization significantly. To settle these deficiencies, a fuzzy progressive learning algorithm is proposed in this paper, which holds three important improvements: (1) setting fuzzy factor for each "semi-labeled" sample so that the phenomenon that the progressive process would impede the optimization of "inconsistent" samples can be avoided; (2) adopting a new stopping condition so that the algorithm can make fully use of the classification information in the "unlabeled" samples; (3) reducing the training set so that the algorithm can be accelerated. Finally, the experimental results show that the fuzzy progressive learning algorithm proposed in this paper is an accurate and fast one for training semi-supervised SVM.