加快SMO算法训练速度的策略研究

摘要

支持向量机(SVM)是以Vapnik的统计学习理论为基础，以结构风险最小化(SRM)为原则的新型学习机。它克服了神经网络的一些缺点，如过学习，维数灾难，易陷入局部最优等。因此，它成为目前机器学习领域的一个热门研究课题。当前对SVM的研究集中在训练算法的设计和应用上。大量的研究表明，作为一种解决模式识别问题和非线性函数的回归估计、预测等问题的新技术，sVM无论在模型拟合效果还是模型推广能力方面都表现出了良好的性质。而序贯最小优化(Sequential Minimal Optimization，SMO)则是一种著名的SVM训练算法，它使得SVM问题的求解摆脱了内存的限制，避免了子问题求解的误差积累。但是当面对大规模一般特点训练数据时，SMO训练速度十分缓慢。本文研究重点是提高SMO的收敛速度。我们的创新工作主要有以下几点： 大量的实验结果表明，SMO收敛速度慢的根本原因是SMO迭代后期当解空间缩小时而工作集搜索空间不变；由此我们以目标函数改变量为依据，在SMO迭代后期适当的减小工作集选择范围。该策略明显减少了很多无效的迭代，显著的缩短了SMO的训练时间，对大样本数据更是表现出了优秀的性能。 其次，考虑到在SVM的优化过程中并不是所有样本都能影响优化进展；因此在SVM<, Light>中的Shrinking策略的基础上，结合SMO选择工作集的特点，我们在SMO的迭代过程中实行改进的Shrinking策略，用来启发式的删除那些可能对优化进展没有影响的样本，以节省训练时间，增强SMO的抗干扰能力。我们提出了两种删除样本策略，一种是基于距离，一种是基于拉格朗日乘子的值。 最后通过对SMO每一轮优化过程中有效的工作集个数的分析，我们认为SMO的停止条件不能准确的判断出优化进展程度。结合目标函数改变量，我们引进一个阈值，用来在SMO迭代后期准确的识别出优化所处的阶段，以适当的废弃那些不能引起优化进展的循环。实验表明该策略可以在损失一点点精度的情况下，大大的提高大规模训练数据的训练速度。在几个著名的数据集的实验结果表明，本文提出的这些方法可以大大缩短SMO的训练时间，特别适用于大样本支持向量较多的数据。

目录

文摘

英文文摘

华南理工大学学位论文原创性声明及学位论文版权使用授权书

第一章 绪论

第二章 SVM模型及基于分解的主流训练算法

第三章 SMO分解算法

第四章 SMO的研究现状及其分析

第五章 改进的SMO算法

结论

参考文献

攻读学位期间已发表论文

致谢