面向超大数据集的SVM近似训练算法

标准SVM学习算法运行所需的时间和空间复杂度分别为O(l3)和O(l2),l为训练样本的数量,因此不适用于对超大数据集进行训练。提出一种基于近似解的SVM训练算法:Approximate Vector Machine(AVM)。AVM采用增量学习的策略来寻找近似最优分类超平面,并且在迭代过程中采用热启动及抽样技巧来加快训练速度。理论分析表明,该算法的计算复杂度与训练样本的数量无关,因此具有良好的时间与空间扩展性。在超大数据集上的实验结果表明,该算法在极大提高训练速度的同时,仍然保持了原始分类器的泛化性能,并且训练完毕具有较少的支持向量,因此结果分类器具有更快的分类速度。