论文部分内容阅读
支持向量机(SVM)是近年来流行的机器学习方法。根据统计学习理论,SVM的推广错误率的上界随分类间隔的增大而减小。SVM算法提出的目的是最大化分类间隔,并且保证有较小的推广错误率。然而在SVM算法的实际应用中,存在着三大必须解决的问题:算法速度问题,支持向量存量问题和算法参数选择问题。目前主流的SVM优化方程和训练算法中不存在同时满足速度快、内存占用少并且支持向量少的算法,主要困难在于SVM训练过程中支持向量个数太多。本文首先对基于SV修剪技术的一种二合一方法提出一个复杂度仅为O(1)的快速实现,然后创造性地提出在SVM训练算法中嵌入该SV修剪方法的一种新SVM训练算法NullSVM。在该算法过程中,每当支持向量数超过给定阈值的时候将进行高效的SV修剪以实现同时提高算法速度、降低内存占用和得到较少的支持向量解的目的。诚然,SV修剪过程中带来的误差会对算法性能造成影响,然而实验表明,虽然NullSVM方法在部分分类问题上识别率会稍低,其速度会得到极大的提升,因此该方法能够基本解决算法速度问题和支持向量存量问题。为了解决SVM算法的参数选择问题,本文根据统计学习理论的结构风险最小化原则,选择结构风险作为评价函数,从不同的参数组合中选择出最优的参数。研究表明结构风险中计算复杂度最高的因子是向量集的最小包球半径R,其复杂度为O (N~3)。因此提出用最大向量距离D代替此R,使得计算复杂度降为O (N~2),如此的改进所产生的误差满足一定的上界。NullSVM包含两个参数C和σ,对固定的σ,较大C参数的可行域包含较小C参数的可行域,所以可以直接把较小C参数的解作为较大C参数的迭代初始值以加快算法的收敛速度。所提出的NullSVM算法能从一个小的C初始值开始,连续计算出从小到大一系列C值的解。基于结构风险评价的参数选择方案利用该特性,实现快速搜索并对一系列的参数作出评价。实验表明,此参数选择方案速度上比常用的基于交叉验证法的参数选择方案有约5倍到10倍提高,识别率更稳定并且不容易过学习,仅在某特定参数搜索范围情况下识别率稍差。