基于可加性核的快速支持向量机分类算法的研究

摘要

支持向量机(SVM)是机器学习中一种非常有效且流行的学习工具。由于它具有很好的泛化性能，已经被广泛的应用于各种应用领域。然而随着科技的不断发展，数据集的规模越来越大，SVM对大规模数据集进行快速的分类面临着巨大的挑战。线性SVM能够解决大规模的问题，但准确率比较低。非线性分类虽然准确率比较高但是训练时间比较长。而基于可加性核的SVM可以利用线性分类的有效性来快速求解非线性的SVM问题同时能达到较高的分类准确率。随机梯度下降算法(SGD)是求解大规模机器学习问题的高效方法之一。本文主要研究用SGD以及一些改进的SGD方法包括ASGD、SVRG和Katyusha算法来解决基于可加性核的SVM分类问题。本文的主要工作包括以下两个方面：
　　一方面，基于可加性核的性质以及Nesterov的加速策略思想提出了用ASGD解基于可加性核的SVM分类问题的算法，即ASGD-AKSVM算法。该算法避免了直接计算梯度更新中涉及到的权重向量与样本的内积，而是利用表示定理和可加性核的性质把此内积写成单变量函数的累加和的形式，进而根据闭区间上连续实值函数的逼近定理用多项式函数来近似此单变量函数。这大大降低了计算复杂度，缩短了训练时间。同时该算法采用了Nesterov的加速策略提高了收敛速度，以及采用查表技巧缩短了训练和测试时间并节省了内存使用。通过实验证明了ASGD-AKSVM算法能够有效处理大规模数据，并且具有较高的分类准确率和较快的收敛速度。
　　另一方面，基于减小方差的随机梯度方法SVRG和改进的梯度修正方法Katyusha提出了K-AKSVM算法，即用减小方差的随机梯度方法解基于可加性核的非线性SVM分类问题。该算法根据可加性核的性质把梯度近似成多项式函数，从而降低了梯度的计算复杂度，然后采用了SVRG算法的减小方差策略和Katyusha算法的修正方法，有效提高随机梯度算法的收敛速率。并通过在标准数据集上进行实验验证了算法的有效性。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 支持向量机分类的应用领域

1.4 本文的研究内容及安排

第二章 支持向量机及常用的分类算法

2.1 支持向量机

2.2 常用的SVM分类算法

第三章 SGD算法解基于可加性核的SVM分类问题

3.1 可加性核

3.2 梯度近似

3.3 SGD方法解基于可加性核的SVM分类问题

3.4 加速SGD方法解基于可加性核的SVM分类问题

3.5 实验结果分析

第四章 SVRG算法解基于可加性核的SVM分类问题

4.1 SVRG算法

4.2 SVRG算法解基于可加性核的SVM分类问题

4.3 实验结果分析

第五章 总结与展望

5.1 工作总结

5.2 工作展望

参考文献

致谢

作者简介