【作者】 王磊；

【导师】 孙世新；

【作者基本信息】 电子科技大学 ， 计算机应用技术， 2007， 博士

【摘要】 支持向量机是建立在统计学习理论的VC维理论和结构风险最小化原则基础上的新型机器学习方法。它根据有限样本信息在模型的复杂度和期望风险之间寻求最佳折衷，能够获得更好的泛化性能。与传统的神经网络等学习方法相比，支持向量机具有泛化能力强、维数不敏感、收敛到全局最优等优点，很好地解决了前者容易出现的过学习、局部极值、维数灾难等棘手问题，因而成为近几年机器学习领域中的一个非常活跃的研究热点。然而，支持向量机是机器学习领域中相对比较新的理论，它在很多方面尚不成熟、不完善，需要进一步地研究和改进。其中，关于它的学习算法的研究是该理论的重点和难点内容之一。本文主要从提升泛化性能、提高学习速度、探索新型学习算法、增强学习过程的健壮性以及半监督学习等几个角度，对支持向量机的学习算法进行了比较系统的研究。论文的主要研究工作包括以下5个方面：1．特殊设计的集成学习算法能够提高支持向量机的泛化性能。在分析不同的样本扰动方式对于增大成员分类器之间差异性的作用之后，本文提出了两种基于二重扰动机制的集成学习算法，它们的共同特点是：均采取同时对输入特征空间和模型参数进行扰动的方式来产生成员分类器，并利用多数投票方法对它们进行组合。数值实验结果表明，两种算法均能够显著提升支持向量机的泛化性能。2．支持向量机的学习过程需要求解一个凸二次规划问题，在大样本情况下，需要的计算开销和存储开销都非常大。通过将开销分解到并行系统的多个计算节点上并行地进行处理或者通过设计并行学习算法是解决该问题的有效途径之一。本文提出了“多重三叉级联（MTC）”并行学习结构，具有反馈速度快、节点利用率高、反馈的支持向量数目多等优点；并且，基于该学习结构设计了支持向量机的并行学习算法，获得了非常高的加速比和并行效率，显著提高了学习速度。3．支持向量机的大多数学习算法都是针对其对偶优化问题进行求解，但直接针对其原始优化问题进行求解也是非常可行的。本文利用Huber函数消除原始优化目标函数中的ι₁范数后，推导得到其无约束、连续、二次可微且严格凸的γ-近似优化问题，然后采用Newton下降法进行求解，并对解的更新规则进行了推导和简化。在此基础上，提出一种能够直接在原始空间中求解支持向量机的近似最优解的快速学习算法，并对算法的收敛性、复杂度以及解的性质进行了分析。4．支持向量机采用的Hinge损失函数对噪声样本引起的罚损失没有任何限制，这是它对噪声样本敏感的根本原因。本文提出一种基于光滑Ramp损失函数的健壮支持向量机方法，能够有效抑制噪声样本对泛化性能的影响。鉴于新方法的优化问题是非凸的，首先采用CCCP过程将其变换成一系列的无约束、二次可微且严格凸的优化问题，然后采用Newton下降法在原始空间中进行求解，并对解的更新规则进行了推导和化简。在此基础上，给出了健壮支持向量机的学习算法。5．半监督支持向量机能够同时利用“标记”和“未标记”样本进行学习，但是，求解它的最优解是一个NP难问题。渐近式学习算法通过逐步地对少量样本进行标记，能够快速获得半监督支持向量机的近似解，但它也存在两个明显缺陷，严重影响了泛化性能。针对这些缺陷，本文提出一种模糊渐近式学习算法，它通过自适应地为样本设置模糊隶属度，消除了渐近过程对“不一致”样本优化的阻碍；并且采用新的算法停止条件，使得“未标记”样本中的分类信息尽量被充分利用；同时，还采用了混合训练集缩减策略，有利于提高算法的学习速度。数值实验结果表明，新算法是半监督支持向量机的一种高精度的、快速学习算法。更多还原

【Abstract】 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.更多还原