支持向量机的训练算法

风靡全球

支持向量机的训练算法

由于方法较好的理论基础和它在一些领域的应用中表现出来的优秀的推广性能,近年来,许多关于方法的研究,包括算法本身的改进和算法的实际应用,都陆续提了出来。尽管算法的性能在许多实际问题的应用中得到了验证,但是算法在计算上存在着一些问题,包括训练算法速度慢、算法复杂而难以实现以及检测阶段运算

量大等等。

传统利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的主要原因

首先,方法需要计算和存储核函数矩阵,当样本点数目较大时,需要很大的内存,例如,当样本点数目超过时,存储核函数矩阵需要多达兆内存其次,在二次型寻优过程中要进行大量的矩阵运算,多数情况下,寻优算法是占用算法时间的主要部分。

SVM方法的训练运算速度是限制它的应一的主要方面,近年来人们针对方法本身的特点提出了许多算法来解决对偶寻优问题。大多数算法的一个共同的思想就是循环迭代将原问题分解成为若干子问题,按照某种迭代策略,通过反复求解子问题,最终使结果收敛到原问题的最优解。根据子问题的划分和迭代策略的不同,又可以大致分为两类。

第一类是“块算法”。“块算法”基于的是这样一个事实,即去掉乘子等于零的训练样本不会影响原问题的解。对于给定的训练样本集,如果其中的支持向量是已知的,寻优算法可以排除非支持向量,只需对支持向量计算权值即乘子即可。实际上支持向量是未知的,因此“块算法”的口标就是通过某种迭代方式逐步排除非支持向量。具体的作法是,选择一部分样本构成工作样本集进行训练,剔除其中的非支持向量,并用训练结果对剩余样本进行检验,将不符合训练结果一般是指违反条件的样本或其中的一部分与本次结果的支持向量合并成为一个新的工作样本集,然后重新训练。如此重复下去直到获得最优结果。

当支持向量的数目远远小于训练样本数目时,“块算法”显然能够大大提高运算速度。然而,如果支持向量的数目本身就比较多,随着算法迭代次数的增多,工作样本集也会越来越大,算法依旧会变得一一分复杂。因此第二类方法把问题分解成为固定样本数的子问题工作样本集的大小固定在算法速度可以容忍的限度内,迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换,即使支持向量的个数超过工作样本集的大小,也不改变工作样本集的规模,而只对支持向量中的一部分进行优化。

固定工作样本集的方法和块算法的主要区别在于块算法的目标函数中仅包含当前工作样本集中的样本,而固定工作样本集方法的优化变量虽然仅包含工作样本,其目标函数却包含整个训练样本集,即工作样本集之外的样本的乘子固定为前一次迭代的结果,而不是像块算法中那样设为。而且固定工作样本集方法还涉及到一个确定换出样本的问题因为换出的样本可能是支持向量。这样,这一类算法的关键就在于找到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果。