支持向量机的序列最小优化学习算法研究

摘要

本文研究了支持向量机(SupportVectorMachine，SVM)的序列最小优化算法(SequentialMinimalOptimization，SMO)[2]，并对算法进行了改进，分别应用于线性SVM和GaussianSVM上. 论文共分四节.第一节概述了论文研究的背景、训练SVM的分解算法的发展历史以及本论文在SMO算法改进上所做的工作. 第二节是SVM及其训练问题的数学描述.SVM训练问题归结为解一个带有线性等式和不等式约束的大规模凸二次规划问题：首先给出当训练样本线性可分时由训练SVM得到的原始优化问题，并得出其对偶问题.继而引出当训练样本不可分时，把原样本空间映射到一个线性可分的高维空间，通过引入核函数构造对偶问题.最后说明允许错分样本时的训练问题. 第三节重点分析SMO算法，研究了SMO算法的理论基础、算法的推导过程(包括用解析法求解带约束的子规划问题和每次成功优化后相关变量的更新)以及每个子规划问题优化变量的选择策略. 第四节先指出了原始SMO算法的缺陷：即核函数计算量太大占用了算法大量时间；子规划问题的第一个优化变量选取过于随机，从而影响整个算法收敛速度.之后，针对上面的缺陷分别对原始的SMO算法进行了改进，把输入样本数据预处理为适当的稀疏矩阵形式；选择第一个优化变量时使对偶问题目标函数的增加量最大，选择第二个优化变量时则在原始SMO算法的可供选择样本范围上加了违反KKT条件的约束.最后对原始的和改进的SMO算法进行了MATLAB仿真，从adult-la和tic-tac-toe这两个Benchmark问题中选择中等规模的两个样本集(adult-la中前500个样本，tic-tac-toe的全部958个样本)进行试验，试验结果表明，不论对线性SVM的训练还是对GaussianSVM的训练，在时间和迭代次数上改进算法均比原始算法少得多.

目录

原创性声明及关于学位论文使用授权的声明

摘要

第一节前言

第二节SVM及其训练问题

第三节SMO算法

第四节SMO算法的改进和基准问题的仿真

结束语

参考文献

致谢